It has been a while since the last blogpost. In most of this time I was working on other parts of my game, which took much longer than I anticipated. On top of that, I also stopped updating my daily Dew animations for a number of reasons. But now, I am back.

Although it’s less than ideal from what I’d like, but this staying away experience now gives me a refreshed view of the language when coming back, just like when one would feel with a previously created artwork. So in this blogpost, I am going to review this language from various perspectives, along with some updates I made and some ideas for future work.

First-class stream with side effects

First-class stream is of course the single defining feature of this language. There are other languages or library frameworks that focus on the same goal of programming with streams, but what most distinguishes Dew from other similar works is that, evaluating a stream for its current value can have side effects.

This side effect design feels both powerful and easy to use, without destroying the declarative nature one would expect from the data flow approach of programming. Side effect is used for instantiate new streams, so it’s trivial to dynamically change the data flow network. Communicating with the external world is also done by side effects, and it’s simply calling external functions as needed through the C FFI.

However, the design with side effects is not without costs. The presence of side effects requires that the lifetime of streams must be well-defined, particularly the ending point of the lifetime, so that the programmer can control when the side effects will stop happen. It was discovered that it’s best to tie stream lifetime to GC aliveness. So not too surprisingly, thinking stream lifetime was a relatively unpleasant part of programming in Dew. I recently redefined stream lifetime in terms of the alive property of a value and evaluated property of a Dew stream, so that the semantics feels clearer now.

To support the well-definedness of stream lifetime, GC aliveness must also be well-defined at each frame. In other words, the complication is that Dew’s GC aliveness doubles as a basis to define program semantics, in addition to help with memory management. Usually in other languages with a tracing garbage collector, the exact reference relations among different values are not important, and it’s fine for the compiler to optimize away some references. But this is not the case with Dew, where it must be precisely defined what values are referenced by each value, and as an example a closure is defined to reference each of its upvalues as determined lexically.

A recent change in GC aliveness is that, I have made a stream as defined by dew -> expr to not reference its current value. This change is largely driven from a theoratical point of view, and it feels an elegant change. It makes a value of type *a feel more like a time-varying value that can be momentarily inspected to be a value of type a, rather than a container that gets updated every frame. When the old semantics is desired, the programmer can always use a hold function:

# hold: *''a -> *''a
let hold x =
   let x' = pre ?? (dew -> ?@x) in
   dew -> let _ = x' in @x

So another benefit of this change is more flexible control of GC aliveness, since the user of a *a stream can choose whether or not to retain its momentary values. Yet a third benefit is when doing compiler optimization to a program like as follows:

let a = dew -> expr_a
let b = dew -> ... @a ...

We would want to combine these two streams, by embedding expr_a into b and resulting in a single stream b'. This is an important for optimization, because each stream has a fixed runtime cost when compiled. And with the new GC aliveness design, we won’t need to make sure the result of expr_a is referenced by b'.

The type system

In Dew, we allow higher-order streams, in the sense that the current value of a stream can be another stream, i.e. the type **a is allowed. Higher-order streams has been useful for building state machines, which is an important building block for many applications, and an important primitive function switch: *(''a\*''a) -> *''a is added to help. However it remains to be seen how higher-order streams are useful in practice, for other cases unrelated to state machines.

In a programming language with streams, one would want a value defined for non-streams like f: a -> b to also work with streams as f: *a -> *b, so that working with time-varying values is close to working with normal values. In Dew, this is achieved by parametric polymorphism on the type level, and a kind of type variable (n*) is introduced to represent any non-negative finite number n of * in its place, so that f: (n*)a -> (n*)b can work with both time-varying values and normal values. This polymorphism with streams can only arise from special language constructs, which makes use of a mechanism that I call stream generalization. This parametric polymorphism together with stream generalization worked well for most of the time. I have tried to improve it recently, and a module-level value of type a can also be used as (n*)a through stream generalization, so I am hoping it will work better.

Moving on to other parts of the type system that is not specific to streams. An recent major update is that I implemented polymorphic variants in Dew, as pointed out to be useful in the previous blogpost. Both the polymorphic variants and structural records use a simple design. I read from experiences of OCaml and Elm that, more advanced features from more sophisticated designs do not seem to work well in practice. So I am using a simple design in Dew, because the main goal here is that types don’t have be explicitly declared, which helps in quick game scripting.

