3 ms·

Could you explain why did you choose to write your own implementation of DAG instead of using something like petgraph? At first glance I get the feeling that i

by matesz 5y ago

Could you explain why did you choose to write your own implementation of DAG instead of using something like petgraph? At first glance I get the feeling that it is really nice! Any elaboration on that would be really appreciated. Good luck with this project. For sure you are on to something. Time will tell. Don’t forget to research industry leaders like Ted Nelson :)

jcburnham 5y ago
Sure, so I do use petgraph for actually visualizing the lambda DAG graphs, since it's got a very nice graphviz integration: https://github.com/yatima-inc/yatima/blob/059b0abccd0ca54b9a27a1c68f70222394dbe681/core/src/graph.rs https://github.com/yatima-inc/yatima/blob/059b0abccd0ca54b9a.... You can see the output of that here: https://i.redd.it/94zg24fboyv61.png https://i.redd.it/94zg24fboyv61.png (N.B. We removed that module from the language core since we're trying to make that no_std, but we're adding it back to our utils crate soon: https://github.com/yatima-inc/yatima/issues/70 https://github.com/yatima-inc/yatima/issues/70) But we can't use petgraph for the actual computational lambda-DAG because of performance. For example, one thing we get by using pointers is constant-time insertion and removal of of parent nodes (every node in the graph points to their parent). We actually wrote our own Doubly-Linked-List in Rust (it can be done!) to store pointers to the parents for this reason: https://github.com/yatima-inc/yatima/blob/main/core/src/dll.rs https://github.com/yatima-inc/yatima/blob/main/core/src/dll..... There's also memory concerns, given that the lambda-DAG collects its own garbage, freeing space allocated for nodes when no longer in use, whereas I believe petgraph is just `Vec` internally, which would require shrinking, and that would also be slow. All this low-level pointer manipulation was, tbh, a huge amount of work, but the end result is a performant lazy lambda-calculus reducer with sharing in a few thousand lines of Rust, which means fast lambdas on wherever WASM runs. (That said, I'm a little bit concerned about cache misses with all the pointer chasing we do, but I haven't yet gotten around to profiling different Yatima expressions to measure this. Would be a great project for an OSS contributor too, so I'll probably make a GH issue for it!)

by matesz 5y ago

jcburnham 5y ago

Sure, so I do use petgraph for actually visualizing the lambda DAG graphs, since it's got a very nice graphviz integration: https://github.com/yatima-inc/yatima/blob/059b0abccd0ca54b9a27a1c68f70222394dbe681/core/src/graph.rs https://github.com/yatima-inc/yatima/blob/059b0abccd0ca54b9a.... You can see the output of that here: https://i.redd.it/94zg24fboyv61.png https://i.redd.it/94zg24fboyv61.png (N.B. We removed that module from the language core since we're trying to make that no_std, but we're adding it back to our utils crate soon: https://github.com/yatima-inc/yatima/issues/70 https://github.com/yatima-inc/yatima/issues/70) But we can't use petgraph for the actual computational lambda-DAG because of performance. For example, one thing we get by using pointers is constant-time insertion and removal of of parent nodes (every node in the graph points to their parent). We actually wrote our own Doubly-Linked-List in Rust (it can be done!) to store pointers to the parents for this reason: https://github.com/yatima-inc/yatima/blob/main/core/src/dll.rs https://github.com/yatima-inc/yatima/blob/main/core/src/dll..... There's also memory concerns, given that the lambda-DAG collects its own garbage, freeing space allocated for nodes when no longer in use, whereas I believe petgraph is just `Vec` internally, which would require shrinking, and that would also be slow. All this low-level pointer manipulation was, tbh, a huge amount of work, but the end result is a performant lazy lambda-calculus reducer with sharing in a few thousand lines of Rust, which means fast lambdas on wherever WASM runs. (That said, I'm a little bit concerned about cache misses with all the pointer chasing we do, but I haven't yet gotten around to profiling different Yatima expressions to measure this. Would be a great project for an OSS contributor too, so I'll probably make a GH issue for it!)