code Semantics as code in an interpreter for an SML-like language

Contents

Required Tasks

In this assignment, you will complete several parts of the implementation of a familiar-looking programming language. The first part (posted now) builds a core data structure (the environment) as an ML abstract data type. Remaining parts implement key features of the interpreter. One class meeting will be a lab-style session to get you started on the interpreter component, which involves exploring and extending provided code.

1. MAP and ENV Abstract Data Types

MAP and ENV signatures are provided and documented in env.sig. Maps map keys to values. Environments are a form of map we have used to define the semantics of programming languages. We separate the notion of more basic MAP and an ENV that extends it as a foundation for a future assignment. In this assignment, you implement a straightforward version of the full ENV abstract data type. A future assignment will consider alternative MAP implementations

Implement an Env structure in the file env.sml, ascribing the ENV signature (defined in the file env.sig), by completing the definition of all bindings in env.sml. This structure should represent maps by association lists, a simple data structure we have worked with in multiple past assignments. Some bindings are provided; others are defined as raise Unimplemented. You must replace all raise Unimplemnted by actual implementations.

- val env0 = Env.empty;
val env0 = - : (''a, 'b) Env.t
- Env.lookup "x" env0; (* It's OK to get a "type vars not generalized" warning *)
stdIn:5.1-5.43 Warning: type vars not generalized because of
value restriction are instantiated to dummy types (X1,X2,...)
val it = NONE : ?.X1 option
- val env1 = Env.bind ("x", 7) env0;
val it = - : (string, int) Env.t
- Env.lookup "x" env1;
val it = SOME 7 : int option
- val env2 = Env.bind ("y", 8) env1;
val env2 = - : (string, int) Env.t
- Env.lookup "x" env2;
val it = SOME 7 : int option
- Env.lookup "y" env2;
val it = SOME 8 : int option
- Env.lookup "x" (Env.unbind "x" env2);
val it = NONE : int option
- val env3 = Env.make [("y", 4),("x", 5),("x",2)];
val env3 = - : (string, int) Env.t
- Env.lookup "x" env3;
val it = SOME 5 : int option

Although the abstraction of the Env.t type prevents the REPL from displaying the internals of such a value, The Env.rewind and Env.replay functions (provided) are useful for enumerating the context of environments to verify they are as expected.

- print (Env.replay (fn ((k, v), acc) => acc ^ k ^ " = " ^ (Int.toString v) ^ "\n") "" env3);
x = 2
x = 5
y = 4
val it = () : unit
- Env.replay (op::) [] env3;
val it = [("y", 4),("x", 5),("x",2)] : (string * int) list

This data structure will power the core of your interpreter (next part of the assignment), so be sure to test it carefully.

2. Explore the SMiLe Language and Interpreter

First: git pull starter master to make sure you have all the code (if you started task 1 before this task appeared) and accept the default merge commit message. (There should not be conflicts.)

The rest of the tasks in this assignment will step you through the implementation of several features in an interpreter for the SMiLe language, a language similar to Standard ML, but with dynamic instead of static type checking. It uses a subset of the SML syntax and a subset of the SML semantics, with the key exception that it performs dynamic type-checking instead of static type-checking.

Wow, this looks long.

The interpreter implementation tasks will require careful reading and understanding of provided code (and text). You will write possibly fewer than 50 new lines of code altogether for the required parts.

How to work effectively:

  1. Follow through the tasks in order. They build on each other.
  2. Your job here is to take evaluation rules (or other definitions) that we have written in English or formal semantics and translate them – usually in the most direct way possible – to SML code. Some rules are specified directly in the assignment; look up and review the rest.
  3. The focus is on understanding and applying the evaluation rules concretely. While you will need to understand the rules and the representation of programs clearly, programming the rules is generally straightforward once you understand those things. This programming is not about being “clever” in how you program things; it’s about translating the rules directly and cleanly.
  4. Believe in the power of ML pattern matching!
  5. Test everything. A lot. Write your tests in files so you can rerun them easily.
  6. Commit and push early and often.

Informal SMiLe Language Definition

Concrete Syntax

Your SMiLe interpter will manipulate Abstract Syntax Trees (ASTs) representing SMiLe programs as ML data structures. The concrete syntax defined here makes it easier to write SMiLe programs. We provide a parser that translates the following concrete syntax to ASTs.

We use grammar in a form similar to Extended Backus Normal Form (EBNF) to describe the concrete syntax of SMiLe programs. Non-terminal symbols are unquoted, e.g., expr. Terminal symbols are quoted, e.g., 'val' or '+'. Non-terminal symbol definitions use = and separate their productions by |, with the list of productions terminated by : The notation ( )* indicates that whatever sequence of symbols appears inside the parentheses can be repeated zero or more times.

The grammar below is a fairly close match for our abstract syntax representation. Since this grammar is ambiguous, the parser enforces precedence and associativity rules. Since the details of the concrete syntax are not the focus of this assignment, it suffices to understand that the precedence rules match those of SML. (Take CS 235 and CS 301 to learn more.) Four non-terminal symbols in this grammar are not defined: int refers to any non-negative integer literal; string refers to any double-quoted string literal; var refers to any valid SML identifier starting with a lower case letter; tag refers to any valid SML constructor name staring with an upper case letter.

program  = binding program
         | binding ;
binding  = 'val' pattern '=' expr
         | 'fun' var funcases ;
funcases = pattern '=' expr '|' funcases
         | pattern '=' expr ;
pattern  = '_' | '()' | 'true' | 'false' | int | string
         | '(' ( pattern ',' )* pattern ')' | tag pattern ;
   expr  = '()' | 'true' | 'false' | int | string
         | unop expr | expr binop expr
         | '(' ( expr ',' )* expr ')' | '[' ( expr ',' )* expr] | '[]' | tag expr
         | 'if' expr 'then' expr 'else' expr
         | 'fn' cases | expr expr | var
         | 'let' program 'in' expr 'end'
         | 'case' expr 'of' cases ;
    unop = 'not' | '~' ;
   binop = '+' | '-' | '*' | 'div' | 'mod' | '^'
         | '=' | '<>' | '<' | '<=' | '>' | '>=' | '::'
         | 'andalso' | 'orelse' ;
   cases = pattern '=' expr '|' cases
         | pattern '=' expr ;

Here is an example SMiLe program defining and using a factorial function:

fun fact x =
  if x <= 1
  then 1
  else x * (fact (x-1))

val fact5 = fact 5
val fact6 = fact 6

Yep, it looks just like an SML program.

Type-checking and Evaluation Rules

The dynamic evaluation rules of SMiLe are the same as those of SML (for the subset of the language SMiLe includes), except that SMiLe performs dynamic type-checking. SMiLe is a dynamically typed language, so there is no static type checking of SMiLe programs.

Summary of Differences with SML

  • Type-related syntax is not supported. As a result, datatypes and constructors are never declared. Just use constructors (called “tags” in our implementation) as if already declared. SMiLe constructors are not first-class. (They can be used as values.)
  • Records and record/tuple accessors (#1, etc.) are not supported. Use pattern-matching to extract tuple parts.
  • Mutual recursion with and is not supported.
  • Real numbers are not supported.
  • The sequencing expression ; is not supported. Use let instead.
  • There is no standard basis library. Everything must be written from scratch.

Many SML syntax features are available, including:

  • Multi-branch pattern-matching and curried form in function bindings.
  • Left-associative function application.
  • Syntactic sugar for lists, including [] and ::.
  • Full patterns in any binding.

Run the SMiLe Interpreter

In your local working copy of the assignment repository, run ./smile help to see how to invoke various features of the SMiLe interpreter. Since you must implement several parts to complete the interpreter, many of the ./smile commands will not do anything useful yet. However, you can run any command on the reference implementation (a completed implementation, without source code) of the interpreter by prefixing the command with ref. Note: the reference interpreter is compiled for the computing environment on the CS Linux machines; it may not work elsewhere.

Interactive REPL

To start a SMiLe REPL on the reference interpreter:

$ ./smile ref
(-: SMiLe :-)
Type Control-D to exit
=)  fun fact n = if n <= 1 then 1 else fact (n - 1)
:)  val fact = <closure for fact>
=)  val fact5 = fact 5
:)  val fact5 = 120
=)  val fact6 = fact 6
:)  val fact6 = 720
=)  ^D
(-: SMiLe :-)

