# Factor and backtracking

## Chris Double — 2004-06-16 05:16:52

    Just for fun, here's a draft of a document on implementing simple prolog

    like backtracking using Factor and continuations. Feedback welcome. I

    need to explain the implementation better...Test code is available at:

      http://www.double.co.nz/factor/backtracking.factor

    ------------------8<----------------

    Continuations

    =============

    When you capture a 'continuation' in Factor you get a quotation, that

    when called, will resume computation from where the continuation was

    originally captured. For example:

      : test-cc0

      [

        "inside continuation" print "cc" set

      ] callcc0

      "resuming continuation" print ;

    Executing this word will display execute the first quotation which the

    top item of the stack being the 'current continuation'. This

    continuation is stored in the global variable "cc". On return from the

    quotation the text "resuming continuation" is printed.

    The 'current continuation' captured by callcc0 can itself be

    called. This will resume computation from the point following the

    original 'callcc0' word. An example of calling the continuation is:

      "cc" get call

      => "resuming continuation"

    This can be called multiple times. An alternative word to capture a

    continuation is 'callcc1'. The continuation captured by this word,

    when called, will take the first argument from the stack and place

    that argument on the stack when resuming the continuation:

      : test-cc1

        [

          "inside continuation" print "cc" set 10

        ] callcc1

        "resuming continuation with value: " write print ;

      test-cc1

      => inside continuation

         resuming continuation with value: 10

      5 "cc" get call

      => resuming continuation with value: 5

      2 "cc" get call

      => resuming continuation with value: 2

    When a continuation is called and computation is resumed to the point

    following the 'callcc' word where it was captured, the stack that was

    originally in place at the time of the capture is restored:

      : test-cc-stack   ( -- )

         1 2 3       ( 1 2 3 -- )

         [                   ( 1 2 3 continuation -- )

           "cc" set     ( 1 2 3 -- )

           2drop drop   ( -- )

         ] callcc0

         ! (***a****)

         .s

         ;

    The stack at point '***a***' will be different depending on whether

    that point is reached by calling the captured continuation or from

    falling through the quotation passed to callcc0 (ie. a normal return

    from the callcc0 call). In the later case, a normal return, the stack

    will be empty due to the 2drops. In the former case, after calling the

    continuation, the stack will contain '1 2 3' due to it being restored

    to the point that it was when the continuation was captured. The

    sometimes requires carefull management of the stack when falling

    through the continuation call:

      "here" test-cc-stack

      => "here"

      "cc" get call

      => 3

         2

         1

         "here"

    Backtracking

    ============

    This section is basically implementing a Factor version of 'amb' [1]

    or 'choose' [2] as implemented in some Scheme examples.

    Imagine we have a word called 'choose'. This word takes a list of

    expressions on the stack and non-deterministically selects an item

    from the list, and returns that item:

      [ 1 2 3 4 5 ] chooose

      => 1, 2, 3, 4, or 5

    The value that it actually returns is whatever value is required to

    successfully complete a program. This is assuming the program has two

    possible completion states, 'success' and 'failure', and can indicate

    when something fails. Here is a simple example of usage:

    : two-numbers ( -- n1 n2 )

      #! Return two numbers that are each non-deterministically selected

      #! from 1-5.

      [ 1 2 3 4 5 ] choose [ 1 2 3 4 5 ] choose ;

    By default, just calling this function succeeds:

      two-numbers .s

      => 1

         1

    The two numbers selected are the first number in the list and as it

    succeeds these numbers are correct. The word 'fail' causes a failure

    to happen and results in different numbers being selected to get

    'success':

      fail .s

      => 2

         1

      fail .s

      => 3

         1

    We use this function inside a word, 'parlor-trick', which takes a

    single number form 1-10 and returns two numbers that can be used to

    add up to the number originally passed:

      : parlor-trick     ( sum -- n1 n2 )

        #! Given a number from 1-10, return two numbers that can be added

        #! to give the original number. Do this by backtracking.

        [ two-numbers 2dup + ] dip = [ ] [ fail ] ifte ;

    We call 'two-numbers' to get the two numbers that will cause the

    program to succeed, duplicate them (so we can return them), and add

    them together. These are compared to the original sum and if equal the

    two numbers are returned. If not equal then the computation

    'fails'. This results in 'two-numbers' returning two different numbers

    and things are repeated until a success occurs.

      7 parlor-trick

      => 5

         2

    When writing parlor-trick we are saying what we want (two numbers that

    add up to the given sum) rather than how to compute it. It is very

    declarative in manner.

    Logic Puzzles

    =============

    This style of programming is very good for 'logic puzzles'. From [1]:

    The Kalotans are a tribe with a peculiar quirk. Their males always

    tell the truth. Their females never make two consecutive true

    statements, or two consecutive untrue statements.

    An anthropologist (let's call him Worf) has begun to study them. Worf

    does not yet know the Kalotan language. One day, he meets a Kalotan

    (heterosexual) couple and their child Kibi. Worf asks Kibi: ``Are you

    a boy?'' Kibi answers in Kalotan, which of course Worf doesn't

    understand.

    Worf turns to the parents (who know English) for explanation. One of

    them says: ``Kibi said: `I am a boy.' '' The other adds: ``Kibi is a

    girl. Kibi lied.''

    Solve for the sex of the parents and Kibi.

    To solve this we introduce variables for the pieces of the puzzle with

    the data that we know, using choice for the options, then assert the

    information we know for a fact, based on this information.

    "parent1", "parent2" and "kibi" are the sexes of the parents (in order

    of appearance) and kibi. "kibi-self-desc" is the sex Kibi claimed to

    be (in Kalotan). "kibi-lied" is whether Kibi's claim was a lie.

      : parent1 ( -- parent1 ) "parent1" get ;

      : parent2 ( -- parent2 ) "parent2" get ;

      : kibi    ( -- kibi )    "kibi" get ;

      : kibi-self-desc ( -- kibi-self-desc ) "kibi-self-desc" get ;

      : kibi-lied     ( -- kibi-lied? )     "kibi-lied?" get ;

      : parent1-set ( value -- ) "parent1" set ;

      : parent2-set ( value -- ) "parent2" set ;

      : kibi-set    ( value -- ) "kibi" set ;

      : kibi-self-desc-set ( value -- ) "kibi-self-desc" set ;

      : kibi-lied-set     ( value -- ) "kibi-lied?" set ;

      : same-sex? ( s1 s2 -- b ) = ;

      : male?     ( s1 -- b ) "male" = ;

      : female?   ( s1 -- b ) "female" = ;

      : lied?     ( s1 -- b ) "yes" = ;

      : solve

        #! Set up the possible values

        [ "male" "female" ] choose parent1-set

        [ "male" "female" ] choose parent2-set

        [ "male" "female" ] choose kibi-set

        [ "male" "female" ] choose kibi-self-desc-set

        [ "yes" "no" ] choose kibi-lied-set

        #! The parents cannot be the same sex

        parent1 parent2 same-sex? assert-false

        #! If kibi is male he cannot have lied

        kibi male? [ kibi-lied lied? not assert-true ] [ ] ifte

        #! Encoding of the remaining rules

        kibi-lied lied? [

          kibi-self-desc male?   kibi female? and

          kibi-self-desc female? kibi male?   and

          xor assert-true

        ] [

          kibi-self-desc male?   kibi male?   and

          kibi-self-desc female? kibi female? and

          xor assert-true

        ] ifte

        parent1 male? [

          kibi female? kibi-lied lied? not and

          kibi male?   kibi-lied lied? and

          xor

          kibi-self-desc male?

          and

          assert-true

        ] [

          kibi female? kibi-lied lied? and assert-true

        ] ifte

        parent1 parent2 kibi .s ;

      init-amb

      solve

      => "female"

         "male"

         "female"

    This shows that parent1 is female, parent2 is male and Kibi is female.

    Implementation

    ==============

    What this code does is for each element in the 'choose' list, it

    expands it to code like the following (in pseudocode):

      global variable choose-fail = [ "error" ]

      [ 1 2 3 ] choose

      => expands to

        let prev-choose-fail = choose-fail

        [ // sk-continuation-item 1

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 1

          ] callcc0

          // sk-continuation-item 2

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 2

          ] callcc0

          // sk-continuation-item 3

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 3

          ] callcc0

          // This is the 'fail' part of 'choose*'

          // sk-continuation-item base case

          call prev-choose-fail

        ] callcc1

    To implement 'choose' we store a 'failure continuation' in a global

    variable. Whenever a computation fails through a call to 'fail' we

    call the global failure continuation to go back to a previous

    choice. If not failure continuations are available we display an error

    message.

      : set-choose-fail ( new-value -- ) "choose-fail" set ;

      : get-choose-fail ( -- value ) "choose-fail" get ;

      : init-choose [ "choose tree exhausted" error ] set-choose-fail ;

      init-choose

    I use a helper function 'lcurry1' for a left curry. It takes a value

    from the stack and a quotation and returns a quotation then when

    called will first put that item on the stack before executing:

      : lcurry1 ( value [ code ] -- code ) [ unit ] dip append ;

      5 [ + ] lcurry1

      => [ 5 + ]

    The implementation of choose will not only select a value from a list,

    but it will 'call' that value if it is a quotation. 'call-or-value'

    handles the 'call if quotation' semantics:

      : call-or-value ( [ code ] or value -- value )

         dup list? [ call ] [ ] ifte ;

    This allows:

      [ 1 2 3 4 ] choose

        !and

      [ [ do-something ] [ or-something ] ] choose

    The second example will return the result of evaluating whichever

    quoted expressions causes sucess of the computation.

    The failure continuation that is executed as a result of calling

    'fail' is really a 'closure'. It is a quotation that when called sets

    'choose-fail' to the previous value of 'choose-fail' so that the next

    fail trys the next failure in the list rather than the one currently

    being run.

      : make-failure-closure ( prev-choose-fail fk -- code )

        #! make a quotiation that when called will set 'choose-fail' to

        #! the previous choose-fail value and then call the failure

        #! continuation 'fk'

        [ call ] lcurry1 swap

        [ set-choose-fail ] lcurry1 swap

        append ;

    A 'success continuation' (sk) is the continuation that is called when

    a successfull result from choose is obtained. It exits from the

    current 'choose' and returns the value on the stack when it is

    called. The (fk) failure continuation is stored so it can be later

    called if a failure results. The failure will immediately go to the

    next choose item.

      : fk-continuation* ( sk prev-choose-fail [ code ] fk -- f f f)

        swap

       [ make-failure-closure set-choose-fail ] dip

       swap

       [ call-or-value  ] dip

       call f f f ;

      : fk-continuation ( sk prev-choose-fail [ code ] -- ) [

      fk-continuation* ] callcc0 2drop drop ;

    The implementation of choose gets the current value of the failure

    continuation. This is passed down the line to other functions (where

    it is called 'prev-choose-fail') and stored in the failure closure so it

    can restore the value back to this current value when required.

    'sk-continuation-item' is called for each item in the 'choose'

    list. It recursively calls itself. The base case of the recusion is to

    call the previous failure continuation.

    : sk-continuation-item ( args prev-choose-fail sk -- )

       pick [

    	[ uncons swap ] 2dip rot [ 2dup swap ] dip fk-continuation sk-continuation-item

       ] [

            drop drop drop get-choose-fail call

       ] ifte ;

     : choose ( [ arg1 arg2 ... ] -- ) get-choose-fail [

     sk-continuation-item ] callcc1 [ 2drop ] dip ;

    The 'fail' word just calls the current failure

    continuation. assert-true and assert-false call fail depending upon

    whether the topmost stack item is true or false.

      : fail ( -- ) get-choose-fail call ;

      : assert-true  ( b -- ) [ ] [ fail ] ifte ;

      : assert-false ( b -- ) [ fail ] [  ] ifte ;

    Sample Implementation

    =====================

    Test code is at:

    http://www.double.co.nz/factor/backtracking.factor

    Load with:

      'backtracking.factor' run-file

    [1]

    http://gd.tuwien.ac.at/languages/scheme/tutorial-dsitaram/t-y-scheme-Z-H-15.html

    [2] http://www.paulgraham.com/onlisp.html

        (Page 294 onwards)

    ------------------8<----------------

    --

      Chris Double

      chris.double@...

## Slava Pestov — 2004-06-16 21:21:00

    Chris Double wrote:

     > Just for fun, here's a draft of a document on implementing simple prolog

    > like backtracking using Factor and continuations. Feedback welcome. I

    > need to explain the implementation better...Test code is available at:

     Wow! This is impressive.

     >   : parlor-trick     ( sum -- n1 n2 )

    >     #! Given a number from 1-10, return two numbers that can be added

    >     #! to give the original number. Do this by backtracking.

    >     [ two-numbers 2dup + ] dip = [ ] [ fail ] ifte ;

     Instead of [ ] [ fail ] ifte, write [ fail ] unless.

     > The implementation of choose will not only select a value from a list,

    > but it will 'call' that value if it is a quotation. 'call-or-value'

    > handles the 'call if quotation' semantics:

     What if I want to choose from a set of lists (that are not to be evaluated?)

     > The failure continuation that is executed as a result of calling

    > 'fail' is really a 'closure'. It is a quotation that when called sets

    > 'choose-fail' to the previous value of 'choose-fail' so that the next

    > fail trys the next failure in the list rather than the one currently

    > being run.

     Instead you can push new namespaces that define a failure continuation

    variable on the namestack using >n. Note that the namestack state is

    part of a continuation. You'll need to balance out using n> too.

     >   'backtracking.factor' run-file

     Of course these are double quotes ".

    Slava

## Chris Double — 2004-06-16 22:29:56

    On Wed, 16 Jun 2004 17:21:00 -0400, Slava Pestov <slava@...>

    wrote:

     >

    > Instead of [ ] [ fail ] ifte, write [ fail ] unless.

     Thanks for that. I'm still getting familiar with what's available in

    the factor library. In some places I use recursion to iterate over a

    list where I could probably use each or inject instead.

     > > The implementation of choose will not only select a value from a list,

    > > but it will 'call' that value if it is a quotation. 'call-or-value'

    > > handles the 'call if quotation' semantics:

    >

    > What if I want to choose from a set of lists (that are not to be evaluated?)

     I thought about that and wasn't sure what the best approach was. I

    could have had everything needing to be quoted but then the most

    common approach becomes:

      [ [ 1 ] [ 2 ] [ 3 ] ] choose

    But with the way it is currently you need to doubly quote lists that

    you don't want to be evaluated:

      [ [ [ 1 2 3 ] ] [ [ 4 5 6 ] ] ] choose

    Which I find difficult to read. Also the 'call-or-value' mechanism

    won't automatically call other callable objects (continuations most

    notably) as it doesn't detect them because they are not lists. Do you

    think the 'quote everything' approach is better? Or is there a better

    option?

     > Instead you can push new namespaces that define a failure continuation

    > variable on the namestack using >n. Note that the namestack state is

    > part of a continuation. You'll need to balance out using n> too.

     Nice! This will be better than constantly updating the global

    variable. I'll give it a try.

     > Of course these are double quotes ".

     Yep, my mistake.

    Chris.

    --

      Chris Double

      chris.double@...

## Slava Pestov — 2004-06-17 02:49:55

    Chris Double wrote:

     > Which I find difficult to read. Also the 'call-or-value' mechanism

    > won't automatically call other callable objects (continuations most

    > notably) as it doesn't detect them because they are not lists.

     A continuation *is* a list.

         3] [ list? . ] callcc0

    t

     > Do you

    > think the 'quote everything' approach is better? Or is there a better

    > option?

     I think the best approach is to have a list of unevaluated literals. A

    more complex list can simply be constructed at runtime and passed to

    'choose'.

     > Nice! This will be better than constantly updating the global

    > variable. I'll give it a try.

     Also look at the 'bind' word.

    Slava

## sa@dfa.com — 2004-07-08 19:02:40

    chris:

    i think you may have inadvertently forgotten to include the definition of

    'init-amb':

      init-amb

      solve

      => "female"

         "male"

         "female"

    Just for fun, here's a draft of a document on implementing simple prolog

    like backtracking using Factor and continuations. Feedback welcome. I

    need to explain the implementation better...Test code is available at:

      http://www.double.co.nz/factor/backtracking.factor

    ------------------8<----------------

    Continuations

    =============

    When you capture a 'continuation' in Factor you get a quotation, that

    when called, will resume computation from where the continuation was

    originally captured. For example:

      : test-cc0

      [

        "inside continuation" print "cc" set

      ] callcc0

      "resuming continuation" print ;

    Executing this word will display execute the first quotation which the

    top item of the stack being the 'current continuation'. This

    continuation is stored in the global variable "cc". On return from the

    quotation the text "resuming continuation" is printed.

    The 'current continuation' captured by callcc0 can itself be

    called. This will resume computation from the point following the

    original 'callcc0' word. An example of calling the continuation is:

      "cc" get call

      => "resuming continuation"

    This can be called multiple times. An alternative word to capture a

    continuation is 'callcc1'. The continuation captured by this word,

    when called, will take the first argument from the stack and place

    that argument on the stack when resuming the continuation:

      : test-cc1

        [

          "inside continuation" print "cc" set 10

        ] callcc1

        "resuming continuation with value: " write print ;

      test-cc1

      => inside continuation

         resuming continuation with value: 10

      5 "cc" get call

      => resuming continuation with value: 5

      2 "cc" get call

      => resuming continuation with value: 2

    When a continuation is called and computation is resumed to the point

    following the 'callcc' word where it was captured, the stack that was

    originally in place at the time of the capture is restored:

      : test-cc-stack   ( -- )

         1 2 3       ( 1 2 3 -- )

         [                   ( 1 2 3 continuation -- )

           "cc" set     ( 1 2 3 -- )

           2drop drop   ( -- )

         ] callcc0

         ! (***a****)

         .s

         ;

    The stack at point '***a***' will be different depending on whether

    that point is reached by calling the captured continuation or from

    falling through the quotation passed to callcc0 (ie. a normal return

    from the callcc0 call). In the later case, a normal return, the stack

    will be empty due to the 2drops. In the former case, after calling the

    continuation, the stack will contain '1 2 3' due to it being restored

    to the point that it was when the continuation was captured. The

    sometimes requires carefull management of the stack when falling

    through the continuation call:

      "here" test-cc-stack

      => "here"

      "cc" get call

      => 3

         2

         1

         "here"

    Backtracking

    ============

    This section is basically implementing a Factor version of 'amb' [1]

    or 'choose' [2] as implemented in some Scheme examples.

    Imagine we have a word called 'choose'. This word takes a list of

    expressions on the stack and non-deterministically selects an item

    from the list, and returns that item:

      [ 1 2 3 4 5 ] chooose

      => 1, 2, 3, 4, or 5

    The value that it actually returns is whatever value is required to

    successfully complete a program. This is assuming the program has two

    possible completion states, 'success' and 'failure', and can indicate

    when something fails. Here is a simple example of usage:

    : two-numbers ( -- n1 n2 )

      #! Return two numbers that are each non-deterministically selected

      #! from 1-5.

      [ 1 2 3 4 5 ] choose [ 1 2 3 4 5 ] choose ;

    By default, just calling this function succeeds:

      two-numbers .s

      => 1

         1

    The two numbers selected are the first number in the list and as it

    succeeds these numbers are correct. The word 'fail' causes a failure

    to happen and results in different numbers being selected to get

    'success':

      fail .s

      => 2

         1

      fail .s

      => 3

         1

    We use this function inside a word, 'parlor-trick', which takes a

    single number form 1-10 and returns two numbers that can be used to

    add up to the number originally passed:

      : parlor-trick     ( sum -- n1 n2 )

        #! Given a number from 1-10, return two numbers that can be added

        #! to give the original number. Do this by backtracking.

        [ two-numbers 2dup + ] dip = [ ] [ fail ] ifte ;

    We call 'two-numbers' to get the two numbers that will cause the

    program to succeed, duplicate them (so we can return them), and add

    them together. These are compared to the original sum and if equal the

    two numbers are returned. If not equal then the computation

    'fails'. This results in 'two-numbers' returning two different numbers

    and things are repeated until a success occurs.

      7 parlor-trick

      => 5

         2

    When writing parlor-trick we are saying what we want (two numbers that

    add up to the given sum) rather than how to compute it. It is very

    declarative in manner.

    Logic Puzzles

    =============

    This style of programming is very good for 'logic puzzles'. From [1]:

    The Kalotans are a tribe with a peculiar quirk. Their males always

    tell the truth. Their females never make two consecutive true

    statements, or two consecutive untrue statements.

    An anthropologist (let's call him Worf) has begun to study them. Worf

    does not yet know the Kalotan language. One day, he meets a Kalotan

    (heterosexual) couple and their child Kibi. Worf asks Kibi: ``Are you

    a boy?'' Kibi answers in Kalotan, which of course Worf doesn't

    understand.

    Worf turns to the parents (who know English) for explanation. One of

    them says: ``Kibi said: `I am a boy.' '' The other adds: ``Kibi is a

    girl. Kibi lied.''

    Solve for the sex of the parents and Kibi.

    To solve this we introduce variables for the pieces of the puzzle with

    the data that we know, using choice for the options, then assert the

    information we know for a fact, based on this information.

    "parent1", "parent2" and "kibi" are the sexes of the parents (in order

    of appearance) and kibi. "kibi-self-desc" is the sex Kibi claimed to

    be (in Kalotan). "kibi-lied" is whether Kibi's claim was a lie.

      : parent1 ( -- parent1 ) "parent1" get ;

      : parent2 ( -- parent2 ) "parent2" get ;

      : kibi    ( -- kibi )    "kibi" get ;

      : kibi-self-desc ( -- kibi-self-desc ) "kibi-self-desc" get ;

      : kibi-lied     ( -- kibi-lied? )     "kibi-lied?" get ;

      : parent1-set ( value -- ) "parent1" set ;

      : parent2-set ( value -- ) "parent2" set ;

      : kibi-set    ( value -- ) "kibi" set ;

      : kibi-self-desc-set ( value -- ) "kibi-self-desc" set ;

      : kibi-lied-set     ( value -- ) "kibi-lied?" set ;

      : same-sex? ( s1 s2 -- b ) = ;

      : male?     ( s1 -- b ) "male" = ;

      : female?   ( s1 -- b ) "female" = ;

      : lied?     ( s1 -- b ) "yes" = ;

      : solve

        #! Set up the possible values

        [ "male" "female" ] choose parent1-set

        [ "male" "female" ] choose parent2-set

        [ "male" "female" ] choose kibi-set

        [ "male" "female" ] choose kibi-self-desc-set

        [ "yes" "no" ] choose kibi-lied-set

        #! The parents cannot be the same sex

        parent1 parent2 same-sex? assert-false

        #! If kibi is male he cannot have lied

        kibi male? [ kibi-lied lied? not assert-true ] [ ] ifte

        #! Encoding of the remaining rules

        kibi-lied lied? [

          kibi-self-desc male?   kibi female? and

          kibi-self-desc female? kibi male?   and

          xor assert-true

        ] [

          kibi-self-desc male?   kibi male?   and

          kibi-self-desc female? kibi female? and

          xor assert-true

        ] ifte

        parent1 male? [

          kibi female? kibi-lied lied? not and

          kibi male?   kibi-lied lied? and

          xor

          kibi-self-desc male?

          and

          assert-true

        ] [

          kibi female? kibi-lied lied? and assert-true

        ] ifte

        parent1 parent2 kibi .s ;

      init-amb

      solve

      => "female"

         "male"

         "female"

    This shows that parent1 is female, parent2 is male and Kibi is female.

    Implementation

    ==============

    What this code does is for each element in the 'choose' list, it

    expands it to code like the following (in pseudocode):

      global variable choose-fail = [ "error" ]

      [ 1 2 3 ] choose

      => expands to

        let prev-choose-fail = choose-fail

        [ // sk-continuation-item 1

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 1

          ] callcc0

          // sk-continuation-item 2

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 2

          ] callcc0

          // sk-continuation-item 3

          [ // fk continuation

            set choose-fail = [ // This is the 'failure closure'

                                // returned by 'make-failure-closure'

                                set choose-fail prev-choose-fail

                                call fk

                              ]

            call sk with value 3

          ] callcc0

          // This is the 'fail' part of 'choose*'

          // sk-continuation-item base case

          call prev-choose-fail

        ] callcc1

    To implement 'choose' we store a 'failure continuation' in a global

    variable. Whenever a computation fails through a call to 'fail' we

    call the global failure continuation to go back to a previous

    choice. If not failure continuations are available we display an error

    message.

      : set-choose-fail ( new-value -- ) "choose-fail" set ;

      : get-choose-fail ( -- value ) "choose-fail" get ;

      : init-choose [ "choose tree exhausted" error ] set-choose-fail ;

      init-choose

    I use a helper function 'lcurry1' for a left curry. It takes a value

    from the stack and a quotation and returns a quotation then when

    called will first put that item on the stack before executing:

      : lcurry1 ( value [ code ] -- code ) [ unit ] dip append ;

      5 [ + ] lcurry1

      => [ 5 + ]

    The implementation of choose will not only select a value from a list,

    but it will 'call' that value if it is a quotation. 'call-or-value'

    handles the 'call if quotation' semantics:

      : call-or-value ( [ code ] or value -- value )

         dup list? [ call ] [ ] ifte ;

    This allows:

      [ 1 2 3 4 ] choose

        !and

      [ [ do-something ] [ or-something ] ] choose

    The second example will return the result of evaluating whichever

    quoted expressions causes sucess of the computation.

    The failure continuation that is executed as a result of calling

    'fail' is really a 'closure'. It is a quotation that when called sets

    'choose-fail' to the previous value of 'choose-fail' so that the next

    fail trys the next failure in the list rather than the one currently

    being run.

      : make-failure-closure ( prev-choose-fail fk -- code )

        #! make a quotiation that when called will set 'choose-fail' to

        #! the previous choose-fail value and then call the failure

        #! continuation 'fk'

        [ call ] lcurry1 swap

        [ set-choose-fail ] lcurry1 swap

        append ;

    A 'success continuation' (sk) is the continuation that is called when

    a successfull result from choose is obtained. It exits from the

    current 'choose' and returns the value on the stack when it is

    called. The (fk) failure continuation is stored so it can be later

    called if a failure results. The failure will immediately go to the

    next choose item.

      : fk-continuation* ( sk prev-choose-fail [ code ] fk -- f f f)

        swap

       [ make-failure-closure set-choose-fail ] dip

       swap

       [ call-or-value  ] dip

       call f f f ;

      : fk-continuation ( sk prev-choose-fail [ code ] -- ) [

      fk-continuation* ] callcc0 2drop drop ;

    The implementation of choose gets the current value of the failure

    continuation. This is passed down the line to other functions (where

    it is called 'prev-choose-fail') and stored in the failure closure so it

    can restore the value back to this current value when required.

    'sk-continuation-item' is called for each item in the 'choose'

    list. It recursively calls itself. The base case of the recusion is to

    call the previous failure continuation.

    : sk-continuation-item ( args prev-choose-fail sk -- )

       pick [

                 [ uncons swap ] 2dip rot [ 2dup swap ] dip fk-continuation

    sk-continuation-item

       ] [

            drop drop drop get-choose-fail call

       ] ifte ;

     : choose ( [ arg1 arg2 ... ] -- ) get-choose-fail [

     sk-continuation-item ] callcc1 [ 2drop ] dip ;

    The 'fail' word just calls the current failure

    continuation. assert-true and assert-false call fail depending upon

    whether the topmost stack item is true or false.

      : fail ( -- ) get-choose-fail call ;

      : assert-true  ( b -- ) [ ] [ fail ] ifte ;

      : assert-false ( b -- ) [ fail ] [  ] ifte ;

    Sample Implementation

    =====================

    Test code is at:

    http://www.double.co.nz/factor/backtracking.factor

    Load with:

      'backtracking.factor' run-file

    [1]

    http://gd.tuwien.ac.at/languages/scheme/tutorial-dsitaram/t-y-scheme-Z-H-15.html

    [2] http://www.paulgraham.com/onlisp.html

        (Page 294 onwards)

    ------------------8<----------------

    --

      Chris Double

      chris.double@...

    Yahoo! Groups Links

