Compiling Clojure to Javascript, pt. 2 -- Why No Eval? | Hacker News Reader

Compiling Clojure to Javascript, pt. 2 -- Why No Eval?

blog.fogus.me

57 pointsJoelMcCracken39 comments

I have much respect for Mr. Fogus, but statements like this make it difficult to take this post seriously:

    ClojureScript is designed to solve the types of big
    problems that are simply too difficult to fathom, much
    less achieve, using raw JavaScript or any number of
    JavaScript frameworks.

Please. ClojureScript may be a beautiful language, but it's not going to solve your problems-so-large-they're-difficult-to-fathom by magic. Better yet, I'd love to hear a real-world example of such a problem that JavaScript is incapable of addressing properly.

Most of my work in Clojure these days involves implementing logic programming and state-of-art predicate dispatch. Both have numerous practical real world use cases (I want them right now) and both would be near impossible to implement with acceptable syntax / performance in plain JavaScript.

Even more importantly this functionality can be provided to end users as libraries not as an alternate version of ClojureScript. For example, while I have a deep respect for CoffeeScript, these types of innovations are "ghettoized" in CoffeeScript because they require users to fork the compiler.

Great -- so if logic programming and predicate dispatch allow you to tackle problems that would otherwise be intractable in JS... Do you have an example of such a problem that you've used logic programming in Clojure to tackle? Perhaps a link to your code?

I'd tend to give Turing-completeness a bit more credit where it's due, especially for flexible dynamic languages.

We've all written code like this:

   class Foo
     method bar(x)
        switch x
          case even?
          case odd?

This is closed. What if I want to add a new case without modifying this class? I could subclass but then I have to know a lot about how Foo works. Perhaps bars has assumptions about whether it needs to run before or after I run my subclassed version, and on and on. This kind of nastiness pervades too much code.

   method bar Foo even?(x)
   method bar Foo odd?(x)
   ...

As far as logic programming - I think the paradigm is so little known that people fail to see how useful it is. Yet many non-trivial programs use ... relational databases!

How would you even begin to express the following idea in JavaScript?

http://stackoverflow.com/questions/6713424/how-do-i-express-...

Note that the idea is actually quite simple and useful!

Another example is to produce all words that form a specific telephone number:

https://gist.github.com/1107653