Unlike the SML/NJ REPL:

  • The SMiLe REPL does not support multi-line inputs and SMiLe does not support semicolon (;).
  • The SMiLe REPL supports only bindings, not stand-alone expressions. Entering fact 5 alone as a line in the REPL session would not parse. Always use a val or fun binding.
  • The SMiLe REPL does not support use.

Source Files

SMiLe source code files use the extension .sml. To run a full SMiLe program from a file with the reference interpreter:

$ ./smile ref examples/fact.sml
(-: SMiLe :-)
:)  val fact = <closure for fact>
:)  val fact5 = 120
:)  val fact6 = 720

(-: SMiLe :-)

Additional ways of interacting with the interpreter internals will be introduced with specific tasks below.

Practice Writing SMiLe Programs

Write a few SMiLe functions and test applications of those functions in a file examples/practice.sml, then run them with the SMiLe reference interpreter. Do try this, but do not spend too long on it.

  1. Write an association list lookup function (you should be able to copy this from env.sml) and apply it to an association list [("y", 4),("x", 5),("x",2)]. The result of running the reference interpreter with this file should be something like:

    (-: SMiLe :-)
:)  val lookup = <closure for lookup>
:)  val assocs = [("y", 4), ("x", 5), ("x",2)]
:)  val lookup_x_assocs = (SOME 5)
    
