I started this about 9 years ago and never finished it. The idea comes from a course in my telecom degree called "Señales Aleatorias y Ruido" (Random Signals and Noise), I spent so many evenings writing probability by hand, and every time I wanted to check a result with a computer it was a ton of boilerplate.
The engine is Rust, the JIT is built on Cranelift, there is also a WASM backend so everything runs in the browser too.
Full disclosure, I could only finish it now because of AI agents. In my experience they are amazing at the runtime and the numerical code, but pretty bad at language design, so I kept that part for myself.
1. It's obvious that you are a big fan of Cranelift. I'd be interested to hear more about your experience in practical terms. For example could you share any insight about use cases where it is best suited, and where it might be better to look elsewhere? Did you hit any pain points? What was its killer feature for NoiseLang?
2. You wrote: "My favorite trick is in the RNG. Generating random numbers is a serial dependency chain, so instead of fighting that, the kernel runs four independent streams at once and lets the out-of-order core overlap them. This trick ended up beating a hand-written SIMD kernel!" What does this mean exactly? you just ran a scalar kernel 4-wide using SIMD instructions? or you interleaved 4 scalar copies of the same algorithm? did you generate the code or just duplicate the streams by hand?
I built a small one of these as a calculator back in the day, it was fun and I always wanted to see someone really run with the idea more, so your project is super cool!
Did you ever look at symbolic or exact operators instead of purely monte-Carlo?
I remember reading the paper for distr, they used a mix of Fourier transforms for convolution and symbolic reduction to build a probabilistic computing library in R. I attempted building a small python library for this, but for my problems the CLT ended up sufficient to approximate the results faster, so I went with that.
You may enjoy reading the paper, it’s not groundbreaking but is a nice presentation of relationships/operations. Maybe it’ll inspire some features for you.
My system is blocking that site as it is on the HaGeZi blocklist. I don't have any further information, and I'm not expressing an opinion on the site. An alternative might be https://noiselang.com, which is not on the blocklist.
Nice! I’ve dabbled with something similar on my own lately (originally wrote/vibed to explain some concepts that came up when discussing D&D) at diceplots.com - different approach, keeping the distributions exactly analytical at every step, never sampling.
Interestingly, shading languages started out like this - way before consumer GPUs.
I remember encountering this idea written in a book written by Ed Catmull of Pixar fame (can't find the title sorry, but it was written in the 80s), but generally comes from signal processing as a way of avoiding aliasing artifacts..
The core idea is to make programming, which is a discrete and discontinuous domain, into a well-behaved band limited signal. Otherwise you get aliasing (or jaggies), which can happen even INSIDE a surface, if the shader's like that.
The code idea for this is the step function which is the integral of the dirac delta. step(x) returns 1 for all x >0 and 0 otherwise.
Step is not a well-behaved function in the sense, that it changes infinitely quickly at x=0. But once we know what we want, we can replace it with something like that, that's well behaved.
Consider the example pseudocode
color = x> 5? green:blue;
can be rewritten as
color = blue + step(x-5)(green-blue)
With the two being equivalent.
Now if we put the code into a shader, we get jaggies. So to combat the value changing infinitely fast, we go for a function that's like step, but changes smoothly* from 0 to 1 around x=0. Enter smoothstep:
color = blue + smoothstep(x-(5+EPSILION),(x-EPSILON), x)*(green-blue)
And so we defined a 'transition zone' of +-EPSILON(an arbitrary number). While any smooth function can work, smoothstep is chosen because it has a smooth first and second derivative (meaning even if you want to get the rate of change, something that often pops up in computer graphics, the result will be still well behaved).
Pixar's Renderman shading language (which is remarkably similar to GLSL/HLSL/C), used to do this automatically for you. Essentially it could take arbitrary code peppered with if statements, and turn it into a continuous function.
Which is kinda cool imo.
It's also a cool trick in the age of AI. Since you have a function that's well-behaved, you can do things like gradient descent to train an AI to synthetize a function for you. You can even say, that you don't need exact results, you can accept some error.
In this case your program optimization problem can be reframed from doing idempotent transformations on the list of instructions, to getting a program that generates a target function whose error is no greater than some (mathematical) reference function.
Does it still count as a Dirac delta when it’s a discrete distribution? (The distributions in TFA are not continuous - they are things like a roll of 1d6 etc)
I didn’t really see loops being handled here. As far as I understand, the biggest technical difficulty with this kind of probabilistic programming language is handling loops, including infinite loops and almost surely terminating loops.
I did a bit of research earlier in my life[0] to study the handling of loops and without using Monte Carlo simulation. The result was actually workable if incredibly resource intensive to the point of being impractical. If I had chosen to do it again, I might’ve accepted using Monte Carlo simulations while still supporting loops.
20 comments
[ 6.1 ms ] story [ 65.6 ms ] threadThe engine is Rust, the JIT is built on Cranelift, there is also a WASM backend so everything runs in the browser too.
Full disclosure, I could only finish it now because of AI agents. In my experience they are amazing at the runtime and the numerical code, but pretty bad at language design, so I kept that part for myself.
It's a toy language. Ask me anything!
I know MCMC isn’t your goal, but seems like this could be used for ABC-MCMC (as is?)
Would also be nice to have an option to plot using a KDE vs histograms.
(Also your FM example seems to be technically PM)
1. It's obvious that you are a big fan of Cranelift. I'd be interested to hear more about your experience in practical terms. For example could you share any insight about use cases where it is best suited, and where it might be better to look elsewhere? Did you hit any pain points? What was its killer feature for NoiseLang?
2. You wrote: "My favorite trick is in the RNG. Generating random numbers is a serial dependency chain, so instead of fighting that, the kernel runs four independent streams at once and lets the out-of-order core overlap them. This trick ended up beating a hand-written SIMD kernel!" What does this mean exactly? you just ran a scalar kernel 4-wide using SIMD instructions? or you interleaved 4 scalar copies of the same algorithm? did you generate the code or just duplicate the streams by hand?
Did you ever look at symbolic or exact operators instead of purely monte-Carlo?
I remember reading the paper for distr, they used a mix of Fourier transforms for convolution and symbolic reduction to build a probabilistic computing library in R. I attempted building a small python library for this, but for my problems the CLT ended up sufficient to approximate the results faster, so I went with that.
You may enjoy reading the paper, it’s not groundbreaking but is a nice presentation of relationships/operations. Maybe it’ll inspire some features for you.
https://arxiv.org/pdf/1006.0764
Seems worth an investigation and maybe mention on the article.
I remember encountering this idea written in a book written by Ed Catmull of Pixar fame (can't find the title sorry, but it was written in the 80s), but generally comes from signal processing as a way of avoiding aliasing artifacts..
The core idea is to make programming, which is a discrete and discontinuous domain, into a well-behaved band limited signal. Otherwise you get aliasing (or jaggies), which can happen even INSIDE a surface, if the shader's like that.
The code idea for this is the step function which is the integral of the dirac delta. step(x) returns 1 for all x >0 and 0 otherwise. Step is not a well-behaved function in the sense, that it changes infinitely quickly at x=0. But once we know what we want, we can replace it with something like that, that's well behaved.
Consider the example pseudocode
can be rewritten as color = blue + step(x-5)(green-blue)With the two being equivalent.
Now if we put the code into a shader, we get jaggies. So to combat the value changing infinitely fast, we go for a function that's like step, but changes smoothly* from 0 to 1 around x=0. Enter smoothstep: color = blue + smoothstep(x-(5+EPSILION),(x-EPSILON), x)*(green-blue)
And so we defined a 'transition zone' of +-EPSILON(an arbitrary number). While any smooth function can work, smoothstep is chosen because it has a smooth first and second derivative (meaning even if you want to get the rate of change, something that often pops up in computer graphics, the result will be still well behaved).
Pixar's Renderman shading language (which is remarkably similar to GLSL/HLSL/C), used to do this automatically for you. Essentially it could take arbitrary code peppered with if statements, and turn it into a continuous function.
Which is kinda cool imo.
It's also a cool trick in the age of AI. Since you have a function that's well-behaved, you can do things like gradient descent to train an AI to synthetize a function for you. You can even say, that you don't need exact results, you can accept some error.
In this case your program optimization problem can be reframed from doing idempotent transformations on the list of instructions, to getting a program that generates a target function whose error is no greater than some (mathematical) reference function.
I did a bit of research earlier in my life[0] to study the handling of loops and without using Monte Carlo simulation. The result was actually workable if incredibly resource intensive to the point of being impractical. If I had chosen to do it again, I might’ve accepted using Monte Carlo simulations while still supporting loops.
[0]: https://github.com/kccqzy/probabilistic-program-inference/bl... Shameless self promotion I know! I put quite a bit of effort into that README and the code.