SlytherLisp Project

SlytherLisp is a lexically-scoped Scheme-like programming language that you will implement and interpreter for. To get started, form a team on GitHub Classroom, which will create a private repository for your group on GitHub.

The very first thing you should do is open up and read README.rst. This will instruct you on how to setup and get going with the project.

Partners Required

You are required to complete this project in a group of two or three. Please use Piazza as a resource in finding your group.

If you really want to work alone, you can Email me and ask for permission.

Deliverable 1: Basic Data Structures

Due Date:Wednesday, September 26 at 11:59 PM

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!).

Note

It is advised that you finish Deliverable 1 early so that you can get a head start on the next deliverable.

Deliverable 2: Parsing

Due Date:Wednesday, October 10 at 11:59 PM

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

Deliverable 3: Evaluator

Extended Deadline:
 Friday, October 26 at 11:59 PM (was Wednesday, 10/24)

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 please plan ahead and get started early.

By the end of this deliverable, you should have a working REPL, which you can use to compute the results of basic mathematical operations, such as (+ 1 (* 2 3)). Please be sure to test your REPL, as there are no unit tests for this. You will receive a low grade on this deliverable if you do not have a working REPL.

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

Note

It is advised that you finish Deliverable 3 early so that you can get a head start on the next deliverable.

Deliverable 4: Language Structures

Due Date:Friday, November 2 at 11:59 PM

Deliverable 4 is an extension of Deliverable 3, you will complete the remainder of the builtin operations for the SlytherLisp language, as defined in the docstrings of slyther/builtins.py.

Deliverable 5: Tail-Call Optimization

Due Date:Friday, November 16 at 11:59 PM

For this deliverable, you’ll be extending SlytherLisp by extending your work from Deliverable 3 to use 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. At this point, all of the provided code examples should run. You will receive a low grade on this deliverable if all of the code examples do not produce a correct result. Be sure to check your results for correctness. For example, if the primes example is producing numbers that are not prime, then it is not correct.

You are free to implement tail call optimization however you wish, but you implementation must be properly tail-call optimized. We will use the same definition as the Scheme specification to determine if your implementation is properly tail-call optimized:

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.

Deliverable 6: Extending the Language

Due Date:Friday, November 30 at 11:59 PM

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

  • A match macro that behaves like Racket’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. Since macros are first class, you could even add anonymous macros to the language.
  • Making the cons form allow for a tail recursive CDR argument by using the tail call modulo cons technique.
  • Adding functions with default parameters and keyword arguments
  • A use macro, such as proposed in one of the LGA-06 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 7: Extra Credit

Due Date:Friday, December 7th at 11:59 PM

Note

This deliverable is optional. If you do not want the extra credit, you may simply ignore it.

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 I will need time to grade before grades are due.

Grading Rubric

This project 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
15% Deliverable 3
15% Deliverable 4
20% Deliverable 5
20% Deliverable 6
25% XC Deliverable 7: Up to 25% extra credit, which works out to 6% on your overall course grade