# Backtracking

## wtanksley@bigfoot.com — 2000-05-10 20:33:22

    I've been doing some more thinking about continuations.  I finally did some

    research, and found these articles again:

    (Bakctracking in Forth:)

    http://x45.deja.com/getdoc.xp?AN=378188059&CONTEXT=957908714.382009393&hitnu

    m=2

    http://x45.deja.com/getdoc.xp?AN=388172034&CONTEXT=957908714.382009393&hitnu

    m=3

    (mlg's entire webpage -- many papers in English, but it's very technical

    English.)

    http://www.forth.org.ru/~mlg

    These are not easy to understand...  But it's clear that they implement

    backtracking, and reasonably clear that they implement continuations.

    The second article contains perhaps a bit more context; there we see that

    backtracking words behave as control structures.  After quite a bit of

    thought, I think I can make sense of this.

    The first thing to notice is that these continuations don't include any

    provision for saving the stack (or any part of it).  If the user wants to

    call the continuation, it's the user's responsibility to provide the proper

    arguments.  Conversely, if a continuation author wants anyone to use his

    code, he'll make it easy to provide the appropriate arguments; perhaps, for

    example, he'll return all of the arguments underneath the answer, so that

    the user can consume the answer and then call the continuation.

    It happens that in this implementation, calling the continuation is implicit

    (which is why it's used only for backtracking).  I can't figure out how to

    translate this to Joy, which proves that I don't understand it yet.  I hope

    that one of you will.

    Sorry for the long, meaningless letter.  I hope the links are of some use.

    -Billy