Re: Semantics of circular imports

[Philip McGrath]

Hi,

(Apparently I wrote this a month ago but left it sitting in "Drafts" ...)

On 2/20/22 12:47, Maxime Devos wrote:
> Philip McGrath schreef op zo 20-02-2022 om 11:47 [-0500]:
>> I was just (or maybe am still?) dealing with some issues caused by cyclic
>> imports of package modules while updating Racket to 8.4: see in particular
>> <https://issues.guix.gnu.org/53878#93>, as well as #66, #112, and #113 in the
>> same thread.
>> [...]
>> I find the semantics of Guile's cyclic module imports very confusing,
>> and I don't know of any documentation for what is and isn't supported
>> other than advice from Ludo’ in <https://issues.guix.gnu.org/48682#7
>> —is there any?
> 
> (The following explanation ignores syntax transformers, #:select and
> #:autoload.)
> 
> Basically, a module consists of a hash table and a thunk
> initialising the hash table.  A few situations to demonstrate:
> 
> ;; Non-cyclic
> (define-module (foo)
>    #:export (foo))
> (define foo 0)
> 
> (define-module (bar)
>    #:export (bar)
>    #:use-module (foo))
> (define bar (+ 1 foo))
> 
> The thunk of 'foo' would be
> 
>    (lambda ()
>      (set-module-value! '(foo) 'foo 0))
> 
> and the thunk of 'bar' would be
> 
>    (lambda ()
>      ;; This calls the thunk of 'foo' if it hasn't yet been called
>      ;; before.
>      (initialise-module '(foo))
>      (set-module-value! '(bar) 'bar (+ 1 (module-value '(foo) 'foo 0))))
> 
> ;; Cyclic, non-problematic
> (define-module (foo)
>    #:export (foo)
>    #:use-module (bar))
> (define foo 0)
> (define (calculate-foobar)
>    (+ 1 (calculate-bar))
> 
> (define-module (bar)
>    #:export (calculate-bar)
>    #:use-module (foo))
> (define (calculate-bar) (+ 1 foo))
> 
> The initialisation thunk of 'foo' would be
> 
>   (lambda ()
>     (initialise-module '(bar))  ; L1
>     (set-module-value! '(foo) 0) ; L2
>     (set-module-value! '(foo) 'calculate-foobar ; L3
>       (lambda () (+ 1 ((module-value '(bar) 'calculate-bar)))))) ; L4
> 
> and the thunk of 'bar' is:
> 
>    (lambda ()
>      (initialise-module '(foo)) ; L6
>      (set-module-value! '(bar) 'calculate-bar ; L7
>        (lambda () (+ 1 (module-value '(foo) 'foo))))) ; L8
> 
> Now let's see what happens if the module (bar) is loaded:
> 
> ; Initialising '(bar)'
> (initialise-module '(foo)) ; L6
>     ;; (foo) has not yet begun initialisation, so run the thunk:
>     ->  (initialise-module '(bar)) ; L1
>         ;; (bar) is being initialised, so don't do anything here
>     -> (set-module-value! '(foo) 0) ; L2
>     -> (set-module-value! '(foo) 'calculate-foobar ; L3
>          (lambda () (+1 ((module-value '(bar) 'calculate-bar)))) ; L4
> 
>        The hash table of '(bar)' does not yet contain 'calculate-bar',
>        but that's not a problem because the procedure 'calculate-foobar'
>        is not yet run.
> (set-module-value! '(bar) '(calculate-bar) ; L7
>    (lambda () (+ 1 (module-value '(foo) 'foo)))) ; L8
> ;; The hash table of '(foo)' contains 'foo', so no problem!
> ;; Alternatively, even if '(foo)' did not contain 'foo',
> ;; the procedure '(calculate-bar)' is not yet run, so no problem!

Oh, wow. I definitely had not realized that, *even inside a declarative 
module*, a reference to a variable with no statically visible definition 
would semantically be a dynamic lookup in a mutable environment at 
runtime (rather than a compile-time error), though I do see now that 
`info guile declarative` does indeed say that marking a module as 
declarative "applies only to the subset of top-level definitions that 
are themselves declarative: those that are defined within the 
compilation unit, and not assigned (‘set!’) or redefined within the 
compilation unit."

Does this mean that Guile treats all imported bindings as non-declarative?
This seems like a big barrier to cross-module inlining, though IIUC Guile
currently doesn't do much of that by default (maybe for this reason).

The use of "top-level" to refer to definitions within a module is 
somewhat confusing to me. I usually understand "top-level" to refer to 
the kind of interactive REPL environment for which R6RS leaves the 
semantics unspecified. Racket uses "module-level variable"  and "module 
context" in contrast to "top-level variable" and "top-level context" to
make this distinction.[1][2][3] (There are also R6RS "top-level 
programs", but I wouldn't think of those unless made very clear from 
context.)

(Also, what is a "compilation unit" in Guile? Is it ever something other 
than a single module corresponding to a single file (potentially using 
`include` to incorporate other files at expand time?)

> 
> ;; Done!
> 
> Now for a problematic import cycle:
> 
> (define-module (foo)
>    #:export (foo)
>    #:use-module (bar))
> (define foo (+ 1 bar))
> 
> (define-module (bar)
>    #:export (bar)
>    #:use-module (foo))
> (define bar (+ 1 foo))
> 
> Now let's reason what happens when we try importing 'bar'.
> The init thunk of '(foo)' is:
> 
>    (lambda ()
>      (initialise-module '(bar)) ; L1
>      (set-module-value! '(foo) 'foo (+ 1 (module-value '(bar) 'bar)))) ; L2
> 
> and the thunk of '(bar)':
> 
>    (lambda ()
>      (initialise-module '(foo)) ; L3
>      (set-module-value! '(bar) 'bar (+ 1 (module-value '(foo) 'foo)))) ; L4
> 
> Now let's see what happens if 'bar' is loaded:
> 
> ; Initialising (bar)
> (initialise-module! '(foo)) ; L3
>    ;; (foo) has not yet begun initialisation, so run the thunk:
>    -> (initialise-module '(bar)) ; L1
>       ;; (bar) is already initialising, so don't do anything
>    -> (set-module-value! '(foo) 'foo (+ 1 bar)))
> 
>       Oops, the variable foo of the module (foo) has not yet been defined,
>       so an 'unbound-variable' exception is raised!


In the context of Racket or R6RS modules, where the semantics are 
essentially those of `letrec*`, I'm used to distinguishing "unbound" variables
from "undefined" variables, two types of errors, though informally "defined"
is often used more loosely: 

  1. Every variable reference must refer to a lexically visible binding, or
     it is an "unbound" variable error. Inherently, this can *always* be
     detected statically at compile time.

  2. A variable may not be accessed until it has been initialized. (More
     precisely, we could discuss a variable's "location", which I see is
     part of Guile's model.) This is the essence of the `letrec`/`letrec*`
     restriction: while the "fixing letrec" papers[4][5] show that useful
     static analysis can be done, this is fundamentally a dynamic property.
     Violating the restriction is an "undefined" variable error at runtime.

> 
> I hope that illustrates a little when and when not cyclic imports work!

This helped quite a bit with avoiding problems in practice---thanks!

I think there are two aspects I still feel uncertain about:

First, it is not clear to me why there was a dependency between
(gnu packages chez) and (gnu packages racket) prior to the change that
prompted me to ask this. Given what Ludo’ wrote in
<https://issues.guix.gnu.org/48682#7>:

> > Do you have any advice on what would be good practice?
> 
> For package modules, the main things are:
>   1. Don’t use #:select or #:autoload for (gnu packages …) modules in a
>      (gnu packages …) module.
>   2. At the top level of a module, only refer to variables within that
>      module.

it sounds like maybe there's some kind of implicit cycle involving---most?
all?---(gnu packages …) modules. Is that true?

Second, Guile's semantics being what they are, is it considered good practice
to take advantage of this dynamic variable resolution and tolerance for cyclic
modules? My personal taste (you may not be surprised to hear) is to prefer
more static semantics and handling cycles explicitly when they are truly
necessary. But if this is a pervasive idiom in Guile, I can try to write with
less of a Racket "accent".

Thanks again for this detailed explanation!

-Philip

[1]: 
https://docs.racket-lang.org/reference/eval-model.html#%28part._vars-and-locs%29
[2]: 
https://docs.racket-lang.org/reference/eval-model.html#%28part._module-eval-model%29
[3]: 
https://docs.racket-lang.org/reference/syntax-model.html#%28part._expand-context-model%29
[4]:
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.441.8816&rep=rep1&type=pdf
[5]:
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.420&rep=rep1&type=pdf

signature.asc
Description: This is a digitally signed message part.