[gambit-list] Guidelines to implement a backend?

Marc Feeley feeley at iro.umontreal.ca
Tue Feb 8 09:53:31 EST 2011


On 2011-02-08, at 8:46 AM, Oleg Parashchenko wrote:

> Hello,
> 
> I've experimented with Scheme-to-PHP compilation using GVM (milestone
> announce below).

I'm really quite impressed!  Your back-end is short and simple, and it clearly achieves the goal of demonstrating a proof of concept.

> Now I'd like to implement a complete backend.

Do you still want to generate PHP?  Is the choice of PHP important or do you want any portable virtual machine?  PHP is a rather slow VM.  More efficient and more portable would be Java and JavaScript.  Given the simplicity of GVM, you could also write a GVM interpreter (in C/C++) and generate some bytecode for that.  There are many options... I don't see a particular advantage to target PHP.

> I need
> guildelines how to do it.

I can help you on your way.  I'll reorder your questions:

> Among questions:
> 
> * How to generate the complete set of r5rs functions from the primitives?

The r5rs functions (and much more) are implemented in the lib/*.scm files which must be compiled by the Gambit compiler.  For example, in lib/_std.scm you'll find these definitions which implement the null? predefined function:

(define-prim (##null? obj)
  (##eq? obj '()))

(define-prim (null? obj)
  (macro-force-vars (obj)
    (##null? obj)))

The define-prim macro, which is defined in lib/_gambit#.scm, has a list of all the primitives defined by the back-end.  When the function being defined by define-prim is a primitive that the back-end implements, the define-prim macro generates a function definition which calls that primitive.  Otherwise, the macro generates a function definition which expands to the body.  In this example, the expansion will be one of the two following pieces of code:

;; when the back-end implements ##null?
(define (##null? obj) (##null? obj))
(define (null? obj) (##null? obj)) ;; note: macro-force-vars normally expands to its body

;; when the back-end DOES NOT implement ##null?
(define (##null? obj) (##eq? obj '())) ;; express ##null? in terms of ##eq?
(define (null? obj) (##null? obj))

Note that in the first case there will not be an infinite recursion because the back-end inlines the call to ##null? (i.e. it does not generate a function call to itself).

> 
> * Which primitives should be implemented?

In some cases you will find define-prim definitions with no body, like this one from lib/_std.scm:

(define-prim (##pair? obj))

This means that the ##pair? function must be implemented by the back-end because there is no (efficient) way to express it in terms of other primitives.

This approach allows an incremental path of implementation of the primitives.  You must implement all the ones for which the define-prim has no body.  The others are optional, but every one that you add to the back-end will improve the performance.

I would start with fixnum arithmetic (##fx+, ##fx=, etc), and ##eq?, ##car, ##cdr, ##cons, ##pair?, which are required to implement many other library functions.

For a complete list of the primitives, check gsc/_prims.scm .  There are over 400 "##" primitives.

> 
> * How to integrate the backend to Gambit?

You've already done that!  When you load a back-end implementation it gets registered as one of the available back-ends.  To integrate it permanently, you have to change the makefile so that when gsc is built, the new back-end is linked with the rest of the compiler.  The last back-end that is loaded is the default back-end.

> Is it possible to select
> a backend from command line?

Not currently, but I will be adding this as a command-line option soon (to support the x86 back-end).

> 
> * What is the recommended way to distribute a backend?

At this point it is the Gambit dumping grounds.  If the back-end is robust, usable and not too big, and there is user interest, then it could be integrated into the Gambit distribution itself.

Marc




More information about the Gambit-list mailing list