Hi Andrew,
I don't understand why 'begin' is being used in the definition of
'alt'. I would expect that to mean, only the result of the second
alternative will be returned.
Here is a definition of 'alt' that works for your example.
(define (alt alt1 alt2)
(lambda (continuation pos)
(alt1 (lambda (pos1)
(if (null? pos1)
(alt2 continuation pos)
(continuation pos1)))
pos)))
Orlando.
On Sat, Nov 27, 2010 at 2:35 PM, Andrew Lentvorski <bs...@allcaps.org> wrote:
> I've been trying to work my way through Mark Johnson's "Memoization in Top
> Down Parsing" paper. I've been trying to work through the continuation
> passing style parts, but I just can't seem to figure out what is wrong with
> the alt operator.
>
> I expect (FOOORBAR identity '(foo bar baz)) to return '(bar baz) for
> consistency with the rest of the code, but all I'm getting is an empty list.
>
> What am I missing? Do I have to bottom out in something like a "future"
> rather than identity and only fully-evaluate when I return? Is it as simple
> as I'm missing a "union" in the function (but, I don't necessarily expect
> that a continuation should allow things to come back so that seems like it
> would be useless)?
>
> I suspect that I really need to understand this *well* before I try
> memoizing the continuations for left-recursion evaluation.
>
> Thanks,
> -a
>
> This is the code I used:
>
> (define (identity args)
> args)
>
> (define (terminal word)
> (lambda (continuation pos)
> (if (and (pair? pos) (eq? (car pos) word))
> (continuation (cdr pos))
> (continuation '()))))
>
> (define (seq seq1 seq2)
> (lambda (continuation pos)
> (seq1 (lambda (pos1) (seq2 continuation pos1))
> pos)))
>
> (define (alt alt1 alt2)
> (lambda (continuation pos)
> (begin (alt1 continuation pos)
> (alt2 continuation pos))))
>
> (define FOO (terminal 'foo))
> (define BAR (terminal 'bar))
> (define FOOANDBAR (seq FOO BAR))
> (define FOOORBAR (alt FOO BAR))
>
>> (FOO identity '(foo bar baz))
> '(bar baz)
>> (BAR identity '(foo bar baz))
> '()
>> (FOOANDBAR identity '(foo bar baz))
> '(baz)
>> (FOOANDBAR identity '(bar baz foo))
> '()
>> (FOOORBAR identity '(foo bar baz))
> '() ; <-- Not what I expected
>
> _______________________________________________
> PEG mailing list
> PEG@lists.csail.mit.edu
> https://lists.csail.mit.edu/mailman/listinfo/peg
>
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
