Lambda the Ultimate

Yes. Sorry about that.

A much better rendition of the page is availble here. The what went wrong/What was done about it boxes were missing.

Shrijvers seems optimistic that the problem is mostly a social one, and not a problem with Prolog.

What do others think?

I think that Prolog has lasting interest as a teaching language, and is one of the handful of PLs that everyone with a broad interest in programming should learn, but that the limitations of its basic computational mechanism make it uncompetitive as a general PL. I find that Haskell, through the list of successes paradigm, is usually a better language for writing the kind of programs Prolog is good at than Prolog.

I think the LP community should be seriously looking for a successor. There's no shortage of candidates.

Nadathur, Jayaraman (1989). Towards a WAM Model for Lambda Prolog. TR-CS-1989-11, Duke.

Issues concerning the implementation of the logic programming language $\lambda$Prolog are investigated. This language extends Prolog by providing for higher-order notions and incorporating a richer set of search primitives. Techniques must therefore be devised for implementing these two new aspects. Extensions to the Warren Abstract Machine (WAM) are proposed in order to deal with the several significant new problems that arise in conjunction with the former aspect. A representation for $\lambda$-terms is outlined that facilitates the examination of their internal structure while simultaneously permitting reductions to be performed easily. Mechanisms are discussed for implementing higher-order unification - an operation that is much more complex than first-order unification - within the backtracking paradigm of Prolog. Instructions for creating $\lambda$-terms and invoking operations within unification are also provided. The nature of compiled code is illustrated through examples, and it is argued that the enhancements to the WAM preserve its behavior over first-order programs. The ideas presented in this paper are the basis of an implementation effort that is currently underway.

This abstract suggests that lambda-Prolog would not be a painful direction for the LP community to take, though I have not read the paper (not available online), and I wonder about the phrasing it is argued that the enhancements to the WAM preserve its behavior over first-order programs.

One of the authors, Nadathur, is involved in the current Teyjus implementation of lambda-Prolog.

I shall email the authors, to see if the paper is available electronically.

Gopalan Nadathur pointed me to this sequel, namely Nadathur (2002). A Treatment of Higher-order Features in Logic Programming:

The logic programming paradigm provides the basis for a new intensional view of higher-order notions. This view is realized primarily by employing the terms of a typed lambda calculus as representational devices and by using a richer form of unification for probing their structures. These additions have important meta-programming applications but they also pose non-trivial implementation problems. One issue concerns the machine representation of lambda terms suitable to their intended use: an adequate encoding must facilitate comparison operations over terms in addition to supporting the usual reduction computation. Another aspect relates to the treatment of a unification operation that has a branching character and that sometimes calls for the delaying of the solution of unification problems. A final issue concerns the execution of goals whose structures becomes apparent only in the course of computation. These various problems are exposed in this paper and solutions to them are described. A satisfactory representation for lambda terms is developed by exploiting the nameless notation of de Bruijn as well as explicit encodings of substitutions. Special mechanisms are molded into the structure of traditional Prolog implementations to support branching in unification and carrying of unification problems over other computation steps; a premium is placed in this context on exploiting determinism and on emulating usual first-order behaviour. An extended compilation model is presented that treats higher-order unification and also handles dynamically emergent goals. The ideas described here have been employed in the Teyjus implementation of the Lambda Prolog language, a fact that is used to obtain a preliminary assessment of their efficacy.

The paper seems to be an evolution of the ideas in the earlier TR, though I have not looked closely enough to be clear. Gopalan says that the new architecture of Teyjus 2.0 represents a further evolution beyond this paper, which has not yet been written up.

but that the limitations of its basic computational mechanism make it uncompetitive as a general PL

I agree. In some sense this is a shame since the basic principle is so appealing.

