A programming language in 450 lines of JavaScript

by breuleux • 12 years ago

316 70 12 years ago

Would love to see a little behind the scenes for this, maybe a write up / blog post. Pretty neat little experiment.

breuleux6• 12 years ago

I 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• 12 years ago

I 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!

mishoo• 12 years ago

I wrote a tutorial some time back — http://lisperator.net/pltut/ — also targeted at JS. It walks you through parsing, evaluating, continuations and CPS compiling.

Theyeard2• 12 years ago

Parsing, evaluating, continuations and CPS... it seems similar to this language: https://curiosity-driven.org/continuations#interpreter but the syntax is clearly different. Also, that interpreter is implemented in ~320 lines of JS.

coppolaemilio• 12 years ago

Loving it! It's so nice to see this kind of things around :)

ravi_thakare• 12 years ago

You can also check out http://javascript.crockford.com/tdop/tdop.html

The article is also in the book Beautiful Code (O'Reilly)

breuleux6• 12 years ago

Indeed, 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).

Yadi• 12 years ago

Ah this is pretty baddass, kudos!

primitivesuave• 12 years ago

This 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• 12 years ago

Yup! 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/

whitten• 12 years ago

This 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.

breuleux6• 12 years ago

Postfix 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_bullington3• 12 years ago

I'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?

elwell• 12 years ago

Or you could use replace() with a fat regex, and then eval(). But this is awesome.

Zelphyr• 12 years ago

But then you'd have three problems...

vidarh3• 12 years ago

That's one of the most terrifying sentences I've read.

klibertp3• 12 years ago

What? 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.

marai2• 12 years ago

That's a nice example of some elegant and readable code.

EpicDavi• 12 years ago

Just 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• 12 years ago

I thought recursive fibonacci solutions like this had O(fib n) run time.

Mithrandir2• 12 years ago

You're both correct: http://stackoverflow.com/questions/4623058/ofib-n-complexity...

EDIT: Tied with JadeNB (https://news.ycombinator.com/item?id=8555051).

JadeNB3• 12 years ago

`O(fib_n)` is `O(phi^n)`, where phi = (1 + sqrt(5))/2 < 2.

EDIT: Tied with Mithrandir (https://news.ycombinator.com/item?id=8555049).

MrRage• 12 years ago

I always thought the fastest was the closed form formula: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

Unless looping and counting is that much faster than doing some floating point math?

aarongolliver• 12 years ago

Only "faster" because you precompute digits of the golden ratio, and will quickly become inaccurate unless you compute more of them

Bognar• 12 years ago

The closed form will become inaccurate at some point. However, there is a way to calculate Fibonacci accurately with O(log(n)) time (ignoring the time to multiply - otherwise O(M(n) log(n)) where M(n) is the time to multiply two numbers of n digits).

taternuts• 12 years ago

Thanks so much for this - really looking forward to going through it in the next couple days

treehau5• 12 years ago

Yes 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• 12 years ago

Wow, nice project! I would love to see both the lexical and syntactic analyzers broken down a little more.

moron4hire• 12 years ago

Damn, 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...

EDIT: though I did end up writing a Pong game in it: https://github.com/capnmidnight/betty-boop/blob/master/pong....

lectrick• 12 years ago

The 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• 12 years ago

can you create your own programming language with python?

aye• 12 years ago

Sure! You could use a parser generator like Yapps [0] to write a parser for your own programming language.

[0] http://mbreen.com/yapps2.html

pjmlp4• 12 years ago

Any 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.

sklogic3• 12 years ago

You don't even need a Turing-complete language for writing compilers, see CompCert for example.

kensai• 12 years ago

Since some 150 lines are comments or blank, it's more like a 300 lines programming language. Even more impressive!

pjmlp4• 12 years ago

This is great! Specially the AST viewer.

Any inspiration from the Tiger book for the language?

CmonDev• 12 years ago

Actually both are scripting languages. Still impressive though.

owlish• 12 years ago

Peter 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

marijn• 12 years ago

Mine's only 157 lines: http://eloquentjavascript.net/11_language.html

Aissen2• 12 years ago

Yours 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).

V-22• 12 years ago

Still very interesting

breuleux6• 12 years ago

The 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.

breuleux6• 12 years ago

That'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• 12 years ago

How about 49 lines?

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• 12 years ago

Dat AST rendering.

V-22• 12 years ago

Let's live it once again 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)"

A programming language in 450 lines of JavaScript

Related Stories