[plt-scheme] Bridging the gap

From: Gary Baumgartner (gfb at cs.toronto.edu)
Date: Wed Mar 18 10:46:10 EDT 2009

I've been trying to get the potential of an expressive programming language
 across to some colleagues and many students, for almost a decade. PLT Scheme
 has been very helpful, but there's an example that finally resonated with three
 different lecturers, in only a few minutes each one afternoon, and later with
 students (individually for now, on sabbatical). So maybe some of you will
 find it similarly useful.

It starts with a very short implementation of a choice operator implementation,
 called -< to look like branching (people comment that they like that),
 and ? to ask for another result.

  (define (?) (error "No."))
  (syntax-rules ()
    ((-<) (?))
    ((-< <e0> . <es>)
     (let ((old-fail ?))
       (let/cc resatisfy
         (set! ? (lambda () (set! ? old-fail) (resatisfy (-< . <es>))))

I tell the person to ignore the implementation, the point is the use:

> (+ (-< 1 2) (-< 30 40)) ; add 1 or 2 to 30 or 40
> (?)

Then something like (let ((x (-< 1 2))) (+ x (-< 30 40))) is worthwhile,
 since they often react in a way suggesting they haven't imagined what it
 really means to have -< available anywhere an expression is allowed.

But the compelling part is not the logic programming (for various reasons).
Instead, what happened was a friend learning to program wrote:

(define (prime-factorization n)
  (let divisor-list ((operand n) (divisor 2))
    (cond ((= operand 1) '())
          ((= (remainder operand divisor) 0)
           (cons divisor (divisor-list (/ operand divisor) divisor)))
          (else (divisor-list operand (+ divisor 1))))))

And tried large numbers:

> (prime-factorization 1234567890)
(2 3 3 5 3607 3803)
> (prime-factorization 1234567890123) ; we wait a bit!

I had shown him the use of -< and ?, so we discussed iterators / generators,
 implementable here by replacing '() and cons. So we did just that, prepending:

  (define-syntax cons  (syntax-rules () ((cons <e> <l>) (-< <e> <l>))))
  (define-syntax quote (syntax-rules () ((quote ())     (?))))


> (prime-factorization 1234567890123)
> (?)

He found this unsurprising, unlike more experienced programmers, who so far
 find it compelling. My friend definitely understood what it accomplished,
 e.g. he knew why (define cons -<) wouldn't work. He's a smart friend, so I
 had the luxury of teaching by starting with code is a forest, written in
 linear textual representation, procedure call is pre-order, etc. He can
 draw the parse tree of new code and trace it, though he's written only two
 procedures (the above, and before that is-prime?).

This was all in one file in an open DrScheme on a suspended laptop when I got
 back to the university, and I just started showing it to people I ran into,
 and it clicked. There were many hooks. Some people liked it for "code is data",
 some liked the "industry best practices" of not touching working code. Some
 liked that a program that programmers execute to rewrite to a particular
 "design pattern"  was now program code. And our students, trained from first
 year in the skill of implementing iterators, can understand what the
 example accomplishes and that it's something they hadn't even thought of
 as potentially expressible in code,

Posted on the users mailing list.