Interpreter, Last portion

Table of Contents

This assignment is the final phase of your interpreter! Most portions within it are independent, which gives you more flexibility at this busy point in the term to work on your project and divide some of the effort among your team members. That said, don’t underestimate the amount of work here; this assignment has more perhaps more individual pieces to do than any of the other interpreter project parts.

Under college policy, I may not grade any work that has been submitted beyond the end of the last final exam time. That means that the usual course late policy will not be in effect. Any requests for an extension must be submitted via an application to the Dean of Students office. That application states that personal extensions such as these will only be granted for “personal reasons such as illness or unusual circumstances beyond the student’s control.”

This is an interpreter project team assignment, which means that if you are working on a team with someone else, you and your partner should do your best to even the workload between you. Strict pair programming is not required, but you should make sure that both team members are contributing to the project. I do recommend that you try to do pair programming if it is convenient to do so.

1 Get started

Hopefully, you’ve got the hang of it by now as to how these projects start. Feel free to go back again to the tokenizer assignment if you want detailed instructions on how to clone the repository to Repl.it. Here is the new GitHub Classroom link that you’ll need to create the repository on GitHub. Once you have created your repository, its name will have final as a prefix.

2 Functionality

Required additions to your interpreter are as follows:

2.1 Some missing special forms

Implement the following special forms: let*, letrec, set!, begin, and, and or.

  • let*: Read the specification in Dybvig. This is easiest to handle by creating a new frame for each binding.

  • letrec: You may read the specification in Dybvig, though the clearest explanation I’ve been able to find is the one on the first two pages of this Fixing Letrec paper. The paper is about how to make letrec more efficient, and you should ignore essentially all of it, but the first two pages do a decent job of laying out the specific details of how letrec works. One detail you’ll notice in the paper is that the language standard leaves unspecified what should happen for an example like this one: 

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

    Guile appears to return “nothing”; if you use display, Guile will show you this is an unspecified result: 

      scheme@(guile-user)> (define y 5)
  scheme@(guile-user)> (display (letrec ((x y) (y x)) x))
  #<unspecified>

    For your interpreter, I have added a type to value.h called UNSPECIFIED_TYPE. This is what you should return from letrec in a situation such as the above. Likewise, so that we can grade this reasonably, your interpreter should display #<unspecified> if letrec runs into the above situation.

    Here is an example: 

      $ cat test-in-01.scm
  (letrec ((x 2) (y 3)) x)
  (letrec ((x y) (y x)) x)
  $ ./interpreter < test-in-01.scm
  2
  #<unspecified>
  • set!: Read the specification in Dybvig. This should be similar to define, except that it does not create a new variable; rather, it modifies an existing one.
  • begin should evaluate each of its arguments and return the result of the last argument. Read the specification in Dybvig. If there’s nothing to return (i.e. zero arguments to begin or no true cases for cond), return VOID_TYPE.
  • Implement and and or. Note that and and or are special forms; make sure you understand why. You should be able to create cases with side-effects generating code (like set!) where the special form nature of and and or matters.
    • and and or both have specified behavior if you supply no arguments to them, or if you supply arguments that aren’t Booleans. We will not test any of those cases.

2.2 More primitive functions

The following arithmetic functions are required: -, <, >, and =.

3 Exemplary functionality

There is some functionality that your interpreter will likely need if you want your interpreter to successfully run with the Scheme assignments that you built early this term. I’m putting all of this functionality in the “exemplary” category. If you are swamped for time and are looking for just “meets expectations,” you can skip this section.

  • Implement cond.
    • You may assume that all of the conditions for cond have type boolean; we will not test otherwise. Your code for cond should allow either #t or else as a default case. (If you’ve done things right, #t should work automatically; you’ll need to code else as a special case.)

    • Strangely, cond technically allows additional arguments or none at all following the condition, like: 

          (cond (#t 3 5 7))
    (cond (#t))

      We will not test any cases like this, and you do not need to implement them.

  • For both cond and begin, if there’s nothing to return (i.e. zero arguments to begin or no true cases for cond), return VOID_TYPE.
  • Additional primitive functions:, *, /, and modulo.
    • * should be able to take any number of numeric arguments >= 2, but for the other functions you may assume two numeric arguments (i.e., print evaluation error if not).

    • / should return a real (i.e., double) if the numbers do not divide evenly. (DrRacket returns a fraction; don’t do this.) For example, (/ 5 2) should return 2.5. We will only test division with two arguments.

      modulo may further assume that its arguments are integers. We will not test non-integer cases for modulo.

4 Capstone work

Work in this section is 100% optional, and doesn’t contribute towards your grade. Nonetheless, if you’re looking for an extra challenge, these are fun additional exercises to try.

  • 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 me easily that this is really working. One approach might be to have the system display to the screen a count of the number of Values freed every time the garbage collector is run, and submit some demonstration code that shows that the number of Values being freed is correct.
  • (load "file.rkt"). 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: 

    $ ./interpreter
> (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). You should only print the prompts if stdin is not 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.

5 Your repository and your files

Your repository will follow the same structure that it has for the previous assignments. There should be no changes at all in the files that I provide; you’ll then need to add in the files from your previous version, and/or switch over to using my binaries. But note that the binaries I provide only go through part 4 of the project. (The project gets too intermingled at this point for me to be able to supply complete partial work.)

Building and testing your code will work precisely the same as on the previous assignment.

6 What to submit

Make sure that you have added files if necessary, then push to GitHub. (You can leave out your compiled executables as well as the .o object files if you wish.)

Make sure to label your submission as usual via an appropriate commit message, and make sure your tests have run on GitHub.

Have fun interpreting!

This assignment was originally created by David Liben-Nowell and has since been updated by Dave Musicant, Jed Yang, and Laura Effinger-Dean.