(I must say that I found this dissertation very interesting.)

   Yes, for putting scalars into structures, you can generate reasonably
   efficient code, but few CL compilers actually do.

Yes, but you were not talking about limitations of current CL compilers. You
were claiming that the semantics of CL was inherently deficient.

   However, when you nest those structures, put them into arrays, or pass
   them as arguments, you have extra pointer and heap overhead.
   Furthermore, the compiler cannot statically decide to optimize the
   pointer overhead away, since that is sometimes wrong (i.e., less
   efficient) and can also change semantics.

Here is an idea: Take the semantics of structures to be defined to be
indirect (as it is in current CL and Scheme). Then make structures immediate
as an optimization. There are only two ways you could possibly tell the
different between an indirect structure and an immediate structure:

a. EQ
b. Mutating a slot. If the structure was implemented as an immediate structure
then mutating one copy would unsoundly fail to mutate other copies.

If a compiler could prove that a given structure type never was mutated and
never appeared as an argument to EQ it would be licensed to implement that
structure as an immediate structure. It might choose not to do so for large
structures since the cost of passing around large structures might outweigh
the cost of allocation, reclaimation, and indirection. But it could use
automatically generated profile data to help determine the tradeoff. Or it
could ask the user, remember the responses between compilations, and allow the
user to subsequently change the decision on a per-structure basis. Having
this decision be orthogonal to the source code makes it easier to change this
decision without having to update the source code in a consistent fashion.

   It is incredibly useful to be able to specify reference vs. value
   semantics, and CL lacks the primitives for doing that.

How is value semantics anything more than a subset of reference semantics?
Modulo efficiency, the only thing I can see is mutation of an immediate
structure. That can be accomplished in reference semantics by making a new
copy of the structure with one slot modified and the others copied over. I.e.
in Scheme:

(define (set-car pair obj) (cons obj (cdr pair)))
(define (set-cdr pair obj) (cons (car pair) obj))

These can be defined as above and DEFSTRUCT can be modified to provide
analogous nonmutating SET functions along with the standard mutating ones.
This is all still within reference semantics. Simply the compiler can
recognize when it optimizes a structure to be immediate and further eliminate
the copying involved with the nonmutating SET functions.

Now all of this handles passing immediate structures as arguments, returning
them as results, assigning them to variables, and storing them in structure
or vector slots. A further optimization can be performed. If a compiler can
prove that there can be at most only one pointer to a structure then even if
the structure is mutated it can be implemented as an immediate structure. (If
there can be only one pointer to a structure then it would not be possible for
it to appear as both arguments to EQ.) Standard `linearity' analysis can be
used to make this determination. Thus if one created a vector of structures,
where the only pointers to those structures existed in that vector, even if
the structure slots were mutated, the compiler could still optimize this as a
vector of immediate structures. Similarly for structures slots containing
structures.

Now immediate vectors are a bit harder since the length of the vector would
need to be determined at compiler time if one wanted to have a structure or
vector of immediate vectors. But again standard `manifestness' analysis can be
used to determine the simple and most common instances of when this is the
case and allow this optimization to take place. Of course one would need a
nonmutating VECTOR-SET operation as a counterpart to VECTOR-SET! along the
lines of the above. But as before, this can be defined purely within and on
top of the current Scheme and CL language spec.

So as I see it the semantics of CL and Scheme are perfectly adequate in this
regard. It is just a matter of optimization.
--

(dotimes (i 10000)
  (* 123.4 i)
  )

each multiply seems to take 1.2 microseconds on my 25 MHz 32-bit
Explorer 2.

(dotimes (i 10000)
  (* 1.234d2 i)
  )

appears to take almost the exact same amount of time.

(dotimes (i 10000)
  (/ 1.234d2 i)                                 ;now we're dividing!
  )

also appears to take the same amount of time.

seems reasonably fast to me, given that it's *only* 25 MHz. clearly
faster devices like a Sparc or Alpha chip would be much faster, although
unless you spent a lot of time doing the math, it'd be hard to see it in
your apps.

it doesn't seem to make too much difference about the declarations, but
this is a poor test-case.

the LispChip has built-in floating-pt. the Exp 1 did not, and was
slow about heavy floating-pt stuff. you wanted to be careful with your
code not to waste time computing any floating-pt value more than once.

my guess is that it would be 128 bits. 4 words, expecting word-alignment
behavior (well, that's machine-dependent stuff, I was thinking of a
32-bit machine).

sounds like you're suggesting that it comes out otherwise...

|   (dotimes (i 10000)
|     (* 123.4 i)
|     )
|  
|   each multiply seems to take 1.2 microseconds on my 25 MHz 32-bit
|   Explorer 2.

this is really _outstanding_.  on a SPARC 10, the following C program takes
3 seconds to run when given an argument, and an imperctibly small number
with none, i.e., 3 microseconds per operation.