Polymorphic variants is simple to implement on its own, but then I made some additional changes that was challenging for compiler implementation. To make language features more orthogonal to each other, I removed ordinary variants in favor of always using polymorphic variants. However there’s a problem with recursive types. Recursive types were used to be constructed with ordinary variants, so with only polymorphic variants I decided to extend the type system for equi-recursive types. It was already non-trivial to do type unification in presence of equi-recursive types, but Dew does monomorphism to all types during compilation, so all types must also be minimized into a unique representation, and automatic boxing on the heap memory is added.

As of now, Dew’s type system already feels of a size comparable to a more mature general purpose functional language. Most common types one would expect from a functional language can also be found in Dew, except for strings, which I’m delibaratedly leaving out. Dew is designed for game scripting, and for best game performance, strings in game scripts should only be used for player-facing texts, and that involves localization. And when localization is considered, it’s better to make use of Dew’s keypath types, and plain strings directly inside Dew script files do not sound a good idea.

The only one more piece that I want to see in Dew is higher-ranked types, which can be used together with records for a simple parametric module system. I expect this to take time and be challenging to implement, so I am leaving it to sometime in future.

Delay and frame phases

When building abstractions in Dew, an issue that commonly arises is delay. It’s not uncommon that a delay of one frame has to be added, so that a particular abstraction can then be built in Dew. This is a result of the concurrent and synchronous nature of the language, and a value in a synchronous frame can depend on all concurrent threads in the same frame.

One example is channels. The output of a channel depends on every concurrent thread that could potentially send a value into the channel. So to read the channel output at one particular frame, there’s no reliable way to know all values sent into the channel within the same frame, until that frame has ended and all concurrent threads have finished. So naturally, one variant of Dew channels dchan is designed to delay one frame for its output. To design a non-delay channel variant chan, I had to add an extra restriction that it must receive exactly one value per frame.

Another example is related to GC aliveness. Sometimes we want to know whether a stream is still alive within one particular frame, and this information can be used to implement a primitive for weak references weakref: ''a -> *?''a. But again, there’s no reliable way to know this GC aliveness information, until the frame has ended.

One way to address the problem is to introduce multiple phases in one Dew frame, so that one synchronous frame is splited into multiple frame phases. Phases can be used to reduced to delays, because what would originally be delayed to the next Dew frame, can now be delayed to the next phase of the same frame. For now, a Dew frame is splitted into two phases, and a special early phase is run before the main phase.

The early phase is a result of the language feature of early streams, which streams are evaluated before regular streams. Dew programs are expected to work with external code, which is likely written in a general-purpose imperative language and has various mutable states. Dew scripts can mutate the external states through the allowed side-effects of C FFI function calls, and the external states can also change between two neighboring Dew frames, when the external code is run. To help Dew scripts react to the external world, the language feature of early streams were introduced, so that at beginning of each frame, a set of consistent observations of the external world can be made and saved.

A consistent view of the external world at the beginning of a frame was thought to be important, but it is less so now after my recent experience with game engine programming. I found that it is generally a bad idea to have any shared mutable states in the game engine at all, if game performance is taken seriously and multi-threading parallelism is well-considered. Assuming we were having a shared mutable state, a fine-grained lock must not be used to avoid too much locking overhead, but a coarse-grained lock should not be used either, because that would limit parallelization. In my game engine, for performance and software tractability, I had to resort to a solution related to multi-version concurrency control (MVCC) and software transactional memory (STM). Nevertheless, it’s now still useful to use early streams to fetch external updates in the early phase, so that dchan channels can be used without delay to help with data flowing to react to the external updates.

Similarly as with the early phase, a late phase could be added to implement weakref. But I haven’t decided how useful it would be in practice.

Ultimately however, there would still be frame delays that are unavoidable in Dew programs, after the more common ones are addressed with more language features. Hopefully this wouldn’t be a problem for games however, because games typically run at 60 fps, making the delayed time short; and the player may be not sensitive to all kinds of delays. I’m not sure how the delay issue can be better solved, but as the number of frame phases increases, parallelization could potentially be hurt, because all computation for a one phase must be done before the next phase can start.

Syntax

The syntax of Dew is largely inspired by OCaml. When I started out to create this Dew language, I know much innovation would happen with the semantics of the language, so the syntax is intentially not as innovative to keep things under control.

