Interpreter 8: Capstone

Implement the following special forms: letrec and set!.

• letrec: Recall that letrec allows you to define (mutually) recursive procedures. Take a look at the specification in Dybvig. The key difference from let is that the bound variables can be accessed from other variables bound in the same let, but unlike let*, the values can't be accessed until all expressions have been evaluated. For instance, consider:

(letrec ((x 3) (y x)) 
  x)

This violates the description in Dybvig that "The order of evaluation of the expressions expr … is unspecified, so a program must not evaluate a reference to any of the variables bound by the letrec expression before all of the values have been computed." The specification says that if this restriction is violated, an exception (i.e., evaluation error) should be raised. However, Guile doesn't handle it correctly! It prints 3. Your interpreter should handle this correctly by raising an evaluation error.

Similarly, consider:

(define y 5)
(letrec ((x y) (y x))
    x)

Again, the value of a variable is accessed before all variables are bound, so your interpreter should raise an evaluation error. This differs from Guile, which appears to print nothing in response to this.

Still not quite sure how to interpret letrec? Here's a rough guide to evaluating (letrec ((x1 e1) ... (xn en)) body1 ... bodyn), although it doesn't inclue all needed error checking:

1. Create a new frame env’ with parent env.
2. Create each of the bindings, and set the to UNSPECIFIED_TYPE (this is in schemeitem.h)
3. Evaluate each of e1, …, en in environment env’.
4. After all of these evaluations are complete, replace bindings for each xi to the evaluated result of ei (from step 2) in environment env’.
5. Evaluate body1, …, bodyn sequentially in env’, returning the result of evaluating bodyn.

