Talk:Logic programming

From Wikipedia, the free encyclopedia

 This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
??? This article has not yet received a rating on the quality scale.
??? This article has not yet received an rating on the importance scale.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
High rated as High-importance on the assessment scale

Contents

[edit] Logic programming and constraint programming

Although logic programming and constraint programming are closely related, I don't believe it's accurate to treat them as synonyms, or one as a subtype of the other. I have drafted a couple of paragraphs to clarify the difference and suggest why one is more appropriate than the other in various problem domains. Question: since the two have already been conflated, and there are multiple redirects to this page, what is the best way to make them again distinct? Glenn6502 02:05, 21 Apr 2004 (UTC)

Hi, you're right, the two aren't synonyms. But I think they can be discussed on the same page. Be bold. -- Arvindn 03:09, 21 Apr 2004 (UTC)

Hmm, is "commercial" an appropriate description of Mercury ? At least it's implementation is released under the GPL. Perhaps a better word might be "industrial-strength", "real-world" or something similar. (Mayhaps something about "programming-in-the-large", "robust", "modular" or something.) Just a Suggestion. StefanLjungstrand 23:32, 29 Apr 2004 (CEST)

[edit] Title

I've never heard the phrase "logical programming" before reading this article. "Logic programming" gets 543,000 hits on google, "Logical programming" gets 5520, most of the first hits being derived from this article. I suggest we change. ---- Charles Stewart 11:50, 24 Sep 2004 (UTC)