To make he discussion slightly more controversial: I think one of the reasons is that the control structures are opaque (or implicit, if you prefer). While several paradigms claim that they can "save" programmers from the tediousness and errors the come from dealing explicitly with control (yes, I am talking to you FP-er out there), until now the experience of many programmers, including people who used several of these languages quite a bit is that this raises various types of problems (including making some types of reasoning harder, even if others are made easier by this language design decision), limiting in practice, and hard on beginners.

Case in point: Laziness.

It seems that the right balance between this lofty goal and other demands is still to be found.

(I hasten to add that this does not mean that imperative languages as found today are "better" than FP languages as found today, only that both paradigms will need to continue evolving).

compares the health of the Prolog community unfavourably to that of Haskell

The Prolog community has had an enormous influence on computer science. Constraint programming is one direct influence, but the main influence has been indirect. Many people who were once logic programming researchers have moved into other areas of computer science and made major impacts. Offhand, here are a few: Tim Lindholm (Quintus Prolog developer, was one of the key designers of the Java Virtual Machine at Sun), Ehud Shapiro (originator of concurrent Prolog, is a major figure in other areas such as DNA computing), Vijay Saraswat (originator of concurrent constraints, is a major figure in parallel languages), Ian Foster (designer of Strand concurrent logic language, is the originator of Grid computing), Pascal Van Hentenryck (pioneer of constraint logic programming, is now a major figure in combinatorial optimization), Seif Haridi (designer of AKL deep guard language, is a major figure in distributed and peer-to-peer computing), Koen De Bosschere (now working in parallelism and computer architecture), Manuel Hermenegildo (a pioneer in And-parallel Prolog and abstract interpretation for Prolog, now a key figure in security with abstraction-carrying code), Peter Van Roy (myself, developer of Aquarius Prolog, coauthor of CTM and also working in distributed computing). This list could be extended greatly; I just wrote down the first names that came to mind.

I think it can fairly be said that the logic programming community has influenced many areas of computer science out of all proportion to its small size.

I think it can fairly be said that the logic programming community has influenced many areas of computer science out of all proportion to its small size.

No one has even hinted at otherwise; that was not and is not the issue being discussed.

Thank you for sharing your experience.
Object-oriented programming itself is issued from modelling and simulation, is it really useless in that context? What are the main issues with it?

...that I intend to address later. I just want to put this placeholder here for now. :-)

One starting point: OOP is in many ways little to no help with continuous simulation. It's also not necessarily all that helpful with a discrete event sim if (for example) all messages really want to go back via an event queue - wouldn't you rather write recipient.message(parms) than queue.add(message(recipient, parms))?

Which isn't to say that it hasn't been a valuable step on the way, or that approaches that're closer to being the Right Thing don't often bear a distinct resemblance to it. But we're talking about 30-40 year old ideas, and we've learned things in the meantime.

Personally I'm fond of approaches that let you define a 'metamodel' describing what amounts to a simulation's 'laws of physics' rather than forcing a general one upon you. But I'm a Haskell-writing EDSL addict, what else did you expect?

Prolog is a very old language. In 1972, the sweet spot that it hit intrigued a lot of people, and unfortunately that has slowed down progress (many logic programmers still stand firm by Horn clauses and the WAM, even today!). My view is that logic programming has to take its place inside a bigger framework, where it can be used when it is needed (and then it really shines), but where other paradigms can be used when it is not appropriate. A far cry from the original dream of programming everything in logic! That original dream is unrealistic, because logic is not the right way to express all computing. "There are more things in heaven and earth, Horatio, than are dreamt of in your philosophy." Logic programming used to be full of Horatios and functional programming still is. Here is an article that explains this in more detail: Logic Programming in the Context of Multiparadigm Programming: The Oz Experience (Journal of Theory and Practice of Logic Programming, Nov. 2003).

here is his take on the whole Wikipedia affair; he alleges that Kowalski and others are trying to censor and bury his contributions to the field, and are using Wikipedia as a forum for doing so.

Read it for yourself and decide.

