8 ms·
A programming language in 450 lines of JavaScript
- drewdahlman 12y agoWould love to see a little behind the scenes for this, maybe a write up / blog post. Pretty neat little experiment.
- breuleux 12y agoI agree I should post one, but it usually takes me a lot of time, and I wasn't sure how much interest there would be. I'll start working on one.
- bramgg 12y agoI started writing my own language in JavaScript last Summer but gave up after only writing the Lexer because I didn't know how to continue. I would LOVE to read this blog post!
- d0m 12y agoNot all parsers need to be complex. If you're up for the challenge, read a bit on top-down parser and try to write it for your language!
- Theyeard 12y agoKaleidoscope - LLVM Tutorial [0] is an excellent resource with code samples in C++ and OCaml. [0] http://llvm.org/docs/tutorial/index.html http://llvm.org/docs/tutorial/index.html
- eric_bullington 12y agoAgreed, it's an excellent resource. One of the best PL tutorials I've ever read. But if you use the OCaml version with a recent version of OCaml, you'll run into a few issues. I sent in a patch with a few simple updates to the path mailing list earlier this year, but last I checked it wasn't merged. Patch is here (it's a text file, despite the "bin" extension): http://permalink.gmane.org/gmane.comp.compilers.llvm.cvs/183464 http://permalink.gmane.org/gmane.comp.compilers.llvm.cvs/183... I also pasted the patch here: http://pastebin.com/YvzB71nJ http://pastebin.com/YvzB71nJ
- pjmlp 12y agoNiklaus Wirth´s book about compiler construction is quite good. It is available at his ETHZ site nowadays, http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
- kyberias 12y agoThere may be better books but this was fairly pragmatic and I learned a lot: http://www.amazon.com/Programming-Language-Processors-Java-Interpreters/dp/0130257869 http://www.amazon.com/Programming-Language-Processors-Java-I...
- mishoo 12y agoI wrote a tutorial some time back — http://lisperator.net/pltut/ http://lisperator.net/pltut/ — also targeted at JS. It walks you through parsing, evaluating, continuations and CPS compiling.
- Theyeard 12y agoParsing, evaluating, continuations and CPS... it seems similar to this language: https://curiosity-driven.org/continuations#interpreter https://curiosity-driven.org/continuations#interpreter but the syntax is clearly different. Also, that interpreter is implemented in ~320 lines of JS.
- coppolaemilio 12y agoLoving it! It's so nice to see this kind of things around :)
- ravi_thakare 12y agoYou can also check out http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html The article is also in the book Beautiful Code (O'Reilly)
- breuleux 12y agoIndeed, that is a very good article. I highly recommend it. TDOP is the combination of recursive descent and Floyd's operator precedence grammars, the latter of which is the technique I used (I find it sufficient for my needs).
- barbudorojo 12y agoTDOP of Vaughan Pratt is also used in maxima (that is the way they use an infix language similar to python as a frontend to Lisp. In maxima you can define easily infix, prefix and postfix operator with a left and right binding force for your grammar. I couldn't find with grep the file I was looking for in the maxima source, but for examen Fateman paper "Syntax Extension as a Tool for Application Programming" is a good reference.
- Yadi 12y agoAh this is pretty baddass, kudos!
- primitivesuave 12y agoThis is awesome! I wish somebody had shown me this when I learned about compilers in CS. The best way I've found in learning about anything theoretical is to write the code for it.
- Jonovono 12y agoYup! I found this course pretty useful when I was studying it. Fun to jump right in alongside the theory and all, I find: http://createyourproglang.com/ http://createyourproglang.com/
- whitten 12y agoThis seems to be a language where there are several kinds of blocks: if-elif-else , a let-in-end, begin-end and curly braces, square brackets, and round parenthesis. There are a few operators, with several levels of precedence, both prefix operators, infix notation, but no sign of post-fix notation like (!) for 3! == 6 and 5! == 120 There also seems to be list data type as well as strings and numbers.
- breuleux 12y agoPostfix operators do work. Try this: let x! = if x == 0 then 1 else x * (x - 1)! end in 5! end Any operator can be prefix, infix or postfix depending on the relative priority with the operators next to them. For instance, in "1 ^ * 2" the engine interprets ^ as postfix because ^ has higher priority (it just gets null as its right hand side). In "1 * ^ 2", ^ is prefix. Unless specified otherwise operators are given maximal priority, which is why the factorial example works. The engine just has specific provisions to allow operators in "prefix position" to have different priority than in infix position, otherwise prefix minus would fail to work as expected.
- eric_bullington 12y agoI'm trying to figure out how much work it would take to add on OCaml style pattern matching to this language, particularly list matching. Would you mind pointing me in the right direction? Like a very brief(ie., a sentence or two), high-level overview of how you might approach the task?
- breuleux 12y agoNot a lot of work. I have implemented pattern matching before, so I just went ahead and did it: http://jsfiddle.net/f1ycatas/2/ http://jsfiddle.net/f1ycatas/2/ See line 266 for the syntax definition (the precedence entry for "->" on line 278 is also relevant) and line 409 for the implementation of pattern matching. I use a few auxiliary functions here: extractArgs just checks that an AST node has a certain form and extracts parts of it, and listify is a kind of normalization function that will give you a list of expressions or statements. I think the code is relatively straightforward: we have a list of "pattern -> body" statements. For each entry we create a fresh environment for the variables declared by the pattern and we try to match the pattern with the value. For matching, if a pattern is a variable name we set that variable in the environment, if it's a number or string we check for equality, and if it's a list of subpatterns we check that we have a list of the correct length and we check the subpatterns recursively. If there's a match, we execute the corresponding body. If that interests you, I wrote a compile-to-JS language called Earl Grey (http://breuleux.github.io/earl-grey/repl/ http://breuleux.github.io/earl-grey/repl/) using a similar parser and it has rather sophisticated pattern matching. The implementation is quite a lot more than 450 lines, though :)
- elwell 12y agoOr you could use replace() with a fat regex, and then eval(). But this is awesome.
- Zelphyr 12y agoBut then you'd have three problems...
- vidarh 12y agoThat's one of the most terrifying sentences I've read.
- klibertp 12y agoWhat? That's actually the way all the compilers/transpilers work. You just take some string and transform it into some other string that happens to be runnable.
- kyllo 12y agoSo Coffeescript for example is just a fat regex plus a call to eval?
- vidarh 12y agoNo, that is actually not the way most compilers/transpilers work. Using a regex for parsing a whole language is something I've never seen done, in 25+ years of writing and reading compilers as a hobby. Using a regex for tokenization or parsing simple sub-expressions is sometimes done, but that too is fairly rare outside of toy parsers. Doing the translation step through replace on the basis of a regex is also not going to work for anything but the simplest translations, not least because the resulting monstrous regex would be nearly impossible for a human to reason about. But the thing that terrified me about it was the thought of someone lifting something lie that out of the browser sandbox and running it server side: The combination of a near undecipherable regex for parsing/translation coupled with eval() to run the result would be a near certain security nightmare.
- marai2 12y agoThat's a nice example of some elegant and readable code.
- EpicDavi 12y agoJust a semi-unrelated comment: The Fibonacci code example classically has a horrid runtime. Will like likely crash your browser when supplied a number higher than the low thirties. IIRC it has a O(2^n) runtime and can be improved either by a bottom up approach (non-recursive) or a "dynamic-programming" (OOohhhh, buzzwords) method where you use memoization (memo table) to store (or memoize) results.
- dopamean 12y agoI thought recursive fibonacci solutions like this had O(fib n) run time.
- Mithrandir 12y agoYou're both correct: http://stackoverflow.com/questions/4623058/ofib-n-complexity-algorithms/4623285#4623285 http://stackoverflow.com/questions/4623058/ofib-n-complexity... EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051 https://news.ycombinator.com/item?id=8555051).
- lqdc13 12y agobut isn't O(phi^n) < O(2^n)? Exponential regardless.
- Mithrandir 12y agoSure, O(2^n) is an upper bound here. O(phi^n) is a tighter bound.
- baddox 12y agoYou're right, although the "<" symbol isn't technically correct notation. I think O(phi^n) ⊂ O(2^n) or O(phi^n) ⊊ O(2^n) would be more correct to indicate that the left is a proper subset of the right, given that big O notation refers to sets of functions.
- 12y ago
- taternuts 12y agoThanks so much for this - really looking forward to going through it in the next couple days
- treehau5 12y agoYes me too! I am curious to know the motivation behind it as well. I have been putting on the back burner going through the "Dragon Book" and I figured a project like this would be motivation to finally get around to it.
- dabockster 12y agoWow, nice project! I would love to see both the lexical and syntactic analyzers broken down a little more.
- moron4hire 12y agoDamn, beat me by 6 lines, though I also cheated and translated to JS to interpret the code: https://github.com/capnmidnight/betty-boop/blob/master/loosp.js https://github.com/capnmidnight/betty-boop/blob/master/loosp... EDIT: though I did end up writing a Pong game in it: https://github.com/capnmidnight/betty-boop/blob/master/pong.html https://github.com/capnmidnight/betty-boop/blob/master/pong....
- lectrick 12y agoThe best thing about this is being able to play with the entire mechanism right on jsfiddle. Thanks for this work and want to read the writeup!
- notastartup 12y agocan you create your own programming language with python?
- aye 12y agoSure! You could use a parser generator like Yapps [0] to write a parser for your own programming language. [0]: http://mbreen.com/yapps2.html http://mbreen.com/yapps2.html
- pjmlp 12y agoAny Turing complete language can be used for writing compilers/interpreters, it is just harder in some than other. Python is actually pretty neat for doing it and you even have tools like PyPy (with RPython) to write a JIT for the language if you wish.
- sklogic 12y agoYou don't even need a Turing-complete language for writing compilers, see CompCert for example.
- pjmlp 12y agoI need to dive into it. Do you mean it because of the formal logic being used?
- sklogic 12y agoThis is because compilation can be represented as a finite sequence of applying simple rewrite rules. You don't need a true Turing-complete language to do so, because you don't have any indeterminate loops in such process. Any simple total language (like Coq) is more than enough.
- kensai 12y agoSince some 150 lines are comments or blank, it's more like a 300 lines programming language. Even more impressive!
- pjmlp 12y agoThis is great! Specially the AST viewer. Any inspiration from the Tiger book for the language?
- CmonDev 12y agoActually both are scripting languages. Still impressive though.
- owlish 12y agoPeter Norvig's lis.py[1] is an oldie but a goodie. It really shows you the beauty and simplicity of Scheme/Lisp interpreters. [1]: http://norvig.com/lispy.html http://norvig.com/lispy.html
- marijn 12y agoMine's only 157 lines: http://eloquentjavascript.net/11_language.html http://eloquentjavascript.net/11_language.html
- Aissen 12y agoYours is a lisp-like, so much easier to parse; and it doesn't have the nice in-dom ast viewer nor nearly the same number of comments (I compared with http://eloquentjavascript.net/code/chapter/11_language.js http://eloquentjavascript.net/code/chapter/11_language.js).
- V-2 12y agoStill very interesting
- Aissen 12y agoIt's even more interesting because it's part of book. Just setting the expectations, because it's not an apple-to-apple comparison.
- breuleux 12y agoThe AST viewer is not included in the 450 lines, although the comments are. Most of the difference is due to the more sophisticated parser and some extra features like arrays.
- breuleux 12y agoThat's pretty cool :) To be fair, though, the 450 lines include about 120 lines of comments, a configurable full operator precedence parser, syntax for array creation and indexing, range and looping operators, short-circuit logical operators... Most minimal language implementations skimp on syntax because it is irrelevant to a language's expressive power. The point of this exercise, though, was to make one that didn't.
- seivadmas 12y agoHow about 49 lines? https://github.com/samphilipd/the-little-schemer/blob/master/scheme.js https://github.com/samphilipd/the-little-schemer/blob/master... I wrote an implementation of Scheme in Javascript to use as I work through the excellent book 'The Little Schemer'. Turns out you can implement a basic version of the language in just 7 functions. It's Turing complete and you can use the base methods to build any function you need.
- worldsayshi 12y agoDat AST rendering.
- V-2 12y agoLet's live it once again https://news.ycombinator.com/item?id=7745561 https://news.ycombinator.com/item?id=7745561 ;) "Have you heard about our Lord and Saviour JavaScript?" "How to touch yourself at night without JavaScript knowing it." "Breaking news! POP3 and IMAP written in Javascript!" "How I ported the control software of a nuclear reactor to reactive Javascript" "Linux kernel ported to JavaScript running in the browser. See how we did it." "How I made a filesystem in javascript." "How I got my girlfriend pregnant using JavaScript." "How to avoid getting HIV using JavaScript." "The Linux kernel doesn't have enough javascript." "I recommended my boss to rewrite the local powergrid infrastructure to javascript and how I lost my job." "I decided to re-implement Javascript in Javascript. It failed. Here is my story." "ABC in # lines of JavaScript (400 comments, 1000 points)"