[Next] [Up] [Previous] [Contents]
Next: Definitions Up: Tutorial Previous: Defining New Types   Contents

Predicates

Now let's define a simple predicate on $ \lambda$-terms: enumerating a list containing all free variables (though possibly with duplicates). Put the following in tutorial.apl:

pred fvs (exp,[var]).
fvs(var(v),[v]).
fvs(app(E1,E2),L) :- fvs(E1,L1),fvs(E2,L2),append(L1,L2,L).
fvs(lam(x\E),L) :- fvs(E,L'), remove(x,L',L).
Note that we use the list library function to remove (all occurrences of) "x" from the list in the third case.

Fire up $ \alpha $Prolog again and try a few queries.

?- fvs(lam (x\var x),X).
Yes.
X = [] 
?- fvs(lam (x\var y),X).
Yes.
X = [y] 
?- fvs(app (var y) (var y),X).
Yes.
X = [y,y]
Note that duplicate names in the term result in duplicate list entries.



James Cheney 2003-10-23