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@...
Chris Double wrote:
> Just for fun, here's a draft of a document on implementing simple prologWow! This is impressive.
> like backtracking using Factor and continuations. Feedback welcome. I
> need to explain the implementation better...Test code is available at:
> : parlor-trick ( sum -- n1 n2 )Instead of [ ] [ fail ] ifte, write [ fail ] unless.
> #! 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 ;
> The implementation of choose will not only select a value from a list,What if I want to choose from a set of lists (that are not to be evaluated?)
> but it will 'call' that value if it is a quotation. 'call-or-value'
> handles the 'call if quotation' semantics:
> The failure continuation that is executed as a result of callingInstead you can push new namespaces that define a failure continuation
> '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.
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-fileOf course these are double quotes ".
Slava
On Wed, 16 Jun 2004 17:21:00 -0400, Slava Pestov <slava@...>
wrote:
>Thanks for that. I'm still getting familiar with what's available in
> Instead of [ ] [ fail ] ifte, write [ fail ] unless.
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,I thought about that and wasn't sure what the best approach was. I
> > 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?)
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 continuationNice! This will be better than constantly updating the global
> 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.
variable. I'll give it a try.
> Of course these are double quotes ".Yep, my mistake.
Chris.
--
Chris Double
chris.double@...
Chris Double wrote:
> Which I find difficult to read. Also the 'call-or-value' mechanismA continuation *is* a list.
> won't automatically call other callable objects (continuations most
> notably) as it doesn't detect them because they are not lists.
3] [ list? . ] callcc0
t
> Do youI think the best approach is to have a list of unevaluated literals. A
> think the 'quote everything' approach is better? Or is there a better
> option?
more complex list can simply be constructed at runtime and passed to
'choose'.
> Nice! This will be better than constantly updating the globalAlso look at the 'bind' word.
> variable. I'll give it a try.
Slava
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
On Thu, 8 Jul 2004 15:02:40 -0400, sa@... said:
> i think you may have inadvertently forgotten to include the definition ofYes, it's really a global renaming problem, sorry about that. 'init-amb'
> '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@...
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
On Mon, 12 Jul 2004 18:22:45 +1100, phimvt@...
<phimvt@...> wrote:
> Both come with their own XYXtst.joy test program andThanks Manfred, I'll take a look. I'm still getting used to the
> XYZtst.out output file. All on the main Joy page. It would
> be of interest to see how these can be rewritten in Factor.
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, ChrisAll the work on Factor is Slava's - he's doing a great job at moving
> and others on the very speedy development of Factor. Keep it up!
Factor along quickly.
Chris.
--
Chris Double
chris.double@...