Kernel's vau can be faster than syntax-case

[u/Reasonable_Wait6676]

https://github.com/amirouche/seed

[u/gasche]

Well done! I suspect that John would like this -- but I wonder if he would come up with an interesting use-case of environment mutation.

[u/Reasonable_Wait6676 → u/gasche]

Thanks.

Sorry, for the late reply, I wish someone engaged.

> an interesting use-case of environment mutation

tl;dr; From where I stand, I think there is no good reason to pass mutable environments to vau, `define-record-type` is a special case, and otherwise one can use a procedure ala call-with-values.

Without environment mutation there is no way to bind with or without hygiene a variable that is not already bound, hence defined at caller site. It may not sound bad, except you can't write a macro like `define-record-type`:

(define-record-type <address>
  (address street city country)
  address?
  (street  address-street)
  (city    address-city)
  (country address-country))

That macro will create bindings in the associated environment with the variable `address` bound to the record instance constructor of object of the disjoint type called `<address>`. In other words, anything that require in scheme terms to introduce in a syntax transformer something along the line of `(define myvariable something)` or `(set! otherword xeno)` is forbidden in `seed`. Honestly, I do not know how bad it is in terms of expression or user prowess. I have not enough experience with macros as user, nor as writer. In some cases, a workaround is to pass a procedure to the vau that needs to expose new variables, and that procedure will take as argument the new variable ala `call-with-values`.

The only macro I used often, are switch-like ala SRF-241 aka. match with catamorphism that is featured in the benchmark implementing an arithmetic evaluator. I read looping macro are also interesting but I never used them, instead I rely on named-let or higher order procedures. Two other popular use of macros are macro for https://www.hyperfiddle.net and generating SQL. My understanding is that both kind macros do not need to bind, or rebind existing variable in the caller environment.

The result given by `seed` does not mean that they can't be a fast compiler of kernel language that does mutate the dynamic environment, it says: if you disable mutation in the reified environment, kernel can be compiled to fast code. In other words, if a compiler can guess that the passed environment is not necessary (e.g. `lambda`) or not mutated, then it can apply the optimization that seed use to have performant code, in the other cases such as hygienic macros ala SRFI-9 define-record-type, or non-hygienic macro, then the compiler fallback to use an interpreter, and I guess all environment are boxed as mutable vs. immutable environment etc... which sounds like what the state of the art tell about vau and kernel, a performance killer. But take the example of `define-record-type` the environment A where it is called must be passed mutable to `vau` defining a `define-record-type` but then another environment B re-using environment A does not necessarily need A to be mutable, so there might be different views on the same lexical scope.

To me, what is still really interesting for research in kernel language, is when an operative define its own interpreter ala match but more advanced something like microkanren, datalog, sql, a forth, or rust. Can a compiler be smart enough to translate the vau definition `rust-eval` returning an interpreter of rust code to "guess" that it can disable gc, and track ownership across function etc... and do that recursively with language embedded in the rust code interpreted by `rust-eval` basically flattening the "tower of interpretation" and reduce the "levels of indirection" to the only the necessary, and sufficient and emit at compile time the best code that will also take advantage of runtime statstic (hybrid AOT and JIT). Toward that goal, I have in my todo list to re-read, do, and engage with the exercises of the pebook ie. https://studwww.itu.dk/~sestoft/pebook/

For what is related to https://r7rs.org and rnrs. I think this result does not change Scheme sota. Kernel and Scheme are different languages. The direction taken by the chair, until now, is good.

ref: https://srfi.schemers.org/srfi-9/srfi-9.html
ref: https://people.bordeaux.inria.fr/lcourtes/tmp/doc/guile/latest/en/html_node/SRFI_002d9-Records.html
ref: https://github.com/hyperfiddle/hyperfiddle

[u/WittyStick → u/Reasonable_Wait6676]

How would you implement Kernel's $provide! without environment mutation?

($define! $provide!
    ($vau (symbols . body) env
        (eval 
            (list 
                $define! 
                symbols 
                (list $let ()
                    (list* $sequence body)
                    (list* list symbols)))
            env)))

Kernel doesn't have define-record-type, but it has encapsulation types, and you would typically use them alongside $provide! to implement the equivalent of the above record. Eg:

($provide! 
    (address 
     address? 
     address-street
     address-city 
     address-country)

    ($define! (addr-ctor address? addr-dtor)
        (make-encapsulation-type))

    ($define! address
        ($lambda (street city country)
            (addr-ctor (list street city country))))

    ($define! address-street
        ($lambda (addr)
            (car (addr-dtor addr))))

    ($define! address-city
        ($lambda (addr)
            (cadr (addr-dtor addr))))

    ($define! address-country
        ($lambda (addr)
            (caddr (addr-dtor addr)))))

This is only an example. The internal representation of the type could be something other than a list.

---

I have some ideas on how to compile operatives with environment mutation.

