Thinking in States
States in Puzzles
Consider:
Given water jugs A, B and C of respective capacities 8, 5 and 3
and respective fill states full, empty and empty, measure
exactly 4 units into both A and B.
Clearly, an important state in this puzzle is the amount
of water in each jug. Using Haskell, let us represent this state
as a triple (A,B,C):
type State = (Int,Int,Int)
Now, we are to find a sequence of transfers leading from state
(8,0,0) to state (4,4,0). We start with a function that, given a
state, yields a list of all proper successor states:
successors :: State -> [State]
successors (a,b,c) =
let ab = min a (5 - b)
ac = min a (3 - c)
ba = min b (8 - a)
bc = min b (3 - c)
ca = min c (8 - a)
cb = min c (5 - b)
ss = [(ab,a-ab,b+ab,c), (ac,a-ac,b,c+ac), (ba,a+ba,b-ba,c),
(bc,a,b-bc,c+bc), (ca,a+ca,b,c-ca), (cb,a,b+cb,c-cb)]
in
[(a',b',c') | (transfer,a',b',c') <- ss, transfer > 0]
We can test this function interactively:
Main> successors (8,0,0)
[(3,5,0),(5,0,3)]
Let us now determine whether we can, starting from the initial
state, actually reach the target state. We try breadth-first
search, a complete and space-inefficient search strategy:
search :: [State] -> Bool
search (s:ss)
| s == (4,4,0) = True
| otherwise = search $ ss ++ successors s
In each iteration, we consider the first state in the given list
of states. If it's the target state, we're done. Otherwise, its
successors are appended to the remaining states (to be considered
later), and the search continues. We can now query
search [(8,0,0)]
True
and know that the puzzle actually has a solution. To find a
sequence of actions leading to the target state, we reconsider
the state representation. Instead of merely keeping track
of the amount of water in the jugs, we also store how we obtained
each configuration. We represent this new state as a
pair (J,P): J is the jug configuration (A,B,C) like
before, and P is a "path" that leads from the starting state
to configuration J. A path is a list of pairs of
integers (From,To), meaning that we poured
water from jug From into jug To. For each
successor state, we record how its configuration was reached by
appending the corresponding path element to (a copy of) its
predecessor's path. The new program
(jugs.hs) is:
type Jugs = (Int,Int,Int)
type Path = [(Int,Int)]
type State = (Jugs, Path)
start :: State
start = ((8,0,0), [])
successors :: State -> [State]
successors ((a,b,c),path) =
let ab = min a (5 - b)
ac = min a (3 - c)
ba = min b (8 - a)
bc = min b (3 - c)
ca = min c (8 - a)
cb = min c (5 - b)
ss = [(ab, a-ab, b+ab,c, path++[(1,2)]),
(ac, a-ac, b,c+ac, path++[(1,3)]),
(ba, a+ba, b-ba,c, path++[(2,1)]),
(bc, a,b-bc, c+bc, path++[(2,3)]),
(ca, a+ca,b, c-ca, path++[(3,1)]),
(cb, a,b+cb, c-cb, path++[(3,2)])]
in
[((a',b',c'), path') | (transfer,a',b',c',path') <- ss, transfer > 0]
search :: [State] -> Path
search (s:ss)
| fst s == (4,4,0) = snd s
| otherwise = search $ ss ++ successors s
A path is now readily found:
search [start]
[(1,2),(2,3),(3,1),(2,3),(1,2),(2,3),(3,1)]
There are various ways to make this more efficient. We could, for
example, prepend the new path elements and reverse the path
once at the end of the search. Besides, we could devise a more
conveniently readable path representation.
In a similar manner, you can solve other puzzles involving search
like "wolf and goat", 8-puzzles, and "missionary and cannibal".
To illustrate how to do without tuples, a Lisp solution (where
nested lists are used to represent the states) is available
from here.
States in Programs
Let us now build an interpreter for a simple programming language
over integers in Prolog. Using Prolog terms, we represent
programs as abstract syntax trees (ASTs) like:
function(Name, Parameter, Body)
call(Name, Expression)
return(Expression)
assign(Variable, Expression)
if(Condition, Then, Else)
while(Condition, Body)
sequence(First, Second)
To symbolically distinguish variables from numerals in arithmetic
expressions, we use the unary functors "v" and "n", respectively.
Look up the definition of is_program/2 in
the source code for a complete declarative
specification of the chosen representation. Also included, you
find a parser to automatically generate this term representation
from more readable syntax. For instance, the following program
(recursively) computing and printing the fourth Catalan number
catalan (n) {
if (n == 0) {
return 1;
} else {
c = catalan(n-1);
r = 2*(2*n + 1)*c / (n + 2);
return r;
}
}
print catalan(4);
is converted to a syntax tree like this:
?- parse("catalan (n) { if (n == 0) { return 1; } else { c = catalan(n-1);
r = 2*(2*n + 1)*c / (n + 2); return r; } } print catalan(4);", Tree).
Tree = sequence(function(catalan, n,
if(bin(=, v(n), n(0)),
return(n(1)),
sequence(assign(c, call(catalan, bin(-, v(n), n(1)))),
sequence(assign(r, bin(/,
bin(*, bin(*, n(2), bin(+, bin(*, n(2), v(n)), n(1))), v(c)),
bin(+, v(n), n(2)))),
return(v(r)))))),
print(call(catalan, n(4))))
To interpret such programs, we have to keep track of the
state of computation. It consists of:
- the binding environment for variables
- all encountered function definitions
These two, collectively referred to as the environment, are
represented as a pair of association lists, associating variable
names with values and function heads with function bodies. This
makes defining and referring to functions as well as accessing
variables O(log(N)) operations in the number of encountered
functions and variables, respectively.
Clearly, the predicates responsible for interpreting syntax trees
define relations between such environments and thus between
states. This is how to interpret imperative programs in a
purely declarative way.
To evaluate expressions with respect to the current environment,
we use the predicate eval/3:
eval(bin(Op,A,B), Env, Value) :-
eval(A, Env, VA),
eval(B, Env, VB),
eval_(Op, VA, VB, Value).
eval(v(V), Env, Value) :-
env_get_var(Env, V, Value).
eval(n(N), _, N).
eval(call(Name, Arg), Env0, Value) :-
eval(Arg, Env0, ArgVal),
env_func_body(Env0, Name, ArgName, Body),
env_clear_variables(Env0, Env1),
env_put_var(ArgName, ArgVal, Env1, Env2),
interpret(Body, Env2, Value).
eval_(+, A, B, V) :- V is A + B.
eval_(-, A, B, V) :- V is A - B.
eval_(*, A, B, V) :- V is A * B.
eval_(/, A, B, V) :- V is A // B.
eval_(=, A, B, V) :- (A =:= B -> V = 1 ; V = 0).
eval_(>, A, B, V) :- ( A > B -> V = 1 ; V = 0).
eval_(<, A, B, V) :- ( A < B -> V = 1 ; V = 0).
The predicates accessing the environment (env_get_var/3
etc.) are straight-forward, and you can look up their definitions
in the source code. Finally, the
predicate interpret/3 specifies how, if at all, each
construct of our language changes the environment:
interpret(print(P), Env, Env) :-
eval(P, Env, Value),
format("~w\n", [Value]).
interpret(sequence(A,B), Env0, Env) :-
interpret(A, Env0, Env1),
( A = return(_) ->
Env = Env1
; interpret(B, Env1, Env)
).
interpret(call(Name, Arg), Env0, Env0) :-
eval(Arg, Env0, ArgVal),
env_func_body(Env0, Name, ArgName, Body),
env_clear_variables(Env0, Env1),
env_put_var(ArgName, ArgVal, Env1, Env2),
interpret(Body, Env2, _).
interpret(function(Name,Arg,Body), Env0, Env) :-
env_put_func(Name, Arg, Body, Env0, Env).
interpret(if(Cond,Then,Else), Env0, Env) :-
eval(Cond, Env0, Value),
( Value =\= 0 ->
interpret(Then, Env0, Env)
; interpret(Else, Env0, Env)
).
interpret(assign(Var, Expr), Env0, Env) :-
eval(Expr, Env0, Value),
env_put_var(Var, Value, Env0, Env).
interpret(while(Cond, Body), Env0, Env) :-
eval(Cond, Env0, Value),
( Value =\= 0 ->
interpret(Body, Env0, Env1),
interpret(while(Cond, Body), Env1, Env)
; Env = Env0
).
interpret(return(Expr), Env0, Value) :-
eval(Expr, Env0, Value).
interpret(nop, Env, Env).
Two things deserve special attention: For one, the print
statement produces a side-effect: It is meant to show
output on the terminal, and this cannot be expressed by
transforming the binding environment. The interpreter is thus not
purely logical. To fix this, we could incorporate a suitable
representation of the state of the "world" into our environment
and adjust it appropriately whenever a print statement is
encountered. Second, return statements are special in that
their resulting environment consists of a single
value. The eval/3 predicate makes use of this when
evaluating function calls.
To interpret a program, we start with a fresh environment and
discard the resulting environment:
run(Tree) :-
env_new(Env),
interpret(Tree, Env, _).
We can run our simple example program like this:
?- parse("catalan (n) { if (n == 0) { return 1; } else { c = catalan(n-1);
r = 2*(2*n + 1)*c / (n + 2); return r; } } print catalan(4);", Tree), run(Tree).
42
States elsewhere
To get rid of the interpreter's overhead incurred by looking up
variables and function definitions in the environment, we now
compile programs to virtual machine code in which variables
and functions are addressed by offsets into specific regions of
the virtual machine's "memory". Using a programming language
permitting efficient array indexing, you can thus interpret
variable access and function calls in O(1).
Our virtual machine (VM) shall be stack-based and have the
following instructions:
| Instruction |
Effect |
|
| halt |
stop execution |
| alloc n |
push n zeros on top of stack |
| pushc c |
push constant c on top of stack |
| pushv v |
push value of variable v on top of stack |
| pop v |
remove topmost element from stack and assign its value to variable v |
| add |
replace topmost two elements of stack by their sum |
| sub |
... subtract |
| mul |
... multiply |
| div |
... integer division |
| jmp adr |
continue execution at instruction adr |
| jne adr |
remove topmost two stack elements and jump to adr if they are not equal |
| jge adr |
jump if greater or equal |
| jle adr |
jump if less or equal |
| call adr |
call subroutine starting at adr |
| print |
remove topmost stack element and print its value |
| ret |
return from subroutine |
Variables are now actually integers, denoting an offset
into the stack frame of the function being executed. 0 (zero)
corresponds to a function's sole argument and is copied on the
stack when encountering a call
instruction. Also, call saves the current frame pointer
and program counter on the stack. A function can allocate
additional space for local variables by means of
the alloc instruction. The return
instruction (ret) removes all stack elements
allocated by the current function, restores the frame pointer and
program counter, and pushes the function's return value on the
stack.
The following example program and corresponding VM code illustrate
most of the instructions:
fac(n) {
f = 1;
while (n > 1) {
f = f*n;
n = n - 1;
}
return(f);
}
print fac(4);
|
|
0: jmp 33
2: alloc 1
4: pushc 1
6: pop 1
8: pushv 0
10: pushc 1
12: jle 30
14: pushv 1
16: pushv 0
18: mul
19: pop 1
21: pushv 0
23: pushc 1
25: sub
26: pop 0
28: jmp 8
30: pushv 1
32: ret
33: pushc 4
35: call 2
37: print
38: halt
|
|
Generating such VM code from an abstract syntax tree is
straight-forward. In essence, we will write a predicate
compile/3 with clauses roughly of the form
compile(functor(Arg1,Arg2,...,Argn), State_0, State) :-
compile(Arg1, State_0, State_1),
compile(Arg2, State_1, State_2),
:
:
compile(Argn, State_(n-1), State_n),
emit(instruction_depending_on_functor, State_n, State).
DCG notation implicitly endows us with two additional arguments
and yields the equivalent version:
compile(functor(Arg1,Arg2,...,Argn)) -->
compile(Arg1),
compile(Arg2),
:
:
compile(Argn),
emit(instruction_depending_on_functor).
When compiling to VM code, we keep track of the state of
the compilation process:
- instructions emitted so far
- offsets of encountered function definitions
- offsets of variables encountered in the current function
- offset of next instruction ("program counter")
We store all this in a quadruple s(Code, Fs, Vs, PC). The
entry point for compilation is compile/2: It starts with a
fresh state, transforms it via compile/3 and then extracts
the accumulated instructions:
compile(Tree, Asm) :-
gen_state(S0),
compile(Tree, S0, S),
state_instrs(S, Asm).
Here are auxiliary predicates to access and transform parts of the
state:
gen_state(s([],[],[],0)).
current_pc(PC, s(Is,Fs,Vs,PC), s(Is,Fs,Vs,PC)).
emit(Code, s(Is0,Fs,Vs,PC0), s([Code|Is0],Fs,Vs,PC)) :-
length(Code, L),
PC is PC0 + L.
start_function(Name, Arg, s(Is0,Fs,_,PC0), s(Is0,[Name-PC0|Fs],[Arg-0],PC0)).
num_variables(Num, S, S) :-
S = s(_,_,Vs,_),
length(Vs, Num0),
Num is Num0 - 1. % don't count parameter
variable_offset(Name, Offset, s(Is0,Fs0,Vs0,PC0), s(Is0,Fs0,Vs,PC0)) :-
( memberchk(Name-Offset, Vs0) ->
Vs = Vs0
; Vs0 = [_-Curr|_],
Offset is Curr + 1,
Vs = [Name-Offset|Vs0]
).
state_instrs(s(Is0,Fs,_,_), Is) :-
reverse([[halt]|Is0], Is1),
resolve_calls(Is1, Fs, Is).
resolve_calls([], _, []).
resolve_calls([I0|Is0], Fs, [I|Is]) :-
( I0 = [call,Name] ->
memberchk(Name-Adr, Fs),
I = [call,Adr]
; I = I0
),
resolve_calls(Is0, Fs, Is).
For example, the predicate start_function/4 records the
offset (= current program counter) of the function to be defined
and starts a new list of encountered variables, originally
consisting only of the function's argument, whose offset (in the
stack frame) is 0. Further variables will get ascending offsets as
they are encountered. This is handled by variable_offset/4,
which either determines a variable's offset from the list of
encountered variables or, if it is new, registers it with a new
offset computed by adding one to the offset of the variable
registered previously.
We can now define compile/3:
compile(nop) --> [].
compile(print(P)) -->
compile(P),
emit([print]).
compile(sequence(A,B)) -->
compile(A),
compile(B).
compile(call(Name, Arg)) -->
compile(Arg),
emit([call,Name]).
compile(function(Name,Arg,Body)) -->
emit([jmp,Skip]),
start_function(Name, Arg),
emit([alloc,NumVars]),
compile(Body),
num_variables(NumVars),
current_pc(Skip).
compile(if(Cond,Then,Else)) -->
{ Cond = bin(Op,A,B) },
compile(A),
compile(B),
{ condition(Op, Instr) },
emit([Instr,Adr1]),
compile(Then),
emit([jmp,Adr2]),
current_pc(Adr1),
compile(Else),
current_pc(Adr2).
compile(assign(Var,Expr)) -->
variable_offset(Var, Offset),
compile(Expr),
emit([pop,Offset]).
compile(while(Cond,Body)) -->
current_pc(Head),
{ Cond = bin(Op,A,B) },
compile(A),
compile(B),
{ condition(Op, Instr) },
emit([Instr,Break]),
compile(Body),
emit([jmp,Head]),
current_pc(Break).
compile(return(Expr)) -->
compile(Expr),
emit([ret]).
compile(bin(Op,A,B)) -->
compile(A),
compile(B),
{ op_vminstr(Op,VI) },
emit([VI]).
compile(n(N)) -->
emit([pushc,N]).
compile(v(V)) -->
variable_offset(V, O),
emit([pushv,O]).
op_vminstr(+, add).
op_vminstr(-, sub).
op_vminstr(*, mul).
op_vminstr(/, div).
condition(=, jne).
condition(<, jge).
condition(>, jle).
By introducing a call_n instruction that discards
the n most recently allocated local variables before
calling a given function, we could add tail call
optimisation and, more generally, stack trimming to
the VM: If a variable isn't needed after a function call, its
stack space can be reclaimed before the call.
To keep the generated VM code compact and easily accessible in
other programming languages, we transform the mnemonic
instructions into integer code:
asm_intcode(Asm, Intcode) :-
maplist(asm_intcode_, Asm, Intcode0),
flatten(Intcode0, Intcode).
asm_intcode_([halt], [0]).
asm_intcode_([alloc,A], [1,A]).
asm_intcode_([pushc,C], [2,C]).
asm_intcode_([pushv,V], [3,V]).
asm_intcode_([pop,V], [4,V]).
asm_intcode_([add], [5]).
asm_intcode_([sub], [6]).
asm_intcode_([mul], [7]).
asm_intcode_([div], [8]).
asm_intcode_([jmp,Adr], [9,Adr]).
asm_intcode_([jne,Adr], [10,Adr]).
asm_intcode_([jge,Adr], [11,Adr]).
asm_intcode_([jle,Adr], [12,Adr]).
asm_intcode_([call,Adr], [13,Adr]).
asm_intcode_([print], [14]).
asm_intcode_([ret], [15]).
Let us now implement the VM we devised. Its state is
determined by:
- values on the stack
- list of instructions to execute
- pc: program counter (offset into list of instructions)
- fp: frame pointer (offset into stack)
Using Haskell, we can use a quadruple to represent this state:
type State = ([Int], [Int], Int, Int)
The function step, given the integer code of a VM
instruction and the VM's current state, computes and returns the
VM's new state:
step :: Int -> State -> State
step instr (stack,instrs,pc,fp) =
case instr of
1 -> ((replicate next 0) ++ stack, instrs, pc2, fp + next)
2 -> (next:stack, instrs, pc2, fp+1)
3 -> ((stack!!(fp - next)):stack, instrs, pc2, fp + 1)
4 -> (tail $ set_nth stack (fp - next) first, instrs, pc2, fp1)
5 -> ((second+first):drop2, instrs, pc1, fp1)
6 -> ((second-first):drop2, instrs, pc1, fp1)
7 -> ((second*first):drop2, instrs, pc1, fp1)
8 -> ((div second first):drop2, instrs, pc1, fp1)
9 -> (stack, instrs, next, fp)
10 -> if second /= first then (drop2, instrs, next, fp2)
else (drop2, instrs, pc2, fp2)
11 -> if second >= first then (drop2, instrs, next, fp2)
else (drop2, instrs, pc2, fp2)
12 -> if second <= first then (drop2, instrs, next, fp2)
else (drop2, instrs, pc2, fp2)
13 -> ([first,fp,pc2] ++ tail stack, instrs, next, 0)
15 -> let fp' = stack !! (fp + 1)
pc' = stack !! (fp + 2)
in
(first : drop (fp+3) stack, instrs, pc', fp')
where next = instrs !! (pc+1)
first = head stack
second = stack !! 1
drop2 = drop 2 stack
fp1 = fp - 1
fp2 = fp - 2
pc1 = pc + 1
pc2 = pc + 2
set_nth :: [a] -> Int -> a -> [a]
set_nth (x:xs) n a
| n == 0 = a:xs
| otherwise = x:(set_nth xs (n - 1) a)
We execute a list of integer codes by continually transforming
the state until a halt instruction is reached:
exec :: State -> IO ()
exec s0@(stack,instrs,pc,fp) =
let instr = instrs !! pc
in
case instr of
0 -> return ()
14 -> do putStr $ (show $ head stack) ++ "\n"
exec (tail stack, instrs, pc + 1, fp - 1)
otherwise -> exec $ step instr s0
main :: IO ()
main =
do prog <- getLine
let ints = read prog::[Int]
s0 = ([],ints,0,0)
exec s0
This code is available from here. Since we
used lists to represent the stack and set of instructions,
indexing is inefficient. To remedy this, we could use an array at
least for the set of instructions. The stack, however, needs to
grow and shrink. We could artificially fix its size, or resize on
demand, and still use a Haskell array. Instead, let us formulate
the program in a language with efficient array operations at its
core: J, a successor
of APL. In the J version (vm.ijs), we
represent the VM's state using an array of four boxed
vectors. Using the power conjunction ^:, we produce
the limit of repeated applications of step:
st =. 3 : '> 0 { y'
is =. 3 : '> 1 { y'
pc =. 3 : '> 2 { y'
fp =. 3 : '> 3 { y'
next =. (>:&pc { is)
print =. 3 : 'y (1!:2) 2'
adv =. 3 : '(2 }.st y); (is y); (2+pc y); ((fp y) - 2)'
jmp =. 3 : '(2 }.st y); (is y); (next y); ((fp y) - 2)'
i1 =: 3 : '(((next y) # 0),st y); (is; 2&+&pc; next+fp) y'
i2 =: 3 : '((next,st); is ; 2&+&pc; >:&fp) y'
i3 =: 3 : '((((fp-next) { st),st); is; 2&+&pc; >:&fp) y'
i4 =: 3 : '(}.({.st y) ((fp-next)y) } st y); (is; 2&+&pc; <:&fp) y'
i5 =: 3 : '((+/1 0 { st y),2}.st y); (is; >:&pc; <:&fp) y'
i6 =: 3 : '((-/1 0 { st y),2}.st y); (is; >:&pc; <:&fp) y'
i7 =: 3 : '((*/1 0 { st y),2}.st y); (is; >:& pc; <:&fp) y'
i8 =: 3 : '((<.%/1 0 { st y),2}.st y); (is; >:&pc; <:&fp) y'
i9 =: 3 : '(st; is; next; fp) y'
i10 =: 3 : '(adv ` jmp @. (-.=/1 0 {st y)) y'
i11 =: 3 : '(adv ` jmp @. (>:/1 0 {st y)) y'
i12 =: 3 : '(adv ` jmp @. (<:/1 0 {st y)) y'
i13 =: 3 : '(((({.&st), fp, 2&+&pc),}.& st) y); (is y); (next y);0'
i14 =: 3 : '(print {. st y)]((}.&st); is; (>:&pc); (<:&fp)) y'
i15 =: 3 : 0
fp1 =. (>:&fp { st) y
pc1 =. (2&+&fp { st) y
(({. st y),(3+fp y)}. st y) ; (is y); pc1 ; fp1
)
step =: 3 : 0
instr =. (pc { is) y
(]`i1`i2`i3`i4`i5`i6`i7`i8`i9`i10`i11`i12`i13`i14`i15 @. instr) y
)
state0 =: ($0); instrs; 0; 0
step ^: _ state0
A transcript showing how to invoke the programs is available from
here. You can
use SWI Prolog to try the
Prolog code.
Written May 15th 2006
Main page