# Discussion 12: Programs as Data disc12.pdf

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything.

# Scheme Programs as Data

All Scheme programs are made up of expressions. There are two types of expressions: primitive expressions and combinations.

• Primitive expression examples: `#f`, `1.7`, `+`
• Combinations examples: `(fact 10)`, `(/ 8 3)`, `(not #f)`

Scheme's built-in list data structure can be used to represent combinations.

• Example: `(list 'fact 10)` results in the combination `(fact 10)`.

## Quasiquotation

The normal quote `'` and the quasiquote ``` are both valid ways to quote an expression. However, the quasiquoted expression can be unquoted with the "unquote" `,` (represented by a comma). When a term in a quasiquoted expression is unquoted, the unquoted term is evaluated.

``````scm> (define a 5)
a
scm> (define b 3)
b
scm> `(* a b)
(* a b)
scm> `(* a ,b)
(* a 3)
scm> '(* a ,b)
(* a (unquote b))``````

### Q1: WWSD? Quasiquotation

``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 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)``

## Eval Procedure

The `eval` procedure forces evaluation of a given expression in the current environment. Since a quote supresses evaluation, calling `eval` on a quoted expression `(quote expr)` will evaluate the expression `expr`.

``````scm> (define a '(1 2 3))
a
scm> (quote a) ; equivalently, 'a
a
scm> (eval 'a)
(1 2 3)``````

## Apply Procedure

When evaluating an expression, once the `operator` and `operands` have been fully evaluated, the operator is `apply`'d using the operands as arguments. This can also be done outside of the implicit context of evaluations using the `apply` procedure. The `apply` procedure applies a given `operator` to a list of `operands`.

``````scm> (apply + '(2 3))
5
scm> (apply (lambda (x) (* 2 x)) (list 1))
2``````

### Q2: WWSD? Eval and Apply

``scm> (define add-numbers '(+ 1 2))``
``scm> add-numbers``
``scm> (eval add-numbers)``
``scm> (apply + '(1 2)) ; Is this similar to the previous eval call?``
``scm> (define expr '(lambda (a b) (+ a b)))``
``scm> expr``
``scm> (define adder-func (eval expr))``
``scm> (apply adder-func '(1 2))``
``scm> (define make-list (cons 'list '(1 2 3)))``
``scm> make-list``
``scm> (eval make-list)``
``scm> (apply list '(1 2 3)) ; Is this similar to the previous eval call?``

### Q3: Geometric Sequence

Implement the procedure `geom`, which takes in a nonnegative integer `n` and a factor `f` that is an integer greater than 0. The procedure should create a program as a list that, when passed into the `eval` procedure, evaluates to the `n`th number of the geometric sequence that starts at 1 and has a factor of `f`. The sequence is zero-indexed.

For example, the geometric sequence starting at 2 is 1, 2, 4, 8, and so on. The expression `(geom 5 2)` returns a program as a list. When `eval` is called on that returned list, it should evaluate to the 5th number of the geometric sequence that has a factor of 2 (and starts at 1), which is 32.

Run in 61A Code

### Q4: Make Or

Implement `make-or`, which returns, as a list, a program that takes in two expressions and `or`'s them together (applying short-circuiting rules). However, do this without using the `or` special form. You may also assume the name `v1` doesn't appear anywhere outside this function. For a quick reminder on the short-circuiting rules for `or` take a look at slide 18 of Lecture 3 on Control.

The behavior of the `or` procedure is specified by the following doctests:

``````scm> (define or-program (make-or '(print 'bork) '(/ 1 0)))
or-program
scm> (eval or-program)
bork
scm> (eval (make-or '(= 1 0) '(+ 1 2)))
3``````
Run in 61A Code

### Q5: Make "Make Or"

The above code generates a program that evaluates an `or` expression without using any `or` statements. However, we can take it even one step further: let's create a program which generates `make-or`, the program you created which generates an `or` expression.

Implement `make-make-or`, a program which generates a program which, when `eval`'d, can be `apply`'d to make an `or` expression with differing varibles. You may find the code you wrote above to be useful.

Hint: recall that you want to construct a list that resembles the program. Do you know what this list would look like?

Run in 61A Code

Now, given this function, determine the outputs from the following expressions:

``scm> (make-make-or)``
``scm> (eval (make-make-or))``
``scm> (eval (eval (make-make-or)))``
``scm> (apply (eval (eval (make-make-or))) '(#t (/ 1 0)))``
``scm> (eval (apply (eval (eval (make-make-or))) '(#t (/ 1 0))))``