Just a thought after the fact: yes, logic programming is the accepted name. DoesPHalt 22:00, 12 Dec 2004 (UTC)
Right: I asked User:Charles Matthews to do the shift a couple of monyhs ago (see User talk:Charles Matthews/Archive6#Move(with delete) Logical programming; I should have put a comment to that effect here. I think the name "logical programming" was started because it sounds more in keeping with the list on programming paradigms. ---- Charles Stewart 09:35, 14 Dec 2004 (UTC)

[edit] Added discussion about claim to be declarative

User:Koffieyahoo reverted my contributions.

So I have added some discussion to the article.--Carl Hewitt 05:39, 13 July 2005 (UTC)

Okay so basically the two changes you made were:

  1. Add reference to the Scientific Community Metaphor
  2. Delete reference to relevant literature.

I deleted the first one as that article does not explain at all that this has anything to do with logic programming, Adapt that page first and then add back the reference here. I re-added the second one because it refers to bakctracking, which is absolutely relevant. Koffieyahoo 12:05, 13 July 2005 (UTC)

[edit] Logic Programming != prolog

While this article reflects the early history of logic programming (and how many people) have come to see the term, in the academic community the term "Logic Programming" is typically applied to a much larger class of of system than those restricted to Horn Clauses. For instance, there has been a lot of recent(ish) interest in finite-domain nonmonotonic logic programming paradims like Gelfond & Lifschitz's stable models semantics http://citeseer.csail.mit.edu/gelfond88stable.html (Aka Answer Set programming or Datalog) and Disjunctive logic programming, both of which can account for both classical (i can show this isn't true) and epistemic (I can't show that this is true) negation, and disjunction in the heads of rules, while these systems are not turing complete (as they are limited to finite domains) they can be used for a lot of interesting problems because you aren't stuck with the constraints of programming in horn-clauses as you are with prolog.

I'm not trying to criticise the existing article, but imho "Logic Programming" needs broadening a bit.

I concur that it would be good to broaden the discussion. Regards,--Carl Hewitt 21:29, 31 October 2005 (UTC)
I certainly concur as well. I added a paragraph about linear logic programming to help make the point. I can add other issues about logic and declarativeness as I get a chance. -Dale Miller (9 Dec 2006) —The preceding unsigned comment was added by 86.218.20.188 (talk) 10:25, 9 December 2006 (UTC).
The pendulum has maybe swung too far the other way now: the history section doesn't regard the invention of PROLOG as worth a mention... --- Charles Stewart 21:13, 31 October 2005 (UTC)
The history section discusses Kowalski's claims although perhaps too briefly. Regards,--Carl Hewitt 21:29, 31 October 2005 (UTC)

[edit] Citations and references

IMO articles read better if we use the Harvard citation style together with a format for references which gives authors and dates together, eg. the APA style. So the first item:

  • John McCarthy. Programs with common sense Symposium on Mechanization of Thoght Processes. National Physical Laboratory. Teddington, England. 1958.
becomes (with some copyedits) either:
  1. John McCarthy. (1959). 'Programs with common sense'. In Proceedings of the Symposium on Mechanisation of Thought Processes held at the National Physical Laboratory, Teddington (1958). London: HMO Stationery Office.
    (the APA style)
    or:
  2. John McCarthy, 1959. 'Programs with common sense'. In Proceedings of the Symposium on Mechanisation of Thought Processes held at the National Physical Laboratory, Teddington (1958). HMO Stationery Office, London.
    (the style that I have been preferring, which just moves the date from the default latex position).

I know Carl Hewitt has put many such references, and it may be more effort than he is willing to invest to change this, but I would like to begin to follow this referencing policy. Other "logic in CS/AI" articles have been following this, and Paolo Libertore has software allowing the automatic formatting of WP markup from .bib entries.

Some other points of style:

  • When it exists, the date of publication should be preferred for references. So 1959, the date of publication of the proceedings is to be preferred to 1958, the date of McCarthy's talk.
  • Single quotes should be used for articles and contributions to edited volumes and italicised emphasis for names of books, journals and conference proceedings. Bold is generally too loud for references sections.

If there is agreement to the above, I shall reformat the references section, at least for this article. --- Charles Stewart 21:11, 31 October 2005 (UTC)

It is fine with me for you to reformat. Regards,--Carl Hewitt 21:19, 31 October 2005 (UTC)

[edit] Rule-based programming

Whilst editing programming paradigms, I've found that rule-based programming is redirected to logic programming. I think they are different enough to warrant separate articles. Specifically, the former form the basis of many computer algebra systems, which have comparatively little to do with logic programming. Is that fair?

Yes, this seems fair to me. Regards,--Carl Hewitt 06:34, 29 November 2005 (UTC)

[edit] Opening Sentence

"Logic programming (sometimes called logical programming) is a programming paradigm that is claimed to be declarative (i.e., based on mathematical logic) but this claim is controversial (see Limitations of Prolog as logic programming below)." Prolog may be controversial, but incorporating such weirdness into the definition of logic programming isn't particularly helpful. This is an article about logic programming, and debates about which schools of practice best reflect logic programming should be down in the article body.

Google definitions shows that this article once began with "Logic programming is a declarative programming paradigm in which a set of attributes that a solution should have are specified rather than set of steps to obtain such a solution. The most widely used logic programming language is Prolog. Other, more modern include Mercury, Visual Prolog, Oz and the Scientific Community Metaphor." This explains a bit more and I'm putting it back in modified version. Scientific Community Metaphor doesn't really seem to belong in this list, which is otherwise of programming languages~ I'm replacing it with Fril, which deserves mention.

The phrase declarative programming paradigm in which a set of attributes that a solution should have are specified rather than set of steps to obtain such a solution doesn't make much sense. So it has been replaced with more accurate statements.--71.198.215.78 09:10, 21 February 2006 (UTC)

"There are two families of logic programming languages: an original sequential form Prolog and a later concurrent form." Concurrency has certainly entered into later implementations of logic programming languages, but if we're going to suggest that this is the defining factor that creates the two main families of programming languages, we had best put a source on this rather bold decision. Also it doesn't really belong in this top part.

Put in reference to Shapiro [1989]. Article needs to report on situation in Logic Programming in general, not just sequential backtracking dialects.--71.198.215.78 09:10, 21 February 2006 (UTC)

Then what's this about "logical deduction was incapable of carrying out concurrent computation in open systems"? Perhaps there should be a section on concurrency and logic programming. If this relates more to Prolog specifically, which is not really such a good representation of logic programming anymore, then it could go into discussions on Prolog instead.

Good idea to put in section on Concurrency in Logic Programming.--71.198.215.78 09:10, 21 February 2006 (UTC)

Thanks. Chira 08:19, 21 February 2006 (UTC)

"kind of programming that is related to mathematical logic" isn't a useful description (I've never heard of a programming language that isn't related to mathematical logic). Perhaps it's more accurate than "in which a set of attributes that a solution should have are specified rather than set of steps to obtain such a solution" but it's also more useless. Perhaps someone can come up with a better opening definition. The comment about the history of logic programming don't help explain what it is, either: those should go down in the history section. Chira 09:13, 21 February 2006 (UTC)

Good idea to tighten this up. --71.198.215.78 09:50, 21 February 2006 (UTC)

[edit] Philosophy

The last section describes John McCarthy's advice taker proposal. This idea inspired many researchers working in Artificial Intelligence during the following years, myself included. I particularly remember Pat Hayes in Edinburgh visiting McCarthy in the late 60s to work with him on the advice taker. One result of this was the famous situation calculus paper, which appeared in 1969. Pat later contributed to the beginnings of logic programming, as the history section of this article mentions.

The first paragraph quotes McCarthy as writing:

"programs to manipulate in a suitable formal language (most likely a part of the predicate calculus) common instrumental statements. The basic program will draw immediate conclusions from a list of premises. These conclusions will be either declarative or imperative sentences. When an imperative sentence is deduced the program takes a corresponding action.”

It is not obvious to me how this relates to logic programming as it is commonly understood, even in the broader sense of this article. In particular, the last sentence of the quote seems to be more of a description of condition-action rules in production systems than it is a description of logic programming.

It could be said that production systems are the suitable formal language that McCarthy was describing, in which case this section is more appropriate for the production system article. On the other hand, the next paragraph of this section suggests that the section would be more appropriate for the article on common sense or for a new article on the advice taker.

Robert Kowalski 12:21, 10 January 2007 (UTC)

I recommend starting a new article on the advice taker with references to it from logic programming and common sense.172.200.28.119 14:40, 13 January 2007 (UTC)

Perhaps what is needed here is a section on knowledge representation, which subsumes both this section and the applications section as well. 82.153.171.123 18:05, 13 January 2007 (UTC)

I would totally agree with this, except that then a forced reference would be http://en.wikipedia.org/wiki/Knowledge_Representation which is not exactly very useful when it comes to philosophy. --Jacinto Dávila 21:40, 30 January 2007 (UTC)

I deleted the philosophy section, which is now in the advice taker article. I agree that the knowledge representation section here needs to be expanded/changed. Also, there should be links to the advice taker article, from the common sense and McCarthy articles, which are now missing.

I deleted the Applications section, because it gives a misleading impression that logic programming has limited applications. A new section on Knowledge Representation is badly needed. Also a section on Problem-solving, i.e. different ways of executing logic programs, would be very useful.

[edit] Disputed

We've gone through this before. Carl Hewitt and company are among the few who believe that that part of concurrent programming that can be analyzed at all can be analyzed through mathematical logic. — Arthur Rubin | (talk) 16:24, 30 March 2007 (UTC)

It would be useful if you could provide citations to the published literature to support your dispute. --2ndMouse 18:36, 30 March 2007 (UTC)
I claim that Hewitt, himself, is not a WP:RS in the field. If you rewrite to state that Carl Hewitt claims that concurrent programming cannot be implemented through mathematical logic, or if you can find sources other than Hewitt and his students, I have no objection. — Arthur Rubin | (talk) 20:07, 30 March 2007 (UTC)
The claim seems to have originated with Hewitt and his students. However, it has been published in the refereed literature many times and there does not appear to be any counterclaim in the published literature. What is the basis of your objection? --2ndMouse 20:32, 30 March 2007 (UTC)
What about Kowalski? Church's thesis? — Arthur Rubin | (talk) 21:46, 30 March 2007 (UTC)
I put in a clarification in Computability_theory_(computer_science)#Power_of_Concurrent_Computation. --2ndMouse 22:25, 30 March 2007 (UTC)
Besides, aren't you banned from editing articles related to Carl Hewitt? — Arthur Rubin | (talk) 21:47, 30 March 2007 (UTC)
The ban expired on 17 February 2007.--2ndMouse 22:28, 30 March 2007 (UTC)
You still haven't stopped Wikilawyering, have you? Please read Wikipedia:Requests for arbitration/Carl Hewitt more carefully: there was no time limit placed on your probation and banning from autobiographical editing. —Ruud 23:31, 30 March 2007 (UTC)

I have reverted Hewitt's changes to the version which significantly revised by no one less than Robert Kowalski himself. —Ruud 00:12, 31 March 2007 (UTC)

[edit] Reversion by Ruud Koot

What do you think of the reversion by Ruud Koot? --70.132.21.226 02:28, 31 March 2007 (UTC)

I agree with these changes, for two main reasons. First, these recent edits reintroduce Carl Hewitt's earlier characterization of logic programming as logic used for computing in a much more general sense than logic programming is generally understood, as characterised for example by the Association for Logic Programming http://www.cs.kuleuven.ac.be/~dtai/projects/ALP/.

It's interesting that this web page does not actually define "logic programming". Do you have a proposed definition?--70.132.26.82 20:30, 2 April 2007 (UTC)

Second, they reintroduce Carl Hewitt's criticism of logic programming, as he redefines it, as not universal. This kind of criticism could be made against virtually any technology and it is both irrelevant and unnecessarily hostile.193.136.124.221 09:56, 31 March 2007 (UTC)

These are legitimate points of controversy.
  • Some of the followers of Kowalski would like to restrict the definition of Logic Programming to backward chaining. The grounds for this restriction seem to be that Prolog was restricted to backward chaining and so a tradition grew up in some parts of the literature to adhere to this restriction. Other parts of the literature beginning with the earlier Planner language and its successors to this day do not adhere to this restriction, which seems somewhat arbitrary. For example McCarthy's original proposal for logic programming used forward chaining which was incorporated in successor work.
  • Also the current article is unnecessarily hostile to Kowalski and Hayes in that it seems likely that what they had in mind when they propounded their theses was computation (as in Turing Machines and the lambda calculus) and they did not envisage that current computation would turn out differently. So the article should be changed to reflect this. Also the article might mention the Representation Theorem for concurrent computation so all of this doesn't seem so mysterious.
  • At the same time, it is remarkable that logic programming (in the general sense of what can be programmed in logic) turned out not to be universal for computation (in the sense that there are concurrent computations that cannot be implemented in logic) and this published result should be reported in the article with no attempt at suppression.
What do you think of these proposed revisions?--70.132.21.226 15:57, 31 March 2007 (UTC)
The current article would be unnecessarily hostile to Kowalski if it implied that his interpretation did not apply to "current computation" without specific sources that he did not intend it to. I think only Carl Hewitt and students believe that "current computation would turn out differently" and that "logic programming ... turned out not to be universal for computation". Hewitt is a prolific writer, but I haven't seen evidence that his views are accepted by the computer science community.
As for the Representation Theorem, the article probably should reference it if it really is a "theorem", as opposed to a redefinition of concurrent computation. — Arthur Rubin | (talk) 16:41, 31 March 2007 (UTC)
I think that you have got Kowalski's position exactly wrong (based on some communications on mailing lists). You should contact Kowalski directly. At this point it is widely accepted that logic programming is not universal, e.g., from seminars and conversations at CMU, MIT, Stanford, and SRI and elsewhere by those who have read the published literature.
As for the Representation Theorem, you can review the proof yourself in:
Thanks for the reference. That clearly applies only to the actor model, which appears not to be mainstream. It does not need to be in any article not specifically about that model. — Arthur Rubin | (talk) 02:51, 1 April 2007 (UTC)
Since the actor model is very general, the Representation Theorem applies to the other main stream models as well. For example it applies to petri net and process calculi models via a 2-phase commit protocol to handle the synchronization. The relevance of the Representation Theorem is that it helps explain how it is possible to have a logical representation of concurrent computations without it being possible for logic to actually carry out the concurrent computations.--70.132.26.82 17:25, 1 April 2007 (UTC)
I do not concur that the actor model is "very general", nor that the Representation Theorem applies to any other methodology. Is there any source other than Hewitt et. al. for the validity of the Representation Theorem to other asynchronous computing models? — Arthur Rubin | (talk) 20:47, 2 April 2007 (UTC)
As I understand it, the purpose of the Wikipedia it not to decide truth but rather to report on published work (please correct me if I am wrong). The Representation Theorem was published in the refereed proceedings of a workshop of AAMAS and then the paper was selected for inclusion in a published volume of Springer Verlag. Also the paper is available on line. Do you see some problem with the proof?
There is a section on the application of the two-phase commit protocol in Synchronous channels in process calculi which shows how to carry out the required construction. --70.132.26.82 02:16, 3 April 2007 (UTC)
It's not entirely correct to say that the purpose of Wikipedia is to ... report on published work. The Undue weight clause requires us to decide which works represent the mainstream view, and to give space in articles accordingly. I don't see the actor model as mainstream, nor any refutation of the assertion that Kowalski represents the mainstream view that logic can model any computation. — Arthur Rubin | (talk) 15:35, 3 April 2007 (UTC)
You don't seem to understand that the Representation Theorem says exactly how logic can model any computation. It's just that logic is not capable of implementing certain concurrent computations. Also you are wrong about the the Actor model not being part of the mainstream. Are you aware of the illustrious researchers who have contributed to its development? At the this point the two most prominent models of concurrency are the Actor model and process calculi.
Also you have very badly misrepresented the current position of Kowalski. For example see the following:
  • Robert Kowalski. "The Logical Way to be Artificially Intelligent." CLIMA VI. Springer Verlag. 2006.--24.23.212.54 02:28, 4 April 2007 (UTC)
The Representation Theorem, as noted in that paper, is philosophical in content, rather than being related to computation theory.
A reading of the paper reveals that the Representation Theorem is related to computation theory. It is a mathematical theorem of computation that is formally stated and proved in the paper. --71.198.216.63 14:34, 4 April 2007 (UTC)
As for Kowalski's views, we'll have to let him decide. He edits here from time to time. — Arthur Rubin | (talk) 05:23, 4 April 2007 (UTC)
Excellent suggestion!--71.198.216.63 14:34, 4 April 2007 (UTC)

One issue is whether logic programming is to be understood, as the current version of the article characterizes it, as: "based upon the fact that a backwards reasoning theorem-prover applied to declarative sentences in the form of implications

   B1 and … and Bn implies H

treats the implications as goal-reduction procedures

   to show/solve H, show/solve B1 and … and Bn."

I believe that this is the generally accepted view of logic programming. It is a very restricted form of logic, but it is sufficient for Turing-computability.

This view is much more restrictive than Carl Hewitt's notion that it is

"the use of mathematical logic for computer programming".

This broader view might be called "logical programming", as Carl Hewitt suggested in an earlier version of the logic programming article. I see no problem with having a separate article called "logical programming", to deal with this broader view.

Good idea! So should we establish a separate article on Logical programming?--71.198.216.63 14:34, 4 April 2007 (UTC)

The other issue is whether "logic programming is universal". However, this issue is concerned with the broader questions of whether "mathematical logic for computer programming" is universal and whether Turing-computability is universal. As it happens, I agree with Carl Hewitt, that both logic and Turing-computability are not universal (in some sense). However, it seems to me that the issues involved are more suitable for the articles on logic and on computability than they are for the article on logic programming. Robert Kowalski 10:30, 4 April 2007 (UTC)

Excellent points. Do you think that these issues should be addressed in the new article on Logical programming?--71.198.216.63 14:34, 4 April 2007 (UTC)
Almost certainly not. Logical programming is a very bad name. Logic programming is questionable; perhaps it should be renamed to Logic of programming or Logic in programming. — Arthur Rubin | (talk) 17:55, 4 April 2007 (UTC)


Why do you think that the name is bad? Your suggestion Logic of programming is certainly off the mark in that it is not about the logic of programming. Likewise your suggestion Logic in programming is also off the mark because it is not about logic in programming.--71.198.216.63 18:44, 4 April 2007 (UTC)
The article appears to be about how logic can model programming or a specific logical model of programming; how could logical programming possibly the correct term. — Arthur Rubin | (talk) 22:43, 4 April 2007 (UTC)
The thrust of Kowalski's contribution seems to be that just as Logic programming is a kind of programming; so Logical programming is a more general kind of programming that can be implemented "logically" , i.e., using mathematical logic.--71.198.216.63 06:29, 5 April 2007 (UTC)
And the question of universality should possibly be in a an article on computability, rather than on programming. — Arthur Rubin | (talk) 17:55, 4 April 2007 (UTC)
And "71.198.216.63", aka Carl, you definitely shouldn't be editing this article if you're considering adding one of his previous suggestions.) — Arthur Rubin | (talk) 17:55, 4 April 2007 (UTC)
And I was wrong about the Representation Theorem being philosophical. It's a badly phrased definition. — Arthur Rubin | (talk) 17:55, 4 April 2007 (UTC)


