[plt-scheme] On continuations...

On Dec 17, 2004, at 3:21 PM, michael rice wrote:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> In trying to firm up my rather dim understanding of
> continuations I've translated a Python function for
> generating the partitions of an integer into a Scheme
> function.
>
> It seems to work properly for several examples but I
> don't have a feeling whether it's a decent translation
> or a terrible hack.
>
> Example at bottom of file. Comments appreciated!
>
>   --mr

Dear heavens!  This may have helped you understand continuations, but I 
wouldn't call it a decent translation.  How about the following:

(define (partitions n)
   (cond [(= n 0) (list empty)]
         [else (apply append
                      (map (lambda (sp)  ; (listof number?) -> (listof 
(listof number?))
                             (cons (cons 1 sp)
                                   (cond
                                     [(null? sp) null]
                                     [(or (null? (cdr sp))
                                               (< (car sp) (cadr sp)))
                                      (list (cons (+ 1 (car sp)) (cdr 
sp)))]
                                     [else null])))
                           (partitions (- n 1))))]))

(equal? (partitions 0) (list empty))
(equal? (partitions 1) (list (list 1)))
(equal? (partitions 2) (list (list 1 1) (list 2)))
(equal? (partitions 3) (list (list 1 1 1)
                              (list 1 2)
                              (list 3)))
(partitions 6)

=>

Welcome to DrScheme, version 209.
Language: Intermediate Student with lambda.
Teachpack: /private/tmp/plt-scheme-init.ss.
true
true
true
true
(list (list 1 1 1 1 1 1) (list 1 1 1 1 2) (list 1 1 2 2) (list 2 2 2) 
(list 1 1 1 3) (list 1 2 3) (list 3 3) (list 1 1 4) (list 2 4) (list 1 
5) (list 6))
 >


This is almost a direct transliteration of the functional core of your 
python program;  rather than banging results into a result box, though, 
it just piles them up in a functional way.  In some ways, this seems to 
me like a powerful indictment of python's 'yield'; that is, reasoning 
about a program that uses 'yield' may be a lot like reasoning about the 
scheme program you wrote.

John Clements



>
> (define (part-gen n eot)
>   (letrec ((return #f)
> 	   (cont (lambda (x)
> 		   (set! cont (lambda (x) (partition n)))
> 		   (cont #f)))
> 	   (partition (lambda (n)
>                         (if (zero? n)
>                             (call/cc (lambda (c) (set!
> cont (lambda (x) (return eot))) (return '())))
>                             (let ((pg (part-gen (- n
> 1) eot)))
>                               (do ((p (pg) (pg)))
>                                 ((equal? p 0) eot)
>                                 (call/cc (lambda (c)
> (set! cont c) (return (append '(1) p))))
>                                 (when (and (not (null?
> p))
>                                            (or (<
> (length p) 2)
>                                                (>
> (second p) (first p))))
>                                   (call/cc (lambda (c)
>                                              (set!
> cont c)
>                                              (return
> (append (list (+ (car p) 1)) (cdr p))))))))))))
>     (lambda () (call-with-current-continuation
> 		(lambda (ret) (set! return ret) (cont #f))))))
>
>
>
> ;Welcome to DrScheme, version 206p1.
> ;Language: Swindle.
> ;> (let ((pg (part-gen 6 0)))
> ;    (do ((p (pg) (pg)))
> ;      ((equal? p 0))
> ;      (display p)
> ;      (newline)))
> ;(1 1 1 1 1 1)
> ;(1 1 1 1 2)
> ;(1 1 2 2)
> ;(2 2 2)
> ;(1 1 1 3)
> ;(1 2 3)
> ;(3 3)
> ;(1 1 4)
> ;(2 4)
> ;(1 5)
> ;(6)
> ;>
>
>
>
> 		
> __________________________________
> Do you Yahoo!?
> Yahoo! Mail - Find what you need with new enhanced search.
> http://info.mail.yahoo.com/mail_250
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2169 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20041217/79b04e07/attachment.p7s>