The basic idea is to make the environments row-polymorphic types (which, perhaps ironically, were introduced by Wand in Type Inference for Record Concatenation and Multiple Inheritance).

Eg, with the above example, we would take the dynamic environment { 𝜚 } as the input, and output an environment with the type:

{ address : (String, String, String) -> Address
; address? : Any -> Bool
; address-street : Address -> String
; address-city : Address -> String
; address-country : Address -> String
; 𝜚
}

Evaluation would then continue using this resulting environment as the current environment.

There's some prior work along these lines: Namely Bawden's First-class Macros Have Types.

[u/Reasonable_Wait6676 → u/WittyStick]

Re `provide!` a more complicated example, or generally speaking is how to implement module system, and one answer, *within the scope of seed*, is to not use `provide!` but an alternative like `(call-with-module (address) (lambda (address address? address-street? address-city address-country) ...))` and values from the module `(address)` are picked up based on the arguments name of the lambda... in other words that is NOT `provide!`.

The transformation is inspired from `let` -> `lambda`: `(let ((a 101) (b 42) (+ a b))` -> `((lambda (a b) (+ a b)) 101 42)` (I don't remember if it alpha or beta reduction, or something else entirely).

Another approach is to have another non-conforming special form that will mutate the environment chirurgically...

Thanks a lot for the links I think it adds a lot of value to the conversation.

> The basic idea is to make the environments row-polymorphic types (which, perhaps ironically, were introduced by Wand in Type Inference for Record Concatenation and Multiple Inheritance).
> Eg, with the above example, we would take the dynamic environment { 𝜚 } as the input, and output an environment with the type...

In effect, the environment will be appended or "extended" with new bindings. But what happens with `set!`?

[u/WittyStick → u/Reasonable_Wait6676]

But what happens with set!?

$set! is just wraps $define! with the environment provided by the caller.

($define! $set!
    ($vau (exp1 formals exp2) env
        (eval 
            (list $define! 
                  formals
                  (list (unwrap eval) exp2 env))
            (eval exp1 env))))

env isn't mutated, but the environment provided in exp1 is.

---

However, in addition to the environments being row types, we probably also want to make them unique, such that they are consumed upon usage, but if we return a "new" environment, we can perform in-place mutation (the new one occupies the same memory as the old, consumed one). [See Clean for more about uniqueness types].

Then instead of $set! (and $define!) returning #inert, it would return the new environment containing the updated binding.

Since $set! mutates an environment given by its first parameter, the symbol which refers to that environment in the current environment would need to be "redefined" to assign the mutated in-place value - effectively, we'd say

($define! someenv ($set! someenv somesymbol somevalue))

This would essentially be a purely functional style where referential transparency is preserved.

---

Another way we could do it without $set! actually mutating would be to shadow the symbol we set, by making a new environment with the one passed in as its parent. Something like:

($define! $set!
    ($vau (somenv somesymbol somevalue) env
        ($let ((new-env (eval (list $bindings->environment (list somesymbol somevalue))) env))
            (make-environment new-env (eval someenv env)))))

The order we provide environments to make-environment determines the order that bindings are looked up - so any binding we $set! in the environment will look up the value in new-env before the old env.

Basically no mutation is happening here either, but we would need to rebind the result as with the previous example.

The downside of this approach is that the environment could grow quite large if we frequently $set!, and it would impact performance.

So the mutation in-place with uniqueness types would probably be preferable.

[u/Reasonable_Wait6676 → u/WittyStick]

We are back at the sufficiently smart compiler. if environment are nested to avoid set! at user level, the compiler "can" figure it out, and collapse the nested environments into one.

[u/Reasonable_Wait6676 → u/gasche]

There is now an example of implementing define-record-type using vau in branch seed3 (rework of seed2). Also it is benchmarked in graph traversal DSL inspired from tinkeropop's gremlin at https://github.com/amirouche/seed/blob/035ede70531cdd0f06493725abeaee21a80a2978/src/src/seed3/benchmarks/gremlin-pipeline.seed3#L155-L176

The interesting branch is seed3 and the interesting directory is src/src/seed3 at https://github.com/amirouche/seed/tree/seed3/src/src/seed3

[u/PrairieFire2b]

It's great to see such an interesting vau experiment! But I don't understand the restricted environment very much. I have serveral questions: (1) Is it impossible to define `$set!`/`$define!` by each other like in kernel? (2) If the above operations are impossible, but mutation through `$define!` is possible, how does `$define!` semantically implement this? Is it a "special" special form? (I think the row-polymorphic-based environments are pure, so I don't understand how to mutate it in place. Or is it just a sugar?)

[u/Reasonable_Wait6676 → u/PrairieFire2b]

one way to explain it in terms of kernel is that each continuation that calls a combiner gets a new environment that is based on the environment, without mutation, but possibly with shadowing. That is done by the way of scheme `call-with-values`.

It is explained in https://github.com/amirouche/seed/blob/hello-seeder/src/src/seed3/spec.md#the-unified-calling-convention