Runtime compilation strategy

Discussion of Common Lisp
makia
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Runtime compilation strategy

Post by makia » Wed Nov 04, 2009 8:02 am

I'm doing small lisp like compiler (to x86 asm) and what is bothering me is "runtime compilation", it's simple enough to do simple static C-like compiler with basic Lisp stuff (C runtime/gc and Lisp compiler emiting x86 asm) but i'm not sure how to do runtime compilation and all the problems that goes with it.
I assume that I can start extern gcc assembler each time from Lisp REPL and use C lib dynamic linker/loader (not pretty ?), or meaby create directly in memory opcodes ... but in both cases I'm not completely sure how to do dynamic symbols address resolving, heap functions/closures .....
I dont have experience in writing compilers .. so if someone can explain basic runtime compilation/loading tactics i will be grateful :)
Thanks

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Runtime compilation strategy

Post by methusala » Wed Nov 04, 2009 11:00 am

Incremental Compiler Project

The goal of this project is to turn GCC into an incremental compiler. GCC will run as a server and maintain a model of the user's program. When a translation unit is recompiled, GCC will re-compile the minimum necessary. Read the announcement and check out the branch at svn://gcc.gnu.org/svn/gcc/branches/incremental-compiler

http://gcc.gnu.org/wiki/IncrementalCompiler

http://en.wikipedia.org/wiki/Incremental_compiler

http://hedgehog.oliotalo.fi/

http://books.google.com/books?id=iCrrcM ... q=&f=false

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Runtime compilation strategy

Post by gugamilare » Wed Nov 04, 2009 1:36 pm

makia wrote:I'm doing small lisp like compiler (to x86 asm) and what is bothering me is "runtime compilation", it's simple enough to do simple static C-like compiler with basic Lisp stuff (C runtime/gc and Lisp compiler emiting x86 asm) but i'm not sure how to do runtime compilation and all the problems that goes with it.
I assume that I can start extern gcc assembler each time from Lisp REPL and use C lib dynamic linker/loader (not pretty ?),
I don't know if it is pretty or not, but calling gcc to create a shared object and linking to it is what ECL does. A friend of one friend of mine also used to do this in a program written in C# (but nothing to do with Lisp).

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Runtime compilation strategy

Post by findinglisp » Wed Nov 04, 2009 5:53 pm

Yup, take a look at ECL. When you call COMPILE-FILE in ECL, it effectively spits out a temporary .c file, invokes GCC on it, and then when you LOAD it, it dynamically loads the resulting dynamic lib.

Most other Lisp compilers don't work this way, BTW. Others, like SBCL, have their own compiler/assembler internal to the Lisp image and can generate assembly code directly into memory or to a file without the need of gcc.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Runtime compilation strategy

Post by nuntius » Wed Nov 04, 2009 9:08 pm

It is much more common for scheme implementations to be built on C compilers. See for example Gambit or Chicken.

makia
Posts: 25
Joined: Tue Jul 22, 2008 2:37 am

Re: Runtime compilation strategy

Post by makia » Thu Nov 05, 2009 12:46 am

findinglisp wrote:Yup, take a look at ECL. When you call COMPILE-FILE in ECL, it effectively spits out a temporary .c file, invokes GCC on it, and then when you LOAD it, it dynamically loads the resulting dynamic lib.

Most other Lisp compilers don't work this way, BTW. Others, like SBCL, have their own compiler/assembler internal to the Lisp image and can generate assembly code directly into memory or to a file without the need of gcc.
yes, i know that, but for example in ECL when you type function in REPL i doubt that you get compiled function (it does not invoke GCC), so if I want something like that I need to invoke gcc on every REPL input or implement interpreter beside compiler
I'm more interested in SBCL/CCL way, to assemble things directly into heap but i'm not sure how to implement this, obvious compiler need to have runtime support to push code into heap ... so it looks like that i dont know how to connect runtime and compiler to have working environment

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Runtime compilation strategy

Post by ramarren » Thu Nov 05, 2009 1:13 am

makia wrote:I'm more interested in SBCL/CCL way, to assemble things directly into heap but i'm not sure how to implement this, obvious compiler need to have runtime support to push code into heap ... so it looks like that i dont know how to connect runtime and compiler to have working environment
I played only a little with assembly, but as far as I know you just mark a heap region as executable if necessary, depending on your operating system (see NX bit on Wikipedia, mprotect syscall on Linux) and jump to it. Of course you need an assembler to generate the machine code which can be placed in memory directly. Other than that you don't need "runtime support to push code into heap" other than normal memory manipulation tools.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: Runtime compilation strategy

Post by dmitry_vk » Thu Nov 05, 2009 4:00 am

Ramarren wrote: I played only a little with assembly, but as far as I know you just mark a heap region as executable if necessary, depending on your operating system (see NX bit on Wikipedia, mprotect syscall on Linux) and jump to it. Of course you need an assembler to generate the machine code which can be placed in memory directly. Other than that you don't need "runtime support to push code into heap" other than normal memory manipulation tools.
You'll also need garbage collector support for moving and reclaiming the code. Moving code in memory might (or might not, depending on linkage strategy) cause text relocations of code that references the generated code. If the generated code closes over some variables, then GC also should support walking over closures.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Runtime compilation strategy

Post by gugamilare » Thu Nov 05, 2009 5:41 am

makia wrote:yes, i know that, but for example in ECL when you type function in REPL i doubt that you get compiled function (it does not invoke GCC)
Indeed, when you type a function in the REPL (or just loads a file without compiling it) ECL transforms your code into bytecode, which it interprets later when necessary. ANSI Common Lisp does not require implementations to compile every function, that is why the functions compile-function and compile-file exist. But there is also nothing preventing you to compile every function using gcc either.

Kohath
Posts: 61
Joined: Mon Jul 07, 2008 8:06 pm
Location: Toowoomba, Queensland, Australia
Contact:

Re: Runtime compilation strategy

Post by Kohath » Thu Nov 05, 2009 7:45 pm

Not that I've got any experience, but instead of generating assembly directly, why not use something like http://llvm.org/, and benefit from all of the optimisers :mrgreen: and things in that project :?: It mentions some type of run-time compilation too.

Post Reply