Lightning Bindings

Lightning Bindings

[Noah Lavine]

Dear Guile Developers,

After watching the discussion of native code generation on this list a
few weeks ago, I decided I'd like to help. I looked at several
possibilities, but it seemed like the easiest and most sure way of
making *something* work was writing bindings to GNU Lightning.

I now have a start at working bindings for Lightning, which you can
see at http://github.com/noahl/guile-lightning. Currently it can only
use a few Lightning instructions, but I have enough to verify that it
generates executable code and that code interfaces with Guile. At this
point I could fairly easily go through the Lightning manual and add
more functions, command-by-command, until I had a complete interface
to the Lightning API.

My thought was to do enough of the Lightning API that it could call C
functions, and then implement a compiler from Guile VM code to native
Lightning-generated code that just called a series of VM functions.
There wouldn't be any inlining or cool things like that, but it would
be a start. You could then add inlining support for individual VM
functions as it seemed important. At that point I would also want to
wrap the rest of the Lightning API, both so that inlined VM functions
could use it and so that other Guile programs could use Lightning like
any other module.

However, I would like to ask two questions before I do that, to make
sure the result is ultimately useful.
   - First, would you like Lightning bindings? As I said, I think it's
the fastest way to get some native code generation going, but I don't
think it'll ultimately be the best. (I can clean up and post my notes
on different code generation systems if you'd like them.)
   - Second, what would a good interface to a native code generation
system be? (I'm assuming we'll want Lightning available as a regular
module in addition to using it to speed up the language.) My current
prototype just mimics the Lightning API, but it's not necessarily the
best way to do this. Is there a better way?

Thank you
Noah Lavine

Re: Lightning Bindings

[No Itisnt]

Neat!

Have you looked into libjit? The only reason I bring it up is because
it seems to be more popular than Lightning and already has some
third-party language bindings.

On Thu, May 27, 2010 at 4:03 PM, Noah Lavine <noah.b.lavine@gmail.com> wrote:
> Dear Guile Developers,
>
> After watching the discussion of native code generation on this list a
> few weeks ago, I decided I'd like to help. I looked at several
> possibilities, but it seemed like the easiest and most sure way of
> making *something* work was writing bindings to GNU Lightning.
>
> I now have a start at working bindings for Lightning, which you can
> see at http://github.com/noahl/guile-lightning. Currently it can only
> use a few Lightning instructions, but I have enough to verify that it
> generates executable code and that code interfaces with Guile. At this
> point I could fairly easily go through the Lightning manual and add
> more functions, command-by-command, until I had a complete interface
> to the Lightning API.
>
> My thought was to do enough of the Lightning API that it could call C
> functions, and then implement a compiler from Guile VM code to native
> Lightning-generated code that just called a series of VM functions.
> There wouldn't be any inlining or cool things like that, but it would
> be a start. You could then add inlining support for individual VM
> functions as it seemed important. At that point I would also want to
> wrap the rest of the Lightning API, both so that inlined VM functions
> could use it and so that other Guile programs could use Lightning like
> any other module.
>
> However, I would like to ask two questions before I do that, to make
> sure the result is ultimately useful.
>   - First, would you like Lightning bindings? As I said, I think it's
> the fastest way to get some native code generation going, but I don't
> think it'll ultimately be the best. (I can clean up and post my notes
> on different code generation systems if you'd like them.)
>   - Second, what would a good interface to a native code generation
> system be? (I'm assuming we'll want Lightning available as a regular
> module in addition to using it to speed up the language.) My current
> prototype just mimics the Lightning API, but it's not necessarily the
> best way to do this. Is there a better way?
>
> Thank you
> Noah Lavine
>
>

Re: Lightning Bindings

[Noah Lavine]

Yes, I tried, but I couldn't get it to build on my system for some
reason, so I went with Lightning. I could try harder to get it to
build if it seems like a good choice.

