Programming in logic vs. Programming in PROLOG 
Author Message
 Programming in logic vs. Programming in PROLOG


Quote:

>> ... 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:


Quote:
> 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
                (_)>(_)

+----------------------------------------------------------------------+

| 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) |
+----------------------------------------------------------------------+



Mon, 03 Aug 1992 10:46:15 GMT  
 Programming in logic vs. Programming in PROLOG

Quote:
> 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



Fri, 07 Aug 1992 13:04:37 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Programming in PROLOG vs. Programming in Logic

2. amazing new facts about (logic) programming and Prolog :-)

3. Purifying Prolog, Monads for Logic Programming?

4. Logic program (Prolog) Profiling

5. More Web Pages for Logic (Prolog) Programming

6. object-oriented logic programming and prolog.

7. MICRO PROLOG / Logic Programming Associates ?

8. Logic programming languages other than Prolog ?

9. OOP vs Logic Programming II

10. OOP vs Logic Programming II

11. OOP vs Logic Programming?

12. Please help me implement Generalized Annotated Logic Programs (GAP) in Prolog

 

 
Powered by phpBB® Forum Software