CSCI 2041 Assignment 5: The Calculon Interpreter

The interpreter is broken into 4 source files

Each of these must be edited to complete features of Calculon associated with required and optional problems.

The above table lists the features of the programming language along with the problems associated with completing them. Middle columns correspond to the above source files with symbols meaning the following:

Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.

NOTE: Tests Released Later: The tests for this assignment will not be released with the publication of the specification. They will be released sometime after once they have been completed. Further instructions on how to use them will be made available on release.

There is an midpoint submission deadline worth 10% of the credit for the assignment. Submit working code at this point that compiles and passes the tests associated with Problem 1 to receive 10% of the credit for the project. This is to motivate getting an early start on this rather large assignment.

To run the milestone tests download the zip of milestone tests and run the following commands.

> unzip a5-milestone-tetsts.zip        # unzip the contents 
> cp a5-milestone-tests/* a5-code/*    # copy test code into assignment directory
> cd a5-code/                          # change to project directory
> make test-p1                         # run the tests which only target problem 1

During final manual inspection the following will be examined for credit.

Some of Calculon's features are demonstrated below.

> calculon
calculon> help;
CALCULON: a calculator/interpreter with an unholy... ACTING TALENT!

--SUPPORTED SYNTAX--
  <expr> ;                          : expression evaluation terminated by semicolon 
  def x = <expr> ; in <expr>        : top-level variable bindings
  1 + 2*9 / (4-2)                   : basic arithmetic operators
  let x=<expr> in <expr> ;          : let bindings for locals
  if <expr> then <expr> else <expr> : conditional execution
  @n n*2+4                          : lambda abstraction with parameter n
  def double = @n n*2;              : top-level function binding
  double 4;                         : function application
  def mul = @a @b a*b;              : nested lambdas for multi-arg function

--BUILTIN COMMANDS--
  help;                             : print this help message
  quit;                             : quit calculon
  whos;                             : show all top-level bindings and their value types
  undef <ident>;                    : remove a global binding
  debug {true|false};               : enable/disabe debug printing of backtraces
  tokens <expr>;                    : show the results of lexing the given <expr>
  parsetree <expr>;                 : show the results of parsing the given <expr>
  show <expr>;                      : show the structure of the evaluated data in <expr> 

--OPTIONAL COMMANDS--
  source <filename>;                : read command from <filename> as if typed
  save <filename>;                  : save all definitions as binary data in <filename>
  load <filename>;                  : load binary variable defs from <filename>
  opparsetree <expr>;               : show the results of parsing AND optimizing the given <expr>
  optimize {true|false};            : enable/disabe optimization of expressions in normal evaluation

calculon> 1+2+3*4/2;            # basic math
- : IntDat(9)

calculon> let a=2 in let b=3 in a*b; # let bindings
- : IntDat(6)

calculon> def x = 7;            # top-level definitions
x : IntDat(7)

calculon> def nope = false;     # booleans
nope : BoolDat(false)

calculon> def double = @n 2*n;  # function definitions via @ lambdas
double : Closure(n, <fun>)

calculon> double 2;             # function call
- : IntDat(4)

calculon> double 7;
- : IntDat(14)

calculon> whos;                 # listing of top-level defs
    double : Closure(n, <fun>)
      nope : BoolDat(false)
         x : IntDat(7)

calculon> def mul = @a @b a*b;  # functions of multiple params via nested lambdas
mul : Closure(a, <fun>)

calculon> mul 3 7;
- : IntDat(21)

calculon> def mul_two = mul 2;  # partial application for curried function
mul_two : Closure(b, <fun>)

calculon> mul_two 5;            # completed application
- : IntDat(10)

                                # recursive definition at top-level
calculon> def fact = @n if n=1 then 1 else n*(fact (n-1));
fact : Closure(n, <fun>)

calculon> fact 5;               # recursive function call
- : IntDat(120)

calculon> tokens mul 3 7;       # show tokenization of expression
Tokens:
[Ident(mul); IntTok(3); IntTok(7); Semicolon ]

calculon> parsetree mul 3 7;    # show parsetree of expression
Parse tree:
Apply
  .func_expr:
    Apply
      .func_expr:
        Varname(mul)
      .param_expr:
        IntExp(3)
  .param_expr:
    IntExp(7)

calculon> show mul;             # show structure of data
Closure(param_name: a, varmap={...} code=
Lambda( b )
  Mul
    Varname(a)
    Varname(b)
)
calculon> quit;                 # Noooooooooo!

That was so terrible I think you gave me cancer!
> 

1. The starting state of Calculon does not recognize conditional keywords like if so will treat them as normal identifiers. This leads to odd errors in which if is misinterpreted as a function being applied to several arguments with errors like:

      calculon> if true then 1 else 5;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calceval.EvalError("Function application is not yet implemented", "{}", "\nApply...
   

   This can be seen using the tokens command which will list if as an identifier rather than its own token

      calculon> tokens if true then 8*2 else 4*3;
      Tokens:
      [Ident(if); BoolTok(true); Ident(then); IntTok(8); Times; IntTok(2); Ident(else); IntTok(4); Times; IntTok(3); 
       Semicolon ]
   

   Once the lexer/parser create conditionals, this error will change.

2. In calclex.ml, edit the main lexing function lex_string so that it recognizes keyword associated with conditionals (if etc.). Examine the token type at the top of the file and return appropriate tokens for each keyword.

   Recompile Calculon and check the results of lexing by using the tokens command which should yield results like the below.

      calculon> tokens if true then 8*2 else 4*3;
      Tokens:
      [If; BoolTok(true); Then; IntTok(8); Times; IntTok(2); Else ; IntTok(4); Times; IntTok(3); 
       Semicolon ]
   

   This shows that if is no the token If rather than an identifier. which is a good start.

1. In calcparse.ml, edit the function parse_cond which is meant to handle conditionals. The correct sequence for a conditional is

      if <expr> then <expr> else <expr>
   

   That means the a series of nested checks via match/with looking for the corresponding tokens. In each case, an arbitrary expression can appear in place of <expr> such as the following:

      calculon> if  let x=true in x  then 1 else 2;
      - : IntDat(1)
   
      calculon> if  if true then false else true  then 1 else 2;
      - : IntDat(2)
   

   Thus you will need to employ the top-level parsing function parse_expr to parse a whole expression between each of the keyword tokens.

   In the expr type defined at the top of calcparse.ml, the Cond variant is associated with conditional execution. The fields if_expr then_expr else_expr should be assigned the three associated expressions listed in the form above.

   While working, employ the parsetree command to show the parse tree of a given expression. For example, the following is a correct parse tree:

      calculon> parsetree if true then 8*2 else 4-3;
      Parse tree:
      Cond
        .if_expr:
          BoolExp(true)
        .then_expr:
          Mul
            IntExp(8)
            IntExp(2)
        .else_expr:
          Sub
            IntExp(4)
            IntExp(3)
   

2. Note that conditionals require all of if/then/else in Calculon so leaving any part off should lead to errors as shown below. Note that the error messages are required for missing then and missing else cases.

      calculon> if true then 1 else 2;
      - : IntDat(1)
   
      calculon> if true then 1 else;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calcparse.ParseError("syntax error", _)
   
      calculon> if true then 1;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calcparse.ParseError("Expected 'else' ", _)
   
      calculon> if true then;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calcparse.ParseError("syntax error", _)
   
      calculon> if true;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calcparse.ParseError("Expected 'then' ", _)
   

1. In calceval.ml, locate the eval_expr function and the case associated with Cond. You will need to make use of the fields like if_expr in the record which are defined at the top of calcparse.ml. Remove the exception raise and start coding.
2. Conditional execution is simple: evaluate the expression associated with the if part, sometimes called the test. If it is true, then evaluate only the then expression, otherwise evaluate the else expression only. The structure of your code will flow according to the above.

3. Evaluating nested expressions should be done recursively via calls to eval_expr. This function always returns a data_t type which is defined at the top of the calceval.ml file. It represents the three kinds of data that exist in Calculon: IntDat for integers, BoolDat for booleans, and Closure for functions of one parameter.

   On evaluating the result of an expression, pattern match the results against these three types. Often one is interested in only one kind of data as the others are in error.

   For conditionals, the results of evaluating if_expr must be a BoolDat which carries a true (eval then_expr) or false (eval else_expr). Other kinds like IntDat should generate errors with messages like the following where the utility data_string has been used to stringify the erroneous data.

      calculon> if 1 then 2 else 3;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calceval.EvalError("Expected Bool for if(), found 'IntDat(1)'", ...
      
      calculon> if 8+7 then 2 else 3;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calceval.EvalError("Expected Bool for if(), found 'IntDat(15)'", ...
      
      calculon> def x = 21;
      x : IntDat(21)
      calculon> if x then 1 else 2;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calceval.EvalError("Expected Bool for if(), found 'IntDat(21)'", "{x: IntDat(21)}", ...
      
      # Only works once lambdas can be evaluated
      calculon> if (@n n*2) then 2 else 3;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calceval.EvalError("Expected Bool for if(), found 'Closure(n, <fun>)'", ...
   

4. Once evaluation code is complete, Calculon should handle if/then/else constructs like any of its other constructs.

The following criteria will be checked in this problem.

1. In the provided version of Calculon, the symbols < and > are not recognized by the lexer while the = sign is but not in comparisons. This leads to the following two kinds of errors.

      calculon> 5 < 7;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calclex.LexError("char '<' not recognized, at position 2 in the input '5 < 7;'")
      
      calculon> 5 = 7;
      - : IntDat(5)
      WARNING: Great Shatner's ghost!
      WARNING: The following tokens remain and will NOT be evaluated
      [Equal; IntTok(7); Semicolon ]
   

2. In calclex.ml, add support for the symbols < and > at an appropriate location. Generate token types LessThan and GreatThan when these symbols are recognized. No action is needed for the = which is already tokenized.

3. Use the tokens command to check that code changes result in proper tokenization.

      calculon> tokens 1 < 10+3;
      Tokens:
      [IntTok(1); LessThan; IntTok(10); Plus; IntTok(3); Semicolon ]
      calculon> tokens 1 > 10+3;
      Tokens:
      [IntTok(1); GreatThan; IntTok(10); Plus; IntTok(3); Semicolon ]
   

1. Comparisons are among the lowest precedence operations in most programming environments and Calculon follows this convention. This allows arithmetic to happen before comparisons are evaluated such as in the following.

      calculon> 5*2 > 3+4;
      - : BoolDat(true)
      calculon> 5*2 = 3+4+3;
      - : BoolDat(true)
      calculon> 5*2 = 3+4+2;
      - : BoolDat(false)
      calculon> 1 < 10*10+2;
      - : BoolDat(true)
   

2. Due to the low-precedence of comparisons, a new production (parsing function) will need to be introduced in the parser that precedes all other productions save for the top-level parse_expr parsing entry point.
3. In calcparse.ml, create a parsing function parse_compare between parse_expr and parse_addsub. Though this function appears visually between them, it will only be part of the parsing recursive descent if other function call it. Modify parse_expr to call parse_compare and plan to make calls to parse_addsub in parse_compare.

4. parse_compare should look for a sequence like one of the following:

      <expr>  <  <expr>
      <expr>  >  <expr>
      <expr>  =  <expr>
   

   <expr> here are generated by deeper recursive calls starting with low-precedence arithmetic operations like addition and subtraction.

5. Comparison has a simpler grammar than arithmetic like + as there is no chaining of comparisons.

      1 + 2 + 3   # allowed in Calculon
      1 < 2 < 3   # not allowed in Calculon
   

   Thus the structure of the code for parsing comparisons can be simpler than what is used for arithmetic operators: no iteration is needed.

6. Parse a left-hand expression, then use match/with to look for appropriate tokens to indicate a comparisons is being done. If so, parse a right-hand expression. The left and right expressions being compared should be saved along with the operation and result in an Intop variant of expr. Examine how these are created in the arithmetic parsing to understand what is required. Like arithmetic operations, if no appropriate symbol is found, then comparisons should simply return a left-hand expression.

7. As before, use the parsetree command to ensure code changes result in an appropriate parse tree. Ensure that the comparisons happen last, after other arithmetic operations.

      calculon> parsetree 10 > 10+3;
      Parse tree:
      Greater
        IntExp(10)
        Add
          IntExp(10)
          IntExp(3)
      
      calculon> parsetree 5*2+1 = 10+3;
      Parse tree:
      Equal
        Add
          Mul
            IntExp(5)
            IntExp(2)
          IntExp(1)
        Add
          IntExp(10)
          IntExp(3)
   

1. In calceval.ml, identify where comparisons should be handled in eval_expr. Like arithmetic, comparisons are an Intop operations. Add cases to an appropriate match/with statement to handle them.
2. Unlike other arithmetic operations which generate IntDat, comparison result in BoolDat with true/false values associated. Make sure in to adhere to this convention.

3. On completing the evaluation function, try out some expressions involving comparisons to ensure that they work properly.

      calculon> 5*2+1 = 10+3;
      - : BoolDat(false)
      calculon> 5*2+1 = 10+1;
      - : BoolDat(true)
      calculon> 5*2+1 < 10+4;
      - : BoolDat(true)
      calculon> def x = 2;
      x : IntDat(2)
      calculon> if x < 3 then 5 else 10;
      - : IntDat(5)
      calculon> let y=4 in if y < x then 1 else 2;
      - : IntDat(2)
   

4. Ensure that the warnings or errors result if repeated comparison is attempted as in the following.

      calculon> 1 < 2 < 3;
      - : BoolDat(true)
      WARNING: Great Shatner's ghost!
      WARNING: The following tokens remain and will NOT be evaluated
      [LessThan; IntTok(3); Semicolon ]
      
      calculon> if 1 < 2 < 3 then 10 else 20;
      ERROR: I'm not familiar with the type of thing I'm seeing...
      Calcparse.ParseError("Expected 'then' ", _)
   

The following criteria will be checked in this problem.

1. The lexing for lambda expressions is already complete but it is worthwhile to examine the associated portions of code. The lexer simply needs to identify @ characters as a special At token.

2. The parser will need to be modified to handle produce lambda expressions. In its initial state, errors will result from use of the @ symbol:

   calculon> parsetree @n n+1;
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calcparse.ParseError("syntax error", _)
   

3. In calcparse.ml find the existing parse_lambda function which presently just falls through to the higher precedence function application.
4. Add cases that look for the token sequence @ <ident> <expr> which is a correctly specified lambda expression. Note that the second token should be an Ident which carries a variable name.
5. Construct a Lambda variant of expr using the appropriate data. The definition for this variant is at the top of calcparse.ml.
6. Also match an error case which will help users identify mistakes in their use of the @ symbol. This would look for a sequence of tokens of the form @ _ where the second token is not an Ident (anything else). Raise a parse error in this case with the message below which indicates that @ should be followed by an identifier.

7. Test your parsing with the parsetree command as demonstrated below.

   calculon> parsetree @n n+1;
   Parse tree:
   Lambda( n )
     Add
       Varname(n)
       IntExp(1)
   
   calculon> parsetree @first @second first*second;
   Parse tree:
   Lambda( first )
     Lambda( second )
       Mul
         Varname(first)
         Varname(second)
   
   calculon> parsetree @ 1+2*n;
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calcparse.ParseError("Expected identifier in lambda expression after @", _)
   

1. In calceval.ml, locate the case in eval_expr which deals with lambda expressions.
2. Evaluating a lambda simply creates a closure. Thus, all that needs to happen is creation of a Closure variant of data_t. The correspondence between fields of Lambda and Closure should be obvious save for the varmap.

3. Closures in calculon are lexically scoped which means that they retain all variable bindings present at their creation. For example, look closely at the varmap portion in the demo below.

   ##############################
   # EXAMPLE 1
   calculon> def x=2;                 # define x and y
   x : IntDat(2)
   
   calculon> def y=5;
   y : IntDat(5)
   
   calculon> def add_xy = @a a+x+y;   # define a function using x,y
   add_xy : Closure(a, <fun>)
   
   
   calculon> show add_xy;             # variable map includes x,y
   Closure(param_name: a, varmap={... x: IntDat(2), y: IntDat(5)} code=
   Add                                ^^^^^^^^^^^^^^^^^^^^^^^^^^
     Add
       Varname(a)
       Varname(x)
     Varname(y)
   )
   
   calculon> def x=199;               # redefine x and y
   x : IntDat(199)
   
   calculon> def y=255;
   y : IntDat(255)
   
   
   calculon> show add_xy;             # original x,y values are retained in map
   Closure(param_name: a, varmap={... x: IntDat(2), y: IntDat(5)} code=
   Add
     Add
       Varname(a)
       Varname(x)
     Varname(y)
   )
   
   ##############################
   # EXAMPLE 2
   calculon> def double = let two=2 in @n two*n;   # local var 'two' to closure
   double : Closure(n, <fun>)
   
   calculon> two;                                  # two is not defined at top level
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calceval.EvalError("No variable 'two' bound", ...
   
   calculon> show double;                          # double retains value for 'two'
   Closure(param_name: n, varmap={... two: IntDat(2), ...} code=
   Mul
     Varname(two)
     Varname(n)
   )
   

4. To enable easy lexical closures, Calculon internally uses OCaml's persistent maps. At the top of calceval.ml, a module Varmap is defined along with the type varmap_t which maps string to data_t, variable names to variable values.
5. To allow a closure to retain the environment in which it is created, construct it with the current varmap. Note that all calls to eval_expr are passed a varmap with the current bindings. Use this to construct the closure.
6. Test your results using Calculon's show command which shows the internal structure associated with a data_t at the top level (see previous examples). Ensure that the varmap associated with each closure contains the bindings that were part of the lexical scope in which it was created.
7. Note that the approach taken here is a bit lazy as ALL variables in the scope of a closure are retained rather than those that are strictly needed for it to work. A more hygenic implementation would analyze the closure code to determine the free variables that need to be retained from the global scope and only retain those for better memory efficiency. However, the present approach of retaining a copy of the map is favored due to ease of implementation.

The following criteria will be checked in this problem.

1. Lexing is complete for function application: there is no special syntax associated with it.

2. Parsing is provided for function application and requires no modification. In calcparse.ml, function application is a high-precedence operation which looks for two adjacent expressions. This creates an Apply variant of expr. This is done in a left-associative fashion as arithmetic operators are parsed so that applications to multiple arguments

   clos arg1 arg2 ... argN
   
   

   are parsed as

   ((((clos arg1) arg2) ...) argN)
   
   

   This allows the results of the first application to create another closure which is applied to the second argument and so forth.

1. In calceval.ml, locate where Apply expressions are handled and begin editing.

2. Evaluate the func_expr associated with the application. In many cases this will be a simple variable name but be an arbitrarily complex expression:

   doub (2+1)        # simple func_expr
   (@m 2*m) (2+1)    # more complex func_expr
   

3. The resulting data produce by the func_expr should be a Closure. Do pattern matching to ensure this is the case. If it is a closure, evaluate the parameter expression associated with the Apply.
4. Refresh your understanding of the fields in the Closure variant. Access the varmap associated with the closure, and add a binding between its parameter name and the parameter data computed in the previous step. Importantly do not use the varmap available in eval_expr as this may have different bindings than the varmap of the closure.
5. Finally, recursively evaluate the closures code in the presence of the varmap created in the previous step and return the results.

6. If the function expression is NOT a closure, application cannot proceed so raise an evaluation error. With a message like the one below. Use the data_string function to stringify the data that was not a closure.

   calculon> 8 6;                  
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calceval.EvalError("Expected Closure for application, found 'IntDat(8)'", ...
   
   calculon> true 9 5;
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calceval.EvalError("Expected Closure for application, found 'BoolDat(true)'", ...
   

7. Test out function application evaluation after recompiling using the examples below. Note the use of the global undef <ident> command to remove a binding from the top level. This is useful to ensure that closures properly retain their lexical scope and are evaluated in that scope.

   ##############################
   # EXAMPLE 1
   calculon> def double = @n 2*n;        # single arg function
   double : Closure(n, <fun>)
   
   calculon> double 6;                   # application
   - : IntDat(12)
   
   ##############################
   # EXAMPLE 2
   calculon> def mulall = @a @b @c a*b*c; # multiple args
   mulall : Closure(a, <fun>)
   
   calculon> mulall 1 2 3;               # full application
   - : IntDat(6)
   
   calculon> def mullast = mulall 1 2;   # partial application
   mullast : Closure(c, <fun>)
   
   calculon> mullast 3;                  # completed application
   - : IntDat(6)
   
   calculon> mullast 4;                  # completed application
   - : IntDat(8)
   
   ##############################
   # EXAMPLE 3
   calculon> def x = 10;                 # test lexical scope
   x : IntDat(10)
   
   calculon> def addx = @a a+x;          # uses x
   addx : Closure(a, <fun>)
   
   calculon> addx 5;                     # works fine
   - : IntDat(15)
   
   calculon> undef x;                    # undefine x
   calculon> x;
   ERROR: I'm not familiar with the type of thing I'm seeing...
   Calceval.EvalError("No variable 'x' bound", ...
   
   calculon> addx 5;                     # function still works
   - : IntDat(15)
   
   calculon> def x=40;                   # redefine x
   x : IntDat(40)
   
   calculon> addx 5;                     # original x=10 used
   - : IntDat(15)
   

The following criteria will be checked in this problem.

1. Examine calculon.ml and locate the code responsible for setting up a top-level def binding. Study this code carefully as it will provide a template for how to implement recursive let bindings.
2. In calceval.ml, locate the where eval_expr handles Letin expressions. This code is relatively simple.
3. Recursive let bindings only matters for functions in Calculon. That means one only needs to look for closures. After the expression associated with the let is evaluated, check it to see whether it is a closure using match/with.
4. If not a closure, nothing needs to change. However, closures should have their varmap modified to include the variable name which is being let-bound. This will allow them to refer back to their own function name in the event that recursion is required.
5. Be careful to directly modify the closure's map and NOT the varmap that the let binding is altering as these may have different bindings in them.
6. When finished, recompile and check your results with either the example above or the simple one below.

# ensure there are no alternative facts
calculon> undef fact;  

# recursive let binding
calculon> let fact = @n if n=1 then 1 else n*(fact (n-1))  in fact 5;   
- : IntDat(120)

The following criteria will be checked in this problem.

While not strictly necessary, boolean operators like and and or allow conditions to be stated somewhat more succinctly than would otherwise be possible. This problem implements these two boolean operators in Calculon. This allows code like the following to execute.

calculon> true and false;
- : BoolDat(false)

calculon> true or false;
- : BoolDat(true)

calculon> if 1<2 and 2<3 then 10 else 20;
- : IntDat(10)

calculon> def between = @lo @hi @x  (lo < x) and (x < hi);
between : Closure(lo, <fun>)

calculon> between 1 3 2;
- : BoolDat(true)

calculon> between 1 3 5;
- : BoolDat(false)

calculon> between 1 3 0;
- : BoolDat(false)

Boolean operations are lower precedence than arithmetic and lower precedence than comparison. This allows combinations of these other operations to be done prior to boolean operations a shown below.

calculon> parsetree 1+2>4 or 2+3>4;
Parse tree:
Or
  Greater
    Add
      IntExp(1)
      IntExp(2)
    IntExp(4)
  Greater
    Add
      IntExp(2)
      IntExp(3)
    IntExp(4)

calculon> 1+2>4 or 2+3>4;
- : BoolDat(true)

One important convention that Calculon follows is that most languages implement and as a higher precedence operator than or which allows the following interpretations.

calculon> def x=5;
x : IntDat(5)

calculon> 1<x and x<3 or 3<x and x<7;       # eval 'and' before 'or' 
- : BoolDat(true)

calculon> (1<x and x<3) or (3<x and x<7);   # explicit parens for the above
- : BoolDat(true)

calculon> parsetree 1<x and x<3 or 3<x and x<7;
Parse tree:
Or
  And
    Less
      IntExp(1)
      Varname(x)
    Less
      Varname(x)
      IntExp(3)
  And
    Less
      IntExp(3)
      Varname(x)
    Less
      Varname(x)
      IntExp(7)

A hand feature of OCaml's REPL is the #use "source.ml" directive which will read OCaml code from a source file and evaluate it in the REPL. Calculon benefits from a similar functionality if the source command is implemented.

> cat small.calc                # unix command line
def one = 1;                    # contents of file small.calc
def double = @n n*2;

> calculon                      # start calculon

calculon> source small.calc;    # read from source file
Reading source file 'small.calc'

calculon> def one = 1;          # from file
one : IntDat(1)

calculon> def double = @n n*2;  # from file
double : Closure(n, <fun>)

calculon> 
End of file 'small.calc'        # end of file

calculon> whos;                 # show definitions
    double : Closure(n, <fun>)
       one : IntDat(1)

calculon> double one;           # call loaded function
- : IntDat(2)

calculon> double 3;
- : IntDat(6)

This allows source files to be created in text editors and loaded into Calculon.

Variable bindings in a Calculon session may be lost if a source file is loaded which redefines them:

calculon> def one = 999;        # define variable 'one'
one : IntDat(999)

calculon> source small.calc;    # source a file
Reading source file 'small.calc'

calculon> def one = 1;          # re-def of 'one'
one : IntDat(1)

...
End of file 'small.calc'
calculon> whos;
    double : Closure(n, <fun>)
       one : IntDat(1)          # one redefined
calculon> one;
- : IntDat(1)

Another common feature of REPL's is the ability to save and restore sessions. Calculon can support this with the save <file> and load <file> commands as follows.

> calculon                      # start calculon

calculon> def pi=314;           # define a few variables
pi : IntDat(314)

calculon> def mul = @a @b a*b;
mul : Closure(a, <fun>)

calculon> whos;
       mul : Closure(a, <fun>)
        pi : IntDat(314)

calculon> save mydefs.dat;      # save defs to a binary file
Saved binary data in 'mydefs.dat'

calculon> quit;

That was so terrible I think you gave me cancer!

> calculon                      # restart calculon

calculon> whos;                 # no defs initially

calculon> load mydefs.dat;      # load binary data
Loading binary data from 'mydefs.dat'

calculon> whos;                 # defs are back
       mul : Closure(a, <fun>)
        pi : IntDat(314)

calculon> mul pi 2;
- : IntDat(628)

In Calculon, saving a session simply amounts to writing the global variable map defined in calculon.ml to disk while loading involves reading the data back and merging it with the current variable map.

Writing and reading a complex data structure like a varmap_t is somewhat difficult if users were required to do it by hand. Fortunately, like many sensible languages, OCaml supports marshalling of data, sometimes known as serialization. This is the process of writing the in-memory binary representation of a data structure to disk which allows it to be read back directly into memory.

The module Marshal provides this serialization of any data structure in OCaml including user-defined data. No special knowledge of the data structure is needed to marshal it. Knowledge of the functions in Marshal will make this problem relatively easy to complete.

While colorful, the error messages in Calculon are a bit general and hard on the eyes as indicated below.

calculon> 10!;
ERROR: I'm not familiar with the type of thing I'm seeing...
Calclex.LexError("char '!' not recognized, at position 2 in the input '10!;'")

calculon> 10+;
ERROR: I'm not familiar with the type of thing I'm seeing...
Calcparse.ParseError("syntax error", _)

calculon> def doub = @ * 2;
ERROR: I'm not familiar with the type of thing I'm seeing...
Calcparse.ParseError("Expected identifier in lambda expression after @", _)

calculon> 10+true;
ERROR: I'm not familiar with the type of thing I'm seeing...
Calceval.EvalError("Expect Int for right arithmetic expression, found 'BoolDat(true)'", "{}", "\nAdd\n  IntExp(10)\n  BoolExp(true)\n")

One minor improvement to this situation would be to treat each exceptions typ slightly differently and print associated messages as shown below.

calculon> 10!;
LEX ERROR: char '!' not recognized, at position 2 in the input '10!;'

calculon> 10+ ;
PARSE ERROR: syntax error
tokens: [Semicolon ]

PARSE ERROR: Expected identifier in lambda expression after @
tokens: [At; Times; IntTok(2); Semicolon ]

calculon> 10+true;
EVAL ERROR: Expect Int for right arithmetic expression, found 'BoolDat(true)'
varmap: {}
expression:
Add
  IntExp(10)
  BoolExp(true)

While still not tremendously helpful, these messages are at least more specific to the kind of error (lex, parse, or evaluate).

To complete this problem, develop some knowledge of exception handling. A reasonable source is in one of our course texts: Practical OCaml Ch 10 on Exception Handling. Exceptions are similar to algebraic types and exception handling of various types is similar to pattern matching. After some research and practice, exception handling will feel quite familiar.

As we have seen, parsing creates a data structure representing what a code should do while evaluation actually executes the code. In between these two steps exists a whole world of possible optimizations which transform the original expressions to produce equivalent results more efficiently. This problem addresses some possible optimization opportunities.

As an opening example, consider the following function in Calculon.

calculon> def five = @n 2+3;
five : Closure(n, <fun>)

calculon> show five;
Closure(param_name: n, varmap={...} code=
Add
  IntExp(2)
  IntExp(3)
)

Whenever the function five is called, its parameter is ignored and instead 2 and 3 are added to return 5 every time. It is not hard to see that this function would be better written

calculon> def five_better = @n 5;
five_better : Closure(n, <fun>)

calculon> show five_better;
Closure(param_name: n, varmap={...} code=
IntExp(5)
)

where the adding of 2 and 3 is done ahead of time saving the need to do an addition at evaluation time.

An interesting question is whether this optimization can be done automatically, a technique called constant folding.

Similarly, the following two functions have the same effect, of adding 9 but the latter does so without needing to do any let binding.

calculon> def add_nine = @n let nine=9 in n+nine;
add_nine : Closure(n, <fun>)

calculon> show add_nine;
Closure(param_name: n, varmap={...} code=
Letin( nine )                   # evaluate a let binding
  .var_expr:
    IntExp(9)
  .in_expr:
    Add
      Varname(n)
      Varname(nine)
)

calculon> def add_nine_nolet = @n n+9;
add_nine_nolet : Closure(n, <fun>)

calculon> show add_nine_nolet;
Closure(param_name: n, varmap={...} code=
Add                             # no let binding to evaluate
  Varname(n)
  IntExp(9)
)

The optimization in which the variable nine is replaced by its constant value 9 is often referred to as constant propagation and in avoids the need to modify the variable map.

This problem adds several features to Calculon to perform limited versions of the constant folding and constant propagation optimizations.

• A function in calceval.ml called optimize_expr which transforms expressions into equivalent, optimized expressions. Some constant folding and propagation are done for this.
• A top-level command optparsetree <expr>; which shows the expression resulting from optimize_expr in the same way that parsetree <expr> shows the results of parsing.
• Automatic optimization of expressions via optimize_expr when the optimize true; top-level option is set.

These optimizations can be done by hand but allowing a coder to use informative variable names and then automatically optimizing the result for performance is a powerful combination.

If creating a zip file is unfamiliar to you, refer to the following guide: Making Zips (tutorial)

Once your are confident your code is working, you are ready to submit. Ensure your folder has all of the required files. Create a zip archive of your lab folder and submit it to Canvas.

On Canvas:

• Click on the Assignments section
• Click on the appropriate link for this lab/assignment
• Scroll down to "Attach a File"
• Click "Browse My Computer"
• Select you Zip file and press OK

You may wish to review the policy on late project submission which will cost you late tokens to submit late or credit if you run out of tokens. No projects will be accepted more than 48 hours after the deadline.

http://www-users.cs.umn.edu/~kauffman/2041/syllabus.html#late-projects