4 ms·
Arc Ported to JavaScript
- deleted 19y ago[deleted]
- DaniFong 19y agoThat is quite something.
- cstejerean 19y agoAlthough unrelated to my challenge (http://blog.offbytwo.com/2008/02/05/a-different-kind-of-arc-challenge-a-quest-for-a-true-100-year-language/ http://blog.offbytwo.com/2008/02/05/a-different-kind-of-arc-...) this seems to be the first implementation of Arc in a language other than Scheme. I'm curious if others will follow.
- nostrademons 19y agoI thought about that while I was writing it (I started before your challenge came out). Here's the results for ArcLite: > wc [^j]*.js 66 147 1359 buffer.js 369 1114 10672 eval.js 149 488 4522 primitives.js 188 509 4989 reader.js 356 1145 11869 types.js 136 370 3260 utils.js 1264 3773 36671 total > wc [^d]*.scm 1093 4404 36047 ac.scm 16 30 242 as.scm 48 152 1252 brackets.scm 1157 4586 37541 total So ArcLite is about 100 lines of code more. OTOH, if you take out the reader (which is supplied by Scheme but I had to write myself for ArcLite) it's -254 lines for ArcLite and -48 lines for Arc0. Which means the JavaScript version is actually smaller, at least in line count. (There's also the matter of the missing I/O primitives, but most of them just delegate to Scheme in Arc0 as well.) I have no idea how it compares in code-tree count. Probably larger, as my JavaScript coding style is fairly dense. One could argue that that's the point of syntax though; it makes common operations take up very little space on the page.
- staticshock 19y agoan important limitation of javascript means this will never quite be a complete implementation: Continuations are not implemented. I had started on a CPS-based interpreter, but then realized that JavaScript lacks tail-call optimization and has a recursion limit of 1000 calls, which'll make any CPS-transformation blow the stack. looks like a good piece of code otherwise, though.
- tlrobinson 19y agoThis guy implemented a continuation-based syntax highlighter in JavaScript: http://marijn.haverbeke.nl/codemirror/story.html http://marijn.haverbeke.nl/codemirror/story.html I'm not sure how relevant it is to implementing Arc, but never say never. JavaScript is Turing complete, after all...
- nostrademons 19y agoThat approach could work. He's storing the current continuation as a global variable, which I never thought of, because typically you want your interpreters to be self-contained. (I was also working off Guy Steele's toy CPS interpreter, which passes cont in and then ends each function with a tailcall to another function or the invocation of the continuation.) But I can't see any real reason why the global won't work; it'll get stored in a data structure when the continuation is captured, and since stack frames are normal JavaScript objects in ArcLite, the garbage collector will hold on to them. It'll mean that any loop that may call back into the interpreter has to be rewritten as a tail-recursive function though, with the tail call being saved into the global continuation variable. Could be quite a bit of overhead.
- tlrobinson 19y agoI believe you can use the "with" operator in JavaScript to use any object as the global object (normally "window" in the browser). I'm not sure how useful that could be, but it might help make it self contained.
- nostrademons 19y ago"with" is dangerous, because it makes it impossible to tell lexically whether you're assigning to an object or to a global variable. If you mistype a variable or pass an object of the wrong type in to "with", you can find yourself with very difficult-to-track-down bugs. In practice I'd only use it with a bunch of assertions, which could bloat the code significantly. Chris Double suggested another alternative over on Proggit: tailcall to window.setTimeout with a delay of 0. This is effectively a trampoline; the continuation gets pushed onto a timer, the eval function returns, then JavaScript picks up again where it should. As a nice side effect, it gives the browser's event loop a chance to run, which eliminates any chance of locking up the machine. Pretty elegant solution, though I'm guessing there's a significant performance penalty.
- tac-tics 19y agoA scheme isn't a scheme without continuations. It's a shame they're such a pain in the ass to implement in platforms w/o gotos or TCO.
- whacked_new 19y agonostrademons you are the man.
- nostrademons 19y agoThanks. :-)
- anaphoric 19y agoCool, you deserve many up votes for this! I just played around with it quickly, pasted in the recursive definition of factorial: (def fact (x) (if (< x 1) 1 (* x (fact (- x 1))))) It was fairly quick, but the results came back as floating point numbers. It broke on (fact 100). Under arc-over-scheme it did better. CLISP performed better than both, but the default limit in the call depth was easily exceeded (E.g. it busted on (fact 8000)). I don't recall exactly, but for around fact 5000 CLISP seemed about twice as fast as arc-over-scheme. These are very rough estimates, but perhaps give people an intuition about performance. Now what I am really waiting for is the arc-over-CLISP. I am too busy with other things to dare an attempt...
- nostrademons 19y agoI tried factorial as one of my test cases. Up through factorial 10 it was still coming back as integers. You may have triggered some overflow condition. The interpreter uses the native JavaScript + operation, then checks whether result == Math.round(result) to see whether it should wrap it in an int or a num. I'm truly amazed you got it to work up to (fact 100), and that it came back in a reasonable amount of time. Firefox has a recursion limit depth of 1000, which means that the interpreter overhead is only about a factor of 10. I was expecting much more...
- anaphoric 19y agoI think it worked for 50, but then it busted on 100. I only tried a couple of calls.
- fkrueger 19y agoQuite well done! I'm very impressed.
- apgwoz 19y agoWhile I didn't think it would be JavaScript, I think my prediction of "how long before there's another implementation out there" of a "few days" was only a little bit off.
- nostrademons 19y agoI was shooting for a weekend but didn't quite make it. ;-)
- albertcardona 19y agoSuper cool, thanks a lot! Now if only we could push return to enter instead of having to use the mouse ...
- byrneseyeview 19y agoTab-return?
- nostrademons 19y agoYeah, that's what I do. I couldn't figure out how to get accesskeys to take "return" as the key. If anyone knows a better solution, I can change it.
- tlrobinson 19y agodocument.getElementById("input").addEventListener("keypress", function(e) { e = e || window.event; if (e.keyCode == 13) { $('#eval').click(); e.target.value = ""; }}, false); ...or the equivalent in jQuery. Not IE compatible (no, I don't care) In the meantime, here's a bookmarklet you can use to "patch" it: javascript:(function(){document.getElementById("input").addEventListener("keypress", function(e) { e = e || window.event; if (e.keyCode == 13) { $('#eval').click(); e.target.value = ""; }}, false);})();