## Chris Double — 2004-07-11 00:47:12

    On Thu, 8 Jul 2004 15:02:40 -0400, sa@... said:

     > i think you may have inadvertently forgotten to include the definition of

    > 'init-amb':

     Yes, it's really a global renaming problem, sorry about that. 'init-amb'

    should be 'init-choose', and the code for that is included. It sets up

    the global backtracking state.

    Cheers,

    Chris.

    --

      Chris Double

      chris.double@...

## phimvt@lurac.latrobe.edu.au — 2004-07-12 07:22:45

    On Thu, 8 Jul 2004 sa@... wrote:

    [..]

    > Just for fun, here's a draft of a document on implementing simple prolog

    > like backtracking using Factor and continuations. Feedback welcome. I

    > need to explain the implementation better...Test code is available at:

    >

    >   http://www.double.co.nz/factor/backtracking.factor

    It may be of interest that backtracking can be implemented

    in Joy without the general primitives "amb" and "fail", and

    without any special internal machinery for capturing the

    continuation. The idea is that the remainder of what is to

    be computed is pushed onto the Joy stack as a quotation,

    which is then treated as a stack. I have written two libraries

    which use this idea:

        plglib.joy   # propositional logic theorem prover using

                     # "semantic tableaux" or "truth trees"

        grmlib.joy   # context free grammar processor for

                     # parsing and generating

    Both come with their own XYXtst.joy test program and

    XYZtst.out output file. All on the main Joy page. It would

    be of interest to see how these can be rewritten in Factor.

    I also use this opportunity to congratulate Slava, Chris

    and others on the very speedy development of Factor. Keep it up!

      - Manfred

## Chris Double — 2004-07-12 21:26:25

    On Mon, 12 Jul 2004 18:22:45 +1100, phimvt@...

    <phimvt@...> wrote:

     > Both come with their own XYXtst.joy test program and

    > XYZtst.out output file. All on the main Joy page. It would

    > be of interest to see how these can be rewritten in Factor.

     Thanks Manfred, I'll take a look. I'm still getting used to the

    different ways of doing things in a concatenative language. I have to

    deliberately tell myself to stop trying to write Scheme code in Factor

    usually!

     > I also use this opportunity to congratulate Slava, Chris

    > and others on the very speedy development of Factor. Keep it up!

     All the work on Factor is Slava's - he's doing a great job at moving

    Factor along quickly.

    Chris.

    --

      Chris Double

      chris.double@...