in ,

Do you have a problem? Write a compiler, Hacker News


            

    Posted on 2019 – 09 – 26              by Oleg Grenrus          

These are notes of the talk I gave atClojuTre 2019. There should be a video recording of the talk, I’ll add a link here. There’sthe slide deck as PDF too.

This work is licensed under a “CC BY SA 4.0” license.

Hello ClojuTre. I’m Oleg from Helsinki.


Imagine you are writing a cool new rogue-like game. So cool many have no idea what’s going on. A definitive character of rogue-likes is procedural generation of content. You’ll need a random number generator for that.


SplitMix is ​​a fast, splittable pseudorandom number generator. Being able to split a generator into two independent generators is a property you’ll want if you use the generator in a functional programming language. Look it up. We’ll concentrate on the being fast part. Obviously you want things to be fast.

SplitMix is ​​fast. It does only 9 operations per generated number, one addition to advance the random seed, andxor,shift,multiplyxor,shift,multiply,xorandShift. 9 in total.

However, for the maximum reach, we want our game to run in the web browsers.


  • JavaScript is a great platform
  • But a terrible programming language

Look carefully. When we multiply two “big” odd numbers, we do get even result. We shouldn’t: product of two odd numbers is odd.

JavaScript numbers are a mess. Next a bit of arithmetics.


Instead of multiplying two big numbers, we split them in high and low parts and multiply many small numbers. Like in an elementary school. Then we’ll have enough precision.


So as we are multiplying 32 bit numbers , and are interested only in lower 32 bits of 64 bit result. Then we need to do only three multiplications.

At the end, we can get correct results, i.e. good random numbers even in JavaScript.


Next if we replace the multiplication inxor-shift-multiplywith a macro doing the right thing, and actually change everything to be a macro, and expand we’ll get …


a lot of code which barely fits on the slide.

