1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
module Code where
import qualified Data.Map as M
import IR (Id(..))
data Datum
= Atom Int -- unifies a constant
| Struct Id -- unifies a structure with arity
| VoidRef (Maybe Int) -- unifies with anything (references may refer to variable names)
| LocalRef Int (Maybe Int) -- code-local variable idx (should not occur on heap)
| HeapRef Int (Maybe Int) -- heap structure idx
deriving (Show, Eq, Ord)
data Instr
= U Datum -- something unifiable
| NoGoal -- trivial goal
| Goal -- we start a new goal, set up backtracking etc
| Call -- all seems okay, call the goal
| LastCall -- tail call the goal
| Cut -- remove all alternative clauses of the current goal
deriving (Show)
type Code = [Instr]
type Defs = M.Map Id [Code]
data Heap =
Heap Int (M.Map Int Datum)
deriving (Show)
emptyHeap = Heap 0 M.empty
type Scope = M.Map Int Int
emptyScope :: Scope
emptyScope = M.empty
data Cho =
Cho
{ hed :: Code -- head pointer
, hvar :: Scope -- variables unified in head (so far)
, gol :: Code -- goal pointer
, gvar :: Scope -- variables unified in the goal
, heap :: Heap -- a snapshot of the heap (there's no trail; we rely on CoW copies in other choicepoints)
, stk :: [(Code, Scope, [Cho])] -- remaining goals together with their vars and cuts
, cut :: [Cho] -- snapshot of choicepoints before entering
}
deriving (Show)
data Interp =
Interp
{ defs :: Defs -- global definitions for lookup (TODO can we externalize?)
, cur :: Cho -- the choice that is being evaluated right now
, cho :: [Cho] -- remaining choice points
}
deriving (Show)
|
