Prolog - This Logo program in Prolog?

Author

This Logo program in Prolog?

pineapple.link@yahoo.com

2007-09-03, 8:08 am

Ran across a posting in the comp.lang.lisp. Someone wanted to
translate a (very short) Logo program into Lisp. The thread got many
postings, in various languages actually, but none in Prolog.

I wondered if a Prolog program could be written as short (or close in
length) to the Logo program, if not shorter. I started a solution
myself, but wondered what some of the gurus might come up with.

The Logo program, and sample output (from
http://www.cs.berkeley.edu/~bh/logo-sample.html):

-------------------------------------------
to choices :menu [:sofar []]
if emptyp :menu [print :sofar stop]
foreach first :menu [(choices butfirst :menu sentence :sofar ?)]
end

And here's how you use it. You type

choices [[small medium large]
[vanilla [ultra chocolate] lychee [rum raisin] ginger]
[cone cup]]

and Logo replies

small vanilla cone
small vanilla cup
small ultra chocolate cone
small ultra chocolate cup
small lychee cone
small lychee cup
small rum raisin cone
small rum raisin cup
small ginger cone
small ginger cup
medium vanilla cone
medium vanilla cup
medium ultra chocolate cone
medium ultra chocolate cup
medium lychee cone
medium lychee cup
medium rum raisin cone
medium rum raisin cup
medium ginger cone
medium ginger cup
large vanilla cone
large vanilla cup
large ultra chocolate cone
large ultra chocolate cup
large lychee cone
large lychee cup
large rum raisin cone
large rum raisin cup
large ginger cone
large ginger cup

---------------------------------

The comp.lang.lisp thread:
http://groups.google.co.th/group/co...78222ff885e864a

pineapple.link@yahoo.com

2007-09-03, 8:08 am

Whoops - note that the Logo program takes an arbitrarily long list of
elements (not fixed in size).

Bart Demoen

2007-09-03, 8:08 am

pineapple.link@yahoo.com wrote:
> Ran across a posting in the comp.lang.lisp. Someone wanted to
> translate a (very short) Logo program into Lisp. The thread got many
> postings, in various languages actually, but none in Prolog.
>
> I wondered if a Prolog program could be written as short (or close in
> length) to the Logo program, if not shorter. I started a solution
> myself, but wondered what some of the gurus might come up with.
>
> The Logo program, and sample output (from
> http://www.cs.berkeley.edu/~bh/logo-sample.html):

choices(ChoiceLists) :- choices(ChoiceLists,Choice), writeln(Choice).

choices([],[]).
choices([CL1|CLs],[Choice|Choices]) :-
member(Choice,CL1),
choices(CLs,Choices).

run :-
choices(
[[small,medium,large],
[vanilla,'ultra chocolate',lychee, 'rum raisin',ginger],
[cone,cup]]
).

I had no time to make it shorter :-)

Make sure to type the query ?- run, fail. in SWI, otherwise you will see only one
line of output !

Cheers

Bart Demoen

Markus Triska

2007-09-03, 8:08 am

pineapple.link@yahoo.com writes:

> I wondered if a Prolog program could be written as short (or close in
> length) to the Logo program, if not shorter.

choices([[small, medium, large],
[vanilla, 'ultra chocolate', lychee, 'rum raisin', ginger],
[cone, cup]]).

member_(Ls, L) :- member(L, Ls).

Example query, tested with SWI-Prolog:

%?- choices(Cs), maplist(member_, Cs, C), maplist(format("~w "), C), nl, fail.
%@ small vanilla cone
%@ small vanilla cup
%@ small ultra chocolate cone
%@ small ultra chocolate cup
%@ small lychee cone
etc.

The extensional menu can also be made available as a Prolog term easily:

%?- choices(Cs), findall(C, maplist(member_, Cs, C), Menu).
@ Menu = [[small, vanilla, cone], [small, vanilla, cup] ...

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

pineapple.link@yahoo.com

2007-09-03, 7:06 pm

Amazing. Thanks.

student

2007-09-03, 7:06 pm

pineapple.link@yahoo.com wrote:

/*
And here's how you use it. You type

choices [[small medium large]
[vanilla [ultra chocolate] lychee [rum raisin] ginger]
[cone cup]]

and Logo replies

small vanilla cone
small vanilla cup
small ultra chocolate cone
small ultra chocolate cup
small lychee cone
small lychee cup
[...]
*/

/*

Generally speaking, in Prolog we start by presenting the Prolog
Inference Engine (PIE) with a description of the problem that is to be
solved. In the present case, I take it the problem to be solved may
fairy be described as follows:

*/

parameter1(small).
parameter1(medium).
parameter1(large).

parameter2(vanilla).
parameter2(ultra_chocolate).
parameter2(lychee). % yum!
parameter2(rum_raisin).
parameter2(ginger).

parameter3(cone).
parameter3(cup).

choices :-
parameter1(Size),
parameter2(Flavor),
parameter3(Serving),
write(Size),spacer,write(Flavor),spacer,
write(Serving),nl,
backtrack.
choices :-
write('No more choices.').

spacer :-
write(' ').

backtrack :-
fail.

/*

We elicit solutions to the problem by iteratively interrogating our
description, checking the answers it gives, and revising the description
until we are satisfied that it is correct and complete.

*/

:- choices.

/*

Finally, when we feel satisfied that our description is correct and
complete, we may proceed to the matter of proving that it is complete
and correct.

*/

-- billh

Bart Demoen

2007-09-04, 8:05 am

student wrote:

> I take it the problem to be solved may
> fairy be described as follows:
....
> parameter1(small).
....
> parameter2(ginger).
>
> parameter3(cone).

I think you overlooked something the OP wrote:

> note that the Logo program takes an arbitrarily long list of
> elements (not fixed in size).

Your program wouldn't work for an extra dimension of choice, which you
would represent as parameter4/1 I assume, but your program needs to be
changed as well.
Also the Logo program caters for extra choices without needing changes.

Cheers

Bart Demoen

Carlo

2007-09-04, 7:09 pm

"Markus Triska" <triska@logic.at> ha scritto nel messaggio
news:m1ir6sdmtx.fsf@gmx.at...
>
> pineapple.link@yahoo.com writes:
>
>
> choices([[small, medium, large],
> [vanilla, 'ultra chocolate', lychee, 'rum raisin', ginger],
> [cone, cup]]).
>
> member_(Ls, L) :- member(L, Ls).
>
> Example query, tested with SWI-Prolog:
>
> %?- choices(Cs), maplist(member_, Cs, C), maplist(format("~w "), C), nl,
> fail.

As usual, Prolog at its best!
But, I don't understand the need for member_/2.

? :- choices(Cs), maplist(member, C, Cs), maplist(format("~w "), C), nl,
fail.

produces the correct result as well.
Maybe a stylistic choice?

Bye Carlo.

Markus Triska

2007-09-04, 7:09 pm

"Carlo" <ccape@tin.it> writes:

> ? :- choices(Cs), maplist(member, C, Cs), maplist(format("~w "), C),nl,fail.
> produces the correct result as well.

Indeed; your solution is preferable.

> Maybe a stylistic choice?

The correct term is, I think, "boneheaded choice".

bart demoen

2007-09-05, 7:06 pm

On Mon, 03 Sep 2007 04:17:35 -0700, pineapple.link wrote:

> Ran across a posting in the comp.lang.lisp. Someone wanted to
> translate a (very short) Logo program into Lisp. The thread got many
> postings, in various languages actually, but none in Prolog.
>
> I wondered if a Prolog program could be written as short (or close in
> length) to the Logo program, if not shorter. I started a solution
> myself, but wondered what some of the gurus might come up with.
>
> The Logo program, and sample output (from
> http://www.cs.berkeley.edu/~bh/logo-sample.html):
>
> -------------------------------------------
> to choices :menu [:sofar []]
> if emptyp :menu [print :sofar stop]
> foreach first :menu [(choices butfirst :menu sentence :sofar ?)]
> end

No more Prolog solutions have been posted since some time now, so maybe
it is time to do a wrapup.

Both my and Markus' solution show that the shortness of a program in a
particular language depends crucially on what is (considered) part of the
language: I assumed member/2 and writeln/1, Markus took maplist/3 and
format/2.

"Pure" Prolog only offers unification and backtracking as extras over
(most) other languages. That in itself is powerful enough to allow for
short and elegant solutions to seemingly complicated problems.

ISO-Prolog adds control (!/0, if-then-else, ...), I/O, arithmetic,
persistent data (assert - yuk), aggregates and a some other term
manipulative actions.

ISO does not add syntactic shorthands for iteration/recursion (like
foreach in Logo), or any other list meta-predicates (like maplist).

Given that other languages (or their designers) do not shy away from
adding sugar and thus promote their language by expressiveness, and given
that Markus' solution of the OP's problem is way shorter than the Logo
one, what direction should Prolog take ?
Make more constructs/predicates part of the language or not ?

It's meant to be a poll ! Please tell comp.lang.prolog what you think, and
if you are shy, just hide behind a hotmail address: lots of us do it when
it suits us :-)

Cheers

Bart Demoen

pineapple.link@yahoo.com

2007-09-06, 4:19 am

>I assumed member/2 and writeln/1, Markus took maplist/3 and
> format/2.

I am such a beginner to Prolog that I did not think of using member
(had glossed the predicate in my earlier readings of Prolog, never
used it). Still being a newbie, I did not realize that one could use
the member function to cycle through each element in a list. Thus my
first attempts to do a "choices" solution in a reasonable amount of
time, in a reasonably minimum length of code, and using recursion vs.
"brute force," failed.

Once I had the hints of 1) consider member, and 2) put a ",fail" at
the end of the query (I know it somehow helps backtracking, but I
still don't understand how, or why it is necessary), I came up with a
largely correct solution that was similar to yours.

> Given that other languages (or their designers) do not shy away from
> adding sugar and thus promote their language by expressiveness, and given
> that Markus' solution of the OP's problem is way shorter than the Logo
> one, what direction should Prolog take ?
> Make more constructs/predicates part of the language or not ?

I hesitate to tell Prolog what Prolog should be - I'm an extreme
Prolog newbie with little experience in the language. Furthermore, I
haven't gotten off my butt and come up with a language that is
better. Having said that, I must say that this exercise was extremely
useful for me because it enabled me to come up with a (naive newbie)
assessment of Prolog from a personal perspective. I was disappointed
that I somehow could not come up with a solution to such an easy
problem more quickly than I did (and the solution is still cryptic and
non-intuitive enough to cause me to look at it and scratch my head and
wonder how or why it works, even though I am the one who wrote it).
This is coming from a guy who once wrote a C compiler for a project.

My thoughts before you even posted this were that Prolog should have
at least basic looping constructs, and iterators over the basic list
structure. Why on earth should someone have to re-invent the wheel
and implement these things each time one sits down to program?
Especially in light of the fact that recursive solutions to problems
like the one above don't come extremely naturally or quickly to most
people (sure - to you gurus it is second nature).

After having these reflections and thoughts, and not being one to sit
around complaining while doing nothing, I did a "proof of concept" for
myself, and wrote a trivial (the gurus will laugh) times_repeat
predicate:

times_repeat(0,_).
times_repeat(I,Pred) :- call(Pred), J is I-1, times_repeat(J,Pred).

The first thing someone might tell me is that this predicate already
exists in the language. I don't know if it does or it doesn't (I said
I'm a newbie), but I also will say again that this was "proof of
concept." In other words, I wondered how easy it would be to add
looping constructs to Prolog.

Someone else might say "well if it only took one or two lines of code,
do we really need such a construct?" I would say yes. It is much
easier to read a simple "times_repeat" in code and understand what it
does rather than having to read some cryptic recursion loop and figure
out what it is doing. I like for my eyes to hit the name of a
predicate and instantly know what is going on. I don't like tracing
through code, however trivial the Prolog gurus think that code is, to
figure out what it is doing.

In addition to the trivial times_repeat above, why not have all the
other looping constructs? Other fine languages have them, why not
Prolog? What about while loops, for loops, etc? If I end up doing
anything substantial in Prolog, and if these tools aren't already
buried in the language somewhere, or available as a library, I will
have to write them myself. Why on earth is this necessary for me to
do? When I sit down to code in Smalltalk I don't have to do it. Why
in Prolog?

Another thing which I think is extremely desirable is a way to easily
iterate over lists. In Smalltalk, one iterator is "do." list do:
[whatever] will iterate over the list of elements, doing whatever you
want for each element in the list. Also available are select, detect,
reject, collect, and inject, among other iterators. Why did I have to
sit down and fathom some way to iterate over a choices list? Why
wasn't this functionality already available?

However, you asked a good question above: given that Markus Triska was
able to come up with a one or two line solution to iterate over a list
and produce a correct solution, is it necessary to build iterators
into the language? I'd say it is. I'd venture to guess that the
average Prolog student doesn't understand Triska's solution, as
amazing as it is, and wouldn't be able to come up with a similar
solution. Instead he'd spend hours hacking away just to iterate over
a simple list. Time is of the essence. If it is hard to work in a
language, it becomes a chore and a bother. If tools are available,
one can spend time writing a solution to the problem instead of
writing tools first, or figuring out a way to (seemingly) do it
without basic tools (like Triska did).

And why is there no other basic data structure available except a
list? I hate lists. I usually avoid lists like the plague when I
work in other languages. I don't like having to iterate up and down
them all over the place, plus lists are slow. Sure, lists have their
uses. But what about arrays? Sets? Bags? Hashes/maps/
dictionaries? Trees and heaps? Why on earth should someone have to
sit down and code these things up? Why aren't they already there?
Isn't this the whole idea of a high-level language? If I wanted to do
everything myself, I'd program in Assembly language!

That's my 2 cents, anyway, and it probably isn't worth even that.

Marco Gavanelli

2007-09-06, 8:05 am

bart demoen wrote:
> Given that other languages (or their designers) do not shy away from
> adding sugar and thus promote their language by expressiveness, and given
> that Markus' solution of the OP's problem is way shorter than the Logo
> one, what direction should Prolog take ?
> Make more constructs/predicates part of the language or not ?
>
> It's meant to be a poll ! Please tell comp.lang.prolog what you think, and
> if you are shy, just hide behind a hotmail address: lots of us do it when
> it suits us :-)

Ok, I will be brave and use my real name, even though I am pretty sure I
will say something either stupid or obvious :-)

