(datatype term (Term String))
(datatype nonterm (NonTerm String))
(datatype tree (NT String tree tree)
                  (T String String))

(function getString (i64) String)

(relation Prod (nonterm nonterm nonterm))
(relation End (nonterm String))



(relation P (i64 i64 nonterm))
(function B (i64 i64 nonterm) tree :cost 1000)

(rule ((End (NonTerm a) s)
       (= s (getString pos)))
      ((P 1 pos (NonTerm a))
       (union (B 1 pos (NonTerm a)) (T a s)))) 

(rule ((Prod (NonTerm a) (NonTerm b) (NonTerm c)) ;; a -> bc
       (P p1 s (NonTerm b))
       (P p2 (+ s p1) (NonTerm c)))
      ((P (+ p1 p2) s (NonTerm a))))


(rule ((Prod (NonTerm a) (NonTerm b) (NonTerm c))
       (= f1 (B p1 s (NonTerm b)))
       (= f2 (B p2 (+ s p1) (NonTerm c))))
      ((union (B (+ p1 p2) s (NonTerm a)) 
       (NT a f1 f2))))

(push)


(set (getString 1) "she")
(set (getString 2) "eats")
(set (getString 3) "a")
(set (getString 4) "fish")
(set (getString 5) "with")
(set (getString 6) "a")
(set (getString 7) "fork")


(Prod (NonTerm "S") (NonTerm "NP") (NonTerm "VP"))
(Prod (NonTerm "VP") (NonTerm "VP") (NonTerm "PP"))
(Prod (NonTerm "VP") (NonTerm "V") (NonTerm "NP"))
(End (NonTerm "VP")  "eats")
(Prod (NonTerm "PP") (NonTerm "P") (NonTerm "NP"))
(Prod (NonTerm "NP") (NonTerm "DET") (NonTerm "N"))
(End (NonTerm "NP") "she")
(End (NonTerm "V") "eats")
(End (NonTerm "P") "with")
(End (NonTerm "N") "fish")
(End (NonTerm "N") "fork")
(End (NonTerm "DET") "a")


(let test1 (B 7 1 (NonTerm "S")))

(run 100)

(check (P 7 1 (NonTerm "S")))
(fail (check (P 7 1 (NonTerm "VP"))))
(fail (check (P 7 1 (NonTerm ""))))

(query-extract test1)

(pop)

(push)

(Prod (NonTerm "S") (NonTerm "A") (NonTerm "B"))
(Prod (NonTerm "S") (NonTerm "B") (NonTerm "C"))
(Prod (NonTerm "A") (NonTerm "B") (NonTerm "A"))
(End (NonTerm "A") "a")
(Prod (NonTerm "B") (NonTerm "C") (NonTerm "C"))
(End (NonTerm "B") "b")
(Prod (NonTerm "C") (NonTerm "A") (NonTerm "B"))
(End (NonTerm "C") "a")

(push)

(set (getString 1) "a")
(set (getString 2) "b")
(set (getString 3) "a")
(set (getString 4) "a")
(set (getString 5) "b")

(run 100)
(check (P 5 1 (NonTerm "S")))
(fail (check (P 5 1 (NonTerm "B"))))
(let test2 (B 5 1 (NonTerm "S")))
(query-extract:variants 10  test2)

(pop)

(push)

(set (getString 1) "a")
(set (getString 2) "a")
(set (getString 3) "a")
(set (getString 4) "a")
(set (getString 5) "a")

(run 100)
(check (P 5 1 (NonTerm "S")))
(check (P 5 1 (NonTerm "A")))
(fail (check (P 5 1 (NonTerm "B"))))
(fail (check (P 5 1 (NonTerm ""))))
(fail (check (P 5 1 (NonTerm "unrelated"))))
(let test3 (B 5 1 (NonTerm "S")))
(query-extract :variants 10 test3)

(pop)