lisper.fsx

open System
open System.Text.RegularExpressions

type Expr =
    | Int of int
    | Symbol of string
    | Exprs of Expr list

(* convert a string into a list of tokens (include parentheses, remove whitespace) *)
let tokenize (str: string) =
    (* split on parentheses (capture them), spaces and newliness (but remove those) *)
    Regex.Split(str, "(\(|\))| +|\n+")
    |> Array.filter (fun x -> x <> "")
    |> Array.toList

(* parse a list of tokens into an AST *)
let parse (tokens: string list) =
    let parseToken (token: string) : Expr =
        match Int32.TryParse token with
        | true, i -> Int i
        | false, _ -> Symbol token

    let rec aux (tokens: string list) (depth: int) =
        match tokens with

        | [] when depth > 0 -> failwith ("balance your parentheses, missing some `)`")

        | [] -> [], []

        | "(" :: xs ->
            let parsed, remaining = aux xs (depth + 1)
            let r', r'' = aux remaining depth
            Exprs(parsed) :: r', r''

        | ")" :: xs ->
            if depth <= 0 then
                failwith ("balance your parentheses, too many `)`")

            [], xs

        | x :: xs ->
            let parsed, remaining = aux xs depth
            parseToken x :: parsed, remaining

    let parsed, remaining = aux tokens 0
    assert (remaining.IsEmpty)
    parsed

(* allows for more than one top-level expression *)
let lastExpression =
    """
    hello
    ()
    (1)
    (2 3)
    (first (list 1 (+ 2 3) 9))
    """
    |> tokenize
    |> parse
    |> Seq.last


let expected =
    Exprs [ Symbol "first"
            Exprs [ Symbol "list"
                    Int 1
                    Exprs [ Symbol "+"; Int 2; Int 3 ]
                    Int 9 ] ]

if lastExpression <> expected then
    failwith
        $"""

actual:
{lastExpression}"

expected:
{expected}
"""