Lisp LIST vs. Prolog LIST 
Author Message
 Lisp LIST vs. Prolog LIST



Quote:
> Hello Prologgers,

>   I'm curious with reason behind implementing Prolog's List as the way
> it is
> when Lisp handle its List in a way that feel more natural to me.

>   Prolog's list is a link list like thing, and the prolog programmers
> can
> feel its presence when using Prolog's LISTs.  Lisp also use link list
> for
> implementating its Lists, but it is invisible and it feel easier.

>   I'm mainly interested in the reasoning behind Prolog's choice of List,
> not
> to compare which feature is better or what

>   Any thoughts?

I thought that Prolog and Lisp had basically the same structure for
lists, the differences are typographical. (My Lisp is a little rusty so I
am ready to be corrected if I have this wrong).
Particular implementations may have all sorts of clever implementations
to speed up processing but this isn't normally visible to the user.




Sat, 27 Jul 1996 22:00:20 GMT  
 Lisp LIST vs. Prolog LIST
Hi!
 I think of the Prolog and LISP lists data structures as the same thing.
Basicly the operations you can perform on each are the same just the syntax
is a little different.

        car('(a,b,c))  <--=-->  [ a | _ ]
        cdr('(a,b,c))  <--=-->  [ _ | Rest]

 What i always wanted to know is why they didn't implement a primitive that
would work like this.

         if you have a list L thats looks like this:

                   L = [a,b,c,d,e]

         and you call a predicate foo:

                   foo(L).      

         they why can't you do this:

                foo([Front | c | Back]).

         with:

                Front = [a,b],
                Back = [c,d].

 I don't know about you but sometimes i feel that would be really handy.

-------------------------------------------------------------------------------
 ___                                               "I want the one I can't have
  _  _        +  +                                  and it's driving me mad
   _   _  ___  _  _                                 it's written all over my

     _  _   _    _  _                                         -I Want the One
      ___    _    ____                                         I Can't Have
-------------------------------------------------------------------------------



Mon, 29 Jul 1996 06:15:24 GMT  
 Lisp LIST vs. Prolog LIST

Quote:
> What i always wanted to know is why they didn't implement a primitive that
>would work like this.
>     if you have a list L thats looks like this:
>               L = [a,b,c,d,e]
>     and you call a predicate foo:
>               foo(L).      
>     they why can't you do this:
>            foo([Front | c | Back]).
>            Front = [a,b],
>            Back = [c,d].

I guess you mean Back = [d,e].

Well... compared to what they did implement, this one is substantially
more work (because it doesn't map directly onto the pointer structure),
and it's nondeterministic.  Consider unifying [X|c|Y] with [a,b,c,d,c,d,e]
for example.

Lists are a directional data structure.  They are much easier to access
from the beginning than from the end.   Bidirectional lists do exist,
of course, but they aren't the same thing and Prolog provides no special
syntax for them.
--
< Michael A. Covington, Assc Rsch Scientist, Artificial Intelligence Programs >



Mon, 29 Jul 1996 08:07:36 GMT  
 Lisp LIST vs. Prolog LIST

Quote:
>   I'm curious with reason behind implementing Prolog's List as the way it is
> when Lisp handle its List in a way that feel more natural to me.

I don't understand.  Prolog's lists are 100% equivalent to LISP's.  Consider

        []                      ()
        [a]                     (A)
        [a, b, c, d]            (A B C D)
        [a | b]                 (A . B)
        [a, b, c | d]           (A B C . D)

The data structures are isomorphic.

Bye,
        Jens.
--


---------------------------------+---------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.



Tue, 30 Jul 1996 04:59:48 GMT  
 Lisp LIST vs. Prolog LIST

Quote:
>  I'm curious with reason behind implementing Prolog's List as the way it is
>when Lisp handle its List in a way that feel more natural to me.

I'm curious about your question.  Prolog lists and Lisp lists are identical.
(Indeed, in Poplog, which is a system offering Prolog, Lisp, Pop-11, and
ML, plus interfaces to other languages, Prolog lists and Lisp lists are
literally the very same objects.)

Quote:
>  Prolog's list is a link list like thing, and the prolog programmers can
>feel its presence when using Prolog's LISTs.  Lisp also use link list for
>implementating its Lists, but it is invisible and it feel easier.

What _are_ you talking about?  The Lisp operations on lists are
        (null X)                - is X the empty list?
        '()                     - make an empty list
        (consp X)               - is X a non-empty list?
        (cons D L)              - make a non-empty list
        (car X)                 - return the head of X
        (cdr X)                 - return the tail of X
        (rplaca X D)            - replace the head of X with D
        (rplacd X L)            - replace the tail of X with L
The Prolog operations on lists are
        X = []                  - is/make X the empty list?
        X = [H|T]               - is/make X a pair with head H, tail T
For the life of me, I can't see Prolog revealing anything here that Lisp
doesn't.  On the contrary, Lisp gives you _more_ access to the implementation
(via rplaca/rplacd) than Prolog does.

Quote:
>  I'm mainly interested in the reasoning behind Prolog's choice of List, not
>to compare which feature is better or what

The only difference is that Prolog doesn't let you smash a list once built.
Even the syntax is almost the same:
        Lisp    (       space   .       )
        Prolog  [       comma   |       ]

I can testify that I for one am _never_ aware of pointers when writing
Prolog list-hacking code.
--

In Victoria, if a burglar injures himself breaking into your house,
_he_ can sue _you_ under the Occupiers' Liability Act 1983.  Nice one, pols!



Fri, 02 Aug 1996 16:10:27 GMT  
 Lisp LIST vs. Prolog LIST

Quote:
>What i always wanted to know is why they didn't implement a primitive that
>would work like this.

>     if you have a list L thats looks like this:

>               L = [a,b,c,d,e]
>     and you call a predicate foo:
>               foo(L).      
>     they why can't you do this:
>            foo([Front | c | Back]).

>     with:

>            Front = [a,b],
>            Back = [c,d].
> I don't know about you but sometimes i feel that would be really handy.

Look at any good book or article about the theory of unification.
In effect, you are asking that Prolog operation should build in the
append operation (which has a zero and is associative but not commutative).
Note that under that interpretation
        A <> B = C <> D
(<> being append) has INFINITELY many solutions, whereas for Prolog
unification as we know it, any equation has at most ONE solution.

You can get the effect you want by using
        append(Front, [c|Back], FooArgument),
        foo(FooArgument)

--

In Victoria, if a burglar injures himself breaking into your house,
_he_ can sue _you_ under the Occupiers' Liability Act 1983.  Nice one, pols!



Fri, 02 Aug 1996 16:14:07 GMT  
 Lisp LIST vs. Prolog LIST

   > What i always wanted to know is why they didn't implement a primitive that
   >would work like this.
   >  if you have a list L thats looks like this:
   >            L = [a,b,c,d,e]
   >  and you call a predicate foo:
   >            foo(L).      
   >  they why can't you do this:
   >         foo([Front | c | Back]).
   >         Front = [a,b],
   >         Back = [c,d].

   I guess you mean Back = [d,e].

   Well... compared to what they did implement, this one is substantially
   more work (because it doesn't map directly onto the pointer structure),
   and it's nondeterministic.  Consider unifying [X|c|Y] with [a,b,c,d,c,d,e]
   for example.

   Lists are a directional data structure.  They are much easier to access
   from the beginning than from the end.   Bidirectional lists do exist,
   of course, but they aren't the same thing and Prolog provides no special
   syntax for them.

This has not so much to do with directionality but with (as you
implied) limitation of first-order unification. Using higher-order
terms (as in lambda-prolog) you can do this kind of pattern matching
using a single unification step.

You represent lists as lambda-abstractions where the tail of the list
is the bound variable. You can then append lists in a single step
using beta-reduction and decompose the list in arbitrary segments
using higher-order unification. Such unifications are indeed
nondeterministic.

The example above becomes - in slightly extended ordinary Prolog
syntax where "\" stands for lambda (NOT lambda Prolog syntax):

        L = \X.[a,v,c,d,e | X],

        foo(\X.Front([c|Back(X)]))
        Front = \X.[a,b|X]
        Back = \X.[d,e|X]
--

Swedish Institute of Computer Science           Phone (intn'l): +46 8 752 15 09
Box 1263                                        Telefon (nat'l): 08 - 752 15 09
S-164 28  KISTA, SWEDEN                         Fax: +46 8 751 72 30



Fri, 02 Aug 1996 17:05:41 GMT  
 Lisp LIST vs. Prolog LIST

Quote:


>    > What i always wanted to know is why they didn't implement a primitive that
>    >would work like this.
>    >     if you have a list L thats looks like this:
>    >               L = [a,b,c,d,e]
>    >     and you call a predicate foo:
>    >               foo(L).      
>    >     they why can't you do this:
>    >            foo([Front | c | Back]).
>    >            Front = [a,b],
>    >            Back = [c,d].
> This has not so much to do with directionality but with (as you
> implied) limitation of first-order unification. Using higher-order
> terms (as in lambda-prolog) you can do this kind of pattern matching
> using a single unification step.

> You represent lists as lambda-abstractions where the tail of the list
> is the bound variable. You can then append lists in a single step
> using beta-reduction and decompose the list in arbitrary segments
> using higher-order unification. Such unifications are indeed
> nondeterministic.

> The example above becomes - in slightly extended ordinary Prolog
> syntax where "\" stands for lambda (NOT lambda Prolog syntax):

>    L = \X.[a,v,c,d,e | X],

>    foo(\X.Front([c|Back(X)]))
>    Front = \X.[a,b|X]
>    Back = \X.[d,e|X]

This data-structure is called "function list" in a paper that Pascal
Brisset and I published in ICLP91.  It can be tracked down to Hughes'
work on a similar data-structure for functional languages.

With this data-structure, it is a good idea to define combinators for
the basic operations on lists.

       Lars-Henrik's notation   LambdaProlog's notation
NIL    \z.z                     z\z                       % identity
CONC   \l.\r.\z.(l (r z))       l\r\z\(l (r z))           % function composition
UNIT   \e.\z.[e|z]              e\z\[e|z]

That NIL and CONC are the operations of a monoid can even be proven in
LambdaProlog.

Then the example above becomes
        L = z\[a,b,c,d,e|z],
        foo L.

foo (CONC Front (CONC (UNIT c) Back)) .

Another application is:

member  Elem  (CONC _ (CONC (UNIT Elem) _)) .

Function lists are a declarative variant of difference lists.  When
concatenating, declarativeness may come to the price of a copy of the
left concatenand, while difference lists will "only" modify it.  Some
care avoids most unnecessary copies.

Higher-order order unification is not strictly necessary for unifying
strings.  String unification is decidable and infinitary, but
higher-order order unification is semi-decidable and infinitary.

Olivier Ridoux



Fri, 02 Aug 1996 19:48:44 GMT  
 Lisp LIST vs. Prolog LIST

   >         L = \X.[a,v,c,d,e | X],
   >
   >         foo(\X.Front([c|Back(X)]))
   >         Front = \X.[a,b|X]
   >         Back = \X.[d,e|X]

   This data-structure is called "function list" in a paper that Pascal
   Brisset and I published in ICLP91.  It can be tracked down to Hughes'
   work on a similar data-structure for functional languages.

The basic idea was there already in Church numerals.
--

Swedish Institute of Computer Science           Phone (intn'l): +46 8 752 15 09
Box 1263                                        Telefon (nat'l): 08 - 752 15 09
S-164 28  KISTA, SWEDEN                         Fax: +46 8 751 72 30



Fri, 02 Aug 1996 21:59:52 GMT  
 Lisp LIST vs. Prolog LIST

   > What i always wanted to know is why they didn't implement a primitive that
   >would work like this.
   >  if you have a list L thats looks like this:
   >            L = [a,b,c,d,e]
   >  and you call a predicate foo:
   >            foo(L).      
   >  they why can't you do this:
   >         foo([Front | c | Back]).
   >         Front = [a,b],
   >         Back = [c,d].

   I guess you mean Back = [d,e].

   Well... compared to what they did implement, this one is substantially
   more work (because it doesn't map directly onto the pointer structure),
   and it's nondeterministic.  Consider unifying [X|c|Y] with [a,b,c,d,c,d,e]
   for example.

append(Front, [c|Back], L) works just fine.  and in the second
example, it offers both alternatives.  people forget just how powerful
append is.

this isn't a primitive in the language, but it runs as fast as any
matching predicate is going to run (except for any discrimination
against user functions).



Fri, 02 Aug 1996 15:02:04 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. Pymacs - tuples/lists .vs. proper-lists/vectors

2. prolog list -> tcl list

3. Newbie Question, list = list + x VS append (x)

4. abstract interfaces vs lazy lists (was: AL in Prolog)

5. Intersection of multiple lists/list of lists

6. DXOracle / PyADO - convert lists of tuples to list of lists

7. Prolog/Lisp vs other languages (was Simple Prolog Question)

8. How can I convert a SATHER list of lists to a TCL list of lists?

9. appending list (with list within) structure in K

10. LIST BOX AND DROP DOWN LIST BOX

11. Listing all parents relating to child list??

12. Have edit in place list box and want to updat from dropdown list

 

 
Powered by phpBB® Forum Software