wingolog

((lambda (x) ((compile x) x)) '(lambda (x) ((compile x) x)))

14 November 2008 11:01 PM (quine | scheme | guile | compilation)

Over the last couple days, I implemented a generic tower of compilers in Guile.

So for example, you have Scheme as a source language, which defines a compiler to GHIL (a scheme-like intermediate language, simpler and without macros), which defines a compiler to GLIL (a lower-level language), which defines a compiler to object code (the byte sequence of VM code).

The compiler takes the source and target language as parameters, and does a depth-first search on the compiler graph to figure out how to get there from here, so to speak.

All well and good you say, but there is a wrinkle, in that sometimes you actually want the result of the computation that you just compiled. This is most clearly the case at the REPL:

scheme@(guile-user)> ,compile 42
Disassembly of #<objcode 871bbd0>:

nlocs = 0  nexts = 0

   0    (make-int8 42)                  ;; 42
   2    (return)                        

scheme@(guile-user)> 42
$1 = 42

So in order not to pollute my delightfully generic compiler with special cases as to whether we want to actually execute the bytecode, I added a fake language, "value", adding a compiler from objcode to value.

I realized when writing about all of this that there is a subset of values that is valid Scheme, bending my language tower into a circle. I suspected a lurking quine, and after some poking and later inspiration from the internet, I found this one:

  ((lambda (x) ((compile x) x)) '(lambda (x) ((compile x) x)))

Delightful, no?

4 responses

  1. Marius Gedminas says:

    Neat!

    Why depth-first rather than breadth-first? If you ever happen to have alternative compilation chains from language A to language B wouldn't you prefer the shorter one?

  2. wingo says:

    Heya Marius! Glad you like that too.

    Depth-first and breadth-first are obviously the same for 1 or 0 solutions. Currently all queries have 1 or 0 solutions, so in practice the difference is moot.

    The question comes in extensibility and prioritization: how can a future user extend the compiler so that their passes are chosen before the system passes?

    I can't think of a way to do that with breadth-first search, given that compilers are stored as an alist on source languages (e.g. the scheme language has a compiler to ghil, ghil has a compiler to glil, etc). With depth first search the solution is obvious, just cons your pass onto e.g. the ghil language object, and it will be chosen if there is a path from your sublanguage to the user's desired target language.

    Happy hacking!

  3. kk says:
  4. ADIL says:

    River map of United statesRiver map of United statesRiver map of United statesRiver map of United statesPrintable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Printable calendar 2017Free Printable calendar 2017

    Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free Printable calendar 2017Free calendar TemplatesFree calendar Templates

    Free calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree calendar TemplatesFree 2017 calendar Templates

    Free 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar TemplatesFree 2017 calendar Templates

    printable calendars printable calendars printable calendars printable calendar printable black calendars printable black calendars printable black calendars printable indian calendars printable us calendars printable us calendars printable calendars us printable calendars indian printable calendars print us calendars

    This is an excellent post i seen.I have to thanks to you to share it. It is really what I wanted to see hope in future you will continue for sharing such a excellent post.

Leave a Reply