Convert Lisp to C ++

Question

I'm working on a toy language that compiles in C ++ based on lisp (a very small subset of the circuit), I'm trying to figure out how to present let expression,

(let ((var 10) (test 12)) (+ 1 1) var) 

At first I thought that I would execute all exprs and then return the last one, but returning will kill my ability to nest expressions, what will be for the let representation?

In addition, all resources are assigned to the original source transformation, I have googled, but all I could hide was a 90-minute schema compiler.

Answer 1

One way to extend let is to treat it as lambda :

 ((lambda (var test) (+ 1 1) var) 10 12) 

Then we convert this to a function and the corresponding call in C ++:

 int lambda_1(int var, int test) { 1 + 1; return var; } lambda_1(10, 12); 

So, in a wider context:

 (display (let ((var 10) (test 12)) (+ 1 1) var)) 

becomes

 display(lambda_1(10, 12)); 

There are many more details, such as the need to access lexical variables outside of let from let . Since C ++ does not have lexically nested functions (unlike Pascal, for example), this will require an additional implementation.

Answer 2

I will try to explain the naive approach to compiling nested lambda s. Since Greg’s explanation of the let extension in lambda very good, I won’t address let at all, I will assume that let derived form or macro and decomposes into a lambda form, which is invoked immediately.

Compiling Lisp or Scheme functions directly into C or C ++ functions will be difficult due to issues raised by other posters. Depending on the approach, the result of C or C ++ will not be recognized (or even very readable).

I wrote the Lisp -to-C compiler after completing the structure and interpreting computer programs (this is one of the final exercises, and in fact I cheated and just wrote a translator from SICP byte code in C). The subset of C that it emitted did not use the C functions to handle Lisp functions at all. This is because the machine language register in chapter 5 of SICP is really lower level than C.

Assuming you have an environment that associates names with values, you can define the essence of the function that calls like this: expand the environment in which the function was defined with the formal parameters associated with the arguments, and then evaluate the body of the function in this new environment .

In the SICP compiler, the environment is stored in a global variable, and there are other global variables containing a list of arguments for calling the function, as well as the procedure object that is called (the procedure object contains a pointer to the environment in which it was defined) and a label for the transition, when the function returns.

Keep in mind that when you compile a lambda expression, there are two syntax components that you know at compile time: the formal parameters and the lambda body.

When the function is compiled, the emitted code looks something like this: this pseudocode:

 some-label *env* = definition env of *proc* *env* = extend [formals] *argl* *env* result of compiling [body] ... jump *continue* 

... where *env* and *argl* are global variables that contain a list of environment and arguments, and extend is some function (this may be a valid C ++ function) that extends the *env* environment by combining names in *argl* with values ​​in [formals] .

Then, when the compiled code is executed, and there is a call for that lambda somewhere else in your code, the calling convention should put the result of evaluating the argument list in the *argl* variable, put the return label in the *continue* variable, and then go to some-label .

In the case of nested lambda s, the emitted code will look something like this:

 some-label *env* = definition env of *proc* *env* = extend [formals-outer] *argl* *env* another-label *env* = definition env of *proc* *env* = extend [formals-inner] *argl* *env* result of compiling [body-inner] ... jump *continue* rest of result of compiling [body-outer] ... somewhere in here there might be a jump to another-label jump *continue* 

This is a little difficult to explain, and I'm sure I made a mess of his work. I cannot come up with a worthy example that does not include me basically casually describing the entire chapter 5 of SICP. Since I took the time to write this answer, I am going to post it, but I'm sorry if it is hopelessly confusing.

I highly recommend SICP and Lisp in small parts .

SICP covers metacircular interpretation for beginners, as well as a number of interpreter options and a byte code compiler that I managed to confuse and cripple above. These are only the last two chapters, the first 3 chapters are just as good. This is a wonderful book. Read absolutely if you have not already done so.

LiSP includes a number of interpreters written in Scheme, a compiler for byte code and a C compiler. I am in the middle of this and I can say with confidence that this is a deep, rich book worthy of the attention of anyone interested in implementing Lisp. It may be a little dated this moment, but for a beginner like me, it is still valuable. This is more advanced than SICP, but be careful. It includes a chapter in the middle on denotational semantics, which basically went right above my head.

Some other notes:

Darius Bacon for self-hosting Lisp for C compiler

lambda lifting , which is a more advanced method that I think Mark Fili uses

Answer 3

If you are looking for tools to translate source code to source, I would recommend ANTLR . It is excellent.

However, you need to think about how to translate from a language with limited text input (lisp) to a less-weakly typed language (c). For example, in your question, what is type 10 ? A short ? A int ? A double ?