arman@oahu.cs.ucla.edu (Arman Bostani) (09/22/89)
I am looking references to any work done in the area of "compiling" logic programming languages (i.e. Prolog, CLP(R), etc.) into a procedural/deterministic language such as C. I, myself, have written a compiler from LOG(F) (functional programming language, related to prolog) to a variant of C, but I have seen very little published work in this area. Thanks for the help, -arman. -- Arman Bostani // UCLA Computer Science Department -- arman@CS.UCLA.EDU // ...!(ucbvax,rutgers)!ucla-cs!arman
bradley@cs.utexas.edu (Bradley L. Richards) (09/23/89)
As far as I'm aware, little work *has* been done in this area (although Borland's highly successful Turbo Prolog is compiled to machine code). One big reason, at least with Prolog, that little work has been done is that you almost inevitably sacrifice one of the most important and distinctive features of the language when you compile it: the ability to have a program change its universe while running (assert/retract). Brad
ok@cs.mu.oz.au (Richard O'Keefe) (09/23/89)
In article <869@gamera.cs.utexas.edu>, bradley@cs.utexas.edu (Bradley L. Richards) writes: > As far as I'm aware, little work *has* been done in this area The first paper I saw on the subject was Chris Mellish's paper about the Prolog component of PopLog. I've seen several others since (alas, my library is in two other countries at the moment, so no reference) and they mostly follow his approach. Ignoring arguments, p :- built-in-test. p :- q. p :- r, s. is compiled as a function with a continuation argument: if it succeeds it calls its continuation; if it fails it returns. define p(Continuation); if built-in-test then call(Continuation); endif; q(Continuation); r(lambda (). s(Continuation endlambda); ;; fail by returning enddefine; The top-level predicate is called with a continuation which prints the variable bindings and then either returns (if the user types ";") or longjumps all the way out (if the user types <CR>). I don't remember how cuts are handled. In a language like C which doesn't let you construct closures (lambda ... endlambda) you can get the same effect by pushing information on a "continuation stack". There are actually some similarities between this method and David Warren's "total non-structure-sharing".
axaris@cs.buffalo.edu (Vassilios Axaris) (09/25/89)
Hello, I have been surprized when I first got my Turbo Prolog compiler, in that I was required to specify the type of objects being used. Later, I realized that even though this was putting a burden on the programmer, as well as deviating from the standard, it could be (as it was I believe) useful in minimizing the runtime type checking of the objects, in Common Lisp manner. In today's RISC world, I think it would be very useful to include such declarations to aid the compiler in creating efficient code, by minimizing tag processing. How does the Prolog community feel about such an addition? Is it reasonable to do it for the sake of improved execution speed on workstation type environments? Vassilios E. Axaris SUNY/Buffalo Computer Engineering
ok@cs.mu.oz.au (Richard O'Keefe) (09/25/89)
In article <10822@eerie.acsu.Buffalo.EDU>, axaris@cs.buffalo.edu (Vassilios Axaris) writes: > I have been surprized when I first got my Turbo Prolog compiler, in that I was > required to specify the type of objects being used. In short, you were surprised to discover that what you got was NOT a Prolog compiler, but a compiler for another (closely related, but still OTHER) language. Whenever I hear that someone is thinking of getting Turbo Prolog, I tell them to look first at Trilogy. If you are willing to use a sort of Prolog/Pascal hybrid (Turbo Prolog), you ought to be happy with a logic programming language which is not a Prolog/Pascal hybrid but was designed from the start to let you do the kinds of things that Pascal is good for in a clean logic programming way. I have a copy of Trilogy, and while it's somewhere between two other countries at the moment, I was favourably impressed by it, and would prefer Trilogy to Turbo any day of the week. > Later, I realized that even > though this was putting a burden on the programmer, as well as deviating from > the standard, it could be (as it was I believe) useful in minimizing the runtime > type checking of the objects, in Common Lisp manner. You should be aware that there are Prolog systems for the PC which can run rings around Turbo Prolog, *without* sacrificing compatibility. I'll let the vendors tell you which ones. Basically, "run time type checking" is a red herring for Prolog. Consider something like append([], L, L). append([H|T], L, [H|R]) :- append(T, L, R). In Pascal terms, this would be type listPtr = ^listRrec; listTag = (kNil, kCons); listRec = record case tag: listTag of kNil: (); kCons: (head: something; tail: listPtr); end {listRec}; function append(A, Z: listPtr): listPtr; begin case A^.tag of kNil: append := Z; kCons: append := mkCons(A^.head, append(A^.tail, L)); end {case}; end {append}; The 'case' statement in the Pascal program is the equivalent of the 'indexing' done in Prolog. No amount of type checking at compile time is going to eliminate that 'case' statement. But that's where the "run-time type checking" is happening in the Prolog system. To be sure, tagging does slow arithmetic down. Static typing can help there, *IF* you also have strict mode checking as well. However, if arithmetic is more than say 30% of the cost of your Prolog program, you aren't doing things the Prolog Way. Lisp needs types much worse than Prolog, because the Lisp equivalent of append/3 would be (defun app (A Z) (if (endp A) ; check A Z (cons (car A) ; check A again (app (cdr A) ; check A again Z)))) where A gets checked three times. In the code produced by a good Prolog compiler, this effectively happens just once, and is ``paid for'' by the `if'. See Author: David H.D. Warren, Luis M. Pereira Title: Prolog: the language and its implementation compared with Lisp Journal: Proceedings of the Symposium on Artificial Intelligence and Programming Languages City: University of Rochester Date: August 1977 Pages: 109-115 Other: published as SIGPLAN Notices 12:8 and as SIGART Newsletter 64 > In today's RISC world, I > think it would be very useful to include such declarations to aid the compiler > in creating efficient code, by minimizing tag processing. Hang on a minute, Turbo Prolog runs on 80*86s, which aren't RISCs... Real Prologs (as opposed to Turbo[*] Prologs) let you pass variables around in a way which requires run-time tests ANYWAY in order to tell whether a variable is instantiated or not; given that, any other tag checking that may be required comes free. Advanced Prologs (SICStus Prolog, NU Prolog, I believe ECRC though I haven't tried it, CHIP, CLP(-)) allow variables to be ``constrained'', which also requires run-time checks in the course of which other tag checks come free. [*] ``Turbo'' is a Latin word meaning ``I swirl [things] around, make [things] confused.'' A ``turba'' is a mob. > How does the Prolog community feel about such an addition? Is it reasonable to > do it for the sake of improved execution speed on workstation type environments? Today's good Prolog compilers on today's workstations already produce fast code, to the point where you might write C or Fortran code for number- crunching or interfacing to existing libraries, but would not be tempted to rewrite your program as such in C. (Unless you have written very bad Prolog code.) Don't make the mistake of thinking that types are necessary for efficiency: BCPL, BLISS, and many other systems programming languages are not typed. However, type checking *IS* useful for detecting mistakes in programs, and types are useful when designing a program. As far as I know, Bruynooghe was the first to write about types in Prolog. But there is a large and growing literature on type checking and type inference in logic programs. The NU Prolog Debugging Environment (spelled NUDE, apparently pronounced `nood') includes a rather powerful type checker. The source code of the Mycroft & O'Keefe type checker was posted to this news group a year or so ago. [Sorry, playmates, but there is a mistake in it. It treats disjunctions as if they were conjunctions. This usually doesn't matter, but occasionally it will reject a disjunction which is in fact well typed.]
picart@irisa.irisa.fr (Marc Picart) (09/25/89)
In article <10822@eerie.acsu.Buffalo.EDU>, axaris@cs.buffalo.edu (Vassilios Axaris) writes: > > Hello, > > I have been surprized when I first got my Turbo Prolog compiler, in that I was > required to specify the type of objects being used. Later, I realized that even > though this was putting a burden on the programmer, as well as deviating from > the standard, it could be (as it was I believe) useful in minimizing the runtime > type checking of the objects, in Common Lisp manner. In today's RISC world, I > think it would be very useful to include such declarations to aid the compiler > in creating efficient code, by minimizing tag processing. > How does the Prolog community feel about such an addition? Is it reasonable to > do it for the sake of improved execution speed on workstation type environments? > > Vassilios E. Axaris My opinion is that the compiler can infere a lot of the declarations by itself. (you can see the work of C. S. Mellish or S. K. Debray) I don't think that, in logic programming, it is necessary for the programmer to help the compiler. The reason is that the aim with high level languages, such as Prolog, is to separate the logic specification, which is the responsability of the programmer, from the implementation which is the responsability of the compiler. Marc Picart.
david@indetech.com (David Kuder) (09/26/89)
In article <27335@shemp.CS.UCLA.EDU> arman@oahu.cs.ucla.edu (Arman Bostani) writes: >I am looking references to any work done in the area of "compiling" >logic programming languages (i.e. Prolog, CLP(R), etc.) into a >procedural/deterministic language such as C. I know of no references to such work. I know of at least one system that tried to compile. I believe that many of the commercial Prolog vendors do compilation. BIM is perhaps the most thorough, but I'm sure Quintus will correct me if I'm wrong. In article <869@gamera.cs.utexas.edu> bradley@cs.utexas.edu (Bradley L. Richards) writes: >As far as I'm aware, little work *has* been done in this area >(although Borland's highly successful Turbo Prolog is compiled to >machine code). On soapbox, I say: Turbo Prolog isn't Prolog! They decided to compile by stripping the guts out of unification among other things. Don't consider them the typical case of compiling Prolog. >One big reason, at least with Prolog, that little work has been done >is that you almost inevitably sacrifice one of the most important and >distinctive features of the language when you compile it: the ability >to have a program change its universe while running (assert/retract). Right. Also there are the predicates that involve running other predicates: call, setof, etc. Since you can build an arbitrary predicate to be run you need to compile in the interpreter. So you can solve the assert/retract by simply always interpreting those clauses. Or you can compile the compiler into every executable. Turns out that assert and compile aren't necessarily all that different in some implementations. Still even with that savings binaries are enormous. -- David A. Kuder david@indetech.com 415 438-2003 {sun,sharkey,pacbell}!indetech!david
garym@ulysses.UUCP (Gary Murphy) (09/26/89)
There is one alternative half-way between a compiled and an
interpreted form. In SB-Prolog, the source files are 'compiled'
to a bytestream of instructions for the Warren Abstract Machine (WAM),
which allows SBP to store compact, pre-compiled and dynamically loaded
predicates. Although not as fast as a true compiler, it performs
much better than a straight interpreter.
There is yet another alternative: wasn't there a posting a while ago
gloating over a prolog-based cpu? That's the one _I_ want! :-)
--
Gary Murphy - Cognos Incorporated - (613) 738-1338 x5537
3755 Riverside Dr - P.O. Box 9707 - Ottawa Ont - CANADA K1G 3N3
e-mail: decvax!utzoo!dciem!nrcaer!cognos!garym
Cosmic Irreversibility: 1 pot T -> 1 pot P, 1 pot P /-> 1 pot Tlee@munnari.oz.au (Lee Naish) (09/27/89)
In article <1503@irisa.irisa.fr> picart@irisa.irisa.fr (Marc Picart) writes: >to separate the logic specification, which is the responsability of the >programmer, from the implementation which is the responsability of >the compiler. I agree with Jose Alberto, that types can be part of the specification (even if they are missing from the program). For example, in the natural specification of append, all arguments are lists. This information is missing in the program. Check out the following reference if you are interested (unfortunately it has some technical errors - I'll produce a revised version some day hopefully). %A Lee Naish %T Specification = program + types %J Proceedings of 7th Conference on Foundations of Software Technology and Theoretical Computer Science %C Pune, India %D December, 1987 %O Published in LNCS 287 by Springer Verlag I would also like to make some comments about Richard O'Keefe's remarks concerning complexity. Obviously complexity is an important issue. It is of vital importance when type checking is always done (eg, in a strictly typed language or with a smart Prolog compiler which attempts to infer types to improve efficiency). However, if a type checker is used simply as a programming aid to locate (some) bugs, then complexity is less important. It is possible to have a very useful debugging tool whose complexty is exponential in the worst case (the Mycroft O'Keefe type checker is a case in point). If I had a linear complexity type checker which failed to find the bug in my program, I would certainly resort to a worst case non-linear complexity type checker which might find the bug (even if I had to put the job in background, and maybe kill it when the paging on my Sun 3/50 got too bad:-). The great thing about finding bugs by static analysis is that no programmer intervention is required. lee
micha@ecrcvax.UUCP (Micha Meier) (09/27/89)
In article <27335@shemp.CS.UCLA.EDU> arman@oahu.cs.ucla.edu (Arman Bostani) writes: > >I am looking references to any work done in the area of "compiling" >logic programming languages (i.e. Prolog, CLP(R), etc.) into a >procedural/deterministic language such as C. There is an article "A Piggy-back Compiler For Prolog" by J.L.Weiner and S.Ramakrishnan in SIGPLAN'88 about a Prolog compiler that compiles into C. The authors claim that they got reasonable performance and portability. Since I've done similar work with ECRC-Prolog, I can say that a Prolog compiler that generates C is extremely user-unfriendly and can never achieve the speed of a good WAM emulator without serious portability flaws. There has been another note about a Prolog compiler into C, Proteus Prolog from MCC, where a very high speed was obtained with some slight modifications in the C compiler. Our experience with generating C was interesting in that it showed us that it is not the way to go, although it has some advantages. Shortly, the main problems vere space and time :-). The compiler either generates huge amounts of C code (if every WAM instruction is expanded) or it uses some sort of threaded code or subroutine calls which both need some code in assembler or modifications in the C compiler if they have to be efficient. This actually loses the portability leaving no other major advantage. Compilation time was the other main problem; if the compiler is written in Prolog, it is slow enough, but it is still nothing compared to the speed of the C compilation. The point is that there is much unnecessary work done in the C compiler, because the Prolog compiler generates only a very small subset of C, the same holds for the assembly code generated by the C compiler. The 'normal' approach, i.e. Prolog compiler generating abstract WAM code and possibly a native code back-end generator achieve much better (orders of magnitude) compilation speed. For example, with our current system, SEPIA, we can compile programs about 1000 times faster than with ECRC-Prolog and the speed of the generated code is better in SEPIA. If the aim is just to compile a Prolog program into an equivalent (and readable) C program, it is a different matter which, I think, can be theoretically achieved. The main task is to implement the backtracking which can be done in the Poplog way, or using continuations in the WAM way, (i.e. either return on success or return on failure), however such a program cannot achieve performances comparable with the up-to-date Prolog systems. --Micha
debray@arizona.edu (Saumya K. Debray) (09/27/89)
arman@oahu.cs.ucla.edu (Arman Bostani) writes: > I am looking references to any work done in the area of "compiling" > logic programming languages (i.e. Prolog, CLP(R), etc.) into a > procedural/deterministic language such as C. See D. H. D. Warren's original work on compiling Prolog: "Implementing Prolog -- compiling predicate logic programs", DAI Research Reports 39 and 40, U. Edinburgh, May 1977. [This is hard to get from Edinburgh, but I've heard that it's available as a research report from SRI International.] There's a bunch of papers on implementing Prolog in Lisp, e.g. see the paper by Ken Kahn and Mats Carlsson in "Implementations of Prolog", ed. J. A. Campbell, Ellis Horwood, 1984. Andrew Turk discusses a number of optimizatios for native code Prolog compilers in Proc. ICLP 86. Mike Newton discusses compiling Prolog into native code for an IBM-3090 in "A High Performance Implementation of Prolog", Caltech CS Dept. Tech. Report TR:5234:86, Apr. 1987. There is also a paper in SIGPLAN-88, by Weiner and Ramakrishnan, that discusses compilation to C. See SIGPLAN Notices vol. 23 no. 7, July 1988. [This paper makes rather strong assumptions about the program, e.g. about the availability of type information, and hence may not satisfy purists.] There is at least one "real" Prolog implementation I'm aware of that compile to native code: BIM-Prolog, from Belgium; I believe Sicstus Prolog, from Sweden, also has a native code compiler for 68020-based machines. bradley@cs.utexas.edu (Bradley L. Richards) writes: > As far as I'm aware, little work *has* been done in this area (although > Borland's highly successful Turbo Prolog is compiled to machine code). One > big reason, at least with Prolog, that little work has been done is that > you almost inevitably sacrifice one of the most important and distinctive > features of the language when you compile it: the ability to have a program > change its universe while running (assert/retract). Not really, it's possible to mix compiled and interpreted code. -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray
jwmills@iuvax.cs.indiana.edu (Jonathan Mills) (09/28/89)
In article <7152@ulysses.UUCP> garym@cognos.UUCP (Gary Murphy) writes: > >There is yet another alternative: wasn't there a posting a while ago >gloating over a prolog-based cpu? That's the one _I_ want! :-) > If it's the LIBRA, we're working on it. The VLSI prototype of the datapath unit is due back from MOSIS by October 2nd, and we will be testing it in both a pipelined & non-pipelined mode. If it works, the next step will be to put 10 slices on a chip to get tag, garbage collect & value ALUs on 4 chips. We are also experimenting with an automatically derived version of the LIBRA using Steven D. Johnson's Digital Design Derivation system (DDD). Although DDD cannot yet handle pipelined architectures, it has the benefit of producing designs that are correct with respect to their original specification. Finally, in my dissertation I described a clause compiler that emitted opcodes for an early version of the LIBRA, and which did NOT post-process WAM code, but instead built a DAG attributed with properties of each token in the Prolog clause, "head/body", "nesting level", "<type>". WAM code could easily have been output from this structure, but there was no need, particularly since I was interested in generating RISC opcodes. Jonathan Wayne Mills (812) 331-8533/855-7081
jwmills@iuvax.cs.indiana.edu (Jonathan Mills) (09/28/89)
In article <14299@megaron.arizona.edu> debray@arizona.edu (Saumya K. Debray) writes: > >... it's possible to mix compiled and interpreted code. > It is also possible to implement assert & retract as demons that fill in and link (or unlink) code templates. See the paper by Mills & Buettner in ICLP 88. Specializations of this kind are closely related to the general topic of partial evaluation. The notion of deriving the demon by compiling the clause template is similar to the notion of partially evaluating a partially evaluated program to yield a generator of specialized programs. Jonathan Wayne Mills (812) 331-8533/855-7081
jeff@aiai.ed.ac.uk (Jeff Dalton) (10/04/89)
In article <2181@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes: >Lisp needs types much worse than Prolog, because the Lisp equivalent >of append/3 would be > (defun app (A Z) > (if (endp A) ; check A > Z > (cons (car A) ; check A again > (app (cdr A) ; check A again > Z)))) >where A gets checked three times. In the code produced by a good Prolog >compiler, this effectively happens just once, and is ``paid for'' by the >`if'. Richard, I've seen this claim before (in Warren's paper, for example), and I've always been a bit puzzled by it. I would expect compiled Lisp code to make only one check, not three. And indeed, if I try various Lisps where it's easy for me to read the compiled code (such as Franz Lisp or KCL), it's clear that only one check is made. However, in many Lisps there's only one check because the compiled code for a car or cdr never includes a check. That is, while some Lisps might analyse the code to see whether a acheck might be needed, some certainly don't: they just emit the code to extract the car or cdr, with no check. It's fair to flame Lisp, or at least some Lisp implementations, for being less safe. It may even be fair to say Lisp needs types more than Prolog does. But I don't think it's fair to say Lisp makes three checks, because it doesn't. -- Jeff
ok@cs.mu.oz.au (Richard O'Keefe) (10/10/89)
> In article <2181@munnari.oz.au> ok@cs.mu.oz.au I claimed that > (defun app (A Z) (if (endp A) Z (cons (car A) (app (cdr A) Z)))) would check three times that A is a list. In article <979@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > Richard, I've seen this claim before (in Warren's paper, for example), > and I've always been a bit puzzled by it. Why be puzzled by it? David Warren and I were both used to Lisp systems (in my case Interlisp-D) that do in fact make the check that many times. Admittedly, Interlisp-D does the check in microcode, but then the Prolog equivalent is in microcode on the Xerox Lisp machines too. People at RMIT in Melbourne use Common Lisp on MacIvory, and I would be surprised if that Lisp system didn't repeat the check three times as part of the three instructions involved. The Lisp system I use here from time to time definitely has the check repeated in CAR and CDR -- I just checked. (ok, ok, so it's a Scheme, not a Lisp, big deal.) > I would expect compiled Lisp code to make only one check, not three. I'll get back to this shortly. > However, in many Lisps there's only one check because the compiled > code for a car or cdr never includes a check. It's fair to flame Lisp, > or at least some Lisp implementations, for being less safe. Now that is a serious mistake. Consider those broken Lisp implementations (but not the ones I've used or the one David Warren used) duly flamed. > But I don't think it's fair to say Lisp makes three checks, > because it doesn't. It _was_ fair for me to say that, because every Lisp I'd personally checked DOES make the three checks. Back to the question of what compiled Lisp code would do. A good Lisp compiler would exploit any type information it could pick up along the way. Now (endp A) succeeds if A is NIL, fails if A is a CONS, and is supposed to signal an error otherwise, so when we have (if (endp A) #|foo|# #|baz|#) a smart compiler would know in #|foo|# that A was NIL and it would know in #|baz|# that A was a CONS, so when it saw (car A) and (cdr A) it would know that it didn't need to repeat the checks. My own good habit of using (endp -) rather than (null -) defeated my own argument here! However, if I had written (if (null A) #|foo|# #|baz|#) then the compiler would only have been entitled to rely on A being different from NIL in the #|baz|# branch, so the (car A) would have to perform the check, and the (cdr A) would then be able to omit it. " So what I *should* have said is that "a naive Lisp compiler which makes the checks which are necessary for safety will do more checking than a " naive Prolog compiler which makes the checks which are necessary for safety".
jeff@aiai.ed.ac.uk (Jeff Dalton) (10/13/89)
In article <2367@munnari.oz.au> ok@cs.mu.oz.au (Richard O'Keefe) writes: > In article <2181@munnari.oz.au> ok@cs.mu.oz.au I claimed that > (defun app (A Z) (if (endp A) Z (cons (car A) (app (cdr A) Z)))) > would check three times that A is a list. >In article <979@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: >> Richard, I've seen this claim before (in Warren's paper, for example), >> and I've always been a bit puzzled by it. >Why be puzzled by it? David Warren and I were both used to Lisp systems >(in my case Interlisp-D) that do in fact make the check that many times. >Admittedly, Interlisp-D does the check in microcode, but then the Prolog >equivalent is in microcode on the Xerox Lisp machines too. People at >RMIT in Melbourne use Common Lisp on MacIvory, and I would be surprised >if that Lisp system didn't repeat the check three times as part of the >three instructions involved. The Lisp system I use here from time to >time definitely has the check repeated in CAR and CDR -- I just checked. >(ok, ok, so it's a Scheme, not a Lisp, big deal.) Microcoded Lisp machines, and other special hardware, tend to make lots of type checks because it doesn't cost very much. On "conventional" machines, most Lisps make such checks in compiled code only if the code was compiled in some sort of "safe" mode. Even you have used at least one Lisp in Edinburgh (Franz Lisp) that makes only one check in compiled code. If you want to know what Lisp does (so that you can makew true statements about it), you have to look at the practice in a number of different implementations. >> However, in many Lisps there's only one check because the compiled >> code for a car or cdr never includes a check. It's fair to flame Lisp, >> or at least some Lisp implementations, for being less safe. >Now that is a serious mistake. Consider those broken Lisp implementations >(but not the ones I've used or the one David Warren used) duly flamed. No one says you have to like the way Lisp works. That it can be unsafe is a valid complaint. In practice, however, the lack of checks is usually a manageable problem. If you want to be safer, you can define some pattern-matching macros that arrange for cars and cdrs to be taken only when the object is known to be a cons. >> But I don't think it's fair to say Lisp makes three checks, >> because it doesn't. >It _was_ fair for me to say that, because every Lisp I'd personally checked >DOES make the three checks. Well, how many did you check? If I check one or two Prologs, am I then justified in making unqualified statements about Prolog as if my observations were true in general? >So what I *should* have said is that "a naive Lisp compiler which makes >the checks which are necessary for safety will do more checking than a >naive Prolog compiler which makes the checks which are necessary for safety". Right. Cheers, Jeff