I should note that a) I'm entirely impartial on the debate concerning the Kowalski/Hewitt schools of thought, such as they are. Hewitt's ideas and research, from Planner to the actor model to whatever else, I've no objection to. However, b) I am an active participant on Wikipedia, and observed first hand Hewitt's numerous attempts to "spam" Wikipedia pages with references to his own work, far above and beyond their actual significance to the field. Gratuitous reference to the Actor model and such were being inserted by Hewitt on page after page after page, in many cases in places where they weren't really appropriate. While Wikipedia does encourage scientists to edit subjects in which they are experts, including areas they might themselves be working on--it only gives them carte blanche to do so as long as they remain objective--and has clear policies for dealing with conflicts of interests among editors. Hewitt quite clearly crossed the line, on numerous times after numerous warnings, which is why he was eventually topic-banned.

In Hewitt's reponse, cited above, he states that the CoI policy essentially prohibits him from citing his own work. However, the policy specifically addresses the issue:

Editing in an area in which you have professional or academic expertise is not, in itself, a conflict of interest. Using material you yourself have written or published is allowed within reason, but only if it is notable and conforms to the content policies. Excessive self-citation is strongly discouraged. When in doubt, defer to the community's opinion.

Wikipedia's policy on no original research adds further:

This policy does not prohibit editors with specialist knowledge from adding their knowledge to Wikipedia, but it does prohibit them from drawing on their personal knowledge without citing their sources. If an editor has published the results of his or her research in a reliable publication, the editor may cite that source while writing in the third person and complying with our NPOV policy.

Many scientists successfully contribute to Wikipedia in their fields of expertise, including citing their own research, with no issues whatsoever. Only a handful that I'm aware of have run into this sort of issue; and Hewitt is, unfortunately, one of the more flagrant offenders.

"here is his take (http://wikicensored.info/) on the whole Wikipedia affair..."

That's a blank page. What did it say?

See here.

...near as I can tell, is an old one in knowledge systems research: the inductive/deductive debate. Hewitt is on the side of the "inductivists", and seems to fancy Kowalski et al as strict deductivists, standing steadfast in the way of progress by refusing to consider "procedural" solutions. Whether or not Kowalski and his peers are in fact enamored of such an absolutist position, I don't know.

As mentioned above, much of the debate seems to be a bit personal. Much logic programming research seems to center around Prolog and its decendents--a language with a mostly-deductionist approach, other a few "impure" features like cut. Hewitt's primary contribution to the field--Planner--is mainly relevant as a historical artifact. Much of the brouhaha on Wikipedia seems to concern the impact Planner had on Prolog--in other words, unfortunately, how much credit Hewitt is entitled to. He seems to feel he is entitled to far greater recognition than he receives, and in some cases--as in Wikipedia--has attempted to alter the record to better highlight his immense contributions.

As is often the case with flamewars among the scientific community, the debate surrounds a prescriptionist rather than a descriptionist issue--a question of how "should" something be done, rather than what something is or how something works. Should we admit or abolish procedures in logic programming? Many other similar debates are found in PLT, or have been in the past--should we admit side effects, should we use static or dynamic type systems, should we default to strict or lazy evaluation, OO-vs-not, structural-vs-goto, formal verification and methods, etc. In most cases, the correct answer is "it depends"--answering a "should" question, in many cases, is a systems design issue, and thus the province of engineers (and possibly policymakers), and not research scientists. Scientists do and should inform the debate, of course--and are far too often ignored by practitioners who instead base design decisions on personal or institutional prejudice--but the best course for a scientist studying knowledge systems is to do research and write papers on the effects of various choices; *not* to go around the country giving talks in which one of your peers is singled out as a boulder blocking the path of progress.

Even though I have, in three posts now, raked Mr. Hewitt over the coals for his petulant behavior--I'll have to agree with him that an absolutist deductive-only position is undesirable. There are many cases where a pure-deductive approach is satisfactory, and Horn clause solvers like Prolog have termination as a desireable property (modulo recursive definitions/"occurs check" violations)--but I think that the dichotomy is improper. To the extent that Hewitt thinks deductive-only approaches should be abandoned; there I do *not* agree.

