Tighter control of stream lifetimes

Yesterday I thought of a new semantics for stream lifetimes, that could provide a tighter control of them. I’ve updated the language specification document, and am going to talk about this change in this post.

As opposed to streams in some functional reactive programming (FRP) designs, the lifetime of a Dew stream is important, because a Dew stream could have side effects when evaluated for its current value. Side effects include spawning new streams, calling game engine functions, and others.

A more unusual thing is that, the lifetime of a Dew stream has to depend on its garbage collection reachability. Imagine we hold a reference to a stream of *t type, if we are unsure about whether its lifetime has ended, the stream would effectively be a *?t-typed value to use. We decided that would be too inelegant, and instead guarantee the lifetime to extend to at least as long as it can be reached via reference, i.e. garbage collection reachability.

Naturally, we further guarantee that a stream’s lifetime ends when it’s no longer reachable, and thus making stream lifetimes controlled by references. This makes a much simpler core language compared to other more explicit approaches, but it’s tricky in multiple ways.

Evaluation in the last frame

To ensure a stream’s lifetime ends when it’s no longer reachable, we have to do a full garbage collection at the end of each frame. In the previous design, if a stream is found to be not reachable by the garbage collector, it won’t be evaluated in the next frame, but it would still be evaluated in the current frame.

Still being evaluated in the last frame is where the problem is. Imagine in one frame we determined that we should get rid of a stream s, we can pass this information immediately to switch or keepalive, and s would be immediately garbage collected at the end of frame, but it would still be delayed to the next frame to take effect. This lack of control is quite undesirable: it could make things more complicated, or introduce additional delay in the gameplay.

To fix this problem, I changed the language so that a stream s is only evaluated after s has been proven reachable, or when @s is evaluated. It’s possible for a stream to be not reachable at the end of frame, but still gets evaluated for its current frame.

This change makes stream computations intertwined with garbage collection. It would hurt performance: some parallelism is lost, and GC must be non-moving; but I think the improved controllability is well worth the performance loss.

Object reachablity

Another tricky aspect of stream lifetime’s end is the exact definition of garbage collection reachability of an object. In a normal programming language, the compiler can freely remove dead upvalue references for a closure. However In Dew, removing references could lead some streams to be ended earlier.

My idea has swung between allowing and disallowing removing references. If reference removal is allowed, all streams with side-effects must have their lifetimes explicitly specified by a *bool stream via keepalive. But now, I’ve settled on disallowing removing references. Together with semantics change described in the previous section, it could have some really interesting use cases.

Suppose we have an entity that is controlled from Dew, but needs feedback from the game engine. Previously, the entity’s lifetime has to be explicitly specified with a *bool stream.

let spawn_entity params controls =
   let id = engine_create params in
   let control = dew -> engine_control id @controls in
   let alive' = %alive || pre true %alive in
   let ret = dew' -> if @alive' then ?(engine_get_feedback id) else ?? in
   keepalive %alive control;

In this approach, the entity’s lifetime is explicitly given by a dynamically scoped variable %alive. The returned feedback stream may be held longer than %alive, and it uses type *?feedback in case there’s no feedback. Note that the feedback lasts one more frame than the control stream, before turning to ??. That’s some valid feedback information that we don’t want to miss.

With the guarantee that dead references won’t be removed, we can also do this:

let entity params controls =
   let id = engine_create params in
   let control = dew -> engine_control id @controls in
   let feedback = dew' -> engine_get_feedback id in
   let ret = dew -> let _ = control in @feedback in

With this approach, the entity’s lifetime is implicitly given by the reachability of the returned stream. When we want to get rid of a such entity, we only need to drop all references to it. Also we can still get the last feedback by evaluating its feedback stream.

I find this implicit approach much simpler; while the explicit approach is still more powerful. While the use of implicit lifetimes may seem to make Dew programs tricky to work with, reference is already an important thing to take care of for performance reasons.

In fact I can define everything with the implicit approach, and only convert it to explicit approach with a combinator when needed:

let spawn entity params controls =
   let ent = entity params controls in
   let ret = switch (dew ->
      if @%alive then
         \pre ?@ent ??) in


Dew has a really unusual semantics that garbage collection reachability affects program semantics. The programmer must be careful working with references.

I’m glad that I chose to implement Dew as a standalone programming language with its own runtime and garbage collector. It would otherwise be quite difficult to implement the updated semantics, in which main computations are intertwined with garbage collection.