all messages for Guix-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Philip McGrath <philip@philipmcgrath.com>
To: Maxime Devos <maximedevos@telenet.be>,
	Ekaitz Zarraga <ekaitz@elenq.tech>,
	Ricardo Wurmus <rekado@elephly.net>,
	guix-devel@gnu.org
Cc: Liliana Marie Prikler <liliana.prikler@ist.tugraz.at>
Subject: Re: Semantics of circular imports
Date: Sun, 27 Mar 2022 10:12:25 -0400	[thread overview]
Message-ID: <3493949.dX3coAEF3O@bastet> (raw)
In-Reply-To: <a3e7d1981fbd45cc658db98281be97d0ca2ea51f.camel@telenet.be>

[-- Attachment #1: Type: text/plain, Size: 8644 bytes --]

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

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

  reply	other threads:[~2022-03-27 14:13 UTC|newest]

Thread overview: 59+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-02-20 10:05 Excessively energy-consuming software considered malware? Maxime Devos
2022-02-20 10:48 ` Tobias Platen
2022-02-20 11:13   ` Martin Becze
2022-02-20 16:52     ` Maxime Devos
2022-02-20 20:39       ` Martin Becze
2022-02-24  9:23         ` Hartmut Goebel
2022-02-24 11:18           ` Martin Becze
2022-02-25  0:27             ` Christine Lemmer-Webber
2022-02-25 12:41               ` Bengt Richter
2022-02-25 13:04                 ` Tobias Geerinckx-Rice
2022-02-25 16:14                   ` Bengt Richter
2022-02-25 16:32                     ` Ricardo Wurmus
2022-02-25 16:49                     ` Paul Jewell
2022-02-25 17:05                 ` Maxime Devos
2022-02-25 17:35                   ` Taylan Kammer
2022-02-25 19:00                     ` Leo Famulari
2022-04-04  8:00           ` Attila Lendvai
2022-04-04  9:43             ` Maxime Devos
2022-04-04 10:15             ` Maxime Devos
2022-04-04 12:49               ` Attila Lendvai
2022-04-04 10:16             ` Maxime Devos
2022-04-04 10:37             ` Maxime Devos
2022-04-04 11:22             ` indieterminacy
2022-04-04 18:39             ` Liliana Marie Prikler
2022-02-24  9:13       ` Hartmut Goebel
2022-02-24  9:36         ` Attila Lendvai
2022-02-20 11:08 ` Ekaitz Zarraga
2022-02-20 11:27   ` Compiling blender Ricardo Wurmus
2022-02-20 11:34     ` Ekaitz Zarraga
2022-02-20 12:19       ` Faster "guix pull" by incremental compilation and non-circular modules? Maxime Devos
2022-02-20 16:47         ` Philip McGrath
2022-02-20 17:47           ` Semantics of circular imports Maxime Devos
2022-03-27 14:12             ` Philip McGrath [this message]
2022-03-27 14:19               ` Maxime Devos
2022-03-27 14:24               ` Maxime Devos
2022-03-27 14:33               ` Maxime Devos
2022-03-27 14:55               ` Maxime Devos
2022-03-28  4:24               ` Zhu Zihao
2022-03-30  4:50                 ` Maxim Cournoyer
2022-02-28 13:17         ` Faster "guix pull" by incremental compilation and non-circular modules? Ludovic Courtès
2022-02-28 18:50           ` Maxime Devos
2022-05-31  4:54             ` Gábor Boskovits
2022-05-31  8:49               ` Maxime Devos
2022-05-31 10:23                 ` Ricardo Wurmus
2022-02-20 15:54       ` Compiling blender Ricardo Wurmus
2022-02-20 16:14         ` Ekaitz Zarraga
2022-02-20 12:20 ` Excessively energy-consuming software considered malware? Taylan Kammer
2022-02-20 12:37   ` Maxime Devos
2022-02-20 12:44     ` Taylan Kammer
2022-02-20 14:59       ` Philip McGrath
2022-02-20 18:53   ` Christine Lemmer-Webber
2022-02-20 20:34   ` Jonathan McHugh
2022-02-20 12:32 ` Paul Jewell
2022-02-20 18:26 ` Liliana Marie Prikler
2022-02-20 19:36 ` Ryan Sundberg
2022-02-21  9:29 ` Attila Lendvai
2022-02-21 13:06   ` Maxime Devos
2022-02-21 18:56     ` raingloom
2022-02-21 23:02     ` Attila Lendvai

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=3493949.dX3coAEF3O@bastet \
    --to=philip@philipmcgrath.com \
    --cc=ekaitz@elenq.tech \
    --cc=guix-devel@gnu.org \
    --cc=liliana.prikler@ist.tugraz.at \
    --cc=maximedevos@telenet.be \
    --cc=rekado@elephly.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/guix.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.