(-: SMiLe :-)
  2. Write a list append function in curried form using patterns directly in the function definition (no case expressions). Remember to parenthesize the argument patterns. Apply append to a pair of lists.
  3. Copy some of your bintree or bst functions and call them on the sample trees from the previous assignment. Remember, SMiLe does not support static types or type declarations, so just go ahead and use the tree constructors without declaring them.

Skim the Interpreter Code

We provide the code of the reference interpreter, but with several core features removed. Tasks below will guide to implement the missing features by editing the eval.sml, sugar.sml, and scope.sml files. Take a quick look through the following files to get your bearings.

Key files that you will use or edit:

  • ast.sml: the definition of Abstract Syntax Trees (ASTs) for the SMiLe language (SmileAst structure), annotated with their correspondence to the concrete syntax, plus functions to pretty-print SMiLe ASTs in the concrete syntax
  • sugar.sig (complete) and sugar.sml (partial): static desugaring operations to simplify syntactic sugar in SMiLe ASTs (SmileSugar structure)
  • env.sig (complete) and env.sml (partial): your implementation of environments, used by the interpreter (Env structure)
  • eval.sig (complete) and eval.sml (partial): evaluation of SMiLe programs and ASTs (SmileEval structure)

Supporting files that you will use but generally do not need to understand:

  • parser (complete): the parser that translates programs from strings to ASTs (SmileParser structure). Ignore unless you are curious. (Take CS 301 for more on how this works.)
  • smile (complete) and main.sml (complete): command-line interface to the SMiLe interpreter (SmileMain structure)
  • smile.sml (complete): top-level SMiLe interpeter operations (Smile structure)

Files supporting testing:

  • unit-tests (add more): tests of interpreter functions that act by calling those ML functions directly
  • examples (add more): example SMiLe programs that also act as full-interpreter tests
  • test.sml (add more): testing infrastructure for running full-interpreter tests (SmileTest structure)

Files supporting optional tasks:

  • scope.sig (complete) and scope.sml (partial): static scope-checking for SMiLe ASTs (SmileScope structure)

The basic operation of the interpreter goes like this:

             +-------------+         +---------------+         +-------------+         +------------+
             |  (complete) |         |   (partial)   |         |  (optional) |         |  (partial) |
