-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathprolog_translate.pro
162 lines (134 loc) · 6.02 KB
/
prolog_translate.pro
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
:- module(prolog_translate, [
clause_mgh/2,
clausehead_mgu/3,
mghclause_disjunct/3,
mghclauses_disjunct/2,
pred_dnfclause/2,
pred_mghclause/2,
pred_mghclauses/2,
foo/1
]).
:- use_module(library(error)).
:- use_module('./language_prolog.pro').
/** <module> Prolog program analysis?
Note:
Do not use.
Most of this file has been superseded by the file language_prolog.pro.
In this document:
- "To explicate" means "to make explicit".
- A "predicate indicator" is a Name/Arity where Name is an atom and Arity is a nonnegative integer.
- DNF stands for "disjunctive normal form".
- "mgh" stands for "most general head".
The transformation steps:
- Normalize to DNF: convenience predicate pred_dnfclause/2.
- Enumerate the clauses of a predicate: builtin clause/2 and findall/3.
- Maximally generalize each clause head: clause_mgh/2.
- Collect explicated clauses: pred_mghclauses/2, pred_mghclause/2.
- Join the explicated clauses into one DNF clause: mghclauses_disjunct/2.
- Analyze determinacy: det (always true without choice points), semidet (true at most once), nondet.
- Translate a det predicate to a function.
- Translate to abstract procedural language.
- Translate unification.
- Each variable _refers_ to a _location_ (an _lvalue_ in C parlance, a _place_ in Lisp parlance).
- Unifying two variables creates (allocates) a new location and sets those variables to point to this new shared location.
- Unifying a variable and a value (ground term) puts the value in the location.
- Unifying two values compares the terms.
- Failure destroys (frees/deallocates) all locations allocated while the code was in the frame.
- Destroying a frame destroys all location allocated in that frame and restores all variables set in that frame.
- Deduplicate atoms to integers.
Emit atom table.
Assume that the program does not create atoms.
The atom table is constant.
- Main (entry point) is a query.
- Are there alternatives to WAM? https://en.wikipedia.org/wiki/Warren_Abstract_Machine
- Predicate argument groundness analysis:
- If argument A is always ground on predicate entry,
then A can be replaced with a unidirectional C input argument.
- If the predicate always grounds the argument A on exit,
then A can be replaced with a unidirectional C output argument.
(pointer to caller-allocated memory).
- A nondet Prolog predicate is essentially a C iterator.
Representing a term:
- An atom is represented by a 16-bit unsigned integer that is a key in the atom table.
Atom comparison is integer comparison.
The atom table is constant.
The program cannot create new atoms at runtime; use strings for that.
- A compound term is represented by (Name,Arity,Arg1,...,ArgN) where Name is an atom, Arity is a 16-bit unsigned integer.
- A string is represented by (Limit,Length,Bytes) where Limit takes 4 bytes, Length takes 4 bytes, and Bytes is the contents of the string.
Creating a choice point is similar to installing an exception handler.
Failing (backtracking) is similar to throwing an exception and unwinding the stack.
A predicate with N parameters may compile to at most 2^N routines.
If we know that a variable is ground when we enter a predicate,
we can optimize it.
```
% This translates to two routines: p_g, p_u
p(0).
p(1).
p(A) :- A >= 5.
% This translates to four routines: b_gg, b_gu, b_ug, b_uu
b(1,0).
b(2,1).
b(A,B) :- A =< B.
% proc1 calls p_g.
proc1 :- p(0), write(hi).
% proc2 calls p_u.
% If proc2 gets inlined, it may call p_g, depending on context.
proc2(A) :- p(A).
```
We want frames (delimited continuations) (shift+reset) for cuts.
Prolog should use three-valued logic with three truth values: true, unknown, and false.
"A \= B" should be unknown, not false.
Three-valued logic simplifies constraint logic programming?
Prolog should use Kleene's "strong logic of indeterminacy" or Priest's "logic of paradoxes"?
- https://en.wikipedia.org/wiki/Three-valued_logic
Supporting built-ins:
- =../2 converts a functor to a representation that is less efficient but more manipulable.
- portray_clause/2 for pretty-printing
Problems:
- This does not work with modules.
Literature:
- "?-Prolog compiles a single Prolog source file into C"
http://www.call-with-current-continuation.org/prolog/README.html
- 1992
"Use of Prolog for developing a new programming language"
"This paper describes how Prolog was used for the development of a new concurrent realtime symbolic programming language called Erlang."
https://pdfs.semanticscholar.org/57d3/1ca47fa9688089b9b7e7c19c199aa03aff1e.pdf
*/
foo(a).
foo(b).
foo(A) :- integer(A), !.
/** pred_dnfclause(++Indicator, -Dnf)
"Dnf is a disjunctive normal form clause that is equivalent to the predicate described by Indicator."
Indicator is Name/Arity.
*/
pred_dnfclause(Ind, Dnf) :-
pred_mghclauses(Ind, Ecls),
mghclauses_disjunct(Ecls, Dnf).
/**
pred_mghclause(++NameArity, -Clause).
pred_mghclauses(++NameArity, -Clauses).
Clause is =|Head :- Body|=.
Clauses is a list of Clause.
*/
pred_mghclause(Ind, Clause) :-
Ind = Name/Arity,
pred_must_exist(Ind),
functor(Head, Name, Arity),
clause(Head, Body),
clause_mgh((Head :- Body), Clause).
pred_must_exist(Ind) :-
(pred_exists(Ind) -> true
; throw(error(unknown_predicate(Ind), _))
).
pred_exists(Name/Arity) :-
functor(Head, Name, Arity),
predicate_property(Head, visible).
prolog:error_message(unknown_predicate(Ind)) -->
['predicate ~p does not exist, or contains typo, or is not loaded, or is autoloadable but not loaded'-[Ind]].
pred_mghclauses(Ind, Cls) :-
findall(Cl, pred_mghclause(Ind, Cl), Cls).
mghclause_disjunct((Head :- Body1), (Head :- Body2), (Head :- (Body1 ; Body2))).
mghclauses_disjunct([C], C) :- !.
mghclauses_disjunct([C|Cs], D) :-
mghclauses_disjunct(Cs,Ds),
mghclause_disjunct(C,Ds,D).