Lisp as assembly language??

Here is a quote from the book, "Paradigms of Artificial Intelligence Programming" by Norvig:

"To put things in perspective, consider that Lisp is at once one of the highest-level languages available and a universal assembly language. It is a high-level language because it can easily capture data, functional, and control abstractions. It is a good assembly language because it is possible to write Lisp in a style that directly reflects the operations available on modern computers."

This sounds insane and exciting at the same time. If I really can use Lisp as an assembly language, then should I not be able to translate assembly code directly into intelligible Lisp code? Is there actually a Lisp type "assembler/disassembler" out there for the Intel platform? I am more used to this idea from Wikipedia:

"Assembly language is also valuable in reverse engineering, since many programs are distributed only in machine code form, and machine code is usually easy to translate into assembly language and carefully examine in this form, but very difficult to translate into a higher-level language."

(In case someone thinks I am confusing machine code with assembly code, here is a quote from the book, "Reversing": "People sometimes make the mistake of thinking that machine code is “faster” or “lower-level” than assembly language. That is a misconception: machine code and assembly language are two different representation of the same thing.")

This makes me wonder though, why is C/C++ considered lower level than Lisp...?

speech impediment wrote:This makes me wonder though, why is C/C++ considered lower level than Lisp...?

Because they traditionally don't include a garbage collector, lambda expressions, metaprogramming tools, etc.

"Lisp" can be a great assembly language. Common Lisp is not (too many features). There have been several simple dialects developed for the purpose. For example, T was built around one, and Mark Tarver and crew are doing something similar for the new version of Qi.
http://www.paulgraham.com/thist.html

My recent comment in the Common Lisp thread on assemblers is also relevant.

Since T is considered a dialect of Scheme, I suppose Scheme is just as suitable?

See also: Lisp Machines

You could FPGA a chip meant to do something similar.

speech impediment wrote: This sounds insane and exciting at the same time. If I really can use Lisp as an assembly language, then should I not be able to translate assembly code directly into intelligible Lisp code? Is there actually a Lisp type "assembler/disassembler" out there for the Intel platform? I am more used to this idea from Wikipedia:

Think of a Lisp where you have high-level control structures (COND/IF, for instance), but then each of the basic functions in the library is an assembly opcode.

Sounds pretty meaningless to me. You can build a computer with an eye towards evaluating s-expressions (in fact, thats were the words CAR and CDR came from), but modern computers are ugly register machines. A register machine only understands in terms of register operations --- you could write lisp that looked like GAS or AT&T assembly syntax, but whats the point? You would lose symbols, garbage collection, lambdas, functions, s-expressions, macros and all the data types but words and dwords -- poof all gone.

If you want a low-level language that resembles Lisp then the hardware must support such a model, like the Lisp machines did. Or write an intermediate assembly layer to make register computers emulate something approaching a Lisp machine.

Warren Wilkinson wrote:You can build a computer with an eye towards evaluating s-expressions (in fact, thats were the words CAR and CDR came from), but modern computers are ugly register machines.

Well, actually, CAR and CDR refer to the "contents of address register" and "contents of decrement register." The original Lisp was implemented on the IBM 704, very much an "ugly register machine."

See here for more history:
http://www.iwriteiam.nl/HaCAR_CDR.html

I'll yield the point on the names of CAR and CDR. I thought they were a Lisp machine terminology for some dedicated hardware that performed list operations. But my point was never that register machines can't host Lisp, but that their base vocabulary is orthogonal to Lisp. If you want a low-level Lisp, try Forth.

Hey, look. The assembly language for a theoretical lisp machine that needs no GC.
http://home.pipeline.com/~hbaker1/LinearLisp.html

Stack-based, it looks like, making it probably easiest to implement in Forth or (though the implementations are rather graphics-oriented) PostScript.

I've been thinking about this a bit lately. I've been reading "Linux Kernel Development 3rd Edition" (LKD-3E) as a part of a "Book of the Quarter" project for work. It's been interesting reading up on the internals of the Linux kernel, and some of the data structures that are used there. It's also been interesting in a different sense: a couple of months ago, I conceived of the idea of "Common Lisp the Operating System"--and as I read about things like the scheduler and block IO, I could see how writing those kinds of things into Common Lisp would be useful.

