Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I'll try to explain a naive approach to compiling nested <code>lambda</code>s. Since Greg's explanation of expanding <code>let</code> into a <code>lambda</code> is very good, I won't address <code>let</code> at all, I'll assume that <code>let</code> is a derived form or macro and is expanded into a <code>lambda</code> form that is called immediately.</p> <p>Compiling Lisp or Scheme functions directly into C or C++ functions will be tricky due to the issues other posters raised. Depending on the approach, the resulting C or C++ won't be recognizeable (or even very readable).</p> <p>I wrote a Lisp-to-C compiler after finishing Structure and Interpretation of Computer Programs (it's one of the final exercises, and actually I cheated and just wrote a translator from SICP byte code to C). The subset of C that it emitted didn't use C functions to handle Lisp functions at all. This is because the register machine language in chapter 5 of SICP is really lower level than C.</p> <p>Assuming that you have some form of environments, which bind names to values, you can define the crux of function calling like this: extend the environment which the function was defined in with the formal parameters bound to the arguments, and then evaluate the body of the function in this new environment.</p> <p>In SICP's compiler, the environment is held in a global variable, and there are other global variables holding the argument list for a function call, as well as the procedure object that is being called (the procedure object includes a pointer to the environment in which it was defined), and a label to jump to when a function returns.</p> <p>Keep in mind that when you are compiling a <code>lambda</code> expression, there are two syntactic components you know at compile-time: the formal parameters and the body of the <code>lambda</code>.</p> <p>When a function is compiled, the emitted code looks something like this pseudocode:</p> <pre><code>some-label *env* = definition env of *proc* *env* = extend [formals] *argl* *env* result of compiling [body] ... jump *continue* </code></pre> <p>... where <code>*env*</code> and <code>*argl*</code> are the global variables holding the environment and argument list, and <code>extend</code> is some function (this can be a proper C++ function) that extends the environment <code>*env*</code> by pairing up names in <code>*argl*</code> with values in <code>[formals]</code>.</p> <p>Then, when the compiled code is run, and there is a call to this <code>lambda</code> somewhere else in your code, the calling convention is to put the result of evaluating the argument list into the <code>*argl*</code> variable, put the return label in the <code>*continue*</code> variable, and then jump to <code>some-label</code>.</p> <p>In the case of nested <code>lambda</code>s, the emitted code would look something like this:</p> <pre><code>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* </code></pre> <p>This is a bit difficult to explain, and I'm sure I've done a muddled job of it. I can't think of a decent example that doesn't involve me basically sloppily describing the whole chapter 5 of SICP. Since I spent the time to write this answer, I'm going to post it, but I'm very sorry if it's hopelessly confusing.</p> <p>I strongly recommend <a href="http://mitpress.mit.edu/sicp/" rel="nofollow" title="SICP">SICP</a> and <a href="http://rads.stackoverflow.com/amzn/click/0521545668" rel="nofollow">Lisp in Small Pieces</a>.</p> <p>SICP covers metacircular interpretation for beginners, as well as a number of variants on the interpreter, and a byte code compiler which I have managed to obfuscate and mangle above. That's just the last two chapters, the first 3 chapters are just as good. It's a wonderful book. Absolutely read it if you haven't yet.</p> <p>L.i.S.P includes a number of interpreters written in Scheme, a compiler to byte code and a compiler to C. I'm in the middle of it and can say with confidence it's a deep, rich book well worth the time of anyone interested in the implementation of Lisp. It may be a bit dated by this point, but for a beginner like me, it's still valuable. It's more advanced than SICP though, so beware. It incudes a chapter in the middle on denotational semantics which went basically right over my head.</p> <p>Some other notes:</p> <p><a href="https://github.com/darius/ichbins" rel="nofollow">Darius Bacon's self-hosting Lisp to C compiler</a></p> <p><a href="http://en.wikipedia.org/wiki/Lambda_lifting" rel="nofollow">lambda lifting</a>, which is a more advanced technique that I think Marc Feeley uses</p>
    singulars
    1. This table or related slice is empty.
    1. POTransforming Lisp to C++
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmichiakig
    1. USmichiakig
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 for emphasizing that this is a whole lot more complicated than just translating `let` to `lambda`/application
      singulars
      1. PO
      1. USacfoltzer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload