Core language (was: letrec*-values)

[mnieper]

The middle-end of Rapid Scheme now rewrites all occurrences of letrec*-values into let-values and letrec* constructs. The letrec* construct is only used for procedure bindings. Thus you may be able to remove letrec*-values from your runtime.

When I have finished the next pass, multiple values should have gone as well, simplifying the output even more. But there is no ETA yet.

[okuoku]

Yeah, I have removed it locally and it will gone on the next push :)

(Perhaps I'd better to have git-submodule copy of upstream so I can easily determine which version I was adopted to. Of course it is OK to change anything on upstream; I know we're on early-stage ;)

[mnieper]

I have pushed the branch cps-transform to the repository so that you can preview how the output will look after CPS transform (that eliminates the exception handling primitives, call/cc, call-with-values, etc.).

The output maintains a calling stack (for error reporting), which, however, is currently unused. The output thus contains a lot of syntax location, making it rather large.

In case, Gambit does not support SRFI 38, you will have to patch the output of syntax literals in (rapid expressions).

Caveat: While the output after the cps-transform is conceptually much simpler than the output of the previous pass, Larceny's optimizer is not sophisticated enough to compile it in reasonable time. I may have to do some code profiling - any help gladly accepted. :-)

Well, maybe Gambit can compile the code in continuation-passing-style much faster.

[okuoku]

Well, maybe Gambit can compile the code in continuation-passing-style much faster.

No, unfortunately. I have tried cps-transform branch, it generated 14MiB of code and it did not finish compile... It consumed 8GiB of memory:

As @feeley 's the Gambit-inside-out talk says, Gambit also uses sort-of CPS IR. So I feel just translating code into CPS would not contribute any of optimisation because Gambit itself also do so too anyway.

Caveat: While the output after the cps-transform is conceptually much simpler than the output of the previous pass, Larceny's optimizer is not sophisticated enough to compile it in reasonable time.

Generally speaking, most of Scheme implementations love complex code; keep program structure anywhere possible and let them optimize let or case as well. ie.) shorter code would require little memory and it should be faster.

In other words: If you expect optimisation on the backend Scheme implementation, then try to generate written-by-a-human like code where possible! ...perhaps deeply-nested letrecs are unfortunately not.

Actually, I also tried to develop R7RS frontend for Gambit(and our own R6RS, NMosh) before, that -- keeping language constructs such as let or case and program structure -- was really complex topic for me, especially i'd wanted to support wider Scheme backends.

Perhaps it would not share certain amounts of efforts that developing Scheme frontend/backend combination from scratch and do so for existing Scheme implementation. I'm also exploring this problem and I haven't get any closer though.

[okuoku]

(let me add a label and change subject since I think it contains good discussion here :)

[mnieper]

In other words: If you expect optimisation on the backend Scheme implementation, then try to generate written-by-a-human like code where possible! ...perhaps deeply-nested letrecs are unfortunately not.

While the deeply-nested letrecs may somehow be alleviated by syntax-transforming them into a flat structure by redefining letrec in (rapid primitive), at least one problem remains: CPS-transforming a program is not idempotent. So if Rapid Scheme's expander CPS-transform the input program and Gambit internally does as well, the resulting code will most likely be sub-optimal. (Gambit does not have the knowledge that no call will ever return, e.g. that its input is already in CPS.)

Nevertheless, I have continued my experiments with the CPS-transformation pass (so that Rapid Scheme gets full control of the evaluation model, including call/cc). I am planning to add further passes which reduce the complexity again (e.g. http://users-cs.au.dk/danvy/sfp12/papers/keep-hearn-dybvig-paper-sfp12.pdf) so that, hopefully, the code will be digestible for R7RS implementations again and so that the way for a native Rapid Scheme back-end will be paved.

During my experiments, however, I stumbled across a strange error with Larceny, which may be one or the reason why Larceny could not digest the CPS-transformed code earlier: https://github.com/larcenists/larceny/issues/782.

Do you happen to have an idea what is going on? Maybe the bug does not lie within Larceny itself but in the R6RS expander it is using.

[okuoku]

Do you happen to have an idea what is going on? Maybe the bug does not lie within Larceny itself but in the R6RS expander it is using.

Hmm, I don't see any problem with my NMosh. It would be a good idea try to capture expanded code and feed it on R5RS mode of Larceny.

[mnieper]

NB: The work-in-progress branch containing the CPS-transformation is now https://gitlab.com/nieper/rapid-scheme/tree/middle-end.

Currently, it also includes a pass that eliminates mutable variables. Long-running tests in this branch have been commented out, and Chibi is used as the default host scheme due to the bug in Larceny.

[okuoku]

I have tried https://gitlab.com/nieper/rapid-scheme/commit/e1f5e709c437fbe6f75f08fa07d551faf0bf327f but chibi-scheme did not complete bootstrap(expand rapid-compiler with rapid-compiler) within a hour... so i couldn't progress to try it with Gambit backend.

[mnieper]

After I have implemented the closure conversion pass, I hope Larceny will be able to run rapid-compiler again.

(As I like to spend my free time on improving of Rapid Scheme, I haven't taken a closer look at Larceny's bug yet. Unfortunately, there haven't been any replies on Larceny's issue list recently either.)