Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

With some googling, I could easily find some documents in compiler design in C, Java, and C# and even in Haskell, but not in Lisp except implementing Scheme/Lisp in Lisp.

Is Lisp not so popular in implementing other (not functional) programming languages? Do you know of some good documentation about implementing a compiler in LISP?

share|improve this question
4  
I guess once you master Lisp other languages seem worthless, and so implementing compilers for them too ;-) There is an example of a compiler in Structure and Interpretation of Computer Programs, but I guess you have read it already. –  piokuc Aug 31 '12 at 17:00
1  
Take a look at a collection of languages available in Racket, they're implemented in quite an idiomatic Lisp way. There's also an outdated but still interesting tutorial covering various compilation techniques in Lisp: bit.ly/I2LFdr –  SK-logic Sep 2 '12 at 12:14
add comment

migrated from stackoverflow.com Aug 31 '12 at 17:03

This question came from our site for professional and enthusiast programmers.

5 Answers

I think there are few examples because of lack of motivation.

Normally when you implement a compiler or an interpreter the point is raising the level of abstraction. It makes a lot of sense to implement an assembler writing in machine code, then a C compiler using the assembler, then a Python interpreter using the C compiler...

Staying on the same level or going in the opposite direction is not nonsense but a lot less natural... and is done mainly for portability. Some cases are implementing an assembler (for a different processor or for a generic processor) using an higher level language, bootstrapping a compiler, implementing a virtual machine.

With Lisp the whole idea of language level doesn't fit that well (here I mean a full Lisp that includes general full macros, reader macros and that is not allergic to side effects, not a self limited version that only allows template based macros or forces you to a functional programming model).

Lisp is neither an high level language, nor a low level one... more than a language Lisp is a meta-language in which you shape the language that would be ideal to solve the problem you are facing. Creating language abstraction levels is just normal programming in Lisp and doesn't require a new language, compiler or interpreter.

In Lisp you don't need to implement a whole different language if you need a specific abstraction (e.g. exceptions, objects), you just implement that abstraction for use within Lisp. There have been systems programmed down from hardware control up to artificial intelligence all in Lisp.

For example in Common Lisp there is support for object oriented programming (and more sophisticated than in C++) but if it wasn't there it could be just coded... and indeed it was a regular library before Common Lisp. In C instead the only way was to create a full compiler from C++ to C to be able to get there.

share|improve this answer
    
Yes, Lisp is a meta-language. And the best way of using it is implementing compilers for the domain-specific languages. Every little macro in Lisp is essentially a compiler. –  SK-logic Sep 2 '12 at 12:20
add comment

Common Lisp Macros are compilers. If you write a macro that transforms some code into Common Lisp that can then be compiled by Common Lisp, then isn't that a compiler? Check out some Common Lisp programming books on Macros, and I think you'll find some very useful information there. I'd recommend On Lisp and Let Over Lambda.

A recent practical example of using Common Lisp macros as a code transformer/compiler is CLPython, but there are all sorts of DSLs/other examples that use this technique.

Another good example is Doug Hoyte's implementation of a Forth compiler in Common Lisp; that one is at the end of Let Over Lambda.

share|improve this answer
add comment

I assume by books about "implementing SCHEME/LISP in LISP" you mean such titles, as Lisp in Small Pieces.

Regarding implementing other languages in Lisp, the tradition is, actually, very mature. For instance, first prototypes of Smalltalk were implemented in Lisp back in the 70s, while for a more modern example you can take a look at CL-JavaScript. And unlike other languages, in which there's only one way to go — lexing-parsing-intermediate representation transformation-code generation — in Lisp there are 2 ways: the conventional one and building on top of Lisp.

Regarding the former approach, it's actually no different from other languages, so you can start with the Dragon Book and apply the same technics. Regarding the latter approach, it has some syntactic limitations, but it also has two advantages: using Lisp's built-in configurable lexer and parser, and the ability to tap into Lisp itself and use its facilities alongside the language you're implementing. It is called DSL-oriented programming, and some of the best books about it were mentioned in the previous answers: On Lisp and Let Over Lambda.

share|improve this answer
add comment

Lisp compilers are pretty conventional, except that the syntax phase is a lot simpler. It's the data structures in lisp that are unusual compared to other languages. Lisp targets a virtual machine with a specific set of properties (different depending on the variant). Google "lisp virtual machine"

share|improve this answer
1  
That is misleading. Lisp implementations target real machines. –  Kaz Sep 23 '12 at 4:00
1  
Lisp implementations target real machines, but lisp compilers target virtual machines that have abstract properties. Lower levels translate these into real machine instruction. –  ddyer Sep 23 '12 at 4:20
    
Lower levels of ... the compiler. –  Kaz Sep 23 '12 at 5:12
    
A completely separate entity that known nothing about compiling, only about transforming abstract machine operations into concrete ones. A conventional example is the mechanism that turns JVM bytecodes into machine code. –  ddyer Sep 23 '12 at 22:41
    
A lexical analyzer is also a completely separate entity that knows nothing about parsing, a parser is a completely separate entity that knows nothing about lexing, or about walking the abstract syntax tree to generate intermediate code, etc. Some Lisp systems have byte codes, some do not. –  Kaz Sep 23 '12 at 22:47
show 1 more comment

Lisp programmers use the language to solve tasks other than writing a Lisp compiler in itself.

Most Common Lisp implementations (I cannot think of an exception at the moment) are compiled, and their compilers are written in Lisp. The code is there, just maybe not the papers and tutorials.

share|improve this answer
    
Clisp is, I believe, only marginally compiled, unless you specifically ask for compilation. Or, at least, that was true some 10 years ago. –  Vatine Jan 1 at 13:12
1  
@Vatine CLISP was byte code compiled at that time. Since then it has sprouted native compilation, with the help of GNU Lightning. –  Kaz Jan 5 at 5:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.