source.sml ---->  parse  ----> AST ---->  desugar  ----> AST ---->  check  ----> AST ---->  eval  ----> output
             |             |         |               |         |             |         |            |
             +-------------+         +---------------+         +-------------+         +------------+

On Metaprogramming

Metaprograms are programs written in an implementation language whose inputs or outputs are programs in a source or target language. Implementing a source language using a similar implementation language, as we are implementing the source language SMiLe with a metaprogram in the implementation language SML, has benefits and pitfalls.

  • The most visible pitfall is potential confusion between the source language features you are implementing and the implementation language features you are using in the implementation.
    • It helps to prefix each feature name by the language name when you speak about it. “To implement SMiLe pattern-matching I need to ML pattern-match on the ML value representing a SMiLe pattern to determine what kind of SMiLe pattern it is.”
    • It can also help to use this naming convention in code, e.g., an ML variable called smile_pattern hold an ML value of type SmileAst.pattern that represents a SMiLe pattern.
  • On the other hand, this forces you to be vigilant in keeping the source-vs.-implementation distinction straight, helping you learn to think clearly about the distinction between the source language and its implementation.
  • Implementing many of the evaluation rules of SML as evaluation rules for SMiLe will help you understand SML more clearly (I’m looking at you, pattern-matching!) and improve your SML and general programming skills.

3. Abstract Syntax Trees and Syntactic Sugar

In this part you will explore the ML representation of SMiLe programs as Abstract Syntax Trees (ASTs) and desugaring of SMiLe programs. You will read the file ast.sml in detail and edit the file sugar.sml. You will submit the code that you write for this task, but you do not need to submit answers to the other questions. They push you to understand key features of the AST representation before you start programming with it.

  1. Read ast.sml to familiarize yourself with the Abstract Syntax Tree representation of SMiLe programs defined in the SmileAst structure in that file. ML datatypes and pattern-matching are beautifully suited to this sort of task. Roughly: one ML type corresponds to one non-terminal in the (simplest) SMiLe grammar; each constructor/tag of this type corresponds to one production of that non-terminal. The ML keyword and supports mutually-recursive datatypes or functions that refer to each other.

  2. Inspect ASTs: Run the command ./smile ast examples/fact.sml to display the AST of the SMiLe program defined in examples/fact.sml.

    • Read the “raw” version of the AST, represented using the SmileAst.program type.
    • For each ML datatype constructor appearing as a node in the raw AST, determine what part of the concrete syntax of the source program examples/fact.sml corresponds to that node in the AST.

  3. Design question: Why are SMiLe tuple expressions represented with by an ML list of SmileAst.expr instead of an ML tuple of SmileAst.expr?

  4. Desugaring in the parser: The provided parser for SMiLe’s concrete syntax does some desugaring before constructing ASTs.

    • Examine the provided SMiLe file examples/lists.sml and raw AST from the output of ./smile ast examples/lists.sml.
    • Find two or three syntactic constructs (at least one in fun bindings and one in constructors/tags) used in these programs that are not representable directly by our ASTs. Describe how the parser appears to rewrite each syntax to fit our AST representation.

  5. Desugaring ASTs after parsing: The SmileSugar structure in sugar.sml implements functions for additional desugaring of ASTs by replacing all occurrences of AST nodes with combinations of other nodes that have equivalent behavior.

    • Read the implementations of the SmileSugar functions.
    • Change the desugar_expr function to replace IfThenElse AST nodes with Case AST nodes that encode the same SMiLe computation as the original IfThenElse. The interpreter implementation will not handle IfThenElse during evaluation.
    • Confirm the validity of your transformation by running ./smile ast examples/fact.sml and inspecting the difference between the raw and desugared ASTs as well as the “pretty-printed” desugared AST, which is created by calling SmileAst.show desugared_ast. The resulting desugared program should behave just like the original.

  6. git add any new files, then git commit and git push your work! It’s a good backup in case things go wrong later.

4. Implement Evaluation Rules of Basic SMiLe Features

