lee@mulga.oz (Lee Naish) (11/10/87)
>From: blenko@burdvax.PRC.Unisys.COM (Tom Blenko) >Subject: Badness > >My favorite bit of erroneous Prolog software is the oft-cited append() >procedure/relation: > > append([],X,X). > append([H|T1],X,[H|T2]) :- > append(T1,X,T2). > >I don't believe I've ever seen the incorrectness (by Richard's view) >acknowledged in a text or publication, I discuss it in "Specification = Program + Types". I argue that in the *natural* specification for append, all arguments must be lists. The paper introduces the notion of "type correct" programs (which can include the normal version of append) and shows why these programs do not produce well typed but incorrect answers. The Mycroft/O'Keefe type checker can also be used to catch programs which call append with non-lists (both these refs have been posted recently). > 3. Backtracking and cut are more difficult use than more > conventional control constructs You may be right about cut, but if you program declaratively, backtracking is never a problem. > 5. It is well known that O'Keefe's and Naish's exhortations > to Lagache (for sensitivity to efficiencies in the > implementation and for conformity to simple declarative > interpretations) will sometimes conflict. It seems less well known that more often they do not conflict! You should always look for a clean solution first. After that, you can try to "optimize" it by adding cuts, asserts etc. Often you find it is not necessary and/or makes the program *slower* (ask Richard about this if you like). Lee Naish
blenko@burdvax.PRC.Unisys.COM (Tom Blenko) (11/11/87)
In article <2385@mulga.oz> lee@mulga.UUCP (Lee Naish) writes: |>From: blenko@burdvax.PRC.Unisys.COM (Tom Blenko) |>Subject: Badness |> | ... | |> 3. Backtracking and cut are more difficult use than more |> conventional control constructs |You may be right about cut, but if you program declaratively, |backtracking is never a problem. But it isn't clear what the admonition to program declaratively means. Programming declaratively, in the sense of pure PROLOG (without call(), not(), and cut()) is not even powerful enough to express IF-THEN-ELSE, which I am willing to assume is a _sine_qua_non_ for programming. One can get IF-THEN-ELSE back with call() and not(), but the non-declarative character of PROLOG not() is also well known. So I don't think we can take "program declaratively" too seriously if it means that we cannot express IF-THEN-ELSE (because it doesn't suffice as programming), or if it means that we have to admit call() and not() (because then it isn't declarative). Just to save some time here, I also point out that not() restricted to, or delayed to await, grounded arguments, as you and others have proposed, does not get one out of the difficulty (of expressing IF-THEN-ELSE declaratively when the condition requires more than constructor matching). | |> 5. It is well known that O'Keefe's and Naish's exhortations |> to Lagache (for sensitivity to efficiencies in the |> implementation and for conformity to simple declarative |> interpretations) will sometimes conflict. |It seems less well known that more often they do not conflict! |You should always look for a clean solution first. After that, you can |try to "optimize" it by adding cuts, asserts etc. Often you find it is |not necessary and/or makes the program *slower* (ask Richard about this |if you like). I'm not sure we're disagreeing. I do recall a perfectly fine declarative program for append3() that you cite in a paper as suffering from non-termination, even though correct declarative solutions are also possible, and other examples are not too hard to come by. So I think the "program declaratively" admonition is not even safe, efficiency questions aside. Tom
broome@brl-smoke.ARPA (Paul Broome ) (11/13/87)
It's not clear that IF-THEN-ELSE is essential for programming. In fact it's often hazardous! The ELSE part of an IF-THEN-ELSE is too all-enclosing. A small example that immediately comes to mind is factorial, often written something like fac(N) = if N=0 then 1 else N*fac(N-1). The danger comes from permitting an unbounded recursion for negative N. It's much better, in this case at least, to say explicitly what cases can be handled and fail for those outside. E.g. something like fac(N) = if N=0 then 1 if N>0 then N*fac(N-1). It would be interesting to see a small example that *requires* IF-THEN-ELSE? Paul <Broome@brl.mil>, <Broome@brl-smoke.uucp> p.s. This was prompted by the following: In article <4815@burdvax.PRC.Unisys.COM> blenko@burdvax.PRC.Unisys.COM (Tom Blenko) writes: >Programming declaratively, in the sense of pure PROLOG (without call(), >not(), and cut()) is not even powerful enough to express IF-THEN-ELSE, >which I am willing to assume is a _sine_qua_non_ for programming.
lee@mulga.oz (Lee Naish) (11/13/87)
I hope not too many people are getting bored by this discussion (I haven't got any flames yet). In article <4815@burdvax.PRC.Unisys.COM> blenko@burdvax.PRC.Unisys.COM (Tom Blenko) writes: >Programming declaratively, in the sense of pure PROLOG >is not even powerful enough to express IF-THEN-ELSE, Forget pure Prolog. Think about logic. Then think about how much of logic can be implemented reasonably efficiently (more than pure Prolog!). There are loads of techniques which have been discovered, ranging from the reasonable well documented WAM to the undocumented $copyVariablesToTopOfHeap/1 (useful for implementing inequality:-). >declarative program for append3() that you cite in a paper as suffering >from non-termination, >So I think the "program declaratively" admonition is not even safe, >efficiency questions aside. I use append3/4 as an example of how purely declarative programming *is* possible, given the right tools. Its true that the techniques don't work for all programs. But, when append3 gets into an infinite loop, adding a cut is not the best solution. The version with a cut is *incorrect*. If only declarative constructs are used then the program can at least be read declaratively, even if efficiency and termination was considered at the time of writing. lee