Source code: alice/tuprolog/Var.java
1 /*
2 * Var.java
3 *
4 * Copyright 2000-2001 deis.unibo.it
5 *
6 * This software is the proprietary information of deis.unibo.it
7 * Use is subject to license terms.
8 *
9 */
10 package alice.tuprolog;
11
12 /**
13 * prolog variable implementation. Variable identificators are time
14 * (a long) and a name (a string). Name is used to identify the variable
15 * from the point of view of an external user, time as internal code.
16 */
17 public class Var extends Term {
18
19 // any variable
20 public static final Var ANY = new Var("_",0);
21
22
23 // the name identifying the var
24 public String name;
25
26 // time, link, mark are used for unification process */
27 int time;
28 Term link;
29 int mark;
30
31 /**
32 * creates a variable identified by name n
33 */
34 public Var(String n) throws InvalidVarNameException {
35 if (Character.isUpperCase(n.charAt(0)) || n.equals("_")){
36 id = VAR;
37 name = n;
38 time = 0;
39 link = null;
40 } else {
41 throw new InvalidVarNameException();
42 }
43 }
44
45 /**
46 * creates an ANY variable ("_")
47 */
48 public Var(){
49 id = VAR;
50 name = "_";
51 time = 0;
52 link = null;
53 }
54
55 Var(String n,int t) {
56 id = VAR;
57 name = n;
58 time = t;
59 link = null;
60 }
61
62
63 public String getName(){
64 return name;
65 }
66
67 // checking type and properties for the var
68
69 public Term getVar(String name_){
70 if (name.equals(name_)){
71 return getTerm();
72 } else {
73 return null;
74 }
75 }
76
77 /**
78 * gets the real term.
79 * <p>
80 * for unbound var it's the var itself, while
81 * for bound var it's the linked term
82 */
83 public Term getTerm() {
84 Term tt = this;
85 Term t = link;
86 while(t != null && (tt = t).id == VAR)
87 t = ((Var)t).link;
88 return(tt);
89 }
90
91 public boolean isConst() {
92 return(false);
93 }
94
95 public boolean isNum() {
96 return(false);
97 }
98
99 public boolean isCompound() {
100 return(false);
101 }
102
103 public boolean isAtom() {
104 return(false);
105 }
106
107 public boolean isClause() {
108 return(false);
109 }
110
111 public boolean isList() {
112 return(false);
113 }
114
115 public boolean isEmptyList() {
116 return(false);
117 }
118
119 public boolean isGround(){
120 Term t=getTerm();
121 if (t==this){
122 return false;
123 } else {
124 return t.isGround();
125 }
126 }
127
128 public boolean isAny(){
129 return (link==null) && name.equals("_");
130 }
131
132 /**
133 * finds a var Term of the list with the same time
134 * of current Term.
135 */
136 private Var findIn(alice.util.LinkedList vl) {
137 while(!vl.isEmptyList()) {
138 if(time == ((Var)vl.head).time)
139 return((Var)vl.head);
140 vl = vl.tail;
141 }
142 return(null);
143 }
144
145 /**
146 * finds a var Term of the list with the same Name
147 * of current Term.
148 */
149 public Var findFromNameIn(alice.util.LinkedList vl) {
150 String na=name;
151 if (na==null)
152 na="_" + String.valueOf(time);
153 while(!vl.isEmptyList()) {
154 if(na.equals(((Var)vl.head).name))
155 return((Var)vl.head);
156 vl = vl.tail;
157 }
158 return(null);
159 }
160
161 /**
162 * finds var occurence in a Struct, doing occur-check.
163 */
164 private boolean findIn(Struct t) {
165 for(int c = 0;c < t.arity;c++) {
166 Term at = t.arg[c].getTerm();
167 switch(at.id) {
168 case NULL:
169 break;
170 case VAR:
171 if(time == ((Var)at).time)
172 return(true);
173 break;
174 case INT:
175 case FLOAT:
176 break;
177 case STRUCT:
178 if(findIn((Struct)at))
179 return(true);
180 break;
181 }
182 }
183 return(false);
184 }
185
186
187 int renameVars(alice.util.LinkedList vars,int count){
188 Term tt=getTerm();
189 if (tt==this){
190 if (name==null){
191 time=count++;
192 } else if (name.equals("_")){
193 time=count++;
194 } else {
195 Var found=findFromNameIn(vars);
196 if (found!=null) {
197 time=found.time;
198 } else {
199 time=count++;
200 vars.append(this);
201 }
202 }
203 return count;
204 } else {
205 return tt.renameVars(vars,count);
206 }
207 }
208
209 /**
210 * renaming of all the variables of the argument list.
211 */
212 public static int rename(alice.util.LinkedList vl,int c,boolean f) {
213 while(!vl.isEmptyList()) {
214 if (f){
215 ((Var)vl.head).name = null;
216 }
217 ((Var)vl.head).time = c++;
218 vl = vl.tail;
219 }
220 return(c);
221 }
222
223
224 /**
225 * var unification.
226 * <p>
227 * First, verify the Term eventually already unified with the same Var
228 * if the Term exist, unify var with that term, in order to handle situation
229 * as (A = p(X) , A = p(1)) which must produce X/1.
230 * <p>
231 * If instead the var is not already unified, then:
232 * <p>
233 * if the Term is a var bound to X, then try unification with X
234 * so for example if A=1, B=A then B is unified to 1 and not to A
235 * (note that it's coherent with chronological backtracking:
236 * the eventually backtracked A unification is always after
237 * backtracking of B unification.
238 * <p>
239 * if are the same Var, unification must succeed, but without any new
240 * bindings (to avoid cycles for extends in A = B, B = A)
241 * <p>
242 * if the term is a number, then it's a success and new link is created
243 * (retractable by means of a code)
244 * <p>
245 * if the term is a compound, then occur check test is executed:
246 * the var must not appear in the compound ( avoid X=p(X),
247 * or p(X,X)=p(Y,f(Y)) ); if occur check is ok
248 * then it's success and a new link is created (retractable by a code)
249 */
250 public boolean unify(Term t,int m) {
251 Term tt = getTerm();
252 if(tt == this) {
253 t = t.getTerm();
254 switch(t.id) {
255 case NULL:
256 return(false);
257 case VAR:
258 if(time == ((Var)t).time)
259 return(true);
260 break;
261 case INT:
262 case FLOAT:
263 break;
264 case STRUCT:
265 if(findIn((Struct)t))
266 return(false);
267 break;
268 case OBJECT:
269 break;
270 }
271 link = t;
272 mark = m;
273 return(true);
274 }
275 else {
276 return(tt.unify(t,m));
277 }
278 }
279
280 public boolean match(Term t) {
281 Term tt = getTerm();
282 if(tt == this) {
283 t = t.getTerm();
284 switch(t.id) {
285 case NULL:
286 return(false);
287 case VAR:
288 if(time == ((Var)t).time)
289 return(true);
290 break;
291 case INT:
292 case FLOAT:
293 break;
294 case STRUCT:
295 if(findIn((Struct)t))
296 return(false);
297 break;
298 case OBJECT:
299 break;
300 }
301 return(true);
302 } else {
303 return(tt.match(t));
304 }
305 }
306
307 /**
308 * ununification by means of the code m
309 * (only link with code greater or equal than m are free)
310 */
311 public void free(int m) {
312 if(link != null) {
313 link.free(m);
314 if(mark >= m)
315 link = null;
316 }
317 }
318
319 /**
320 * unlinks linked var.
321 * <p>
322 * (not used by prolog core; only for extension and not prolog manipulation )
323 */
324 public void unlink(){
325 link=null;
326 }
327
328 /**
329 * copying a var.
330 * <p>
331 * if bound var then copying of the term linked, else
332 * the list passed as arg are variables already linked, so <p>
333 * if current var is founded in the list, then the copy of the var
334 * is the element of the list; if not, then a new copy is made and
335 * the is var added to the list
336 */
337 public Term copy(alice.util.LinkedList vl) {
338 Term tt = getTerm();
339 if(tt == this) {
340 Var v = findIn(vl);
341 if(v == null) {
342 v = new Var(name,time);
343 vl.insert(v);
344 }
345 return(v);
346 } else {
347 return(tt.copy(vl));
348 }
349 }
350
351 // comparison and sorting - sorting based on creation (time) time (no lexical soring)
352
353 public boolean isGT(Term t) {
354 Term tt = getTerm();
355 if(tt == this) {
356 t = t.getTerm();
357 return(id > t.id || (id == t.id && time > ((Var)t).time));
358 }
359 else
360 return(tt.isGT(t));
361 }
362
363 public boolean isEQU(Term t) {
364 Term tt = getTerm();
365 if(tt == this) {
366 t = t.getTerm();
367 return(id == t.id && time == ((Var)t).time);
368 }
369 else
370 return(tt.isEQU(t));
371 }
372
373 /**
374 * gets string representation of the var.
375 * <p>
376 * if var bounded, then write Name/Term; else
377 * if there is no name, write underscore character
378 */
379 public String toString() {
380 Term tt = getTerm();
381 if (name != null){
382 if(tt == this){
383 return(name);
384 }
385 else {
386 return(name + " / " + tt.toString());
387 }
388 } else {
389 if(tt == this){
390 if(time < 0){
391 return("_" + String.valueOf(time + Integer.MIN_VALUE));
392 } else {
393 return("_" + String.valueOf(time));
394 }
395 } else {
396 return(tt.toString());
397 }
398 }
399 }
400
401 /**
402 * get the flat string representation of a variable.
403 * <p>
404 * if var bounded, then get the string representation of the Term bound
405 */
406 public String toStringFlattened() {
407 Term tt = getTerm();
408 if(name != null){
409 if(tt == this){
410 return(name);
411 } else {
412 return(tt.toString());
413 }
414 } else {
415 if(tt == this){
416 return("_");
417 } else {
418 return(tt.toString());
419 }
420 }
421 }
422 }