monotonously-increasing maps

[gelisam]

To implement new types of declarations, such as type classes (#167) or base functors (#162), macros need to be able to cooperate by adding information to some global list or map, in the same way define adds entries to the list of top-level definitions.

The obvious way to do that is to define a global mutable Map and for the macros to mutate it, but allowing macros to perform arbitrary mutations would definitely break Klister's promise that the macros cannot observe the order in which the compiler chooses to expand them.

The proposed solution is to take inspiration from the lvish library:

1. The values a mutable variable can take are ordered by a join-semilattice.
2. The only way to write to a mutable variable is modify (lub x) for some x.
3. If the mutable variable ever reaches ⊤, the entire computation fails, because some threads might have observed something they shouldn't have.
4. The only way to read a mutable variable is via a "threshold read": we block until the mutable variable's value is above the threshold, and then we learn where it crossed the threshold.
5. A "threshold" is a horizontal line in the semilattice defined by a set {x,y,z} of values which pairwise lub to ⊤.
6. Crossing the threshold means that the mutable variable has a value t which is ≥ one or more of the values x, y and z in our threshold.
7. If t ≥ x and t ≥ y, then t ≥ lub x y = ⊤, thus t = ⊤.
8. Thus, as long as the entire computation doesn't fail, t is above exactly one value in the threshold, and that's the value which the threshold read returns.

Klister is not using threads, but the goal that the result should not depend on the order in which the tasks are performed is similar to the goal that the result should not depend on the thread scheduling.

If a and b are types with suitable lattices, then Map k a, (a, b), and Either a b have suitable latices too. Infinite combinations of these, like [a], as well. At the leaves, Set c and IVar c (whose lattice has lub c1 c2 = ⊤ for every pair, and thus can only be written to once) have lattices for every c. And of course () and Void.

So this is quite a rich set of types, and it's not too clear exactly how to provide all of this to the user. But as the very first step, a Map Symbol (IVar c) would allow users to create custom top-level definitions by assigning a value to the symbol being defined. The threshold read in this case is simply to wait until a given symbol has been assigned a value, at which point that value is read.

[gelisam]

Hmm, if we want multiple top-level declarations to contribute to the same LVar, that LVar needs to be available at the top-level. Which means that the type signature for creating an LVar needs to be something like newLVar :: a -> LVar a, not newLVar :: a -> IO (LVar a). That seems wrong, no?

[gelisam]

Ah, it works if it's newLVar :: a -> Macro (LVar a), because a macro can create the LVar and then define the declaration-macros which refer to it.

[gelisam]

The feature is inspired by MetaPRL's "Resources" feature, which is not monotonously-increasing, but does allow attaching values other than definitions to symbols.

[gelisam]

@doyougnu and I discussed possible APIs. Here is the "top-level" approach:

(define-mono-map my-map)
(insert-mono-map my-map my-key my-value)
(run
  (print (lookup-mono-map my-map my-key)))

And here is the "macro monad" approach:

(define-macro my-macro
  (lambda (stx)
    (do monad-macro
      (my-map <- (create-mono-map))
      (insert-mono-map my-map my-key my-value)
      (pure '(...)))))

We ended up with this hybrid approach:

(meta
  (define-mono-map my-map))
(define-macro my-macro
  (lambda (stx)
    (do monad-macro
      (insert-mono-map my-map my-key my-value)
      (x <- (lookup-mono-map my-map my-key)
      (pure '(...)))))

[gelisam]

The top-level approach is similar to our existing top-level binders, so let's review how those work.

Currently, when we write

(define x (string-append "foo" "bar"))
(run (putStrLn x))

The task which expands (run (putStrLn x)) is blocked until (define x (string-append "foo" "bar")) has made some progress, because it could (and indeed does) bind a macro which would affect how the (run ...) piece is expanded. (define x ...) binds x to a macro which expands to CoreVar something, and then the (run ...) piece can be expanded. In particular, that piece and the (string-append ...) piece can be expanded in parallel.

Similarly, in

(define-mono-map my-map)
(insert-mono-map my-map my-key my-value)
(run
  (print (lookup-mono-map my-map my-key)))

The (insert-mono-map ...) task would be blocked until (define-mono-map ...) binds my-map to a macro which expands to CoreVar something.
The (insert-mono-map ...) and (run ...) task don't need to depend on each other, so in theory they can be expanded in parallel. Unfortunately:

1. Until at least a little bit of progress is made on (insert-mono-map ...), there is no way to know whether it might bind a macro which affects how the (run ...) piece is expanded, so in practice the (run ...) task would block until the (insert-mono-map ...) piece has been at least partially expanded.
2. Even if the two pieces do expand in parallel, that's irrelevant because with the top-level approach, the insertion and lookup would not occur at expansion-time, they would occur when the resulting Core executes. Core executes top to bottom, so this API gives no parallelism opportunities where one macro is blocked on a MonoMap key and another macro unblocks it.

Thus, the top-level approach is not a good API for MonoMap.

[gelisam]

Another reason why the top-level approach is undesirable is that it does not support some of the use cases we have in mind for MonoMaps.

Haskell-style type classes is one such use case, of course, but we also want to allow the user to implement variants of type classes which don't quite match Haskell's design. For example, maybe the user wants to allow a local instance in a where clause which is only visible locally. It seems plausible to use scope sets to restrict the visibility of an instance to a local scope even though the instance is added to a global MonoMap. But with the top-level approach, it would not be possible for a macro in a where clause, deeply nested inside an expression context, to generate a define-mono-map call which is only intended to work in a top-level definition context.

[gelisam]

With the macro-effect approach, it is easier to imagine a pair of macros being expanded in parallel, one being stuck on a call lookup-mono-map and the other calling insert-mono-map to get the first macro unstuck. It is also clear how the macro side-effects can occur inside a macro which expands in an expression context.

However, one difficulty is that once a parent macro has called create-mono-map and obtained a MonoMap, it is difficult for that macro to pass on that opaque MonoMap value to later macros, such as the pair of macros we imagined above. Those macros would need to be expanded from two different parts of a the Syntax object returned by the parent macro, but since those macros only receive a Syntax object as input, there is no way for them to receive the MonoMap value from the parent macro. In other scheme-like languages, this is not a difficulty because any value can be embedded inside a Syntax object, but in Klister, our Syntax objects are precisely typed and so the leaves of the Syntax object can only be strings, integers, and identifiers.

Hence our preference for the hybrid approach: a globally-defined MonoMap, accessible by all later macros including the pair of macros we have imagined. Even better: a parent macro can now use such a MonoMap to pass on arbitrary opaque values to later macros! The keys of a MonoMap are identifiers, and identifiers can be passed from a parent macro to a later macro, thus the parent can store an opaque value in a MonoMap, and the later macro can retrieve it from that same MonoMap.