pf@romeo.cs.duke.edu (Pierre Flener c/o awb) (02/15/90)
In article <...> jha@lfcs.ed.ac.uk (Jamie Andrews) writes: > In article <...> rar@KRONOS.ADS.COM (Bob Riemenschneider) writes: >> ... if you forget about the relation between Prolog and >> logic programming, ... > I'm not sure what you mean by "the relation between Prolog > and logic programming" -- it sounds like you think these are > separate concepts. Provided I correctly interpret Jamie's reaction as surprise and disagreement, I would like to jump in here and make a statement that is funnily not universally recognized: "Programming in PROLOG" is NOT equal to "Programming in Logic" (!) These concepts are related, but distinct! Let me elaborate on this viewpoint. "Programming in Logic" can be defined as (1) coming up with a logic description of the relation to be implemented [declarative aspect], and (2) executing this description so as to compute results [procedural aspect]. The advantages of this approach are (1) that such a logic description is totally declarative (order is irrelevant, ...); (2) there is no bias towards sequential or parallel execution; (3) there is no bias towards a particular use of the description, i.e. this is truly relational programming and complete reversibility is achieved; (4) and so on. Now, are these criteria satisfied when you program in PROLOG? NO! Indeed, (1) PROLOG's inference engine is neither sound, nor complete, nor fair [because of the search rule, lack of occurs-check, and negation-as- failure]; (2) PROLOG includes control predicates [cut, fail, ...] and extra- logical predicates [I/O, ...] that have nothing to do with logic; (3) true reversibility is a rare phenomenon in PROLOG programs; (4) PROLOG's syntax is only a subset of [first order] logic; (5) and so on. There are basically 4 ways to face this dilemma: (1) "Programming in PROLOG = Programming in PROLOG"; i.e. you forget about what makes the concept of "Programming in Logic" so attractive; (2) "Programming in PROLOG = Programming in NEW-Logic"; i.e. you change the logic in order to re-establish the equality; (3) "Programming in DREAM-LOG = Programming in Logic"; i.e. you change the programming language in order to re-establish the equality; (4) "Programming in PROLOG = Programming in Logic + ..."; i.e. you provide the tools that allow you to program in Logic, and THEN convert your program into a PROLOG program. The latter approach is without doubt the wisest one. This is the goal we pursue in the FOLON research project at the University of Namur (Belgium). This project is based upon Yves Deville's Ph.D. thesis "Logic Programming- Systematic Program Development", an updated version of which is soon to be published by Addison Wesley (Reading, Massachusetts). This insightful book can be loosely summarized as follows: starting from the above viewpoint on Programming in Logic, a 3-step methodology is proposed: (1) elaboration of a specification; (2) construction of a logic description that is correct & complete wrt the specification [sole concern is the declarative semantics of Logic]; (3) derivation of a PROLOG program that is correct & complete wrt the specification [i.e. coping with everything that makes the difference between Logic and PROLOG programming]. Let me illustrate our approach with the following problem that has been recently posted to the net: In article <...> anjo@swi.psy.uva.nl (Anjo Anjewierden) writes: > Below is a definition of list_length/2 (length/2 in Edinburgh > compatibles). I would like to know whether there is a better/shorter > solution that handles all cases and is deterministic given certain > calling patterns (see definition below). > [procedures deleted] Well, using our approach, you would elaborate the following specification: ... directionality: in(ground,ground):out(ground,ground) <0-1> in(ground,var) :out(ground,ground) <1-1> in(var,ground) :out(ground,ground) <1-1> in(var,var) :out(ground,ground) <*-*> ... and construct the following logic description (LD): length(L,N) <==> L=[] & N=0 v L=[H|T] & length(T,M) & add(M,1,N) (quantifications being implicit and obvious) NOW, [hopefully] upon pressing a button, this LD is derived into 4 PROLOG programs, one for each of the 4 specified directionalities ! (taking into account peculiarities of your interpreter) Anjo's programs, as well as Lee Naish's and Andreas Stolcke's enhancements (!) should be obtained very easily, since all the considerations used to write them have been considered in our framework! Any comments on our approach ??? o _ /-_ Pierre (_)>(_) +----------------------------------------------------------------------+ | Pierre Flener email: pf@cs.duke.edu "The only way to get | | Dept. of Comp. Science phone: (919) 660-6526 rid of a temptation | | Duke University is to yield to it." | | Durham, NC 27706 (USA) (Oscar Wilde) | +----------------------------------------------------------------------+
lee@munnari.oz.au (Lee Naish) (02/19/90)
In article <17578@duke.cs.duke.edu> pf@romeo.cs.duke.edu (Pierre Flener c/o awb) writes: > a 3-step methodology is >proposed: (1) elaboration of a specification; (2) construction of a logic >description that is correct & complete wrt the specification [sole concern >is the declarative semantics of Logic]; (3) derivation of a PROLOG program >that is correct & complete wrt the specification [i.e. coping with >everything that makes the difference between Logic and PROLOG programming]. > >Any comments on our approach ??? Various Gurus and True Believers of logic programming have been saying this sort of thing for a long time. I don't think its quite that simple. Efficient Prolog programs are NOT equivalent to natural specifications. Take append for example. In the natural specification, all arguments must be lists. This is not true of the standard (efficient) coding. If the coding was changed, so it is equivalent to the specification, an extra test would be needed: append([], A, A) :- list(A). append(A.B, C, D) :- append(B, C, D). If the specification of append(A,B,C) was changed, so it is equivalent to the normal coding, it would be: A is a list, B is a list if and only if C is a list, and C has the same "elements" as A and B in that order. The definition of an element needs to be extended to non-lists. The asymmetry of the specification with respect to the first two arguments reflects the implementation of lists. If the representation of lists allowed access to the last element faster than the first element then the specification of an efficient append would be different. This is not a desirable property of specifications. It is tempting to use an "incomplete" specification such as If A and B are lists, C is B concatenated onto A. However, when negation as failure is used, incompleteness turns into unsoundness. An append definition which is correct with respect to the definition above can cause incorrect answers to reasonable queries. This is all discussed in the following paper: %A Lee Naish %T Specification = program + types %J Proceedings of the Seventh Conference on the Foundations of Software Technology and Theoretical Computer Science %C Pune, India %D December 1987 %E Kesav V. Nori %O published as Lecture Notes in Computer Science 287 by Springer-Verlag %P 326-339 I now have an almost final draft of a revised and extended version, entitled "Types and the intended meaning of logic programs". lee