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