Language Design (data types), also Parsers in Prolog

[I sent these out just before ima died, but am reposting them since I'm
not sure whether they got very far. -John]


In Prolog, abstract data types are already available. I'll
illustrate with an example: lists.


list([]).
list([Hd|Tl]) :- list(Tl).


This is the usual recursive definition of a list. The predicate
"list" succeeds if its argument is a proper list.


Now, take the usual "append":


append([], X, X).
append([X|A], B, [X|C]) :- append(A, B, C).


and annotate it with data type definitions:


append(L1, L2, L3) :- list(L1), list(L2), list(L3),
((L1 = [], L2 = L3) ; % "or"
(L1 = [X|A], L3 = [X|C], append(A, L2, C)).


Admittedly, the syntax is clumsy (it could easily be cleaned up), but
it does handle the abstract data type nicely. We could define a
parameterised list type:


tList([], Type).
tList([Hd|Tl], Type) :- Type(Hd), tList(Tl, Type).


and so on ("Type" is another type definition predicate, of course).


Now, if the Prolog compiler is told that "list" is a data type
definition, it can staticly check that all uses of "list" are valid,
so that run-time uses of "list" are only needed where the arguments
are of some more universal type (run time errors could also be
generated instead of just failing as in standard Prolog).


This method could be extended to more standard programming languages
by using boolean functions for type checking. The compiler would
attempt to interpret the type checking functions at compile time to
avoid as much run-time checking as possible.




----------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.