I think the main issue is agreeing on a common syntax, first for the
most peculiar advanced extensions of Prolog. Then, if we want to add
syntactic sugar for often used predicates, that is fine, but I don't see
this as urgent issue.

For instance, most Prolog implementations now have some CLP library, and
typically they have some library for CLP(FD). I believe CLP is very
important for Prolog, as it fits very well into the language, both
theoretically and implementation wise (consider that CP was born as CLP,
and now the market leader is ILOG, a C++ implementation: this sounds
like a lost opportunity for Prolog).

But if we look at CLP(FD), every Prolog has its own syntax. I understand
that the internal implementation can be different, and the most advanced
features can be different: if one finds a very good implementation for
constraint XXX, she will add it to her own Prolog, and no-one is obliged
to do the same. But why do we have to use different syntaxes for the
basic parts, that have the very same meaning?

I am familiar with SICStus and ECLiPSe. If I want to define domains in
ECLiPSe I write:

X :: [1..10,15..20].

while in SICStus:

X in (1..10) \/ (15..20).

I think we need a standard.

Going back to your question, I find the implementations of iterations in
ECLiPSe is very expressive, and I personally use them a lot, although it
took me a while to fully understand them. When I move to SICStus I miss
them a bit, but it is not a big issue.

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Kish Shen