Thanks to Messrs. Curry and Howard, we know that programs are proofs of some proposition. Program fragments, such as (imperative) procedures are likewise proofs, as are algorithms in the abstract. If a mathematician is given a fourth-degree polynomial to solve, he doesn't attempt to derive the solution himself--he pulls out his CRC manual (or looks online to mathworld or some similar resource) and takes advantage of 500 years of mathematical knowledge to plug-and-chug. (We'll ignore numerical approxmations, and assume the exact formula is used). To put it another way, the algorithm for the solution to a quartic polynomial is a theorem that up to four unique solutions exist (one which has the added benefit of stating what they are). Purely deductive approaches place a limit on the sort of theorems that may be introduced into the system.

In some cases, a procedure may constitute an additional axiom; one which cannot be derived from the existing axioms but which is consistent with the system. By allowing this such axioms, the system is strentghened. In other cases, such as the quartic formula (which can be derived from elementary algebra, but is difficult to derive if you don't know the tricks involved), procedures may be "optimizations" of things which can be derived from within an existing system.

The cost of adding arbitrary theorems (procedures) is that it is harder if not impossible to exclude the introduction of axioms or theorems which are incorrect (produce an inconsistent system), or fail to terminate, or both.

I suspect that in most cases, the trade-offs involved are application dependent. Polemics for or against a particular position, when that position does have some useful application, are unhelpful. A common sin in CS debates is an insistence on "universality"--that a technique must be applicable to all relevant problems in order to be useful, and that techniques which are only relevant to a subset of problems are worthless and should be discarded. By portraying deductionists (or certain alleged deducitonists) as "being in the way", Hewitt does the field no favors. Likewise, I can think of a few practitioners on the other side of the debate, who I won't name here (not being involved in the Hewitt affair), who do exhibit a hostile attitude towards inductive approaches; when they go overboard in their advocacy, they are equally unhelpful.

Thanks for the summary!

Am I the only one who find the deductive/inductive distinction made in this debate somewhat strange? I can understand the deductive nature of Prolog (within limits), but I am less certain about the notion of inductive reasoning used here.

American AI strongly favors "forward" chaining systems, and planning systems which are also forward. This may be related to the fact that at the conclusion of the Planner project the notion of backtracking is rejected as "only a search" method, and focus moved on to the Actor model. Meanwhile in Europe development proceeds on backtracking and Prolog.

Edit: Using this link instead of the one above. On page 3.

What went wrong:
1. Although pragmatically useful at the time it was
developed, backtracking proved to be too rigid and
uncontrollable.

What was done about it:
1. Concurrency based on message passing was
developed as an alternative to backtracking.

Hopefully this helps to explain Hewitt's attitude towards backtracking, but personally I don't get it. Is there something wrong with backtracking? I for one am unable to reach that conclusion.

I'm also confused by the supposed dichotomy. To me, "inductive" approaches refers to things like machine learning, or Inductive Logic Programming. I'm not sure what connection it has to procedural knowledge representations. I'm also confused by the supposed characterisation of Robert Kowalski as committed to "deductive" approaches. Kowalski has done much research on non-deductive techniques, such as Abductive Logic Programming. Perhaps, given that neither party is a member of LtU (as far as I know), it might be better to not attempt to paraphrase their positions.

(Nit-picking something Scott said:)

Horn clause solvers like Prolog have termination as a desireable property (modulo recursive definitions/"occurs check" violations)[...]

As far as I remember, Prolog's operational semantics is Turing-complete, and reasoning with Horn clauses is undecideable. IIRC, Datalog is decideable.

(Nit-picking something Scott said:)

Horn clause solvers like Prolog have termination as a desirable property (modulo recursive definitions/"occurs check" violations)[...]

As far as I remember, Prolog's operational semantics is Turing-complete,

Due to recursive definitions.