Recoding Lisp programs in C
michael b maxwell
language such as Lisp or Prolog, for obvious reasons. At the same time,
it is frequently asserted that a mature Lisp program can be recoded in C
for increased speed and decreased size.
My question is, how much faster, and how much smaller?
Obviously this depends on many things. Let's assume for the purposes of
discussion reasonably good Lisp and C compilers. (e.g. Frantz Liszt, etc.;
I don't "speak" C, so insert your favorite C compiler here!) Let's also
assume you've made what modifications in your Lisp program you can to speed
it up, e.g. doing (sstatus translink on), using localf (assuming that
works, which it doesn't on my Sun...), setting up the allocation of space
for different forms of data so as to optimize garbage collection, etc.
Likewise whatever optimizations you can make to the C version.
The improvements gained by recoding in C also obviously depend on what kind
of a program you're recoding; so what programs are helped most?
Pointer-intensive ones?? Arithmetic-intensive ones?
On a large program, recoding the entire thing in C is probably not
worthwile (I would guess). How can you tell what parts would best benefit
from translation? (I assume here a Lisp like Frantz, which allows
calling of C functions from Lisp code.) Or does this really gain you
anything?
Have many people really done the translation? Or is it one of those things
that everyone talks about, but no one does anything about? :-) What gains
did you realize? Are there any published studies?
--
Mike Maxwell
Boeing Artificial Intelligence Center
..uw-beaver!{uw-june,ssc-vax}!bcsaic!michaelm
Jay Freeman
There's another issue beside time and speed, having to do with real-time
systems. A current net discussion bewails the plight of the poor F-16
pilot bounced by a Foxbat, when his or her Ada-coded countermeasures system
raises an error message due to run-time range checking. But imagine the
plight of the same pilot when the revised fire-control system -- rewritten
in Lisp -- says "Garbage Collection" and goes to sleep for a while.
(There are Lisp implementations that do incremental garbage collection, of
course.)
--
Jay Reynolds Freeman (Schlumberger Palo Alto Research)(canonical disclaimer)
VLD/VMB
then any C translation is going to have to provide garbage
collection anyway. I once toyed with the idea of providing
a set of C library routines to support LISPy programming,
but it seemed too weird to me. Why not just use a good
LISP compiler instead, especially since the direct translation
into C will be much less maintainable than the LISP source.
Personally I think AI has been oversold.
pre...@ccvaxa.uucp
> /* Written 8:39 pm Oct 5, 1985 by gw...@BRL.ARPA in ccvaxa:net.lang.c
> */ If the code needed to be done in LISP in the first place, then any C
> translation is going to have to provide garbage collection anyway.
The key word there is "needed." it may well be that Lisp provided
a more efficient environment for developing the application even if
the application didn't rely on especially Lisp-ish features like
garbage collection, type mutability, and symbols.
----------
> I once toyed with the idea of providing a set of C library routines to
> support LISPy programming, but it seemed too weird to me.
If a C environment with similar capabilities for dynamic development
were available, many such applications might be written in C to
start with.
----------
> Why not just use a good LISP compiler instead, especially since the
> direct translation into C will be much less maintainable than the LISP
> source.
The Lisp environment is likely to be loaded down with features that
are not strictly needed for the running of the application. Lisp
compilers generally produce code that runs within the Lisp environment,
not as stand-alone applications (some do).
Of course, the translation to C allows the developer an obvious
opportunity to rework the application to preserve needed features
while eliminating unneeded flexibility. I suspect the rewriting
is as important as the change in language.
--
scott preece
gould/csd - urbana
ihnp4!uiucdcs!ccvaxa!preece
ri...@ada-uts.uucp
>> ***** ada-uts:net.lang.c / brl-tgr!gwyn / 9:39 pm Oct 5, 1985
>> If the code needed to be done in LISP in the first place,
>> then any C translation is going to have to provide garbage
>> collection anyway.
What about having the C version be conscientious about using "malloc"
AND "free"? Though many people I know feel that dynamic storage
allocation is a "detail" that programmers need never worry much about,
I wonder if making sure to "free" anything you "malloc" is all that
hard.
I wrote my own slightly modified versions of "malloc" and "free" which
remember how many allocated blocks haven't been freed, and then prints
out an error message at the end of the program (I also modified "exit"
to do this) if all allocated blocks haven't been freed. Unfortunately,
I haven't had time to use these versions in recent work.
Has anyone out there REALLY used "free"? I'm very curious about this...
>> Personally I think AI has been oversold.
I'd like to shake your hand. I have my own opinions about AI that I
won't (and shouldn't) flame about, but KEEP THAT DISRESPECT FLOWING !!!
-- Rich
Joe Chapman
>> Has anyone out there REALLY used "free"? I'm very curious about this...
Well, I've used free immediately after doing a malloc; the routines in
question needed a considerable amount of space for some nonsensical
operation, and in the convolution which ensued there were several
different places where the function might legitimately return. Since
free doesn't trash the space, but merely makes it available for re-use,
I wasn't living so perilously as it might appear.
I should probably caution the folks at home against trying this; were I
rewriting that stuff today I'd certainly be a bit more conventional and
less obscure (i.e., put the free at the bottom of the function and goto
it), but I was young then...
--
Joe Chapman decvax!cca!emacs!joe joe@cca-unix
"The dubious practices admitted to herein are no longer
even my own, and the fabric of the software with which
I and my employer are now associated is devoid of even
a suggestion of them."
George Williams
No, no, no. People seem to think AI => LISP. *That* has been oversold, real AI
hasn't been developed yet and so can't be sold.
(If I have posted this twice, I apologize, I got a swap error somewhere in
posting).
George Williams
decvax!frog!aphasia!gww
God bless you, in case you sneeze.
Eugene D. Brooks III
>Does anyone out there really use free?
Yep, I do in packet switched memory server simulators. I am allocating
and freeing packets all the time. That is until I realize that I am
spending too much cpu time in malloc and free. One then only mallocs
10000 of them at a time and links them into a free list which a packet
allocator pmalloc and pfree operate out of.
.
ma...@prism.uucp
/* Written 12:58 pm Oct 7, 1985 by richw@ada-uts in prism:net.lang.c */
>
> What about having the C version be conscientious about using "malloc"
> AND "free"? Though many people I know feel that dynamic storage
> allocation is a "detail" that programmers need never worry much about,
> I wonder if making sure to "free" anything you "malloc" is all that
> hard.
>
Ask anyone who has ever developed a piece of commercial code for a small
machine. (Yes, Virginia, there are people who develop applications for IBM
PC's...) I, for example, am currently working on a product that will operate
on potentially megabytes of data, and must run in 256 to 512 K of physical
memory, with no help from virtual memory. You'd better believe we're careful
to match every malloc with an appropriate free!
-------------------------------------------------------------------------------
Matt Landau ARPA: matt%mirror@cca
Mirror Systems, Inc. UUCP: {decvax!cca, ima!inmet, mit-eddie, wjh12}...
Cambridge, MA ...mirror!prism!matt
-------------------------------------------------------------------------------
Blessed are they that run around in circles, for they shall be known as wheels.
Smith
be quite sure when you can free something. Having written a farily large Lisp
interpreter I was faced with this problem in just about every procedure. "What
is now free and what must I keep?" The answer is not easy because in a program
which is highly recursive, ie lots of procedures each of which can call a large
subset of the rest, it is very hard, if not impossible to know that item 'x'
is now free. My response to the question "why not recode in C?" is that reliable
garbage collection is hard and you are going to have to write it if the
program is fairily complex. One interesting aspect of 'mark and gather' garbage
collection in a recursive environment is that you have to mark all references
made by local variables in activated procedures. This means that you must run
down a stack of pointers to local variables and mark recursively all lists that
they refer to. For simple programs the cost of constructing this mark stack
is quite high and it has to be done for just about every recursive function.
This means that simple programs (where you know you are not going to run out
of memory doing one 'evaluation') are probably more effecient when written in C.
Peter Ashwood-Smith
Human Computing Resources,
Toronto Ontario.
Mikel Manitius
I used to use it in an old version of a parser I had, it worked
quite well, although I never really got down and benchmarked it.
--
Mikel Manitius - ...{ihnp4|akguc|attmail|indra!koura}!codas!mikel
Peter da Silva
YES. Some of us have to write programs that will run to completion in 64K, or
feel that cutting down the size of programs is a good idea. Yes, I free() every
pointer I malloc() as soon as I no longer need it.
tp@ndm20
On the subject, could anyone give me literature references for a good
on-the-fly garbage collector? Something in C would be especially
useful. What I'm looking at doing is the following: I would like an
allocator that managed disk and memory, so I could allocate more than
I had room for (for machines with limited address space) and have the
allocator and associated routines move things off to disk if I am not
using them, garbage collect some space, and bring in the item I want
from disk. Basically software VM. References to such a beast would
be GREATLY appreciated, but I'll be happy with just stuff on garbage
collection.
Thanks,
Terry Poot
Nathan D. Maier Consulting Engineers
(214)739-4741
Usenet: ...!{allegra|ihnp4}!convex!smu!ndm20!tp
CSNET: ndm20!tp@smu
ARPA: ndm20!tp%s...@csnet-relay.ARPA