On Fri, May 28, 2010 at 4:49 PM, No Itisnt <theseaisinhere@gmail.com> wrote:
> Neat!
>
> Have you looked into libjit? The only reason I bring it up is because
> it seems to be more popular than Lightning and already has some
> third-party language bindings.
>
> On Thu, May 27, 2010 at 4:03 PM, Noah Lavine <noah.b.lavine@gmail.com> wrote:
>> Dear Guile Developers,
>>
>> After watching the discussion of native code generation on this list a
>> few weeks ago, I decided I'd like to help. I looked at several
>> possibilities, but it seemed like the easiest and most sure way of
>> making *something* work was writing bindings to GNU Lightning.
>>
>> I now have a start at working bindings for Lightning, which you can
>> see at http://github.com/noahl/guile-lightning. Currently it can only
>> use a few Lightning instructions, but I have enough to verify that it
>> generates executable code and that code interfaces with Guile. At this
>> point I could fairly easily go through the Lightning manual and add
>> more functions, command-by-command, until I had a complete interface
>> to the Lightning API.
>>
>> My thought was to do enough of the Lightning API that it could call C
>> functions, and then implement a compiler from Guile VM code to native
>> Lightning-generated code that just called a series of VM functions.
>> There wouldn't be any inlining or cool things like that, but it would
>> be a start. You could then add inlining support for individual VM
>> functions as it seemed important. At that point I would also want to
>> wrap the rest of the Lightning API, both so that inlined VM functions
>> could use it and so that other Guile programs could use Lightning like
>> any other module.
>>
>> However, I would like to ask two questions before I do that, to make
>> sure the result is ultimately useful.
>>   - First, would you like Lightning bindings? As I said, I think it's
>> the fastest way to get some native code generation going, but I don't
>> think it'll ultimately be the best. (I can clean up and post my notes
>> on different code generation systems if you'd like them.)
>>   - Second, what would a good interface to a native code generation
>> system be? (I'm assuming we'll want Lightning available as a regular
>> module in addition to using it to speed up the language.) My current
>> prototype just mimics the Lightning API, but it's not necessarily the
>> best way to do this. Is there a better way?
>>
>> Thank you
>> Noah Lavine
>>
>>
>

Re: Lightning Bindings

[Thien-Thi Nguyen]

() Noah Lavine <noah.b.lavine@gmail.com>
() Thu, 27 May 2010 17:03:48 -0400

      - Second, what would a good interface to a native code
   generation system be?  (I'm assuming we'll want Lightning
   available as a regular module in addition to using it to speed
   up the language.)  My current prototype just mimics the
   Lightning API, but it's not necessarily the best way to do
   this. Is there a better way?

Perhaps you can look at how MELT (for GCC) does things.  Keeping
within striking distance of GCC interop (i.e., its plugin design)
is probably a lot of work, but maybe the benefit would be greater.

thi

Re: Lightning Bindings

[Noah Lavine]

I didn't realize GCC had a Lisp interface. Interfacing with GCC would
be excellent.

This is perhaps far-fetched, but I think the best thing would be if we
could persuade them to replace MELT with Guile. It looks to me from
the docs like MELT is yet another Lisp engine, which is exactly what
Guile is trying to replace. We could offer them a well-tested,
more-feature-complete extension language, and they could offer us
interfaces to good code generation.

Noah

On Sat, May 29, 2010 at 4:09 PM, Thien-Thi Nguyen <ttn@gnuvola.org> wrote:
> () Noah Lavine <noah.b.lavine@gmail.com>
> () Thu, 27 May 2010 17:03:48 -0400
>
>      - Second, what would a good interface to a native code
>   generation system be?  (I'm assuming we'll want Lightning
>   available as a regular module in addition to using it to speed
>   up the language.)  My current prototype just mimics the
>   Lightning API, but it's not necessarily the best way to do
>   this. Is there a better way?
>
> Perhaps you can look at how MELT (for GCC) does things.  Keeping
> within striking distance of GCC interop (i.e., its plugin design)
> is probably a lot of work, but maybe the benefit would be greater.
>
> thi
>

Re: Lightning Bindings

[Ludovic Courtès]

Hello,

Noah Lavine <noah.b.lavine@gmail.com> writes:

> I didn't realize GCC had a Lisp interface. Interfacing with GCC would
> be excellent.

MELT is a “middle end”, useful when writing optimization passes, but not
when writing a front-end.

> This is perhaps far-fetched, but I think the best thing would be if we
> could persuade them to replace MELT with Guile. It looks to me from
> the docs like MELT is yet another Lisp engine, which is exactly what
> Guile is trying to replace. We could offer them a well-tested,
> more-feature-complete extension language, and they could offer us
> interfaces to good code generation.

I don’t think that’d work because MELT is very tightly integrated with
GCC’s internals AIUI.

Thanks,
Ludo’.

Re: Lightning Bindings

