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.
Driver/Navigator
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.”
Warm-Up
Double & Halve
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))
(halve16) --> 8
(double2) --> 4
(double3) --> 6
(double4) --> 8
(double (double4)) --> 16
(halve (double5)) --> 5
Are you satisfied your double behaves correctly?
Multiplication
The following scheme procedure implements a×b without using the * operator:
(define (mult a b)
(if (= b 0)
0
(+ a (mult a (- b 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 /.
publicstaticintfastMult(int a, int b){
if (b == 0) return0;
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.
Pair Programming
Driver/Navigator
Warm-Up
Double & Halve
(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)) --> 5Multiplication
(define (mult a b) (if (= b 0) 0 (+ a (mult a (- b 1)))))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;}(= (fast-mult 2 6) (mult 2 6) (* 2 6) )