[plt-scheme] Implementing Rabin-Miller

On Oct 15, John Clements wrote:
> 
> On Tuesday, October 15, 2002, at 04:09  PM, Paulo Jorge O. C. Matos 
> wrote:
> 
> > (1)  Choose a random number, a, such that a is less than p.
> > (2)  Set j = 0 and set z = am mod p.
> > (3)  If z = 1, or if z = p - 1, then p passes the test and may be 
> > prime. (4)  If j > 0 and z = 1, then p is not prime.
> > (5)  Set j = j + 1. If j < b and z ? p - 1, set z = z2 mod p and go 
> > back to step (4). If z = p - 1, then p passes the test and may be 
> > prime.
> > (6)  If j = b and z ? p - 1, then p is not prime.
> >
> 
> This looks like a terrible specification of an algorithm. Rewrite it
> like this:
> [...]
> Due to a dreadful spec, I may be off in the boundary condition for
> j.  Frankly, it might be easier to read in scheme:

I disagree with that "might" in the last sentence -- I think that it
is very definitely easier.  This is the same story over and over
again: I keep finding people who didn't learn to be proper programmers
and then describe algorithms using some semi-imperative, mostly vague
descriptions.  This is just like so many situations where a simple
algorithm is turned inside-out, statements shuffled around, just so
the whole thing can be implemented with "dynamic programming" -- when
the original plain algorithm is so much clearer with a simple
memoization slapped on.  I see this continuously in my wife's work:
she just has to describe the simple *memoized* algorithm using
*dynamic programming*, the latter gets the "Oooh!" effect while the
former is mostly unknown at best (usually disregarded as a typo).
There are also the theory guys -- people who will teach you the
insides of the concepts of computations using Turing Machines -- all
with diagrams that get more and more exotic with little arrows for
"yes" and "no" results, and crappy descriptions of connecting N
machines in parallel with "and" and "or" switches.  When they get
someone who shows them that the whole thing can be explained much
better (in almost every metric -- short, precise, simple), then they
might get impressed for a microsecond but eventually file the incident
under a "software engineering issue".

For the sake of being on-topic, just so it doesn't look like good
programmers try to avoid gotos: it is possible.  For example, the
piece of syntax below makes this work --

  > (let ((x #f))
      (with-gotos
        (set! x 0)
        (goto start:)
        (set! x 99)
        start:
          (goto (if (even? x) even: odd:))
        even:
          (printf "even: ")
        odd:
          (printf ">>> ~s\n" x)
          (set! x (add1 x))
          (when (> x 10) (goto end:))
          (goto start:)
        end:))
  even: >>> 0
  >>> 1
  even: >>> 2
  >>> 3
  even: >>> 4
  >>> 5
  even: >>> 6
  >>> 7
  even: >>> 8
  >>> 9
  even: >>> 10
  #f

The code looks complex but it's quite simple.  The only value I
personally see in it is to study how it manages the labels and gotos.
Otherwise, it is a bad idea.  Anyway, here it is:

(define-syntax (with-gotos stx)
  (syntax-case stx ()
    ((_ body ...)
     (let loop ((code (syntax->list #'(body ...))) (blocks '()) (current #f))
       (cond
        ((null? code)
         (let* ((goto (datum->syntax-object stx 'goto stx))
                (blocks
                 (let loop ((bs   (if current (cons current blocks) blocks))
                            (next #f)
                            (r    '()))
                   (if (null? bs)
                     r
                     (let ((b (reverse
                               (if next
                                 (cons #`(#,goto #,next) (car bs)) (car bs)))))
                       (loop (cdr bs) (car b)
                             (cons (if (null? (cdr b)) (list (car b) #'#f) b)
                                   r)))))))
           #`((let/cc #,goto
                (letrec #,(map (lambda (block)
                                 #`(#,(car block) (lambda () #,@(cdr block))))
                               blocks)
                  #,(caar blocks))))))
        ((identifier? (car code))
         (loop (cdr code)
               (if current (cons current blocks))
               (list (car code))))
        (else
         (loop (cdr code)
               blocks
               (if current
                 (cons (car code) current)
                 (list (car code) (car (generate-temporaries
                                        '(label))))))))))))

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!