In this part you will explore the ML SmileEval structure in eval.sml, which contains code for evaluating SMiLe programs represented as ML SmileAst.program values, and extend it by implementing evaluation rules for a couple basic SMiLe language features: structural equivalence checks (used by SMiLe = and SMiLe pattern-matching) and evaluation rules for SMiLe tuple expressions.

  1. Warmup: Read eval.sml up through the definition of the environment type. Consider the following questions:

    • How do values built by the ClosureValue constructor differ from the closures we have drawn in environment diagrams? Speculate on reasons for these differences.
    • Why is the function name represented by a var option instead of just a var?

    Consider what you learned about creating cyclic structures in past reading about Lisp. You do not need to submit answers to these questions.

  2. Warmup: Read the definition of eval_expr in eval.sml. Read several cases from eval_expr to get a feel for how the SMiLe evaluator works and inventory which kinds of SMiLe expressions are currently supported and which are not.

    With your Env structure implemented, you should be ready to run the simplest of SMiLe programs with your interpreter, even though it is missing several features. Try ./smile examples/simple.sml.

    $ ./smile examples/simple.sml
(-: SMiLe :-)
:)  val x = 5
:)  val y = 10
:)  val z = false
    
(-: SMiLe :-)

  3. Implement the helper function SmileEval.eq : value * value -> bool to compare the two SMiLe values, represented as ML SmileEval.values, recursively using deep structural equivalence. This function is used to implement the SMiLe = operator (as well as part of pattern matching).

    • Two non-closure SMiLe values are equivalent if and only if they have the same SMiLe type (represented by an ML constructor) and their corresponding sub-values are equivalent.
    • SmileEval.eq returns false if any of its arguments contains a SmileEval.ClosureValue representing a SMiLe closure. If not for this restriction, it would be possible to implement eq using ML =. Use ML pattern-matching in a recursive ML function instead.

    Test your function on several cases. To do so, use ./smile meta to run an SML session with the SMiLe libraries loaded. You are encouraged to write down tests in files so that they can be run repeatedly. In the ./smile meta SML session, you can use "unit-tests/test-eq.sml"; or you can simply run ./smile meta < unit-tests/test-eq.sml. We have provided a few starter tests in the file unit-tests/test-eq.sml. You should add more!

    Debugging: If you wish to experiment interactively with the internals of your implementation, you can use the ./smile meta session (an SML REPL) without any file. You may wish to repeat some of the lines from the top of our test-eq.sml file to open various structures and import their names (otherwise you must use, e.g., SmileEval.eq) and to set the maximum depth and length of values that the SML REPL will print when showing results (see Control.Print....).

    You should now also be able to run your interpreter on SMiLe programs that use the = operator. Write and test some additional programs in examples that use just the basics available so far.

    $ ./smile
(-: SMiLe :-)
Type Control-D to exit
=)  val yes = 3 + 4 = 5 + 2
:)  val yes = true
=)  val no = 3 + 4 = 7 + 8
:)  val no = false
=)  ^D
(-: SMiLe :-)

  4. Implement the evaluation rule for SMiLe tuple expressions (represented by SmileAst.Tuple AST nodes) in SmileEval.eval_expr.

    • Evaluating a SMiLe tuple expression evaluates each SMiLe subexpression in order to create a SMiLe tuple of values.
    • Try to accomplish this in just one extra line of ML code. (Hint: think higher-order functions!)

    Test your implementation by writing some unit tests for SmileEval.eval_expr in unit-tests.sml/test-eval_expr.sml, copying the general approach of the unit test file for eq. Run these tests with ./smile meta < unit-tests/test-eval_expr.

    You should now also be able to run your interpreter on SMiLe programs that use tuples. ./smile examples/tuples.sml. Write and test some additional programs in examples that use just the basics available so far.

    $ ./smile examples/tuples.sml
(-: SMiLe :-)
:)  val t1 = (7, ("hello world", true))
:)  val t2 = ((7, ("hello world", true)), 251, (7, ("hello world", true)))
:)  val not_same = false
:)  val same = true
    
