Lambda the Ultimate

We rarely use the scientific method even in computer science, and especially rarely in PL. We do not often practice science, as horrible as that may sound, we are mostly just PL designers, engineers, and (for the more formal of us) mathematicians.

Thankfully, our publication venues do not have rigid scientific contribution requirements (otherwise, nothing would get published). Is your idea interesting and novel? Even if everything was pretty much discovered in the 70s, you might have a new spin on how to use and combine multiple technologies, that would be a contribution. Just don't call it science.

I'm studying PL and games (but mostly PL and interactive applications, of which games are an example). The original poster could check out my latest paper submission on a DIY environment for game creation that aims at a higher ceiling then projects like Kodu. Be careful with things like functional reactive programming, they don't really handle discrete behavior that well; I'm currently looking at behavior-based programming abstractions to fill in the gap.

Very interesting paper; it also feels very reactive in nature. I wonder how you would encode long actions with it (something like walk_to_monster that spans many frames).

My objective is somewhat similar, but not visual (I wish to build a language based on text) and rather than focus on just one way of expressing game code I want two:
1. rules (time-based logic invariants, queries, however we may wish to call them) which work similarly to a reactive framework and which specify snippets of code that are all executed during one tick of the simulation loop
2. behaviors (coroutines, micro-threads, also this can be called with many names) which take care of those aspects that cannot be easily formalized in terms of "what to do during one tick" and instead need many ticks to execute properly

The glue to bind these two together is a lightweight event system where one of the two runtimes raises events and the other consumes them.

I am starting with syntax, typing rules and semantics, but if this thing has zero chance of being accepted anywhere PL-y then I wonder if formalizing it is a good idea or not...

When I look at it, I think it just isn't clear what problem you are solving. A little brown-nosing seems to help these days too. What about a paper with the title "Functional Programming to the Rescue: Actor based Reactive Programming made trivial in F#"?

[ This is a bit of a grudge. People have little time, I know that. But I sometimes come across a paper of which I am sure that the only reason it got accepted was because of the title. ]

Check out event calculus and other related work I mentioned earlier. EC is temporal logic that provides exactly what you say you need: events (instantaneous changes) + fluents (continuous behaviors, rules). You might find the vocabulary you need to describe your work in the aforementioned models.

A reactive dataflow model such as FRP, Lustre, or Esterel can also handle queries and tick behaviors, though these models don't always make it easy to share the results. E.g. functional reactive programming is rather poor for open composition, mostly due to its purity.

I am starting with syntax, typing rules and semantics, but if this thing has zero chance of being accepted anywhere PL-y then I wonder if formalizing it is a good idea or not...

Formalizing it is a fine idea regardless of whether it's considered 'new' or a small variation of existing models. Formalizing the model will bring you a lot of direct benefits, e.g. with regards to validating optimizations and cleaning up any messy elements in the model.

Ok, you sold me on formalization (your statement sounds suspiciously similar to something I read in Girard's Proofs and Types :D).

Fluents look like a way to express conditions that change over time, in a manner similar to what I wish to handle with my behaviors; the syntax I have seen in the papers you linked does not satisfy me, though; I see my designers producing something like that as quite difficult. Also, in a game you have lots of conditions that do not ever become false, like

ships_(t+1) = {s \in ships_t : s.Life > 0}

My belief is that fluents and a (pure functional) event calculus is very conveniently encoded monadically, while this other set of invariant conditions that I mentioned above can be encoded as rules on sets in a logic programming/SQL queries kind of way.

I will take some time next week to carefully study the material you suggested, though. Thanks.

Behaviors are frame-independent, so you would just invoke the "move to: monster" behavior and it would execute on each time delta to move the subject (according to its speed, which is combined with the time delta to compute displacement on each frame). The "move" behavior itself won't pass through until its objective is met (reaching the monster).

I see no point anymore to separate what you call rules and behaviors; i.e., a rule is just a coroutine that maintains its invariant. The harder challenge are discrete behaviors that have lasting effects (e.g., "hit by bullet" -> "die").

If you are into text, you should check out my older paper. This was done before I got behaviors, though.

Why are you worrying about formalizing your PL at this point? Designing it to be useful will be enough of a challenge. The point of formalization shouldn't be "to submit a paper to conference", you should get something useful out of it if you do it (like gained insight into a new novel PL mechanism).

Actually, hit by bullet -> die is easily encoded as:

state =
  monsters = {m : m \in monsters and m.hits = 0}
  bullets = {b : b \in bullets and b.hits = 0}

monster =
  hits = count{m : m \in state.bullets and collision(m,self)}

What I am worried about is encoding complex behaviors that span many frames; I still am not sure how you would manage behaviors which need to share their results to each other, like:

   let! nearest_target = reach_nearest_target
   match nearest_target_with
   | Planet p -> do! bombard_planet p
   | Resources r -> do! mine_resources r
   | Ship s -> do! fight_against s

unless you encode lots of temporaries inside the ship state that should belong only inside the scripted behavior...

While I share your view that formalization should have a purpose, my idea is that a good denotational semantics can be of great help for explaining (to me and my colleagues) what I am going to implement functionally, and it is interesting in a paper because it is a bit more succint and generally understood than code would be. Also, it is a good specification against which I will measure the second, imperative implementation.
About the fact that it is useful, well, I am rewriting a commercial game I had built in a more imperative fashion with this new system, and the amount of effort needed is very little in comparison; I am building this system to solve my own problems, not because I think it is neat :)

