[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Summer of Code Recap
From: |
Christopher Lemmer Webber |
Subject: |
Re: Summer of Code Recap |
Date: |
Tue, 11 May 2021 11:19:41 -0400 |
User-agent: |
mu4e 1.4.15; emacs 27.2 |
I suspect what changed most of all is in commit
4311dc9858ba7c6db50a851e95fc7c387b9381b2
Right now in compile-js.scm it does:
(define lower-cps (@@ (language cps optimize) lower-cps))
(define (compile-js exp env opts)
;; TODO: I should special case the compilation for the initial fun,
;; as this is the entry point for the program, and shouldn't get a
;; "self" argument, for now, I add "undefined" as the first
;; argument in the call to it.
;; see compile-exp in (language js-il compile-javascript)
(define (intmap->program map)
(intmap-fold-right (lambda (kfun body accum)
(acons (make-kid kfun)
(compile-fun (intmap-select map body) kfun)
accum))
(compute-reachable-functions map 0)
'()))
(values (make-program (intmap->program (lower-cps exp opts))) env env))
That last line, with the lower-cps... well, it looks like assumptions
have changed. Based on reading the commit history, it looks like this
step is now done *before* handing it over to
compile-bytecode/compile-js.
So my guess would be something like:
diff --git a/module/language/cps/compile-js.scm
b/module/language/cps/compile-js.scm
index 128f5d64d..3c95c105f 100644
--- a/module/language/cps/compile-js.scm
+++ b/module/language/cps/compile-js.scm
@@ -44,7 +44,7 @@
accum))
(compute-reachable-functions map 0)
'()))
- (values (make-program (intmap->program (lower-cps exp opts))) env env))
+ (values (make-program (intmap->program exp)) env env))
This does not work, however. Not sure why, or what really should be done...
Christopher Lemmer Webber writes:
> I've now verified that the place where things fall apart is fairly
> simple. The following file does not compile:
>
> (define (add x y)
> (+ x y))
>
> (add 1 2)
>
> So yeah, it's just functions in general.
>
> It looks like the stage where things are breaking is between the
> cps -> js-il representations.
>
> I figured since probably the changes need to happen in
> module/language/cps/compile-js.scm, I should look at
> the commit log in compile-bytecode.scm in that same directory.
> It looks like a lot has changed since 2017!
>
> I suspect I need help at this stage! :)
>
>
> Christopher Lemmer Webber writes:
>
>> Hi!
>>
>> Ian did some great work here in the past... let's not let it go to
>> waste. Let's try to merge it!
>>
>> I've made a branch in my gitlab repo here:
>>
>> https://gitlab.com/dustyweb/guile.git
>>
>> the branch is "compile-to-js-merge"
>>
>> I've dealt with the merge conflicts and etc I've been able to identify,
>> but things have already started to bitrot... I'd like to prevent them
>> from bitrotting further. I fixed some things, updating the code to
>> where it appears things have shuffled around to as best as I could.
>>
>> Currently I can get a file as simple as "just-plus.scm" to compile:
>>
>> (+ 1 2)
>>
>> This outputs to:
>>
>> function (unit_cont){var k_0 = function (v_0,k_4){var k_1 = function
>> (v_0){var v_1 = 3;return k_4(v_1);};if ((arguments["length"])==(2)) {{return
>> k_1(v_0);}} else {{return undefined;}}};return k_0(undefined,unit_cont);};
>>
>> Progress!
>>
>> However, the amb.scm file no longer works as described below. I get the
>> following:
>>
>> In language/cps/intset.scm:
>> 472:6 3 (visit-branch #(4294967295 1073741823 #f #f #f #f #f #f (#f))
>> _ 0 # #)
>> 472:6 2 (visit-branch 4294967295 _ 0 _ _)
>> In language/cps/split-rec.scm:
>> 78:22 1 (_ _ _ _)
>> In ice-9/boot-9.scm:
>> 1685:16 0 (raise-exception _ #:continuable? _)
>>
>> ice-9/boot-9.scm:1685:16: In procedure raise-exception:
>> Throw to key `match-error' with args `("match" "no matching pattern" #<cps
>> (const-fun 62)>)'.
>>
>> I guess that's something that probably changed. I'm going to look into
>> it...
>>
>> Anyway, is there support from the maintainers from getting this merged
>> if I can get things working again? I'd really like to see this effort
>> not go to waste... I'd even like to write a few demos using it.
>>
>>
>> Ian Price writes:
>>
>>> 1 Introduction
>>> ==============
>>>
>>> As many of you are aware, I have been working on compiling Guile
>>> Scheme to JavaScript this summer, as part of the Google Summer of
>>> Code. This post serves to bookend my work for the year.
>>>
>>> Before I go any further, I have to give my thanks to my mentor [Chris
>>> Webber], without whom this project would have fizzled out weeks ago;
>>> Google and the Gnu Project, naturally, for providing the Summer of
>>> Code and allowing me to work on this project; and our fearless leader,
>>> [Andy Wingo], for answering a wide variety of stupid questions.
>>>
>>>
>>> [Chris Webber] https://dustycloud.org/
>>>
>>> [Andy Wingo] https://wingolog.org/
>>>
>>>
>>> 2 Project Aims
>>> ==============
>>>
>>> For a full introduction to the project, you can of course refer back
>>> to my [project proposal], but very briefly my hopes for this summer
>>> were:
>>>
>>> 1. To rewrite the previous version of my compiler from the [previous
>>> CPS representation] to use the new representation ["CPS Soup"]
>>> representation.
>>> 2. To completely port ice-9/boot-9.scm (our basic "prelude") to
>>> JavaScript, and in particular, to support the [Guile Module
>>> system].
>>> 3. To handle Proper Tail Calls by use of the [Cheney on the MTA]
>>> strategy.
>>> 4. To include a new `guild' script for bundling compiled JS files with
>>> their dependencies.
>>>
>>>
>>> [project proposal] https://shift-reset.com/static/docs/gsoc-2017.pdf
>>>
>>> [previous CPS representation]
>>> https://wingolog.org/archives/2014/01/12/a-continuation-passing-style-intermediate-language-for-guile
>>>
>>> ["CPS Soup"] https://wingolog.org/archives/2015/07/27/cps-soup
>>>
>>> [Guile Module system]
>>> https://www.gnu.org/software/guile/manual/html_node/Modules.html#Modules
>>>
>>> [Cheney on the MTA] http://www.pipeline.com/~hbaker1/CheneyMTA.html
>>>
>>>
>>> 3 What was Achieved
>>> ===================
>>>
>>> You can find all of my work on the [compile-to-js-2017] branch of my
>>> Gitlab. A full list of the commits can be found [here], but I will
>>> summarise the changes now:
>>>
>>>
>>> [compile-to-js-2017]
>>> https://gitlab.com/ijp/guile/tree/compile-to-js-2017
>>>
>>> [here] https://gitlab.com/ijp/guile/compare/1b36a76e...gsoc-2017-end
>>>
>>> 3.1 Compile Guile CPS Soup to JavaScript
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> When I was working on my initial attempt at compiling Guile to
>>> JavaScript, two years ago, Guile used a different CPS representation
>>> as its intermediate language. The initial experiments with the CPS
>>> Soup representation occurred while that work was ongoing, but as it
>>> was not considered "stable", the plan was not to move to this
>>> representation until after I had completed my other objectives.
>>>
>>> Now, however, CPS Soup is the IL of Guile, and so the first task that
>>> was accomplished was to move to this representation. Since I had
>>> already created my own JS-IL as a target, I did not need to make any
>>> changes to the code generation side from JS-IL to JavaScript proper.
>>> The main change was to reconstruct the nested scope structure that was
>>> implicit in the dominator structure that Guile made available.
>>>
>>> The full code for the compiler is split into several sections,
>>> corresponding to different stages in the compiler pipeline.
>>>
>>>
>>> 3.1.1 CPS to JS-IL Compiler
>>> ---------------------------
>>>
>>> - module/language/cps/compile-js.scm
>>> - module/language/cps/spec.scm
>>>
>>> These modules constitute the compiler from CPS to my JS-IL
>>> intermediate language.
>>>
>>>
>>> 3.1.2 JS-IL to JavaScript Compiler
>>> ----------------------------------
>>>
>>> - module/language/js-il.scm
>>> - module/language/js-il/compile-javascript.scm
>>> - module/language/js-il/inlining.scm
>>> - module/language/js-il/spec.scm
>>>
>>> These modules constitute a somewhat ad-hoc intermediate representation
>>> as a target for the CPS compiler. It differs from JavaScript, e.g., by
>>> continuing to separate continuations and functions, and a slightly
>>> specialised function representation to handle Guile's complicated
>>> notion of procedure arity.
>>>
>>>
>>> 3.1.3 JavaScript Representation
>>> -------------------------------
>>>
>>> - module/language/javascript.scm
>>> - module/language/javascript/simplify.scm
>>> - module/language/javascript/spec.scm
>>>
>>> This is primarily the representation of JavaScript as Scheme Records.
>>> This is separate from the representation of JavaScript Guile already
>>> has in the form of `(language ecmascript)' primarily to avoid a
>>> circularity when Guile determines which compilers to run in the
>>> pipeline, as recommended by Andy Wingo.
>>>
>>>
>>> 3.2 A pre-amble capable of running through boot-9
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> In order to run Guile, it is not enough to be able to compile Scheme
>>> (or indeed any other language supported by Guile) forms to JavaScript,
>>> we also need to incorporate as much of Guile's runtime as possible.
>>> This involves implementing VM primitives (such as you might see in
>>> vm-engine.c); basic Guile types like Symbols, Pairs, and Structs; as
>>> well as many of the functions that Guile implements in C rather than
>>> Scheme.
>>>
>>> Although I certainly did not implement all of the functionality Guile
>>> achieves, I was able to implement sufficiently many (including what
>>> amounts to a port of much of module.c) that one can successfully run
>>> though ice-9/boot-9.scm from start to finish.
>>>
>>> This took up the bulk of the time I spent on this project, due to the
>>> size of the compiled output of boot-9.scm, and my own difficulties
>>> debugging the bootstrap process. More on this below.
>>>
>>> The code can be found at
>>> - module/language/js-il/runtime.js
>>>
>>>
>>> 3.3 A linking script for JavaScript
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> Since we are using the `(language ...)' infrastructure, we can take
>>> advantage of the existing `guild compile' script for compiling to
>>> JavaScript, we simply need to use the `--to' switch. However, this
>>> does not produce a file which you can just load up without any
>>> additional work, especially if you are working with multiple modules.
>>>
>>> In order to make it easier to deal with this, I have included a `guild
>>> jslink' script, which can be used to package up a "main" script along
>>> with the `runtime.js' and its dependencies. See below for an example.
>>>
>>> The code can be found at
>>> - module/scripts/jslink.scm
>>>
>>>
>>> 4 What was not Achieved
>>> =======================
>>>
>>> 4.1 Cheney on the MTA
>>> ~~~~~~~~~~~~~~~~~~~~~
>>>
>>> One of my regrets is that I did not implement Baker's "Cheney on the
>>> MTA" (as seen in [Chicken Scheme]) for handling Proper Tail Calls in
>>> JavaScript. Historically, JavaScript has not guaranteed that tail
>>> position function calls do not grow the stack, and this is obviously
>>> of fundamental importance for languages like Scheme. Fortunately, ES6
>>> has added support for [proper tail calls] and we can expect to see
>>> increased support for it in future JavaScript versions. (Indeed,
>>> during testing on node v.6.10.3, I did not have to increase the stack
>>> size until very late).
>>>
>>>
>>> [Chicken Scheme] https://www.call-cc.org/
>>>
>>> [proper tail calls]
>>> https://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls
>>>
>>>
>>> 5 How to use it
>>> ===============
>>>
>>> I've talked a lot about what I've did and didn't do, but what about
>>> actually using this thing?
>>>
>>>
>>> 5.1 Obtaining the Code
>>> ~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> The code is not currently available from the main Guile repository,
>>> but only the `compile-to-js-2017' branch on my [GitLab].
>>>
>>> If you already have a checkout of guile, you can add my repo as a
>>> remote with
>>> ,----
>>> | $ git remote add ijp https://gitlab.com/ijp/guile.git
>>> `----
>>> and fetch the branch with
>>> ,----
>>> | $ git fetch ijp
>>> `----
>>>
>>> You can then check out the `compile-to-js-2017' branch and build as
>>> normal.
>>>
>>>
>>> [GitLab] https://gitlab.com/ijp/guile/tree/compile-to-js-2017
>>>
>>>
>>> 5.2 A Non-Trivial Example
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> As an example of how to use the JS Backend that is short, but
>>> non-trivial, I am using John McCarthy's `amb' operator (see [A Basis
>>> for a Mathematical Theory of Computation]) to search for Pythagorean
>>> Triples.
>>>
>>> First we have a module for the `amb' operator in amb.scm
>>> ,----
>>> | (define-module (amb)
>>> | #:export (amb fail))
>>> |
>>> | (define original-fail
>>> | (lambda _
>>> | (error 'amb "No more paths to search")))
>>> |
>>> | (define *amb-fail* original-fail)
>>> |
>>> | (define (fail)
>>> | (*amb-fail* #f))
>>> |
>>> | (define (amb-thunks . values)
>>> | (let ((failure *amb-fail*))
>>> | (call/cc (lambda (escape)
>>> | (for-each (lambda (value)
>>> | (call/cc (lambda (continue)
>>> | (set! *amb-fail* continue)
>>> | (escape (value)))))
>>> | values)
>>> | (failure #f)))))
>>> |
>>> | (define-syntax amb
>>> | (syntax-rules ()
>>> | ((amb exprs ...)
>>> | (amb-thunks (lambda () exprs) ...))))
>>> `----
>>>
>>> Next we have the code performs the search in triple.scm
>>> ,----
>>> | (use-modules (amb))
>>> |
>>> | (let ((a (amb 4 5 6 7 8 9 10))
>>> | (b (amb 4 5 6 7 8 9 10))
>>> | (c (amb 4 5 6 7 8 9 10)))
>>> | (if (= (* c c) (+ (* a a) (* b b)))
>>> | (list a b c)
>>> | (fail)))
>>> `----
>>>
>>> We compile the files in the usual manner, only now we specify the
>>> `javascript' language (We make sure to add the current directory to
>>> the load-path for triple.scm).
>>>
>>> ,----
>>> | $ guild compile amb.scm --to=javascript --output=amb.js
>>> | $ guild compile -L . triple.scm --to=javascript --output=triple.js
>>> `----
>>>
>>> Next we link the two together into a file main.js, making sure to
>>> specify amb.js as a dependency of triple.js. (This step will take a
>>> little while, since it also compiles a bunch of dependencies)
>>>
>>> ,----
>>> | $ guild jslink triple.js -o main.js --depends="(\"amb\" . \"amb.scm\")"
>>> `----
>>>
>>> Finally, you can run it with `node', although as mentioned above you
>>> may have to increase the stack size.
>>>
>>> ,----
>>> | $ node --stack-size=2000 main.js
>>> `----
>>>
>>> Which should, fingers crossed, print out the triple 6,8,10.
>>>
>>>
>>> [A Basis for a Mathematical Theory of Computation]
>>> http://www-formal.stanford.edu/jmc/basis1.pdf
>>>
>>>
>>> 6 What is next?
>>> ===============
>>>
>>> Having recapped what was and what was not achieved, the next question
>>> is: where does the project go from here? I have been asked about my
>>> plans for all sorts of features, e.g. support for [Web Assembly], but
>>> I think the following things are the most important to think about.
>>>
>>>
>>> [Web Assembly] http://webassembly.org/
>>>
>>> 6.1 Inclusion into Guile
>>> ~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> The entire point of the project is to have something that can be
>>> included in Guile proper. I have not spoken with Guile's maintainers
>>> about incorporation into the main distribution, but I expect there
>>> would be not be too many problems with moving the "official branch" to
>>> the main repository.
>>>
>>>
>>> 6.2 All Guile built-ins in runtime.js
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> Although I have included enough to get though boot-9.scm, this does
>>> not include all of the built-ins we would want in our programs. Two
>>> things I use very often which do not appear in runtime.js are ports
>>> and bytevectors.
>>>
>>> We would like most, if not all, Guile built-ins to be available for
>>> those who need them, so these will need to be implemented. However,
>>> this is a lot of extra code for some people who don't need it, which
>>> brings us to a different issue...
>>>
>>>
>>> 6.3 Linking Guile Modules & Features
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> In [a blog post], Andy Wingo lays out many tasks that he would like to
>>> see in a future Guile. One of the most important of these, for us, are
>>> under the headings "linking multiple modules together" and "linking a
>>> single executable". To grossly simplify, we want to be able to link
>>> various files into one single executable, which contains all and only
>>> the code we need for our application.
>>>
>>> As it stands, I included a simple script `guild jslink' that bundles
>>> various compiled JavaScript files into one file, but we would like it
>>> to be much more featureful: removing modules, functions, even types we
>>> don't need; and inferring which modules are required by our
>>> application and bundling them without requiring the information
>>> `jslink' does. This would allow us to minimise the amount of code that
>>> needs to be sent over the network, which is very important to web
>>> developers.
>>>
>>> This is a large task, and one I don't know enough about at the moment
>>> to attempt, but it is work that would benefit not just our JavaScript
>>> compiler, but people who want to deploy regular Guile applications.
>>>
>>>
>>> [a blog post]
>>> https://wingolog.org/archives/2016/02/04/guile-compiler-tasks
>>>
>>>
>>> 6.4 JavaScript Version
>>> ~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> I am not an expert in JavaScript, in fact, before this summer I
>>> probably hadn't written it for two years, which means the code
>>> certainly does not match up with the current best practices and
>>> specifications. Further, all of my testing for this compiler was done
>>> on [Node.js] v.6.10.3 only (this was the version available in the
>>> Fedora 25 repositories).
>>>
>>> The code should be vetted to determine precisely which modern JS
>>> features are used (I believe proper tail calls, and ES6 Maps are the
>>> main ones), and it should be tested on all major browsers. If
>>> necessary, we should incorporate switches in the compiler to allow JS
>>> users to compile for particular implementations, taking advantage of
>>> particular modern JS features, or providing our own implementations of
>>> those that are not supported (e.g. Cheney on the MTA).
>>>
>>>
>>> [Node.js] https://nodejs.org/en/
>>>
>>>
>>> 6.5 JS Integration
>>> ~~~~~~~~~~~~~~~~~~
>>>
>>> One of the strengths of Guile is that it allows people to integrate
>>> their Scheme and C code, and although it has not been a focus for this
>>> summer, we should aim to provide similar levels of integration between
>>> Scheme and JS. There are two cases to consider.
>>>
>>>
>>> 6.5.1 JS calling Scheme
>>> -----------------------
>>>
>>> As it stands, you can perform some limited interaction from JavaScript
>>> in a similar manner to how you would interact with Guile from C. For
>>> instance, by using `scm_current_module', `scm_public_lookup', and the
>>> `scheme.Symbol' constructor, one could look up a scheme function, e.g.
>>> `iota', and then invoke it by `scheme.call'.
>>>
>>> That said, C idioms are not JS idioms, and so we should work to
>>> provide a much nicer API through the `scheme' object.
>>>
>>>
>>> 6.5.2 Scheme calling JS
>>> -----------------------
>>>
>>> In the case of Scheme calling JavaScript, I think we should follow the
>>> example of `(system foreign)', which provides an API for linking to
>>> dynamic C libraries, and creating Scheme versions of C functions, and
>>> automatically marshalling/unmarshalling C types to Scheme types. One
>>> additional complication we would have with JS would be the presence of
>>> exceptions, but I think these could also be marshalled into Scheme
>>> ones without much trouble.
>>>
>>>
>>> 7 Lessons Learned
>>> =================
>>>
>>> It goes without saying that a project like this teaches you a lot
>>> about the technical design of Guile, how to navigate the codebase,
>>> etc, but I want to highlight a few "softer" lessons from this summer.
>>>
>>>
>>> 7.1 Compilers are "Easy", Runtimes are Hard
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> When I first set out to write this project two summers ago, I
>>> naturally assumed that the majority of the effort would go into the
>>> compiler, and much less into the built-ins. In reality, the effort was
>>> reversed. Partly this was due to my experience in writing Scheme, and
>>> Functional Programming more generally, meant that the tree-traversing
>>> code typical of a compiler pass was relatively straightforward, and
>>> the compiler was not doing a lot of optimisation, mostly code
>>> generation.
>>>
>>>
>>> 7.2 Bootstrapping is Hard
>>> ~~~~~~~~~~~~~~~~~~~~~~~~~
>>>
>>> The last point leads into this one, bootstrapping is pretty tricky.
>>> With boot-9, you have several versions of the module system at
>>> different times. My own attempt to write module code that handled this
>>> ended up being abandoned for a rewrite that more closely followed the
>>> Guile C code. The size of the compiled boot-9 code, and the, at times,
>>> non-local consequences of implementing certain built-ins made it
>>> tricky to debug.
>>>
>>>
>>> 7.3 Don't Panic
>>> ~~~~~~~~~~~~~~~
>>>
>>> This is a much more personal one, and one that I think is very
>>> important for anyone who wants to take part in a program like the
>>> Summer of Code, where you are spending a lot of time mostly on your
>>> own. In a complex software project, things are not always going to go
>>> smoothly. You might spend weeks banging up against a difficult
>>> problem. Don't Panic! If it was easy it would have already been done.
>>> Keep in Contact with your Mentor! It is tempting to only check in when
>>> you think you have something of progress to report, but they are there
>>> to help you, and explaining your issues to someone else is often very
>>> useful when trying to overcome them, even if they don't have an answer
>>> for you.
>>>
>>>
>>> 8 Wrapping Up
>>> =============
>>>
>>> If you are still with me, good on you. As the new semester is starting
>>> I will be devoting much less time to this, and that will likely be
>>> true till December, but I will make an effort to keep up with
>>> guile-user and be on the IRC Channel to help the daring souls who want
>>> to give this a go. My priorities will be documenting the ILs, filling
>>> in missing builtins, and improving jslink. I especially want to see
>>> basic IO and MiniKanren up and running, and for it to be convenient to
>>> use Guile's builtin libraries.
>>>
>>>
>>> Happy Hacking, Ian Price
>>>
>>> (This is a crosspost to guile-user of my blogpost [Summer of Code
>>> Recap], but please comment on this list, rather than there)
>>>
>>> [Summer of Code Recap]
>>> https://shift-reset.com/blog/2017/8/28/Summer%20of%20Code%20Recap/