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 extensions such as these will only be granted "… in the most extraordinary circumstances… 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 "Core" capstone work

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. Normally, this is a required part of this assignment, but I'm making this piece optional because of our shorter-than-usual term. It is super fun to get to see your old Scheme code (especially the sieve of Eratosthenes!) run on your interpreter. I would recommend trying to run your old Scheme assignments on your interpreter, and figure out perhaps which functionality below you need to get it to run, and do that.

Again, this is entirely optional and does not contribute to your grade, but it does add to the experience you'll have if your project can really run the Scheme code you wrote in the first few weeks.

  • Implement cond.
  • Additional primitive functions:, *, /, and modulo.

4 "Traditional" capstone work

Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.

If you have implemented any of these, explain what you have done in a readme.txt file.

  • 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, apart from an updated value.h; 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 assignments (make test, and make capstone).

6 What to submit

Push all of your files to GitHub. Your Makefile may have changed if you modified it to work with my binaries. If you did this, add a readme.txt file explaining what you did.

The graders and I need to know which commit is the one that we should use for grading. This is handled well in Git with tags. You did this back in the original clab. If you've forgotten how to tag in Git, look at the end of part 1 of the C lab. Name your tag final-done.

Have fun interpreting!

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