4 ms·

I added some optimizations to my compiler that turns Lisp into JavaScript

112 points by healeycodes 2y ago

User23 2y ago
Good stuff. On a Lisp compiler optimization tangent: It’s still relevant to SBCL and also generally interesting so the CMUCL advanced compiler manual section[1] is good reading. [1] https://cmucl.org/docs/cmu-user/cmu-user.html#Advanced-Compiler-Use-and-Efficiency-Hints https://cmucl.org/docs/cmu-user/cmu-user.html#Advanced-Compi...
tromp 2y ago
Do you check whether constant folding actually results in shorter code? E.g. something like let a="hello "; b=a++a; c=b++b; in c++c probably shouldn't be changed into "hello hello hello hello hello hello hello hello "
- dualogy 2y ago
  A sufficiently smart minifier should rewrite that back into `"hello ".times(8)` =)
- healeycodes 2y ago
  The Lisp variant that the compiler supports at the moment only handles f64 numbers so I don't think this kind of issue is possible. However, this is a very relevant point. If the goal is just shorter code (as opposed to a mix of shorter code and less run-time operations), then you need to check that folding strings (and similar types) actually makes the expression shorter to represent.
- retrac 2y ago
  Depends whether you're optimizing for program size or runtime speed.
- kazinator 2y ago
  If these operations produce mutable strings, the conditions under which that would be allowed are fairly stringent. It's not worth doing; it's better for the Lisp to have constructs that allow the programmer easily stage the evaluation in the desired way. Common Lisp has load-time-value. It's also easy to write a macro called macro-eval which evaluates its argument at macro time, and substitutes the result (as a quoted object).
  - basil-rash 2y ago
    What is the case you imagine where mutable strings would prohibit this?
    - kazinator 2y ago
      Any situation where the program depends on the expression producing a new string each time it is evaluated, rather than returning the same string. The program may be modifying the string, on the assumption that nothing else has access to it, since it is brand new. The program could also be relying on the string having a unique identity, not comparing equal to any previously seen object. (E.g. assuming that each time the expression is evaluated, it produces an object that can serve as a unique key in an EQ hash table). Any situation in which these behaviors cannot be ruled out (because the object escapes beyond the scope of analysis), the optimization cannot be applied.
      - basil-rash 2y ago
        Ah, well all JS strings are always immutable and only value-referable (you have no access to the underlying memory location), so that’s not a concern here.
        kazinator 2y ago
        What about the identity side of it? Does the JS specification say that an operation like "a" + "b" is not required to create a new object? Regardless of whether there is such a spec, you can write code that is sensitive to the difference.
        basil-rash 2y ago
        In fact, you cannot. But I encourage you to try!
        kazinator 2y ago
jagged-chisel 2y ago
My immediate reaction is that this is as much a semantic mistake as “this message does not exist.” Maybe I’m wrong, but … well, there it is.
love2read 2y ago
I did a similar thing in opposite order, I compile js to scheme. https://github.com/u9g/js2scheme/blob/main/example.js https://github.com/u9g/js2scheme/blob/main/example.js Not a serious project, made purely because I had a class that mandated writing scheme for the homeworks. I think the coolest thing to come out of that project was that I learned that it is possible to convert branching if statements to lisp constructs. That was a fun project :)
- djtango 2y ago
  I admire your commitment towards not writing Scheme but I recommend giving it a go. Maybe use it as an opportunity to learn Vim or Emacs and have a go at structural editing. It'll change how you think about your code...