The published paper states a theorem and gives a proof. Why do you think that the Representation Theorem is a definition? --71.198.216.63 18:44, 4 April 2007 (UTC)
I fail to see how the set of "computations of S" can be different from the set of time abstractions of progressions of operations from/in S, especially since there's no definition of "computation" in the paper. — Arthur Rubin | (talk) 22:43, 4 April 2007 (UTC)
You seem to have missed that DenoteS is the least fixed point of ProgressionS and obeys all of the Laws for Actors which axiomatically define computation.--71.198.216.63 07:29, 5 April 2007 (UTC)
So the "theorem" is primarily a definition of "computation" in the actor model. — Arthur Rubin | (talk) 13:29, 5 April 2007 (UTC)
You seem to have missed the point of the just previous comment that the Laws for Actors axiomatically define and characterize computation. It is then necessary to prove the Representation Theorem.--71.198.216.63 17:19, 5 April 2007 (UTC)
I think not. The statement
The denotation DenoteS of an Actor system S is the set of all computations of S.
Looks as if it might be more a definition of "computation" than of Denote, making the theorem a definition. I suppose "denote" or Denote may mean something different in Actor systems than in English. But even if "computation" is defined elsewhere, the theorem reads that "computations" are exactly time-abstracted timed progressions from the initial state. This should be trivial, and is trivial in all definitions of computation that I'm familiar with.
Can you explain how "computation" is defined so this not trivial? — Arthur Rubin | (talk) 17:40, 5 April 2007 (UTC)
Computation is defined and characterized earlier in the paper in terms of Actor laws. Because of the problem of unbounded nondeterminism, it is not trivial to develop a denotational characterization of the computations, which was first accomplished by Will Clinger in his dissertation that is highly recommended reading. What is Commitment? Physical, Organizational, and Social just has a simpler construction than Clinger. Concurrent computation is not the same as nondeterministic Turing Machine and lambda calculus computation.--71.198.216.63 19:32, 5 April 2007 (UTC)
I disagree. The word "computation" doesn't appear earlier in the paper. — Arthur Rubin | (talk) 20:58, 5 April 2007 (UTC)
It seems that you missed the immediately preceding section 3 titled "Actors and Events" whose first sentence is "Actors are the universal primitives of concurrent digital computation." This section presents some Actor laws which define and characterize concurrent computation.--71.198.216.63 21:57, 5 April 2007 (UTC)

(outdent)

Exactly. (Actor model) computations are exactly the time-abstracted timed progressions of (Actor) events. If that's not trivial, then there's something fundamentally wrong with the Actor model. (And what this might have to do with "logic programming", "logical programming", "logic of programming", or "login in programming" is not at all clear.)
The relationship is clearly explained in the previous version of Logic programming that was reverted by Ruud Koot: Computations that cannot be implemented by Logical Programming are outside the capabilities of the nondeterministic lambda calculus. Likewise the Representation Theorem for concurrency is a generalization of the denotational models of the nondeterministic lambda calculus (that do not embody unbounded nondeterminism). Note that Logical Programming as defined by Kowalski is a generalization of Logic Programming. Consequently Logic Programming is even more limited than Logical Programming.--71.198.216.63 17:56, 6 April 2007 (UTC)
For what it's worth, there's no evidence that the paper is published, so we can't use it a reference, anyway, other than as to Carl's opinion. — Arthur Rubin | (talk) 22:16, 5 April 2007 (UTC)


The paper was published in the refereed proceedings of COIN at AAMAS'06. A revised version is published in Springer Verlag Lecture Notes in Artificial Intelligence edited by Javier Vázquez-Salceda and Pablo Noriega.--71.198.216.63 18:00, 6 April 2007 (UTC)

[edit] Opening sentences and references should reflect widely-held views

The opening sentences of the current version of this article do not reflect widely-held views about logic programming. They criticize logic programming by suggesting it is a flawed variant of something else called "logical programming". In doing so, they steer the reader toward the article on "logical programming", which emphasizes the contribution of Carl Hewitt and other American AI researchers toward understanding the relationship between logic and computation. I have never heard of "logical programming" as distinct from logic programming, and this view of logic programming would surely not be endorsed by the logic programming community. (This is to say nothing of the fact that the current opening sentence is run-on and ungrammatical.)

The references section contains references that have very little to do with logic programming per se, and vastly overemphasize American AI researchers such as Sussman, Cordell Green, Hewitt, McCarthy and Winograd. All of these researchers are very important in the general field of logic as applied to AI, but have had little or no impact on logic programming per se. A rather egregious example of this is the presence of Hewitt's paper "The repeated demise of logic programming", a recent (2006) very informal workshop paper, when seminal papers from people like Colmerauer, van Emden, and David H. D. Warren are absent.

It's hard to escape the conclusion that the article was edited by someone with an overinflated view of Carl Hewitt's influence on logic programming. Hewitt's PLANNER system was very influential to AI in general -- there is no question of that. It is certainly important to point out the connection in this article. But it is completely unnecessary, and rather insulting to the field of logic programming, to suggest that logic programming is merely a flawed variant of Hewitt's and other American researchers' ideas.

A little about me: I did my PhD on semantics of logic programming languages in 1991, my thesis was published by Cambridge University Press, I have had articles on logic programming published in Theoretical Computer Science and Journal of Logic Programming, I originated the comp.lang.prolog FAQ and maintained it for several years, and I wrote the article on Prolog for the Macmillan Handbook of Programming Languages (ed. Peter Salus). I have had no bone to pick with Carl Hewitt before this day -- in fact, I found the article only because I was searching for a more printable version of "The repeated demise of logic programming".

I have been a Wikipedia contributor for a few months. I am not editing this article yet because I don't want to get into an edit war, and the article history seems to suggest that that will be the result. However, I certainly want to register my opposition to the opening sentences and the references section of the current article, and to state my opinion that they do not reflect widely-held views of logic programming.

JamesHAndrews 23:28, 10 April 2007 (UTC)JamesHAndrews

I have a question. What exactly is logic programming? The term seems to be used in various ways. For example “Algorithm = Logic + Control” uses forward reasoning as well as backward reasoning.--208.194.81.131 17:07, 15 April 2007 (UTC)


I agree with James Andrews and object to the edit "Revision as of 20:12, 9 April 2007 171.66.51.202 (Talk)(We think that Kowalski's proposal should be adopted that "logical programming" be used for the general sense of using logic as the language of programming.)"

I certainly did not propose this major alteration of the logic programming article. I had hoped that that the supporters of Carl Hewitt would be satisfied with presenting their own views in a new article on logical programming and would allow the logic progamming article to deal with its subject in its own terms.Robert Kowalski 12:33, 11 April 2007 (UTC)

It looks like some people at Stanford attempted to start a new article on Logical programming as you suggested but that it was reverted for some reason. Maybe you can do better.--70.231.229.132 01:08, 14 April 2007 (UTC)
It's the Brits vs the Americans!--64.134.12.226 04:57, 16 April 2007 (UTC)

[edit] What is Logic Programming?

That's a good question. I, for one, do not have an "exact" definition. I have written or contributed to three encylopedia articles about logic programming:

Hogger, C. and Kowalski, R., "Logic Programming" in Encyclopedia of Artificial Intelligence, (ed. S. Stuart) John Wiley and Sons Inc., 1987, pp. 544-558. Also revised article in second edition, 1992, pp. 873-891.

Kowalski, R., "Logic Programming Principles", in Encyclopedia of Computer Science and Engineering, Revised Edition, (eds. A. Ralston and E. Reilly), Van Nostrand Reinhold Company Inc., 1993 pp. 778-783. Fourth edition (eds. A Ralston , D Hemmendinger , E. Reilly) 2000.

