Language Design (data types)

johnl@ima.UUCP (Compilers moderator)
11 Apr 86 16:35:45 GMT

          From comp.compilers

Related articles
Language Design (data types) johnl@ima.UUCP (1986-04-11)
| List of all articles for this month |

Relay-Version: version B 2.10.2 9/12/84; site mit-prep.ARPA
Posting-Version: version B 2.10.2 9/18/84; site ima.UUCP
From: johnl@ima.UUCP (Compilers moderator)
Newsgroups: mod.compilers
Date: 11 Apr 86 16:35:45 GMT
Article-I.D.: ima.190
Posted: Fri Apr 11 11:35:45 1986
Date-Received: 12 Apr 86 12:19:59 GMT
Originally-from: Peter Ludemann <ihnp4!alberta!ubc-vision!cs.ubc.cdn!ludemann>

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

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

Post a followup to this message

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