[Gardeners] Lisp for imperative algorithms

[Peter Seibel]

On Jun 26, 2006, at 4:57 PM, Matthew Swank wrote:

> Peter Seibel wrote:
>
>> Well, I find that Common Lisp is an excellent language for dealing
>> with pseudo-code because it provides many different control
>> constructs. For an example look at the section "Local Flow of
>> Control" from chapter 20 of Practical Common Lisp[1] where I show how
>> you can create a very literal translation of some very low-level
>> pseudo code from Knuth's _Art of Programming_ and then transform it
>> into "regular" Lisp code. The nice thing is that the first version,
>> which is a quite literal translation of Knuth's code, is something
>> you can actually run and test. Then you can refactor bit by bit and
>> know that you've always got a working version.
>>
>> -Peter
>>
>> [1] <http://www.gigamonkeys.com/book/the-special-operators.html>
>>
>>
>>
> Well, while tagbody is as beautiful as any goto, it isn't essential.
> Any language with decent local function definition abilities will do:
>
> Peter's example from PCL:
>
> (defun algorithm-s (n max) ; max is N in Knuth's algorithm
>   (let (seen               ; t in Knuth's algorithm
>         selected           ; m in Knuth's algorithm
>         u                  ; U in Knuth's algorithm
>         (records ()))      ; the list where we save the records  
> selected
>     (tagbody
>      s1
>        (setf seen 0)
>        (setf selected 0)
>      s2
>        (setf u (random 1.0))
>      s3
>        (when (>= (* (- max seen) u) (- n selected)) (go s5))
>      s4
>        (push seen records)
>        (incf selected)
>        (incf seen)
>        (if (< selected n)
>            (go s2)
>            (return-from algorithm-s (nreverse records)))
>      s5
>        (incf seen)
>        (go s2))))
>
> Peter's example using thunks instead of labels:

Hadn't you better use LABELS instead of FLET since these have to be  
able to call each other? Anyway, my point is that Common Lisp  
provides constructs that map almost *exactly* to the notions used in  
Knuth's pseudo code: there's no mental translation required to see  
that LABELS are essentially equivalent to TAGBODY/GO--you just  
transcribe Knuth's algorithm and then start refactoring. (And along  
the way you can translate to helper functions using LABELS or FLET or  
whatever).

-Peter

-- 
Peter Seibel           * peter at gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp  * http://www.gigamonkeys.com/book/