With regards to Common Lisp as an "assembly language"--why not? It has already been mentioned that Forth is sort-of an Assembly Language Lisp. I would further postulate that, like Forth, a lispy language could be constructed from assembly instructions, and also like Forth, it would be easy to write a Lispy assembler in the language itself. (I was impressed to see stack-based x86 Assembler in a Forth implementation once!)

Putting all that aside, though, I would also point out that Common Lisp also has functions for bit-twiddling; it has "car" and "cdr" (which, although highly criticized, are essentially assembly-level ways of addressing memory); it even has "goto" and other low-level instructions that would be horrible to use in typical code, but great for macro code.

LKD-3E mentions in passing a "threaded red-black tree"--a red-black tree where the nodes are also threaded together as a linked list. I'm not quite sure how I'd implement something like that in Common Lisp--I'm still rather new to it--but I have the feeling that (A) I'd be using a lot of CARs and CDRs, and (B) the end-result data structure will be as low-level as anything you'd put together in C or Asm.

So I'd go so far as to say that even Common Lisp is this weird mix of Assembler and High-Level Language

I find this a fascinating subject. But there seem to be so many dead ends. Here is a page I found some time back with Lisp OSes. There are many dead projects mixed in if I remeber correctly.
http://linuxfinances.info/info/lisposes.html

This one seems very interesting.

http://common-lisp.net/project/movitz/
"The Movitz system aspires to be an implementation of ANSI Common Lisp that targets the ubiquitous x86 PC architecture "on the metal". That is, running without any operating system or other form of software environment. Movitz is a development platform for operating system kernels, embedded, and single-purpose applications. There can potentially be several completely different operating systems built using Movitz."

Common Lisp on the metal would be an example of Common Lisp as Assembly, no? Project hasn't been posted to in years though.

I wrote a 8051 assember in Lisp- I took the approach of trying to "lisp-ify" the usual assembly language; ie make a domain-specific language using Lisp. So I built up "lispy" definitions of all the mnemonics, which when evaluated by the assembler, emit the 8051 machine code. There are also the usual dw, db etc directives. So essentially, a program is written using the native assembly mnemonics, but in Lisp as the sample program shows below;

(defproject testproj
(:text-base #x100
:data-base nil
:text-align 16
:data-align 8))

(defmacro xyzpdq (parm)
`(add acc ,parm))

(defparameter +RESERVE-DATA-LEN+ 100)


(defdata tst-data2 (:org #x20)
(dw '*text-start* '*text-end* '(- *text-end* *text-start*))
(dw '*data-start* '*data-end* '(- *data-end* *data-start*))
(dw '*bss-start* '*bss-end* '(- *bss-end* *bss-start*))
(dw 'tst-code))

(defbss tst-bss ()
(reserve +RESERVE-DATA-LEN+))

(defdata tst-data ()
(dw 0 1 2 3 'tst-code 'tst-bss)
(db 4 5 6 7 '(lobyte tst-data2))
(db \"hello, world\")
supercat2
(filldata +RESERVE-DATA-LEN+)
(filldata 10 #\\x)
(filldata 2 '(let ((x 1) (y 2) (z 3))
(list x y z))) )

(deftext tst-code ()
(nop)
(xyzpdq 10)
(nop)
supercat
(addc a 1)
(anl acc 15)
(inc dptr)
(cjne acc 3 'tst-data)
(clr a)
(asm51symbols:push acc)
(asm51symbols:pop acc)
(ajmp 'supercat2)
(acall 'supercat)
(acall 'tst-data)
(acall '(+ tst-code 2)))" )


A big win is being able to use Lisp's macro syntax to build up program structure. The assembler is multi-pass so forward declarations etc are OK, and a desk-check of the output machine code looks OK but I haven't run it yet. As you can see with push/pop I have namespace problems.. probably I should dig into that a bit more- in this case there is a collision w/ Lisp's functions of the same name- OTOH I want the usual Lisp functions available for macros etc but that leads to the symbol collision. An easy solution would be to put some extra syntax on the 8051 mnemonics so the collision doesn't occur- maybe an underscore or something.

Project is open source- would be happy to give out the source code but I've not posted it anywere..

Greg

If you're working in a self-defined package, you could also shadow those functions, which would allow you to access them with CL:push and CL:pop.