Autology: A Lisp with access to its own interpreter(github.com)
github.com
Autology: A Lisp with access to its own interpreter
https://github.com/Kimbsy/autology
55 comments
In Common Lisp, at least, it's pretty typical for the compiler or interpretter to have packages for interacting with its internals. For example, `sb-c`, `sb-vm`, and `sb-ext` packages in SBCL; and the `ccl` package with Clozure Common Lisp, etc.
That ability also shows up in the inspector - it's possible to inspect types, classes, functions, etc. and inspect the internal data structures the compiler uses to represent them.
With SBCL it's even possible to modify the "virtual ops" the compiler uses, and emit assembly code that SBCL doesn't support out of the box.
It's a really convenient feature, and it would be nice if to see other languages pick it up.
That ability also shows up in the inspector - it's possible to inspect types, classes, functions, etc. and inspect the internal data structures the compiler uses to represent them.
With SBCL it's even possible to modify the "virtual ops" the compiler uses, and emit assembly code that SBCL doesn't support out of the box.
It's a really convenient feature, and it would be nice if to see other languages pick it up.
Are there any examples?
Thank you! Looks useful.
"The Common Lisp Condition System" is a great book, by the way, thanks. :)
"The Common Lisp Condition System" is a great book, by the way, thanks. :)
Thanks! I hope it serves you well.
Here is a little code snippet for CCL that changes the compiler to accept a Scheme-like ((...) ...) syntax.
https://flownet.com/ron/lisp/combination-hook.lisp
https://flownet.com/ron/lisp/combination-hook.lisp
Thank you! If you have any SBCL-related snippets as well, let me know!
I haven't read any of the code to see how it compares, but this work reminds me of research from Nada Amin & Tiark Rompf on "towers of interpreters", where a stack of meta-circular interpreters uses some explicit staging operations that make it possible to specialize for the interpreter code in a way that removes overhead.
https://www.cs.purdue.edu/homes/rompf/papers/amin-popl18.pdf
https://www.cs.purdue.edu/homes/rompf/papers/amin-popl18.pdf
This in turn, is based on black[0] which is an extension to scheme, which in turn is inspired by [1]
[0] http://pllab.is.ocha.ac.jp/~asai/Black/
[1] https://www.lirmm.fr/~dony/enseig/MR/notes-etudes/Reflective...
[0] http://pllab.is.ocha.ac.jp/~asai/Black/
[1] https://www.lirmm.fr/~dony/enseig/MR/notes-etudes/Reflective...
There's no relationship - tower of interpreters is related to lightweight modular staging
https://dl.acm.org/doi/10.1145/1868294.1868314
This is just lisp or more broadly "I'm an interpreted language" since you know... Python has access to much of its interpreter runtime too . And if you think you can't do wild stuff in Python you can (hint: you can use ctypes on libpython to do way more than you think you can do).
https://dl.acm.org/doi/10.1145/1868294.1868314
This is just lisp or more broadly "I'm an interpreted language" since you know... Python has access to much of its interpreter runtime too . And if you think you can't do wild stuff in Python you can (hint: you can use ctypes on libpython to do way more than you think you can do).
Isn't having access to the interpreter (and scanner, and parser, and compiler) kind of what makes something Lisp rather than something else with a lot of parentheses?
Typically, Lisp is quite flexible, via macros and reader macros, but the smallest core is still fixed in function (the part that implements special forms, order of evaluation, etc., basically eval and apply). This makes even that core replaceable on a form by form basis. Interesting from a theoretical perspective but not very useful in practice, and performance killing as the author points out.
Once upon a time that was true. The original Lisp interpreter could be extended by writing new FEXPR routines, which are given their argument code as source to interpret.
In the FEXPR era, Lisp didn't have lexical scopes, so FEXPR routines did not require an environment parameter.
FEXPRs were eventually abandoned in favor of macros. That was largely due to practical reasons; Lisp people were pressuring themselves or else being pressured to make Lisp perform better. It was not because FEXPRs were exhaustively researched.
A modern treatment of FEXPRs will almost certainly be lexically scoped, so that FEXPRs will have a lexical environment parameter to pass to the recursive eval calls.
Autology makes a different choice here by passing a parameter *i* (implicitly) which is not simply the lexical environment, but an object for interpretation, which can be selectively customized. This makes a categorical difference.
It's immediately obvious to me that this allows possibilities that are impossible under FEXPRs.
Here is why: when a FEXPR recursively evaluates code, whether through the standard eval provided by the host Lisp, or its own custom evaluation routine, it will encounter invocations of other FEXPRs. And those FEXPRS are "sealed off": they are coded to invoke a certain eval and that's it.
Concretely, suppose we are writing an if operator as a FEXPR. We get the if form unevaluated, and destructure it into the pieces: condition, consequent, alternative. What our FEXPR does then is recursively call eval to evaluate the condition. If that is true, we recursively call eval to evaluate consequent, otherwise we call eval on the alternative. (In all eval calls we pass down the lexical environment we were given).
Now suppose someone is writing a FEXPR in which they want to heavily customize the Lisp dialect with their custom evaluator, custom-eval. Problem is what, happens when custom-eval sees an if form that is programmed using our if FEXPR? It just calls that FEXPR, whose body calls eval; it doesn't know that the code is in a customized dialect which requires custom-eval!
It looks as if that the approach in Autology handles (or if not, could easily handle) the situation. The FEXPR which customizes the Lisp dialect can pass down a modified interpreter via *i*. Then when interpretation encounters if, it will call the if FEXPR, and what FEXPR will use the customized interpreter on the condition, then and alternative.
Now (non-hygienic) macros can already support this, in theory. If you've written a DSL as a macro, and in that DSL you choose to expand regular macros defined in the host Lisp, at least some of them with simple behaviors like the if example will also Just Work. This is because macros don't (usually!) call eval, but generate code. That code just ends up being pasted into the expression of whatever dialect is being processed, and will therefore be interpreted as that dialect. A macro arranges for evaluation by inserting the pieces of code into the template such that they are in the right kind of syntactic context to be evaluated. For this to work across dialects, the dialects have to be similar. E.g. an if macro might rewrite to cond. If the target dialect has a sufficiently compatible cond construct, then everything is golden: the if to cond rewrite will work fine.
So how we can look at dynamic interpreter customization is that it brings one aspect of FEXPRs closer to macros. Macros can do some things that FEXPRs cannot, and vice versa.
In the FEXPR era, Lisp didn't have lexical scopes, so FEXPR routines did not require an environment parameter.
FEXPRs were eventually abandoned in favor of macros. That was largely due to practical reasons; Lisp people were pressuring themselves or else being pressured to make Lisp perform better. It was not because FEXPRs were exhaustively researched.
A modern treatment of FEXPRs will almost certainly be lexically scoped, so that FEXPRs will have a lexical environment parameter to pass to the recursive eval calls.
Autology makes a different choice here by passing a parameter *i* (implicitly) which is not simply the lexical environment, but an object for interpretation, which can be selectively customized. This makes a categorical difference.
It's immediately obvious to me that this allows possibilities that are impossible under FEXPRs.
Here is why: when a FEXPR recursively evaluates code, whether through the standard eval provided by the host Lisp, or its own custom evaluation routine, it will encounter invocations of other FEXPRs. And those FEXPRS are "sealed off": they are coded to invoke a certain eval and that's it.
Concretely, suppose we are writing an if operator as a FEXPR. We get the if form unevaluated, and destructure it into the pieces: condition, consequent, alternative. What our FEXPR does then is recursively call eval to evaluate the condition. If that is true, we recursively call eval to evaluate consequent, otherwise we call eval on the alternative. (In all eval calls we pass down the lexical environment we were given).
Now suppose someone is writing a FEXPR in which they want to heavily customize the Lisp dialect with their custom evaluator, custom-eval. Problem is what, happens when custom-eval sees an if form that is programmed using our if FEXPR? It just calls that FEXPR, whose body calls eval; it doesn't know that the code is in a customized dialect which requires custom-eval!
It looks as if that the approach in Autology handles (or if not, could easily handle) the situation. The FEXPR which customizes the Lisp dialect can pass down a modified interpreter via *i*. Then when interpretation encounters if, it will call the if FEXPR, and what FEXPR will use the customized interpreter on the condition, then and alternative.
Now (non-hygienic) macros can already support this, in theory. If you've written a DSL as a macro, and in that DSL you choose to expand regular macros defined in the host Lisp, at least some of them with simple behaviors like the if example will also Just Work. This is because macros don't (usually!) call eval, but generate code. That code just ends up being pasted into the expression of whatever dialect is being processed, and will therefore be interpreted as that dialect. A macro arranges for evaluation by inserting the pieces of code into the template such that they are in the right kind of syntactic context to be evaluated. For this to work across dialects, the dialects have to be similar. E.g. an if macro might rewrite to cond. If the target dialect has a sufficiently compatible cond construct, then everything is golden: the if to cond rewrite will work fine.
So how we can look at dynamic interpreter customization is that it brings one aspect of FEXPRs closer to macros. Macros can do some things that FEXPRs cannot, and vice versa.
Obligatory reference to John Shutt and Kernel whennever FEXPRs are mentioned.
Reified reference for contexts where this wasn't yet defined: https://web.cs.wpi.edu/~jshutt/kernel.html
Access to eval and a generic recursive data type as internal structure means the language is closed on itself, can introspect, manipulate, create more through the same means it's programmed (see norvig lispy with python [lists] instead of parens)
But eval is opaque; it implements a particular dialect and that'w what you get when you recurse into it. It looks like Autology provides a way to customize the dialect that eval will process recursively. Interpreter extensions that handle subexpressions via eval will then work in the context of the altered dialect (that being provided by a parent interpreter extension itself).
Fair point, but the usual eval core is so small that I couldn't see it being split apart, and then layering new traits can still be done (still opaque though).
You can actually get completely stupid with this in Common Lisp using something called a "Reader Macro" which lets you temporarily take complete control over the interpreter.
For example, I have this joke project that defines a DSL for fizzbuzz:
https://github.com/DanielKeogh/fizzbuzz
For example, I have this joke project that defines a DSL for fizzbuzz:
https://github.com/DanielKeogh/fizzbuzz
If you like this, you'll love Shen https://shenlanguage.org/
Since its written in Clojure which runs on the JVM why not a *jvm* variable also ;)
Lisp take on generating an embedded VM at runtime/ad hoc basis (vs. polymorphic coding)?
How would use the most recent 'trie of lisp git diffs' differ from command to do a system call fork of lisp / duplicate lisp lists / apply 'diffs' to forked system call of lisp?
Perhaps, lisp concurrency support without a system()/debugger.[1]
(humor) To bad iLisp would be confused with other brand name(s).
[1] : Evil Scheduler: Mastering Concurrency Through Interactive Debugging : http://aoli.al/blogs/deadlock-empire/
How would use the most recent 'trie of lisp git diffs' differ from command to do a system call fork of lisp / duplicate lisp lists / apply 'diffs' to forked system call of lisp?
Perhaps, lisp concurrency support without a system()/debugger.[1]
(humor) To bad iLisp would be confused with other brand name(s).
[1] : Evil Scheduler: Mastering Concurrency Through Interactive Debugging : http://aoli.al/blogs/deadlock-empire/
These "inter-lingual" examples such as https://github.com/Kimbsy/autology/blob/main/resources/examp... are pretty cool. What is the use-case of this or why would one want to do this? Just trying to bounce off ideas.
So the best thing I could come up with (assuming a theoretical perfect implementation that wasn't horribly slow and expensive) was the idea that since many languages have their own niches and categories of problems that they are best used to express/solve, you could conceivably work on a complex problem where different parts of the computation are most elegantly expressed in different languages. So having a metalanguage that allows you to switch syntax in a lexical scope would be useful!?
Highly doubtful that this benefit would outweigh the egregious complexity cost of using a language like Autology, but a fun thought experiment.
Highly doubtful that this benefit would outweigh the egregious complexity cost of using a language like Autology, but a fun thought experiment.
It is definitely worth pursuing. :)
Calling code across languages at least is very widespread. And typically requires custom, often clunky, solutions for all language pairs.
So is this like a "better FFI", in some sense of the term?
Looks like just automated FFI, putting some glue around your function and then invoking the appropriate compiler for that language.
I don't really see the difference between (with-*i* "c" foo) and a macro that expands to (with-c "foo")
I don't really see the difference between (with-*i* "c" foo) and a macro that expands to (with-c "foo")
It's awesome to see the amount of ideas you can explore with 1kloc lines of clojure!
I was working on something similar to this a while ago, but the goal of it was experimenting with what a language that could modify it's own syntax would look like. I was going to write something as basic as possible and then have example scripts on transforming the syntax to other languages. I was probably just going to do brainfuck and c in the end, but I wanted something like that to be possible. I couldn't figure out how to make a language modify a tree structure for tweaking the ast of the interpreter, but I guess lisp fits the bill there.
Mind blown when you write better language using the language itself. Why I wasted so much time in assembly?
Then you remember there are certain restrictions as regards to time travel.
[deleted]
Interesting!
Racket has the capacity to declare DSLs that are then applied at the file level, but this is even finer-grained.
Racket has the capacity to declare DSLs that are then applied at the file level, but this is even finer-grained.
I think CosmicOS had the same idea [1] to seamlessly introduce special forms without defining the implicit interpreter in advance.
[1] https://cosmicos.github.io/message.html#section18
[1] https://cosmicos.github.io/message.html#section18
What is "" and so forth? It does not even render properly here on HN after having copy pasted it from the website. Custom font or what? I will check later if no one replies.
The CosmicOS message has multiple possible encodings, including base 4 representations shown below (e.g. the message starts with 121001031211132233...). The very first page contains glyphs corresponding their compact graphic representations. I think there was some description about these, but I couldn't find them so I will just recall my understanding here. The base 4 representation uses four symbols 0--3, which are derived from textual tokens:
---
12 (0|1)+ 3 -- Names. A particular name `xxx` is only available after the `intro xxx;` declaration. Note that the name `intro` itself is the first token ever and never explicitly defined.
02 (0|1)+ 3 -- Binary numbers. Note that unary numbers used initially are encoded using a special function "unary" with ordinary binary numbers 0 (0203) and 1 (0213) as bits.
2 without preceding 0 or 1 -- Opening parenthesis.
3 without preceding 0 or 1 -- Closing parenthesis.
023 -- Auto-closing opening parenthesis, denoted `|` in the textual form. `(a | b | c d)` is same as `(a (b (c d)))`.
123 -- Single-item parentheses, denoted `$` in the textual form. `$x` means `(x)` and typically used in variable getters.
2233 -- Marks the end of the current expression. Each expression in the CosmicOS message should evaluate to true.
---
Now, keep in mind that every name is effectively a specially marked number. I think each line segment in glyphs corresponds to a particular bit position, and numbers have short overline and underline to distinguish themselves from names.
---
12 (0|1)+ 3 -- Names. A particular name `xxx` is only available after the `intro xxx;` declaration. Note that the name `intro` itself is the first token ever and never explicitly defined.
02 (0|1)+ 3 -- Binary numbers. Note that unary numbers used initially are encoded using a special function "unary" with ordinary binary numbers 0 (0203) and 1 (0213) as bits.
2 without preceding 0 or 1 -- Opening parenthesis.
3 without preceding 0 or 1 -- Closing parenthesis.
023 -- Auto-closing opening parenthesis, denoted `|` in the textual form. `(a | b | c d)` is same as `(a (b (c d)))`.
123 -- Single-item parentheses, denoted `$` in the textual form. `$x` means `(x)` and typically used in variable getters.
2233 -- Marks the end of the current expression. Each expression in the CosmicOS message should evaluate to true.
---
Now, keep in mind that every name is effectively a specially marked number. I think each line segment in glyphs corresponds to a particular bit position, and numbers have short overline and underline to distinguish themselves from names.
so it's hot code reloading on steroids? really neat idea, I'm working on a similar Lisp-style language and will probably adopt this idea (and cite you of course). In my language, you can redefine any symbol, even numbers, so (def 10 12) is valid code (so is (def def 42), which breaks `def`!).
I wonder what use cases there are for such extreme flexibility, aside from funs and games!
I wonder what use cases there are for such extreme flexibility, aside from funs and games!
Redefining 'def' is a trick used in Tcl to make "safe" configuration languages exposed to the end user. You define all of your configuration options as functions and then undefine everything else (including "proc" which corresponds to defun) allowing you to evaluate users' config files with this safe interpreter as code.
I can't find a good source for this practice of manually undefining functions, but here is a link to relevant built-in functionality: https://www.tcl-lang.org/man/tcl8.6/TclCmd/safe.htm
I can't find a good source for this practice of manually undefining functions, but here is a link to relevant built-in functionality: https://www.tcl-lang.org/man/tcl8.6/TclCmd/safe.htm
None; it's for fun and games. But maybe thats the most enjoyable use case anyway.
I couldn't agree more
Please feel free to use any/all of it, it's really fun to play around with.
reminds me a little bit of the Kernel programming language
Reminds me a lot, except that Kernel does away with "special forms".
Link for "Kernel" because it's a lousy name to have to search for: https://web.cs.wpi.edu/~jshutt/kernel.html
One interesting bit that remains unappreciated about Kernel is that environments are reified and are "copy-on-write". So, if you make an environment change, it propagates forward but previous calls only see the previous environment unless explicitly give them access.
It's a little unusual, but it works out pretty well. You can call the "ground environment" which is immutable and lets you compile things. You can access the "lexical environment" which works like normal. And you can call a "dynamic environment" that lets you capture things.
It's interesting in that it contains the scope of "dynamic environments" and still allows things to be compiled (which was the big downside of dynamic environments circa 1970s).
One downside I found is that the obvious implementation thrashes the hell out of your garbage collector. "Environments" really want a data structure that is more complicated and copy-friendly than "cons pairs".
Link for "Kernel" because it's a lousy name to have to search for: https://web.cs.wpi.edu/~jshutt/kernel.html
One interesting bit that remains unappreciated about Kernel is that environments are reified and are "copy-on-write". So, if you make an environment change, it propagates forward but previous calls only see the previous environment unless explicitly give them access.
It's a little unusual, but it works out pretty well. You can call the "ground environment" which is immutable and lets you compile things. You can access the "lexical environment" which works like normal. And you can call a "dynamic environment" that lets you capture things.
It's interesting in that it contains the scope of "dynamic environments" and still allows things to be compiled (which was the big downside of dynamic environments circa 1970s).
One downside I found is that the obvious implementation thrashes the hell out of your garbage collector. "Environments" really want a data structure that is more complicated and copy-friendly than "cons pairs".
> One interesting bit that remains unappreciated about Kernel is that environments are reified and are "copy-on-write". So, if you make an environment change, it propagates forward but previous calls only see the previous environment unless explicitly give them access.
That's not quite how it works. Environments are mutable, but only the locals of an environment that we have a direct reference to. We cannot mutate any of the bindings in the parents without a reference to the parents, and the language provides no facility to obtain references to the parents given only a reference to the child.
We can however, explicitly pass around references to parent environments if we do have access to them, because environments are first-class, and we can move around references where we want. We can have a child mutate its grandparent environment, and those changes will be visible to the child's parent - but this is only possible if the child has a direct reference to the grandparent - which it would not have under normal circumstances - it has to be provided with that reference explicitly.
We could for example, bind our top-level scope into a symbol in the top-level, such that any descendants of the top level can mutate any bindings in the top level.
Obviously, we would not do this in practice because it would let us rebind `print-x` and `foo`, or even rebind `*globals*` to some another value.
A safer way to do this would be to bind a setter for x in the top level.
This works because the outermost `$vau` on $set-x!` is evaluated in the top level, where `$set-x!` is defined, so it receives the top level environment as its dynamic environment, which it binds to the symbol `top-level` in its local environment, and then returns an operative whose static environment is its own local environment.
When `$set-x!` is called, it ignores its caller's dynamic environment, but its static environment contains the symbol `top-level`, bound to the top level environment.
---
The immutable part of environments is the list of parents that any environment has. When we create an environment through say `(make-environment list-of-parents)`, the environment creates an immutable copy of the list of parents, which prevents whoever created the environment from being able to modify this list later. For example, we wouldn't want this
However, the creator of this list can mutate the bindings in the parent after creating the env.
But usually it will be the case that `some-environment` is encapsulated by the creator who will eventually return `env`, but no reference to `some-environment` - which will prevent any mutation of the bindings in the parents.
---
There is no way to mutate the ground environment because every standard-environment is a child of the ground, but with no direct reference to the ground. The ground is just its parent. The definition of `make-kernel-standard-environment` is interesting, because it's just
Although Kernel is specified using mutable environments, the Kernel report does make them optional. It doesn't really go into depth about how one would implement Kernel with immutable environments besides a brief note.
If you do have immutable environments, then a fun challenge is how you would implement `make-kernel-standard-environment`. If using the definition above, then the environment returned by the call to `make-kernel-standard-environment` notably does not have the binding `make-kernel-standard-environment` in it (because the binding happens after).
That's not quite how it works. Environments are mutable, but only the locals of an environment that we have a direct reference to. We cannot mutate any of the bindings in the parents without a reference to the parents, and the language provides no facility to obtain references to the parents given only a reference to the child.
We can however, explicitly pass around references to parent environments if we do have access to them, because environments are first-class, and we can move around references where we want. We can have a child mutate its grandparent environment, and those changes will be visible to the child's parent - but this is only possible if the child has a direct reference to the grandparent - which it would not have under normal circumstances - it has to be provided with that reference explicitly.
We could for example, bind our top-level scope into a symbol in the top-level, such that any descendants of the top level can mutate any bindings in the top level.
($define! *globals* (get-current-environment))
($define! x 0)
($define! print-x
($lambda () (write x)))
($define! foo
($lambda ()
($set! *globals* x 1)))
(foo)
(print-x)
Obviously, we would not do this in practice because it would let us rebind `print-x` and `foo`, or even rebind `*globals*` to some another value.
A safer way to do this would be to bind a setter for x in the top level.
($define! x 0)
($define! $set-x!
(($vau () top-level
($vau (value) #ignore
($set! top-level x value)))))
($define! print-x
($lambda () (write x)))
($define! foo
($lambda ()
($set-x! 1)))
(foo)
(print-x)
This works because the outermost `$vau` on $set-x!` is evaluated in the top level, where `$set-x!` is defined, so it receives the top level environment as its dynamic environment, which it binds to the symbol `top-level` in its local environment, and then returns an operative whose static environment is its own local environment.
When `$set-x!` is called, it ignores its caller's dynamic environment, but its static environment contains the symbol `top-level`, bound to the top level environment.
---
The immutable part of environments is the list of parents that any environment has. When we create an environment through say `(make-environment list-of-parents)`, the environment creates an immutable copy of the list of parents, which prevents whoever created the environment from being able to modify this list later. For example, we wouldn't want this
($define! parents (list some-environment))
($define! env (make-environment parents))
($set-car! parents some-other-environment)
However, the creator of this list can mutate the bindings in the parent after creating the env.
($define! parents (list some-environment))
($define! env (make-environment parents))
($set! some-environment some-binding some-value)
But usually it will be the case that `some-environment` is encapsulated by the creator who will eventually return `env`, but no reference to `some-environment` - which will prevent any mutation of the bindings in the parents.
---
There is no way to mutate the ground environment because every standard-environment is a child of the ground, but with no direct reference to the ground. The ground is just its parent. The definition of `make-kernel-standard-environment` is interesting, because it's just
($define! make-kernel-standard-environment
($lambda () (get-current-environment)))
Although Kernel is specified using mutable environments, the Kernel report does make them optional. It doesn't really go into depth about how one would implement Kernel with immutable environments besides a brief note.
If you do have immutable environments, then a fun challenge is how you would implement `make-kernel-standard-environment`. If using the definition above, then the environment returned by the call to `make-kernel-standard-environment` notably does not have the binding `make-kernel-standard-environment` in it (because the binding happens after).
How did you resolve all this? When I implemented Kernel, this was one of my big sticking points as to whether environments were only copy-on-write or genuinely mutable.
Section 4.3.1 and Fig 4.1 from his thesis doesn't really help clear this up much.
> Although Kernel is specified using mutable environments, the Kernel report does make them optional. It doesn't really go into depth about how one would implement Kernel with immutable environments besides a brief note.
Thanks. I must have missed that. I'll go look again at some point.
Part of the problem I had was that the environment handling was cons-ing up a lot of garbage. I really needed some way to default everything to "ground environment" to prevent the creation of a new environments all over the place.
Section 4.3.1 and Fig 4.1 from his thesis doesn't really help clear this up much.
> Although Kernel is specified using mutable environments, the Kernel report does make them optional. It doesn't really go into depth about how one would implement Kernel with immutable environments besides a brief note.
Thanks. I must have missed that. I'll go look again at some point.
Part of the problem I had was that the environment handling was cons-ing up a lot of garbage. I really needed some way to default everything to "ground environment" to prevent the creation of a new environments all over the place.
> How did you resolve all this? When I implemented Kernel, this was one of my big sticking points as to whether environments were only copy-on-write or genuinely mutable.
I must have read the Kernel report several dozen times, implemented it a few times (both with and without mutation), and tested against other implementations - most often klisp, because it's the most complete.
There is some wording in it which makes you question whether bindings in parents can be mutated, but it's not explicitly stated that this should not be the case. There are suggestions that it should be.
We know that ground or any of it's ancestors are not meant to be mutated, as per Section 3.2
> Implementations are expressly forbidden to provide any means by which a Kernel program could capture or attempt to mutate any improper ancestor of the ground environment.
Most of the details about environments are in Section 4.8:
> Changing the set of bindings of an environment, or setting the referent of the reference in a binding, is a mutation of the environment. (Changing the parent list, or a referent in the list, would be a mutation of the environment too, but there is no facility provided to do it.)
As mentioned in my previous reply, the list of parents (and the references in that list) are the immutable parts. This doesn't say we can't mutate bindings in the parent - only that we can't mutate the ancestry.
> The Kernel data type environment is encapsulated. Among other things, there is no facility provided for enumerating all the variables exhibited by an environment, and no facility for identifying the parents of an environment.
This confirms that there's no way of capturing references to parents given we only have a reference to a child.
> In particular, whenever a combiner is called, it has the opportunity, in principle, to mutate the dynamic environment in which it was called. This power is balanced by omitting any general facility for determining the parents of a given environment, and also omitting any other general facility for mutating the parents, or other ancestors, of a given environment.
This is one of the confusing parts - but it doesn't say we can't mutate bindings in ancestors - only that there's no general facility to do it. Presumably, Shutt is referring to having no facility to mutate bindings in the parents if we only have a reference to the child.
> The (second-class) Scheme operative set! allows Scheme code to modify any binding that is visible, regardless of whether or not the binding is local. Binding mutation in Kernel is more controlled, because the environment mutators can only affect capturable environments — $set! mutates an environment captured by the client, while equipowerful primitive $define! does the capturing itself. Encapsulation of the environment type allows ancestor environments to be visible without being capturable, making them effectively read-only.
Similar to the previous one, he is comparing Kernel's $set! to Scheme's set! to indicate that $set! can only mutate the locals of a captured environment. (Ie, that the parent bindings are effectively read-only, given our only reference is the encapsulated child environment).
The main hint that he intended it to be possible is in the rational of $provide!
> When more than one combiner is exported to the surrounding environment, it would be technically possible to locally capture the surrounding environment and use $set! for the exportation:
---
> Thanks. I must have missed that. I'll go look again at some point.
All of the sections on mutability are marked (optional) in their headings!
In Section 4.9 he gives a brief note about the optionality, but doesn't dive deep on how to implement it.
> It isn’t clear to what extent one can do serious Kernel programming without mutating environments; but separating the mutators into an optional module allows language implementors to explore this question within the bounds of Kernel specified by this report. In the absence of environment mutators as such, the programmer would presumably fall back on Kernel’s rich vocabulary of environment constructors (notably the $let family), which the report does not class as mutators, although environment initialization is routinely described in terms of adding bindings.
> Per §3.4, language extensions are judged against features described in the report rather than against features actually supported by the extending implementation; so, failure to support features in the Environment mutation module as a whole does not prevent a non-comprehensive implementation from providing alternative means for doing some of the same things
My experience with implementing Kernel without mutation is that it's probably better to give up following the report to the word, but we can get something almost equivalent by taking some liberties. The main liberty I took was to modify the evaluator so that it returns an environment along with the value, and this environment is used for evaluation of the next expression. A $define operative (note the absence of !) creates a child of the current environment and binds its symbols into this new child, which becomes the new current environment. This can avoid the need for defining the entire ground in $letrec* and having the user-program be run in its body.
Special care needs to be taken for recursion when not having mutability, because the examples of recursion in the Kernel report have a subtle dependency on mutation of the environment - namely, they reference a binding which does not exist yet, but by the time the recursive function is defined and bound, it now exists in the static environment.
This itself is another hint that bindings in parents aught to be mutable - without this, recursion as used in the Kernel report would not work. Consider one of the trivial examples of recursion in the report.
If the environment were not mutable, when the recursive call to $or? is made, it would look up the immutable copy of ground it took as it's static environment, which does not contain $or?
But clearly, this recursion is intended to work, so $or? must be available in the static environment when the recursive call is made - so a mutation of the ground was made that the body of the $or? operative is witness to, even though it is in a child of ground.
This is related to my previous point about `make-kernel-standard-environment`. Without mutability, it's bizarre, because it exports a standard environment without the `make-kernel-standard-environment` binding in it yet. To do this without mutating the environment, we could try to define it twice:
A proper solution needs to use a combination of $vau, $letrec, $bindings->environment and make-environment.
$letrec* itself probably needs to be primitive without mutation. I'm not sure how you could implement it without $define! or without already having a $letrec equivalent. Maybe some clever trick with $vau.
---
> Part of the problem I had was that the environment handling was cons-ing up a lot of garbage. I really needed some way to default everything to "ground environment" to prevent the creation of a new environments all over the place.
I don't think you can really prevent the creation of new environments in Kernel. It's pretty explicit in the definition of $vau that a new environment is created to hold the locals, and that its parent is the static environment where the $vau expression was called.
Perhaps one thing that could improve the way ground bindings are accessed would be to generalize the idea behind the `keyed-static-variable` feature, but apply it to all ground bindings too. Basically, have a kind of "key environment" type, whose bindings cannot be shadowed in child environments, and have the ground environment be one such key environment. This approach could speed up symbol lookup for ground symbols, because currently they're at the bottom of a depth-first search. If they were not shadowable, they could be searched before non-key symbols. However, this is diverging a fair bit from the Kernel spec.
I must have read the Kernel report several dozen times, implemented it a few times (both with and without mutation), and tested against other implementations - most often klisp, because it's the most complete.
There is some wording in it which makes you question whether bindings in parents can be mutated, but it's not explicitly stated that this should not be the case. There are suggestions that it should be.
We know that ground or any of it's ancestors are not meant to be mutated, as per Section 3.2
> Implementations are expressly forbidden to provide any means by which a Kernel program could capture or attempt to mutate any improper ancestor of the ground environment.
Most of the details about environments are in Section 4.8:
> Changing the set of bindings of an environment, or setting the referent of the reference in a binding, is a mutation of the environment. (Changing the parent list, or a referent in the list, would be a mutation of the environment too, but there is no facility provided to do it.)
As mentioned in my previous reply, the list of parents (and the references in that list) are the immutable parts. This doesn't say we can't mutate bindings in the parent - only that we can't mutate the ancestry.
> The Kernel data type environment is encapsulated. Among other things, there is no facility provided for enumerating all the variables exhibited by an environment, and no facility for identifying the parents of an environment.
This confirms that there's no way of capturing references to parents given we only have a reference to a child.
> In particular, whenever a combiner is called, it has the opportunity, in principle, to mutate the dynamic environment in which it was called. This power is balanced by omitting any general facility for determining the parents of a given environment, and also omitting any other general facility for mutating the parents, or other ancestors, of a given environment.
This is one of the confusing parts - but it doesn't say we can't mutate bindings in ancestors - only that there's no general facility to do it. Presumably, Shutt is referring to having no facility to mutate bindings in the parents if we only have a reference to the child.
> The (second-class) Scheme operative set! allows Scheme code to modify any binding that is visible, regardless of whether or not the binding is local. Binding mutation in Kernel is more controlled, because the environment mutators can only affect capturable environments — $set! mutates an environment captured by the client, while equipowerful primitive $define! does the capturing itself. Encapsulation of the environment type allows ancestor environments to be visible without being capturable, making them effectively read-only.
Similar to the previous one, he is comparing Kernel's $set! to Scheme's set! to indicate that $set! can only mutate the locals of a captured environment. (Ie, that the parent bindings are effectively read-only, given our only reference is the encapsulated child environment).
The main hint that he intended it to be possible is in the rational of $provide!
> When more than one combiner is exported to the surrounding environment, it would be technically possible to locally capture the surrounding environment and use $set! for the exportation:
($let ((outside (get-current-environment)))
...
($set! outside (foo bar quux) (list foo bar quux)))
---
> Thanks. I must have missed that. I'll go look again at some point.
All of the sections on mutability are marked (optional) in their headings!
In Section 4.9 he gives a brief note about the optionality, but doesn't dive deep on how to implement it.
> It isn’t clear to what extent one can do serious Kernel programming without mutating environments; but separating the mutators into an optional module allows language implementors to explore this question within the bounds of Kernel specified by this report. In the absence of environment mutators as such, the programmer would presumably fall back on Kernel’s rich vocabulary of environment constructors (notably the $let family), which the report does not class as mutators, although environment initialization is routinely described in terms of adding bindings.
> Per §3.4, language extensions are judged against features described in the report rather than against features actually supported by the extending implementation; so, failure to support features in the Environment mutation module as a whole does not prevent a non-comprehensive implementation from providing alternative means for doing some of the same things
My experience with implementing Kernel without mutation is that it's probably better to give up following the report to the word, but we can get something almost equivalent by taking some liberties. The main liberty I took was to modify the evaluator so that it returns an environment along with the value, and this environment is used for evaluation of the next expression. A $define operative (note the absence of !) creates a child of the current environment and binds its symbols into this new child, which becomes the new current environment. This can avoid the need for defining the entire ground in $letrec* and having the user-program be run in its body.
Special care needs to be taken for recursion when not having mutability, because the examples of recursion in the Kernel report have a subtle dependency on mutation of the environment - namely, they reference a binding which does not exist yet, but by the time the recursive function is defined and bound, it now exists in the static environment.
This itself is another hint that bindings in parents aught to be mutable - without this, recursion as used in the Kernel report would not work. Consider one of the trivial examples of recursion in the report.
($define! $or?
($vau x e
($cond ((null? x) #f)
((null? (cdr x)) (eval (car x) e))
((eval (car x) e) #t)
(#t (apply (wrap $or?) (cdr x) e))))) ; recursive call
If the environment were not mutable, when the recursive call to $or? is made, it would look up the immutable copy of ground it took as it's static environment, which does not contain $or?
But clearly, this recursion is intended to work, so $or? must be available in the static environment when the recursive call is made - so a mutation of the ground was made that the body of the $or? operative is witness to, even though it is in a child of ground.
This is related to my previous point about `make-kernel-standard-environment`. Without mutability, it's bizarre, because it exports a standard environment without the `make-kernel-standard-environment` binding in it yet. To do this without mutating the environment, we could try to define it twice:
($letrec* ((...all other ground bindings...)
(make-kernel-standard-environment ($lambda () (get-current-environment))
(make-kernel-standard-environment ($lambda () (get-current-environment)))
A proper solution needs to use a combination of $vau, $letrec, $bindings->environment and make-environment.
($letrec* ((...all other ground bindings...)
(make-kernel-standard-environment ;; must be the final binding in ground.
((wrap
($vau () e
($letrec ((make-kernel-standard-environment
($lambda ()
(make-environment
($bindings->environment
(make-kernel-standard-environment
make-kernel-standard-environment))
e))))
(get-current-environment))))))))
$letrec* itself probably needs to be primitive without mutation. I'm not sure how you could implement it without $define! or without already having a $letrec equivalent. Maybe some clever trick with $vau.
---
> Part of the problem I had was that the environment handling was cons-ing up a lot of garbage. I really needed some way to default everything to "ground environment" to prevent the creation of a new environments all over the place.
I don't think you can really prevent the creation of new environments in Kernel. It's pretty explicit in the definition of $vau that a new environment is created to hold the locals, and that its parent is the static environment where the $vau expression was called.
Perhaps one thing that could improve the way ground bindings are accessed would be to generalize the idea behind the `keyed-static-variable` feature, but apply it to all ground bindings too. Basically, have a kind of "key environment" type, whose bindings cannot be shadowed in child environments, and have the ground environment be one such key environment. This approach could speed up symbol lookup for ground symbols, because currently they're at the bottom of a depth-first search. If they were not shadowable, they could be searched before non-key symbols. However, this is diverging a fair bit from the Kernel spec.
Thanks for taking the time to write up such a detailed response.
I'm giving a talk on this in May for London Clojurians, and I'll also be talking about it at Lambda Days in Krakow in June.
https://www.meetup.com/london-clojurians/events/306843409/
The project was initially inspired by Dr John Sturdy's thesis "A Lisp through the Looking Glass" which is all about interpreter towers and the ability to modify them in both directions.
This is all just for fun, I've yet to think of anything truly useful you can do with this. If you have any cool ideas please let me know, they might even make it into my talk!