[Thien-Thi Nguyen]

() Noah Lavine <noah.b.lavine@gmail.com>
() Tue, 1 Jun 2010 10:57:15 -0400

   I didn't realize GCC had a Lisp interface.

It has a recently (2009?) approved run-time plug-in system, for
which MELT is one example.  Incidently, Emacs also has also recently
won approval for the development of a analogous architecture, so...

   Interfacing with GCC would be excellent.

...yeah, i think the most riteous hack would involve GCC (and Emacs).
That's not to say there could be other valid (and most likely easier
to achieve with less work) approaches.

   This is perhaps far-fetched, but I think the best thing would
   be if we could persuade them to replace MELT with Guile. It
   looks to me from the docs like MELT is yet another Lisp engine,
   which is exactly what Guile is trying to replace. We could
   offer them a well-tested, more-feature-complete extension
   language, and they could offer us interfaces to good code
   generation.

On this i disagree, perhaps because persuasion is not one of my
strengths.  I tend to think, what if i were the MELT hacker?
Would i want this kind of noise in my playground?  My answer might
well be: Why don't you study MELT, develop a congruent Guile-based
system, and then we'll talk.

But that's just the curmudgeon (who perceives precious time
passing ever faster) in me talking; take it FWIW.  I hope you keep
us updated on this matter -- it's very exciting in any case!

thi

Re: Lightning Bindings

[Ludovic Courtès]

Hi Noah,

Noah Lavine <noah.b.lavine@gmail.com> writes:

> After watching the discussion of native code generation on this list a
> few weeks ago, I decided I'd like to help. I looked at several
> possibilities, but it seemed like the easiest and most sure way of
> making *something* work was writing bindings to GNU Lightning.

Excellent!

Have you looked at, ahem, guile-lightning?  :-)

  http://cvs.savannah.gnu.org/viewvc/guile/guile-lightning/?root=guile

As you can see it’s an old attempt to do this.  I haven’t looked in
detail, but there may be ideas or code to borrow.

> My thought was to do enough of the Lightning API that it could call C
> functions, and then implement a compiler from Guile VM code to native
> Lightning-generated code that just called a series of VM functions.
> There wouldn't be any inlining or cool things like that, but it would
> be a start. You could then add inlining support for individual VM
> functions as it seemed important.

I had a vague plan to implement JIT in the VM using lightning in C:

  http://www.fdn.fr/~lcourtes/software/guile/jit.html

The (presumed) advantage is that opcodes from vm-*.c could be largely
reused.  The obvious disadvantage is that it would be C.  Writing
lightning assembly can be tedious, but probably less so if done in
Scheme.

>    - First, would you like Lightning bindings?

Yes!  :-)

>    - Second, what would a good interface to a native code generation
> system be? (I'm assuming we'll want Lightning available as a regular
> module in addition to using it to speed up the language.) My current
> prototype just mimics the Lightning API, but it's not necessarily the
> best way to do this. Is there a better way?

Something close to lightning at the lowest level probably makes sense.
Then there could be a higher-level interface like
<http://cvs.savannah.gnu.org/viewvc/guile/guile-lightning/compiler.scm?revision=1.3&root=guile&view=markup>
or close to the VM’s own assembly.

Looking at
<http://github.com/noahl/guile-lightning/blob/master/binds.scm> it seems
that you plan to have one subr for each lightning instruction.  That
would make the cost of assembling a single instruction quite high,
compared to that of the raw lightning C macros.

Thanks,
Ludo’.

Re: Lightning Bindings

[Andy Wingo]

Hi Noah,

On Thu 27 May 2010 23:03, Noah Lavine <noah.b.lavine@gmail.com> writes:

> I now have a start at working bindings for Lightning, which you can
> see at http://github.com/noahl/guile-lightning.

Fascinating! Congrats on getting through the foreign function docs; a
high-level interface is really necessary there... But very cool to see
that you were able to get something working with so little code!

>    - Second, what would a good interface to a native code generation
> system be? (I'm assuming we'll want Lightning available as a regular
> module in addition to using it to speed up the language.) My current
> prototype just mimics the Lightning API, but it's not necessarily the
> best way to do this. Is there a better way?

Second question first :) I collected my general thoughts on native code
compilation here:

  http://thread.gmane.org/gmane.lisp.guile.devel/10234

