[plt-scheme] Re: problem with amb macros

Hi,

thanks for your quick answer! The code is the following - the Dorai
Sitaram book macro and the code form SICP:

(require (lib "defmacro.ss"))

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()

        (error "amb tree exhausted")))))

(initialize-amb-fail)

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! amb-fail +prev-amb-fail)
                           (+fk 'fail)))
                       (+sk ,alt))))
                 alts...)

          (+prev-amb-fail))))))

(define (req condition)
  (if (not condition)
      (amb)))


(define nouns '(noun student professor cat class drawer))
(define verbs '(verb studies lectures eats sleeps))
(define articles '(article the a))
(define prepositions '(prep for to in by with))

 (define parse-sentence
   (lambda ()
     (list 'sentence (parse-noun-phrase) (parse-verb-phrase))))

 (define parse-simple-noun-phrase
   (lambda ()
     (list 'simple-noun-phrase (parse-word articles) (parse-word
nouns))))

 (define parse-noun-phrase
   (lambda ()
     (letrec ((maybe-extend
               (lambda (noun-phrase)
                 (amb
                  noun-phrase
                  (maybe-extend (list 'noun-phrase noun-phrase (parse-
prepositional-phrase)))))))
       (maybe-extend (parse-simple-noun-phrase)))))

 (define parse-word
   (lambda (word-list)
     (req (not (null? *unparsed*)))
     (req (memq (car *unparsed*) (cdr word-list)))
     (let ((found-word (car *unparsed*)))
       (set! *unparsed* (cdr *unparsed*))
       (list (car word-list) found-word))))

 (define *unparsed* '())

 (define parse
   (lambda (input)
     (set! *unparsed* input)
     (let ((sent (parse-sentence)))
       (req (null? *unparsed*))
       sent)))


(define parse-prepositional-phrase
  (lambda ()
    (list 'prep-phrase (parse-word prepositions) (parse-noun-
phrase))))

(define parse-verb-phrase
  (lambda ()
    (letrec ((maybe-extend
              (lambda (verb-phrase)
                (amb
                 verb-phrase
                 (maybe-extend (list 'verb-phrase verb-phrase (parse-
prepositional-phrase)))))))
      (maybe-extend (parse-word verbs)))))





The following two sentences should be possible to parse in 2 resp. 5
ways:

(parse '(the professor lectures to the student with the cat))

(parse '(the professor lectures to the student in the class with the
cat))


However, in both cases, when I do (amb) immediately afterwards I get
"amb tree exhausted".



Same thing with puzzle 4.43, where in the version with the commented
line I should get alternatives from (amb):

; exercise 4.43
(interpret
  '(define (yachts)
    (let ((gabrielle (amb 'moore 'downing 'hall 'barnacle 'parker))
          (lorna (amb 'moore 'downing 'hall 'barnacle 'parker))
          (rosalind (amb 'moore 'downing 'hall 'barnacle 'parker))
          (melissa 'barnacle)
          (maryann 'moore 'downing 'hall 'barnacle 'parker))
      (require (not (eq? gabrielle 'barnacle)))
      (require (not (eq? lorna 'moore)))
      (require (not (eq? rosalind 'hall)))
      (require (eq? melissa 'barnacle))
     ;(require (eq? maryann 'moore))
      (require
        (cond ((eq? gabrielle 'moore) (eq? lorna 'parker))
              ((eq? gabrielle 'downing) (eq? melissa 'parker))
              ((eq? gabrielle 'hall) (eq? rosalind 'parker))
              (else false)))
      (require
        (distinct? (list gabrielle lorna rosalind melissa maryann)))
      (list (list 'gabrielle gabrielle)
            (list 'lorna lorna)
            (list 'rosalind rosalind)
            (list 'melissa melissa)
            (list 'maryann maryann)))))

(amb)

Best greetings,
Sigrid





On Dec 14, 7:11 pm, Jens Axel Soegaard <jensa... at soegaard.net> wrote:
> Hi Sigrid,
>
>
>
> > please excuse my question as it's not about PLT-scheme specific  - I'm a
> > complete autodidact studying on my own, trying to solve the SICP
> > exercises, and I think this group is very helpful and instructive :-)
>
> > I want to solve the amb exercises in SICP not always using the custom
> > amb evaluator from the book, but one of the existing macros (as an
> > exercise to employ these macros "in the real world").
> > However, with both the amb macro from the Dorai Sitaram book and one
> > taken fromhttp://community.schemewiki.org/?amb, I do not get the
> > expected behavior when I call (amb) again to get the residual alternatives.
> > E.g. in exercise 4.45, there should be 5 alternatives, but I get "amb
> > tree exhausted" already when I call (amb) after the first try.
>
> > In general it seems the failure continuations are stored correctly in
> > the macros - simple cases like
>
> > 1) (amb 1 2) -> 1
> > 2) (amb) -> 2
>
> > work as expected, but for the more complicated cases as the
> > language-parsing or the puzzles (e.g., exercise 4.43 in the
> > "more-than-one-solution" version) it seems that the macros are not
> > really equivalent of the SICP amb evaluator... Is this possible?
>
> Without actually testing the macro, I'd say the intention
> of the implementation ofhttp://community.schemewiki.org/?amb
> is that you can use with SICP. However, it might be that
> solutions are generated in a different order than shown in
> SICP.
>
> Do you have a concrete example, that shows where you get
> results that differ from your expectation? Can you
> perhaps show us what your code for 4.45 looks like?
>
> --
> Jens Axel Søgaard
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme