Talk:Logic programming

From Wikipedia, the free encyclopedia

You have new messages (last change).

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/. 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)
Retrieved from "http://en.wikipedia.org../../../l/o/g/Talk%7ELogic_programming_8720.html"