lee@mulga.oz (Lee Naish) (09/27/87)
Virtually every time someone posts Prolog code to the network I groan. I see code like this: >merge([],[],[]). >merge([],List2,List2):- !, fail. >merge(List1,[],List1):- !, fail. >merge([Head1|Tail1],[Head2|Tail2],[Head1,Head2|R]):- merge(Tail1,Tail2,R), !. I wince, I tear my hair out, I fall to my knees and bang my head against the nearest rock crying; is this the Prolog code people write? What happened to logic programming? Am I wasting my time? Then I compose myself. I grit my teeth, take hold of my electronic butchers knife and attack the code. Out with the filth! Out with the cuts, the dirty negation, the asserts. Wash it clean. Just leave the essence; pure beautiful logic: merge([],[],[]). merge(Head1.Tail1, Head2.Tail2, Head1.Head2.R) :- merge(Tail1,Tail2,R). Then I look on it anew. I see it can be run as Prolog. No choice point will be created! It will be fast! It can be run backwards! It can be run any way need dictates. I breath a sigh of relief and my confidence in logic programming and Prolog are restored.
shebs@utah-cs.UUCP (Stanley Shebs) (09/28/87)
In article <2265@mulga.oz> lee@mulga.UUCP (Lee Naish) writes: >Virtually every time someone posts Prolog code to the network I groan. >I see code like this: > >>merge([],[],[]). >>merge([],List2,List2):- !, fail. >>merge(List1,[],List1):- !, fail. >>merge([Head1|Tail1],[Head2|Tail2],[Head1,Head2|R]):- merge(Tail1,Tail2,R), !. > >I wince, I tear my hair out, I fall to my knees and bang my head >against the nearest rock crying; is this the Prolog code people write? >What happened to logic programming? Am I wasting my time? I must be too old and cynical - whenever I see really bad code, my main regret is that the authors are not in a class I'm teaching, so I can fail them on that program. (We have used large red stamps saying "VOMIT" to good effect, also...) I would like to see next editions of Prolog textbooks flush all the hype about Prolog being "declarative" (whatever that's supposed to mean) and replace it with sections on good style. I would like even more to see cuts disappear from implementations entirely, to be replaced by meta-level capabilities, but I suppose that's a forlorn hope, since everybody wants "efficiency". stan shebs shebs@cs.utah.edu
debray@arizona.edu (Saumya Debray) (09/29/87)
In article <5005@utah-cs.UUCP>, shebs@utah-cs.UUCP (Stanley Shebs) writes: > I would like ... to see cuts disappear from implementations entirely, > to be replaced by meta-level capabilities, but I suppose that's a > forlorn hope, since everybody wants "efficiency". You can't fault people for wanting efficiency. You *can*, however, fault implementations that rely overmuch on cuts for performance (I guess most current implementations would end up being faulted: for example, how many commercial Prolog systems out there would recognize that, given the mode <+,+,-,-> for the predicate part([],_,[],[]). part([E|L], M, [E|U1], U2) :- E =< M, part(L,M,U1,U2). part([E|L], M, U1, [E|U2]) :- E > M, part(L,M,U1,U2). there's no need to create choice points for it? None that I'm aware of! [*]). Hopefully, as compilers improve, cuts will become less essential for good performance. Talking about implementations, I was quite surprised to see, at SLP 87 earlier this month, at least two high-powered commercial Prolog systems suffer a factor of 3 slowdown when I changed append/3 from append([],L,L). append([H|L1], L2, [H|L3]) :- append(L1, L2, L3). to append([],L,L). append([H|L1], L2, L) :- L = [H|L3], append(L1, L2, L3). Their performance, on naive reverse on a Sun-3/75, dropped from about 140 KLIPS for the "usual" append to about 40 KLIPS for my "mutant" append. You think people would do a better job of handling inline predicates and temporaries! ----- [*] Some versions of SB-Prolog recognize that no choice point need be created in this case. Of course, SB-Prolog isn't a commercial system. ----- -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray
lhe@sics.se (Lars-Henrik Eriksson) (10/05/87)
In article <2217@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes: >Talking about implementations, I was quite surprised to see, at SLP 87 >earlier this month, at least two high-powered commercial Prolog systems >suffer a factor of 3 slowdown when I changed append/3 from > > append([],L,L). > append([H|L1], L2, [H|L3]) :- append(L1, L2, L3). >to > append([],L,L). > append([H|L1], L2, L) :- L = [H|L3], append(L1, L2, L3). > >Their performance, on naive reverse on a Sun-3/75, dropped from about >140 KLIPS for the "usual" append to about 40 KLIPS for my "mutant" >append. You think people would do a better job of handling >inline predicates and temporaries! In at least one "high-powered commercial Prolog system" naive reverse suffers a 35% slowdown (on a SUN) when you change append/3 to append([],L,L). append([H|L1], [H|L2], L3) :- append(L1, L2, L3). i.e. change the order of the second and third arguments! The slowdown of append itself is obviously greater, although I haven't made any measurements. Apparently poor handling of inline predicates isn't the only thing that's going on... Lars-Henrik Eriksson lhe@sics.se Swedish Institute for Computer Science Box 1263 S-163 13 SPANGA, SWEDEN
debray@arizona.edu (Saumya Debray) (10/17/87)
In article <1528@sics.se>, lhe@sics.se (Lars-Henrik Eriksson) writes: > In at least one "high-powered commercial Prolog system" naive reverse > suffers a 35% slowdown (on a SUN) when you change append/3 to ... > Apparently poor handling of inline predicates isn't the only thing that's > going on... Hmmm ... I wonder if changing the name of the predicate from "append" to "foo" results in a significant slowdown! :-) As long as we're trying to optimize the hell out of append, it's interesting to note that entering the loop at the bottom instead of the top, i.e. generating the instruction sequence [...], getlist 1, unify, unify, getlist 3, unify, unify, switchonterm instead of switchonterm, [...], getlist 1, unify, unify, getlist 3, unify, unify, execute append/3 can give a 7-10% improvement in naive-reverse LIPS numbers (not to be sneezed at entirely, since we could only get about a 5-7% speedup using special unification instructions based on i/o modes). (Besides, this technique applies to other tail-recursive predicates as well, so one needn't be embarrassed about using it to improve nrev.) -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: {allegra, cmcl2, ihnp4} !arizona!debray
lhe@sics.se (Lars-Henrik Eriksson) (10/21/87)
In article <2431@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes: >Hmmm ... I wonder if changing the name of the predicate from "append" >to "foo" results in a significant slowdown! :-) It does not. People who have looked at the code tell me there is a special WAM instruction for clauses of the form foo([X|A],B,[X|C]) :- foo(A,B,C) where "foo" can be any function symbol.