> 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:

    ($let ((outside (get-current-environment)))
        ...
        ($set! outside (foo bar quux) (list foo bar quux)))

> but this would be bad style because the local binding of outside is visible to everything in the local block, granting power to mutate the surrounding environment to everything in the local environment, and therefore (probably) to anything that captures a descendent of the local environment.

---

> 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

Here $vau captures ground as its static environment - but at the point this capture occurs, $or? does not exist in the ground environment. The $vau combination is first evaluated, and then the resulting operative is bound to $or?

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)))

But even this is problematic. When we first call to `make-kernel-standard-environment` in the body of this $letrec*, it returns an environment which contains `make-kernel-standard-environment` - but if we call `make-kernel-standard-environment` on that environment, it returns an environment which doesn't contain it.

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))))))))

It could be done also using $let-redirect instead of $bindings->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.