<< Previous exercise (4.49) | Index | Next exercise (4.51) >>


 ;; In (analyze expr) adds 
 ((ramb? expr) (analyze-ramb expr)) 
 ;; add these code to amb evaluator 
 (define (analyze-ramb expr) 
   (analyze-amb (cons 'amb (ramb-choices expr)))) 
 ;; amb expression 
 (define (amb? expr) (tagged-list? expr 'amb)) 
 (define (amb-choices expr) (cdr expr)) 
 (define (ramb? expr) (tagged-list? expr 'ramb)) 
 (define (ramb-choices expr) (shuffle-list (cdr expr))) 
 ;; random-in-place, from CLRS 5.3 
 (define (shuffle-list lst) 
  (define (random-shuffle result rest) 
   (if (null? rest) 
           (let* ((pos (random (length rest))) 
                  (item (list-ref rest pos))) 
            (if (= pos 0) 
                (random-shuffle (append result (list item)) (cdr rest)) 
                (let ((first-item (car rest))) 
                      (random-shuffle (append result (list item)) 
                                      (insert! first-item (- pos 1) (cdr (delete! pos rest))))))))) 
   (random-shuffle '() lst)) 
 ;; insert item to lst in position k. 
 (define (insert! item k lst) 
   (if (or (= k 0) (null? lst)) 
       (append (list item) lst) 
       (cons (car lst) (insert! item (- k 1) (cdr lst))))) 
 (define (delete! k lst) 
   (cond ((null? lst) '()) 
         ((= k 0) (cdr lst)) 
         (else (cons (car lst)  
                     (delete! (- k 1) (cdr lst)))))) 


 ; this procedure gets the random element to the start of the list. The rest 
 ; is the same as in amb. 
 (define (analyze-ramb exp) 
   (define (list-ref-and-delete ref lst)        ; get random item from list. 
     (define (loop count prev-items rest-items) ; and return a list with the 
       (if (= count 0)                          ; random item as its car 
           (cons (car rest-items)               ; and the rest of the list as the cdr 
                 (append prev-items (cdr rest-items))) 
           (loop (- count 1)                    ; this will mangle the list every time 
                 (cons (car rest-items)         ; creating a "random" amb.  
                 (cdr rest-items)))) 
     (if (null? lst) 
         (loop ref '() lst))) 
   (let ((cprocs (map analyze (amb-choices exp)))) 
     (lambda (env succeed fail) 
       (define (try-next choices) 
         (if (null? choices) 
               (let ((randomized (list-ref-and-delete 
                                  (random (length choices)) 
                 ((car randomized) env 
                                   (lambda () 
                                     (try-next (cdr randomized))))))) 
       (try-next cprocs)))) 


This solution is kind of like the above one, but with a clear process.

 ;; version 1 
 (define (analyze-ramb exp) 
   (let ((cprocs (map analyze (amb-choices exp)))) 
     (lambda (env succeed fail) 
       (define (try-next choices) 
         (if (null? choices) 
             (let ((l (length choices))) 
               (let ((c (list-ref choices (random l)))) 
                 (c env 
                    (lambda () 
                      (try-next (remove choices c)))))))) 
       (try-next cprocs)))) 
 (define (remove seq elt) 
   (filter (lambda (x) (not (eq? elt x))) seq)) 
 ;; version 2: won't do extra works during running 
 (define (shuffle seq) 
   (define (iter seq res) 
     (if (null? seq) 
         (let ((index (random (length seq)))) 
           (let ((element (list-ref seq index))) 
             (iter (remove seq element) 
                   (cons element res)))))) 
   (iter seq nil)) 
 (define (ramb-choices exp) (shuffle (cdr exp))) 
 ; analyze-ramb is the same as analyze-amb