🚀 go-pugleaf

ICON (described in "The ICON Programming Language", Griswold & Griswold,
Prentice-Hall, 1983) is a descendant of SNOBOL.  It has a fairly
conventional syntax, but adds backtracking, strings, hash tables,
and pattern-matching (patterns are not a data type as in SNOBOL, but
you can do most of the same sorts of things).

Version 7 of ICON (the current one) is implemented (in C and YACC) as
a compiler which produces abstract instructions which are then interpreted
by another C program.  This is rather like the Berkeley Pascal "pi"
compiler and "px" interpreter.

Version 5 of ICON (the one described in the book) had two implementations
sharing a common front end: an "abstract instruction" version, and one
which produced native code.  However, the book says that "a difference of
5% to 10%" in speed between "compiled" and "interpreted" versions was
typical.  So the ICON group decided that it wasn't worth maintaining the
native-code version any longer.

What I'd like to understand is why the difference was so slight.
Let's put it in context (bigger numbers mean faster, each language's
C-coded interpreter set to 1):

 1   Pascal, Berkeley "pi" + "px"
36   Pascal, Berkeley "pc"		-- my measurement on a SUN-3

 1   Prolog, WAM emulated in C
 2   Prolog, WAM emulated in assembly code
 4   Prolog, WAM macro-expanded and peephole-optimised to native code

 1.0 ICON, Version 5 "icont" + "iconx"
 1.1 ICON, Version 5 "iconc"

It's a long time since I was sure of my facts about Berkeley Pascal, but
I don't recall the abstract instructions as being designed for particularly
fast emulation, or the compiler as doing much optimisation.  I suspect that
a ratio of 4 to 10 for "simple-minded native code" -vs- "good C emulator"
should be more typical of Pascal.

So why is the ICON ratio so low?

It could be that the emulator was unusually good, or the compiler unusually
bad, or it could be something about the language.  To put _that_ in
context, I decided to take a Prolog program and recode it in ICON.  Since
I happened to have it handy, I used the "darlington-to-workington" example
on page 163 of the 3rd edition of Clocksin & Mellish (section 7.9).
The total times to find all shortest paths from each town were
    original Prolog version	4.8 seconds
    ICON version		6.2 seconds
    comparable Prolog version   0.5 seconds

ohe original Prolog version is the one which appears in Clocksin & Mellish.
It uses "findall", which is a fairly expensive operation, and uses a
quadratic algorithm for finding the shortest element of a list.
The ICON version, not being able to backtrack over a Prolog-like data base,
backtracks over a vector of triples, but is otherwise determinate.
The second Prolog version is much closer to the ICON version in structure.

The ICON version suffers from not having lists (in the sense of Prolog and
Lisp).  Instead it has extensible vectors (and calls them lists).  This is
a neat idea, but the overheads of the ICON implementation are high.  So I
declared a "pair" record type (pair(Cost,Path) in ICON corresponding to
Cost-Path in Prolog) and a "cons" record type (cons(Head,Tail) in ICON
corresponding to [Head|Tail]) in Prolog.  Allow a factor of 3 for the
size of the data structures (ICON data structures taking up a lot of
memory), and a factor of 2 to allow for the fact that the ICON emulator
is coded in C and the Quintus Prolog emulator isn't, and we're looking
at a ratio of about 2 to 1 between ICON and Prolog [on _this_ task, as
coded by me, running on a Sun-3/50, & other context].

The bottom line of this comparison is that the ICON interpreter doesn't seem
to be especially good or especially bad.  If ICON were like Prolog, we
would expect about a factor of 4 between the speed of interpreted code and
the speed of native code.  That fact that this was _not_ observed suggests
that either the compiler or the language was the problem.

It's worth drawing a distinction between polymorphic languages like ML
and typed Prolog, and languages with overloading, like PL/I and ICON.
An example of a polymorphic operation is:
	-- len: * list -> int
	++ len nil = 0
	++ len H.T = 1 + len T
which computes the length of a list, be the type of the elements what it may.
An example of an overloaded operation is:
	*X
which yields: the cardinality of a character set, the cardinality of a
(general) set, the length of a string, the length of a vector, the
number of fields in a record, &c, each of which is a different machine-
level operation.  Similarly (courtesy of automatic run-time coercion),
X||Y (string concatenation) does not correspond to a single operation either.

So I _think_ the low ratio for ICON wasn't do to the compiler either, but 
to the fact that there is so little that the compiler can do.

Would anyone who understands (I have the ICON Implementation book, but have
not finished it yet and still can't pretend to understand) the ICON
implementation care to comment on this?

[I'm quite happy with ICON's speed: it's quite a bit faster than AWK....]