2007-09-06, 7:07 pm

bart demoen wrote:

> ISO does not add syntactic shorthands for iteration/recursion (like
> foreach in Logo), or any other list meta-predicates (like maplist).
>
> Given that other languages (or their designers) do not shy away from
> adding sugar and thus promote their language by expressiveness, and given
> that Markus' solution of the OP's problem is way shorter than the Logo
> one, what direction should Prolog take ?
> Make more constructs/predicates part of the language or not ?
>
> It's meant to be a poll ! Please tell comp.lang.prolog what you think, and
> if you are shy, just hide behind a hotmail address: lots of us do it when
> it suits us :-)
>

Well, since I work on ECLiPSe, there are a few features of ECLiPSe that
I would like to see as standard. Most of these are syntatic sugar, and
can easily be added to other Prologs:

1) Named structures (structures with field names):

I think this may be one of the most important syntatic feature of
ECLiPSe -- it avoids easy to make errors (using the wrong argument of a
structure), makes the code more readable, and much easier to modify
(adding/removing arguments from a structure).

2) `Logical loops'

This often makes iterations simplier to write and avoids the need to
invent names for auxillary loop predicates. It is also easier for Prolog
newbies to use than recursion (which is what the loops are transformed to).

3) Array notations

I use this less than the previous two features myself, because I don't
really write the type of application programs that need them. However, I
think if you need to write programs that requires arrays, then this is
really useful syntax. It makes it much easier for programmers to think
of structures as arrays.

4) High-level interface to external languages

This is the interface ECLiPSe has to Java and Tcl/Tk (and also
originally Visual Basic, but that is no longer maintained because Visual
Basic is not cross-platform, and we don't really use Visual Basic
ourselves).

This is not a syntatic feature like the previous ones, but it would be
nice to have some sort of standard for interfacing to external
languages, and one of the advantage of this interface is that the
ECLiPSe (Prolog) side of the interface is mostly independent of the
external language. You still have bi-directionality (in that you can
invoke execution of code of one language from code in the other). We use
this interface to implement the TkECLiPSe GUI for ECLiPSe (written in
Tcl/Tk).

I think the advantage of the ECLiPSe side code being independent of the
external side when Saros was implemented -- this is an IDE for ECLiPSe
in eclipse (eclipse is the eclipse IDE/toolset development platform,
yes, it is confusing, but we did use the name ECLiPSe first :-)). The
ECLiPSe side code was for TkECLiPSe was essentially reused for Saros
(where the external language is Java) and did not need much modifications.

Cheers,

Kish

Marco Gavanelli

2007-09-06, 7:07 pm

Kish Shen wrote:
> bart demoen wrote:
>
>
> Well, since I work on ECLiPSe, there are a few features of ECLiPSe that
> I would like to see as standard. Most of these are syntatic sugar, and
> can easily be added to other Prologs:
>
> 1) Named structures (structures with field names):
>
> I think this may be one of the most important syntatic feature of
> ECLiPSe -- it avoids easy to make errors (using the wrong argument of a
> structure), makes the code more readable, and much easier to modify
> (adding/removing arguments from a structure).

I totally agree, this is one feature I use very often in ECLiPSe, and I
miss it very much in the projects where we use other Prologs.

Cheers,
Marco

--
http://www.ing.unife.it/docenti/MarcoGavanelli/

Kish Shen

2007-09-06, 7:07 pm

pineapple.link@yahoo.com wrote:
>
> And why is there no other basic data structure available except a
> list? I hate lists. I usually avoid lists like the plague when I
> work in other languages. I don't like having to iterate up and down
> them all over the place, plus lists are slow. Sure, lists have their
> uses. But what about arrays? Sets? Bags? Hashes/maps/
> dictionaries? Trees and heaps? Why on earth should someone have to
> sit down and code these things up? Why aren't they already there?
> Isn't this the whole idea of a high-level language? If I wanted to do
> everything myself, I'd program in Assembly language!
>

I am not quite sure what you mean by list being a basic data structure
of Prolog. Term is the basic data structure of Prolog, and you can
easily use a compound term for building many of the other data
structures you mentioned, including lists (lists are just compound terms
(you can see them as binary trees), with some special syntax). Trees,
graphs etc. can easily be constructed with compound terms. You can also
use them as arrays, as the arguments can be accessed in constant time.
Maps should also be easy to implement -- you can bind a variable to the
item being mapped to (which can be any term), thus forming the mapping.

I am also not sure what you mean by `code them up', but it is easy to
define the data structures, for example, a node for trees with 3
branches could be defined as

