Lab 0: Generating Expressions
Bard College – Computer Science – Design of Programming Languages

In our first lab we will explore scheme and review programming with recursion. We’ll also write programs to automatically generate test cases for our programs — meta-programming!

Warm-Up 

Double & Halve

Write two scheme procedures: double that doubles its input and halve that halves its input.

(double 2) --> 4
(double 3) --> 6
(double 4) --> 8
(double (double 4)) --> 16
(halve 6) --> 3
(halve (double 5)) --> 5

Does halve always return a whole number? It probably should.

Multiplication

The following scheme procedure implements a×ba \times b:

 (define (mult a b)
  (if (= b 0)
      0
      (+ a (mult a (- b 1)))))

Trace the program for computing 2×62\times6. (Your trace should take b number of steps.)

I bet we could do better.  Write a faster version of mult that runs the procedure with swapped arguments, if the second argument is larger (this is OK because multiplication is commutative). 
2×62\times6 turns to 6×26 \times 2, both evaluate to 12.

(= (mult 2 6) (mult 6 2) (* 2 6) (* 6 2))

This should be #t.

We should probably write more test cases to make sure our new procedures are working properly.

Generating Expressions

Let’s put our new multiply procedure to use in some scheme arithmetic expressions, but let’s make the computer do the work: we can automatically create random expressions

Consider this grammar:

<expression> --> (<operator> <number> <number>)
<operator>   --> + | * | / | -
<number>     --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

which describes expressions like:

(/ 2 3)
(* 1 1)
(* 5 5)

This scheme code realizes that grammar in code: