Solution Files

Required Questions

Quasiquotation

Consult the drop-down if you need a refresher on quasiquotation. It's okay to skip directly to the questions and refer back here should you get stuck.

scm> (define a 5)
a
scm> (define b 3)
b
scm> `(* a b)  ; Quasiquoted expression
(* a b)
scm> `(* a ,b)  ; Unquoted b, which evaluates to 3
(* a 3)
scm> `(* ,(+ a b) b)  ; Unquoted (+ a b), which evaluates to 8
(* 8 b)

Q1: WWSD: Quasiquote

Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:

python3 ok -q wwsd-quasiquote -u

scm> '(1 x 3)

scm> (define x 2)

scm> `(1 x 3)

scm> `(1 ,x 3)

scm> `(1 x ,3)

scm> `(1 (,x) 3)

scm> `(1 ,(+ x 2) 3)

scm> (define y 3)

scm> `(x ,(* y x) y)

scm> `(1 ,(cons x (list y 4)) 5)

Programs as Data

Consult the drop-down if you need a refresher on Programs as Data. It's okay to skip directly to the questions and refer back here should you get stuck.

scm> (define expr (list '+ 2 2))
expr
scm> expr
(+ 2 2)
scm> (eval expr)
4

scm> (define (add-program x y)
...>     `(+ ,x ,y))
add-program
scm> (add-program 3 6)
(+ 3 6)

Q2: If Program

In Scheme, the if special form allows us to evaluate one of two expressions based on a predicate. Write a program if-program that takes in the following parameters:

1. predicate : a quoted expression which will evaluate to the condition in our if-expression
2. if-true : a quoted expression which will evaluate to the value we return if predicate evaluates to true (#t)
3. if-false : a quoted expression which will evaluate to the value we return if predicate evaluates to false (#f)

The program returns a Scheme list that represents an if expression in the form: (if <predicate> <if-true> <if-false>). Note that we don't want to evaluate the expression (in our program at least).

Here are some doctests to show this:

scm> (define x 1)
scm> (if-program '(= 0 0) '(+ x 1) 'x)
(if (= 0 0) (+ x 1) x)
scm> (eval (if-program '(= 0 0) '(+ x 1) 'x))
2
scm> (if-program '(= 1 0) '(print 3) '(print 5))
(if (= 1 0) (print 3) (print 5))
scm> (eval (if-program '(= 1 0) '(print 3) '(print 5)))
5

(define (if-program condition if-true if-false)
  `(if ,condition ,if-true ,if-false)
)

Use Ok to test your code:

python3 ok -q if-program
Copy
✂️

Q3: Exponential Powers

Implement a procedure (pow-expr base exp) that returns an expression that, when evaluated, raises the number base to the power of the nonnegative integer exp. The body of pow-expr should not perform any multiplication (or exponentiation). Instead, it should just construct an expression containing only the symbols square and * as well as the number base and parentheses. The length of this expression should grow logarithmically with respect to exp, rather than linearly.

Examples:

scm> (pow-expr 2 0)
1
scm> (pow-expr 2 1)
(* 2 1)
scm> (pow-expr 2 5)
(* 2 (square (square (* 2 1))))
scm> (pow-expr 2 15)
(* 2 (square (* 2 (square (* 2 (square (* 2 1)))))))
scm> (pow-expr 2 16)
(square (square (square (square (* 2 1)))))
scm> (eval (pow-expr 2 16))
65536

Hint:

1. x^2y = (x^y)²
2. x^2y+1 = x(x^y)²

For example, 2¹⁶ = (2⁸)² and 2¹⁷ = 2 * (2⁸)².

You may use the built-in predicates even? and odd?. Also, the square procedure is defined for you.

Here's the solution to a similar homework problem.

(define (square n) (* n n))

(define (pow-expr base exp)
    (cond ((= exp 0) 1)
        ((even? exp) `(square ,(pow-expr base (/ exp 2))))
        (else `(* ,base ,(pow-expr base (- exp 1)))))
)

Use Ok to test your code:

python3 ok -q pow
Copy
✂️

Macros

A macro is a code transformation that is created using define-macro and applied using a call expression. A macro call is evaluated by:

1. Binding the formal parameters of the macro to the unevaluated operand expressions of the macro call.
2. Evaluating the body of the macro, which returns an expression.
3. Evaluating the expression returned by the macro in the frame of the original macro call.

scm> (define-macro (twice expr) (list 'begin expr expr))
twice
scm> (twice (+ 2 2))  ; evaluates (begin (+ 2 2) (+ 2 2))
4
scm> (twice (print (+ 2 2)))  ; evaluates (begin (print (+ 2 2)) (print (+ 2 2)))
4
4

Q4: Repeat

Define repeat, a macro that takes a number n and an expression expr. Calling repeat evaluates expr in a local frame n times, and its value is the final result. You will find the helper function repeated-call useful, which takes a number n and a zero-argument procedure f and calls f n number of times.

For example, (repeat (+ 2 3) (print 1)) is equivalent to:

(repeated-call (+ 2 3) (lambda () (print 1)))

and should evaluate (print 1) repeatedly 5 times.

The following expression should print four four times:

(repeat 2 (repeat 2 (print 'four)))

(define-macro (repeat n expr)
  `(repeated-call ,n (lambda () ,expr)))
; Call zero-argument procedure f n times and return the final result.
(define (repeated-call n f)
  (if (= n 1) (f) (begin (f) (repeated-call (- n 1) f))))

Use Ok to test your code:

python3 ok -q repeat-lambda
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

If you are in a regular section of CS 61A, fill out this lab attendance and feedback form. (If you are in the mega section, you don't need to fill out the form.)

Then, submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.