Re: thoughts on targetting the web

[Christine Lemmer-Webber <cwebber@dustycloud.org>]

Chris Lemmer-Webber <cwebber@dustycloud.org> writes:

> O M G!  So excited to read this email.  Yes!

So, re-poiking this thread.  I'm still just as excited as I was when I
sent this some time ago!

Any updates?  How can we help?  Can we test things?  Poke at something?
Contribute something?'

I'm excited for this future!

> Andy Wingo writes:
>
>> Hi :)
>>
>> A brain-dump tonight.  I was thinking about what it would mean for Guile
>> to target the web.  The goal would be for Guile to be a useful language
>> for programming client-side interaction on web pages.  Now, there are a
>> number of takes for Schemes of various stripes to target JS.  I haven't
>> made a full survey but my starting point is that in a Guile context, we
>> basically want the Guile Scheme language, which is to say:
>>
>>  1. Tail calls.  The solution must include proper tail calls.
>>
>>  2. Multiple values.  The solution should have the same semantics that
>>     Guile has for multiple-value returns, including implicit
>>     truncation.
>>
>>  3. Varargs.  The solution should allow for rest arguments, keyword
>>     arguments, and the like.
>>
>>  4. Delimited continuations.  The solution should allow non-local exit
>>     from any function, and should allow for capturing stack slices to
>>     partial continuations, and should allow those continuations to be
>>     instantiated multiple times if desired.  We should be able to target
>>     fibers to the web.  Otherwise, why bother?
>>
>>  5. Garbage collection.  *We should re-use the host GC*.  Although it
>>     would be possible to manage a heap in linear memory, that has
>>     retention problems due to cycles between the Guile heap and the JS
>>     heap.
>
> It sounds like from when we spoke not long ago that progress towards the
> WASM-GC proposal has been happening I think?  So this seems feasible?
>
> However, I do think that a "proof of concept" GC would still be an
> advancement.  Like, even lifting the dead-simple version from SICP as a
> stopgap.  We'll all know it's not ideal, but it'll still be progress.
> Getting somethign going and showing it is helpful.
>
> That said, I also know how meh such a proposed approach can feel. ;)
>
>>  6. Numbers.  We should support Scheme's unbounded integers.  Requires
>>     bignums in the limit case, but thankfully JS has bignums now.  We
>>     will still be able to unbox in many cases though.
>>
>>  7. Target existing web.  We shouldn't depend on some future WebAssembly
>>     or JS proposal -- the solution should work in the here and now and
>>     only get better as features are added to the web platform.
>
> Yes.  Though, to jump back again to when you and I talked offline, I
> think what I recommended was that as an early proof of concept, a good
> idea might be to just have a small number of APIs, or even bet, make a
> mini "fantasy console".  Here's an interesting example (and the one we
> talked about, off-list):
>
>   https://euhmeuh.github.io/wasm-adventure/
>
> What's interesting about this first is that it's just a Racket program
> that generates quasiquoted s-expression representation WASM.  Now,
> obviously your compiler will do more interesting things than that.  But
> the second interesting thing is the "fantasy console" component... a set
> of custom interfaces to render a simple 8-bit aesthetic console.
>
> My argument for this is: supporting "the existing web" is a big step.
> Targeting a much smaller number of APIs, and being able to show the
> world a demo that Guile's WASM compiler can do something cool... that's
> very motivating, I think.
>
> But an even simpler hello world would be to simply have access to
> console.log, and write a scheme program that does ye olde Fibonacci
> sequence and spits out the results on the page.  Not as exciting, but
> that's the reasonable (and classic scheme) first step I think.
>
> But yes, target the existing web... eventually!  Just don't get so hung
> up on worrying about those interfaces that it distracts from making
> something that can generate some WASM, is my thoughts.
>
>> From a UX perspective, I would expect we would generally want
>> whole-program compilation with aggressive DCE / tree-shaking, producing
>> a single JS or WebAssembly artifact at build-time.  But that's a later
>> issue.
>
> Yes, focus on things working first... major optimizations can come later!
>
>> I have thought about this off and on over the years but in the end was
>> flummoxed about how to meet all requirements.  However recently I think
>> I have come up with a solution for most of these:
>>
>>  (1) In JS, tail calls are part of ES2015, but not implemented in all
>>      browsers.  In WebAssembly, they are a future plan, but hard for
>>      various reasons.  So in practice the solution for today's web is to
>>      use a universal trampoline and make all calls tail calls --
>>      i.e. call all functions via:
>>
>>        while true:
>>          call(pop())
>>          
>>      Whenever we can target proper tail calls, this will only get
>>      faster.
>>
>>  (2) Neither JS nor WebAssembly have the truncation semantics we want.
>>      Therefore we will return values via an explicit array, and then the
>>      continuation will be responsible for consuming those values and
>>      binding any needed variables.
>>
>>  (3) Although JS does have varargs support, WebAssembly does not.  But
>>      we can actually use the same solution here as we use for (1) and
>>      (2) -- pass arguments on an explicit array + nvalues, and relying
>>      on the function to parse them appropriately.  In this way we can
>>      get Guile keyword arguments.  This also makes the type of Scheme
>>      functions uniform, which is important in WebAssembly contexts.
>>
>>  (4) This is the interesting bit!  As hinted in (1), we will transform
>>      the program such that all calls are tail calls.  This is a form of
>>      minimal CPS conversion -- minimal in the sense that functions are
>>      broken up into the minimum number of pieces to ensure the
>>      all-tail-calls property.  Non-tail calls transform to tail calls by
>>      saving their continuation's state on a stack, which is the same as
>>      stack allocation for these continuations.  The continuation of the
>>      call pops the saved state from the stack.  Because the stack is
>>      explicit, we can manipulate it as data: slice it to capture a
>>      delimited continuation, drop values to make a non-local exit, splat
>>      a saved slice back on to compose a captured delimited continuation
>>      with the current continuation, and so on.  Therefore we have the
>>      necessary primitives to implement delimited continuations as a
>>      library.
>
> I think I understand 15% of this, but the amount I could absorb in the
> limited time I spent stewing on it sounds cool anyway.  Neat!  Most
> importantly, you have a good idea that you think will work, so yay!
>
>>  (5) Scheme needs a representation that can store any value.  In JS this
>>      is easy because JS is untyped.  For WebAssembly, I think I would
>>      lean on externref for this purpose, which effectively boxes all
>>      values.  There are no fixnums in the current WebAssembly spec, so
>>      this is suboptimal, and we have to call out to JS to evaluate type
>>      predicates and access fields.  But, support for structured
>>      GC-managed types is coming to WebAssembly, which will speed up
>>      object access.
>>
>>  (6) The easy solution here is to make JS numbers, which are doubles at
>>      heart, represent flonums, and use JS bignums for Scheme integers.
>>      Fine.
>>
>>  (7) This principle has been taken into account in (1)-(6).
>>
>> Now, a note on the transformation described in (4), which I call
>> "tailification".
>>
>> The first step of tailification computes the set of "tails" in a
>> function.  The function entry starts a tail, as does each return point
>> from non-tail calls.  Join points between different tails also start
>> tails.
>>
>> In the residual program, there are four ways that a continuation exits:
>>
>>   - Tail calls in the source program are tail calls in the residual
>>     program; no change.
>>
>>   - For non-tail calls in the source program, the caller saves the state
>>     of the continuation (the live variables flowing into the
>>     continuation) on an explicit stack, and saves the label of the
>>     continuation.  The return continuation will be converted into a
>>     arity-checking function entry, to handle multi-value returns; when
>>     it is invoked, it will pop its incoming live variables from the
>>     continuation stack.
>>
>>   - Terms that continue to a join continuation are converted to label
>>     calls in tail position, passing the state of the continuation as
>>     arguments.
>>
>>   - Returning values from a continuation pops the return label from the
>>     stack and does an indirect tail label call on that label, with the
>>     given return values.
>>
>> I expect that a tailified program will probably be slower than a
>> non-tailified program.  However a tailified program has a few
>> interesting properties: the stack is packed and only contains live data;
>> the stack can be traversed in a portable way, allowing for
>> implementation of prompts on systems that don't support them natively;
>> and as all calls are tail calls, the whole system can be implemented
>> naturally with a driver trampoline on targets that don't support tail
>> calls (e.g. JavaScript and WebAssembly).
>>
>> This algorithm is implemented in the wip-tailify branch in Guile's git.
>>
>> I have this little driver program:
>>
>>     (use-modules (system base compile)
>>                  (system base language)
>>                  (language cps tailify)
>>                  (language cps verify)
>>                  (language cps renumber)
>>                  (language cps dce)
>>                  (language cps simplify)
>>                  (language cps dump))
>>
>>     (define (tailify* form)
>>       (let ((from 'scheme)
>>             (make-lower (language-lowerer (lookup-language 'cps)))
>>             (optimization-level 2)
>>             (warning-level 2)
>>             (opts '()))
>>         (define cps
>>           ((make-lower optimization-level opts)
>>            (compile form #:from 'scheme #:to 'cps #:opts opts
>>                     #:optimization-level optimization-level
>>                     #:warning-level warning-level
>>                     #:env (current-module))
>>            (current-module)))
>>         (format #t "Original:\n")
>>         (dump cps)
>>         (format #t "\n\nTailified:\n")
>>         (let* ((cps (tailify cps))
>>                (cps (verify cps))
>>                (cps (eliminate-dead-code cps))
>>                (cps (simplify cps))
>>                (cps (renumber cps)))
>>           (dump cps))))
>>
>> If I run this on the following lambda:
>>
>>   (lambda (x)
>>     (pk x
>>         (if x
>>             (pk 12)
>>             (pk 42))))
>>
>> Then first it prints the dump of the optimized CPS:
>>
>>   Original:
>>   L0:
>>     v0 := self
>>     L1(...)
>>   L1:
>>     receive()
>>     v1 := current-module()                      ; module 
>>     cache-set![0](v1)
>>     v2 := const-fun L7                          ; _ 
>>     return v2
>>
>>   L7:
>>     v3 := self
>>     L8(...)
>>   L8:
>>     v4 := receive(x)                            ; x 
>>     v5 := cache-ref[(0 . pk)]()                 ; cached 
>>     heap-object?(v5) ? L16() : L11()
>>   L16():
>>     L17(v5)
>>   L11():
>>     v6 := cache-ref[0]()                        ; mod 
>>     v7 := const pk                              ; name 
>>     v8 := lookup-bound(v6, v7)                  ; var 
>>     cache-set![(0 . pk)](v8)
>>     L17(v8)
>>   L17(v9):                                      ; box 
>>     v10 := scm-ref/immediate[(box . 1)](v9)     ; arg 
>>     false?(v4) ? L22() : L19()
>>   L22():
>>     v12 := const 42                             ; arg 
>>     call v10(v12)
>>     L25(receive(arg, rest...))
>>   L19():
>>     v11 := const 12                             ; arg 
>>     call v10(v11)
>>     L25(receive(arg, rest...))
>>   L25(v13, v14):                                ; tmp, tmp 
>>     tail call v10(v4, v13)
>>
>> Then it prints the tailified version:
>>
>>   L0:
>>     v0 := self
>>     L1(...)
>>   L1:
>>     receive()
>>     v1 := current-module()                      ; module 
>>     cache-set![0](v1)
>>     v2 := const-fun L8                          ; _ 
>>     v3 := restore1[ptr]()                       ; ret 
>>     tail calli v3(v2)
>>
>>   L8:
>>     v4 := self
>>     L9(...)
>>   L9:
>>     v5 := receive(x)                            ; x 
>>     v6 := cache-ref[(0 . pk)]()                 ; cached 
>>     heap-object?(v6) ? L17() : L12()
>>   L17():
>>     L18(v6)
>>   L12():
>>     v7 := cache-ref[0]()                        ; mod 
>>     v8 := const pk                              ; name 
>>     v9 := lookup-bound(v7, v8)                  ; var 
>>     cache-set![(0 . pk)](v9)
>>     L18(v9)
>>   L18(v10):                                     ; box 
>>     v11 := scm-ref/immediate[(box . 1)](v10)    ; arg 
>>     false?(v5) ? L24() : L20()
>>   L24():
>>     v14 := const 42                             ; arg 
>>     v15 := code L37                             ; cont 
>>     save[(scm scm ptr)](v5, v11, v15)
>>     tail call v11(v14)
>>   L20():
>>     v12 := const 12                             ; arg 
>>     v13 := code L29                             ; cont 
>>     save[(scm scm ptr)](v5, v11, v13)
>>     tail call v11(v12)
>>
>>   L29:
>>     L30(...)
>>   L30:
>>     v16, v17 := receive(arg, rest...)           ; tmp, tmp 
>>     v18, v19 := restore[(scm scm)]()            ; restored, restored 
>>     tail callk L34(_, v18, v19, v16)
>>
>>   L34:
>>     meta: arg-representations: (scm scm scm)
>>     L35(...)
>>   L35(v20, v21, v22):                           ; _, _, _ 
>>     tail call v21(v20, v22)
>>
>>   L37:
>>     L38(...)
>>   L38:
>>     v23, v24 := receive(arg, rest...)           ; tmp, tmp 
>>     v25, v26 := restore[(scm scm)]()            ; restored, restored 
>>     tail callk L34(_, v25, v26, v23)
>>
>> I think I would like to implement the "save" and "restore" primcalls on
>> stock Guile, to be able to adequately test tailification.  But then I'd
>> look at targetting WebAssembly (just to make it interesting; run-time
>> performance would be faster no doubt if I targetted JS, due to GC
>> concerns).
>>
>> Anyway, thoughts welcome.  Happy hacking :)
>>
>> Andy
>
> This is all great.  I think getting something that works well enough to
> write some proof-of-concept demos in is the real goal.  If you can make
> something that can compile just enough to WASM where me adding the
> fantasy console stuff would help (I might just lift wasm-adventure's),
> then I think we could make some pretty cool demos for the world.  Maybe
> we could even have a special guile-fantasy-console gamejam? ;)
>
> Anyway exciting, exciting, exciting!  My main advice in all of it: don't
> let great be the enemy of good-enough, and all that.  Getting to the
> point where we're able to do *something* is still useful, if the hooks
> are in place to iterate from good-enough to great over time.
>
> Yay!
>
>  - Chris