Building a REPL

• Step 01

  The Expression Type

  A REPL evaluates expressions. We start with a tiny language: integer literals, addition, let-bindings, and variables. Four constructors is all we need.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  ▶ Try it

  Step 02

  Values and Environments

  Evaluation produces values. For now, just integers. An environment maps variable names to their values using a simple association list.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  ▶ Try it

  Step 03

  The Evaluator

  Pattern matching makes the evaluator beautifully direct. Each expression form maps to a straightforward computation. Let-bindings extend the environment for the body expression.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  ▶ Try it

  Step 04

  A Tiny Tokenizer

  To read user input, we need a tokenizer. It splits a string into meaningful chunks: numbers, identifiers, operators, and parentheses. Whitespace is consumed but not produced.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int

  | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z')

  || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  tokens := TNum (int_of_string s) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  let tok = match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s in

  tokens := tok :: !tokens

  end else begin

  let tok = match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected char" in

  tokens := tok :: !tokens;

  incr pos

  end

  done;

  List.rev !tokens

  ▶ Try it

  Step 05

  The Parser

  A recursive descent parser turns tokens into our expression AST. It handles operator precedence naturally: addition is parsed as a left-associative chain of atoms.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z') || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  tokens := TNum (int_of_string s) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  let tok = match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s in

  tokens := tok :: !tokens

  end else begin

  let tok = match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected char" in

  tokens := tok :: !tokens; incr pos

  end

  done;

  List.rev !tokens

  let parse tokens =

  let toks = ref tokens in

  let next () =

  match !toks with

  | [] -> failwith "unexpected end"

  | t :: rest -> toks := rest; t in

  let peek () =

  match !toks with [] -> None | t :: _ -> Some t in

  let rec parse_expr () =

  let left = parse_atom () in

  parse_add left

  and parse_add left =

  match peek () with

  | Some TPlus ->

  ignore (next ());

  let right = parse_atom () in

  parse_add (Add (left, right))

  | _ -> left

  and parse_atom () =

  match next () with

  | TNum n -> Lit n

  | TIdent s -> Var s

  | TLParen ->

  let e = parse_expr () in

  ignore (next ()); e

  | TLet ->

  let (TIdent name) = next () in

  ignore (next ());

  let rhs = parse_expr () in

  ignore (next ());

  let body = parse_expr () in

  Let (name, rhs, body)

  | _ -> failwith "unexpected token" in

  parse_expr ()

  ▶ Try it

  Step 06

  The Read-Eval-Print Loop

  Now we connect all the pieces. The REPL reads a line, tokenizes it, parses the tokens, evaluates the expression, and prints the result. A persistent environment accumulates bindings across interactions.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z') || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos]

  do incr pos done;

  tokens := TNum (int_of_string

  (String.sub input start

  (!pos - start))) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  tokens := (match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s) :: !tokens

  end else begin

  tokens := (match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected") :: !tokens;

  incr pos

  end

  done; List.rev !tokens

  let parse tokens =

  let toks = ref tokens in

  let next () = match !toks with

  | [] -> failwith "end"

  | t :: r -> toks := r; t in

  let peek () = match !toks with

  | [] -> None | t :: _ -> Some t in

  let rec expr () =

  let l = atom () in add l

  and add left = match peek () with

  | Some TPlus ->

  ignore (next ());

  add (Add (left, atom ()))

  | _ -> left

  and atom () = match next () with

  | TNum n -> Lit n

  | TIdent s -> Var s

  | TLParen ->

  let e = expr () in

  ignore (next ()); e

  | TLet ->

  let (TIdent name) = next () in

  ignore (next ());

  let rhs = expr () in

  ignore (next ());

  Let (name, rhs, expr ())

  | _ -> failwith "unexpected" in

  expr ()

  let print_value = function

  | Int n -> Printf.printf "=> %d\n" n

  let repl () =

  let env = ref empty_env in

  try while true do

  print_string "> ";

  let line = input_line stdin in

  let tokens = tokenize line in

  let ast = parse tokens in

  let result = eval !env ast in

  print_value result

  done with End_of_file ->

  print_endline "Goodbye."

  let () = repl ()

  ▶ Try it

  main.ml 1 / 6

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  Step 01

  The Expression Type

  A REPL evaluates expressions. We start with a tiny language: integer literals, addition, let-bindings, and variables. Four constructors is all we need.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  ▶ Try it

  Step 02

  Values and Environments

  Evaluation produces values. For now, just integers. An environment maps variable names to their values using a simple association list.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  ▶ Try it

  Step 03

  The Evaluator

  Pattern matching makes the evaluator beautifully direct. Each expression form maps to a straightforward computation. Let-bindings extend the environment for the body expression.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  ▶ Try it

  Step 04

  A Tiny Tokenizer

  To read user input, we need a tokenizer. It splits a string into meaningful chunks: numbers, identifiers, operators, and parentheses. Whitespace is consumed but not produced.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int

  | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z')

  || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  tokens := TNum (int_of_string s) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  let tok = match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s in

  tokens := tok :: !tokens

  end else begin

  let tok = match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected char" in

  tokens := tok :: !tokens;

  incr pos

  end

  done;

  List.rev !tokens

  ▶ Try it

  Step 05

  The Parser

  A recursive descent parser turns tokens into our expression AST. It handles operator precedence naturally: addition is parsed as a left-associative chain of atoms.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int

  | TIdent of string

  | TNum of int | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z')

  || c = '_'

  || (c >= 'A' && c <= 'Z') || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  while !pos < len && is_digit input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  tokens := TNum (int_of_string s) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos] do

  incr pos done;

  let s = String.sub input start (!pos - start) in

  while !pos < len && is_alpha input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  let tok = match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s in

  tokens := tok :: !tokens

  end else begin

  let tok = match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected char" in

  tokens := tok :: !tokens;

  incr pos

  tokens := tok :: !tokens; incr pos

  end

  done;

  List.rev !tokens

  let parse tokens =

  let toks = ref tokens in

  let next () =

  match !toks with

  | [] -> failwith "unexpected end"

  | t :: rest -> toks := rest; t in

  let peek () =

  match !toks with [] -> None | t :: _ -> Some t in

  let rec parse_expr () =

  let left = parse_atom () in

  parse_add left

  and parse_add left =

  match peek () with

  | Some TPlus ->

  ignore (next ());

  let right = parse_atom () in

  parse_add (Add (left, right))

  | _ -> left

  and parse_atom () =

  match next () with

  | TNum n -> Lit n

  | TIdent s -> Var s

  | TLParen ->

  let e = parse_expr () in

  ignore (next ()); e

  | TLet ->

  let (TIdent name) = next () in

  ignore (next ());

  let rhs = parse_expr () in

  ignore (next ());

  let body = parse_expr () in

  Let (name, rhs, body)

  | _ -> failwith "unexpected token" in

  parse_expr ()

  ▶ Try it

  Step 06

  The Read-Eval-Print Loop

  Now we connect all the pieces. The REPL reads a line, tokenizes it, parses the tokens, evaluates the expression, and prints the result. A persistent environment accumulates bindings across interactions.

  type expr =

  | Lit of int

  | Add of expr * expr

  | Let of string * expr * expr

  | Var of string

  type value = Int of int

  type env = (string * value) list

  let empty_env : env = []

  let extend env name v = (name, v) :: env

  let lookup env name =

  match List.assoc_opt name env with

  | Some v -> v

  | None -> failwith ("unbound: " ^ name)

  let rec eval env = function

  | Lit n -> Int n

  | Add (a, b) ->

  let (Int x) = eval env a in

  let (Int y) = eval env b in

  Int (x + y)

  | Let (name, rhs, body) ->

  let v = eval env rhs in

  eval (extend env name v) body

  | Var name -> lookup env name

  type token =

  | TNum of int | TIdent of string

  | TPlus | TEqual

  | TLParen | TRParen

  | TLet | TIn

  let is_alpha c =

  (c >= 'a' && c <= 'z')

  || (c >= 'A' && c <= 'Z') || c = '_'

  let is_digit c = c >= '0' && c <= '9'

  let tokenize input =

  let len = String.length input in

  let pos = ref 0 in

  let tokens = ref [] in

  while !pos < len do

  let c = input.[!pos] in

  if c = ' ' || c = '\t' || c = '\n' then

  incr pos

  else if is_digit c then begin

  let start = !pos in

  while !pos < len && is_digit input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  tokens := TNum (int_of_string s) :: !tokens

  tokens := TNum (int_of_string

  (String.sub input start

  (!pos - start))) :: !tokens

  end else if is_alpha c then begin

  let start = !pos in

  while !pos < len && is_alpha input.[!pos]

  do incr pos done;

  let s = String.sub input start

  (!pos - start) in

  let tok = match s with

  tokens := (match s with

  | "let" -> TLet | "in" -> TIn

  | _ -> TIdent s in

  tokens := tok :: !tokens

  | _ -> TIdent s) :: !tokens

  end else begin

  let tok = match c with

  tokens := (match c with

  | '+' -> TPlus | '=' -> TEqual

  | '(' -> TLParen | ')' -> TRParen

  | _ -> failwith "unexpected char" in

  tokens := tok :: !tokens; incr pos

  | _ -> failwith "unexpected") :: !tokens;

  incr pos

  end

  done;

  List.rev !tokens

  done; List.rev !tokens

  let parse tokens =

  let toks = ref tokens in

  let next () =

  match !toks with

  | [] -> failwith "unexpected end"

  | t :: rest -> toks := rest; t in

  let peek () =

  match !toks with [] -> None | t :: _ -> Some t in

  let rec parse_expr () =

  let left = parse_atom () in

  parse_add left

  and parse_add left =

  match peek () with

  let next () = match !toks with

  | [] -> failwith "end"

  | t :: r -> toks := r; t in

  let peek () = match !toks with

  | [] -> None | t :: _ -> Some t in

  let rec expr () =

  let l = atom () in add l

  and add left = match peek () with

  | Some TPlus ->

  ignore (next ());

  let right = parse_atom () in

  parse_add (Add (left, right))

  add (Add (left, atom ()))

  | _ -> left

  and parse_atom () =

  match next () with

  and atom () = match next () with

  | TNum n -> Lit n

  | TIdent s -> Var s

  | TLParen ->

  let e = parse_expr () in

  let e = expr () in

  ignore (next ()); e

  | TLet ->

  let (TIdent name) = next () in

  ignore (next ());

  let rhs = parse_expr () in

  let rhs = expr () in

  ignore (next ());

  let body = parse_expr () in

  Let (name, rhs, body)

  | _ -> failwith "unexpected token" in

  parse_expr ()

  Let (name, rhs, expr ())

  | _ -> failwith "unexpected" in

  expr ()

  let print_value = function

  | Int n -> Printf.printf "=> %d\n" n

  let repl () =

  let env = ref empty_env in

  try while true do

  print_string "> ";

  let line = input_line stdin in

  let tokens = tokenize line in

  let ast = parse tokens in

  let result = eval !env ast in

  print_value result

  done with End_of_file ->

  print_endline "Goodbye."

  let () = repl ()

  ▶ Try it

  Playground ×