🚀 go-pugleaf

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