bimandre@kulcs.uucp (Andre Marien) (09/26/89)
In article <2181@munnari.oz.au> O'Keefe writes : >However, if > arithmetic is more than say 30% of the cost of your Prolog program, > you aren't doing things the Prolog Way. Agreed. > To be sure, tagging does slow arithmetic down. Static typing can help > there, *IF* you also have strict mode checking as well. > Don't make the mistake of thinking that types are necessary for > efficiency: BCPL, BLISS, and many other systems programming languages are > not typed. > As far as I know, Bruynooghe was the first to write about types in Prolog. At ICLP 89 there was a paper of me and others, including Bruynooghe, which clearly shows that types are useful for efficiency, especially for improving arithmetic. People who are interested can read the article for more details. > 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. Now this is interesting : other tag checking that may be required comes free ! If I only would know how that can be done. I spend years optimizing this stuff for the BIM_Prolog compiler, and have not found a way to do that. Could you tell us how this can be done ? Andre' Marien bimandre@kulcs
ok@cs.mu.oz.au (Richard O'Keefe) (09/27/89)
In article <1742@kulcs.kulcs.uucp>, bimandre@kulcs.uucp (Andre Marien) writes: > At ICLP 89 there was a paper of me and others, including Bruynooghe, which > clearly shows that types are useful for efficiency, especially for > improving arithmetic. People who are interested can read the article for > more details. I haven't finished reading the paper in question: "The impact of abstract interpretation: an experiment in code generation" Andre' Marien, Gerda Janssens, Anne Mulkers, Maurice Bruynooghe Proc 6ICLP, pp 33--47. Three points: (1) I recently posted a message about type systems and complexity. To the best of my belief the type system used by Marien et al. is _NOT_ like the ones I was criticising. As far as I know, my remarks about complexity may NOT apply to it. (2) It isn't really clear from the paper just how types help. The paper talks about "call-types", giving as an example append(List, List, Free) where type List == nil | Int.List This appears to combine both type information proper and mode information. The paper explicitly says that "the mode information is in fact derived from the type information". "Free" is not what we normally mean by a "type" in Prolog. When I said that types are not _necessary_ for efficiency, I meant TYPES, not MODES. Of course mode information can help. There is an example in the paper of how TYPE information as such may help. The example is that if you have a predicate like append(_A1, _A2, _A3) :- _A1 = [], _A2 = _A3. append(_A1, _V, _A3) :- _A1 = [_X|_U], _A3 = [_X|_W], append(_U, _V, _W) then once you have determined that _A1 does not have a "list" tag you don't need to bother checking whether it is [] or not, there is nothing else it can be. Clearly, I was wrong. Strict type checking CAN eliminate as much as one comparison per procedure call. (3) The examples reported in the paper were (a) naive reverse (four clauses) (b) inserting into a tree (three clauses) (c) adding up the elements of a list (three clauses) It should be noted that (b) and (c) do one arithmetic operation per recursive call. I do appreciate that the point of the paper was to show that abstract interpretation could get Prolog even closer to C (the unoptimised Prolog code for nrev and sumlist started out about twice as slow as the C code), and that the extreme difficulty of doing almost anything in C made it painful to consider large examples, but I do wish that some large examples had been reported (I'm sure that some must have been studied). -- GNUs are more derived than other extant alcelaphines,| Richard A. O'Keefe such as bonteboks, and show up later in the fossil | visiting Melbourne record than less highly derived species. (Eldredge) | ok@munmurra.cs.mu.OZ.au