inopinatus 2y ago
"Javascript is a Lisp" would definitely be found in the Big Bumper Book of Divisive Things To Say To Programmers alongside its more famous entries, "Tabs or Spaces?", and "Vim or Emacs?".
gergo_barany 2y ago
Cool stuff! A suggestion: Avoid the term "dead code elimination". Yes, it is an established term, but it is established as a term for two distinct optimizations. One form of "dead code" is code that can never be executed: if (false) { someDeadCode; // "dead" } The other meaning is code that can be executed but computes a value that can never be used: x = someValue; y = someOtherValue; // "dead" return x; I advise my students to use the terms "unreachable code" and "unused code", respectively.
- healeycodes 2y ago
  Ah, this is a useful distinction. Thanks.
bjoli 2y ago
Guile scheme has a way to easily see the result of many of these optimisations since they are done on the source level. This means you see the result of inlining, DCE, constant propagation and partial evaluation. Extremely handy and helps even mediocre programmers like myself develop a good understanding of when optimisations are triggered.
rambojohnson 2y ago
why

112 points by healeycodes 2y ago

Good stuff. On a Lisp compiler optimization tangent: It’s still relevant to SBCL and also generally interesting so the CMUCL advanced compiler manual section[1] is good reading. [1] https://cmucl.org/docs/cmu-user/cmu-user.html#Advanced-Compiler-Use-and-Efficiency-Hints https://cmucl.org/docs/cmu-user/cmu-user.html#Advanced-Compi...

tromp 2y ago

Do you check whether constant folding actually results in shorter code? E.g. something like let a="hello "; b=a++a; c=b++b; in c++c probably shouldn't be changed into "hello hello hello hello hello hello hello hello "

dualogy 2y ago
A sufficiently smart minifier should rewrite that back into `"hello ".times(8)` =)
healeycodes 2y ago
The Lisp variant that the compiler supports at the moment only handles f64 numbers so I don't think this kind of issue is possible. However, this is a very relevant point. If the goal is just shorter code (as opposed to a mix of shorter code and less run-time operations), then you need to check that folding strings (and similar types) actually makes the expression shorter to represent.
retrac 2y ago
Depends whether you're optimizing for program size or runtime speed.
kazinator 2y ago
If these operations produce mutable strings, the conditions under which that would be allowed are fairly stringent. It's not worth doing; it's better for the Lisp to have constructs that allow the programmer easily stage the evaluation in the desired way. Common Lisp has load-time-value. It's also easy to write a macro called macro-eval which evaluates its argument at macro time, and substitutes the result (as a quoted object).
- basil-rash 2y ago
  What is the case you imagine where mutable strings would prohibit this?
  - kazinator 2y ago
    Any situation where the program depends on the expression producing a new string each time it is evaluated, rather than returning the same string. The program may be modifying the string, on the assumption that nothing else has access to it, since it is brand new. The program could also be relying on the string having a unique identity, not comparing equal to any previously seen object. (E.g. assuming that each time the expression is evaluated, it produces an object that can serve as a unique key in an EQ hash table). Any situation in which these behaviors cannot be ruled out (because the object escapes beyond the scope of analysis), the optimization cannot be applied.
    - basil-rash 2y ago
      Ah, well all JS strings are always immutable and only value-referable (you have no access to the underlying memory location), so that’s not a concern here.
      - kazinator 2y ago
        What about the identity side of it? Does the JS specification say that an operation like "a" + "b" is not required to create a new object? Regardless of whether there is such a spec, you can write code that is sensitive to the difference.
        basil-rash 2y ago
        In fact, you cannot. But I encourage you to try!
        kazinator 2y ago

jagged-chisel 2y ago

My immediate reaction is that this is as much a semantic mistake as “this message does not exist.” Maybe I’m wrong, but … well, there it is.

love2read 2y ago

I did a similar thing in opposite order, I compile js to scheme. https://github.com/u9g/js2scheme/blob/main/example.js https://github.com/u9g/js2scheme/blob/main/example.js Not a serious project, made purely because I had a class that mandated writing scheme for the homeworks. I think the coolest thing to come out of that project was that I learned that it is possible to convert branching if statements to lisp constructs. That was a fun project :)

djtango 2y ago
I admire your commitment towards not writing Scheme but I recommend giving it a go. Maybe use it as an opportunity to learn Vim or Emacs and have a go at structural editing. It'll change how you think about your code...

inopinatus 2y ago

"Javascript is a Lisp" would definitely be found in the Big Bumper Book of Divisive Things To Say To Programmers alongside its more famous entries, "Tabs or Spaces?", and "Vim or Emacs?".

gergo_barany 2y ago

Cool stuff! A suggestion: Avoid the term "dead code elimination". Yes, it is an established term, but it is established as a term for two distinct optimizations. One form of "dead code" is code that can never be executed: if (false) { someDeadCode; // "dead" } The other meaning is code that can be executed but computes a value that can never be used: x = someValue; y = someOtherValue; // "dead" return x; I advise my students to use the terms "unreachable code" and "unused code", respectively.

healeycodes 2y ago
Ah, this is a useful distinction. Thanks.

bjoli 2y ago

Guile scheme has a way to easily see the result of many of these optimisations since they are done on the source level. This means you see the result of inlining, DCE, constant propagation and partial evaluation. Extremely handy and helps even mediocre programmers like myself develop a good understanding of when optimisations are triggered.

rambojohnson 2y ago

why