(-: SMiLe :-)

  5. git add any new files, then git commit and git push your work! It’s a good backup in case things go wrong later.

5. Implement SMiLe Pattern Matching

In this part you will implement pattern matching support for SMiLe case expressions. A SmileAst.Case AST node carries a SmileAst.expr, e, representing the object (target) to evaluate and match against a (SmileAst.pattern * SmileAst.expr) list representing the branches of the SMiLe case expression. You will implement pattern-matching support with two SML functions, SmileEval.match and SmileEval.eval_cases, that will require about 25-40 lines altogether, but they both consist of a collection of small simple cases. This is the largest single programming task in this assignment.

  1. Review the Case branch of the SmileEval.eval_expr function. Note the arguments it passes to SmileEval.eval_cases. eval_cases does the work of search for the first matching SMiLe pattern and evaluating the associated SMiLe expression. To check whether a SMiLe matches a SMiLe value and extract any SMiLe bindings this match introduces, eval_cases uses the helper function SmileEval.match.

  2. Implement SmileEval.match, a recursive function that checks to see if a SmileEval.value matches a single SmileAst.pattern. The match function takes four arguments in curried form:

    1. The ML function to call to add new bindings to a SMiLe environment.
    2. The SMiLe value to match against.
    3. The SMiLe pattern to try.
    4. The SMiLe environment to extend.

    If the SMiLe value and SMiLe pattern match (as defined below), match returns SOME of an environment that is the initial environment (as passed to match), extended with all the bindings the SMiLe pattern-match introduces. If there is no match, match returns NONE.

    The implementation should use ML pattern-matching to ML-pattern-match simultaneously on an ML constructor for a SmileEval.value and an ML constructor for a SmileAst.pattern.

    Given a SMiLe value, v, and a SMiLe pattern, p, either p matches v or it does not. If they match does, the match returns an environment extended with new SmileAst.var * SmileEval.value bindings. The order in which bindings are added in a match does not matter. Assume that one pattern binds each possible variable at most once. In other words, no pattern will include VarPattern "x" more than once, so shadowing and binding order are not issues.

    The rules for SMiLe pattern matching should be unsurprising:

    • Wildcard matches everything and produces no bindings.
    • VarPattern s matches any value v and binds s to v.
    • UnitPattern matches only UnitValue and produces no bindings.
    • BoolPattern false matches only BoolValue false and produces no bindings (and similarly for true).
    • IntPattern 17 matches only IntValue 17 and produces no bindings (and similarly for other integers).
    • StringPattern "smile" matches only StringValue "smile" and produces no bindings (and similarly for other strings).
    • TuplePattern ps matches a value of the form TupleValue vs if ps and vs have the same length and each element of ps matches the corresponding element of vs. The match introduces all bindings introduced by all elementwise submatches.
    • TagPattern (s1,p) matches TaggedValue(s2,v) if s1 and s2 are the same ML string (via ML =) and p matches v. The match introduces all bindings introduced by the match of p and v. We call the strings s1 and s2 the constructor name or tag name.
    • Nothing else matches.

    Use bind (the argument) instead of Env.bind when you need to introduce new bindings into an environment. This allows the caller of match to decide whether to use normal Env.bind or a version that additionally prints the bindings it introduces.

    Test your match implementation by creating a test-match.sml with some test cases (test-eq.sml is a great template; change the inputs) and running it with ./smile meta < unit-tests/test-match.sml.

  3. Implement eval_cases, a function that takes three arguments:

    • v : value, the SMiLe value to match against.
    • cases : (pattern * expr) list, the ordered list of pairs of SMiLe pattern and corresponding SMiLe result expression.
    • env : environment, the environment to extend with match bindings and use to evaluate the chosen result expression.

    eval_cases iterates through the list of cases in order, applying match to the arguments Env.bind, v, each SmileAst.pattern, and the given env, until it finds a SmileAst.pattern that matches v.

    • For the first SmileAst.pattern that matches v, eval_cases evaluates the associated SmileAst.expr from the list, using the match environment returned by match (which is env extended with all bindings introduced by the match).
    • No patterns after the first match are considered. At most one expr is evaluated.
    • If no pattern matches, call SmileEval.match_error to report the error.

    Test your eval_cases implementation by creating a test-eval_cases.sml with some test cases (test-eq.sml is a great template; change the inputs) and running it with ./smile meta < unit-tests/test-eval_cases.sml.

    You should also be able to run concrete source programs that use case expressions. Try ./smile examples/pat.sml and write more of your own.

    $ ./smile examples/pat.sml
