Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.6.2.16 $; site ada-uts.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!ada-uts!richw
From: richw@ada-uts.UUCP
Newsgroups: net.lang
Subject: Efficiency of Languages ?
Message-ID: <15100004@ada-uts.UUCP>
Date: Fri, 18-Oct-85 13:36:00 EDT
Article-I.D.: ada-uts.15100004
Posted: Fri Oct 18 13:36:00 1985
Date-Received: Tue, 22-Oct-85 05:59:03 EDT
Lines: 41
Nf-ID: #N:ada-uts:15100004:000:2067
Nf-From: ada-uts!richw    Oct 18 13:36:00 1985


This note is not really meant to be a response to anything, although
it stemmed from the discussion of garbage collection & efficiency in
LISP.

First of all, I don't know of any features of any languages which are
"inherently" expensive to implement, regardless of the machine
architecture.  For instance, ANY algorithm that takes advantage of
the random-access of memory (i.e. order(1) time to fetch from
memory) on most computers will have a factor of N increase in execution
time when implemented on a Turing machine.  Remember this when
flaming about the wonder of LISP because of the speed of LISP-
machines; if only there were FORTRAN-machines  :-)

(BTW it'd be nice to see a LISP implementation that used one of the
incremental garbage collection algorithms I've been hearing about;
be nice for any GC'ed language, e.g. CLU & Smalltalk, too)

I also think that, like time/space tradeoffs in algorithm design,
there are "abstraction/implementation-difficulty" tradeoffs in language
design. That is, the more high-level abstractions provided by a language
(e.g. GC), the harder it is to come up with a relatively efficient
implementation (compiled or interpreted) of the language.  In general,
this is a result of the fact that a high-level, general feature provided
by a language has to be efficient in ALL possible uses in order to
compete with lower-level, tuned implementations.  As an example,
you could probably write a program using explicit memory allocation/
deallocation that would beat the pants off the same program if it
used automatic storage management.  But, then again, the former
program would be much more tedious to write.

I use this argument as a defense to critics of CLU, which I feel provides
one of the most useful high-level constructs (iterators) of any language.
I am willing to pay the price (which can actually be small) for this
step towards more abstract languages.  Remember that if a higher-level
construct really costs in execution time, the lost time may be made up
in program development time!

Comments ?

-- Rich Wagner