> Bending is the opposite of folding. Whatever fold consumes, bend creates.
But in everyday language bending is not the opposite of folding, they are more or less the same thing. Why not "unfold", which also has a connotation of "the process of happening" as well as merely the opposite of folding?
I have a question about the example code and output for bending:
type Tree:
Node { ~lft, ~rgt }
Leaf { val }
def main():
bend x = 0:
when x < 3:
tree = Tree/Node { lft: fork(x + 1), rgt: fork(x + 1) }
else:
tree = Tree/Leaf { val: 7 }
return tree
tree = fork(0)
tree = ![fork(1), fork(1)]
tree = ![![fork(2),fork(2)], ![fork(2),fork(2)]]
tree = ![![![fork(3),fork(3)], ![fork(3),fork(3)]], ![![fork(3),fork(3)], ![fork(3),fork(3)]]]
tree = ![![![7,7], ![7,7]], ![![7,7], ![7,7]]]
Where does the initial "tree = fork(0)" come from?
The first `fork` is from using bend and passing the initial state
The program above will initialize a state (`x = 0`), and then, for as long as `x < 3`,
it will "fork" that state in two, creating a `Tree/Node`, and continuing with `x + 1`.
When `x >= 3`, it will halt and return a `Tree/Leaf` with `7`.
When all is done, the result will be assigned to the `tree` variable:
Re: name. Fold and bend are indeed called fold and unfold in Haskell and traditional functional programming literature.
I wonder if bend has to do with how we manipulate the computation's interaction graph while evaluating a bend. There might be some bending of wires!
Re: code example
In the code example, x=0 is the seed value. tree = fork(0) must mean "fork off to evaluate the bend at the seed value". In that first fork, we fork twice with the value x=1, to get the left and right subtrees of the top level node. We then fork four instances of x=2, eight instances of x = 3, and finally get our balanced binary tree with eight 7s.
Note this is guesswork. I don't know what the ![a, b] syntax means, and I haven't read much of the guide.
Appendix: Notes on Fold Vs Bend
I wrote these for an earlier draft while reminding myself about these operations. I include them more for my benefit, and in case they help you or the audience.
Fold and bend are categorical duals, aka catamorphisms and anamorphisms. One takes a monadic value and reduces it into an ordinary value. The other takes an ordinary value and expands it into a comonadic value.
Fold starts with a value in an inductive data type, and then replaces its constructors with a function. For example it takes a list (1:2):3, and replaces the constructor : with the function `+`, to get (1+2)+3 = 6
Bend starts with a seed value and a function taking values into constructor expressions for a conductive data type. It then grows the seed into a potentially infinite AST. For example the seed value 1 and the function f(x:xs) = (x+1) : (x:xs) gives us the infinite lazy list [1, 2, 3, ...]
The question that comes to me is: can I use fork(x) outside of a bend?
Seems like probably not, there doesn't seem to be enough information in the 'argument' to this 'function' to do anything useful without the implicit context of the bend construct.
For that reason I think I'd prefer it if fork was a keyword (like 'bend' and 'when') rather than a 'function', just at the surface syntax level to give a clue it is something special.
I guess fork is a kind of 'magic' function that represents the body of the bend. It's a bit like a 'self' or 'this'.
At the moment this syntax is in a weird half-way point ...the underlying concept is necessarily functional but it's trying to look kind of like an imperative for-loop still.
I wonder if we couldn't just explicitly create a 'bendable' recursive function that can be 'bent' by calling it. But I guess it's like this because it needs to be tightly constrained by the 'when' and 'else' forms.
TBH the more I look at this example the more confusing it is. The other part I wonder about is the assigning of new values to tree var... can I set other local vars from outside the bend scope? I don't think so, I guess it'd be a syntax error if the var names assigned in the 'when' and 'else' clauses didn't match?
Again it's sort of overloading an imperative-looking syntax to implicitly do the 'return' from the implicit recursive function.
Later on there is this example:
def render(depth, shader):
bend d = 0, i = 0:
when d < depth:
color = (fork(d+1, i*2+0), fork(d+1, i*2+1))
else:
width = depth / 2
color = shader(i % width, i / width)
return color
And here I wonder - does 'width' have a value after the bend? Or it's only the last assignment in each clause that is privileged?
That's an odd mix in a language which otherwise has explicit returns like Python.
If so I wonder if a syntax something like this might be clearer:
def render(depth, shader):
bend color with d = 0, i = 0:
when d < depth:
yield (fork(d+1, i*2+0), fork(d+1, i*2+1))
else:
width = depth / 2
return shader(i % width, i / width)
return color
i.e. name the return var once in the bend itself, yield intermediate values (to itself, recursively) and return the final state.
`bend` is a convenience syntax that "just creates an in-place recursive function, immediately calls it with an initial state, and then assigns the end result to a local variable" ... "in a single statement, rather than needing to name a separate external auxilliary function that you'll only use once", according to the original author on Twitter:
https://x.com/VictorTaelin/status/1791964640533958924 and
https://x.com/VictorTaelin/status/1791996185449791932
But contrary to this, I think explicitly separating function declaration and function calling, in the following kind of syntax, would make it much clearer and less complected where the initial condition `tree = fork(0)` comes from. In the original example it came from `bend x = 0`, but here the function declaration is separate and the call more explicit: so it more obviously comes from `createTree(0)`:
type Tree
Branch { left, right }
Leaf { value }
def main():
createTree(x):
x < 3 ?
Tree.Branch { left: createTree(x+1), right: createTree(x+1) }
Tree.Leaf { value: 7 }
createTree(0)
Besides not needing a local variable `tree` here, the unique thing here is the elimination of the else-clause, to reduce unnecessary nesting, and a rule that the language just early returns the last result of any nested condition. If it doesn't go into any nested condition, then it just returns the last result in the main function body (like Ruby). Without any `return` keywords needed in either case. Wouldn't this be quite beautiful?
They never took off because we discovered, to our surprise to some extent, that gradient descent through back propagation works better than expected if you give it the right learning media and the right input and output encodings. It took a ton of fiddling ("graduate student descent") to figure those out.
Back then everyone thought it was doomed to get stuck at local minima, but it turns out that has a lower probability of happening if the search space has enough dimensions. It works well enough to make the sand talk back to us and now that particular design has sucked all the air out of the room.
Nobody has tried EC at anywhere near the scale of GPTs/LLMs because that amount of compute is expensive and at this point we know those will at least work.
I still think EC is fascinating and would love to play with it some more at some point, maybe trying it combined with back propagation in novel ways. Compute only gets cheaper.
They're probably hitting ctrl+c at the end of the lines they don't want to run, that's telling the terminal "cancel that" but it'll usually just go to the next line and leave what you typed in place, like in this video.
I think I have a use for this but I’m realizing that I don’t know how to build a mental model of what is going to parallelize in this system. Surely some algorithms are better and getting chopped up than others - how can I tell what is going on?
I think this is an unsolved tooling question right now.
You could get some sense of the parallelism by using `/usr/bin/time` and dividing the wall time with the user time.
You could look at the Task Manager / Activity Monitor / htop and see if it's using 800% CPU or whatever.
You could use psrecord (https://pypi.org/project/psrecord/) to get a relatively finegrained CPU+mem usage graph across the duration of the program.
But it would probably still be best to record some sort of stats in the Bend/HVM itself, enabled via a CLI flag. Reductions per ms, sampled across the program duration, or something like that.
I'd be interested in anybody's ideas of what a good metric would be here!
Fala Taelin, nice work! Does HVM2 compile interaction nets to e.g. spirv, or is this an interpreter (like the original HVM) that happens to run on the GPU?
I ask because a while back I was messing around with compiling interaction nets to C after reducing as much of the program as possible (without reducing the inputs), as a form of whole program optimization. Wouldn't be too much harder to target a shader language.
Edit: Oh I see...
> This repository provides a low-level IR language for specifying the HVM2 nets, and a compiler from that language to C and CUDA
HVM
I was talking about traversing an interaction net to recover a lambda-calculus-like term, which can be lowered to C a la lisp in small pieces with minimal runtime overhead.
Honestly the motivation is, you are unlikely to outperform a hand-written GPU kernel for like ML workloads using Bend. In theory, HVM could act as glue, stitching together and parallelizing the dispatch order of compute kernels, but you need a good FFI to do that. Interaction nets are hard to translate across FFI boundaries. But, if you compile nets to C, keeping track of FFI compute kernel nodes embedded in the interaction network, you can recover a sensible FFI with no translation overhead.
The other option is implementing HVM in hardware, which I've been messing around with on a spare FPGA.
It is an interpreter that runs on GPUs, and a compiler to native C and CUDA. We don't target SPIR-V directly, but aim to. Sadly, while the C compiler results in the expected speedups (3x-4x, and much more soon), the CUDA runtime didn't achieve substantial speedups, compared to the non-compiled version. I believe this is due to warp-divergence: with non-compiled procedures, we can actually merge all function calls into a single "generic" interpreted function expander that can be reduced by warp threads without divergence. We'll be researching this more extensively looking forward.
Oh that's cool! Interested to see where your research leads. Could you drop me a link to where the interaction net → cuda compiler resides? I skimmed through the HVM2 repo and just read the .cu runtime file.
Edit: nvm, I read through the rest of the codebase. I see that HVM compiles the inet to a large static term and then links against the runtime.
Yes, Kind2 will be a type layer on top of Bend, with a similar relationship as in JavaScript / TypeScript (but much more integrated, less ad-hoc and with proofs!). I don't want Kind2 to compete directly with Lean though, as it is doing an amazing job and I'm rooting for it. So, Kind2 will be just a type system for Bend that happens to let you prove theorems about your programs, rather than a higher promise to digitalize all of maths and stuff.
I've made a benchmark of Bend running a simple counter program on CPU vs GPU, vs Haskell,Node,Python,C that I plan to write a blogpost about, probably this Sunday:
This is unproven (and not a toy problem), but I imagine it's going to do pretty well at compilers. The amount of time I'm waiting at work, hypnotizing the tsc process that sits at 100% CPU, wishing it was parallel...
> That's a 111x speedup by doing nothing. No thread spawning, no explicit management of locks, mutexes. We just asked bend to run our program on RTX, and it did. Simple as that. Note that, for now, Bend only supports 24-bit machine ints (u24), thus, results are always mod 2^24.
Ahh, not even 32bit? Hmm, that seems pretty arbitrary for someone not accustomed to gpu's and wanting to solve some problems requiring 64 bits (gravitational simulation of solar system at millimeter resolution could use ~58bit ints for position).
I know the docs say this will be fixed soon, but what is the main reason for restricting number types to 24 bits? I saw in the code that they are wrapper around the 32-bit system number types, so what prevents Bend from changing them to U32(u32) right now?
Seriously though. Implementing a full high-level lang in parallel is HARD, so, to simplify it greatly, we made IC nodes 64-bit, which allows us to use native 64-bit atomic operations in many parts of the implementation. Since each 64-bit node has 2 ports, that gives us 32 bits per port. And since we use 3 bits for the tag, that leaves us with 29 bit payloads. We used that space to easily implement unboxed numbers (f24, u24, i24).
That said, we will have (boxed) 64-bit numbers soon! With this foundation in place, adding them is a matter of coding. I just want to have some time to let people use the limited version, find bugs, etc., before I add more stuff.
268 comments
[ 3.0 ms ] story [ 237 ms ] threadNow I just need a Common Lisp implemented using it!
It's magical how the GPU version is basically flat (although with a high runtime init cost)
I would say that the play on words that gives the language its name ("Bend") doesn't really make sense...
https://github.com/HigherOrderCO/bend/blob/main/GUIDE.md
> Bending is the opposite of folding. Whatever fold consumes, bend creates.
But in everyday language bending is not the opposite of folding, they are more or less the same thing. Why not "unfold", which also has a connotation of "the process of happening" as well as merely the opposite of folding?
I have a question about the example code and output for bending:
Where does the initial "tree = fork(0)" come from?all the other "fork"s in the output are produced explicitly by:
so presumably the initial fork(0) state is implicitly produced by the bend
I wonder if bend has to do with how we manipulate the computation's interaction graph while evaluating a bend. There might be some bending of wires!
Re: code example
In the code example, x=0 is the seed value. tree = fork(0) must mean "fork off to evaluate the bend at the seed value". In that first fork, we fork twice with the value x=1, to get the left and right subtrees of the top level node. We then fork four instances of x=2, eight instances of x = 3, and finally get our balanced binary tree with eight 7s.
Note this is guesswork. I don't know what the ![a, b] syntax means, and I haven't read much of the guide.
Appendix: Notes on Fold Vs Bend
I wrote these for an earlier draft while reminding myself about these operations. I include them more for my benefit, and in case they help you or the audience.
Fold and bend are categorical duals, aka catamorphisms and anamorphisms. One takes a monadic value and reduces it into an ordinary value. The other takes an ordinary value and expands it into a comonadic value.
Fold starts with a value in an inductive data type, and then replaces its constructors with a function. For example it takes a list (1:2):3, and replaces the constructor : with the function `+`, to get (1+2)+3 = 6
Bend starts with a seed value and a function taking values into constructor expressions for a conductive data type. It then grows the seed into a potentially infinite AST. For example the seed value 1 and the function f(x:xs) = (x+1) : (x:xs) gives us the infinite lazy list [1, 2, 3, ...]
Seems like probably not, there doesn't seem to be enough information in the 'argument' to this 'function' to do anything useful without the implicit context of the bend construct.
For that reason I think I'd prefer it if fork was a keyword (like 'bend' and 'when') rather than a 'function', just at the surface syntax level to give a clue it is something special.
I guess fork is a kind of 'magic' function that represents the body of the bend. It's a bit like a 'self' or 'this'.
At the moment this syntax is in a weird half-way point ...the underlying concept is necessarily functional but it's trying to look kind of like an imperative for-loop still.
I wonder if we couldn't just explicitly create a 'bendable' recursive function that can be 'bent' by calling it. But I guess it's like this because it needs to be tightly constrained by the 'when' and 'else' forms.
TBH the more I look at this example the more confusing it is. The other part I wonder about is the assigning of new values to tree var... can I set other local vars from outside the bend scope? I don't think so, I guess it'd be a syntax error if the var names assigned in the 'when' and 'else' clauses didn't match?
Again it's sort of overloading an imperative-looking syntax to implicitly do the 'return' from the implicit recursive function.
Later on there is this example:
And here I wonder - does 'width' have a value after the bend? Or it's only the last assignment in each clause that is privileged?That's an odd mix in a language which otherwise has explicit returns like Python.
If so I wonder if a syntax something like this might be clearer:
i.e. name the return var once in the bend itself, yield intermediate values (to itself, recursively) and return the final state.But contrary to this, I think explicitly separating function declaration and function calling, in the following kind of syntax, would make it much clearer and less complected where the initial condition `tree = fork(0)` comes from. In the original example it came from `bend x = 0`, but here the function declaration is separate and the call more explicit: so it more obviously comes from `createTree(0)`:
Besides not needing a local variable `tree` here, the unique thing here is the elimination of the else-clause, to reduce unnecessary nesting, and a rule that the language just early returns the last result of any nested condition. If it doesn't go into any nested condition, then it just returns the last result in the main function body (like Ruby). Without any `return` keywords needed in either case. Wouldn't this be quite beautiful?Back then everyone thought it was doomed to get stuck at local minima, but it turns out that has a lower probability of happening if the search space has enough dimensions. It works well enough to make the sand talk back to us and now that particular design has sucked all the air out of the room.
Nobody has tried EC at anywhere near the scale of GPTs/LLMs because that amount of compute is expensive and at this point we know those will at least work.
I still think EC is fascinating and would love to play with it some more at some point, maybe trying it combined with back propagation in novel ways. Compute only gets cheaper.
You could get some sense of the parallelism by using `/usr/bin/time` and dividing the wall time with the user time.
You could look at the Task Manager / Activity Monitor / htop and see if it's using 800% CPU or whatever.
You could use psrecord (https://pypi.org/project/psrecord/) to get a relatively finegrained CPU+mem usage graph across the duration of the program.
But it would probably still be best to record some sort of stats in the Bend/HVM itself, enabled via a CLI flag. Reductions per ms, sampled across the program duration, or something like that.
I'd be interested in anybody's ideas of what a good metric would be here!
EDIT: CLI flag, not CPU flag
I ask because a while back I was messing around with compiling interaction nets to C after reducing as much of the program as possible (without reducing the inputs), as a form of whole program optimization. Wouldn't be too much harder to target a shader language.
Edit: Oh I see...
> This repository provides a low-level IR language for specifying the HVM2 nets, and a compiler from that language to C and CUDA HVM
Will have to look at the code then!
https://github.com/HigherOrderCO/HVM
Edit: Wait nvm, it looks like the HVM2 cuda runtime is an interpreter, that traverses an in-memory graph and applies reductions.
https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
I was talking about traversing an interaction net to recover a lambda-calculus-like term, which can be lowered to C a la lisp in small pieces with minimal runtime overhead.
Honestly the motivation is, you are unlikely to outperform a hand-written GPU kernel for like ML workloads using Bend. In theory, HVM could act as glue, stitching together and parallelizing the dispatch order of compute kernels, but you need a good FFI to do that. Interaction nets are hard to translate across FFI boundaries. But, if you compile nets to C, keeping track of FFI compute kernel nodes embedded in the interaction network, you can recover a sensible FFI with no translation overhead.
The other option is implementing HVM in hardware, which I've been messing around with on a spare FPGA.
Edit: nvm, I read through the rest of the codebase. I see that HVM compiles the inet to a large static term and then links against the runtime.
https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
Will have to play around with this and look at the generated assembly, see how much of the runtime a modern c/cu compiler can inline.
Btw, nice code, very compact and clean, well-organized easy to read. Rooting for you!
I’d also love to find an example of writing a small interpreter in Bend - which runs on the GPU.
https://docs.google.com/spreadsheets/d/1V_DZPpc7_BP3bmOR8Ees...
It's magical how the GPU version is basically flat (although with a high runtime init cost).
https://github.com/HigherOrderCO/bend/blob/main/GUIDE.md#par...
Running the equivalent C code takes ~2.3 seconds on my machine. Same order of magnitude as bend on the beefy GPU.
> That's a 111x speedup by doing nothing. No thread spawning, no explicit management of locks, mutexes. We just asked bend to run our program on RTX, and it did. Simple as that. Note that, for now, Bend only supports 24-bit machine ints (u24), thus, results are always mod 2^24.
Ahh, not even 32bit? Hmm, that seems pretty arbitrary for someone not accustomed to gpu's and wanting to solve some problems requiring 64 bits (gravitational simulation of solar system at millimeter resolution could use ~58bit ints for position).
This is a proof of concept version which focuses on the provable correctness of the parallel compiler.
I know the docs say this will be fixed soon, but what is the main reason for restricting number types to 24 bits? I saw in the code that they are wrapper around the 32-bit system number types, so what prevents Bend from changing them to U32(u32) right now?
Short answer: GPU
Long answer: CUDA
Seriously though. Implementing a full high-level lang in parallel is HARD, so, to simplify it greatly, we made IC nodes 64-bit, which allows us to use native 64-bit atomic operations in many parts of the implementation. Since each 64-bit node has 2 ports, that gives us 32 bits per port. And since we use 3 bits for the tag, that leaves us with 29 bit payloads. We used that space to easily implement unboxed numbers (f24, u24, i24).
That said, we will have (boxed) 64-bit numbers soon! With this foundation in place, adding them is a matter of coding. I just want to have some time to let people use the limited version, find bugs, etc., before I add more stuff.
Eeek.