Re: Faster "guix pull" by incremental compilation and non-circular modules?

[Philip McGrath]

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

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