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!

Pair Programming

The point of pair programming is not to (necessarily) finish the lab faster by divide and conquer. For example in this week’s lab, you should not have one person dedicated to depth-limiting the expression generation and the other person working on generating expressions with an arbitrary number of arguments. Instead you should actively work together on the same task at the same time, each person taking a slight different role (e.g., driver/navigator). However, there might be times where you are working asynchronously and your sub-tasks might diverge. But by submission, all teams members must have a full understanding of the entire project, as if each member wrote the entire thing alone.


Decide on the initial driver (types) and the navigator (guide); if you have three members, one of the two navigators can take notes and document choices and TODO items. Importantly: rotate roles (perhaps every 25 minutes). You can read more about the ‘driver/navigator’ style of pair programming in the essay by Böckeler & Siessegger, an important point they raise:

  • “Apply the ‘5 seconds rule’: When the navigator sees the driver do something "wrong" and wants to comment, wait at least 5 seconds before you say something - the driver might already have it in mind, then you are needlessly interrupting their flow. As Navigator, don't immediately point out any error or upcoming obstacle: Wait a bit for the driver to correct or write a sticky note to remember later. If you intervene immediately, this can be disruptive to the driver's thinking process.”


Double & Halve

  1. Write a scheme procedure: double that doubles its input without using the * operator; 
  • halve should undo it.

(define (halve x)
  (bitwise-arithmetic-shift-right x 1))

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

Are you satisfied your double behaves correctly?


The following scheme procedure implements a×ba \times b without using the * operator:

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

  1. There is probably better ways to multiply; do you remember one from the Data Structures course? We did something similar to the approach described in SICP 1.3 using recursion in Java. Translate it to Scheme without using * or /.

public static int fastMult(int a, int b) {
    if (b == 0)     return 0;
    if (b % 2 == 0) return fastMult(a+a, b/2);
    return fastMult(a+a, b/2) + a;

Write some tests to make sure your new fast-mult works correctly.  

(= (fast-mult 2 6) (mult 2 6) (* 2 6) )

This should evaluate to #t

BONUS: Make fastMult work for all integers including negative numbers.