Kowalski, R.A., “Logic Programming”, MIT Encyclopaedia of Cognitive Science (eds. R A Wilson and F C Keil) MIT Press, 1999, pp. 484-486.

The MIT Encyclopaedia article skirts the issue with the following characterisation:

"Logic programming is the use of logic to represent programs and of deduction to execute programs in logical form. To this end, many different forms of logic and many varieties of deduction have been investigated. The simplest form of logic, which is the basis of most logic programming, is the Horn clause subset of logic....."

The second sentence of the Algorithm = Logic + Contol paper, on the other hand, states:

"In this paper, we are concerned not only with the use of predicate logic as a programming language in its own right, but with its tool for the analysis of algortithms."

Like most concepts, the concept of logic programming does not seem to have an exact definition. However, there is a generally accepted view of logic progamming, which my three encyclopedia articles attempted to capture. This view is quite close to the current version of the wikipedia article,and rather different from Carl Hewitt's recent views. In fact, I was not aware that Carl Hewitt held such different views until he started editing the wikipedia article. Robert Kowalski 11:43, 16 April 2007 (UTC)

I don't understand. How do your views differ from Carl Hewitt?--208.194.81.131 16:27, 16 April 2007 (UTC)

It is a matter of getting the balance right. If you type "logic programming" into Google Scholar or just plain Google, you will get a good idea about the range of topics associated with logic programming. In my opinon, the wikipedia article should broadly reflect that range of activity. At the moment, it is not too bad, except for a large number of idiocyncratic references at the end of the article. On the other hand, there are several topics, such as inductive logic programming, datalog and meta-programming, still missing.Robert Kowalski 10:12, 17 April 2007 (UTC)

OK, but what is the disagreement with Hewitt?--64.134.12.226 15:12, 17 April 2007 (UTC)

Probably the best way to understand the disagreement with Hewitt is to look at the history of edits to the logic programming article.Robert Kowalski 17:22, 17 April 2007 (UTC)

We looked at the history and it's not clear what the disagreement is.--208.194.81.131 18:06, 17 April 2007 (UTC)

Is that the royal "we", the editoral "we", or a comment that multiple people are using the IP address (meaning all edits in the CH-dominated articles from that IP address should be reverted). — Arthur Rubin | (talk) 22:30, 17 April 2007 (UTC)

We are on wireless at a conference in which the Wikipedia is being cited as a great success!--208.194.81.131 00:02, 18 April 2007 (UTC)

BTW, wasn't Carl Hewitt banned?--208.194.81.131 16:59, 18 April 2007 (UTC)

He is banned from making autobiographical edits. As long as he doesn't repeatedly violate that ban he won't be fully banned from editing, meaning he is currently allowed to discuss issues on the talk page. This should be constructive comments, unless he wants to risk being ignored by the people who can decided to make changes to the article based on his comments. —Ruud 19:28, 18 April 2007 (UTC)

[edit] I don't get it

This article reads like one Ph.D. precisely defining logic programming to another Ph.D. who already knows what they're talking about. Definitions like "B1 and … and Bn implies H" don't help if you don't explain further. Break it down for me. How can you do anything with "B1 and … and Bn implies H"? This page would be a lot more useful if people who haven't already been exposed to logic programming can walk away understanding the gist of it. indil 20:41, 8 October 2007 (UTC)

I think all that's needed here is a simple and concrete (i.e. real world) example of backward and forward chaining, written so that a high school student could understand it. (Think "Sunday supplement"/"Time Magazine" level of detail and type of prose.) That should do the trick for the general reader. Otherwise, this is an excellent article. ---- CharlesGillingham (talk) 00:09, 7 December 2007 (UTC)

I agree that some examples would be helpful. I wonder why Arthur Rubin | (talk) reverted the example by Logperson.Robert Kowalski (talk) 09:58, 7 December 2007 (UTC)

Primarily the damaged Wikiformat. It's reinserted and reformatted, now. — Arthur Rubin | (talk) 13:31, 7 December 2007 (UTC)

[edit] Have the issues brought up in April 07 been resolved?

Does the article, as it stands today, represent a consensus view of what logic programming is? It's not clear from the discussion if these issues finally got resolved, or were just dropped. ---- CharlesGillingham (talk) 00:14, 7 December 2007 (UTC)

I think all editors without severe COI issues concur, but that's just me and Ruud. — Arthur Rubin | (talk) 00:53, 7 December 2007 (UTC)
Good to know. That's what it looked like. Thanks. ---- CharlesGillingham (talk) 02:21, 7 December 2007 (UTC)
Since then a new contribution has appeared: History of Logic Programming by Carl Hewitt. Since Hewitt is prohibited from editing the article, I added it to the external links.--171.66.49.67 (talk) 20:13, 8 March 2008 (UTC)

What does "COI" mean? I think the biggest remaining problem is the biased list of references at the end of the article, as point out by JamesHAndrews. Also, there are some areas, such as constraint logic programming, inductive logic programming and metaprogramming, missing. Robert Kowalski (talk) 09:58, 7 December 2007 (UTC)

COI is WP:COI, conflict of interest. I had forgotten about you, but most of the rest of the editors were essentially Carl Hewitt, who is banned from editing articles about him or his work. That has led some of us to keep CH's material in the rare instances that it actually appears to be relevant to the article, because he is banned from adding it. — Arthur Rubin | (talk) 13:39, 7 December 2007 (UTC)

[edit] Curry-Howard isomorphism

The Curry-Howard isomorphism is quite different from logic programming in the sense of this article. In this article, axioms are programs and proofs are computations. In the Curry-Howard isomorphism, proofs are programs, which is very different. A quick google search reveals no research relating the two. —Preceding unsigned comment added by Logperson (talk • contribs) 12:33, 26 February 2008 (UTC)

