4 ms·

Infinite Loops

65 points by stablemap 9y ago

cdancette 9y ago
Repl.it is a service to edit and run snippets of code in the browser. The code runs on their servers (except JavaScript) and they extended the support for infinite loops (no timeouts)
- amasad 9y ago
  That's a good summary, thanks! So in addition to not timeboxing the user code what's interesting about this is the heuristics we came up with for trapping potential infinite loops in JS.
deleted 9y ago
[deleted]
robinduckett 9y ago
Docker Cloud's container service could learn a thing or two from this
jpolitz 9y ago
Nice! Something like this is super-important for user experience. This is a problem we've thought a lot about with Pyret, and have different concrete solutions. Rather than use heuristics that turn long-running computations into errors, we capture continuations and yield to the browser periodically. This allows long-running computations to eventually complete, while allowing the user to fully interact with buttons and the page while it's happening. This generalizes to nice abstractions for functional event loops and ways to manage asynchronous APIs for novices. The Doppio JVM and the Whalesong compiler for Racket have similar underlying approaches. It's quite a bit of effort to work around this inherent limitation of the browser's evaluation model for web-based IDEs!
- amasad 9y ago
  First of all big fan of Pyret. And I (the author) did something similar in the past and I totally agree it's the way to go. What I did is exploded every JavaScript program on statements, wrapped function calls with thunks, and then converted the program and every function to a generator and inserted a yield statement between every other statement. See https://amasad.me/js-debugger https://amasad.me/js-debugger It worked well enough and was able to build a couple of demos on top of it (last time I checked chrome broke some of my demos so try them on other browsers). However, I think it's quite a hack and that the proper solution would be to build a JS VM. There are still issues to be worked out there like the problem that you can't instrument native code (say an event handler, or built-in functions) and that there are things that are inherently synchronous in the browser that you can't make async (e.g. event bubbling). However, one of Repl.it's goal is to support every language ever existed so building and maintaining our own virtual machines would be quite an undertaking for our 3 person team. What I'm hoping for is that we sometime soon leverage WASM to compile down an existing JS VM.
  - enum 9y ago
    Hi @amasad, In collaboration with @jpolitz, we've been working on way to debug programs written in arbitrary source languages in the browser that you may find interesting. You can find a technology demo here: http://www.stopify.org http://www.stopify.org Stopify uses existing compilers that produce JavaScript (e.g., ScalaJS, BuckleScript, etc.) We've tested with ten languages, five of which are on the website. There are three key pieces to Stopify: (1) first-class continuations for JavaScript (warts included), (2) browser-specific optimizations, and (3) language-specific optimizations (i.e., many compilers emit a sane subset of JavaScript that Stopify can exploit to improve performance). We've conducted a pretty extensive performance evaluation that we can also share. E.g., we've found that PyJs + Stopify can be as fast as Skulpt with suspensions.
    - amasad 9y ago
      This looks awesome! I'm excited to learn more. Is there an abstract I can read? the website/github doesn't say much about how it works.
mizzao 9y ago
The halting problem has been solved!
speps 9y ago
How do we go about requesting more languages? I would love to see D or REBOL on the list :)
maweki 9y ago
Mentioning that this problem is generally undecidable would have been nice, together with an analysis of which heuristics are then used. As I see it, they more or less just time the loops and if it was running too long it's an infinite loop. The author suggests one edge case for this where the loop waits for user input. So for some definition of infinity this might be okay.
- amasad 9y ago
  Time the loops plus an iteration counter. Together they work well. If something is taking long AND is looping a lot then there's a good chance we're running up against an infinite loop. Additionally we setTimeout and reset the counter so that we don't stop infinite generators. Good point re undecidability, it's a knowledge curse mistake.
redmorphium 9y ago
I may be mistaken, but I believe that behind the scenes, it's the token bucket algorithm that does rate control.

65 points by stablemap 9y ago

Repl.it is a service to edit and run snippets of code in the browser. The code runs on their servers (except JavaScript) and they extended the support for infinite loops (no timeouts)

amasad 9y ago
That's a good summary, thanks! So in addition to not timeboxing the user code what's interesting about this is the heuristics we came up with for trapping potential infinite loops in JS.

deleted 9y ago

[deleted]

robinduckett 9y ago

Docker Cloud's container service could learn a thing or two from this

jpolitz 9y ago

Nice! Something like this is super-important for user experience. This is a problem we've thought a lot about with Pyret, and have different concrete solutions. Rather than use heuristics that turn long-running computations into errors, we capture continuations and yield to the browser periodically. This allows long-running computations to eventually complete, while allowing the user to fully interact with buttons and the page while it's happening. This generalizes to nice abstractions for functional event loops and ways to manage asynchronous APIs for novices. The Doppio JVM and the Whalesong compiler for Racket have similar underlying approaches. It's quite a bit of effort to work around this inherent limitation of the browser's evaluation model for web-based IDEs!

amasad 9y ago
First of all big fan of Pyret. And I (the author) did something similar in the past and I totally agree it's the way to go. What I did is exploded every JavaScript program on statements, wrapped function calls with thunks, and then converted the program and every function to a generator and inserted a yield statement between every other statement. See https://amasad.me/js-debugger https://amasad.me/js-debugger It worked well enough and was able to build a couple of demos on top of it (last time I checked chrome broke some of my demos so try them on other browsers). However, I think it's quite a hack and that the proper solution would be to build a JS VM. There are still issues to be worked out there like the problem that you can't instrument native code (say an event handler, or built-in functions) and that there are things that are inherently synchronous in the browser that you can't make async (e.g. event bubbling). However, one of Repl.it's goal is to support every language ever existed so building and maintaining our own virtual machines would be quite an undertaking for our 3 person team. What I'm hoping for is that we sometime soon leverage WASM to compile down an existing JS VM.
- enum 9y ago
  Hi @amasad, In collaboration with @jpolitz, we've been working on way to debug programs written in arbitrary source languages in the browser that you may find interesting. You can find a technology demo here: http://www.stopify.org http://www.stopify.org Stopify uses existing compilers that produce JavaScript (e.g., ScalaJS, BuckleScript, etc.) We've tested with ten languages, five of which are on the website. There are three key pieces to Stopify: (1) first-class continuations for JavaScript (warts included), (2) browser-specific optimizations, and (3) language-specific optimizations (i.e., many compilers emit a sane subset of JavaScript that Stopify can exploit to improve performance). We've conducted a pretty extensive performance evaluation that we can also share. E.g., we've found that PyJs + Stopify can be as fast as Skulpt with suspensions.
  - amasad 9y ago
    This looks awesome! I'm excited to learn more. Is there an abstract I can read? the website/github doesn't say much about how it works.

mizzao 9y ago

The halting problem has been solved!

speps 9y ago

How do we go about requesting more languages? I would love to see D or REBOL on the list :)

maweki 9y ago

Mentioning that this problem is generally undecidable would have been nice, together with an analysis of which heuristics are then used. As I see it, they more or less just time the loops and if it was running too long it's an infinite loop. The author suggests one edge case for this where the loop waits for user input. So for some definition of infinity this might be okay.

amasad 9y ago
Time the loops plus an iteration counter. Together they work well. If something is taking long AND is looping a lot then there's a good chance we're running up against an infinite loop. Additionally we setTimeout and reset the counter so that we don't stop infinite generators. Good point re undecidability, it's a knowledge curse mistake.

redmorphium 9y ago

I may be mistaken, but I believe that behind the scenes, it's the token bucket algorithm that does rate control.