node(Data, BranchOne, BranchTwo, BranchThree)

where Data is the data you want to put into the node.

Cheers,

Kish

Joachim Schimpf

2007-09-06, 7:07 pm

pineapple.link@yahoo.com wrote:
> ...
> In other words, I wondered how easy it would be to add
> looping constructs to Prolog.

Others have already mentioned ECLiPSe's loop construct. I just wanted
to add that ECLiPSe's loops look like loops and can be understood
as loops, but they can also be understood as a kind of super-maplist.
Indeed they were invented out of frustration with maplist/foldl etc.

Some discussion about the relationship between iteration, higher-order
constructs and bounded quantification can be found in the following
slide set and paper:
http://www.eclipse-clp.org/reports/LogicalLoopsAll.ppt
http://www.eclipse-clp.org/reports/loops.pdf

-- Joachim

Markus Triska

2007-09-06, 7:07 pm

bart demoen <bmd@cs.kuleuven.be> writes:

> Make more constructs/predicates part of the language

Definitely; format/2 seems to be well established already, not to
mention append/3, length/2, member/2 and reverse/2, which everybody
provides anyway. call/N, foldl/N+3, last/2, maplist/N+1, memberchk/2,
nth0/3, and select/3 would also be nice to have guaranteed.

Of the libraries, I often use association lists/balanced trees (as
provided by library(assoc) in many implementations). A standard set of
predicates to easily throw the various errors, and a predicate like
must_be/2 from SWI-Prolog's "error" library would also be great.

between/3 is important too; speaking of which, wouldn't it make sense
to extend it to general arithmetic (integer) expressions, like:

%?- N = 1, between(3*N-1, 5*N+1, X).

Similarly for numlist/3.

DCGs almost go without saying.

Especially for CLP(FD), I find Eclipse's looping constructs useful
too; also append/2 and transpose/2 from SICStus 4. Speaking of CLP(.),
there seems to be little consensus among implementers regarding
primitives for attributed variables etc., but for *users* I think it's
not that bad. For example, CLP(Q), CLP(R) and CHR seem to be pretty
similar across implementations. CLP(FD) admittedly not quite so.

pineapple.link@yahoo.com

2007-09-06, 7:07 pm

> I am not quite sure what you mean by list being a basic data structure
> of Prolog. Term is the basic data structure of Prolog, and you can
> easily use a compound term for building many of the other data
> structures you mentioned, including lists (lists are just compound terms
> (you can see them as binary trees)...

Is this not a list? [whatever, ...]

Every language I am aware of or have ever worked in provides as a
minimum an array "built-in." I do not see an array "built-in" in
Prolog. I see what I describe above, a "list." There are even what
appear to be operators built-in for manipulation of the list, the
"|" (i.e. [H|T]). I presume this is a list type similar to a lisp
list, or a linked-list. It certainly has the limitation of being
accessed like a linked-list (only at the ends). The only real
advantage I see to a linked-list is for performance of insertion and
deletion of elements in the middle, and growing dynamically. All the
Prolog code examples that I see use this list ubiquitously, almost as
if there is nothing else available, or nothing else superior. The
only other language I've seen with such love for the list type is
lisp. I can only imagine that Prolog borrowed its love for the list
from that language.

>You can also use them as arrays,

Show me the declaration of a 1000 element array with constant-time,
fast, positive-integer keyed access. And show me how to use it.

> Maps should also be easy to implement

My point was, "why should they have to be implemented?" They can be
implemented in Smalltalk too. But they don't need to be - they are
already there, complete with all iterators and mechanisms for
manipulating them. Perhaps some people enjoy sitting around all day,
implementing stacks, queues, maps, whatever. Others actually need to
get work done, and wish that those things were already there.

To me, "it can be implemented" is not an argument. Backtracking and
unification can be implemented too, so perhaps these things should be
removed from the language? In fact, everything can be implemented
from pure machine code... why don't we just go back to that? Once we
are all working in machine code or assembler, whenever someone asks
why something isn't there, we can tell them "it can be implemented."

Note that anything I am proposing would not (indeed - should not)
require any basic change to the language itself. I am not asking for,
say, static-type checking or changes in semantics or syntax or things
of this nature - things which would truly modify the language itself.
The stuff I'm talking about is simply optional stuff that someone
could choose to use or not to use. However, it's also stuff that's
"standard" in many other languages, or it should be at least. This
also seems like stuff that could be implemented as a library, if that
is desirable, although to me really basic things like arrays should be
provided by the language itself (for performance?), not simply tacked-
on as "syntactic sugar."

If you disagree with anything I say above, by all means, "let me have
it."

Thanks.

pineapple.link@yahoo.com

2007-09-06, 7:07 pm

pineapple.link@yahoo.com

2007-09-06, 7:08 pm

A more concise version of the choices Logo program, written by Brian
Harvey, the creator of Berkley Logo:

to choices :menu
foreach crossmap "sentence :menu "print
end

Kish Shen

2007-09-06, 10:06 pm

pineapple.link@yahoo.com wrote:
>
> Is this not a list? [whatever, ...]

This is precisely the `special syntax' I mentioned. A list is really a
structure (with the functor name .) with two arguments -- the head and
the tail, i.e.

[H|T] == .(H,T)

and

[1,2,3] == .(1,.(2,.(3,[])))

As lists are used so often, special syntax allows you to write list more
easily.

> Every language I am aware of or have ever worked in provides as a
> minimum an array "built-in." I do not see an array "built-in" in
> Prolog. I see what I describe above, a "list." There are even what
> appear to be operators built-in for manipulation of the list, the
> "|" (i.e. [H|T]). I presume this is a list type similar to a lisp
> list, or a linked-list. It certainly has the limitation of being
> accessed like a linked-list (only at the ends). The only real
> advantage I see to a linked-list is for performance of insertion and
> deletion of elements in the middle, and growing dynamically. All the
> Prolog code examples that I see use this list ubiquitously, almost as
> if there is nothing else available, or nothing else superior. The
> only other language I've seen with such love for the list type is
> lisp. I can only imagine that Prolog borrowed its love for the list
> from that language.
>

As I said, the basic data structure in Prolog is the term. A structure
can have any number of arguments (within reason, and some Prolog
implementation may impose rather small limits on the number of
arguments). For any structure, the number of argument is of course
fixed, and this is why lists are useful, because they can be of
indeterminate length.

>
> Show me the declaration of a 1000 element array with constant-time,
> fast, positive-integer keyed access. And show me how to use it.
>

Well, there are no declarations as such in Prolog -- variables, data
structures etc. are created when they are first used.

To create a 1000 element array:

functor(Array, a, 1000)

This creates a structure (aka compound term) wtih the name a and 1000
arguments (You can of course use any other valid name you want).

Implementationally, this would be implemented like an array in other
languages, i.e. the arguments are in successive memory locations.

and to access the Nth element of this array (in constant time):

arg(N, Array, Element)

You can say that this is quite cumbersome syntax, and that is one reason
why ECLiPSe provides special syntax to support more traditional array
like syntax (example from the ECLiPSe manual):

[eclipse 1]: Prime = a(2,3,5,7,11), X is Prime[2] + Prime[4].
Prime = a(2, 3, 4, 7, 11)
X = 10

instead of

[eclipse 6]: Prime = a(2,3,4,7,11), arg(2,Prime,P2),arg(4,Prime,P4),
X is P2+P4.

Prime = a(2, 3, 4, 7, 11)
P2 = 3
P4 = 7
X = 10

which is the normal Prolog syntax.

>
> My point was, "why should they have to be implemented?" They can be
> implemented in Smalltalk too. But they don't need to be - they are
> already there, complete with all iterators and mechanisms for
> manipulating them. Perhaps some people enjoy sitting around all day,
> implementing stacks, queues, maps, whatever. Others actually need to
> get work done, and wish that those things were already there.
>

I am not sure what you mean by `is there'. As I hoped I showed, it is
quite easy to construct trees etc. with compound terms. This is because
the argument of a compound term can be any other term, including another
compound term. I can't really see how it could be made easier. It is
also easy to manipulate such terms. It is true that there are no
standard iterator over structures, but it is not that difficult to write
code to traverse these structures.

In addition, ECLiPSe does provide iterators over compound terms,
including some support for nested compound terms.

> To me, "it can be implemented" is not an argument. Backtracking and
> unification can be implemented too, so perhaps these things should be
> removed from the language? In fact, everything can be implemented
> from pure machine code... why don't we just go back to that? Once we
> are all working in machine code or assembler, whenever someone asks
> why something isn't there, we can tell them "it can be implemented."
>
> Note that anything I am proposing would not (indeed - should not)
> require any basic change to the language itself. I am not asking for,
> say, static-type checking or changes in semantics or syntax or things
> of this nature - things which would truly modify the language itself.
> The stuff I'm talking about is simply optional stuff that someone
> could choose to use or not to use. However, it's also stuff that's
> "standard" in many other languages, or it should be at least. This
> also seems like stuff that could be implemented as a library, if that
> is desirable, although to me really basic things like arrays should be
> provided by the language itself (for performance?), not simply tacked-
> on as "syntactic sugar."
>

As I said, arrays exist in standard Prolog, the `syntactic sugar'
provided by ECLiPSe is to make writing of the code easier. It has no
impact on performance.

Cheers,

Kish

> If you disagree with anything I say above, by all means, "let me have
> it."
>
> Thanks.
>

pineapple.link@yahoo.com

2007-09-06, 10:06 pm

> > Is this not a list? [whatever, ...]
>
> This is precisely the `special syntax' I mentioned.

Well should there not be "special syntax" for other things you claim
either already exist in Prolog, or can be created easily, i.e. Arrays,
Sets, Maps, etc?

> You can say that this is quite cumbersome syntax, and that is one reason

It is cumbersome enough, and ugly enough, for me not to use it, that's
for sure.

> why ECLiPSe provides special syntax to support more traditional array
> like syntax (example from the ECLiPSe manual):

Okay, now we are getting somewhere. Obviously, the ECLiPSe people
agree with me on the need for so-called "syntactic sugar."

> I am not sure what you mean by `is there'. As I hoped I showed, it is
> quite easy to construct trees etc. with compound terms.

I'd say there is a difference between "is there" and "easy to
construct." Either way, assuming trees are "there," then why does
Yap, which I just finished looking at, have a library which provides
trees - in fact several different types of trees? I have also seen
libraries which provide other things (heaps/stacks/queues for B
Prolog, etc). If it were that easy to construct these things, it
would seem that these libraries are unnecessary wastes of code and
time.

> I can't really see how it could be made easier.

Perhaps the libraries I referred to above make it easier (I'm guessing
- I haven't used them). Perhaps that is why the libraries were
constructed.

> It is true that there are no
> standard iterator over structures, but it is not that difficult to write
> code to traverse these structures.

Demoen and Triska probably think it was easy to write the code to
traverse over the "choices" list. They are probably at the level
where they don't even "see" the code when they look at it, rather they
"see" an iterator when they look at the code (even though the iterator
isn't there). This is similar to the guy in The Matrix telling Neo "I
don't even see the code anymore... all I see is blonde over here,
redhead over there." But for other people....

> In addition, ECLiPSe does provide iterators over compound terms,
> including some support for nested compound terms.

Again, now we are getting somewhere. Why do you think ECLiPSe
provides these things, if it is as easy to roll your own as you say it
is?

Regards.

pineapple.link@yahoo.com

2007-09-06, 10:06 pm

Jan Wielemaker

2007-09-07, 4:18 am

On 2007-09-06, pineapple.link@yahoo.com <pineapple.link@yahoo.com> wrote:
>
> Show me the declaration of a 1000 element array with constant-time,
> fast, positive-integer keyed access. And show me how to use it.

Arrays are better implemented wth higher-arity terms. In SWI-Prolog,
which poses no limit on the term-arity, you can do

functor(Term, my_array, 1000)

and then you access the elements using arg/3. This is constant time. The
only trouble is what if you want to do anything but instantiate the
array. To change a value, you need to copy the array. There are
libraries out there that use trees, so they only need to copy something
proportional to log(N). Many Prologs, including SWI, provide some for
of destructive assignment (setarg/3, mutable terms, etc). That solves
your problem, but it isn't very Prolog-like.

Of course, I agree compatible array implementations should be part of
all Prolog implementations ...

Cheers --- Jan

pineapple.link@yahoo.com

2007-09-07, 4:18 am

On Sep 7, 2:45 pm, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:

> The
> only trouble is what if you want to do anything but instantiate the
> array. To change a value, you need to copy the array.

I found this very informative. Does the same problem exist in
changing values in other data structures (the list for instance)? Why
or why not?

(Based on what I've seen so far, I'm guessing the same problem exists,
as I've seen lists appended to and taken apart, but I don't think I've
seen a particular cell's value being changed)

Thanks.

Jan Wielemaker

2007-09-07, 10:06 pm

On 2007-09-07, pineapple.link@yahoo.com <pineapple.link@yahoo.com> wrote:
> On Sep 7, 2:45 pm, Jan Wielemaker <j...@nospam.ct.xs4all.nl> wrote:
>
>
> I found this very informative. Does the same problem exist in
> changing values in other data structures (the list for instance)? Why
> or why not?
>
> (Based on what I've seen so far, I'm guessing the same problem exists,
> as I've seen lists appended to and taken apart, but I don't think I've
> seen a particular cell's value being changed)

In pure Prolog, the only operation on a datastructure is to instantiate
unbound variables in it. You can bind a variable to a term holding a new
variable of course. This has very big benefits from the viewpoint of
avoiding unexpected changes to datastructures. Sometimes you can design
datastructures where you don't have to copy too much to achieve both
reasonably efficient update and the safe `never change' semantics.

There are cases where the cost of copying are too high. For those cases
you need an escape from pure Prolog. Many implementations have some way
to achieve this, but the details vary.

--- Jan

pineapple.link@yahoo.com

2007-09-08, 8:04 am

Choices... the newbie "I hate lists!" version.

(There is a slight amount of "cheating" in that the asserted facts
(you will see what I mean) are hardcoded into the choices rule. But
I'm sure one of you gurus can suggest a way that they can be built
from the input list and called dynamically?)

% Usage
% ?- build_choices([[small...],[vanilla...],[cone...]],
['size(','flavor(','container(']).
% ?- choices, fail.

build_choice([],_).
build_choice([H|T],Name) :-
concat(Name,H,X), concat(X,')',Atom), atom_to_term(Atom,Term,_),
assert(Term),
build_choice(T,Name).

build_choices([],[]).
build_choices([ChoicesH|ChoicesT],[Names
H|NamesT]):-
build_choice(ChoicesH,NamesH), build_choices(ChoicesT,NamesT).

choices :- size(X), flavor(Y), container(Z), write(X), write(' '),
write(Y), write(' '), write(Z), writeln('').

Markus Triska

2007-09-08, 7:06 pm

pineapple.link@yahoo.com writes:

> concat(Name,H,X), concat(X,')',Atom), atom_to_term(Atom,Term,_),

Consider =../2.

> choices :- size(X), flavor(Y), container(Z), write(X), write(' '),
> write(Y), write(' '), write(Z), writeln('').

Consider format/2 and nl/0; for example, what about this version:

make_fact(Name, Choice) :- Fact =.. [Name, Choice], assertz(Fact).

make_facts(Name, Cs):- maplist(make_fact(Name), Cs).

menu(Whats) :-
maplist(call, Whats, Items),
maplist(format("~w "), Items),
nl.

Then you can create the relevant facts like this:

?- maplist(make_facts, [size,flavor,container], [[small, ...], ...]).

and easily print more general menus, like only for size and container:

% ?- menu([size,container]), fail.
%@ small cone
%@ small cup
%@ medium cone
%@ medium cup
%@ large cone
%@ large cup

or for size exclusively:

% ?- menu([size]), fail.
%@ small
%@ medium
%@ large

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Sponsored Links