A Lexical Mistake

Mention in this post refers to a different project than The Mention Programming Language based on Smalltalk. In fact, name was originally intended for a Smalltalk anyway and got reused twice privately before I was happy with the scope of the project (feasibility).

Also, this project was killed some time ago. I’ve moved onto other things and when I look into more Haskell programming I will not be resurrecting this project (I have some more practical ideas in mind).

In my last attempt at coding gamedev, Haskell style, I found my true enemy to be my inability to fathom the modeling of high level game objects in basic Haskell records. The problem was pretty simple, I’m either not yet good enough to figure out how to implement high level game objects in Haskell, or the task requires something closer to the Functional Reactive type frameworks. The same Functional Reactive Programming that I still, to this day, don’t really understand.

In theory I should probably just keep reading through my copy Real World Haskell, but I always like to have one gamedev project and one language that I’m working on. This doesn’t necessarily include any reading or minor experiments of course, but it does help to limit how thinly I spread my free time and it’s nice to keep the gamedev and language design cravings in check (plus, it’s kind-of a fun, strange kind of duo, really).

Since my Haskell game project was essentially killed a while back, that left me with some time to work on a some gamedev projects in Python. The premise was, high level language, good for modeling game objects and apparently a solid library lineup. Solid at least, until I realized that almost all of my games require one simple critical feature. Tools.

The odd reality of any serious game development is that, no matter how clever your game is, you still need the tools, in which all of the content is created and developing those tools is, in my experience, a very hardcore UI intensive process, which given the current state of UI frameworks in Python is well…not good. Actually, perhaps that’s not fair, GTK may have done the trick nicely, but by the time I’d figured out how much UI I felt was really necessary, it seemed like I shouldn’t have to develop yet more UI code for the in-game UI.

Oh… and the Mention programming language is on temporary hiatus due to the heavy usage of untested extensions to the lambda calculus and type theory. While I slowly learn the math skills involved in learning the type theory (not that there aren’t other benefits to be had from learning mathematics properly anyway), I figure its going to take me at least a year to get it fully on track again.

Moving On…

So now there I was… back in Haskell… the Mention language stalled… and no game development project in sight… So I came up with an idea. What if I put some of the ideas I had floating around, and put them all together as a game, a language, and something to keep me working through Haskell. I would be developing a game engine designed specifically to beat the crap out of Haskell’s concurrency—and my CPU too, I suppose—while I also designed a high level game object language to implement the actual, high level game stuff.

It wasn’t actually until I’d been working on the language for a couple of weeks, when I realized what I was actually trying to implement, however. This link should probably actually be old news to anyone interested in gamedev, but here it is anyway: Tim Sweeney’s POPL 2006 talk “The Next Mainstream Programming Language: A Game Developer’s Perspective” (PPT Slides, Scribd Slides, I couldn’t find the video of the talk again.)

In the talk, he covers quite a few of the practical qualities that a modern commercial game contain in lines of code, complexity, and so on, but the point that stuck with me the most was the section on Concurrency. I swear, it literally screams “HASKELL!,” and not just because Haskell is mentioned later on, either. What I didn’t realize at the time, was that I’d end up trying to pull off a solution to Sweeney’s challenge, rather than simply using Python or Ruby and keeping the games… non-concurrent (or semi-concurrent).

There is actually a little section on why he doesn’t like Haskell at the very end of the slides. I’d just like to point out (for those who don’t realize this) that they’re all mostly irrelevant concerns since they’re all solvable in about five-seconds-flat by anyone who has more than two months of experience with Haskell, or aren’t significant problems anyway (laziness is not a performance hog, and targeting GHC optimizations isn’t impossible, et cetera). Honestly, I actually think it’ll probably be the two months of experience that causes the most problems (i.e. the unpopularity), but that may not be as much of an issue either, as better learning materials emerge.

Three Languages, for a Good Computer Game

So I’ve mentioned Haskell, and alluded to a scripting language, and of course we also have our shader language. To start with, I’d like to point out that the shader language is only partially bound to the game language, and even then it’s an indirect link, courtesy of the abstraction layer that typically accompanies the rendering code—that’s engine side—thus, the shader language may either be a separate language project, or (as I’ll be using) a prepackaged solution like GLSL. Regardless, at the moment only the engine and the scripting language are important.

