OCaml map not updating before the next step in a sequence

Question

I am trying to implement a basic parser, scanner, and a minimal language in OCaml. I believe the issue is that I'm trying to maintain a map between variables in this toy language and their values, and the language should be able to handle an expression like a=2;a and return 2. The name seems to successfully store the number 2, but by the time the program moves on to evaluating the second expression, it does not find the name in the map. And I can't understand why.

Below is the abstract syntax tree.

Ast.ml

type operator = Add (* for now just one operator *)

type expr =
    Binop of expr * operator * expr
  | Lit of int                      (* a number *)
  | Seq of expr * expr              (* a sequence, to behave like ";" *)
  | Asn of string * expr            (* assignment, to behave like "=" in an imperative language *)
  | Var of string                   (* a variable *)

Here are the parser and scanner.

parser.mly

%{ 
open Ast 
%}

%token SEQ PLUS ASSIGN EOF
%token <int> LITERAL
%token <string> VARIABLE

%left SEQ PLUS 

%start expr
%type <Ast.expr> expr

%%

expr:
| expr SEQ expr        { Seq($1, $3) }
| expr PLUS   expr { Binop($1, Add, $3) }
| LITERAL          { Lit($1) }
| VARIABLE         { Var($1) }
| VARIABLE ASSIGN expr { Asn($1, $3) }

scanner.mll

{ 
open Parser 
}

rule tokenize = parse
  [' ' '\t' '\r' '\n'] { tokenize lexbuf }
| '+' { PLUS }
| ['0'-'9']+ as lit { LITERAL(int_of_string lit) }
| ['a'-'z']+ as id { VARIABLE(id) }
| '=' { ASSIGN }
| ';' { SEQ }
| eof { EOF }

And here's where I tried to implement a sort of name-space in a basic calculator.

calc.ml

open Ast

module StringMap = Map.Make(String)
let namespace = ref StringMap.empty

let rec eval exp = match exp with  
  | Lit(n) -> n        
  | Binop(e1, op, e2) ->
      let v1 = eval e1 in
      let v2 = eval e2 in
      v1+v2
  | Asn (name, e) -> 
      let v = eval e in 
      (namespace := StringMap.add name v !namespace; v)
  | Var(name) -> StringMap.find name !namespace
  | Seq(e1, e2) -> 
      (let _ = eval e1 in 
      eval e2)

let _ =
  let lexbuf = Lexing.from_channel stdin in
  let expr = Parser.expr Scanner.tokenize lexbuf in
  let result = eval expr in
  print_endline (string_of_int result)

To test it out I compile, and it compiles successfully, then run $ ./calc in a terminal, and enter a=2;a then press Ctrl+D. It should print 2 but it gives a Not found exception. Presumably this is coming from the StringMap.find line, and it's not finding the name in the namespace. I've tried throwing print lines around, and I think I can confirm that the sequence is being correctly processed in the terminal and that the first evaluation is happening successfully, with the name and value getting entered into the string map. But for some reason it seems not to be there when the program moves on to processing the second expression in the sequence.

I'd appreciate any clarification, thanks.

Answer 1

I cannot reproduce your error. Feeding the AST directly to eval

let () =
  let ast = Seq(Asn ("a", Lit 2),Var "a") in
  let result = eval ast in
  print_endline (string_of_int result)

prints 2 as expected.

After fixing your parser to recognize the end of the stream:

entry:
| expr EOF { $1 }

using it in

let () =
  let s = Lexing.from_string "a=2;a\n" in
  let ast = Parser.entry Scanner.tokenize s in
  let result = eval ast in
  print_endline (string_of_int result)

prints 2 as expected. And without this fix, your code fails with a syntax error.

EDIT: Rather than using a makefile, I will advise to use dune, with the following simple dune file:

(menhir (modules parser))
(ocamllex scanner)
(executable (name calc))

it will at least solve your compilation troubles.