🚀 go-pugleaf

In article <6814@megaron.arizona.edu> gudeman@arizona.edu (David Gudeman) writes:
>Oh well, I guess I shouldn't apply my dry sense of humor to people who
>don't know me.  The word "horrified" should be taken as hyperbole.
>What I _meant_ was that this use of records is no where near as
>efficient as the use of conses in Prolog and Lisp.  Looking up a field
>in a record requires (1) looking up the record constructor, (2) hashing 
>on the name of the field, (3) going back to the record to get the
>value.  Rather than trying to write a Prolog program in Icon, it would
>have been more efficient to completely reformulate the solution for
>Icon.

Since I didn't exhibit the source code for either the Icon version of the
program or any of the 16 Prolog variants I was trying, it was rather a
surprise to find my use of Icon constructs being criticised.  Unfortunately,
in the rather long interval between my original posting and this subsequent
discussion, I deleted the files in question.

Again, without seeing the code as I wrote it, it is a little unjust to
describe what I did as "trying to write a Prolog program in Icon".  Far
more accurate would be to describe it as "trying to write a Pop-2
program in Prolog and in Icon".  The program was a graph searching
algorithm loosely based on the Darlington-to-Workington example in
Clocksin & Mellish.  The Open set is a collection of <Node,Cost,Path>
triples, the Path being a sequence of nodes through which the Node can
be reached.  With this data structure, if you can reach 50 nodes from
a given node, their representatives in the Open set will share most of
their Path structures -- this appears to be impossible with Icon arrays.

I had skipped the chapter on records in the Icon Implementation book,
because I thought I could predict how that would be done.  Clearly I
was wrong.  I expected that, as in Pop-2 and Pop-11, field names would
be global function constants (in Pop, doublets).  The inconvenience of
having to repeat part of the record name in the field name is minor (and
it can make the code easier to read), the gain in efficiency is major.

As for it being "more efficient to completely reformulate the solution",
that rather misses the point.  The algorithm I started with was known
to be inefficient FOR PROLOG!  We're talking factors of TEN here.  The
point was not to try to write the most efficient possible program in
each language, but to pick a variant of a given algorithm which could
be expressed naturally in both languages, and see what a compiler did
to it.

>>... Icon does have things called lists, but they are not at
>>all what everyone else means by lists:  they are flex arrays.
>
>I probably should just pass on this one, but I can't help myself...
>By "everyone else" you must mean "everyone in the Lisp/Prolog
>community" because outside of that group "list" is a generic term
>referring to an ordered collection of objects.  The operations on a
>list are generally considered to be application specific.  Also,
>outside of that group no one would know what you mean by the term
>"flex array".

"Flex array" is not a Prolog or Lisp term.  It is an Algol 68 term.
As for my use of "list", I refer you to section 5.4.1, page 126, of
"The SNOBOL 4 Programming Language", where we find
	DATA('LIST(VALUE,NEXT)')
"linked list" page 25, Segdewick, "Algorithms" 1st ed,
the use of the word "list" in Knuth "The Art of Computer Programming",
and so on.  The book "The Turing Programming language" uses "list"
in two senses: as a sequence of items in a grammar, e.g. <export list>,
and for the linked list data structure.  I suggest that the word "list"
has several senses (including a verbal one), but that the "data structure"
sense is almost universally understood to be the "linked list" one.
For the more abstract "ordered collection" data structure, the usual
term is "sequence".

>Ask a C programmer, a Smalltalk programmer, a Snobol4
>programmer, and a data-structures teacher what a list is.  You will
>probably get three or four different answers.

As it happens, I *am* a C programmer and have been a Smalltalk programmer
and a Snobol 4 programmer.  When I asked myself, myself agreed with me...
(I also asked a former PL/I programmer, who started talking about PUT SKIP
LIST and the like, but agreed that "list processing" was about pointers,
so again myself agreed with me.)
I've already cited the only instance of "list" I could find in the
Snobol 4 book.  "list" in the sense of a data structure doesn't appear
in Harbison & Steele, but on p204 of Stroustroup's C++ (1st ed) we find
an "slist" class using a [linked] list implementation.  It has to be
admitted that the Smalltalk books use the term "list" to mean "visually
presented sequence".  There is no "list" data structure in Smalltalk,
but there *is* a LinkedList class, so I imagine that other Smalltalk
programmers, if asked what "list" means *as a data structure* would
answer in terms of LinkedList.

>Isn't unification just as remote from conventional machines as Icon
>operations are?

No.