This brings us to the title of the post then, a game scripting language, and it’s a strange one too. The problem is actually not as simple as just dropping in any kind of scripting language. No, the engine is intended to push Haskell’s concurrency potential to the limit (even on tomorrow’s hardware), but for this to happen, the scripting language must not become a bottleneck in the process. Sounds simple, right… but what happens when you build a game that scales big, really big even—beyond Supreme Commander big—and now it’s the scripting language that’s trying to handle unreasonable amounts of data (in addition to the engine). I don’t want to force game programmers to rewrite high level game code back in Haskell, simple to make it fast enough, that’s the entire purpose of the scripting language.

The solution then is the same as in the engine, make it massively concurrent, just like that Tim Sweeney talk was implying. But, a presumably object-oriented language, with extreme concurrency can only really mean one thing—it has to be semi-functional, and support either the process-oriented approach (Erlang), or the same Software Transaction Memory as Haskell below it—I chose the latter.

From Smalltalk, To Software Transactional Memory

Given the requirement for a Software Transactional Memory, it might seem obvious to simply write a variant of OCaml or Lua, but my experience with Smalltalk demanded otherwise. I believe that the best design pattern for implementing games is the prototype pattern. There are only really a few languages that make this pattern the global design pattern for the language, and in my opinion, JavaScript isn’t really the language of choice for writing semi-functional code in.

What I’ve done then is to start from a basic Smalltalk messaging syntax (that’s about the only real syntax in Smalltalk anyway) and then extend it to a full, text only syntax, removing all of the class and inheritance features and lastly, removing the main source of side effects, mutable variables. The result is a semi-functional object-oriented programming language, exclusively applying Software Transactional Memory for mutable object state, and making heavy use of prototypes and delegation.

There’s actually quite a lot, going into the design of Fire, oh yeah, that’s the name of this little programming language, and it would be quite pointless to go into great detail, at the end of an already lengthy post. What I can promise however, is a complete language specification, for those who are interested in the precise definition of the language and core libraries. And for everyone else, I should be following up this post later with essays covering some of the challenges faced in the unusual design requirements of The Fire Programming Language.

Anyway, that’s basically the status update, or the plan at least. The Fire Programming Language does actually have a complete syntax already too, and the first draft of said syntax chapter in the spec is also almost complete. Any question or reservations about the project are more than welcome, either in the comments or by email, and lastly… This is a long term project, one which I suspect may take anywhere up to year or more, before it hits a 1.0. What I do expect though, is some alphas and betas ready within 6 months or so and I’ll be setting up some git (public) repositories over the next couple of months for anyone who wants to muck about with it or give feedback (and the spec will slowly appear on a pages section of this blog).

– Lorenz

During some of the early design work on the Mention programming language, I recognized that a fixed parser would be unable to deal with a great number of interesting language problems. Things like embedded SQL and other DSL language, or perhaps even a unit notation.

All of these things could be added into a syntax, I believe, with a carefully constructed extensible parser. Each extension would become a libraries (modules) adding or replacing function points in the existing parser later reusing some of them as part of the extended syntax. (The actual parser would be based on Parsec and other similar combinator parsers. OMeta is also related to this parser architecture.)

The problem with adding new syntaxes to a language isn’t just the parser implementation however. Most of the really tricky problems actually come from the rest of the tool chain. Things like the compiler, debugger, profilers, editor, and a bunch of other potential tools. It had become clear to me that I wasn’t just working on an extensible parser, but rather an extensible language, and that meant an extensible compiler architecture.

Basically I thinking about a completely extensible intermediate language, which would power a set of semi-extensible libraries for implementing the bulk of the tool-chain. These libraries will take the leg-work out of processing the source code, and will allow the tools to manipulate or interact with the code in its intermediate form (this includes editors and analytical tools). The only problem I saw was that I had absolutely no idea how to construct such an intermediate language, little own how to write tools and libraries to interact with it.

Anyway, recently I run into the latest (at the time) Steve Yegge post, with a somewhat inspiring discussion about the Prototype Pattern (The Universal Design Pattern). After musing about pattern (again) for a couple of days, it finally hit me, I had the architecture all wrong. This isn’t just some extensible compiler or parser…this was the Self programming language…redesigned, implemented and tailored for the task of compiler writing. The AST is simply a specialized variation of the Prototype pattern, or more succinctly, a compiler is just a constrained dialect of Self, designed for compiler tasks.