I feel quite strongly that the calling convention for native code should
be the same as that of bytecode, and that it should use the same stack.
This way we don't have to maintain separate stack walkers or debuggers
or the like. Also this way we get proper tail calls and multiple value
handling as well.

I tend to think that Ludovic's proposal, or something like it, is the
most practical means to get a portable JIT compiler going; though I
don't really know.

In the end though Guile needs to be generating native code
ahead-of-time, I think. Doing that portably is hard; we'll need to
leverage some other project. I think that project should be GCC. I was
talking to Dodji Seketeli the other day, a GCC dev, and he says that GCC
maintainers are willing to allow other programs to use it for code
generation, but they don't know yet what abstractions they need to
provide.

So first we should probably implement a native code compiler directly
ourselves, for one architecture, and see how that experience changes our
internal language barriers and then go to GCC with a set of
requirements.

(Since I know the question will come up, possibilities are numerous --
basically we want to emit something on the RTL level, I think, though
I'm sure there will be much back-and-forth here; and licensing-wise, it
might involve a build server (already planned), or a plugin, or a
library. It will take a couple years I think.)

>    - First, would you like Lightning bindings? As I said, I think it's
> the fastest way to get some native code generation going, but I don't
> think it'll ultimately be the best.

At the very least it's an interesting tool to have! Though I do agree
though that it's not ideal.

> (I can clean up and post my notes on different code generation systems
> if you'd like them.)

I would be very interested in your observations, yes :)

> Thank you
> Noah Lavine

Thank you!

Andy
-- 
http://wingolog.org/

Re: Lightning Bindings

[Noah Lavine]

On Tue, Jun 1, 2010 at 5:06 AM, Andy Wingo <wingo@pobox.com> wrote:
> Hi Noah,

Hi Andy!

> I feel quite strongly that the calling convention for native code should
> be the same as that of bytecode, and that it should use the same stack.
> This way we don't have to maintain separate stack walkers or debuggers
> or the like. Also this way we get proper tail calls and multiple value
> handling as well.

That makes a lot of sense.

> I tend to think that Ludovic's proposal, or something like it, is the
> most practical means to get a portable JIT compiler going; though I
> don't really know.

You may be right; although I think actually with the FFI, it would be
just as easy to get it going in Scheme. According to the docs, right
now Scheme code can access any function in the Guile binary -
including the functions that implement the VM instructions. I was
planning to just use that capability to generate machine code that
called those C functions.

I just thought of another thing that would be good to think about. I
think we might ultimately not want to be generating machine code for
each procedure, because that would make it impossible to do tracing
optimizations like current JavaScript engines (if I understand the
proposal right), and also because that might lead to generating a lot
of machine code for non-bottleneck points just to get at one
bottleneck. I don't think this is something we should try to implement
now, but it'd be nice if the code generation infrastructure was
flexible enough that it could be added on later.

That also raises another point I had forgotten about. Your earlier
thread asked how to get native code generation for Guile in such a way
that it didn't make Guile too big to understand. I think a good choice
would be to *not* put code generation in the core of Guile. Instead,
make a module you can load that will generate native code. Maybe it
would offer an alternate language, "compiled-guile", or something. It
doesn't even have to be distributed with the Guile libraries, although
it probably would be. This has two advantages - first, it makes core
Guile small. Perhaps people who do embedded systems would appreciate
that, or who want to embed Guile in their programs and care more about
small code size than incredible speed. Second, it gives you the chance
to have multiple native code backends at once. For instance, a JIT and
an AOT backend. All you really need for this is a way for core Guile
to call native code, which you now have with the FFI.

> In the end though Guile needs to be generating native code
> ahead-of-time, I think. Doing that portably is hard; we'll need to
> leverage some other project. I think that project should be GCC. I was
> talking to Dodji Seketeli the other day, a GCC dev, and he says that GCC
> maintainers are willing to allow other programs to use it for code
> generation, but they don't know yet what abstractions they need to
> provide.

Oh, that's excellent! When I was looking at options earlier, I thought
that GCC would be the ideal, but it would be too hard to use their
stuff. If they're willing to work on this, then probably that would be
best.

> I would be very interested in your observations, yes :)

Well, here are some thoughts on existing work that we might be able to reuse:

         Nanojit - from Mozilla and Adobe. C++ library for code
generation. Has optional optimization passes, but could be used
without them. Probably good, but extremely poorly documented.

         SpiderMonkey - the JavaScript runtime from Firefox, written