[edit] History of Logic Programming by Carl Hewitt

Please add History of Logic Programming by Carl Hewitt to the external links.--67.169.9.177 (talk) 20:43, 11 March 2008 (UTC)

The article became famous here when it was censored by the Wikipedia. Does anyone know why it was censored?--136.152.144.253 (talk) 20:25, 14 March 2008 (UTC)

Our professor says that Kowalski objected to the article which led to it being excised from the Wikipedia. He also said that the article is by far the best one on the history of logic programming (even though it is from Hewitt's point of view).--63.249.108.250 (talk) 20:44, 15 March 2008 (UTC)
Kowalski has nothing to do with. In fact, he seemed to agree that Hewitt's articles are signficant. No, this reference to Carl's article was deleted from this Wikipedia article because it appears to be a class project to add it, and Hewitt and his students are forbidden from adding material about Hewitt or by Hewitt. — Arthur Rubin (talk) 22:00, 15 March 2008 (UTC)
Perhaps they are referring to Kowalski's complaint to Ruud Koot on November 10, 2007--207.47.0.2 (talk) 05:15, 17 March 2008 (UTC)

Funny, same thing happened here. —Preceding unsigned comment added by 171.66.50.16 (talk) 00:05, 15 March 2008 (UTC)

Carl and his students are banned from editing information related to Carl, per an ArbComm decision. If someone else in the field, preferrably someone with an account, would add the material, it might stay. However, it appears the Carl means something completely different by "Logic programming" than we do, so it still couldn't be in this article. — Arthur Rubin (talk) 06:59, 15 March 2008 (UTC)
There is an interesting discussion in the article about the controversy between Kowalski and Hewitt as to what is logic programming. Sounds like the Wikipedia is firmly on the side of Kowalski--63.249.108.250 (talk) 20:44, 15 March 2008 (UTC)
I don't think Kowalski commented on this article. At least, I took no notice of it at the time. — Arthur Rubin (talk) 22:00, 15 March 2008 (UTC)
Perhaps they are referring to the fact that you are taking Kowalski's side in the controversy with Hewitt over the definition of logic programming.--207.47.0.2 (talk) 05:15, 17 March 2008 (UTC)
It is not Kowalski's side of the controversy. It is the commonly accepted notion of logic programming versus Hewitt's definition, which is actually a redefinition of a commonly understood concept, which can be found defined, as in this article, in all the usual AI textbooks, such as Russell-Norvig, Poole-Goebel-Mackworth, Lugar, and Nilsson. If there is a place in Wikipedia for this external link to Hewitt's views on this matter, it is better in the article on Carl Hewitt than in the article on logic programming. 136.187.112.157 (talk) 05:34, 17 March 2008 (UTC)
The article by Hewitt says that Logic Programming is "the logical deduction of computational steps". I looked at the Wikipedia article and in the textbooks, but there is no common short definition of Logic Programming. What do you think is the commonly accepted definition?--171.66.49.41 (talk) 20:30, 17 March 2008 (UTC)
Logic programming is evolving concept. Originally it meant only Horn clauses executed by SLD, which is complete for deriving logical consequences and also Turing complete,but was extended to Horn clauses with negation as failure executed by SLDNF. Other extensions include abductive logic programming and answer set programming. All these extensions share the idea that computation can be reduced to deduction.
Hewitt’s definition "the logical deduction of computational steps" is too vague to be definition. If you try to make it more precise it doesn’t make sense. In any case, why should one person redefine concept that has generally accepted understanding, even if it doesn’t have rigid definition. 136.187.112.157 (talk) 01:14, 18 March 2008 (UTC)
It does seem that our understand of logic programming has evolved with time. Arguably, the original logical lambda calculus of Church (the one with logical propositions) was the first real logic programming language.
Horn clause execution by SLD seems more like a hack because it only does backward chaining. Even Kowalski (who evidently coined the term "logic programming") has used forward chaining over the years.
Using the definition in his article, Hewitt argued persuasively that (at least for concurrent systems) that computation cannot be reduced to deduction. So we had better not take that as the definition :-)
So it seems that Hewitt's definition is good for some things. But I agree that is not as precise as we would like. So the question is: How can the Hewitt definition be improved?--171.66.60.193 (talk) 01:36, 18 March 2008 (UTC)
We concur :-) --BytesCafe (talk) 02:10, 18 March 2008 (UTC)
OK. So maybe not all computation can or should be reduced to deduction. But it is fair to say that logic programming is concerned with the part of computation that can be reduced to deduction. Certainly Turing computability can be reduced to deduction. On the other hand, there is no good purpose served by taking a familiar concept, which has a commonly accepted understanding and terminology, and changing that terminology to mean something different. We would then need new term for the old concept. Natural language then becomes unusable. It is more practical to introduce new term for new concept, such as “logical programming” for Hewitt’s idea, as he earlier suggested. 136.187.112.157 (talk) 03:26, 18 March 2008 (UTC)
Yes, it seems perfectly consistent with Hewitt's definition to say that logic programming is concerned with that part of computation that can be reduced to deduction. And you are right that Turing computability and indeed all of sequential nondeterministic computing can be reduced to deduction. Also all of the parallel lambda calculus can be reduced to deduction. All of these examples involve the logical deduction of computational steps. So there doesn't seem to be any conflict.--67.180.94.17 (talk) 04:54, 18 March 2008 (UTC)
But Hewitt’s “definition” is not really definition. Computation as deduction is also vague. Logic programming has generally understood meaning within a community of researchers, textbook writers and students. It is not correct for one person to impose own definition on everyone else. 136.187.112.157 (talk) 07:06, 18 March 2008 (UTC)
It seems that the "logical deduction of computational steps" is the best short form definition that we have so far. (Although Hewitt has clearly been a proponent of this definition; it is not clear that he first invented it.) Of course, anyone who has a better idea is free to propose it so certainly no one person has a monopoly here.
Also the community seems to be deeply divided between a resolution camp and a concurrency camp, both of which go back to the genesis of the field. So there doesn't seem to be a single generally understood meaning of logic programming.--207.47.0.2 (talk) 08:05, 18 March 2008 (UTC)
Look in any AI textbook. Do a google search. You will see there is generally understood notion of logic programming. It does not have rigid and precise definition. If you want to introduce a new or different notion, you should use a different name, maybe logical programming, for example. 136.187.112.157 (talk) 08:24, 18 March 2008 (UTC)
The divide is deeply entrenched in the literature of some four decades. Google Scholar has plenty of publications by both sides.
I'm afraid that trying to introduce "logical programming" at this point would simply cause more confusion. What would we say is the difference between "logical programming" and "logic programming"? --207.47.0.2 (talk) 14:47, 18 March 2008 (UTC)
I'd like to see evidence that anyone other than Hewitt uses "logic programming" the way Hewitt does. Many of his concepts are unique to him and are more-or-less rejected by the consensus of all who use the related concepts. — Arthur Rubin (talk) 15:10, 18 March 2008 (UTC)
It would be useful to know which related concepts you have in mind. That way we could have a better idea who you are talking about.--171.66.48.34 (talk) 18:07, 18 March 2008 (UTC)
It seems that this controversy snuck up on Kowalski and Hewitt. They didn't realize that they had been talking past each other for decades!--171.66.48.34 (talk) 16:45, 18 March 2008 (UTC)