(-: SMiLe :-)
:)  val x = 10
    
(-: SMiLe :-)

  4. git add any new files, then git commit and git push your work! It’s a good backup in case things go wrong later.

6. Implement SMiLe Bindings and Function Application

  1. Implement SmileEval.eval_binding: Implement Val and Fun bindings in eval_binding.

    SmileEval.eval_binding takes a function for adding bindings to environments, a SMiLe binding, and the current SMiLe environment. It evaluates the SMiLe binding, and returns the SMiLe environment extended by the binding. This requires 5-10 lines of ML code, most for Val bindings.

    • SMiLe val bindings evaluate their SMiLe expression, then match their SMiLe pattern against the result value. If the result matches the pattern, any bindings from the match are added to the current environment. Use the match function to your benefit.

    • SMiLe fun bindings introduce a binding from the function’s name to a SMiLe closure value for the function.

    Use bind (the argument) instead of Env.bind when you need to introduce new bindings into an environment or pass a binding function to a helper function. This allows the caller of eval_bindings to decide whether to use normal Env.bind or a version that additionally prints the bindings it introduces.

  2. Read and describe (in comments with the code) how the SmileAst.Let case in SmileEval.eval_expr and the top-level SmileEval.eval_program work. Notice that these two are highly similar.

  3. Implement SMiLe function application (call) expressions: Review the evaluation rule for function application and implement it in the SmileAst.Apply case of SmileEval.eval_expr. If something other than a ClosureValue is encountered where you expect the closure, use the function dynamic_type_error to report it.

    Recall that SMiLe functions all support multi-branch definitions. Rather than a single argument and a single body expression, SMiLe functions have lists of pairs of SmileAst.pattern and associated SmileAst.expr, matching the multi-branch function defintions familiar from ML. This means that evaluating a function call requires pattern-matching to choose the right branch and binding variables in the pattern to parts of the argument value. This should feel highly similar to the treatment of SmileAst.Case expressions!

    An important distinction with our earlier graphical representation of closures is that SMiLe closures in this implementation carry an environment that does not bind the original name of the function. (That would require mutation and we can get away without it!) Instead, a function’s name is carried separately in the closure. To support recursive functions, you must ensure that the function’s name (if any) is bound in the environment where you evaluate its body. (Use Env.bind.)

    Testing: At this point, your interpreter should be ready to run all valid SMiLe programs. You can test individual programs with ./smile examples/fact.sml, for example, or run a suite of full-interpreter tests with ./smile test to test all of the example programs in the examples directory. You should also write some of your own test programs. The provided examples are by no means exhaustive. Often you will be able to repurpose older SML code for this, removing use of any types/exceptions to work with SMiLe. See how much of prior assignments you can get running. Write new code. Go wild! 8^)

  4. git add any new files, then git commit and git push your work! It’s a good backup in case things go wrong later.

Optional Tasks

Be sure to complete the required tasks and submit them before trying any of these optional extensions. These are here if you are curious; they are not intended for extra credit.

7. Static Scope Checking (optional)

Implement the SmileScope.freevars function in scope.sml. Its job is to find all the unbound (or “free”) variables used in a SMiLe program AST. Once you have implemented this function any SMiLe programs with scope errors will be rejected before they are sent to the evaluator.

Your implementation will traverse the AST, tracking a simple static environment of type (Ast.var, unit) Env.t that tracks the set of variables that will be bound in the current scope. As you descend through a binding, you will grow this environment, binding any bound variables to the unit value to indicate they are bound in the current scope. When the functions reach lists of cases (pattern/expression pairs), they should consider all possible cases.