in C++. In order to be useful, you'd probably have to take out most of
their primitive operations and replace them with your own. You'd also
have to understand their garbage collection and figure out how it
interfaced with Guile's. The upside would be potentially extremely
fast code generation, since you'd get the tracing JIT and the fast
native code generation. The downside would be a lot of complexity. Has
an LGPL license (among others).

         GNU Lightning - a very simple native code generator, written
in C. The upside would be its extreme simplicity. The downside would
be the apparently total lack of optimization.

         GCC - the ideal. It has the best AOT compilation of
everything listed here, but it'd need work to use it. I think the
biggest obstacle is that GCC assumes everything is written to and from
a file. You'd need to change that to use it as a JIT backend. (The
biggest issue is that the compiler and assembler are only connected
through files.) Other than that, though, it shouldn't be too bad to
wrap its C interfaces with the FFI. (Possible idea: get the GCC
developers working with us by offering to replace GCC MELT with Guile
if they'll make nicer backend interfaces. Everyone would win.)

         PLT Scheme - contains MzScheme, an LGPL-licensed Scheme
interpreter with a JIT backend. Their backend is just a hacked version
of Lightning, so it might not be much faster than what we would have
with our own Lightning backend, but it could be possible to reuse
their code. Unfortunately, the code looks pretty complicated.

        MIT/GNU Scheme or Bigloo Scheme - two GPL-licensed Scheme
implementations with native code generators. MIT Scheme is quite
similar to Guile, so it wouldn't be too terrible to implement it as a
language on top of Guile and get their code that way (also Edwin,
their Emacs clone written in Scheme, which might be neat). The project
is also so inactive that they might be willing to merge with Guile,
which could be good. Bigloo Scheme might be harder to interface with,
but also has an AOT code generation backend that can rival GCC, so
that could ultimately have impressive results.

> So first we should probably implement a native code compiler directly
> ourselves, for one architecture, and see how that experience changes our
> internal language barriers and then go to GCC with a set of
> requirements.

That makes a lot of sense.

> (Since I know the question will come up, possibilities are numerous --
> basically we want to emit something on the RTL level, I think, though
> I'm sure there will be much back-and-forth here; and licensing-wise, it
> might involve a build server (already planned), or a plugin, or a
> library. It will take a couple years I think.)

Yes, the license is one thing I'm unsure about. There is a lot of good
GPL-licensed code for doing what we want to do, and it would be nice
to be able to reuse it.

Thanks!
Noah

Re: Lightning Bindings

[Andy Wingo]

Greets,

On Tue 01 Jun 2010 16:55, Noah Lavine <noah.b.lavine@gmail.com> writes:

>> I tend to think that Ludovic's proposal, or something like it, is the
>> most practical means to get a portable JIT compiler going; though I
>> don't really know.
>
> You may be right; although I think actually with the FFI, it would be
> just as easy to get it going in Scheme.

To an extent, yes; but there are two problems that I see.

One is the performance difference between implementing JIT compilation
in Scheme versus implementing it in C. To an extent we're able to be
somewhat wasteful in the compiler because it's all pre-computation, and
it's not necessary to load up the compiler at runtime. But having to
load a Scheme compiler at runtime for programs that don't invoke the
compiler has a space-and-time penalty. Furthermore, one would be jitting
the /compiler/ too, which is a needless timesink when you want to make
your /program/ faster.

Secondly, foreign functions are not called in tail context relative to
the VM. Tail-calling a foreign function that tail-calls a Scheme
function that tail-calls a foreign function consumes stack space. You
need architecture-specific hooks within the VM itself to be able to
tail-call a foreign function; and necessarily so, as they have different
calling conventions. As long as you're mucking about on that level, it's
almost easier to implement in C directly.

I could be wrong of course; let me know if I'm not understanding you
correctly :)

> According to the docs, right now Scheme code can access any function
> in the Guile binary - including the functions that implement the VM
> instructions.

Many VM ops are implemented inline; and especially, the ops that handle
control flow (function calls, prompts, etc).

> I think we might ultimately not want to be generating machine code for
> each procedure, because that would make it impossible to do tracing
> optimizations like current JavaScript engines (if I understand the
> proposal right)

