title: Backtracking (by mlg)
description:

: ENTER ( addr -- )
  >R
;
: PRO ( -- )
   R> R> >L ENTER LDROP
;
: CONT ( i*x -- j*x )
   L> >R  R@ ENTER  R> >L
;

 Continuation: for a called word, it is the address of the residue
 of the calling procedure's code.

 PRO is a prologue of a backtrackable word.
 It moves the continuation address from the return stack to the L-stack.
 When the definition is exited, the continuation address is removed from
 the L-stack.

 CONT (a.k.a. YIELD ) calls the continuation. The stack effect ( i*x -- j*x )
 is due to execution of the continuation. For the time of executing
 the continuation, its address is temporarily removed from the L-stack.

 Words that use PRO and CONT can call the continuation any number of
 times (0, 1, or N).

 Generators are words that generate values and call the continuation for
 each of the values.

 Filters are words that check some condition and call the continuation
 only for values that make the condition true.

 Generators implement loops over sets of values. Filters are
 condition-checking statements, or loops that execute 0 or 1 times.

 The advantage of backtracking is that we get reusable routines that
 implement loops. If we change the way of looking over a set of values,
 we change the corresponding iterator, and do not touch the words that
 use this iterator.


Examples:

: generate-numbers (  --> i --  -->  )
   PRO 20 0 DO I CONT LOOP
;
: filter-even ( i --> i --  -->  )
  PRO DUP 2 MOD 0= IF CONT ELSE DROP THEN
;
: filter-3*n ( i --> i --  -->  )
  PRO DUP 3 MOD 0= IF CONT ELSE DROP THEN
;

: t1
    generate-numbers .
;

: t2
    generate-numbers filter-even filter-3*n .
;


t1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  ok[Dec]
t2
0 6 12 18  ok[Dec]



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