Alternatives to Stateful Closures

[scolsen]

Currently, Carp doesn't support altering state in closures. As stated in DynamicSemantics, a closure's environment is captured in its entirety at creation time and prevents mutation of captured variables. This makes the definition of some classic functions impossible, such as this example from Let Over Lambda:

(let ((counter 0))
  (lambda () (incf counter)))

This function increments a value every time it is called. So, it successively returns 1, 2, 3....

The corresponding function in Carp always returns 1 instead of incrementing the value on each call:

(defn adder []
  (let [x 0]
    (fn [] (inc x))))

Stateful closures are a technique I find useful. I don't think Carp needs to support them--and in fact it might make more sense not to depending on the language's overall semantics, but I am wondering whether we have a canonical way to likewise perform some ad-hoc capturing of state or a drop in replacement for places in which we'd use some stateful closure.

As an example case, mapping over a Stream sumtype is significantly easier with stateful closures.

Is the solution simply to allocate and pass around structs whenever one needs to keep track of some state?

[eriksvedang]

I forbid mutating lambdas mainly for ease of implementation, heh. But since the hope is that most higher level programming in Carp will be done in a functional style I think it's a pretty good choice, since mutating closed over variables can become pretty messy and very imperative (although I agree that they are also useful and neat sometimes). And yes... passing around structs is the "official" method for solving such problems for now. If you have the time it would be illuminating if you posted a small example of how you'd write the Stream code with mutating closures, vs. how you have to do it now (using structs).

[scolsen]

Sure thing! I don't actually have a struct implementation, but here's what I was trying to accomplish with closures:

First, the sumtype we use to define a Stream, it's got a bottom/empty state Nil and otherwise is a pair of values, the current value in the stream, and the rest of the stream, which is a step function from the stream's type variable a to Maybe the same type (we use the Maybe to know when we've reached the end of the stream).

(deftype (Stream a) (Cons [a (Fn [a] (Maybe a))] (Nil [])))

To get successive elements, we define next which gets the next element by calling the stream function using the previous element:

(defn next [s]
    (match s
      (Stream.Cons x n)
        (match (n x)
          (Maybe.Nothing) (Stream.Nil)
          (Maybe.Just y) (Stream.Cons y n))
      (Stream.Nil) (Stream.Nil)))

All good so far, we can define a function that returns a stream based on an initial array of elements. A stream from an array returns a pair of an index and the value at that index. The restriction on mutation here is actually quite nice---we can close over the underlying array without fear of accidentally mutating it!

  (defn from-array [arr]
    (Stream.Cons (Pair.init 0 @(Array.unsafe-nth arr 0))
      (fn [p]
         (Array.nth arr (inc (Pair.a p)))) 

All's well thus far:

(Stream.next (Stream.next (from-array &[1 2 3])))
=> (Pair 2 3)

Things collapse when we attempt to define map, which should take a (Stream a) and return a (Stream b)

This is the obvious definition of map which doesn't work:

(defn map [f s]
  (match s
     (Stream.Nil) (Stream.Nil)
     (Stream.Cons x g) (Stream.Cons (f x) (fn [z] (f (g z))))))

The issue is that map breaks next. Ideally one want's to be able to write something like (Stream.Next (Stream.map f s)) but since we don't have a stateful closure, next has to pass a value to the streams step function. Unfortunately, mapping breaks this as the previous value is no longer of the same type as the original stream--it is now of the type of the mapped stream--for instance, if we tried to use this on our from-array stream to get the second member of the index/value tuple, it wouldn't work, since the array-based stream expects a pair input, but after mapping would receive a single Int/Char/ whatever the Array's member type is.

A stateful closure would fix this as then next doesn't need to explicitly pass an argument to the stream's step--it merely calls it to advance the stream based on the definition:

;; assume we have stateful closures and variables outside the closure are mutable from
;; within the closure:
;; i will be incremented on each call to the step function, without requiring explicit argument passing
;; this also simplifies the value of the stream (i doesn't have to be a pair)
(defn from-array [arr]
    (let [i 0]
      (Stream.Cons @(Array.unsafe-nth arr 0)
        (fn []
           (Array.nth arr (inc i))))

;; And the corresponding redefinition of next:
(defn next [s]
  (match s)
     (Nil) (Nil)
     (Cons _ step) (Cons (step) step))

If this were the case, the original definition of map works as is--we effectively map a stream just by redefining its step function as the composition of f and its original step function:

(defn map [f s]
  (match s
     (Stream.Nil) (Stream.Nil)
     (Stream.Cons x step) (Stream.Cons (f (step)) (fn [] (f (step))))))

And it all works!

I've thought about this a bit more, and I actually think there are ways to implement something similar without structs using some indirection in functions. Having the guarantee that the underlying array won't be mutated by the closure is a pretty nice and keeps the stream pipeline nice and functional...so maybe we should keep closure's mutation free? It does make things easier to reason about!

I do think we should try to figure out a good idiom for replacing stateful closures in general (even if it's as simple as "use a struct")!

[eriksvedang]

Thanks a lot for this excellent writeup @scolsen , you're truly a great writer! I've been out of the loop because of life stuff but will read this properly on Monday and give some feedback.

[eriksvedang]

OK, now I've given this some more thought and read through your text again. Thanks for the pedagogical explanation. Since you seem to have some ideas for how to do this without changing the implementation of the language, I'll eagerly await those results, and we can discuss the issue more after we know how it went.

[scolsen]

It's possible to do this using Pointers! #1036

[scolsen]

It depends on #1012 but here's the trick:

(defn stateful [] (let [x 1] (fn [] (let-do [x* (the (Ptr Int) (Unsafe.coerce &x))] (Pointer.set x* (+ x x)) x))))
(defn runstate [] (let-do [f (foo)] (ignore (f)) (ignore (f)) (f)))
(runstate)
Compiled to 'out/Untitled' (executable)
8
=> 0
鲤 

x, which is defined in the let and normally not set!able, is added to itself with each call to the lambda returned by stateful, and is totally encapsulated.

[scolsen]

@TimDeve devised an elegant means of defining a safe stateful closure! #1036 (comment)

I think it's safe to close this :)