Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proper Tail Optimization doesn't work #2140

Open
amirouche opened this issue Sep 2, 2017 · 7 comments
Open

Proper Tail Optimization doesn't work #2140

amirouche opened this issue Sep 2, 2017 · 7 comments

Comments

@amirouche
Copy link

amirouche commented Sep 2, 2017

GNU Guile has now a working prototype of a compiler backend that generates JavaScript.

It use lots of tail calls. I compiled it with traceur using the following command:

$ traceur --out script.js --script out.prettier.js --proper-tail-calls  --experimental

I run it in chrome using the following html file:

<html>
  <body>
    <script src="https://google.github.io/traceur-compiler/bin/traceur.js"></script>
    <script src="https://google.github.io/traceur-compiler/bin/BrowserSystem.js"></script>
    <script src="/script.js" type="text/javascript"></script>
  </body>
</html>

It fails with a Uncaught RangeError: Maximum call stack size exceeded.

The original scheme program is:

(js-invoke (js-eval "console") "log" "héllo world")

The input JavaScript file can be found here. That input file is correctly intrepreted by nodejs v8.4.0 using the --harmony_tailcalls flag.

@arv
Copy link
Collaborator

arv commented Sep 2, 2017

The option for tail calls is not enabled by default. How did you coming your ES6 code?

@amirouche
Copy link
Author

The option for tail calls is not enabled by default.

I enabled it with --proper-tail-calls flag, it's not enough?

How did you coming your ES6 code?

I don't understand the question.

@arv
Copy link
Collaborator

arv commented Sep 2, 2017

Oops. Typo, should have been "how did you compile your code"

If I remember correctly the tall call implementation in traceur did not cover all cases. I have to look closer at your code.

Note, no one is really maintaining this project at the moment. If you have some time your contribution would be appreciated.

@amirouche
Copy link
Author

Actually the compilation is ok, it's just that I don't have a correct traceur-runtime.js. I had to replace some string with [email protected]/src/. I don't know how to build the "traceur/dist/common" version of the runtime.

Yes hopefully I can help.

I just successfully ran the following program:

"use strict";

function foo(n) {
  if (n===0) {
    return "done"
  } else {
    return foo(n-1)
  }
}

console.log(foo(100000));

I guess I need to find out what is not optmised in the other case.

@amirouche
Copy link
Author

amirouche commented Sep 3, 2017

By the way the code is written using CPS. Someone told me cheney on the MTA should be the way to go. But I don't understand how in the context of JavaScript it makes sens.

@amirouche
Copy link
Author

amirouche commented Jul 25, 2019

Hopefully, it will be helpful to someone on the same quest.

For what it's worth, I managed to translate a subset of Scheme (!) to JavaScript using Continuation-Passing-Style and a trampoline. Here is the Scheme description of the transformation in nanopass framework syntax:

https://github.com/scheme-live/ruse-scheme/blob/5921af59c8586c1e76996e446df76d40601f93a9/rusec.scm#L987-L1101

It works. The thing is that as-is it is very slow, proof: https://www.measurethat.net/Benchmarks/Show/5674/0/ruse-compiler-factorial

The rest of the compiler can be found at https://github.com/scheme-live/ruse-scheme/blob/master/rusec.scm

edit: change link to code to updated version and replace benchmark link with something that is not buggy

@amirouche
Copy link
Author

Ideas on how to optimize the code is 💯 welcome.

Here is another jsperf link because the other is broken: https://jsperf.com/ruse-scheme-factorial-v0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants