Skip to content

Instantly share code, notes, and snippets.

@chshersh
Last active February 5, 2024 14:15
Show Gist options
  • Save chshersh/6d354c0a3a9a4120a30226f26853653f to your computer and use it in GitHub Desktop.
Save chshersh/6d354c0a3a9a4120a30226f26853653f to your computer and use it in GitHub Desktop.
An OCaml pretty-printer and parser for Untyped Lambda Calculus
(* Type *)
type expr =
| Var of string
| App of expr * expr
| Lam of string * expr
(* Pretty printer *)
let rec pretty = function
| Var x -> x
| App (l, r) -> Printf.sprintf "(%s) (%s)" (pretty l) (pretty r)
| Lam (x, body) -> Printf.sprintf "λ%s.(%s)" x (pretty body)
(* Parser *)
open Angstrom
let parens_p p = char '(' *> p <* char ')'
let name_p =
take_while1 (function 'a' .. 'z' -> true | _ -> false)
let var_p = name_p >>| (fun name -> Var name)
let app_p expr_p =
let ( let* ) = (>>=) in
let* l = parens_p expr_p in
let* _ = char ' ' in
let* r = parens_p expr_p in
return (App (l, r))
let lam_p expr_p =
let ( let* ) = (>>=) in
let* _ = string "λ" in
let* var = name_p in
let* _ = char '.' in
let* body = parens_p expr_p in
return (Lam (var, body))
let expr_p: expr t =
fix (fun expr_p ->
var_p <|> app_p expr_p <|> lam_p expr_p <|> parens_p expr_p
)
let parse str =
match parse_string ~consume:All expr_p str with
| Ok expr -> Printf.printf "Success: %s\n%!" (pretty expr)
| Error msg -> failwith msg
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment