Xref: utzoo comp.lang.prolog:1238 comp.lang.misc:1792 Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!zodiac!joyce!sri-unix!quintus!ok From: ok@quintus.uucp (Richard A. O'Keefe) Newsgroups: comp.lang.prolog,comp.lang.misc Subject: Re: Is ICON higher level than Prolog? Message-ID: <321@quintus.UUCP> Date: 29 Aug 88 23:52:21 GMT References: <6814@megaron.arizona.edu> Sender: news@quintus.UUCP Reply-To: ok@quintus.UUCP (Richard A. O'Keefe) Organization: Quintus Computer Systems, Inc. Lines: 90 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 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. , 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.