This is true. However I think that compiling Scheme and compiling JS are
a bit different; Scheme is much more amenable to ahead-of-time
compilation, and less polymorphic. A proper inliner can catch many
"trace trees" at compile time, and function calls are typically
implemented much more efficiently than in JS (I hear SpiderMonkey has
activation records that use ~30 words!). So I would not expect trace
trees in Scheme to be as beneficial as it is in JS.

> and also because that might lead to generating a lot
> of machine code for non-bottleneck points just to get at one
> bottleneck.

Hm, I'm not sure what you mean here; can you explain?

> I don't think this is something we should try to implement
> now, but it'd be nice if the code generation infrastructure was
> flexible enough that it could be added on later.

Flexibility is very important, yes!

> Your earlier thread asked how to get native code generation for Guile
> in such a way that it didn't make Guile too big to understand. I think
> a good choice would be to *not* put code generation in the core of
> Guile.

I agree with you in the ahead-of-time case. The "languages" in the
compiler are modules that are lazily loaded; a native-code compiler
would be a module with a "language" interface, and as such would only be
loaded when the user requests native compilation (through various
means).

For the JIT case, the argument is almost convincing enough for me not to
want a JIT at all! But if it can be done minimally and cleanly in C, the
mental costs might be worth it.

> [Native compilation only via a loadable module] has two advantages -
> first, it makes core Guile small. Perhaps people who do embedded
> systems would appreciate that, or who want to embed Guile in their
> programs and care more about small code size than incredible speed.

Embedded people are a strange crowd ;) On the one hand there's my N900
with 64GB of storage, which is practically a desktop to itself. On the
other there's 12-bit microprocessors that only PicoBIT is appropriate
for. We should certainly be able to disable the jit as a compile option,
if it's implemented in C; for some people the small code-size of
bytecode is really paramount. For some people they still want speed, so
cross-compiled AOT native code is best, while omitting the native-code
compiler on the target.

For people with severe constraints, sometimes other Scheme systems will
serve them best. Chibi seems fine, for example.

Given all the constraints though, from a performance and size
perspective I'm still inclined to do a stupid-but-fast-and-small JIT in
C, and a smarter AOT compiler in Scheme. YMMV, of course :)

> When I was looking at options earlier, I thought that GCC would be the
> ideal, but it would be too hard to use their stuff. If they're willing
> to work on this, then probably that would be best.

Yeah agreed. I think we'll have to do a lot of social hacking to get
what we want, but socially and technically this would be the best
solution.

>> I would be very interested in your observations, yes :)
>
> Well, here are some thoughts on existing work that we might be able to
> reuse:

Thanks for these observations! I'll chew on them over time :)

Cheers,

Andy
-- 
http://wingolog.org/

Re: Lightning Bindings

[Noah Lavine]

Hi Ludo,

I didn't realize guile-lightning existed! It looks like that project already has most of the code for Lightning bindings, so it might be better to try to update it to work with Guile 2.0. I also saw your idea for JIT, which I could work on as well. However, all three projects use different ideas of how Lightning should connect to Guile, so before I code more I would like to talk about which would be better.

Here is my understanding of the three approaches:

The approach in my project was to make machine code a Guile datatype, which you could allocate with a special init function and write to with writing functions which are just Guile versions of the Lightning macros. It could be called as a function through the dynamic FFI.

The approach in the other guile-lightning project is to represent the Lightning code as a Guile list which mirrors the Lightning virtual instruction set. When a list is completely built, it would then be passed to a special function (written in C) to assemble it. It also has some infrastructure for labels and a special method of calling these functions, neither of which I understand yet.

The approach in your plan for JIT, as I understand it, is to implement this completely in the C layer. The machine code would be stored as part of the representation of a procedure, and would be invisible from the Scheme side.

(I should also point out that my plan for compilation was to first start generating machine code with as few inlined instructions as possible, which would just call VM functions to do its work. This was also your plan, and I believe also the plan of the earlier guile-lightning project.)

It is not clear to me which one of these is the best way, or even if there is a best way.

The reason I did not use the approach of the other guile-lightning, to make a list and then assemble it, was that it seemed inelegant and possibly slow to have to iterate through instructions twice whenever I compiled something, first to generate the list and then to compile it. However, I doubt it would be very slow, and thinking about it now it might even be faster if the iteration programs became smaller and fit in cache.

As for doing it all in C, I am concerned about this because if there were bindings available in Scheme, then it might be possible to write a nice compiler in Scheme someday, which would do clever things like inlining and interprocedural optimization. (Or, more easily, persuade the MIT Scheme or Bigloo people to donate their compilers.) Writing it in C could make that more difficult - but if it also made Guile programs faster right now, then it might be worth doing anyway.

