Problem 1

Rewrite the definition of foo below to replace the let* with nested let's following the process outlined in the lecture notes.

> (define (foo L) (let* ((P (car L)) (x (car P)) (y (cadr P))) (+ x y)))
> (foo '((3 5)))
8

Problem 2

It turns out that even lists are syntactic sugar! In the below, we define the function kons that pairs together two values by producing a function that returns the first value if the argument is #t and the second value otherwise. We package these up nicely as functions kar and kdr that behave like the car and cdr. We also define the empty list as knull. We could define this any old way we want, but I like defining it as I have because the kar or kdr of knull is knull (as opposed to an error), which is an interesting feature.

(define kons (lambda (x y) (lambda (w) (if w x y))))
(define kar (lambda (L) (L #t)))
(define kdr (lambda (L) (L #f)))
(define knull (letrec ((F (lambda (x) F))) F))

Here are a few examples:

> (define L (kons 3 (kons 7 (kons 1 knull))))
> (kar L)
3
> (kar (kdr L))
7
> (equal? (kdr (kdr L)) knull)
#f
> (equal? (kdr (kdr (kdr L))) knull)
#t

Write a function kadd that takes a list in the above format and returns the sum of the values in the list.

> (kadd (kons 3 (kons 7 (kons 1 knull))))
11
> (kadd knull)
0

Problem 3

Write a function (diet-scheme P) that takes a list representing a scheme expression and returns a list representing an equivalent expression that contains no let of any kind. Note: assume that P contains no let* or letrec, and that any regular let in P consist of only a single name/value pair.

> (define prog1 '(let ((x (sqrt 3.14159))) (+ x (/ 1 x))))
> (diet-scheme prog1)
'((lambda (x) (+ x (/ 1 x))) (sqrt 3.14159))
> (define prog2 '(let ((x (sqrt 3.14159))) (let ((y (/ 2.7128 x))) (expt (+ x y) 3))))
> (diet-scheme prog2)
'((lambda (x) ((lambda (y) (expt (+ x y) 3)) (/ 2.7128 x))) (sqrt 3.14159))
> (eval (diet-scheme prog1)) ; Make sure racket has scheme languge set to "swindle"
2.336642924164682
> (eval (diet-scheme prog2)) ; Make sure racket has scheme languge set to "swindle"
36.0346818606035
      

Note: First of all, realize that your code can use all the let, let* and letrec expressions you want. It's the output of your code that won't have them. Second, don't be freaked out that parameter P is scheme code. In the end, it's just a list, and you know how to compute with lists. So if, for example, I wanted to change every addition to a multiplication in a scheme program I could do the following:

> (define (add-to-mul P)
      (if (list? P)
          (map add-to-mul P)      ; recursively replace +'s in the elements of list P
          (if (equal? P '+) '* P) ; P is not a list.  If it's + make it *, otherwise leave it unchanged
  ))
> (add-to-mul '(map (lambda (x) (+ x x)) (list (- 4 2) (sqrt 25) (+ 5 7))))
'(map (lambda (x) (* x x)) (list (- 4 2) (sqrt 25) (* 5 7)))
> (eval (add-to-mul '(map (lambda (x) (+ x x)) (list (- 4 2) (sqrt 25) (+ 5 7))))) ; Make sure racket has scheme languge set to "swindle"
(4 25 1225)
      

Submit

Submit via the submit script (submit-external -c=SI413 -p=hw05 hw05.scm).