Lisp as assembly language??

[speech impediment]

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...?

[nuntius]

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.

[speech impediment]

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

[TheGZeus]

See also: Lisp Machines

You could FPGA a chip meant to do something similar.

[findinglisp]

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.

[Warren Wilkinson]

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.

[findinglisp]

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

[Warren Wilkinson]

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.

[TheGZeus]

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.

[snowfarthing]

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