Expressiveness is what Dew is all about, and I would have no reason other than this to invest time into Dew. I hope by making full use of streams, complex game dynamics could be made easier to implement, or at least so for my own games.

As a language designer, I don’t actually have a precise idea of Dew’s expressiveness, since language design only directly concerns about what and how primitive building blocks goes into the language. To test Dew’s expressiveness, what I would do is to try it out with some problems that I can think of. Sometimes I can recognize some missing feature would be really useful, so I went ahead and added it in; and sometimes Dew’s expressiveness surprises me about what it can do.

Recently, I got an interesting idea from someone in Fediverse. He has a theory that, to test a programming language’s expressiveness, you could try to implement an interpreter in the same language to do what the original language is capable of. For the instance of Dew, the test could then be writing an interpreter to do mob AI. I am not exactly sure whether this expressiveness test makes sense, but I am going to do it anyway since it sounds fun.

A generic mob AI in Dew

In Dew, the type *typ represents a stream, which evaluates to a typ-typed value in each time frame. I chose * to represent stream type because it’s the single most important thing in the language.

Now, an mob AI in Dew could then be simply represented as a function

spawnmob: *observables -> *controls

Note that this function should be called only once when the mob is created, rather than be called multiple times throughout the mob’s lifetime like one would do normally.

The mob can of course need its per-mob states. A mob AI function with states could have the type of

spawnmob_stateful: *observables -> *states -> (*controls,*states)

which accepts the states of its previous frame, and returns the new states of the current frame. For simplicity, we assume the states given to the function at the first frame is zero-initialized.

To implement spawnmob in terms of spawnmob_stateful, we would need to use the well-known pre stream operator. pre a b takes an initial value and a stream, and returns a new stream which always yields the previous value of stream b, except when the first frame it yields a.

let spawnmob observables =
   let state' = pre zero state
   and controls, state = spawnmob_stateful @observables @state' in
   controls

Note that there is not a single type declaration, even though the code is fully statically typed. This power comes from Hindley-Milner type inference.

In normal languages, the function spawnmob_stateful would be implemented as a non-stream function, which gets called every frame.

spawnmob_nonstream: (observables,states) -> (controls,states)

Now spawnmob_stateful can also be written in terms of spawnmob_nonstream:

let spawnmob_stateful observables states' =
   let *(controls, states) = dew ->
      spawnmob_nonstream (@observables, @states') in
   controls, states

Here we see some other Dew stream operators. @expr means to get the current value of stream expr. dew -> expr spawns a stream, whose values over time is defined by evaluating expr once for each frame. The pattern *pat can match against a stream.

Note that here we implement spawnmob in terms of spawnmob_stateful and spawnmob_nonstream for demonstration purposes; one do not actually need to do this in Dew. Within spawnmob, it’s required that internal mob states are eventually implemented as state streams and pre, but one does not need to do this directly and could use some abstractions instead.

Mob AI interpreter

Having an idea how a generic mob AI could be done in Dew, implementing an interpreter is quite straightforward. We would just need to add an additional program parameter to the functions spawnmob, spawnmob_stateful and spawnmob_nonstream.

spawnmob: program -> *observables -> *controls
spawnmob_stateful: program -> *observables -> *states -> (*controls,*states)
spawnmob_nonstream: (program,observables,states) -> (controls,states)

One thing to note however is that states now is the state of the interpreter, which in turns is supposed to encapsulate the states of interpreted program.

Now, I won’t go over the details how an interpreter can actually be implemented, and I am more interested in how the data program can be represented in Dew.

When I started to make Dew, it was intended to serve a single game in my mind, so Dew only has immutable tuples, options and lists. (Note: in case of any confusion, the spec doc on this site has been updated to include more datatypes.)

To represent program, algebraic datatypes(ADT) which are ubiquitous in ML languages would really be useful here to represent tagged unions; and array is another datatype that I miss, which could potentially make the interpreter more efficient. It’s definitely viable to do an interpreter without them, although it would be less elegant or less efficient. Also technically, both tagged unions and array could be emulated to a limited extent with support from game engine.

There’s actually a much more important problem than tagged unions and arrays here, and that is how one can construct cyclic data structures in Dew. This could be useful to represent program, because the jumps in the program could then be implemented as simple references rather than numeric indexes. And it turns out this looks very simple to do in Dew:

let p1 = (1, zero) :: p2
and p2 = (2, zero) :: p3
and p3 = (3, fun () -> p1) :: []

let in Dew is designed to be always recursive. I made it so because it would require fewer keystrokes in a game script. More importantly, the restrictions of what could make into a recursive let are more relaxed from a usual ML language. This is important for Dew, because the program

let x = f x

actually makes sense if x is a stream.

When running the above program, the right hand side of p1, p2, p3 would all be placed in a thunk before evaluating, and when evaluating the thunk of p3, it only needs the reference to the thunk of p1, rather than the evaluated value of it.

The same method can also be applied to more complex situations:

let root = build_tree (fun () -> root)

These all look nice, except there is one problem: we are running into recursive types here, which our Hindley-Milner based type checker would reject. Let’s assume the type of p1 is [a], and by the right hand side of p1, a is then (num, () -> [a]). So we get the type equation

a = (num, () -> [a])

A usual way to do recursive types in a functional language is using ADT, and let a be a named type recty.

type recty = R of (num, () -> [recty])

let p1 = R (1, zero) :: p2
and p2 = R (2, zero) :: p3
and p3 = R (3, fun () -> p1) :: []

# the next line alone does not need to be fixed
let root = build_tree (fun () -> root)

With ADT, the recursive type problem is resolved, so that we can have a nice way to construct cyclic data structures in Dew. I don’t think cyclic data structures are useful for my own game, but we now get one motivation to add ADT nevertheless.

State machines

Now I’d like to think about how I could do a mob AI practically in a real game. I’ve talked about generic ones and those discussion still holds; but in a real game, instead of worrying about making interpreters, I would worry more about modularization, code reusability, etc.

A classical and very useful approach is to introduce state machines, so we can break up the implementation of spawnmob into a few states. So now I’d like to see how a state machine can be written in Dew.

Suppose we use a different function for each state in the state machine, and let’s for a moment forget about state switches. We would probably want the states to be parameterized, and we name the type of the parameters like params1, params2. Then the type of these state functions are:

state1: params1 -> *observables -> *controls
state2: params2 -> *observables -> *controls
...

Now let’s imagine it’s an instance of state_n running, and now it wants to switch to anther state state_m. What we could do in state_n is to call the state_m function with all the needed arguments, and that would get us a *controls stream in return. Instead of getting more values from state_n, we now want to switch to the returned *controls stream from state_m forever.

A naive approach would be to proxy the stream of state_m through the stream of state_n. However, this approach would result in a long chain of states. Each state switch would result in one more state in the state chain, and the value produced by current state function would need be passed through the whole state chain before it’s actually used.

With the current design of Dew, what we should do instead is to return the state switch information, and use an additional runstm function to handle the switch outside of the state functions.

state1: params1 -> *observables -> *(?controls, ?switch)
state2: params2 -> *observables -> *(?controls, ?switch)
...

runstm : *(?controls, ?switch) -> *controls

Type expression ?typ is the option type of typ in Dew, with data constructors ?expr and ?? for Some (expr) and None respectively.

Since the state we switch to now can also switch to another state later, switch should have the type of *(?controls, ?switch), Here we run into recursive types again, so again we have to use an ADT.

In the code below, I also added support for state switch after the current frame. For better lifetime of the stream after the switch in that case, we would need to accept a thunk to instantiate the stream in the next frame, instead of an already-instantiated stream.

type ''a stm = Switch of *(''a stm)
             | SwitchAfter of (''a, () -> *(''a stm))
             | Value of ''a

runstm : *(''a stm) -> *''a

state1: params1 -> *observables -> *(controls stm)
state2: params2 -> *observables -> *(controls stm)
...

I won’t go into the details here about the difference of 'a and ''a in Dew, but ''a is just a normal type variable.

The runstm function could be implemented concisely.

let runstm state0 =
   let switchnow state =
      match @state with
      | Switch s -> s
      | _ -> state in
   let statefn = pre (fun ()->state0) nextstatefn
   and *(ret, nextstatefn) = dew ->
      let state = switchnow (@statefn ()) in
      match @state with
      | Switch _ -> assert false
      | SwitchAfter (v, s) -> v, s
      | Value v -> v, (fun ()->state) in
   ret

So far we’ve got a working state machine in Dew. The state machine is generic, nestable, and each state is represented as a simple function.

Animation with state machines

To test the expressive power of the state machines we just made, let’s consider use them to make some animations.

To make animations, we consider the following combinators.

lift : *''a -> *(''a stm)
map : (''a -> ''b) -> *(''a stm) -> *(''b stm)
concat : *(?''a stm) -> (() -> *(?''a stm)) -> *(?''a stm)
timed : num -> *(?''a stm) -> *(?''a stm)

lift lift a regular stream to a state machine stream, and map maps all values yielded by a state machine stream. timed truncate a given animation to a specified number of frames, where the end of an animation is defined by ??. Finally, concat concatenates two animations.

The implementation is fairly simple:

let timer () =
   let ret = pre 0 (ret+*1) in ret

let lift s =
   dew -> Value @s

let map f s =
   dew -> match @s with
   | Switch s -> Switch (map f s)
   | SwitchAfter (v,s) -> SwitchAfter (f v, map f s)
   | Value v -> Value (f v)

let concat a b =
   dew -> match @a with
   | Value ?? -> Switch b
   | Value ?v -> Value ?v
   | SwitchAfter (v,s) -> SwitchAfter (v, concat s b)
   | Switch s -> concat s b

let timed duration a =
   let timeup = timer () >= duration - *1 in
   map (fun x -> if @timeup then ?? else x) a

*expr as a unary primitive operator turns a value to a stream by repeating it forever. concat only introduces overhead before the former animation ends, and these animation combinators can be used with state machines together.

With the inclusion of recursive types and ADTs in Dew, I am satisfied with the expressive power of state machines we’ve got so far. However, I also see a problem with the state machines: it’s getting a bit too complex for such a basic thing. It is still an elegant datatype with a few powerful combinators, but it takes mental overhead to think whether we are dealing *(''a stm) or *''a. This is important because Dew is intended as a game scripting language, and I want it to be easy to use so the programmer can focus on the game content and have short iteration cycles.

A different approach is to get support from language level, and add a primitive stream operator for the state switch:

switch : *(''a \ *''a) -> *''a

t1\t2\..\tn is the new syntax I come up with for anonymous tagged unions. I like such syntax, since it can help to save keystrokes when writing a game script.

The difference of compiler-implemented switch than a user-implemented one is that the former one would not leave streams behind after the state switch.

Actually, I already have a related primitive operator softref in Dew now, but it’s not powerful enough for state switches.

softref : *bool -> ''a -> *?''a

softref takes a condition stream and a value, and keeps the reference to the value until the condition turns false. switch is strictly more powerful in softref in that, in addition to that we can get rid of the original stream after the state switch, we can replace the output stream with a new stream; whereas softref can only discard the original stream, and the output stream afterwards is useless.

An implementation of softref in terms of switch could be:

let softref cond v =
   switch (dew ->
      if @cond then ?v\
      else \*??)

Conclusion

It turns out recursive types are much more useful than I expected for some of the more complex situations. So I am going to implement ADT in Dew, along with some more datatypes. These datatypes are not exactly too difficult to implement; I only left them out for implementation simplicity. Additionally, I would replace the softref operator with the more powerful switch.

To be clear, state machines and animations are among the first things I’d think about when designing the language. I didn’t notice the problem previously because I got away with either (1) not needing the output of state machines, and using side effects of state machines instead; or (2) ignoring the performance issues of the naive implementation.

Actually, I didn’t expect I could do mobs in my first game. I thought it was hard, and planned to do an empty game world with only the player in it instead. After these thoughts, I’ve decided to do mobs right away — they are actually not difficult to implement with Dew, and they would make a much more alive game world.