OCaml’s syntax is well-established although with some well-known quirks. So when I was creating Dew, I tried to address some of quirks. One is the syntax of negative literal numbers, which in OCaml are often required to be put in parentheses like f (-1). In this case, parentheses are required to avoid the ambiguity that - could also mean the binary minus operator. I expect negative literal numbers to be used frequently in game scripting, and requiring parentheses often would be inconvenient.

The solution used by Dew is introducing whitespace sensitivity. It is significant whether an operator is locally surrounded by whitespaces. Still taking - as the example, it would be read as different parser tokens for different surrounding whitespace cases:

a - b # binary minus operator
a -b  # unary minus operator
a- b  # invalid syntax
a-b   # binary minus operator, but binds more tightly than `a - b`

Thus f (-1) can be written as f -1 without ambiguity, and whitespace-sensitive rules like this are also used by other operators. This design has worked well in practice. It can reduce parentheses in many cases without introducing any ambiguity. The only downside is that, occasionally whitespaces have to be used when I’d prefer not.

The syntax of Dew has been mostly stable. However after the long time of experience doing other work, my personal preferences has shifted a little, and two syntax changes were made recently. These changes are not strictly necessary, and changes like these are why I think Dew is still a work-in-progress. I hope Dew can be more stable when it is first released.

One change is that let in Dew is no longer recursive by default, and let rec must be used for recursive let bindings. Previously let is always recursive, except for some cases involving dynamically scoped variables. This change was made because (1) I am finding rebinding the same variable useful; (2) accidental recursive defenitions could sometimes result in cyclic dependency only detected in runtime, or maybe compile errors that are difficult to read; and (3) binding of dynamically scoped variables is now more elegantly handled.

Another change is that I decided to change the syntax of (|expr|) and [|expr|] to %(expr) and %[expr] respectively. The new syntax feels more concise and easier to type.

Applications

So far I’ve successfully used Dew for procedurally generated animations. I have built abstractions and combinators to work with animations at a high level. In my experience it worked really well, and sometimes it felt magical.

What is lacking from the animation abstractions is support for mulitple animated objects. I have an idea for multi-animation synchronization, but it needs channels, so I’ll try out the idea after channel is implemented. Yes, channel is still not implemented yet, but I will be working on it right next.

For GUIs, my last post is still relevant. Since the long time after the last post, I was already forgetting about my own GUI idea from back then, but was able to recollect my memories from the blogpost, and I found it a pleasure to read. I may have some minor improvements now, but the overall structure layed out in that blogpost is already elegantly done.

A major downside of writing GUIs in Dew is that, all streams have to be re-evaluated every frame, even in the case of a single user input event that only locally affects the GUI. For functional reactive programming (FRP), it would be possible to solve the problem by (1) having a second kind of streams, which are usually called events, and (2) driving the re-evaluation of the data flow network from input event updates, so that only necessary streams are re-evalauated. But for Dew however, I haven’t found a good way to improve from the current design. It was not much of a concern when I started the project, because Dew is designed for game scripting after all, where it’s not unusual to rebuild a scene dynamically each frame.

As for the main game, I am planning to use a variant of the GUI abstractions to encode a scene graph in Dew. This is really exciting and I am eager to see how well it will work out.

It has become clearer to me that for an application, it could be useful to use multiple Dew units at the same time, and have them communicate with each other. The multiple Dew units could be organized hierarchically, like the scene tree design in Godot game engine. The multiple Dew units could also possibly run at different frequencies, and this to some extent could help with the re-evaluation efficiency problem I mentioned above, so that a larger Dew units can be splitted into smaller ones running at different frequencies. To help with such use cases, (1) I recently improved Dew runtime, and the limitation of disallowing re-entrant calls of Dew C APIs is removed, and (2) I am also planning to introduce an efficient and type-safe serialization mechanism into the language, to facilitate communication across different Dew units.

Conclusion

In the end, despite of all the careful planning ahead, I have to admit that Dew is a highly explorative work, which started with the idea or belief that first-class streams should be useful for game programming.

The exploration so far has revealed strengths and weaknesses of Dew, which is totally normal because any programming language or tool would have its strengths and weaknesses. As the Dew programming language becomes more and more stable, I am feeling that the end of this adventure is close.

But the end is definitely not here now, and there’s much work left to do before I can call it complete. I will write another blogpost on animations soon, after I experiment with abstractions for multi-animation synchronization.