main (int argc, char ** argv)
{
    if (argc == 2) {
        int i;
        double d;
        for (i = 0; i < 10000000; i++)
            d = 123.4 * i;
    }
    return 0;

        GCL     0.6 seconds
        CLISP   2.2 seconds
        CMUCL   4.1 seconds

are you sure you meant _microseconds_, not milliseconds?

isn't this a result comparable to that of declaring types?  if I took a
casually written lisp program and converted it to C, I'd have to declare
lots more variables types than i did in lisp.  I'd also have to use lots
of malloc/free calls, which I didn't in lisp.  let us say the the
programs get tested with the exact same test suite...I'd expect the C
version to not exhibit the GC-related slowdowns that might be apparent
in the lisp version because that behavior would be distributed
differently, even though the total would likely be exactly the same
amount of RAM allocated and GC'd.

my currently used Lisp dialects do the typical thing--generational GC,
which waits until a threshold is reached before GC'ing gen 0. a C
program GCs every time you let go of something (free it), and so the
time distribution is different. this is the most painful thing
preventing "real-time" behavior--it occurs more-or-less randomly, and
has unpredictable duration.

some years ago, when i was porting Macsyma to the Explorer, I fiddled
with cons-areas, wondering if I could do a better job of controlling GC
occurrences myself.  the idea was that I would allocate an area, work in
it, copy a result out of it and immediately free the area, avoiding
having to GC that area, cutting the cost of a GC when it finally did
occur.  this was before generational GC had become available.  Macsyma
is/was horrible about generating garbage.

unfortunately, it's totally bogus.  Marty Hall, a person CLEARLY more
conversant on lisp compilers than I am, pointed out that the compiler
would have eliminated the multiply, since the result wasn't being used.
all I measured was 10000 loops of nothing.

the equivalent function, which didn't eliminate it:

(defun foo ()                                   ; 0.197
  (let ((x 3.217))
    (declare (optimize (speed 3) (safety 0)))
    (dotimes (i 10000)
      (declare (integer i))
      (setq x (* x (float i)))
      )
    x)
  )

10k times, single-float, best optimization.  0.197 seconds for the whole
thing.  conses about 35 words, or some such--that's a dynamic
behavior,for reasons unknown to me.  that's 20 microseconds per.  still
good, but not great.  double-float time is 25 microseconds.  divide is
actually *faster*, but only about 1%.

disassembling this shows that it's only got 13 instructions, excluding
the FEF overhead. I don't know how many registers the LispChip has, but
it appears to be only one (!?) from looking at the assembly code. I
do'nt know the design, but the assembly code has several push and pop
instructions in it, which suggests that there's an on-chip
stack-register, and the there are two working registers for holding
numbers. the actual loop has three of these instructions in it, and my
(fading) knowledge of microprocessor design suggests that if they were
all registers they wouldn't be necessary here. or would you just have
different ones? been too long...

--> main (int argc, char ** argv)
--> {
-->     if (argc == 2) {
-->  int i;
-->  double d;
-->  for (i = 0; i < 10000000; i++)
-->      d = 123.4 * i;
-->     }
-->     return 0;
--> }
-->
--> of the three Common LISP implementations I have running here, interpreted
--> performance for your LISP expression is:
-->
-->  GCL     0.6 seconds
-->  CLISP   2.2 seconds
-->  CMUCL   4.1 seconds

those are decent numbmers. interpreted runtime on the E2-25 is ~9.8
seconds. for ten thousand cycles, single-float.

--> are you sure you meant _microseconds_, not milliseconds?

absolutely. the original number I gave was 0.012 seconds, but it was a
bogus number. the real one is 0.2 seconds.

Allegro 4.2 tells me it's 33 milliseconds for the compiled version,
i.e., about 3 microseconds per multiply.  and the dissassemble is
bigger, apparently.  looks like 104 words, and 28 instructions, 8 for
overhead.

2. What exactly is the problem with lacking user-visible block
   read and write?  The underlying I/O system will still use block r/w.

(There are cases where Lisps typically represent things more
efficiently than C -- consider e.g. a naive implementation of cons in
C using malloc.)

Do you know that a number of Lisps never cons unless required to
do so by the user's program?

This problem with think kind of account is that it assumes everyone
knows what you're talking about.  It lines up with what lots of
people who dislike Lisp already believe, but doesn't say just how
bad the problem actually is.  People therefore assume it's as
bad as they always thought it was, or worse, since they may not
have considered all your examples (what exactly is wrong with
typed streams, for instance?).

Now, it was fairly easy on VAXes to find cases where Franz Lisp was
faster than C.  Moreover, for some time after Common Lisps appeared,
Franz fit better with C and Unix than they did.  Some CLs have passed
Franz in some ways, but then development of Franz stopped years ago.
Now we're starting to see Lisps that compile to C and pass arguments
on the C stack (which KCL did to some extent in the mid 80s), that are
packaged as shared libraries, that can be linked into C programs on a
more or elss equal basis, etc.  There are also roles for Lisp that
don't involve competing with C but complementing C instead.  What we
now think of as a typical Lisp didn't have to be typical and may
not be typical in the future.  Whether market forces will take any
notice is a different question.

Of course, there will be some applications for which Lisp works
less well than C.  But so far as I can tell, there's no language-
intrinsic feature that prevents there being cases where Lisp works
as well as or better than C.  Of course, maybe there's some lesser
consequence we should consider.

It's possible, I suppose, that someone else disagrees, thus
making it not a straw man, but it's not me.

   in my experience it is more common in real-world programming
   projects to encounter cases were C's memory-management philosophy
   results in higher throughput and fewer problems for interactivity and
   real-time response than one which relies on GC.

I would not disagree with them.

Anyway, in Franz Lisp, "ports" are alost directly FILE *s.
Nothing prevents there being fd-based operations as well.
(Indeed, there's an fdopen.)

And what is the problem for Lisp lw processes anyway?

Inclusion of lexical closures in a language does not slow down
cases that don't use them.  So how is this part of a consistent
choice of expressive power over highest possible performance?

The problem is that even if you add the same number (or more)
declarations to your Lisp program, on many Lisp implementations it
would still not run as fast as the corresponding C program.  And
there is no standard way of figuring out why.

For example, in CMU CL, at some point, FLOOR was much slower than
TRUNCATE because FLOOR didn't get inlined.  In Lucid, adding redundant
declarations could slow down your program.  Trying to track down the
sources of such problems is just as hard as trying to track down a
compiler bug or a pointer bug in C (actually, harder than a pointer
bug if you have Purify for C...).

Another problem is that if you want to get memory utilization in
CommonLisp that is as efficient as in C, you often have to change your
program logic radically, in ways that are much less abstract than in
C.  For example, arrays of structures end up having one pointer and
one structure header overhead for each element ("struct { int x,y; }
foo[N];").  Structures having multiple "small" objects do not get
packed by most CommonLisp implementations ("struct { char x,y,z; }
foo[N];").  Structures of fixed-size arrays have a pointer plus an
array header overhead for each element ("struct { float
vect1[3],vect2[3]; } foo[N];").

The only way to program around those limitations is to convert
everything to FORTRAN-style code, where you don't use structures and
rely on monotyped arrays of characters, bytes, and floating point
numbers and use array indexes as pointers.  If you do program
FORTRAN-style, it is usually relatively easy to get good performance
in CommonLisp (there are still some gotchas to watch out for), but
most people choose Lisp in order to have convenient and powerful means
of expressing their algorithms at their disposal, not to be squeezed
into FORTRAN-style programming.

Your previous posting amounted to saying "lisp is better because,
other things being equal, wouldn't you rather use it?"  I am
paraphrasing, but that is what I understood you to be saying.  I have
been explicitly talking all along about cases for which other things
are _not_ equal.  If you really know that the cost of implementing
lisp's more powerful features relative to a C-like language will not
in fact result in unacceptable performance for a given application
then it is true either that lisp is better (if you also intend to use
those features) or at least, as you stated, the choice of language is
simply a matter of taste, or organizational requirements, or whatever.
In my experience, however, there is a significant class of
applications for which the cost of implementing lisp's features has
proven to be too high, such that C-like languages are in fact better
in those cases just as the existence of lisp's more powerful features
make it a better choice in others.

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

[...]

My repeatedly emphasized point is not deep, mysterious, hard to grasp,
or even requiring much in the way of complex justification or
analysis.  A higher level language like lisp will have made
performance trade-offs making it a better choice of language for some
applications and a worse choice for others relative to a lower-level
language like C.  All of the lengthy thread which has ensued is, I
believe, the result of people who feel so threatened by any suggestion
that there can be any application for which lisp is not the best
choice of implementation language that they have felt it necessary to
vehemently attack what were mild observations of (to me. at least)
obvious truths.

   disassembling this shows that it's only got 13 instructions, excluding
   the FEF overhead. I don't know how many registers the LispChip has, but
   it appears to be only one (!?) from looking at the assembly code.

At the macroinstruction level, it's a stack machine, with some shortcuts
and warts in various places.  Most instructions leave their result(s) on
the stack, and args and locals are kept there (the top 1K is buffered
on-chip).  At the microcode level, it's mostly register-to-register with
32 pseudo-two-ported and 992 scratch registers (and at times in the past
we had experimental microcodes that implemented stack-accumulator and
register-window architectures).

As for the multiply speed, my memory and the 1987 chip spec suggest that
the only hardware assist was support for a two-bit-per-step Booth
algorithm for 32-bit integer multiply.  Plus, floats are consed;  header
word plus 32 or 64 bits of data (but consed in a special area that's
GC'd quickly and frequently).

Yeah, there are still some lispm people out here.  I'm typing this on a
Sun with the diamond keys mapped to Control and Control to Rubout (but I
read mail on the Explorer).