Your implementation will follow a shape that is fairly similar to the SmileEval functions (and their supporting helpers), but instead of evaluating and following just one path through the AST, freevars will perform one full tree traversal, visiting every part of the tree once.

You will want to define ML helper functions to work over bindings and exprs found in programs. Use the ML and form for mutually recursive functions:

fun freevars prog = ...
and freevars_binding b env = ...
and freevars_cases cases env = ...
and freevars_expr e env = ...

While checking for free variables, also check for conflicting bindings in a single pattern. Patterns should bind any given variable at most once. A variable cannot appear twice in a pattern. For example, the SMiLe (or SML) pattern (x,x) is illegal. (As an AST, this would be TuplePattern [VarPattern "x", VarPattern "x"].) Raise an exception if you find conflicting bindings in a pattern.

8. A Simpler Language (optional)

In this part, you will explore one last instance of syntactic sugar.

You have already investigated several examples of desugaring in our implementation of the SMiLe language. If all instances of an expression form can be rewritten to other forms in the language to produce an equivalent program, we know that this form is “just syntax;” it does not contribute any “interesting” semantics to the language beyond the semantics of the other existing expression forms. We will soon take this to the extreme in class, showing that it is possible to implement any computation using no more than single-argument functions, function application, and literally nothing else. For now, we content ourselves with writing off a couple more essential expression forms in our language as mere syntactic sugar.

At this point we have seen that there are many similarities between SMiLe/SML let expresssions, case expressions, and function application expressions. Evaluation of each of these involves:

  • evaluating one or more argument expressions, pattern-matching against the result, and introducing bindings to parts (or the entirety) of the result:
    • in function calls: the argument expression
    • in let expressions: the binding expressions
    • in case expressions: the target expression
  • and evaluating one “body expression” in some environment extended with these bindings:
    • in function calls: evaluate the body expression in the definition environment extended by the match
    • in let expressions: evaluate the body expression in the current environment extended by the matches
    • in case expressions: evaluate the expression following the matching pattern in the current environment extended by the match

Currently, the interpreter exploits these similarities to share significant code among the evaluation rules for these three expression forms. Nonetheless, the interpreter would be simpler if we had fewer evaluation rules.

Implement two of the three (let, case, or function application) as sugar in terms of the third:

  • Modify SmileSugar.desugar_expr to do the desugaring.
  • Modify SmileEval.eval_expr to eliminate the cases that have now been handled by desugaring.

9. More Ideas (optional)

  1. Closure Size Optimization: Adapt your implementation of helper functions for freevars (functions that find free variables) to optimize the space used for function closures. Our current implementation of closures keeps around the entire environment, even the parts that the closure will never need. By running freevars_expr on the body of a function starting from a static environment that contains only variables that will be bound as part of the function application evaluation rule, you can detect the free variables of the closure – those variables that may be referenced when no binding is in scope within the give expression. These are the only variables the closure could ever need from its environment. Thus, we might save space by storing an environment in the closure that binds only these variables. Do this.

  2. For a much larger challenge, add an ML datatype SmileAst.typ describing types of SMiLe expressions. Add a SmileTypeCheck structure with a typecheck function that takes a SmileAst.expr, a static typing environment mapping variables to types, and a proposed typ for the expr, and decides whether expr may have this type. Emulate the SML type system as closely as possible. Edit the sources.cm file to include the new structure in the build. Not satisfied? Think about how type inference might work. I can share some literature on this if you are curious.

Submission

Remember to git add any new files (such as tests) that you created.

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

  1. Make sure you have committed your latest changes.

    $ git add ...
$ git commit ...

  2. Run the command cs251 sign to sign your work and respond to any assignment survey questions.

    $ cs251 sign

  3. Push your signature and your latest local commits to the hosted repository.

    $ git push

Confirm: All local changes have been submitted if the output of git status shows both:

  • Your branch is up to date with 'origin/master', meaning all local commits have been pushed
  • nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.