/
halt_assembler.pl
105 lines (92 loc) · 3.62 KB
/
halt_assembler.pl
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
:- module(halt_assembler, [execute/1]).
:- use_module(halt_machine).
:- op(700, xfy, :=).
/** <module> Assembler
*
* Given a sequence of machine instructions, perform them on the raw machine.
*
* @author Daniel Lyons
* @license MIT
*/
% The table of operations
spec(and(A,B)) :- m(A) := m(A) /\ m(B).
spec(or(A,B)) :- m(A) := m(A) \/ m(B).
spec(exclusive_or(A,B)) :- m(A) := m(A) xor m(B).
spec(not(A)) :- m(A) := \ m(A).
spec(move(A,B)) :- m(A) := m(B).
spec(set(A,C)) :- m(A) := C.
spec(random(A)) :- m(A) := random.
spec(jump(X)) :- ip := X.
spec(jump_if_zero(X,A)) :- (m(A) = 0) -> ip := X ; advance.
spec(halt) :- halted := true.
% Basic operations
evaluate(M, m(A), V) :- get_register(M, A, V).
evaluate(M, A /\ B, V) :- evaluate(M, A, RA), evaluate(M, B, RB),
V is RA /\ RB.
evaluate(M, A \/ B, V) :- evaluate(M, A, RA), evaluate(M, B, RB),
V is RA \/ RB.
evaluate(M, A xor B, V) :- evaluate(M, A, RA), evaluate(M, B, RB),
V is RA xor RB.
evaluate(M, \ A, V) :- evaluate(M, A, RA), V is \ RA.
evaluate(M, A -> B ; C, V) :- evaluate(M, A, RA),
RA -> evaluate(M, B, V) ; evaluate(M, C, V).
evaluate(M, m(A) := B, V) :- evaluate(M, B, RB), set_register(M, A, RB, V).
evaluate(_, A, A) :- number(A).
evaluate(_, random, V) :- V is random(2).
evaluate(M, advance, V) :- advance(M, V).
evaluate(M, A = B, V) :- evaluate(M, A, RA), evaluate(M, B, RB),
RA = RB -> V = true ; V = false.
% Special cases
evaluate(M, ip := X, MA) :- set_instruction_pointer(M, X, MA).
evaluate(M, halted := true, MA) :- set_halted(M, MA).
% Perform the specification
evaluate(M, X, V) :-
clause(spec(X), Body), evaluate(M, Body, V).
/** execute(+Code:[instruction]) is det.
*
* Executes the sequence of assembler instructions, printing either
* 'Program halts!' if the machine halts or runs out of
* instructions, otherwise printing 'Unable to determine if
* application halts' if we hit the 10,000th instruction without
* halting.
*/
execute(Code) :- execute(Code, _).
/** execute(+Code, -FinalMachine) is det.
*
* Execute Code as a sequence of assembler instructions, unifying
* the final state of the machine with FinalMachine.
*/
execute(Code, FinalMachine) :-
initialize(Code, InitialMachine),
execute_loop(InitialMachine, FinalMachine).
% Executes a single instruction, then determine if we should loop or
% not, looping if so.
execute_loop(Machine0, MachineN) :-
execute_one(Machine0, Machine1),
%% if we're halted, display the message; otherwise continue
((is_halted(Machine1) ; instruction_count(Machine1, 10000))
-> do_halt(Machine1)
; execute_loop(Machine1, MachineN)).
/** execute_one(+InputMachine, -OutputMachine) is semidet.
*
* Executes one instruction.
*/
execute_one(Machine0, Machine1) :-
%% fetch the next instruction
next_instruction(Machine0, Inst),
%% evaluate it
evaluate(Machine0, Inst, Machine1).
/** do_halt(+Machine) is det.
*
* Determine whether halt was artificial or natural and write to
* standard output accordingly.
*/
do_halt(machine(_, _, _, _, true)) :-
write('Program halts!'), nl.
do_halt(machine(Code, _, _, IP, _)) :-
length(Code, CodeLength), CodeLength =< IP,
write('Program halts!'), nl.
do_halt(machine(_, 10000, _, _, _)) :-
write('Unable to determine if application halts.'), nl.
do_halt(_) :-
write('Unable to determine if application halts (possible bug).'), nl.