Loading...

​​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 \times b$​:

​​

​​ (define (mult a b)

​​  (if (= b 0)

​​      0

​​      (+ a (mult a (- b 1)))))

​​

​​Trace the program for computing ​​$2\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\times6$​ turns to ​​$6 \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: