johnl@ima.UUCP (Compilers mailing list) (05/13/86)
[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.
----------------------------
Send-date: Wednesday, April 16, 1986 at 12:17 PST
Really-from: Peter Ludemann <ludemann@cs.ubc.cdn>
Subject: Parsers in Prolog
A request was made recently about parsers in Prolog. One of the
better articles is:
Warren, D.H.D.: _Logic Programming and Compiler Writing_
in "Software - Practice and Experince vol 10, 1980.
There is also a forthcoming paper at the 3rd International
Logic Programming Conference, entitled "Deterministic Logic Grammars"
by H. Abramson. It has some discussion of DCTGs and LL(k) and LR(k)
grammars.
Incidentally, I found that I could do quite a bit with the description
in Clocksin&Mellish.
--
Send compilers mail to ima!compilers or, in a pinch to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbncca}!ima
Send meta-mail to ima!compilers-request