Top-level laziness and recursion

[jamii]

In zig, modules are 'just structs' but the namespace of structs is partitioned into fields and defs. Field values belong to the struct and are eagerly evaluated in order when the struct is instantiated at runtime. Def values belong to the struct type, are lazily evaluated at compile time and may be mutually recursive. (The comptime interpreter throws a compile error if it forces a cyclic dependency).

In 1ML modules really are 'just structs' which happen to have been evaluated at compile time. But they move quickly past recursion so it's not clear to me exactly how they handle this. My hunch is that let rec blocks are evaluated eagerly (at compile-time for modules/types and at runtime for recursive closures).

Is let rec style recursion an acceptable price to pay for unifying the namespaces? Can we recover laziness without dual namespaces? Would the lack of laziness break nice zig features (eg make platform-specific meta-programming onerous because we have to carefully avoid eagerly-evaluating anything that would not work on the target platform even if we don't use it) (eg not being able to run a test because some value that the test doesn't even depend on does not compile).

---

Additional restrictions that are important in zig:

• Comptime-evaluated code cannot cause side-effects
• Comptime-evaluated functions which return types may be memoized.

---

A basic 1ML -like solution would be a module syntax which allows mutually recursive bindings, eagerly evalutes them and returns a struct.

odd_even = module {
  even = (n) if (n == 0) 'true' else odd(n - 1)
  odd = (n) if (n == 0) 'false' else even(n - 1)
}
odd_even.even(3)

=>

'false'

module [
  a = b + 1
  b = 1
]

=>

[a: 2, b: 1]

module [
  a = b + 1
  b = a + 1
]

=>

compile error

This allows for mutual recursion, but not for eg cyclic imports. How annoying is this?

---

We add a lazy type and extend the module syntax to return lazy values.

module [
  a = b + 1
  b = a + 1
]

// equivalent to

[
  a: lazy(() b + 1)
  b: lazy(() a + 1)
]

I don't like this because it:

• Introduces reference cycles, which makes these values hard to print/serialize
• Introduces invisible side-effects when accessing these values for the first time
• Requires either that we have some cycle-detection mechanism at runtime, or that some language features are only available at compile-time (which in turn implies no multi-stage programming).

[jamii]

Clojure does not support cyclic imports, and only allows mutual recursion via pre-declaration:

(declare odd)

(defn even [x] (if (= x 0) true (odd (- x 1)))

(defn odd [x] (if (= x 0) false (even (- x 1)))

I don't remember this being particularly onerous, although being dynamically typed maybe reduces the dependency edges between modules anyway.

[jamii]

If we have:

// a.zest
b = import('b.zest')

// b.zest
a = import('a.zest')

then we create a circular data-structure, which is otherwise not allowed in zest.

It's ok for functions to be mutually recursive across modules, but mutually recursive closures also create circular data-structures unless we do something clever to share a single closure object between them?

It's not ok for constants to have circular dependencies though.

[jamii]

Here's a proposal. It's called "we have lazy at home".

Add import literals import('foo.zest'). These look like a function, but the argument must be a constant path. (Can extend this later to deno-style package imports.)

A module looks like (name = (literal | function))*. To evalaute a module:

• Evaluate all import literals, in any order, replacing them with their value.
• Resolve names in each function against those available in the current module (functions can be mutually recursive).
• Return a struct containing the names+values in the module.

Imports are memoized, so importing the same file twice produces one value with a refcount of 2. Imports may form a dag but may not contain cycles. That means no mutual recursion across modules, unfortunately.

If you want to compute something, do it in a function:

wasm-page-len-log = () u32[16] // log2(64 * 1024)
wasm-page-len = () u32[1] << wasm-page-len-log

(We might want to allow memoizing functions like wasm-page-len-log = #memo () .... Memoized functions would not be allowed to take mutable arguments and would raise runtime errors if they try to do IO.)

Conditional compilation looks like:

io = () {
  if (get-os() == 'linux') {
    import('io/linux.zest');
  } else {
    import('io/other.zest');
  }
}
open = (path) io().open(path)

The import literal is replaced by the module contents. In the interpreter, we pay for a branch in io() and a struct lookup in .open. In compiled code we can stage that away and replace io().open with a constant.

---

This approach avoids adding implicit laziness hiding in the . operator. Computation is always visibly triggered by a function call.

---

If the lack of mutual recursion across modules becomes annoying we can tweak this design slightly. Force modules to form a tree, but allow access to the root of the tree with a function root(). Since we can't call functions at load-time, this can't be used to form a cyclic data-structure.

---

Given a salsa-like framework, it seems straightforward to extend this approach to support both incremental compilation and notebook-style incremental evaluation. Everything is just a big bag of maybe-memoized functions.

Module evaluation can be fast - probably on par with zig parsing and ast-gen. And then we can diff the results against our current bag of functions and keep any memo-tables for functions whose transitive hash hasn't changed.