So this my proposal is this, use the prototype pattern for Mentions AST and build a framework of libraries and tools designed to aid in the maintenance and development of an AST and the compilers, parsers, debugger, et cetera, which depend on it.

There are already a few pitfalls that I can imagine coming out of this system. For one, a good namespace or typing system will probably be required to prevent name conflicts. That is, each extension or collection of extensions would add only private collections of attributes, while a smaller group of shared public attribute interfaces would be used to facilitate cooperation between extensions. And then there’s still the issue of expected behavior, which may be complicated by the potential for different combinations of compiler extensions to inadvertently interact in unexpected ways.

In any case, I believe that this will be one of the key features of the core Mention programming language and it may even make some of the more complicated features like type systems easier to implement and experiment with later on. At the very least, you can expect to see some follow up material on this when I start to get further into the implementation of the Mention.

– Lorenz

Over the past few months I’ve been putting together a collection of requirements, of sorts, for a new class of dynamic functional programming languages, a language that could provide powerful dynamic features on par with Smalltalk or Self (and JavaScript etc.), without losing some important features like laziness or strong static typing.

One of the requirements I keep stumbling across is the need for referentially transparent functions that are capable of interacting directly with mutable data structures. Yeah, the kind that, by definition, are not referentially transparent.

At first I considered using compiler attributes to mark a piece of code that interacts with side effects vs. code that doesn’t. Something like the IO/ST monads from Haskell but general enough any function can interact with mutable variables, not just ones returning a monadic value. Unfortunately any code that interacts with mutable variables may behave radically differently when not constrained by the full monadic infrastructure or some equivalent like strictness (Scheme and ML).

I believe the only useful solution is to define a new property of the code–read transparency–which allows us to recognize code that is referentially transparent on immutable data while also referentially transparent towards unchanging mutable variables.

The above definition depends on the equivalence property of values, which I define along the lines of “any two data structures are equivalent if they are functionally the same value, or they only contain mutable variables containing equivalent state.” Given a good equivalence for all primitives this allows us to easily check for all functions which could safely be called in our new semi-functional programs.

The original motivating example for this concept was to allow functions like show in Haskell to work with any arbitrary data structure, mutable or not. This would greatly simplify programs like interpreters, which could use many of the same functions as pure code, without having to use somewhat cumbersome combinators like the lifting functions and unboxing functions (readIORef, etc.).

An important thing to remember about this property is that, while many previously referentially transparent functions would now only be read transparent, when used only with pure functional data, they are in fact promoted automatically to fully referentially transparent functions. That is, they remain effectively referentially transparent if you don’t care about mutable state, or to put it another way–the functions become more flexible, not less so. Only when the implementation of a function relies on language features that prevent mutable data from being used would the more restrictive referential transparency be required (like lazily evaluated results, incorporating the read operation).

We don’t actually have to stop there either. Just because a piece of code isn’t read transparent, that doesn’t mean that it suffers from all variations of side-effects. There are still yet more shades of grey which we can use to limit the damage caused by bugs and side-effects in our software. A property like write transparency for code that reads and writes to mutable data structures but performs no IO could be equally useful, just as the ST monad in Haskell, which cannot perform IO is useful for working with mutable state.

Unfortunately while our little definition is a rather interesting take on the mutable state issue, there are some rather serious caveats we still have to consider. The biggest problem we face here is that, while a read transparent function can read from mutable variables without any reprimands, it cannot use the unread mutable variable in the result, unless it uses it, still boxed. That is, if we returned a result lazily, the result might be different depending on when the result was used, definitely not something we want, and the primary reason that mutable state in Haskell is limited to the ST monad et cetera.

More concretely, we can return new mutable variables (since the result would always be equivalent), use the results from reading a mutable variable so long as we read it strictly before the function returns, and finally we can return the mutable variable verbatim as part of the result (something Haskell can do also). If any language implemented mutable variables unboxed however, they would not be usable in last context however, and you would always have to read from them strictly, leading to somewhat less flexibility in the language.

One last thing I’d like to add. The above definition is strikingly similar to something that might be rigorously defined and explored, but for some reason I haven’t done so in this post. Well, for all intents and purposes, I wouldn’t know where to start, at least not yet anyway. If and when I apply this property in an actual language implementation however, you can be sure I’ll have a rigorous writeup of it and it will likely be part of the languages spec too.

– Lorenz