Here are the definitions of the S and K combinators:
S = (lambda (x) K = (lambda (x)
(lambda (y) (lambda (y) x))
(lambda (z) ((x z) (y z)))))
Show algebraically that ((S K) K) is equivalent to the identity function.
Study the abstract functional representation of numbers and booleans that we developed in class. Write functions called bool->rep and rep->bool to convert between the Scheme values #t and #f and the functional values for true and false. Then write the functions logical-not, logical-and, and logical-or. Logical-and and logical-or should take two thunks (zero-argument functions) as arguments, which get evaluated in order, and only when necessary. Hint: use test. Examples:
(rep->bool true) => #t (bool->rep #f) => #<procedure> (rep->bool (logical-not true)) => #f (rep->bool (logical-and (lambda () true) (lambda () false))) => #f (define infinite-loop (lambda () (infinite-loop))) (rep->bool (logical-or (lambda () true) (lambda () (infinite-loop)))) => #t
Here is the definition of Y we derived in class:
(define Y
(lambda (g)
((lambda (f) (g (lambda (a) ((f f) a))))
(lambda (f) (g (lambda (a) ((f f) a)))))))
Read through the derivation to refresh your memory. To create a recursive function such as factorial using Y, we first create a "template" function temp that uses a bound variable r in place of the recursive call, and then we pass temp to Y:
(define temp
(lambda (r)
(lambda (n)
(if (= n 0)
1
(* n (r (- n 1)))))))
(define fact (Y temp))
(fact 5) => 120
Using Y, redefine the snoc function so that it does not depend on the name "snoc". Hint: Y only works for functions of one argument, so you'll need to curry snoc.
(define snoc
(lambda (x lst)
(if (null? lst)
(list x)
(cons (car lst) (snoc x (cdr lst))))))
Y seems awfully complicated. If we don't mind writing "(r r)" in place of "r" for each recursive call in the body of our template function, we can create factorial using the following less-complicated combinator (why not call it Y-not):
(define Y-not
(lambda (f) (lambda (a) ((f f) a))))
(define temp2
(lambda (r)
(lambda (n)
(if (= n 0)
1
(* n ((r r) (- n 1)))))))
(define fact2 (Y-not temp2))
(fact2 5) => 120
This seems to work fine. So why not use Y-not for recursion instead of Y? What is the fundamental difference between them? Create a test case in Scheme that clearly demonstrates this difference.
(Re-)read pages 39-51 of the textbook, and review the define-datatype example from class.
Do Exercise 2.7 on page 52: Rewrite your lexical-address program so that it processes abstract syntax instead of concrete syntax. That is, create a datatype called expression using define-datatype, and have your program recurse over the abstract syntax tree generated by your parsing function. The final value returned by lexical-address may then be generated by converting the result back into concrete syntax. Here are some test expressions. Call your parsing and unparsing functions concrete->abstract and abstract->concrete, respectively. For example, the top-level lexical-address function would look like this:
(define lexical-address
(lambda (datum)
(abstract->concrete (lex (concrete->abstract datum) '()))))
You should add two new variants to your datatype, representing the translation of a given bound or free variable reference:
(lex-info (id symbol?) (depth number?) (position number?)) (free-info (id symbol?))
Write abstract functional versions of ackermann and count-digits.
Put all of your function definitions into a single Scheme file called assign4.ss and be sure to include your name in a comment at the top of the file. Submit this file electronically by running the /common/cs/submit/cs131-submit script from any Pomona Linux machine.
For questions 1 and 4, either write out your answers on paper and turn this in during class, or else put your answers in a plain text file called README and submit this file using cs131-submit.
If you have questions about anything, don't hesitate to ask!