Our great sponsors
-
-
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
-
-
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
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/059b0abccd0ca54b9a....
You can see the output of that here: 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)
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.....
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!)
I would dearly love to make Yatima a usable theorem prover, and Lean has been a huge inspiration particularly regarding syntax. But building a usable theorem prover is a huge project, and at minimum will require substantial work on our theory, on type-inference (which is fairly minimal right now) and on advanced features like quotient types or univalence.
On that point, we've done a little exploration on encoding the Path types from Cubical Type Theory as self-types, and I think there's some promising work to be done there. But I know my limits and while I feel very comfortable building a useful programming language that can do a little bit of basic theorem proving, I know that doing a proper job on a real theorem is going to require larger scale resources.
As far as the link from the Self-Types paper, our theory is similar to their System S, but is not the same. Not 100% sure but I think the main relevant difference here is about Leibniz equality, which iirc allows for saying `a == b` when `a` and `b` are of different types. Yatima's Equal type https://github.com/yatima-inc/introit/blob/main/Equal.ya, implements the more standard homogenous/Martin-Löf equality, but this is just a library, not a language builtin.
We really do need to write an actual paper for Yatima's theory though, especially considering that we've combined the self-types from System S with a variation of Quantitative Types a la Idris 2. Writing that paper is likely step 0 of any Yatima as a theorem prover project, until then we should view Yatima as just an unsound functional programming language with some nice type-level features
Absolutely accepting contributions, come join our matrix channel: #yatima:matrix.org https://matrix.to/#/!bBgWgXJqeKuDuiUYWN:matrix.org?via=matri...
This issue (on improving the test-suite) is a particularly good starter issue: https://github.com/yatima-inc/yatima/issues/37
So, I love Rust immensely, but it's a totally different style of programming than a functional language like Haskell. For example, Rust closures are absolutely not the same as pure functions, and if you try to use them that way you'll have a bad time. Another thing is that Rust's approach to garbage collection is "opt-in" (with Rc, etc), which is great for low-level control, but not so great when you're trying to write high-level or non-performance-critical things. And lastly, recursion is Rust is restricted by the stack, so if you try to recurse too much you'll panic. You can manually increase the stack, of course, but this is again a case of having to explicitly handle your resources.
In some sense, Yatima's trying to be to Rust what Haskell is to C. We reuse a lot of the primitives (like ints, uints, chars, etc), but in a separate runtime layer that lets you just use a lambda like a lambda, and not have to worry if you're recursing too much. Now, that comes with overhead, but in a lot of places (like on the web) that's acceptable.
Another thing to think about is determinism. One goal of Yatima is to have each content-id always run the same way given the same inputs. That means we have to forgo using things like hardware floats (or at least not without some complex wrapping) which can cause UB if you try to read their bits (even in WASM).
I think definitely we're going to want to explore both frontend (along the lines of something like https://seed-rs.org/) and backend use cases for Yatima. I'm looking with great interest at https://github.com/lunatic-solutions/lunatic to see if there's a way for us to integrate their lightweight processes. As far as I understand this is along the lines of what https://www.unisonweb.org/ is doing.
The other thing I'm thinking about is smart contracts. Since Yatima is almost `no_std`, we should be able to build it as a pallet for substrate.dev.
So, I love Rust immensely, but it's a totally different style of programming than a functional language like Haskell. For example, Rust closures are absolutely not the same as pure functions, and if you try to use them that way you'll have a bad time. Another thing is that Rust's approach to garbage collection is "opt-in" (with Rc, etc), which is great for low-level control, but not so great when you're trying to write high-level or non-performance-critical things. And lastly, recursion is Rust is restricted by the stack, so if you try to recurse too much you'll panic. You can manually increase the stack, of course, but this is again a case of having to explicitly handle your resources.
In some sense, Yatima's trying to be to Rust what Haskell is to C. We reuse a lot of the primitives (like ints, uints, chars, etc), but in a separate runtime layer that lets you just use a lambda like a lambda, and not have to worry if you're recursing too much. Now, that comes with overhead, but in a lot of places (like on the web) that's acceptable.
Another thing to think about is determinism. One goal of Yatima is to have each content-id always run the same way given the same inputs. That means we have to forgo using things like hardware floats (or at least not without some complex wrapping) which can cause UB if you try to read their bits (even in WASM).
I think definitely we're going to want to explore both frontend (along the lines of something like https://seed-rs.org/) and backend use cases for Yatima. I'm looking with great interest at https://github.com/lunatic-solutions/lunatic to see if there's a way for us to integrate their lightweight processes. As far as I understand this is along the lines of what https://www.unisonweb.org/ is doing.
The other thing I'm thinking about is smart contracts. Since Yatima is almost `no_std`, we should be able to build it as a pallet for substrate.dev.
Sure, if you consider Haskell's runtime (I know that technically GHC /= Haskell, but in practice it's the only Haskell that matters, except maybe something like Asterius) all the primitives are backed by C libraries: https://hackage.haskell.org/package/ghc-prim-0.4.0.0/docs/GH...
Likewise with conventions around pointers, arrays, etc. to the point where if you want to do anything really low-level or performance sensitive in Haskell, you're essentially punching a hole into C. As a random example, within the fast base64bytestring library, you find lots of use of `malloc`, `ForeignPtr` etc.: https://github.com/haskell/base64-bytestring/blob/master/Dat... And of course because this is C there aren't really many safety guarantees here.
The plan with Yatima with its primitives, and eventually when we write an FFI is to integrate with Rust in the same way that Haskell uses C. My hope is that with Yatima's affine types we might even be able to FFI to and from safe Rust (since the borrow checker uses affine types), but this is a little bit of a research project to see how much that works. Even to unsafe Rust though, we have better safety guarantees than C, since unsafe Rust's UB is still more restricted than C's is.
There's definitely some similarities to ATS conceptually, but not that much in the actual implementation, and definitely not in the syntax.
That said, Hongwei Xi is a genius, and ATS is one of the most important and innovative languages of the past decade, despite the crazy syntax (seriously, t@ype for the sort of flat memory types is just bonkers). I'm really looking forward to ATS3 though https://github.com/githwxi/ATS-Xanadu, and I think there's chance it could gain serious traction.
Related posts
- Yew alternatives
- [Rust] Comment construisez-vous la pile complète avec de la rouille?
- Is Rust Ready for the Web Yet?
- Recommended web-app framework for newbies and juniors?
- They interviewed the founder of a full-stack Rust framework called "MoonZoon" in this newsletter. Has anyone here used MoonZoon before?