all messages for Guix-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Philip McGrath <philip@philipmcgrath.com>
To: Ekaitz Zarraga <ekaitz@elenq.tech>,
	Ricardo Wurmus <rekado@elephly.net>,
	guix-devel@gnu.org
Cc: guix-devel@gnu.org,
	Liliana Marie Prikler <liliana.prikler@ist.tugraz.at>
Subject: Re: Faster "guix pull" by incremental compilation and non-circular modules?
Date: Sun, 20 Feb 2022 11:47:45 -0500	[thread overview]
Message-ID: <6012789.Rgyoke53jH@bastet> (raw)
In-Reply-To: <753ba5897ed397b5e95175cd139137975245945b.camel@telenet.be>

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

Hi,

On Sunday, February 20, 2022 7:19:07 AM EST Maxime Devos wrote:
> Ekaitz Zarraga schreef op zo 20-02-2022 om 11:34 [+0000]:
> > Making a Guix pull is unpredictable too...
> 
> An idea for making "guix pull" faster:
> 
>   1. Make package imports non-circular, breaking up package modules
>      in parts when necessary.
> 
>   2. Instead of building all of Guix as a single derivation,
>      create a DAG of derivations.  More concretely:
> 
>      First read the *.scm files to determine which module imports
>      which modules. Then to compile, say, (gnu packages acl),
>      a derivation taking gnu/packages/acl.scm and its dependencies
>      gnu/packages/attr.go, gnu/packages/base.go, ... is made
>      compiling gnu/packages/acl.scm to a gnu/packages/acl.go.
> 
>      Then to build all of Guix, 'union-build' or 'file-union' is used.
> 
> The benefit is that if, say, gnu/packages/gnunet.scm is changed, then
> the old gnu/packages/acl.go will be reused because its derivation
> doesn't depend on gnu/packages/gnunet.scm (*).
> 
> The need for non-circular imports can be avoided by computing the
> strongly-connected components and compiling all the modules in a
> component as a single unit.
> 
> Greetings,
> Maxime.
> 
> (*) Actually I didn't verify if acl.scm depends on gnunet.scm or not.

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.

As I mentioned there, I am most familiar with the semantics of Racket
modules,[1][2][3][4][5][6] and secondarily with R6RS libraries.[7]

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?

Racket's module system fundamentally requires that module imports for a DAG
(see footnote 1 in § 2.2 of [1]), which is necessary to provide “The Separate
Compilation Guarantee”[1][6]:

> Any effects of the instantiation of the module’s phase 1 due to compilation
> on the Racket runtime system are discarded.

This is an extremely useful property, especially if you care about
reproducibility.

I know that R6RS does not provide The Separate Compilation Guarantee, since
§ 7.2 [8] explicitly says:

> An implementation may distinguish instances/visits of a library for
> different phases or to use an instance/visit at any phase as an
> instance/visit at any other phase. An implementation may further expand
> each library form with distinct visits of libraries in any phase and/or
> instances of libraries in phases above 0. An implementation may create
> instances/visits of more libraries at more phases than required to satisfy
> references. When an identifier appears as an expression in a phase that is
> inconsistent with the identifier's level, then an implementation may raise
> an exception either at expand time or run time, or it may allow the
> reference. Thus, a library whose meaning depends on whether the instances
> of a library are distinguished or shared across phases or library
> expansions may be unportable.

I haven't found anything in R6RS that explicitly addresses cyclic library
imports, but I think this passage from § 7.2 [8]:

> If any of a library's definitions are referenced at phase 0 in the expanded
> form of a program, then an instance of the referenced library is created
> for phase 0 before the program's definitions and expressions are evaluated.
> This rule applies transitively: if the expanded form of one library
> references at phase 0 an identifier from another library, then before the
> referencing library is instantiated at phase n, the referenced library must
> be instantiated at phase n. When an identifier is referenced at any phase n
> greater than 0, in contrast, then the defining library is instantiated at
> phase n at some unspecified time before the reference is evaluated.
> Similarly, when a macro keyword is referenced at phase n during the
> expansion of a library, then the defining library is visited at phase n at
> some unspecified time before the reference is evaluated.

combined with the specification in § 7.1 [9] that:

> The expressions of variable definitions are evaluated from left to right, as
> if in an implicit letrec*, and the body expressions are also evaluated from
> left to right after the expressions of the variable definitions. A fresh
> location is created for each exported variable and initialized to the value
> of its local counterpart. The effect of returning twice to the continuation
> of the last body expression is unspecified.

means that they are prohibited. If library (a) and library (b) were each to
import each other and each to refer to the other's definitions at phase 0,
then library (a) must be instantiated *before* library (b), but library (b)
must also be instantiated *before* library (a), so an attempt to instantiate
either library would diverge.

Of course, Guile can, as an extension, assign meaning to cyclic module
imports, but I question whether Guile would be wise to do so, and whether
Guix would be wise to rely on it. It was before my time, but I know the
design of Racket's module system was influenced by the experience of
programming with Rackets "units"[10][11], which do support mutually recursive
references. Units are great when you really do need them, but the view of
those who experienced them was that acyclic modules are a better choice as
the fundamental mechanism of code organization. While you can make a compiler
or build system handle cyclic dependencies (albeit without all the nice
properties of the Racket and R6RS module systems), humans tend to find them
very confusing, especially when they are not explicit.

-Philip

[1]: Matthew Flatt, “Composable and Compilable Macros: You Want it When?”
(ICFP 2002), https://www.cs.utah.edu/plt/publications/macromod.pdf
[2]: Matthew Flatt, "Submodules in Racket: You Want it When, Again?"
(GCPE 2013), https://www.cs.utah.edu/plt/publications/gpce13-f-color.pdf
[3]: https://docs.racket-lang.org/reference/syntax-model.html#%28part._mod-parse%29
[4]: https://docs.racket-lang.org/reference/eval-model.html#%28part._module-eval-model%29
[5]: https://docs.racket-lang.org/reference/eval-model.html#%28part._module-phase%29
[6]: https://docs.racket-lang.org/reference/eval-model.html#%28part._separate-compilation%29
[7]: http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-10.html#node_chap_7
[8]: http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-10.html#node_sec_7.2
[9]: http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-10.html#node_sec_7.1
[10]: Flatt & Felleisen, "Units: Cool Modules for HOT Languages" (PLDI 1998),
http://www.ccs.neu.edu/scheme/pubs/pldi98-ff.ps.gz
[11]: https://docs.racket-lang.org/reference/mzlib_unit.html

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

  reply	other threads:[~2022-02-20 16:52 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 [this message]
2022-02-20 17:47           ` Semantics of circular imports Maxime Devos
2022-03-27 14:12             ` Philip McGrath
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=6012789.Rgyoke53jH@bastet \
    --to=philip@philipmcgrath.com \
    --cc=ekaitz@elenq.tech \
    --cc=guix-devel@gnu.org \
    --cc=liliana.prikler@ist.tugraz.at \
    --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.