As we explore interpreters for the next several weeks, on occasion I will ask you to extend yourself beyond what the book presents.
This week, we begin with substitution. Or, if you prefer, this will be how we introduce the more general concept of naming into our programming language. Currently, AE only allows arithmetic expressions; we will extend it with with to allow the introduction of variable bindings, and (therefore) we'll call it WAE.
The Structures
Your interpreter should make use of the following data structures:
;; binding isa id WAE
(struct binding (name named-expr))
;; num isa number
(struct num (value))
;; binop isa symbol WAE WAE
(struct binop (op lhs rhs))
;; with isa binding WAE
(struct with (binding body))
;; id isa symbol
(struct id (name))
Your interpreter needs to use these structure definitions and obey these contracts so that it will be compatible with the tests written by your classmates.
The Functions
Your parse and interp code should obey the following contracts:
;; parse : s-exp -> WAE
;; Consumes an s-expression and generates the corresponding WAE
(define (parse sexp)
...)
;; interp : WAE -> number
;; Consumes a WAE representation of an expression and computes
;; the corresponding numerical result
(define (interp expr)
...)
If everyone obeys these names and contracts, then our unit tests will work across all interpreter implementations.
Unit Tests
Before you go much further, work with a partner to produce a set of tests for this language. This implies, of course, that you have read how with works, and are ready to begin implementing. For example, you should be able to write a parser and interpreter that transform the WAE program
{with {x 5} {+ x x}}
into the Scheme value 10.
Post your tests to Sakai. Under "Resources" I created a folder called WAE Unit Tests. That hyperlink may even take you there, if you are logged into Sakai. Create a file called username-WAE-tests.rkt and upload it to this folder. Include at the top of the unit tests file a comment header that includes your name, your partner's name, and the date.
How many tests? The great singer-songwriter Madonna once sang "How many roads must a man walk down?" Or, perhaps that was Simon and Garfunkel... anyway, my point is that you should have enough tests to be convinced your language implementation handles the cases it needs to handle.
Testing for errors: If you want to include tests that should cause either the parser or interpreter to fail, you may use the form check-error. You can look it up online. It explicitly expects the expression it is given to fail, and reports a "pass" if the expression dies. This gives us a way to write tests for our interpreter that cause it to crash.
Check in with me or Zach when you have written your test suite.
Implement with
Implement substitution on the with form. This is described in Chapter 3 of PLAI.
You and your partner should pause here to update your lab notebook with any challenges or confusion you encountered along the way. And, therefore, you should also note what you then did to overcome your confusion. Externalize your learning through the use of your lab notebook.
Checkpoint
<WAE> ::= <num>
| {<binop> <WAE> <WAE>}
| {with {<id> <WAE>} <WAE>}
| <id>
<binop> ::= + | - | * | /
where an <id> is not +, -, *, /, or with.
Your interpreter should, at this point, handle the above grammar.
Download the unit tests from your classmates, and include them in your own testing.
Extension: Conditionals
Our language is boring. We cannot make decisions.
Add the form if0 to your language. It should test whether the test-expression is zero; if it is, it evaluates the true-expression. Otherwise, it evaluates the false-expression.
For example:
{if0 0 1 2} returns 1.
{if0 {- 3 {+ 1 2}} 2 3} returns 2.
Introduce the data structure definition
;; if0 isa WAE WAE WAE
(struct if0 (test-exp true-exp false-exp))
to your definitions list.
Extend your unit tests to include this language extension. Then, extend your parser and interpreter to handle this language extension; all previous tests should continue to pass.
Upload your new unit tests to Sakai as
username-if0-WAE.rkt
Optional Extension: multi-armed with
Extend your with implementation to support multiple bindings. For example:
{with {{x 5} {y 4}} {+ x y}}
should evaluate to 9.
Extend your test suite, and save those tests as
username-mWAE-tests.rkt
for upload to Sakai.
Implement your parser so it handles either the original with or the new, multi-arm with. (That is, your old tests should continue to pass.)
You should have tests that include both multi-arm with as well as if0.
We're Done!
It is possible you will get within a lab period.
If so, begin reading Chapter 4.
Turn In
Please turn in:
1. Your code: username-substlab.rkt. This should include the extension for conditionals (and you may, optionally, decide not to implement multi-arm with).
2. Your unit tests: username-substlab-tests.rkt
Yes, these may be in the above file, too, but I'd like to see them in a separate file just for reading/grading purposes.
This should all go into your Sakai dropbox.
