Lab 12: Programs as Data

Due by 11:59pm on Wednesday, November 15.

Starter Files

Download Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your email.

YouTube link


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.

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)
scm> (define b 3)
scm> `(* a b)
(* a b)
scm> `(* a ,b)
(* a 3)
scm> `(* ,(+ a b) b)
(* 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.

Recall that all Scheme programs are made up of expressions. There are two types of expressions: primitive (a.k.a atomic) expressions and combinations.

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

Scheme stores any non-primitive expression as a Scheme list! This means we can represent our programs as data by using Scheme lists.

For example, evaluating (list '+ 2 2) results in the list (+ 2 2). If we then call eval on this list, it will be evaluated as a combination expression, which will return 4! The eval procedure takes in one argument expr and evaluates expr in the current environment.

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

Additionally, quasiquotation is very helpful for building procedures that create expressions. Take a look at the following add-program:

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

add-program takes in two inputs x and y and returns an expression that, if evaluated, evaluates to the result of adding x and y together. Within add-program, we use a quasiquote to build the addition expression (+ ...), and we unquote x and y to get their evaluated values in the addition expression.

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 want to return if predicate evaluates to true (#t)
  3. if-false : a quoted expression which will evaluate to the value we want to 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>). Evaluating this expression returns the result of our if expression.

Here are some doctests to show this:

scm> (if-program '(= 0 0) '2 '3)
(if (= 0 0) 2 3)
scm> (eval (if-program '(= 0 0) '2 '3))
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)))

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

Use Ok to test your code:

python3 ok -q if-program

Q3: Exponential Powers

Implement the procedure pow-expr, which takes in a base n and a nonnegative integer p. The procedure should create a program as a list that, when passed into the eval procedure, evaluates the value n^p, or n to the pth power.

For example, the expression (pow-expr 2 5) returns a program as a list. When eval is called on that returned list, it should evaluate to 2^5, which is 32. We'll do this by building nested multiplication expressions!

scm> (define expr (pow-expr 5 1))
scm> expr
(* 1 5)
scm> (eval expr)

scm> (define expr2 (pow-expr 5 2))
scm> expr2
(* (* 1 5) 5)
scm> (eval expr2)

Hint: Note that the expression returned by (pow-expr 5 2) is just the expression returned by (pow-expr 5 1) nested in another multiplication expression. There is an inherent recursive structure here, so what programming paradigm do you think we should use?

(define (pow-expr n p)

Use Ok to test your code:

python3 ok -q pow

Q4: Swap

Implement swap, a procedure which takes a call expression expr and returns the same expression with its first two operands swapped if the evaluated value of the second operand is greater than the evaluated value of the first operand. Otherwise, it should just return the original expression.

For example, (swap '(- 1 (+ 3 5) 7)) should return the expression (- (+ 3 5) 1 7) since 1 evaluates to 1, (+ 3 5) evaluates to 8, and 8 > 1. Any operands after the first two should not be evaluated during the execution of the procedure, and they should be left unchanged in the final expression. You may assume that every operand evaluates to a number and that there are always at least two operands in expr.

Hint: Quasiquotation might not be the best way to approach this problem (look at the bindings in the let expression to see why this might be the case). What other methods of building lists could we use to solve this problem?

Reminder: Don't forget to evaluate the first two operands when comparing them!

(define (cddr s)
  (cdr (cdr s))

(define (cadr s)
  (car (cdr s))

(define (caddr s)
  (car (cddr s))

(define (swap expr)
    (let ((op (car expr))
        (first (car (cdr expr)))
        (second (caddr expr))
        (rest (cdr (cddr expr))))
Use Ok to test your code:

python3 ok -q swap