The sixth(?) Assignment is to introduce a new form: letrec-datatype that works like define-datatype but is lexical, instead of global.It might look something like this:
(letrec-datatype ([ls ls? (kons (kar symbol?) (kdr ls?)) (nl)] [ ... there could be other data types here ]) ls)
Note the above form returns a type (so these types have to have indefinate extent. Also note that the types may be recursive interms of one another (if we had a foo type in the above clause, it could use ls? and ls could use foo?). Like define-datatype, you'll need a cases statement also.
This is an open-ended assignment, you might not have working code by Thursday, but you should atleast have some ideas
(define abstract (lambda (x body) ...))When abstract returns, the variable x has been removed from the body. You will need a driver, translate, that will call abstract only when the argument is a lambda.
(define translate (lambda (e) (match e ((lambda (,x) ,body) (abstract x body)) ((,[rator] ,[rand]) `(,rator ,rand)) (,x (guard (synbol? x)) x))))When you get an asnwer for (! 5), translate it back into S's, K's, and I's. When you run the lambda calculus, just use normal-order reduction. The third exercise is to implement the pure lambda calculus. The goal is to implement and test (! 5). Recall that the pure lambda calculus has only variables, x applications, (M N), and abstraction, (lambda (x) M) and nothing else. It does not have conditionals, primitves, constants, etc. Also, to make the exercise just that much more exciting, at every step, you must collect all the redex/context pairs, and then throw a random number at this list of pairs to decide how to reconstruct the lambda term, to start the process again. The computation terminates when this list is empty. At that point, you might consider how you will take the resultant lambda term and cause it print as the number "120". The second exercise is to implement begin*, which is like begin, but as part of the expansion, it flattens out the begin*, so that there is only one begin* at the top-level. Watch out for part two, where one of the expression could be a macro call and it too might expand to a begin*, which has to be flattened into the one begin*. So we begin.
(fresh (x y z) (== 'a x) ...)could have been rewritten as
(fresh (y z) (let ((x 'a)) (all ...)))or even
(let ((x 'a)) (fresh (y z) ...))So, here is the statement of the problem:
(fresh (... x ...) ... (== E x) ...)
(fresh (... ...) (let ((x E)) (all ... ...))).
walk, for example. Write a
syntax-rulesmacro that implements a new "smarter"
syntax-rules. For example, you can write something that determines if a symbol is among a list of symbols. You can use this to determine whether a lexical variable is in a list of lexical variables. This would certainly come in handy. You may also change the syntax of
==to require additional information. Thus, the user who wants to gain the efficiency from this feature may have to include more information.