4 ms·
My current side project is an implementation of a Clojure like language greatly inspired by and built similarly to Kernel. Absolutely everything user accessibl
by reitzensteinm 6y ago
My current side project is an implementation of a Clojure like language greatly inspired by and built similarly to Kernel.
Absolutely everything user accessible is a first class immutable closure that takes two objects, for arguments and calling environment.
If your object has been sent a message, you need to inspect it - by sending the message a message! Then maybe the message messages the environment to evaluate your message, which...
The turtles all the way down dependency is handled by equality testing being short circuited in the case of a pointer compare. If you (msg* my-list [:first]), my-list will message [:first] its own [:first] to inspect it. But if you send it the interned [:first] message, it'll recognize it implicitly.
This is, as you can imagine, absolutely horrendously slow - as the Kernel inventor found their own implementation to be. The core.clj file [1], which basically implements fn, destructuring let and cond, takes twenty seconds and 88 million function calls to execute.
However, the simplicity of evaluation (there aren't even local variables built in) and pervasive immutability means you get partial evaluation almost for free. Running in partial mode, eval evaluates what expressions it can and returns simplified code containing the unbound variables.
E.g. where x is unbound and y is 2, (+ (+ 1 y) x) => (+ 3 x)
You can partially evaluate multiple times as more arguments are known. In theory this allows you to elide all of the boilerplate when compiling. I'm working on the compiler now.
You can also cache whatever you want by writing it to disk, even if it closes over its environment. Every result is written and read to enforce that this works.
The initial objects are written in a bootstrap language (js). The goal is to keep that under 1k lines, although it could probably be half that. Then Clojure-like is bootstrapped, although not cleanly. Then the compiler is written in Clojure, which lets you JIT to js and get sane performance. I also have a C version using tcc, but it's harder to develop and significantly lags the js version.
It's been pretty interesting, although I struggle to see any practical uses. Writing code in a language with the clean mental model of something like the SICP metacircular evaluator is a joy.
[1] https://gist.github.com/reitzensteinm/d95d13609f6d6fd96291332b5dc1247d https://gist.github.com/reitzensteinm/d95d13609f6d6fd9629133...
- QuesnayJr 6y agoI didn't realize that Kernel ends up being necessarily very slow. Can you give a quick explanation of why?
- reitzensteinm 6y agoBecause everything is a fexpr, with lambda built on top of it, when you call a function you're not passing it values, you're passing it code and a first class environment to use to execute it. Further, because macro like features are first class, they're executed each time they're used as opposed to generating code. I believe there are decent implementations but I bet they put a fair amount of work in to making them fast. The naive reference implementation is extremely slow. While my toy project is a bit different and probably even more wasteful (with a list calling convention and immutability), it faces similar challenges. Take a read through core.clj and try to spot where the 88 million function calls are spent.
- mst 6y agoYah, my kernel-like thing ... oh gods the number of reductions. lambda (wrap) basically has to be VM provided code, and that's just the start. But for sheer flexibility it's beautiful and I don't feel like giving up yet :)
- sparkie 6y agoklisp is quite efficient (though still slow compared to other Lisps). Bronze-age-lisp optimizes some of the most critical parts in assembly language. This is probably the fastest Kernel you will find. Some details on the design were published in 4 posts to this group: https://groups.google.com/g/klisp https://groups.google.com/g/klisp
- mst 6y agoA naive implementation has to do a ridiculous number of scope lookups, even before you get to anything else. Also instead of compile time macros, one has runtime fexprs, which means the equivalent of macro expansion happens every invocation. However, one can have kernel style semantics with at least moderately reasonable performance by basically applying a combination of constant folding and expansion caching. It's a bunch of extra effort though, and non-trivial to make work, though I'm currently experimenting myself with something where I'm willing to do that. A key part is to be able to recognise fexprs that are 'really' just macros and pre-expand them and cache the expansion - without at least that you're screwed. I'm also experimenting with what else I can cache given the principle that everything is a lexical environment. I'm rather enjoying myself ... but understand the risks.