Hit by bullet is much more complicated. What if you have different kinds of bullets with different damages? I guess with behavior abstractions, we can easily deal with muti-frame behavior but discrete behaviors become more challenging.

Semantics are important and need to be described, but Greek will only get you so far, not to mention few people read Greek.

Well, my system for defining behavior was born exactly to model projectiles with different different behaviors. Not different damages, since those are trivial to implement with rules:

State = 
  Ships = {s : s \in Ships and s.Life > 0}
  Projectiles = ...

Ship =
  Colliders = {p : p \in Projectiles and collision(p,self)
  Life = Life - sum{p.Damage : p \in Colliders}

Something that is much harder to implement with rules is, for example, the fact that some projectiles may, upon impact, generate other projectiles or the fact that some projectiles are guided and not ballistic (and so require a steering AI) or other such conditions. That is what is easily defined by multi-frame behaviors with local state.

I'm not planning on using Greek much, mostly double square brackets and maybe a sigma for the current state; should look nicer than the source of the implementation, at least I hope so...

The harder challenge are discrete behaviors that have lasting effects (e.g., "hit by bullet" -> "die").

I imagine these are much easier in a collection-oriented discrete time model than in a continuous time individual behavior model.

But I do agree that it's been a challenge for me - not just the lasting effect, but also garbage-collection of defunct agents (that no longer maintain a relevant behavior). My own model has steered towards favoring a fixed number of behaviors (relationships between agents) per application, suitable for embedded systems and live programming but not so much for disposable monsters.

By somewhere you mean "anywhere" or "anywhere PL related"?

Would you suggest I submit this to software engineering conferences then?

I suggest you look at places first where you can submit this (and then write it with an angle which makes it interesting for that). Thing is, there has to be something interesting or new about it, and from your short description I cannot decide what that new or interesting quality would be.

But there are lots of comparable papers on LtU, but mostly they highlight the use a scientific language -or a newly developed language at some university. Maybe you should look where these were published. Even then it is often debatable, a Haskell paper sometimes is scientifically completely uninteresting but sometimes gets published because, well, I guess people sometimes want to know about implementations.

Anyway, you need to push it with an angle which makes it interesting/publishable for others. So if you go for PL, I would focus on implementation and performance; if you go for games, or functional languages, I would focus on evangelizing F#/light-weight threads and functional programming.

[ Anyway, take it with a grain of salt. I am out of science. So, I just know mostly from reading papers which got accepted what seems to work. ]

Well, the main points of this work would be:
a. ease of expressing concepts with this mix of different formalisms, which becomes clear when you compare this solution with doing the same thing with existing game engines
b. simplicity of the underlying system; very abstract, general-purpose, object-oriented game engines which are considered state of the art are huge and have non-trivial overhead: running a handful of customized game instructions requires too many supporting classes. At some point a specialized language becomes simpler to maintain than a ginormous class hierarchy
c. automated optimizations; by using techniques coming from physical query optimization we can implement many ad-hoc indices that are often hand-coded in games (projectiles and ships that collide, for example)

Does this angle seem reasonable?
The innovation is there, and as an (indie) game developer I would really love something like this. There are a lot of advanced applications of PLs, from monads to FRP to declarative goodness. Nothing outright revolutionary or new, though...

Hey, I want to help, but I am not sure I am the one you should ask.

Having said that, I think you still make it too complex. Dumb it down to something everyone in the audience grasps immediately [as research]. Like my "Functional Programming to the Rescue" title proposal, or "Declarative Style Games in F#"; i.e., just push that by doing stuff declaratively you can write complex games easily. (Or, you're doing very interesting research in making 'Declarative Style Games' possible on the .Net platform because current state of the art, well, sucks.)

After that, you maybe have the time to push your other points. Like mixing paradigms makes sense, _and_ it doesn't come at a run-time cost _since_ --insert your other points/performance metrics here--.

"Declarative Style Games in F#" sounds quite right.

Now I understand the need for simplification, in fact I'd like to follow this line of reasoning:

- current state of the art truly sucks, costs too much and is very error-prone
- declarative programming makes *most* game dev easier and faster thanks to automated optimization; double win here
- *only* declarative makes some things harder to express (namely state machines, AI and articulated behaviors); we need some help in the form of scripting/coroutines to avoid making two steps forward and one back

So the focus is on the declarative part, and coroutines come in only as a necessary addition to make declarative games feasible and not just an academic exercise.

Also, thanks a lot for the feedback. Invaluable. (Thanks to Sean too, you guys are great :D)

Ah well, might as well make a final comment.

*only* declarative makes some things harder to express (namely state machines, AI and articulated behaviors); we need some help in the form of scripting/coroutines to avoid making two steps forward and one back

I agree with the one step forward, two steps back comment. But stating that doing stuff declaratively makes things harder to express is a no-go. You'll immediately be fighting the functional (functional declarative is always better - even for state machines) and logical camp (Prolog is the best and only manner to declaratively describe AI.) You'll need other reasons.

Well, I understand your point.

I would not just "state that", since I'm afraid that would no be appreciated much by a reviewer, especially one who likes declarative languages. Also, I wish to state something less general, that is that there exists *some* programs which are not as easy to express declaratively. For this purpose, I have identified a set of examples where a declarative language works great and another set of examples where the declarative implementation is quite cumbersome; this second set of examples happily happens to be very easily implementable with coroutines. Also, my coroutines are functional and can be seen (by looking at their semantics) as a set of changing, temporary rules; indeed, the very same semantic function that formalizes the declarative rules can be used to formalize the coroutines, which clearly are interpreted as rules that change over time:

let behavior ship =
  script{
    let! nearest = find_nearest_enemy ship.Position
    do! while (distance(ship.Position,nearest.Position > ship.WeaponsRange)
                     (move_towards ship nearest)
    do! attack ship nearest
  }

can be expressed with rules by explicitly modeling the current state of the behavior and its parameters:

type Ship
   CurrentBehavior = Ref =
      Null => FindNearest
      FindNearest and Nearest <> None => ReachNearest
      ReachNearest and distance(ship.Position, nearest.Position) > ship.WeaponsRange => Attack
      ...
   Nearest : Ref = Behavior = FindNearest => ...

which is clearly more cumbersome and error-prone, especially considered that many behaviors are usually set-up by game designers rather than game-programmers, and thus require a syntax that is as intuitive as possible.

Sounds better?

Great, two pieces of code in a language I hardly know. The first snippet I think I recognize as vanilla F#; the second snippet, don't know, is that your extension?

Looks to me that both examples can be seen as instances of declarative descriptions: the first example by people in the functional camp (even though it reads very imperative, but, then again, so do monads), the second example by people who like rule based programs.

I would avoid using the word declarative for other purposes than whatever you implemented/want to achieve in F#, or what other people did likewise in other languages. As long it's not C/Lua, it's declarative.

Having said that, yah, you certainly have a case that the first example reads a lot better. But this is evangelizing F#, right? I distinctly remember seeing the let! and do! notation before.

[ Actually, I do think that -given the right venue- people will find these discussions on the merits of declarative programming interesting. ]

The first example is F# (monadic), and is actually pure functional code. Let! and do! are bindings, and 'm{ ... }' is like 'do' in Haskell.

The second example is my declarative extension, yes.

I'm not so sure that this really counts as evangelizing F#: the same thing could be done by building an appropriate extension to any other functional language (that supports monads for the coroutines part). It is more about expressing games cleanly with two formalisms, one for rules that define some invariants about the state and the other for behaviors that define some sequences of invariants that change over time.

Maybe calling one declarative and the other coroutines is not very precise, so I will probably stick with "rules/invariants" + "behaviors". Indeed, my behaviors are quite declarative, so that distinction may not be correct...

You could try CUFP, although I don't know how much in industry you are. It's cohosted with ICFP, which does publish proceedings and has an invitation for short reports on the use of functional programming. (But I imagine it's difficult getting in ICFP. Hmm, you missed the deadline for that.)

About (3), the coroutine mechanism is very similar to LUA's. You have yield, you have resume (you don't have create, that is implicit). My coroutines are built in F# with monads, so we have a mix of state monad and coroutines bound together in a single monad:

let coroutine =
  script{
    let! x = get_x // get x from the current state
    let y = f x // perform a regular, functional computation
    do! yield  // yield (will be resumed by caller)
    let! z = another_coroutine y // will correctly propagate nested yields to caller
    do! set_x z // write the current state
    return z   
  }

Coroutines will be suspended when they reach a "yield", or (if they timeout for a single tick) in proximity of a "let!" or "do!". Coroutines are resumed at each timestep, but the advantage of building everything with monads and meta-programming in general is that this system is much more customizable than LUA's coroutines or Python's generators (which are deeply ingrained into the VM). Also, F# is a compiled, statically typed, heavily optimized language; my tests show that the very same implementation of an interruptible function with F#, LUA, Python and C# (Python and C# use coroutines) shows the following performance results (millions of yields per second, same number of yields and same computations between yields):

F#  7.6
C#  5.8
LUA 1.2
Py  1.0

Also, type inference means that F# code looks quite like a scripting language, and as such it is a bit friendlier towards a designer; using C# and yields like Unity does has a similar performance profile but the code is far more complicated than a designer would appreciate in my experience.

Also, type inference means that F# code looks quite like a scripting language, and as such it is a bit friendlier towards a designer

I don't think type inference necessarily helps in this case. Aggressive type inference can lead to some pretty nasty error messages that might cause the hypothetical designer some serious frustration. Also, someone that's not much of a programmer may choose to omit type annotations in most or all cases if not forced to give them. Not only does this greatly impede the compiler's ability to give decent errors, it also makes it much harder for the next person (or the same person two weeks later) to understand the code.

Adding anything beyond a very simple type system is going to require some sophistication on the part of the programmer. Even with inference, the programmer still has to understand type error messages, declare algebraic data types, understand the value restriction (in the case of F#), et cetera. If that's not acceptable, some sort of optional or soft typing approach might be a better solution. Contracts might also play a role; Racket has quite a lot to demonstrate here.

though all the current scripts we have built for our current game with F# until now are yet to require a single type annotation. The experience has been so positive that we have just migrated the input system to our scripts and we will soon migrate the rest of the game logic.

We have not used any particularly advanced feature of the type system, not even parameterized types, since those are rarely used when writing scripts. Also, and this is very important, scripts are usually built by:
1. instancing some general script combinators that determine the shape of your script (think of it as a game pattern)
2. defining how the general script combinator accesses the state f the game
the importance comes from the fact that state accesses guide the type inference algorithm a lot, and they are built by hand with type annotations by whoever defined the game state.

It's a bit late, so I hope it sounds right in the browser as it sounded right in my head :)

Personally, I think that not requiring a certain degree of sophistication from their scripters would be an extremely foolish mistake for a game company to make. Many game companies do make this mistake and end up wasting a lot of resources on unmaintainable spaghetti code.

Ignoring the issue of type inference, staticly typechecked languages are much more compatible with productivity-boosting features such as intellisense. While they may require a bit more effort for scripters to learn, I think the investment would pay off quite a bit in the long run.

You may be right about using Racket-style contract system to acheive a certain level of software quality while not requiring as much sophistication from scripters.

From my personal experience, the game engine developers usually write a series of accessor functions for scripts that give scripters the possibility of reading/writing the state. These functions are often explicitly typed and grouped into large classes or records; for example:

type StateFunctions = { 
  get_state : Script;
  get_player_ship : Script;
  ...
  }

all scripts have access to a value of type StateFunctions, which has the exact purpose you suggest: Intellisense (huge productivity boosts happen here, especially for a reasonably complex game state). Also, final scripts are not that sophisticated that type inference (with the help coming from a lot of use from the above set of functions) fails too often. When it does, well, a developer who understands typing is sitting at the next desk :)