Assignments

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

Posted solutions

Michel

The fifth exercise is to do all this with one combinator, X. Not only do S and K make a basis, but so does X. You have to figure out what X is and write an abstraction algorithm to write (! 5) in terms of X alone. Then use the same tricks with macro expansion. to repeat the fourth exercise. Part two of this exercise is to invent two additional combinators to add to S, K, and I so that the generated combinator code is not so voluminous. The hint I gave in class is that Kyle Ross used a technical word during class on Tuesday that in fact was one of the combinators. The fourth exercise is to run a combinator-only (S, K, and I) version of the (! 5) problem. You can easily do this with identifier macros, and then expand the code to look again like the argument in the third exercise. Now, in order to do this you will need to invent the abstraction algorithm Now, I will give you the specification, but I wanted you to puzzle with it for awhile.

(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.

The first assignment is due on Tuesday 1/17/2006. Please bring copies of your work to share with the entire class. I don't yet know how many will be taking the course, but a reasonabale estimate is five. I prefer my copy to be non-landscaped, so just save the trees for the rest of the class. Be prepared to explain your solution and have it criticized by the entire class.

Here is the first assignment:

Using only the content of chapters 1, 9, and the code appendix of The Reasoned Schemer, plus I presume a healthy understanding of Scheme, see if you can take advantage of Scheme's lexically-scoping operators to simplify fresh. Consider.

(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:

Determine where and when

(fresh (... x ...) ... (== E x) ...)

can be replaced by

(fresh (... ...) (let ((x E)) (all ... ...))).

This is quite tricky, so if you think you have the right answer, think a bit harder about the problem. Either you have allowed for too few possibilites or you have allowed for too many possibilites.

We should be able to agree that lexically-scoped variables are more efficient than logic variables sitting in a substitution, since lexical variables are looked up in constant time, whereas logic variables require at least linear time. Furthermore, whenever we can shrink the substitution without processing the substitution we gain in efficiency.

You may use anything in either chapter or the appendix, including var? and walk, for example. Write a syntax-rules macro that implements a new "smarter" fresh.

You may be surprised by how much you can do with 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 fresh and/or == to require additional information. Thus, the user who wants to gain the efficiency from this feature may have to include more information.

If you do not have a copy of the book, let me know.

You may not have a solution by the time the assignment is due. That is okay for this problem. If you don't have a working solution, be prepared to show the class how far your thinking has progressed.