What I find most curious is that Kowalski doesn't have a succinct counterproposal to defining logic programming as the logical deduction of computational steps.--12.48.196.50 (talk) 14:10, 19 March 2008 (UTC)

We were also wondering.--BytesCafe (talk) 01:54, 20 March 2008 (UTC)
If Kowalski's position is so wishy-washy, why does it have any credibility?--70.231.241.69 (talk) 17:12, 22 March 2008 (UTC)
"We" were wondering while all the IPs and BytesCafe refer to themselves as "we". We (most Wikipedians reading this discussion) believe this to be a class project, and therefore subject to deletion. We (Wikipedia) do not recognize "role accounts", and it's policy that they should be blocked. — Arthur Rubin (talk) 17:24, 22 March 2008 (UTC)
You dodged an interesting question, namely, "Why has the Kowalski 'wishy-washy' approach persisted?" There must be sociotechnical reasons.--70.231.241.69 (talk) 21:23, 22 March 2008 (UTC)
What I find curious is that this well-defined definition has retained use, in spite of the fact that it redefines both words of the term in order to make it fit. I think we would need references, other than Hewitt's works, that use the term as he defines it, in order for it to be included. As an aside, could the multiple IPs identify themselves? I think most of them are students in one of Carl's (or his student's) classes, or possibly as class project to get Hewitt's definition in Wikipedia. — Arthur Rubin (talk) 14:27, 19 March 2008 (UTC)
Now I get it: NPOV is any published point of view except Hewitt's :-) —Preceding unsigned comment added by 71.142.107.205 (talk) 02:45, 21 March 2008 (UTC)
Hewitt's point of view is notable, in an article other than one specifically about him and his concepts, only if someone other than he or his students thinks it's notable. That restricts the scope considerably. — Arthur Rubin (talk) 13:23, 21 March 2008 (UTC)
In other words, *you* think it's not notable.--63.249.90.198 (talk) 20:45, 21 March 2008 (UTC)
Well, I do think it's not notable, but, because Hewitt spammed all articles about subject in which he made a contribution, no matter how minor, we can't take his word about anything any more. So we need independent sources that his contributions are notable before they can be included. Kowalski would probably do. — Arthur Rubin (talk) 23:46, 21 March 2008 (UTC)
Most curious, this opinion by Arthur Rubin! Who is he? —Preceding unsigned comment added by 209.76.192.5 (talk) 06:16, 9 April 2008 (UTC)
I'm basing my opinion, not on any special knowledge of logic programming, but on the on-Wikipedia actions of those championing Carl Hewitt's views. Unless you want to revisit the ArbComm decision banning Carl and his students from editing Wikipedia articles about Carl or his views, this definition of logic programming cannot stand without proof of notability. — Arthur Rubin (talk) 12:59, 9 April 2008 (UTC)
And what do you have against Hewitt's artice? Everybody in the field seems to know about it and the controversy with Kowalski. —Preceding unsigned comment added by 209.76.192.5 (talk) 14:34, 9 April 2008 (UTC)
All the anons posting here know about Hewitt's article. Whether anyone else does has yet to be determined. — Arthur Rubin (talk) 21:56, 9 April 2008 (UTC)
Do you actually personally know any of the members of the community?98.210.237.109 (talk) 09:32, 10 April 2008 (UTC)
I disagree. We have lots of things about Hewitt here.--ComputerHistoryMuseum (talk) 18:49, 2 April 2008 (UTC)
Another entry in the WP:SOCK drawer. — Arthur Rubin (talk) 20:01, 2 April 2008 (UTC)
Yeah, it would be good to hear from Kowalski. Didn't he use to edit the Wikipedia?--98.210.241.114 (talk) 05:24, 22 March 2008 (UTC)
Logic Programming has probably retained use because it describes certain phenomena. The question is "Can we scientifically characterize the phenomena?"
PS. You don't seem to know much about Silicon Valley :-) --BytesCafe (talk) 02:22, 20 March 2008 (UTC)

[edit] Fernando Pereira the photographer

Can somebody please unlink the name Fernando Pereira in the article? The link is going to a photographer, not the logician. Thanks, EdJohnston (talk) 15:25, 13 May 2008 (UTC)