{Historical} Lisp 'manually' compiled to assembly
Minti
I was going through wikipedia's article on eval at
http://en.wikipedia.org/wiki/Eval. For eval in Lisp it mentions that:
<quote>
Lisp was the original language to make use of an eval function. In
fact, definition of the eval function led to the first implementation
of the language interpreter. Before the eval function was defined, Lisp
functions were manually compiled to assembly language statements.
However, once the eval function had been manually compiled it was then
used as part of a simple input-interpret-output loop which formed the
basis of the first Lisp interpreter. Later versions of the Lisp eval
function have also been implemented as compilers.
<quote>
I am not a great historian, but could anyone clarify what exactly is
meant by "Lisp functions were __manually__ compiled to assembly"?
Thanks and Regards,
Imanpreet Singh Arora
Peter Seibel
People would write Lisp functions and then say, "gosh, I wish we had a
Lisp compiler". Then they'd turn around and translate the function
they just wrote in Lisp into assembly and feed it to the computer.
-Peter
--
Peter Seibel * pe...@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Coby Beck
news:m2u0c2z...@gigamonkeys.com...
> "Minti" <iman...@gmail.com> writes:
>>
>> I am not a great historian, but could anyone clarify what exactly is
>> meant by "Lisp functions were __manually__ compiled to assembly"?
>
> People would write Lisp functions and then say, "gosh, I wish we had a
> Lisp compiler". Then they'd turn around and translate the function
> they just wrote in Lisp into assembly and feed it to the computer.
I here that's still the case today ;)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
Ulrich Hobelmann
> "Peter Seibel" <pe...@gigamonkeys.com> wrote in message
> news:m2u0c2z...@gigamonkeys.com...
>> "Minti" <iman...@gmail.com> writes:
>>> I am not a great historian, but could anyone clarify what exactly is
>>> meant by "Lisp functions were __manually__ compiled to assembly"?
>> People would write Lisp functions and then say, "gosh, I wish we had a
>> Lisp compiler". Then they'd turn around and translate the function
>> they just wrote in Lisp into assembly and feed it to the computer.
>
> I here that's still the case today ;)
Well, most of us translate them into C or Java, if we are required to. ;)
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
Pascal Bourguignon
> Hello All,
>
>
> I was going through wikipedia's article on eval at
>
> http://en.wikipedia.org/wiki/Eval. For eval in Lisp it mentions that:
>
> <quote>
> Lisp was the original language to make use of an eval function. In
> fact, definition of the eval function led to the first implementation
> of the language interpreter. Before the eval function was defined, Lisp
> functions were manually compiled to assembly language statements.
> However, once the eval function had been manually compiled it was then
> used as part of a simple input-interpret-output loop which formed the
> basis of the first Lisp interpreter. Later versions of the Lisp eval
> function have also been implemented as compilers.
> <quote>
Well, the 704/7090 had a processor-level "EVAL" instruction, the XEC
instruction, that fetches and executes a processor instruction at the
specified address. So in a way, EVAL was just providing a high level
equivalent of this assembler instruction, it was not the first :-)
http://www.bitsavers.org/pdf/ibm/7090/
> I am not a great historian, but could anyone clarify what exactly is
> meant by "Lisp functions were __manually__ compiled to assembly"?
This is a step in the bootstrap process, when you don't have a
highlevel language. Nowadays, we would just use another programming
language to write the compiler. But when you have no compiler, a
smart solution is to write the first compiler or interpreter in the
highlevel language, and they to hand-compile it, ie. to translate it
manually.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Do not adjust your mind, there is a fault in reality"
-- on a wall many years ago in Oxford.
Ivan Boldyrev
> But when you have no compiler, a smart solution is to write the
> first compiler or interpreter in the highlevel language, and they to
> hand-compile it, ie. to translate it manually.
AFAIR, first Pascal compiler was bootstrapped in similair way.
--
Ivan Boldyrev
| recursion, n:
| See recursion
Tin Gherdanarra
This is John McCarthy in his own words:
"The implementation of LISP began in Fall 1958. The original idea was
to produce a compiler, but this was considered a major undertaking, and
we needed some experimenting in order to get good conventions for
subroutine linking, stack handling and erasure. Therefore, we started by
hand-compiling
various functions into assembly language and writing subroutines to
provide a LISP "environment". These included programs to read and print
list structure. I can't now remember whether the decision to use
parenthesized list notation as the external form of LISP data was made
then or whether it had already been used in discussing the paper
differentiation program. The programs to be
hand-compiled
were written in an informal notation called M-expressions intended to
resemble FORTRAN as much as possible."
Minti
Tin Gherdanarra \/\/|20+3:
Thanks for the information, however, again beloinging to a different
generation of programmers, it is still quite hard to believe all of it.
But, I wonder, how exactly was this Lisp code made to execute. Was the
code converted to assembly for _every_ program that was written back
then? Or the ultimate aim was to use the "assembled" routines in a
compiler or an interpreter?
Regards,
Imanpreet Singh Arora
Tin Gherdanarra
John and other researchers spent days and weeks scribbling
on little sheets of paper and probably used a lot of pencils
and big erasers. This is how it used to be done in these
days. And it's how most of the CRAY supercomputers were
prototyped, by the way.
As for assembler, the first assemblers were women who
needed a day-job at home because of the kids. They got
a stack of pages with assembly listings and converted
them into pages of machine opcodes (probably in octal). I shit
you not. I remember reading a story in Reader's Digest
as a child where they discussed a new super-advanced IBM machine
that could "program itself" and made all this human
labor obsolete. "Programming itself" simply meant that
the assembly language geek could fire up a program
in the privacy of his punch-card reader room and have
a computer program translate it into bits. A so-called
"assembler" if I recollect that right. Unfortunately
I don't recollect which of the hundreds of Reader's
Digests it was.
>
>
> Regards,
> Imanpreet Singh Arora
>
Kenny Tilton
I don't know:
"Once we decided on garbage collection, its actual implementation could
be postponed, because only toy examples were being done."
Sounds like the toys actually ran, and I have to ask, why not? Why does
hand compiling sound unreasonable? The core Lisp functions only had to
be built once, and there were not that many. Then translating Lisp to
machine language became just a matter of calling those built-ins.
I think Minti is right when he mentions the generation thing. I still do
not believe /I/ once programmed on punch cards or Apple Integer Basic
using a cassette player to save my work, and I was the one who did it.
The key is remembering that, at the time, one is having so much damn fun
that one does not mind, and the better tools do not exist yet so there
is nothing to miss. Except one day someone says, OK, this sucks, let's
spend some time finding a better way...
Someday people will howl at the idea of /typing/ software, right?
kenny
Pascal Bourguignon
Here is an example of this hand-compilation output, from the LISP 1.5
assembler sources:
First, a comment with the source of the lisp function MAPCAR, as an
M-expression:
REM
REM MAPCAR(L,F) = (L=0 YIELDS 0,
REM F(L) YIELDS 0,
REM 1 YIELDS MAPAR(CDR(L),F))
REM
Then the hand-compiled function, in assembler: [my comments]
D HED
MAPCAR TZE 1,4
SXD RET,4
TSX $SAVE,4
TXL $END3,,F+2 SAVE 3 ITEMS
STQ F
MCPR STO L
LXD F,4
TXH *+3,4,10 [l=0 ?]
TSX F,4 [call f(l)]
TRA *+4
SXD *+2,4
TSX COMPAT,4
1,,**
LXD 1,4
CLA 0,4
PDX ,4 [cdr(l)]
PXD ,4 [l<-cdr(l)]
TNZ MCPR
RTRN TSX UNSAVE,4
LXD RET,4 PAGE 091
TRA 1,4
Here is another example:
REM
REM FUNCTION COPY
REM COPY(L)= (L=0 YIELDS 0, CAR(L)=-1 YIELDS L,
REM OTHERWISE CONS(COPY(CAR(L)),COPY(CDR(L))))
R HED
COPY TZE 1,4 L=0
SXD CS1,4
PDX 0,4 L
SXD CT1,4 L PAGE 055
CLA 0,4 CWR(L)
PAX 0,4 CAR(L)
TXL C1,4,-2 CAR(L)=-1
CLA CT1
LXD CS1,4
TRA 1,4
C1 TSX $SAVE,4
TXL $END2,,CS2+2 SAVE 2 ITEMS
LXD CT1,4 L
CLA 0,4 CWR(L)
STO CS2
ANA DECM CDR(L)
TSX COPY,4 COPY(CDR(L))
LXA CS2,4 CAR(L)
STO CS2 COPY(CDR(L))
PXD 0,4
TSX COPY,4 COPY(CAR(L))
LDQ CS2
TSX $CONS,4
TSX UNSAVE,4
LXD CS1,4
TRA 1,4
CT1
--
__Pascal Bourguignon__ http://www.informatimago.com/
ATTENTION: Despite any other listing of product contents found
herein, the consumer is advised that, in actuality, this product
consists of 99.9999999999% empty space.
Pascal Bourguignon
> Someday people will howl at the idea of /typing/ software, right?
As soon as mind-reader devices are good and cheap enough (and the USAF
allows their civil use).
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
Rob Warnock
+---------------
| Sounds like the toys actually ran, and I have to ask, why not? Why does
| hand compiling sound unreasonable? The core Lisp functions only had to
| be built once, and there were not that many. Then translating Lisp to
| machine language became just a matter of calling those built-ins.
|
| I think Minti is right when he mentions the generation thing. I still do
| not believe /I/ once programmed on punch cards or Apple Integer Basic
| using a cassette player to save my work, and I was the one who did it.
When I was learning to program the IBM 1410 [circa 1965!], for quite a
while I did everything in raw *machine language* [really!], which wasn't
as bad as it sounds since the 1410 had *decimal* addressing of memory --
its "100k" characters really *were* locations 00001 through 99999!!
[For some reason(?) there was no location 0.]
It was a "character" machine, not a "byte" machine, and a character
consisted of bits named 1, 2, 4, 8, A, B, W, and C. "C" was actually
character parity, and you couldn't enter it yourself -- the machine
set it automatically. "W" was the "word mark" attribute, and marked
the beginning of a variable-length word. [Both instructions and data
could be variable-length! Yes, bignums in hardware!] The "1248AB"
gave you a 6-bit graphic character set, thus upper-case only. The
first character of an instruction word was the opcode (always with
the "W" bit turned on), and to the extent possible opcodes were
mapped to characters that were somewhat mnemonic, e.g., "N" was
No-Op, "L" was Load (input from I/O device in "load mode"), etc.
You bootstrapped the machine in the morning by typing the following
string into location zero and hitting "Start" (where the "v"s over
the "L" & "N" are word marks):
v v
L%B000012$N
This read one complete record from magnetic tape drive #0 into
location 12, which you'll notice [counting from 1!] is the location
just after the no-op, and then executed the no-op, and then executed
whatever had been read in, usually the bootstrap for the operating
system on the rest of the tape.
Well, I discovered that writing all of memory out to tape as a single
record wasn't hard to do, either, and I started saving "core images" of
my playing/learning work on a private scratch tape. You could easily
save multiple "core images" on a single tape [append-only, of course,
no update-in-place], and simply skip past the first few to get to the
one you wanted. The hardest part was keeping up-to-date the paper
cheatsheets I had that told me where in memory I'd put the various
bits of test code and library routines for each of the images! ;-}
Anyway, to address Kenny's point: Once one has handcoded the barest
minimum of utility routines in bare machine code -- output a string,
output a number, input a number, input a letter, save a core image,
or for Lisp, CONS, CAR, CDR, etc. -- from there on up you're already
programming only in subroutine calls, which might as well be some
high-level virtual machine for all you care. I mean, you think "CAR"
and what you write down is a the machine code for a subroutine call
to wherever you had stuck the code for CAR.
[This is a *lot* easier than it sounds if you have a machine with
"readable" instructions and addressing, such as an IBM 1410 or an
LGP-30 (another early favorite for me).]
Even a PDP-10 wasn't *that* hard to code in absolute binary [well,
octal, mostly], since it was a "word" machine with fixed-format
instructions that had field boundaries aligned (mostly) on nice
octal digits. The instructions format was so:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OP | AC |I| X | Y |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
OP = op-code, AC = accumulator, I = use indirection, X = index (if plusp),
and Y was an 18-bit address, which was (then) all of memory.
Keying instructions into the console front panel was easy, since the
switches were colored by threes in alternating shades of light & dark
blue. Made is *really* easy to "type in" octal values!
[Not sure this really had a point, other than that maybe every programmer
should have the experience of having/getting to do at least a little
bit of serious work with "bare metal" at least once in their career...]
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Pascal Bourguignon
> [...]
> [This is a *lot* easier than it sounds if you have a machine with
> "readable" instructions and addressing, such as an IBM 1410 or an
> LGP-30 (another early favorite for me).]
Don't worry, the children of micro-processors knew their instruction
sets in hexadecimal by heart too.
> [...]
> [Not sure this really had a point, other than that maybe every programmer
> should have the experience of having/getting to do at least a little
> bit of serious work with "bare metal" at least once in their career...]
Indeed.
--
__Pascal Bourguignon__ http://www.informatimago.com/
PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.
Thomas F. Burdick
> Tin Gherdanarra \/\/|20+3:
>
> > "The programs to be
> >
> > hand-compiled
> >
> > were written in an informal notation called M-expressions intended to
> > resemble FORTRAN as much as possible."
>
> Thanks for the information, however, again beloinging to a different
> generation of programmers, it is still quite hard to believe all of it.
You don't have to go back in time all the way to the 50's, in the 80's
and early 90's there were still people doing this: anyone who
programmed games on a Commodore 64, or anything graphics-related on a
DOS-based PC, probably has some experience hand-compiling BASIC, C, or
Pascal.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'