! See http://rosettacode.org/wiki/Amb

! Largely inspired by (in french)
! http://www.rfc1149.net/inf355/2009/05/29/corrige-du-tp-scheme-2/

! Copyright (C) 2009 Jon Harper
! See http://factorcode.org/license.txt for BSD license.
USING: continuations fry kernel locals namespaces prettyprint
sequences ;
IN: amb

: words ( -- seq ) {
    { "the" "that" "a" } 
    { "frog" "elephant" "thing" } 
    { "walked" "treaded" "grows" }
    { "slowly" "quickly"  }
} ;
: letters-match? ( str1 str2 -- ? )
    [ last ] [ first ] bi* = ;
: sentence-match? ( seq -- ? )
    dup rest t [ letters-match? and ] 2reduce ;

SYMBOL: amb-next

: amb-init ( -- ) [ amb-next set f ] callcc1
[ "Alternatives exhausted" throw ] when ;
: next-amb ( -- next ) amb-next get continue ;

:: amb ( alternatives -- next )
    [
       :> escape
       amb-next get :> old-amb-next
       alternatives 
       [ 
         '[
            amb-next set
            _ escape continue-with
          ]  callcc0
       ] each
       t old-amb-next continue-with
    ] callcc1 ;

: search ( -- ) 
    amb-init
    words [ amb ] map
    dup sentence-match?
    [ " " join ] [ drop next-amb ] if . ;

MAIN: search