• set!: Read the specification in Dybvig. This should be similar to define, except that it always modifies an existing variable, and may be used in contexts outside of the global environment (unlike how we've restricted the testing of your define implementation). We'll have set! return a VOID_TYPE, similar to define.

Implement < (the less-than function) and equal?. equal? only needs to work for numbers, strings, and symbols; it does not need to perform any sort of deep equality test on a nested structure. Also, for symbols you should feel free to just check whether the symbols are the same (e.g., <code>(define a 1) (equal? a a)</code> would return true, while <code>(define a 1) (define b 1) (equal? a b)</code> would return false).

The tests for this portion use both your old functionality and this new functionality together, which may mean lead to finding some bugs in your old code. Part of completing this assignment may involve some debugging that is not directly related to the new functionality. One note from past experience is that until now, we have had limited ability to test if you are doing the right thing when you have a let or lambda with multiple bodies. In both cases, each body should be evaluated (starting from the first), and the result of evaluating the final body should be returned.

I strongly encourage you to implement one new piece of functionality at a time, testing with small test cases as you go, and to use a debugger for debugging. This can be visually in VSCode or using gdb on the command line.

Each of these extensions counts towards one point.

• Implement additional primitives
  • * should be able to take any number of numeric arguments >= 1. Note that (* n) returns n.
  • - should be able to take any number of numeric arguments >= 1. Note that (- n) returns the number -n, while (- n1 n2 n3) returns the result of ((n1 - n2) - n3).

  • / should return a real (i.e., double) if the numbers do not divide evenly. (Guile returns a fraction; don't do this.) It's fine to only implement the two-argument case.

  • code>modulo. I recommend implementing a version where you assume that the arguments are integers.

  • >, <\=, >\= and \=. As these functions all use similar logic, you may earn at most two points from these functions, even if you implement all 4. Note that the difference between \= and equal? is that \= only works with numbers.

• Implement the Scheme function display (described further down in this section of Dybvig). The simplest cases, which are those I'd focus on, are the following:

  (display x)  ;; displays value of a particular variable
  (display "hello world") ;; displays a particular string without the quotes
  

  You can handle non-printable characters (newlines, etc) inside the strings in any reasonable way, so long as the code doesn't crash.

• Implement when (described further down in this section of Dybvig)
• Implement unless (described further down in this section of Dybvig)

• Implement additional special forms

Note that these are special forms, not primitive functions. You should be able to think of test cases (e.g., ones that use set!) where this distinction matters.

• and is a special form. and is technically defined for any number of arguments (including 0) and for any type of arguments; however, I recommend you focus on the case where you have 1 or more arguments of Boolean type. More details are available in the Dybvig specification.

• or is a special form. or is technically defined for any number of arguments (including 0) and for any type of arguments; however, I recommend you focus on the case where you have 1 or more arguments of Boolean type. More details are available in the Dybvig specification.

• Format your output so that it resembles Guile output as closely as possible. Specifically, don't have an extraneous space after the last item in a list before the closing parenthesis. You don't need to write tests for this case! (But should include it in your write up.)

• Handle additional syntax (improvements to tokenization and parsing)
  • Correctly handle square brackets. See the Parser assignment for more details on this extension.

Each of these counts for two points.

• Implement additional primitives
  • list takes any number of arguments and returns a (proper) list containing the arguments. For example, (list) returns (), (list 3) returns (3), and (list 3 4 5) returns (3 4 5).
  • map takes two arguments, a procedure and a list. It returns a new list, where the procedure has been applied to each element of the original list.
• Implement additional special forms
  • cond. It turns out cond's specification is more complex than how we used it in class. Don't worry about the non-standard syntax options, you may assume that each clause has exactly the form (bool expr), even though cond technically allows things like (bool) or (bool expr1 expr2). However, you should implement cond so that either #t or else are allowed as the default case (#t should work automatically, else will need to be handled as a special case). If there is nothing to return for cond (no true cases), return VOID_TYPE.
  • let* Create a new frame for each binding pair.

• Implement the third version of define shown in Dybvig,

which is the one that lets you use define alone as shorthand for both define and lambda:

(define (myfunction x y z)
   (+ x y z))

The above works, but is really shorthand for

(define myfunction
    (lambda (x y z)
       (+ x y z)))

• Handle additional syntax (improvements to tokenization and parsing)
  • Correctly parse dotted pairs, e.g. (a . b). Make sure that you also account for this case in the evaluation.

These ideas may require changes in what happens when you run ./interpreter, and you might wonder how to do that given that you also don't want to break the tests. One option is to make a separate C file that will just hold your main function, with the different functionality (e.g., the simple interface). You can then use an alternative Makefile that doesn't compile main.c but does compile your separate C file. You can then compile this via: make -f ReplMakefile, where ReplMakefile is the name of the new Makefile. You should give the new executable a different name than interpreter (e.g., interpreter2) and then run it by similarly on the command line (e.g., ./interpreter2).

For these extensions, you don't need to write tests, but you should describe in the write-up how I can run your extensions and check manually that they work.

If you create new files, you will need to edit ./zipitup to ensure your files are included in the Gradescope submission. After submitting, please also double-check that all necessary files are on Gradescope (switch from the autograder tab to the files tab on Gradescope).

• Garbage collection. A simple mark-and-sweep collector is relatively easy to implement and should improve your memory usage. Have some way of demonstrating to the user that this is really working. One approach might be to have some demonstration code that displays a count of the number of SchemeItems freed every time the garbage collector is run, and also display some information to help the viewer know that the number of SchemeItems being freed is correct. Please make sure that the displays happen only with your demonstration code, not when running the M and E tests.
• (load "file.scm"). This reads in a file and executes the code in the file as if it were typed in.

• A simple interface. The classic core of an interpreter is the read-eval-print loop, a.k.a. REPL. You can add this functionality to your code so that you can more easily use your interpreter interactively. For example:

  $ ./interpreterRepl
  > (define factorial
  .   (lambda (n)
  .     (if (= n 0)
  .         1
  .         (* n (factorial (- n 1))))))
  > (factorial 5)
  120
  >
  

  One issue you will run into with this is you get unnecessary printouts of prompts when you are using a file for input instead of typing the code in manually. You can figure out whether the interpreter is being called interactively using the isatty and fileno functions (man isatty in the terminal to learn more). You should only print the prompts if stdin is interactive.

  Note that you can end an interactive session by typing Ctrl-D (sending an "end-of-file" character), so there is no need for a "quit" command.

  If you really want to dive into this approach, optionally figure out how to use the readline library to provide things like history and editing for your REPL.

Most of the extensions require you to write tests to check that they work. These should be in a similar format to my M and E tests and you should put the code (.scm file) and correct output (.output file) in the user-tests directory. To run your tests, run ./user-tests from the command line. Your tests should be thorough: think about the expected input, but also weird edge cases. You are not required to write tests for cases that will fail (i.e., the ones where your interpreter will correctly print "Evaluation error") but you may do so if you like.

Please name each test file in a descriptive way (e.g., and-test1 or let-star-3).

You should list the extensions you implemented in contributions.txt. It's fine if this is a bulleted list. In this file, please also indicate if there are any edge cases that you know your code fails on. If you implemented any of the extensions that don't have a testing component, provide a description of how I can run your code to see the extensions in action. Again, if there are any edge cases that don't work, please let me know that as well.

To receive an M:

• Complete extensions totaling at least 5 points.
• Write tests for the new functionality. The tests should have comprehensive coverage of the functional code.
• Describe the new functionality in contributions.txt.
• In contributions.txt, be upfront about any edge cases that still fail.
• Write the code so that it does not contain significant stylistic or efficiency problems
• Fill out the interpreter reflection form, linked from Moodle.

To receive an E:

• Fulfill all the criteria for an M.
• Complete extensions totaling at least 10 points.
• Use good coding style and include comments on each function that you write.

As with previous assignments, there are M tests and E tests. See the section of Scheme Intro 2 labeled "How to test your work" if you need a refresher on how to run these tests. Note that the interpreter tests will fail if your code has compiler warnings and/or valgrind errors. Make sure to run the tests in the Docker environment.