Language Design Project: SlytherLisp

SlytherLisp is a lexically-scoped Scheme-like programming language that you will implement. To get started, download the starter code and read README.rst.

Partner Optional

You are free to work on this project with a partner if you wish, but such is not required. If you would like to work with a partner, please Email me your group by Friday, April 6th at 5 PM.

In addition, groups of three are possible. If you work in a group of three, note the additional requirements for Deliverable 4.

Deliverable 1

Due Date:Thursday, April 12th at 11:59 PM (get it done early if you want to enjoy the E-Days celebrations!)

For this deliverable, you will be implementing a few simple data structures under slyther/types.py. Replace all of the lines that say raise NotImplementedError('Deliverable 1'). Note that there’s some stuff for Deliverable 3 at the bottom of the file: you don’t have to do this (yet!).

Gradescope Submission Link

Deliverable 2

Due Date:Thursday, April 19th at 11:59 PM

For this deliverable, you will implement the tokenizer and parser of the language. You’ll be working under slyther/parser.py.

Gradescope Submission Link

Deliverable 3

Due Date:Friday, April 27th at 11:59 PM

For this deliverable, you’ll be implementing the evaluator, builtins, REPL, and functions. You’ll be working under four different files:

  • slyther/evaluator.py
  • slyther/types.py (at the bottom)
  • slyther/builtins.py
  • slyther/repl.py

This one is a big deliverable, so plan ahead and get started early.

You are not required to have tail-call optimization working for this deliverable.

Gradescope Submission Link

Deliverable 4

Due Date:Friday, May 4th at 11:59 PM

For this deliverable, you’ll be extending SlytherLisp by:

  • Extending your work from Deliverable 3 to use tail-call optimization.
  • Coming up with at least one extension to the language. Implement this extension and document it in your README.rst file.

Note that you need to do both (this is not a choice of one or the other).

Groups of Three

Groups of three must implement two significant extensions to the language rather than just one.

Tail-Call Optimization

Consider the following (simple) example:

(define (print-n-times f args n)
  (if (<= n 0)
      NIL
      (let ()
         (print (eval (cons f args)))
         (print-n-times f args (- n 1)))))

Since the call to print-n-times is the last call of the function (what returns from print-n-times is returned by the function), we can reuse our current stack frame for that function call, rather than allocating a new stack frame and returning the result of the computation.

My advice (for a starting point) is to move your lisp_eval function body into a loop, and if, at the bottom of the loop, it can reassign expr and stg and repeat rather than calling lisp_eval recursively, do so.

You’ll probably need to make modifications to other parts of the interpreter as well.

Test your optimization works using the fib-iter and carmichael examples. There is also a --tco flag to the test script that runs the carmichael example for you.

You are free to implement tail call optimization however you wish, but you implementation must be properly tail-call optimized. Per the Scheme specification, this means:

A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return.

Extending the Language

Come up with a significant extension to the language. Suggestions include:

  • A match macro that behaves like Haskell’s pattern matching
  • Adding a new syntax to the language (such as quasiquotations)
  • Optimizing the abstract syntax tree
  • Adding a library and/or namespace mechanism
  • Adding a way to load and use Python libraries
  • Allowing for user-defined macros (see defmacro in Scheme). Since macros are first class, you could even add anonymous macros to the language.
  • Adding functions with default parameters and keyword arguments
  • A use macro, such as proposed in one of the LGA-17 videos
  • Continuation
  • More and more and more inspiration
  • Any other significant extension of your liking!

Implement your extension, and document how it works in the README.rst file. Include at least one example program that makes use of your extension.

Deliverable 5 (optional)

Due Date:Friday, May 11th at 11:59 PM

Extend SlytherLisp in as many ways as you choose, and document your extensions for extra credit. For example, you might want to make the REPL nicer by using Readline or Prompt Toolkit. As another example, you might want to do a performance comparison of SlytherLisp on PyPy versus on CPython: and maybe even compare the same algorithms implemented on other languages. You could even rewrite SlytherLisp in a totally different programming language!

You are not required to maintain passing unit tests for this extra credit deliverable. Have fun!

This deliverable is worth up to 25% extra credit, but the allocation is determined based on the significance and effort of your work, so simple extensions will only receive a little extra credit. Please include an estimate for the number of hours you spent on this deliverable in your README.rst.

Note that I am not able to offer extensions on this deliverable (nor can slip days be spent) as grades are due the following Monday.

Grading Rubric

This project counts for the Language Design Project, which is worth 24% of your overall grade in the course. The grade is divided up as follows:

Percent Description
15% Deliverable 1
15% Deliverable 2
20% Deliverable 3
15% Deliverable 4: Tail-Call Optimization
15% Deliverable 4: Capable of running all provided examples
20% Deliverable 4: Extending SlytherLisp
25% XC Deliverable 5: Up to 25% extra credit, which works out to 6% on your overall course grade