Reference Designs

Several of your classmates have generously agreed to share their solutions with everyone, in order for folks to study and learn from others' designs. They are all available in the designs/ folder of the cs173-python repo (you should just be able to git pull to get them). There are currently 4 solutions up, we might post more if a few folks get back to us. This page briefly describes what you might look for in each implementation.

Note that these designs were chosen mostly because they each clearly embody a particular concept that we think might be useful to consider for your design. They didn't necessarily pass all (or any) particular tests in their first handin, but are useful points in the design space that you might ultimately choose and learn from.

Design 1

This design focuses on a radically simple object core. All the different kinds of objects are represented with a single value type in the core:

  (define-type CVal
    [VObject (val : PrimVal) (fields : (hashof string CVal))])

Simple values, like integers and strings, are desugared into object expressions that evaluate to VObjects. For example, a PyNum holding 5 turns into:

  (CObject (VNum 5) (make-hash (list (values "%add" (CFunc ...)) ...)))

Where "%add" contains a core language function that performs addition on numbers (using a CPrim). Addition thus desugars from e1 + e2 into roughly

  (CApp (CGetField (desugar e1) "%add") (list (desugar e2)))

So all of the type-testing for different overloading of addition can be implemented with dynamic dispatch on the first argument.

Check out the python-objects.rkt file, and then figure out how the simple Python program print(5 + 4) is handled by this implementation, all the way through from parsing to desugaring to the core.

Design 2

This design is object-focused, much like design 1, but chooses a different representation for the different kinds of built-in objects. Check out python-core-syntax.rkt to see how things are defined. The main novelty here is that there is a separate Racket type for each kind of built-in object, written as OInt, OString, ODict, etc.

In contrast to Design 1, this implementation doesn't desugar numbers and strings to their object representations. Instead, it leaves them as simple expressions (e.g. (CInt 4)) until interpretation time, and then the interpreter turns them into objects:

    [CInt (n)
          (AObject (make-int n) store)]

Where make-int is a helper that creates an OInt object at interpretation time. This makes desugared code cleaner, but at the expense of a more complicated core. In fact, this implementation has one of the more complex core languages, but also a good grasp of Python's object model. Note that a number of object-centric operations have been worked out, like is-subclass and is-instance.

This design has a somewhat complicated definition of scope, that pays close attention to nonlocal and global. There are three different kinds of variables (defined by Var), for each of the local, nonlocal, and global cases. There are separate helpers to deal with adding declarations of nonlocal, global, and local variables in desugaring. It might not be a good starting point if you don't understand the details of these operators yet, but probably very useful if you're steeped in the details of scope and want to see how someone else is trying to tackle the the corner cases.

To understand this implementation, you should start in python-core-syntax.rkt and see how objects are defined, then check out the interpreter and desugarer. This implementation is doing a reasonable job of handling function definitions, so you can write simple programs that use def and return. Most of the built-in primitives aren't functional yet.

Design 3

This implementation has a few really neat tricks, and may be the furthest along of the ones posted here. It has an interesting solution for handling built-in functions, control operators, and has a rich object (and method-lookup) model.

One particularly interesting feature of this design is the handling of control operators and return values. In python-monad.rkt this implementation defines an answer type that is similar to designs others have discussed, for returns and exceptions:

(define-type (ROption 'a)
  [RValue (value : 'a)]
  [RReturn (value : CVal)]
  [RError (value : CVal)])
  

But then, aware of the impending cacaphony of type-cases that will result, the implementation also defines a series of helpers for dealing with ROptions. Operations over this data structure are defined in monadic style (don't worry about what that is, you can just read this code's implementation of it). The key helper is m-bind, which has the following signature:

(define (m-bind (m : (PM 'c)) (f : ('c -> (PM 'd)))) : (PM 'd)

Where PM is an alias for this type:

(define-type-alias (PM 'b)
  (Store -> (Store * (ROption 'b))))

So, PM is the type of functions that takes a store and produces a store paired with some kind of result. Does that sound like anything you've seen before? How about every single case of your ParselTongue interpreter with store-passing style? For each subexpression, the interpreter evaluates it, extracts the value and the store, does something with the value and passes the store along almost untouched.

The combination of m-bind and PM are abstracting over this pattern. Check out the body of m-bind to see that in there are basically two cases - one for lifting the function that is the second argument over the result in an RValue, or alternatively completely ignoring that functional argument and yielding a RReturn or RError again as appropriate. This may take a little bit to grok, but if your interpreter is suffering from answer-case overload, this is a great thing to spend a few hours on.

Much like Design 1, this implementation also performs primitive operation overloading via dynamic dispatch on objects. For example, there is a built-in num-type in python-lib.rkt that defines __add__ as a call to the primitive function 'add. These primitive functions are defined in python-interp.rkt. To understand these, I would start by looking at the things in python-lib.rkt and then find the corresponding uses of define-primf in python-interp.rkt to see what they do. There is a powerful pattern underlying this implementation of lifting native Racket code into the fields of the built-in objects that is worth looking into.

Design 4

And now for something completely different...

This design is focusing heavily on control via CPS. It is also the only design that decided to include more than 2 languages (a surface and a core). Instead, it has a surface language, a staging language, and a very tiny CPS core target. There's a good description in the LANGUAGES.txt file that goes along with this submission describing what each is for.

This implementation can't run many tests, but is taking control operators quite seriously and is worth looking at if you're planning on extending your implementation to handle generators, for instance. The values and object story are not as sophisticated here, so really look into this if you want to understand control better, and also if you want to see just how small a core at least one student has actual tests working for.

(There's comparatively little written about this implementation because its own README and LANGUAGES file describe it pretty well.)

Design 5

(Added Nov 7). There is one more design, which is notable for its careful attention to scope. There's a pretty detailed writeup of how they handled scope in their README; we'll leave it in their words. This implementation also already passes 12 test files.