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
ROption
s. 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.