Guidelines to implement a backend?
Hello, I've experimented with Scheme-to-PHP compilation using GVM (milestone announce below). Now I'd like to implement a complete backend. I need guildelines how to do it. Among questions: * Which primitives should be implemented? * How to generate the complete set of r5rs functions from the primitives? * How to integrate the backend to Gambit? Is it possible to select a backend from command line? * What is the recommended way to distribute a backend? Thanks! Now the announce: Gambit Scheme PHP backend, milestone 1: proof of concept http://github.com/olpa/schemevm/tree/milestone1 http://github.com/downloads/olpa/schemevm/gambit-php-20110208-milestone1.tar... The goal of this release is to mark the milestone 1. I wanted to understand the GVM and to check if compilation to PHP is possible. This is done. While the current gambit-php version is very limited (only a few primitives are partially implemented), it covers all the important functionality: * boot up: "Hello, World" example * recursion: factorial, fibonacci, ackermann * closures: function which return function which return function etc * continuations: basic return example, yin-yang puzzle Scheme code and generated PHP code: http://github.com/olpa/schemevm/tree/milestone1/step-by-step-examples The second use of this milestone release is a demostration how to start a backend. The package contains the minimal amount of code to compile the examples. Therefore, the code is much easier to understand then the code of a complete working backend. I coded straightforward. If I saw a way to solve a problem, I used this way without trying alternatives. In the development process "make it work, make it work correctly, make it work fast", I'm on the step zero "experiment if it would work". One of the consequences is that performance is poor. For example, Ackermann function A(3,9) is 100 times slowed as by gsi-script and 30 times slower as native PHP implementation. The output from yin-yang puzzle is 30 times slower as by gsi-script and 10 times slower as by Guile. However, I'm optimistic and think there is a lot of possibilties for optimization. The code is developed for PHP 4.4.8 and tested under PHP 3.0. -- Oleg Parashchenko olpa@ http://uucode.com/ http://uucode.com/blog/ XML, TeX, Python, Mac, Chess
Afficher les réponses par date
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
Hello Marc, On Tue, 8 Feb 2011 09:53:31 -0500 Marc Feeley <feeley@iro.umontreal.ca> wrote: ...
Do you still want to generate PHP? Is the choice of PHP important or do you want any portable virtual machine?
My big plan is to code a library for developers and sell it. Instead of using a traditional programming language, I'd like to program in a pseudocode (by coincide, it is Scheme R5RS) and generate versions for many platforms: c, java, .net etc. And the main platform is conventional PHP.
PHP is a rather slow VM.
Yes. But at least I hope that Scheme-to-PHP converted code will be not much slower than an equivalent native PHP code. ...
I need guildelines how to do it.
I can help you on your way. I'll reorder your questions: ...
Thanks, the instructions are clear.
Marc
-- Oleg Parashchenko olpa@ http://uucode.com/ http://uucode.com/blog/ XML, TeX, Python, Mac, Chess
On 2011-02-09, at 9:03 AM, Oleg Parashchenko wrote:
Hello Marc,
On Tue, 8 Feb 2011 09:53:31 -0500 Marc Feeley <feeley@iro.umontreal.ca> wrote:
...
Do you still want to generate PHP? Is the choice of PHP important or do you want any portable virtual machine?
My big plan is to code a library for developers and sell it. Instead of using a traditional programming language, I'd like to program in a pseudocode (by coincide, it is Scheme R5RS) and generate versions for many platforms: c, java, .net etc. And the main platform is conventional PHP.
PHP is a rather slow VM.
Yes. But at least I hope that Scheme-to-PHP converted code will be not much slower than an equivalent native PHP code.
If performance is important then I would suggest that you test performance manually, i.e. you compile a Scheme program "by hand" to PHP roughly how Gambit-PHP would do it, and check performance against a program directly coded in PHP. It would be unfortunate if you spent a lot of time developing a PHP back-end for Gambit to discover in the end that the performance is not good enough for your application. My intuition tells me that the code generated by Gambit-PHP will be at best an order of magnitude slower than pure PHP. Marc
On Feb 9, 2011, at 9:03 AM, Oleg Parashchenko wrote:
But at least I hope that Scheme-to-PHP converted code will be not much slower than an equivalent native PHP code.
Maybe you misunderstood what Marc said about this: On Feb 9, 2011, at 9:37 AM, Marc Feeley wrote:
My intuition tells me that the code generated by Gambit-PHP will be at best an order of magnitude slower than pure PHP.
i.e., Marc thinks the Gambit Scheme->PHP generated code will be at least 10 times slower than pure PHP. In my book, that's "much slower." warmest regards, Ralph Raffael Cavallaro raffaelcavallaro@me.com
Is this because the stack needs to be software-emulated in a language such as PHP - is there no way to apply some tough optimizations making the speed loss <=15% or so as compared with code handwritten in the host language? Mikael 2011/2/11 Raffael Cavallaro <raffaelcavallaro@mac.com>
On Feb 9, 2011, at 9:03 AM, Oleg Parashchenko wrote:
But at least I hope that Scheme-to-PHP converted code will be not much slower than an equivalent native PHP code.
Maybe you misunderstood what Marc said about this:
On Feb 9, 2011, at 9:37 AM, Marc Feeley wrote:
My intuition tells me that the code generated by Gambit-PHP will be at best an order of magnitude slower than pure PHP.
i.e., Marc thinks the Gambit Scheme->PHP generated code will be at least 10 times slower than pure PHP. In my book, that's "much slower."
warmest regards,
Ralph
Raffael Cavallaro raffaelcavallaro@me.com
_______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
participants (4)
-
Marc Feeley -
Mikael -
Oleg Parashchenko -
Raffael Cavallaro