how lisp implemented in assembly language? [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. 开发者_Go百科 Closed 11 years ago.

many (may be all?) programming language consist of assembly language

how lisp implemented in assembly language?

is there any good reference, manual, tutorial, or keyword for google?

any official rule/convention for build your own lisp implementation?

such as tail recursion should follow some embodiment rule or something..

thanks

---

Although the other comments and posts are right, this question is overly vague and maybe a bit confused, I can't help but share some recommendations. I've collected a number of links and books on implementing Lisp as I have recently developed a bit of a fascination with language implementation. It's a deep topic, of course, but reading the stuff related to Lisp is especially compelling because you can skip a lot of the intense reading on parsing if you implement a Lisp compiler or interpreter in Lisp, and just use read. This allows the authors to get to the meat of compilation or interpretation quickly. These recommendations are books I've read or started or am reading, and mostly deal with Scheme, not Common Lisp, but still might be of some interest.

If you've got no background in language implementation, and have never had the pleasure of reading about the classic Lisp and Scheme "metacircular evaluators", I would recommend Structure and Interpretation of Computer Programs. If you've seen Lisp-in-Lisp (or Scheme-in-Scheme...) you can skip ahead. In the last two chapters of SICP, the authors present a few different interpreters for Lisp/Scheme and a few variants, as well as a byte-code compiler and a virtual machine. It's simply a brilliant book, and free.

If you don't have time to read SICP, or don't want to slog through it just to get to the interpretation and compilation chapters, I would recommend The Little Schemer. Even though it's very short and intended for newcomers to Lisp and Scheme, if you've never seen a Lisp interpreter written in Lisp, they do present one, and it's quite a delightful book, but might not be for everyone due to the cute style.

There's another free book on Scheme similar to SICP, called An Introduction to Scheme and its Implementation, which I haven't read but used as a reference for a few bits. There are sections on interpreters and compilers in there, and it seems to go a bit deeper than SICP, dealing with hairier things like parsing too. It maybe needed an editor, but it's an impressive offering nonetheless.

With a decent idea of how to do Lisp in Lisp, you can approach implementing Lisp in something lower level.

Lisp in Small Pieces is frequently recommended. I've read most of it, and can say it's definitely a great book, full of nitty gritty stuff. I'm going back over it with a fine comb, because it's easy to skim when you don't understand stuff. I also struggled with getting the code from the author's site to run; if you get it, I recommend using Gambit Scheme and running the code that relies on Meroonet with Meroon, from this distribution. Lisp in Small Pieces presents a number of interpreters written in Scheme as well as a byte-code compiler and a compiler-to-C.

Lisp in Small Pieces moves fast, and it's quite dense. If it's too much for you, perhaps start with The Essentials of Programming Languages. I've read some of it and it's quite good, but it's more interpreters. Apparently one of the older editions (1st? I'm not sure...) included a compiler. There seems to be a lot of change between the 3 editions, but the first is super cheap on Amazon, so check it out.

As for compilation to C, this is kind of a gross subject with lots of hairy bits. Compilation to C brings up all these weird corner issues, like how to optimize tail-calls and handle closures, first-class continuations and garbage collection, but it's pretty interesting, and a lot of "real" implementations of Scheme go this route. Marc Feeley's presentation on this is pretty interesting, titled The 90 Minute Scheme to C compiler.

I have fewer resources on compiling all the way down to assembly, but there is a often recommended paper which introduces compilation of Scheme to x86, called An Incremental Approach to Compiler Construction. It assumes little of the reader, however I found that it simply goes too fast and doesn't fill in enough details. Maybe you'll have better luck.

A lot of the above recommendation comes from this monster comment on Hacker News from over a year ago, from mahmud. It references a number of ML resources, and compilation using continuations. I haven't gotten that far in my study, so I can't say what's good or not. But it's an incredibly valuable comment. The referenced works include Andrew Appel's "Compiling with Continuations" and Paul Wilson's "Uniprocessor Garbage Collection Techniques" paper.

Good luck!

---

I thought about it a bit in the past (then resorted to using a C kernel instead). Of course there is no single "assembly", but for x86/32bit this is what I was planning:

Basic values are stored in 64-bit nodes with three lowest bit used as tag with the following meaning:

000 -> cell (64 bits are basically two pointers: car/cdr)
001 -> fixnum (64-3-1 bits usable for values)
010 -> vector (32-3 bits for size and 32 bit for pointer to first element)
011 -> symbol (32 bits pointing to values in global env, 32 pointing to name)
100 -> native code (32 bits pointing to executable machine code, 32 bits to args)
101 -> float (using 64-3-1 bit by dropping 4 bits from mantissa)
110 -> string (using 32-3 bits for size and 32 bits pointing to bytes)
111 -> struct (32 bits pointing to definition, 32 bits pointing to content)

3 bits remain usable when considering pointers if all allocations are assumed to be a multiple of 8 bytes (reasonable with a cell size of 8 bytes). One extra bit would be needed for implementing a simple garbage collector (the "alive" bit). In the C implementation I ended up allocating this bit in various parts (e.g. least significant bit of higher 32 bits if that was a pointer) depending on the node type.

My idea was to have memory of two types: "nodes memory" (with the layout described above) that was allocated in pages and reused with a free list, and "binary memory" to be used for variable sized strings/code/arrays.

Specific code is needed depending on the node type to implement a touch function that recursively marks as alive nodes referred by an alive node.

All this is of course just a naive approach, but still I got it working in "C" and I'm sure I could have done that also in assembly (my C code is using void * everywhere so is basically just a portable 32-bit assembler). For lazyness in my C implementation I only used 32 bits for floats and for integers (using the higher 32 bits) instead of using all available bits.

---

Take a look at Clozure Common Lisp for an example of assembly language used in implementing a lisp. Clozure CL is mostly implemented in Common Lisp itself, but there is a kernel written in C and some low level functionality in assembly.

For example, here is a macro from compiler/X86/x86-lapmacros.lisp implementing a primitive CAR function on x86 hardware, with one assembly instruction for respectively 32bit and 64bit:

(defx86lapmacro %car (src dest)
    (target-arch-case
       (:x8632
          `(movl (@ x8632::cons.car (% ,src)) (% ,dest)))
       (:x8664
          `(movq (@ x8664::cons.car (% ,src)) (% ,dest)))))

As shown, the assembly code is itself encoded in Lisp form. Porting to another platform involves (among other things) to translate these low level operations into another assembly language and cross-compile to create a runtime on the new platform.

ECL (Embeddable Common Lisp) takes another approach by compiling into C. This makes it convenient to port the implementation to platforms that have a C compiler.

---

Your question is based on very outdated assumptions. These days, almost no language implementations are written in assembly language, and I know of no Lisp implementations that are. Besides self-hosting implementations, C is a common implementation language these days.

If you want to see an assembly language representation of a lisp function, there's the DISASSEMBLE function.

---

That it's a big question to answer well.

Short answer: JIT.

Big answer: Dragon book.