Making a Mini-Lisp: Introduction to Transpilers in JavaScript

https://angularclass.com/making-a-mini-lisp-introduction-to-transpilers/

by gdi2290 • 11 years ago

78 23 11 years ago

ane• 11 years ago

Is the ad hoc distinction between compilation and "transpilation" really worth it? Can't we just call them compilers? I get that the difference between compilation and transpilation is that the target language of the latter is not a lower lever language, which would be in the case of C and Assembler, but that it targets a language that's more or less of a similar level. Is this really worthy of another term? I'm not sure.

seiji• 11 years ago

Maybe the transpiler is just a spackled polyfill enabling splats because dunders are unreliable?

noelwelsh• 11 years ago

I'm with you. A transpiler is exactly a compiler.

reikonomusha2• 11 years ago

While as you point out there's not necessarily an academic difference, the notion that your target language will itself require a compiler and/or runtime is useful to know up front. Transpilers also usually attempt close to 1-to-1 translation. Functions become functions, constants become constants, etc.

As someone who has written many compilers before, I'd almost feel it would be a slight disservice to call a transpiler a compiler, mostly because their architecture and goals are often different.

hellofunk• 11 years ago

I think the distinction is useful too, as it gives you a better idea of where a language actually sits in a development workflow.

meric2• 11 years ago

I think it's fine to call it a compiler if it compiles a language to another of a lower level of abstraction, which may be true with compiling lisp to javascript, depending on if macros and read macros were implemented. There's just no way a programmer can manipulate the reader in javascript.

emptybits• 11 years ago

I don't see the need for a word beyond "translator" for what you describe. It's a well known word and used correctly, I think, if I say "this program translates Lisp into Javascript."

Scotups• 11 years ago

formatting on code sample was wonky, just fixed them , refresh and enjoy!

tlack• 11 years ago

Great article! Really accessible for a newbie. I'd love to see a comparison between using a manual lexer/parser like the one seen here and using OMeta/JS, which seems like a real time saver for people playing around with languages. https://github.com/alexwarth/ometa-js

PeCaN2• 11 years ago

For playing around with languages I'd actually recommend writing your own lexer and parser. It isn't hard, and writing a recursive descent parser really helps understanding grammars and BNF. Before you have a solid grasp of how context-free grammars work, parser generators aren't much of a time saver IMO.

In my experience getting a BNF grammar right is something of an art which you pick up after having written a few parsers.

wtbob2• 11 years ago

As someone who's been working on figuring out a way to transpile or interpret a powerful dynamic language to Lua, JavaScript, Python and Go, the really tough thing to do is non-local exits. If you can solve that, I think that everything else is easy (well, a Simple Matter of Programming anyway).

It's okay if your target language already supports non-local exits, particularly parameterised ones (although even that can be faked with a well-designed global), but if it doesn't then it's a pain (imagine how you'd do it in Go: every single function call will return an additional value, indicating if a non-local exit is intended).

Alternatively, imagine trying to transpile call/cc to JavaScript…

PeCaN2• 11 years ago

Just transform it to continuation-passing style[1] and call/cc is no problem (neither are non-local exits). Granted your compiled code will be somewhat large and not much like 'regular' code in the language. That can be solved by doing selective CPS transform (IcedCoffeeScript[2] does this), but that gets slightly less straightforward.

Compiling continuations to a dynamic language is actually really easy.

1: https://en.wikipedia.org/wiki/Continuation-passing_style

2: http://maxtaco.github.io/coffee-script/

truncate• 11 years ago

I'm interested to know more about IcdeCoffeeScript approach. Any blogs/articles that you know of?

Typically direct CPS conversion are straightforward, but the performance suffers a lot. I'm looking for languages that are using some hybrid approaches.

wtbob2• 11 years ago

Just transform it to continuation-passing style and call/cc is no problem (neither are non-local exits). Granted your compiled code will be somewhat large

I'm well aware, but CPS code can be _insanely_ large (essentially a function declaration for every line of code in the original source). That's quite painful.

meric2• 11 years ago

Does Javascript's try...catch and error count as non-local exit?

sinamdar• 11 years ago

Shameless Plug here.

Inspired by Peter Norvig's 'How to write a Lisp Interpreter in Python', I created three variants of it along the same lines as the OP. The first is a Simple Lisp Interpreter in Javascript [1]. The second separates Syntactic Analysis from Execution [2]. And the third supports non deterministic computing [3].

[1] https://bitbucket.org/sainamdar/lisp2js

[2] https://bitbucket.org/sainamdar/lisp2js2

[3] https://bitbucket.org/sainamdar/lisp2js2nd

lisper2• 11 years ago

The language being defined here is not a Lisp, it's a (trivial) language that just happens to use (something like) S expressions as the surface syntax. (The reason it's only "something like" S expressions is that it has ad-hoc commas to delimit argument lists.)

The characteristic that defines a Lisp is that code is not a sequence of characters, it's a data structure -- typically a tree of cons cells -- which can be manipulated within the language itself. The language being defined here doesn't have that property.

It is this property that allows you to write macros, which is what makes Lisp cool. Without it you don't have Lisp, you just have a run-of-the-mill programming language with weird syntax.

jhedwards• 11 years ago

You make an interesting and important point, but to be honest the article's intended audience is people who are intimidated by language translation or just have never done it before. The "Minilisp" is not really a language so much as a tool to demonstrate the concepts of tokenizing, parsing and recursion. It is unfortunate if the result is a mischaracterization of real Lisp, but I was trying to cut a balance between being accurate and filling the article with tangential information.

lisper2• 11 years ago

That's a fine goal, but there's more at stake here than mere "accuracy". When you design a language that uses S-expression syntax (sort of) and has "Lisp" in its name, but eliminates the reason for using S-expressions, you're not really laying a foundation for understanding, you're creating a cargo cult (https://en.wikipedia.org/wiki/Cargo_cult, specifically https://en.wikipedia.org/wiki/Cargo_cult#Metaphorical_uses_o...)

junke• 11 years ago

To expand a little on this, the article shows the parsed AST:

   {
     type: 'function',
     value: 'defn',
     children: [ 
       { type: 'function_name', value: 'average' },
       { type: 'arguments', children: [
                             { value: 'x' },
                             { value: 'y'}
                            ]
       },
       { type: 'function', value: '/', children: [...] }
     ]
   }

The parenthesis-based surface syntax is directly translated into the above, which is IMO more verbose and contains no additional information. On the other hand, it is valid Javascript data.

So it looks like it is equivalent to manipulate the above form. Now, suppose you want to define a function which returns a form which performs a function call. We won't use macros, but simply a function that builds an AST. We can't write Javascript directly with this parser, so let's say there are primitive Lispy functions to build equivalent javascript trees:

    (defn my-funcall ()
      (js%hash (js%kv "type" "function")
               (js%kv "value" "my-fn")
               (js%kv "children"
                      (js%vector 
                        (js%hash 
                          (js%kv "value" 3))))))

... whereas, a lisp-based approach would be:

    (defn my-function (list 'my-fun 3))

Making a Mini-Lisp: Introduction to Transpilers in JavaScript

Related Stories