Of particular interest is the encode function, the relevant bit:

  (run* [q]
      (exist [x y xo yo]
        (appendo x y s)           ;; infer all possible lists that could concat
                                  ;; to form s 
        (wordo x xo) (wordo y yo) ;; convert to words
        (project [xo yo]
          (== q (apply str xo yo)))) ;; create the combined string

Note I don't have to mention indices, for loops, list comprehensions or any other iterative machinery.

All the other solutions I saw had a lot of boilerplate to express this simple idea of inferring the lists that could be concatenated to form s.

    I'd tend to give Turing-completeness a 
    bit more credit where it's due

Turing completeness is a fun topic for conversation, but it doesn't stand up to practical application. That is, every language has a point of diminishing returns regarding expressivity vs. possibility. JavaScript falls somewhere on the spectrum with things like Underscore.js and Coffeescript providing increasingly more bang for the buck. If you were truly such an adherent to the Turing completeness trap then I would be a sad panda without the clear expressivity gains that Underscore and Coffeescript provide.

I trust that you do understand the concept of compilation right? It'd be terribly difficult and tedious to implement JavaScript, for instance, in x86 assembly (but possible!), much like it would be to implement the things that David's logic programming and predicate dispatch in JavaScript directly. Having a language which supports syntactic abstraction allows you to hide away lots of the complexities and let the compiler generate them for you. It's no different than using C instead of x86, or Scheme to C to x86, or whatever other path to x86 you can think of.

I am pretty sure he understands compilation.

A large advantage of lisp like languages is the data-as-code paradigm. To give up eval is to give up this.

It is definitely impossible to efficiently compile code with evals for all possible programs, but lots of code using the data-as-code paradigm generates data that is completely independent of input sources (macro like). This could be computed at compile time and thus efficiently compiled. A similar technique has been used for making Haskell run faster, called super compilation, and it shouldn't be too hard to implement in any functional language.

For evals that can't be compiled, well, it would be nice to still be able to do the dynamic inefficient eval, without botching the efficiency of the entire program. Do the normal dead code analysis, the eval might not work right, so provide a warning. The programmer can always do things to ensure any code they need isn't dead code eliminated by using it elsewhere. Yeah this is messy, but it leaves the choice up to the programmer and has no less power.

> A large advantage of lisp like languages is the data-as-code paradigm. To give up eval is to give up this.

Code as data is about (among other things) programs writing programs, the majority of which (compilers and macros) don't need runtime eval, i.e. the program that writes the program isn't the program that's running it.

Neither I, nor anyone I know, needs runtime eval of ClojureScript code in the browser. As the post states, it's certainly not needed for REPL interaction with a browser, something we intend to support. Why should we spend time writing something with no demonstrated need, other than to satisfy peoples' abstract notions of what constitutes a Lisp?

Whole program optimization: "Optimizer, here is my entire program, do whatever you can in pursuit of size and speed: renaming, moving and eliminating as you see fit."

Runtime eval: "Oh, wait, here's more program!"

You can't do the former well and support the latter. If you think having the choice is important, write the code. Here's some of what's required:

    A ClojureScript port of the compiler (when multimethods are finished, not too bad)
    Syntax quote
    Runtime representation of namespaces, vars etc

What you'll end up with is something that generates huge, slow JavaScript programs. Make sure to emphasize to your users "But it has eval, and is written in a real Lisp!".

Seriously, I'm sure someone somewhere might actually require this, but they'll have to satisfy their own needs.

Honestly, an in-browser REPL isn't compelling to me. What's compelling is an on the fly compiler / evaluator so that I can run Clojure code via node directly (or some other JS via the CLI) without starting up the JVM.

"As the post states, it's certainly not needed for REPL interaction with a browser"

Ok, it is not needed per se, but how can it be done without also writing your own parser and evalulator? I didn't see mention of the how in the article.

Also it's not

Runtime eval: "Oh, wait, here's more program!"

It's: "Oh, you forgot this part of the program, that I already gave you an exact description of".

I'm not advocating any sort of complicated change, just evaluating simple independent expressions that generate the input to evals. I hypothosize that in most cases this is possible. Maybe eval is more often used in ways that does depend on input (REPL is such a case).

I'm not sure exactly how this would be implemented, but the repl action would be to send your browser clojurescript to a server, which then compiles it, which then replies to you, which you then append to the dom in a script() (or, eval it).

This seems tricky, though, because it seems as though you'd need a to evaluate it within the context of the previously compiled environment, and ideally you would want to return /only/ the newly required code + libs. You wouldnt want to return code that re-initializes the dom, for example.

https://github.com/ibdknox/brepl has that repl implementation.

Simple Lisp READ and EVAL are very small programs. Supporting all of Clojure would be a bigger project, but enough for a useful REPL is a quick undergraduate project. Unless for some odd reason ClojureScript doesn't have APPLY.

Supercompilation is the precisely the tool that should not be used for compiling a dynamic language--it relies heavily on static analysis that are simply unfeasible in a dynamic language. eg: anything that touches a dynamically bindable var cannot be specialized--this dynamicity will essentially infect the rest of the functions in the call graph. This is especially true when you're staging compilation via eval. Supercompilation is very slow and memory intensive, and it would be insane to track variable specialization information throughout runtime.

Static analysis is already being done, since it is being compiled. Supercompilation taken to the extreme is very slow, but don't take it to the extreme, doing just enough to evaluate the expressions which are passed into eval would be fine (and these are often simple, macro like substitutions).

I'm not sure if we share the same notion of supercompilation. The whole point of supercompilation is to speculatively evaluate terms to supply branch-level constraints that propagate through the call graph, enabling program transformations such as inlining, dead code elimination, partial evaluation and deforestation. Whole-program transformations such as these are done during compilation (i.e. in the dev environment and not in production.) How would you retro-actively undo an existing transformed piece of code when a new form is observed by eval? How would you maintain a list of already-applied transformations to allow new code to be specialized? Supercompilation is not an incremental procedure.

My notion of supercompilation is just the evaluating of expressions at compile time that do not depend on things at run time.

A trivial case that most compilers do is converting print 1+1 to print 2. Since 1+1 does not depend on anything that could happen at run time and does not produce any other side effects. (You need to analyze that + hasn't been overloaded to have side effects/etc.).

The idea is that many of the expressions being passed into eval could be calculated in entirety at compile time, so there is no need to have eval in the compiled result at all. Just evaluate at compile time, remove the eval and the quotes.

I am not talking about trying to optimize eval, if you have a variable string going in, you can't possibly do that. I guess I shouldn't have used the term supercompiling, it may mean something more powerful than in the cases I'd seen it and I was probably trying too hard to use a buzzword...

The term that describes what you are referring to is 'partial evaluation'

The code-as-data paradigm in Lisp means that you can write your own eval. Eval was an important historical discovery, because of the fact that it could be written in Lisp itself. In fact, a minimal eval is rather easy: Recurse down nested linked lists, switching on the first element to handle special forms, and recursively evaluating functions and arguments.

Eval is basically a DSL, which happens to be the same as the host language. Part of the awesomeness of Lisp is that you can write your own DSLs. Sometimes that involves macros, sometimes that involves a home-brew eval function. But either way, the full-blown eval has very few use cases.

I'm not sure that this was clear, but the reason this is important is for an in-browser REPL.

Would it be possible to turn down the GCC compilation levels, in the "I want an REPL" use case?

Seems like a great idea. This way, developers can decide if they need eval and make the tradeoff. Note that eval can also be use for metaprogramming, and that not having the full code of clojure also affects runtime reflection.

Which is more to the spirit of Clojure and LISPs in general: developers being able at any momemnt to change the language as if he was the language designer.

Or, as said on Five Questions about Language Design[1]: Give the Programmer as Much Control as Possible

[1] http://www.paulgraham.com/langdes.html

Thanks for this. I forgot about this essay.

I had to go and look up Eval and Evil again: http://stackoverflow.com/questions/197769/when-is-javascript...

Clojure supports namespaces and namespace-public/namespace-private functions.

It's relatively easy to stuff every namespace-public function into a hash of its full name -> mangled name, thus both making resolving trivial and preventing supercompilation from stripping functions you might need.

This would prevent supercompilation from stripping any functions, because you never know what a future eval would need.

This is bad because, without supercompilation, ClojureScript and its dependencies are quite large. Would you rather your compiled .js file be 500kb or 5kb? That's the difference we're talking about, here.

Sure, ClojureScript might not be a "full lisp" without eval, but pragmatically, having tiny .js files is a much bigger win.

This level of eval that we're discussing is only really important for developers. Give your super users a bookmarklet which downloads the huge lib, and pops a repl up on the page. Everyone else gets to use the library as usual.

Put the standard lib on a public CDN, and this would be okay.

And I have no doubt that's how it would be done, except that it turns out eval isn't actually necessary for a browser interactive REPL, which is pretty much all that developers need.

Problem is that the js compilation happens on the server, then. Not all who may desire an interactive REPL are necessarily trusted.

You can always use applet to compile on the client, you don't have to compile on the server. It would be easy to create reply like this.

Didn't even think of that. Good point.

You've described exactly why eval is antithetical to dead code elimination: you must defensively include absolutely every public function in every referenced library, because you do not know beforehand which functions an arbitrary evalled form will call.

Well, we can drop all namespaces other than those used or explicitly specified. It's all solveable.

His argument is a total straw man, he wants us to tear it down. He also begs the question that eval is for a repl.

So the ClojureScript folks decided to give up flexibility for speed? A Lisp w/o eval is not a Lisp. Strikes me as a motherly premature (de)optimization.

I'm not a Clojure user, but I am a bit confused about why you can't have EVAL, and also a COMPILE function, which does the appropriate dead-code elimination.

That is, in Common Lisp, the REPL functions aren't usually compiled, but you can call a COMPILE function to trigger them into bytecode.

I don't see the difference for your problem. I would like to be corrected. :-)

It seems that it should be possible to 'force' certain libraries into the compiled js, and then do a 'dumb' non-optimized eval. Yes, you get a bigger js file than if you just stuck with dead code optimization, but having access to the full library at runtime is the entire point.

You can totally just add a flag called :eliminate-eval or :enable-eval and this is a non-issue.

I'm happy with their choices regarding the allocation of their time. I'd rather see more maturity and more core libs being made available to ClojureScript than eval/browser-repl being there immediately.

You can easily write eval as a regular function, right? Except it needs magical access to the global environment. (Please correct me if I'm wrong; I haven't used Clojure, just checked out http://clojure.org/evaluation.)

So I'd blame the definition of Clojure's eval function more than the implementation goals here -- if users had to write (eval foo (the-global-environment)) then you could leave the-global-environment out and still supply a useful eval without any problem in compiling programs.

I've thought about this a bit, and I am not sure whether I disagree. I think I do.

"But honestly, if ClojureScript programs are composed of data forms directly manipulable by the language itself then why not just provide eval anyway? The answer can be found, as many answers in life, in the tradeoffs."

This seems to beat around the bush a lot so here's the problem as I see it:

When the code hits the browser, ClojureScript programs are not composed of Data Structures.

They are composed of Java script, which acts as an assembly code. In a normal lisp, you would have the compiler right along side the generated assembly, so there would be no big deal... you want to eval something, just compile it and link it in to the run-time.

In this case, the compiler is on the server, the code is in the browser... to provide an 'eval', you would have to send an RPC from the server to the browser...

It is disingenuous to say that you cannot support an optimizing compiler and maintain the presence of eval in the language. This is simply not true.

What you cannot do is:

1.) Separate the compiler from the runtime.

2.) Aggressively ELIMINATE code that is not being used.

"You cannot effectively leverage these libraries without an optimizing compiler utilizing dead-code elimination. You cannot have the optimizing compiler if you wish to support eval. Q.E.D."

Note that it is 'the optimizing compiler' not 'an optimizing compiler'. It would be possible to have an optimizing compiler without dead code elimination, or even the same optimizing compiler with dead code elimination turned off (no idea of that is possible).

I think that claim number 1 is the questionable one. It seems like it would be relatively easy to decide the level of dead code elimination by indicating whether eval is available to the language. It may just mean you have to declare what functions/packages are to be made available to eval (which from a security standpoint makes a lot of sense; actually).

--- Thinking about it, A possible repl implementation would actually be fairly simple:

1.) Create a hashtable

2.) Fill hash-table with desirable functions to execute

3.) Write an interpreter that recursively applies the head symbol of a list to the tail of a list (by looking up the symbol in the hash table). (Edit: There may be another wrinkle, like looking up variable symbols).This is basically what eval does.

4.) Create a loop that parses a lisp list into a javascript list, and applies the interpreter.

The hole here is that there is no way to define 'new' functions. This may be possible by having a function returning a function which calls our interpreter (and adding that to the hash table as a new function). The question I have about this is being able to use arguments.. but even that may be possible.

In fact, the above seems to allow for dead code elimination, as you have declared exactly which functions you want accessible to the user.

edit: Sorry if I offended, but what is wrong with my post?

Reply on news.ycombinator.com