Language Design (data types)

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 definieiont 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.
--
-----------------------------------------------------------------------------
Send submissions to: ima!compilers


ima is reachable as { ucbvax!cbosgd | ihnp4 | cca | bbncca | think |
uiucdcs | allegra | inmet | yale | harvard }!ima!...
Arpa mail may make it to ima!compilers@CCA-UNIX or ima!compilers@BBNCCA

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