Name: Barak A. Pearlmutter

CIRT user-id: barak

CIRT user-id: barak

I want American computers in space. Don't want Russian computers. Russian computers are like Russian booster rockets ... biggest in world.-Georgy Grechko, former Soviet cosmonaut

- What value is printed when you type each of the following to
Scheme? (2 points each)
expression result (define (foo x) (if (= x 0) + *)) ((foo 2) 3 4)

`12`(and 'a 'b 'c)

`c`(or 'a 'b 'c)

`a`(if 'a 'b 'c)

`b`(define a '(1 2 3)) `(a ,a b ,@a c (,a) (d ,@a a))

`(a (1 2 3) b 1 2 3 c ((1 2 3)) (d 1 2 3 a))` - Write a
*tail-recursive*definition of`add-nums`, a function that takes a single argument, a list, a returns the sum of all the elements in the list that were numbers. The sum should not include numbers nested within sublists. Hint: use a helper function of two arguments (6 points for being tail recursive, 4 for being correct)Examples:

(add-nums '()) ; 0 (add-nums '(a 1 b 2 c 3 d e)) ; 6 (add-nums '((1) 2 (a 45 b) c 3)) ; 5

(define (add-nums lis) (add-nums-aux lis 0)) (define (add-nums-aux lis subtotal) (if (null? lis) subtotal (add-nums-aux (cdr lis) (+ subtotal (if (number? (car lis)) (car lis) 0)))))

- Rewrite the following pseudocode in Scheme, using procedure
calls in place of goto and assignment. (10 points)
foo(i,j) { L1: if (i < j) { j = j-i; goto L1; } else if (j < i) { i = i-j; goto L1; } else return i; }

(define (foo i j) (cond ((< i j) (foo i (- j i))) ((< j i) (foo (- i j) j)) (else i)))

- Convert each expression into an equivalent backquote form. (2
points each)
expression equivalent using backquote (list 'this 'is 'example n 'of m)

`(this is example ,n of ,m)

(append s1 '(followed by) s2)

``(,@s1 followed by ,@s2)`(cons 'foo (append s '(more)))

``(foo ,@s more)`(list 'joe (list 'the x) 'saw (car y))

``(joe (the ,x) saw ,(car y))`(cons 'a (car y))

``(a ,@y)`or``(a . ,y)`(append (list (+ a 3) (+ a 4)) '(and more))

``(,(+ a 3) ,(+ a 4) and more)` *Extra credit:*Given these definitions(define (c-car x c) (c (car x))) (define (c-cdr x c) (c (cdr x))) (define (c-cons x lis c) (c (cons x lis))) (define (c-null? x c1 c2) (if (null? x) (c1) (c2))) (define (foo a b c) (c-null? a (lambda () (c b)) (lambda () (c-car a (lambda (caa) (c-cdr a (lambda (cda) (foo cda b (lambda (fcdab) (c-cons caa fcdab c))))))))))

What does`(foo '(x y z) '(p d q) (lambda (x) x))`return? (3 points + Scheme self actualization)

(x y z p d q)

Explanation: the c- functions take an extra argument, a procedure, which they call with the result of the non-c- version.Similarly,

`c-null?`calls either it's second or it's third argument, depending on whether its first argument is the empty list.Since these procedures are here made with lambda, we can untangle things by rewriting them with

`if`and`let`as follows, and also using a new version of`foo`that returns its result rather than calling its third argument upon it(define (foo a b) (if (null? a) b (let ((caa (car a))) (let ((cda (cdr a))) (let ((fcdab (foo cda b))) (cons caa fcdab))))))

Now we can substitute in variables' values where they occur,(define (foo a b) (if (null? a) b (cons (car a) (foo (cdr a) b))))

which is our old friend`append`.The original version, in which all functions take an extra argument which they call tail-recursively upon their result, is called

*continuation passing style*or*CPS*. It is simple to mechanically translate programs into CPS, which make the order of evaluation very explicit, and contains names for intermediate values that were anonymous in the original code. These and other properties make it particularly suitable for compilers, and many compilers convert represent the program in CPS form as in intermediate stage of compilation.