FsharpFsharp

An interpreter for a meaningful subset of F#, written in F# — a lexer, an offside-aware (indentation-sensitive) parser, and a tree-walking evaluator, with a comprehensive test suite that pins behaviour to genuine F# semantics.

The name is the joke: F# implementing F#.

Layout

Path	Purpose
src/FsharpFsharp/Ast.fs	AST (Expr, Pattern)
src/FsharpFsharp/Value.fs	Runtime Value type + Env
src/FsharpFsharp/Lexer.fs	Tokenizer with line/column + SpaceBefore tracking
src/FsharpFsharp/Parser.fs	Recursive-descent, offside-rule parser
src/FsharpFsharp/Evaluator.fs	Tree-walking evaluator + built-in library
src/FsharpFsharp/Interpreter.fs	parse / run / display entry points
src/FsharpFsharp.Cli	Command-line runner / evaluator
tests/FsharpFsharp.Tests	xUnit suite (lexer, parser, evaluator, programs, errors, regressions)

Build & test

dotnet test                       # run the whole suite
dotnet run --project src/FsharpFsharp.Cli -- -e "1 + 2 * 3"
echo 'let rec f n = if n<=1 then 1 else n*f(n-1)
f 5' | dotnet run --project src/FsharpFsharp.Cli

Supported language subset

• Literals: int, float (incl. exponents like 2.5e3), string (with escapes), char 'a', bool, unit ()
• Bindings: let / let rec / mutually-recursive let rec … and …, light indentation syntax and let x = e in body, let mutable x = e, tuple/pattern destructuring let (a, b) = e
• Functions: fun x y -> e, let f x y = e, full currying, partial application and closures; parameters and bindings may carry (ignored) type annotations (x: int) / let f x : int =
• Control flow: if/then/elif/else, match/with (incl. when guards, as-patterns, or-patterns A | B), the function shorthand; while … do, for i = lo to/downto hi do, for pat in seq do; begin/end
• Patterns: wildcard, variable, literals (incl. negative ints, floats, chars), unit, cons h :: t, list [a; b], tuple (a, b), constructor Some x / Node (l, r), record { X = a; Y = b }
• Types: discriminated unions type T = A | B of int * string and records type R = { X: int; Y: int } with { X = 1; Y = 2 }, field access r.X, functional update { r with X = 9 }; user exception Name of T
• Options / results: Some/None/Ok/Error, Option.*, Result.*, and option-returning List.tryFind/tryHead/tryItem/tryPick/choose
• Operators: + - * / % (ints and floats), string +, comparisons = <> < > <= >=, short-circuit && ||, :: and @, pipes |> <| ||>, composition >> <<, unary minus, ref ! :=, operator sections like (+) and (*)
• Data: lists [..], arrays [| .. |] with indexing a.[i] and mutation a.[i] <- v, integer ranges a..b, tuples, list/array comprehensions [for x in xs -> e] / [for … do … yield …], sequencing by newline or ;
• Exceptions: failwith, raise, try … with (incl. Failure msg and user cases), try … finally
• String interpolation: $"…{expr}…"
• Built-ins: not fst snd id ignore failwith raise compare abs sign max min sqrt pown float int string ref; the printf/printfn/sprintf family (%d %i %s %f %g %e %b %A %O %%); String.length String.concat; and much of the List and Array modules (map mapi map2 filter fold foldBack reduce collect length rev head tail last isEmpty append concat sum max min exists forall contains find init replicate iter zip unzip sort sortBy partition take skip distinct …)

How it stays faithful

The interpreter was hardened by differential testing against dotnet fsi: snippets are run through both this interpreter and the real F# compiler, and any divergence within the supported subset is treated as a bug. That process caught and fixed subtleties such as sprintf "%e"/"%g" formatting, string 3.0 → "3", string true → "True", float exponent literals, the (*) operator section vs. block comments, f -5 negative-literal arguments, leading-operator line continuation in pipelines, x |> fun x -> ..., and the optional leading | in match/function.

Example

let rec qsort xs =
    match xs with
    | [] -> []
    | pivot :: rest ->
        let smaller = List.filter (fun x -> x < pivot) rest
        let larger  = List.filter (fun x -> x >= pivot) rest
        qsort smaller @ [pivot] @ qsort larger

qsort [3; 1; 4; 1; 5; 9; 2; 6]   // [1; 1; 2; 3; 4; 5; 6; 9]

And a small expression-language interpreter — discriminated unions, records, options, pattern matching and record update, all interpreted by FsharpFsharp:

type Expr =
    | Num of int
    | Var of string
    | Add of Expr * Expr
    | Mul of Expr * Expr
    | Let of string * Expr * Expr

type Env = { Bindings: (string * int) list }

let rec lookup name bindings =
    match bindings with
    | [] -> None
    | (k, v) :: rest -> if k = name then Some v else lookup name rest

let rec eval env e =
    match e with
    | Num n -> n
    | Var x ->
        match lookup x env.Bindings with
        | Some v -> v
        | None -> failwith ("unbound: " + x)
    | Add (a, b) -> eval env a + eval env b
    | Mul (a, b) -> eval env a * eval env b
    | Let (x, v, body) ->
        let value = eval env v
        eval { env with Bindings = (x, value) :: env.Bindings } body

// let x = 6 in let y = 7 in x * y + 1
eval { Bindings = [] }
     (Let ("x", Num 6, Let ("y", Num 7, Add (Mul (Var "x", Var "y"), Num 1))))   // 43