Homework 11a

MUST BE DONE WITH YOUR PARTNER

MUST USE CHECKED-SIGNATURES!

Due Date Tues at 9:00pm (Week 11)

Purpose Implement the first version of StateLang

In this, and a subsequent, assignment, you will implement a subset of Advanced Student Language we will call StateLang: i.e., a language with functions, numbers, variable mutation, and box mutation. This assignment, which is the first half, has you just implement the "pure" part that has neither variable nor box mutation.

NOTE: In these assignments you are implementing part of ASL: you are not using ASL.

Exercises

Exercise 1 We would like to write programs in StateLang as S-Expressions. A few examples:

10

(+ 1 2)

(* (- 1 2) (/ 3 4))

(lambda (x) (+ x 1))

((lambda (x) x) 10)

i.e., we should support numbers, (binary) arithmetic expressions, (single-argument) lambdas, and function application. A couple of the positions in the syntax are special (i.e., the argument position in a lambda, and the operator in an arithmetic expression), but the rest should be able to be other expressions to support nesting.

In this exercise, you should define appropriate structs and use them to define an Expr type that captures expressions.

Exercise 2 While your structs that you defined previously should allow you to write recognizable versions of the examples above, we would like to be able to write exactly what you see above, so implement a parse function that turns an SExpression into an Expr. It should take an arbitrary SExpression as input and should use error if the input cannot be converted into an Expr.

Exercise 3 If this were like your calculator, you would proceed directly to writing eval. What is different here is that you have variables, which we have to figure out how to deal with. In BSL/ISL/ISL+, we’ve said that function application (the place where variables show up) proceeds by substitution. i.e., you evaluate the argument and then substitute for all occurrences of the function variable in its body.

In order to express that, we first need to be precise about what we mean by values. We never wrote this down for the calculator, because values in that case were just numbers. But here, values can be two things: numbers or functions! So first, define a signature Val for values.

Now, write a helper function, subst, that takes an Expr, a variable (a Symbol) and a Val. It should replace all occurrences of the variable with the value. Note: be sure you do the right thing when you cross into the body of a lambda! What should happen if the variable you are replacing is the same as the argument name of the lambda? If you aren’t sure, experiment with ISL+!

Exercise 4 Now that you have subst, you should write eval which takes an Expr and returns a Val. When you reach an application, after you evaluate the argument, use subst to substitute the argument into the body. Important note: your function may behave strangely (not in a good way) if you allow "unbound" variables to exist in expressions. The next exercise has you define a function to check for such bugs, but for this problem, you can restrict your test cases to those where such errors are absent.

Exercise 5 One error that programs can have is typos in variables. These so-called "scoping" bugs are relatively easy to detect without running the program. Design a function wf that takes an Expr and either returns the same Expr if there are no scope issues (so it is "well-formed" or "wf"), and calls error if there are. Your error should include all the scoping bugs, not just the first one! Note: you may want to define a helper with an accumulator to do this.