I had to shortedbit-shift-left (tobslandunsigned-bit-shift-righttoUBSR.


Look closely. Would you write this kind of code.


We bind (“assign”) a constant value touvvariable.


And the calculate the high and low 16 bit parts of it. Something we could write directly:let [u 0x85eb v ca6b], i.e.optimize by hand. Should we do so?


No. Let’s rather write an (optimizing) compiler. We don’t have time to optimize by hand.


Recall, we have a very specific problem. Working with a very very tiny subset of Clojure. Some simple arithmetic and bit mangling of (bit numbers.)


We’d like to add a little ofmagic, which would make the program magically run faster. In my toy-micro benchmarks the speed-up is 10 percent. It’s definitely worth it.


What is this magic?


A little cute macro. Of course.


We get aformand convert it into internal representation on a way in, and back to Clojure on the way back.

Working the whole Clojure syntax directly is insane task. We want only deal with a small sane subset of it. Also in a easier to manipulate format. Clojure as a pragmatic language is still optimized for writing and reading, not machine manipulation so much.


The next step is to expand a multiplication using a trick we have seen previously. We could have done it already infrom-clojurestep, but it’s good engineering to have only one thing per step.


And the important part is theoptimizefunction .


The internal representation I used is nested vectors with a node type as a first element. An uniform representation made it way easier to do everything else. Note how literals 1 and 3 are wrapped into vector too. We can simply look at the head of a vector to know what we are dealing with.

Code is Data.


A difficult part inCode is Dataare local variables. I chose to usede Bruijnindices, so instead of names: (x) andyoraand (b) there are numbers counting towards the correspondinglet(which binds only one variable at the time by the way).

de Bruijn indices are tricky to grok. Look at the colors, they are there to help. The blue: var 1references “one away”let.

I don’t expect you to understand them. It’s one way to represent bindings. Perfectly there should be a library, so you don’t need to think about low-level details.


Once we got rid out of names, we can still keep them around using metadata. That’s a really cool feature in Clojure, I have to admit. The metadata is there, but not in your way. And having names around is actually useful when you try to debug things.


Now we have a setup done. Let’s jump into optimizations.


Recall our code snippet. There’suvwhich is bound to a constant. And then it’s used an expression which could simplify if we do this and that …


Let’s keep it super simple.

  • We can have a small set of simple local rewrite rules. Local meaning, we don’t need to look around, only at one subexpression at the time.
  • Then we try to match the rule everywhere, and if it match, perform the rewrite.
  • And loop until there’s nothing to do.

The first optimization is inlining. In a sense it’s most powerful one, as it makes opportunities for other optimizations to fire, even that on itself it doesn’t do much.

So if we have a let-binding, then in some cases we perform a substitution. Replace allxs with anexpressioninside a body.

let x 1 y 1 ( xy)to a lot simpler( 1 2). But nothing more, just that.


I need to point out, that optimizing is somewhat of an art. Sometimes it work, sometimes it don’t.

For example, we don’t want to duplicate an expensive(fibonacci 100)expression. We want to evaluate it once and share the result.

On the other hand, if someone already went and computed the value, then we can push it to the leaves of an expression tree.

Heuristics are tricky.

Luckily for our needs simple heuristics work well.


Wheninliningis a valid rewrite?


Not in every language. Consider this not-so-functional example.

If we substitute everything, the(do-foo)and(do-bar)would be in different order. And(do-quux)will be gone completely, hopefully it didn’t anything important!

We need a language where there are no side-effects, nor there are so much difference in the execution order. Whole Clojure isn’t such language. Our tiny subset is.

I have heard there are programming languages ​​which behave like our small one, but are more general purpose!

OK. Let’s move to the next optimization.


When we have something simple as( 1 2), let us evaluate it already at compile time.

For every primitive operation, if the arguments are known constants, just do it.


Now, I ask you whenconstant foldingis a valid rewrite.


Well, that was a trick question. It really depends on primitives, whether it make sense to perform them at compile time. (Even pure languages ​​have primitives to print stuff on a screen).

But you could think about thatprecalculateexample . When does it makes to perform the calculation (assuming we somehow know it terminates):

  • At compile time?
  • At start up?
  • At first access?

It really depends, and there are no single simple answer.

Again, optimizations is an art.


Because we work with nice internal representation, writing individual optimizations is so nice.

  • if a node is not one of special nodes
  • and all node arguments are constants
  • evaluate it.

The code is shorter than my explanation. And still understandable.


With these two optimizations, inlining and constant folding, we get from this big (and repetitive) code blob to …


Something which actually fits on the slide without font size scaling. It’s not super-pretty, but it’s hard to spot if something can be done there.


We can make it look nice with one more optimization. When you bind a let-expression to a variable in outer let-expression, we can float out the inner one.

A very old idea it is.


And then we get (in my opinion) a very nice direct code. Six intermediate results to get final one.


That’s what I wanted to tell you.


  • Implementing small (domain specific) languages is fun.
  • If you approach problems with “let’s write a programming language to describe them” -attitude there a lot of big hammers in your disposal. A lot of wheels is already invented.
  • Languages ​​don’t need only be about numerics, it could be HTTP routing, authorization rules, UI-workflows, CI-scripts (I could bash about bash), data descriptions, you name it.
  • But make your languages ​​typed, lazy, pure, total or and even dependentfor extra fun and interesting new problems. 😉

Thank you.

Site proudly generated byHakyll

Brave Browser
Read More
Payeer

What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

GIPHY App Key not set. Please check settings

Dow Futures Search for Reprieve After Chaotic Selloff as Investors Assess Over-Hyped Trump Rally, Crypto Coins News

Dow Futures Search for Reprieve After Chaotic Selloff as Investors Assess Over-Hyped Trump Rally, Crypto Coins News

What are the most indispensable books for indie hackers ?, Hacker News

What are the most indispensable books for indie hackers ?, Hacker News