What do you think of this? What way should I try to implement this?

Noah

Re: Lightning Bindings

[Andy Wingo]

Hi Noah,

On Tue 01 Jun 2010 00:49, Noah Lavine <noah549@gmail.com> writes:

> The approach in [Ludovic's] plan for JIT, as I understand it, is to
> implement this completely in the C layer. The machine code would be
> stored as part of the representation of a procedure, and would be
> invisible from the Scheme side.

Well, one should always be able to disassemble that code, architectures
permitting :) I do think this is the right way to go FWIW, though
perhaps we should only JIT existing procedures after they have been
called some number of times. There is also the Rubinius strategy of
offloading JIT compilation to a separate thread, but that shouldn't be
necessary...

> As for doing it all in C, I am concerned about this because if there
> were bindings available in Scheme, then it might be possible to write a
> nice compiler in Scheme someday, which would do clever things like
> inlining and interprocedural optimization.

I think we'll have this eventually, yes -- but that's at a level above
native code generation. This kind of optimization is best done as
source-to-source transformations of Tree-IL, IMO. See e.g. Oscar
Waddell's thesis.

> What do you think of this? What way should I try to implement this?

Are you most interested in AOT compilation or JIT compilation? If it's
JIT, I would work on something more like Ludovic's solution; if it's AOT
compilation, I would see about making a compiler from one of Guile's
intermediat languages to a new "lightning" language. See "Compiler
Tower" in the manual.

Just my opinion anyway :)

Cheers,

Andy
-- 
http://wingolog.org/

Re: Lightning Bindings

[Ludovic Courtès]

Hi Noah!

Noah Lavine <noah549@gmail.com> writes:

> Here is my understanding of the three approaches:
>
> The approach in my project was to make machine code a Guile datatype,
> which you could allocate with a special init function and write to
> with writing functions which are just Guile versions of the Lightning
> macros. It could be called as a function through the dynamic FFI.
>
> The approach in the other guile-lightning project is to represent the
> Lightning code as a Guile list which mirrors the Lightning virtual
> instruction set. When a list is completely built, it would then be
> passed to a special function (written in C) to assemble it. It also
> has some infrastructure for labels and a special method of calling
> these functions, neither of which I understand yet.
>
> The approach in your plan for JIT, as I understand it, is to implement
> this completely in the C layer. The machine code would be stored as
> part of the representation of a procedure, and would be invisible from
> the Scheme side.

Yes.

> The reason I did not use the approach of the other guile-lightning, to
> make a list and then assemble it, was that it seemed inelegant and
> possibly slow

It depends on when and how the instruction stream is written.  From a
usability viewpoint, having a simple s-exp for asm instructions is
nice (and elegant, IMO).

OTOH, I find the ‘make-integer-id’ example at
<http://github.com/noahl/guile-lightning/blob/master/binds.scm> quite
elegant too.

BTW, note that end-of-buffer situations must be handled, somehow.  If
the whole call generation procedure is burried in a single C functions,
it can hide these details to the application.  Otherwise, it’d be up to
the application to handle this situation, e.g., by linking two code
buffers together and adding a jump instruction in the first one to the
second one.

Anyway, these are just random thoughts.

Thanks,
Ludo’.

Re: Lightning Bindings

[Noah Lavine]

They claim that MELT is tightly integrated with GCC, but after reading http://gcc.gnu.org/wiki/MiddleEndLispTranslator, I don't believe it. The "MELT compiler implementation" description suggests that it's a pretty simple-minded sexp-to-C translator. I also notice that none of the examples has any control structures more complicated than `if` and `foreach`. I'd say it's basically a nice syntax for messing with GCC data structures.

When the page says "very tightly integrated into GCC", it seems to mean "has boxed versions of a few internal GCC data structures" (there's a list on the page I link. It's not very long). That shouldn't be hard at all to connect Guile to.

The only part that could be tricky is interfacing with GCC's garbage collection. I don't know how Guile's FFI interacts with other memory management systems, so this could be a problem, but I think it could be done. It's going to have to be solved anyway if Guile is going to interface with other memory management systems.

Besides, this is one of Guile's objectives, isn't it? GNU programs shouldn't need to implement their own extension languages, because Guile can handle it.

Noah