The proper place for objects in code

When I worked at Prover Technology I took part in projects that involved automatically generating code that had to be reviewable by safety engineers who were not software specialists. This highlighted a number of cultural differences between the software development crowd and other technically-competent people.

An interesting difference popped up when we discussed which Object-Oriented Programming (OOP) features would not be appropriate in the generated code. Virtual methods were one of the forbidden techniques, because reviewers needed to know what code would be executed through a function call, and dynamic dispatch made it unacceptably difficult.

Note that this was in the context of safety-critical applications, and typical assessments of costs and benefits of software development techniques may differ somewhat from other domains. With that being said, unexpected behavior from software is more often than not a bug, and bugs cost money. I don't think we should discard this kind of opinion just because "embedded/safety critical software is another beast".

The point of this anecdote is that what is considered acceptable or even desirable techniques by one group could be discarded by another equally intelligent group. That does not mean there is no objective truth, but rather that we should always question what our group considers as universal truth.

The rest of this post presents a widely accepted definition of object-oriented programming, my critique of its suitability, a short note on the comparison with functional programming, and finally alternatives to OOP.

Definition

I suppose the "oriented programming" part must mean that objects should have the central role. I think this video gives a pretty good definition of "objects".

To summarize, the four pillars are encapsulation, abstraction, inheritance and polymorphism. I personally object to the use of "abstraction" here because it's too vague. Let us look at each of the remaining three techniques, and why they can be problematic in certain situations.

Encapsulation

 Encapsulation, according to ChatGPT, is

the bundling of data and methods (or functions) that operate on that data into a single unit, often called a class in object-oriented programming. This unit restricts access to the internal components of an object, providing a clear interface through which other parts of the program can interact with it while hiding the implementation details. Encapsulation helps in achieving modularity, information hiding, and abstraction, which are important principles for building maintainable and scalable software systems.

In practice, for many developers 'internal components' and 'implementation details' often means data, and the means to achieve information hiding and abstraction is to use methods. 

In my experience, the shape of data is vital to understanding a problem domain. As such, it should have a central role in domain modelling. It should be easy to create and change a domain model as the customer's and the developer's understanding of the problem domain evolves.

I say that a data structure is loose when it does not effectively prevent invalid value representations. An example could be strings to represent integers, or using multiple fields to represent alternatives instead of using an union or a class hierarchy.

I think the need for encapsulation stems from mutable state, and loose data structures

Consider for example the following problem description.

A boolean expression is made of operands and an operator. The possible operators are negation (NOT), conjunction (AND) and disjunction (OR). Negation-based expressions must have exactly one argument. Other expressions can have any number of arguments (e.g. AND without arguments is the same as TRUE).

 A class-based implementation could be:

enum BoolOperator { Not, And, Or }
class BoolExpr {
  private BoolOperator _op;

  // Any number for And, Or. 1 for Not.
  private List<BoolExpr> _args;

  private BoolExpr(
            BoolOperator op,
            params BoolExpr[] args)
  {
    if (op == BoolOperator.Not && args.Count != 1)
      throw new ArgumentException("Not must have exactly one argument");
    _op = op;
    _args = args.ToList();
  }

  public static BoolExpr CreateNot(BoolExpr e) =>
    new BoolExpr(BoolOperator.Not, e);

  public static BoolExpr CreateAnd(params BoolExpr[] args) =>
    new BoolExpr(BoolOperator.And, args);
  ...

Another implementation, without encapsulation:

type BoolExpr =
    | Not of BoolExpr
    | And of BoolExpr list
    | Or of BoolExpr list

You could argue that the first modelling isn't the best OOP could offer. I picked it because it's not unlikely that it would in fact be picked in a real situation, and because it illustrates the need for encapsulation. Without encapsulation, the fields would be accessible to external code and the responsibility to enforce the restriction on the number of arguments depending on the operator would be left to the caller. This data structure is loose because it makes it possible to represent negations without arguments, or with multiple arguments.

The second implementation exposes its internals, but it also captures the domain precisely and concisely.

Inheritance

Inheritance can be used for two purposes: code reuse (a.k.a extension) and interface implementation. It's unfortunate that these two distinct use cases share the same terminology in C++ and C#. Inheritance for code reuse is hard to get right and in my opinion it should be avoided. This issue is well known so I won't expand on it here.

Below is an example of an excessively flexible collision and damage management system.

abstract class WithMutualDamageBase : ICollidable {
  public virtual void Collide(ICollidable other) {
    if (...) {
      var damage = this.CalculateDamageFrom(other);
      this.InflictDamage(damage);
    }
    if (...) {
      var damage = other.CalculateDamageFrom(this);
      other.InflictDamage(damage);
    }
  }
  protected virtual void InflictDamage(Damage damage) ...
  protected virtual Damage CalculateDamageFrom(ICollidable other) ...
}

The public method Collide offers some basic code that inheritors can override. It does its job by delegating the task of computing and inflicting damage to two other virtual methods.

This base class is excessively flexible. A subclass can choose to override any, all or none of the three methods. It can also choose to call the base methods in its overrides. A subclass of that subclass can do the same. Figuring out which method from which class is executed and when becomes detective work. Any change is likely to have unintended consequences.

It's not uncommon to see people give up and copy-paste code from abstract classes, and then modify the copy in the subclass as needed, which defeats the original purpose of inheritance and virtual methods.

Polymorphism

... is fine. No problem there. The only criticism I might have is that it's not specifically object-oriented. You can do it in C with function pointers. You can also do it in dynamically typed languages without bothering with virtual methods and inheritance. You can do it in functional languages using functions.

A short note on OOP vs FP

I put some effort into clarifying and justifying my understanding of the term "object-oriented programming" because debates about OOP vs functional programming (FP) tend to equate OOP with imperative programming (which relies on mutating data) and FP with immutability.

I think that's unfortunate because imperative programming predates OOP, and the additions of OOP brought on top of imperative programming are not all evidently positive. It's also unfair to claim that functional programming rejects imperative programming. The interest for the monadic do-notation shows that even the hardest supporters of FP see the stylistic benefits of imperative statements.

Everything shouldn't be a class

In practice, classes are ubiquitous and serve many purposes. As such when you look at a class it can be difficult to identify what kind of pattern, if any, it was meant to follow, initially. The result is that you easily end up with multi-purpose monsters that are several thousands of lines long.

They have too many fields and methods, and lack of clarity of the dependencies between methods and fields. Within the context of a class, each field has the same downsides as global variables in large procedural programs. See the source code of DataGridView in Windows.Forms for an example of what I mean. Over 100 mutable fields and 14000 lines of code. It's an extreme example, but not a rarity. All projects I have worked on end up with this kind of obese classes.

Here is a non-exhaustive list of purposes that are often not best served by objects and classes, although that does not imply that classes are always wrong in each situation. See my explanations.

Domain modelling

Use so-called algebraic data types, i.e. records and unions. Or the closest thing you have in your language of choice. If all you have is objects and inheritance, then so be it, but keep to that pattern. You can look at what the code the F# compiler generates from unions, and get inspired by that. For example:

/// A boolean expression. The different kinds of boolean
/// expressions are all implemented as nested subclasses.
abstract class BoolExpr {
  ...
  public abstract IEnumerable<BoolExpr> GetSubExprs();

  public sealed class NotExpr : BoolExpr {
    public BoolExpr SubExpr { get; }

    public NotExpr(BoolExpr subExpr} { SubExpr = subExpr }

    public override IEnumerable<BoolExpr> GetSubExprs() {
      yield return SubExpr;
    }
  }

  public sealed class AndExpr : BoolExpr ...

  public sealed class OrExpr : BoolExpr ...
}

 

Use immutable data-structures. It's however perfectly fine to use mutation and imperative code locally within a function.

If you need to expose mutable data structures across functions, see if you can divide the lifecycle of data into construction (write, no read from the outside), consumption (read, no write), disposal. 

 

Software should be designed like restaurants: separate the kitchen (construction), the service (consumption) and the garbage room (disposal).

Data transfer "objects"

Basically the same as domain modelling, even simpler. Immutable data structures, no functions needed.

Database querying and updating

I'm not a big fan of ORM frameworks due to the different nature of relational databases and complex objects. The point with objects is encapsulation and methods, whereas databases don't attempt encapsulation and have limited support for functions. It's also easy to load more than you need and intend from the database if you think in terms of objects, which causes performance issues.

Use the database's query language. Better, build your queries using syntax trees and expressions instead of strings. Some of the mainstream programming languages support that out of the box (e.g. C# and LINQ).

Data structures & algorithms

Use whatever you need for the performance required. Large amounts of objects are typically not performance-friendly, due to memory layout issues and indirection required by abstraction. And for that matter neither are immutable data structures. In this kingdom imperative programming and low overhead rule uncontested.

Hiding mutable state

The thing is, you can't. If state can mutate somewhere, other places in the code that rely on that state need to know, and their individual reaction needs to be coordinated, especially if further mutation follows as a result. There are ways to do that with events, but it can be difficult to follow the chain of handlers and the new events they trigger. Such chains can result in infinite recursion. A missed opportunity is that mainstream OOP languages do not provide the notion of transaction. I believe they would fit nicely in the world of objects.

Language features that aren't object-oriented

I'll take example of the C# programming language which was revised multiple times.

It was initially created to counter Java, a language whose design was directed by two principles: objects and simplicity. As such it lacked a number of things that we take for granted today, such as generics and lambdas. Much of C# that we use today did not exist. The language was centered to objects: classes, interfaces, events, properties.

C# 2 added generics, iterators and anonymous methods. None of these features are object oriented. On the contrary, they were introduced to alleviate some of the limitations of objects. Generics were added after much lobbying by Don Syme, who would later create F#. They bring value to statically typed objects, but the language design team behind C# and .net CLR did not see practical value in them. Iterators are a convenient way to create implementations of iterators, which are objects that are otherwise tedious to design and implement. Anonymous methods do the same as function objects, but in a less tedious way inspired from functional programming.

C# 3 added LINQ and expression trees, which are functional concepts (monads and abstract syntax trees). Extension methods allow to organize "secondary" methods, thus de-cluttering large classes that object-centered code organization tends to create.

I'm not quite sure that C# 4 was a positive development. Named parameters are useful to clarify confusing method signatures full of bools, which arise because optional parameters make it easy to write such signatures. I don't care about dynamic, and I know nobody who does. I won't fight OOP enthusiasts who wish to claim those additions.

C# 5 brought async and await, directly copied from F#, who implemented them using its own flavor of monads. Definitively a functional programming feature.

C# 6 introduced expression-based bodies. Guess what programming paradigm is based on expressions rather than statements...

I could continue, but there is a trend if you look at the history of C#. Each new addition falls into one of these categories: small syntax that is welcome by few and ignored by most, endless fixes for issues caused by null or other OOP constructs, and functional programming ideas first tested in F#.

Much of modern C# consists of moving away from its "purely OOP" Java origins.

Modules as objects

F# has modules but they lack abstraction in the sense that there are no module interfaces, no module implementations, and therefore no means to switch module implementations for e.g. the purpose of testing. The F# modules are basically static classes. C# doesn't have modules, but static classes are sometimes used for that.

A module is a collection of data types and operations operating on these types. Compare that with objects, which are data types with encapsulated data and operations operating on this data. These two definitions are similar, and I believe we should be using objects to implement modules.

Let's take the example of the interface of a module implementing a vector space. Using pseudo-code, it might look like this:

module interface VectorSpace {
  using Scalar as S;
  type Vector;
  Vector getZero();
  Vector operator+(Vector, Vector);
  Vector operator*(Scalar, Vector);
}

Translating this to C# is straight-forward:

interface IVectorSpace<S, V> {
  V GetZero();
  V Add(V v1, V v2);
  V Mult(S k, V v);
}

An implementation:

class VectorSpace3d :
  IVectorSpace<double, VectorSpace3d.Vector> {
  public record Vector(double x, double y, double z);

  public Vector GetZero() => new Vector(0, 0, 0);

  public Vector Add(Vector v1, Vector v2) =>
    new Vector(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z);
 
  public Vector Mult(double k, Vector v) =>
    new Vector(k * v1.x, k * v1.y, k * v1.z);
}

Other implementations could use arrays and take advantage of SIMD, use 32-bit floats instead...

Notes on creating large landscapes in Unreal Engine 5.3

I'm currently working on my next project, a skiing VR game using Unreal Engine. Note there's no .net or F# involved in this post.

The process of creating a large landscape in Unreal Engine 5.3 wasn't a smooth experience for me for the following reasons:

• Shadow issues when moving around the terrain. Someone else has encountered that problem and described it here.
  

• Low-resolution textures, even after increasing the streaming pool size
• Falling through the floor, or missing landscape sections

The first issue I can't seem to fix. The other two issues were due to a bug or lack of precision in the mechanism that loads and unloads far sections of the landscape, and I fixed them as described in the rest of this post.

Create new open world level

You can also create an empty level, but the open world template level has atmosphere and light already set up.

Import landscape from heightmap

To do this, switch to landscape edit mode, go to the manage tab, choose to create a new landscape, select heightmap file to import.

Side note: Use The Gimp to edit heightmaps, it can work with 16bit graylevel PNGs, which Unreal can use. Be careful to avoid software that is limited to 8 bits per color component such as Paint.NET. It's not suitable for manipulating heightmaps.

Delete initial landscape

To do this, you must be in selection mode, select all proxys under the landscape node, delete them, them delete the landscape node itself. One would expect that selecting the landscape node and deleting it would take care of the subnodes, but that doesn't work.

Set up world partition grid

A world partition grid controls how actors are loaded and displayed as the view point approaches them. By default, it's set for a small landscape. In particular, the range outside of which landscape components are not loaded is set to less than 1km by default. Initially, I didn't notice because the HLOD system (see below) filled in outside that range, but there would be issues with low quality of textures, lack of physics (the controlled character can fall below the ground) and issues with shadows.

In the world settings, create a grid with suitable sizes, i.e. a kilometer or so (1e5 units) for the cell size and a multiple of that for the load range. Name that grid something suitable, e.g. LandscapeGrid.

Use that grid for the imported landscape.

Build hierarchical levels of detail (HLODs)

Landscape proxy nodes are loaded and displayed according to the world partition grid. Nodes that are outside the loading range can display simplified meshes and materials instead to fill in the empty space and avoid mountains popping up suddenly as the view point moves forward. The problem is that since version 5, the editor creates the simplified mesh using the most detailed level of detail, i.e. LOD 0.

To work around this issue, in the LOD settings, set the screen size of the LOD 0 to something coarse, e.g. 1 instead of 0.5. This will (temporarily) force LOD 0 to a level of detail that would normally be more suitable for something like LOD 2.

Delete and then build the HLODs

Reset the LOD 0 screen size back to the smaller value (e.g. 0.5).

I got these steps from the video below.

An alternative is to delete the HLODs and force loading of all landscape proxy components. In my case, I don't see any benefits in using HLODs, although that might change as the project advances, I suppose.

A conversation with OpenAI's ChatGPT

I'm a bit late to the party when it comes to trying out ChatGPT. After seeing a somewhat provocative tweet on the subject of ChatGPT's effect on a programmer's productivity which basically claimed "use it and get 10 times faster, or don't and be pushed out of a job by the programmers who do", I decided I had to give it a go.

I have a number of concerns regarding the use of ChatGPT to boost one's productivity. Such as, if it's really valuable as a tool, and only the top five or so most popular languages are supported, is it going to kill less popular languages such as F#? A commonly cited obstacle to adoption is that it suffers from "weaker tooling" than e.g. C#. Also how valuable really is ChatGPT?

I asked ChatGPT to explain the following few but non-trivial lines:

    let rec private isHeap cmp (heap : Heap<'a>) idx =

        let count = heap.count

        if idx >= count then true

        else

            let left = 2 * idx + 1

            let right = 2 * idx + 2

            (left >= count || cmp (heap.arr.[idx], heap.arr.[left]) && isHeap cmp heap left) &&

            (right >= count || cmp (heap.arr.[idx], heap.arr.[right]) && isHeap cmp heap right)

 Here is what the AI had to say:

This is a recursive function in F# that checks whether a given data structure is a valid heap or not. The function takes in two arguments: cmp, which is a comparison function that returns a Boolean value indicating whether the first argument is less than or equal to the second argument; and heap, which is a generic data structure of type Heap<'a>, where 'a is a type parameter representing the type of the elements in the heap. The third argument idx is the index of the current node being evaluated in the heap.

The function starts by checking if the current index is greater than or equal to the count of elements in the heap, and if it is, it returns true, which indicates that the rest of the heap is valid.

If the current index is less than the count of elements, then the function calculates the indices of the left and right children of the current node and evaluates the following conditions:

1. If the left child index is greater than or equal to the count, then the left child does not exist and the condition is true by default.

2. If the left child exists, then the function checks if the comparison of the current node and the left child using the cmp function is true, and if it is, it recursively calls the isHeap function on the left child. If the comparison is false, the function returns false.

3. The same process is repeated for the right child, with the only difference being that the index of the right child is used instead of the left child.

The function returns true if both conditions for the left and right children are true, which indicates that the current node and its children form a valid heap.

I was impressed it managed to recognize that cmp is a comparison function, and also recognized the algorithm as a whole. It also managed to recognize the purpose of the generic type parameter 'a. To verify that it really "understood" what we were talking about, I then asked where was the minimum element located in such a heap.

 

In a binary heap, the minimum element is always located at the root node, which has an index of 0 in an array representation of the heap. In this code, the root node is represented by the element at index idx in the array heap.arr where heap is the Heap<'a> data structure passed as an argument to the isHeap function.

 

Correct again. But a bit unspecific, maybe. Then I got curious if it could find a bug. Over the years, I discovered and fixed a couple. My confidence in my code there isn't very high.

Yes, there is a bug in the code you submitted. The comparison function cmp is used to compare the values of two elements in the heap and determine their order. However, in a binary heap, the order of the elements is defined by a specific property such as the minimum value, maximum value, or the order of the elements in the original array. The code only checks that the parent node is less than or equal to its children, which is not necessarily the correct comparison for all binary heap data structures.

For example, if the comparison function cmp is checking for a min-heap, then the comparison should be cmp (heap.arr.[left], heap.arr.[idx]) and cmp (heap.arr.[right], heap.arr.[idx]) instead of cmp (heap.arr.[idx], heap.arr.[left]) and cmp (heap.arr.[idx], heap.arr.[right]), respectively.

 

That got me really scratching my head, because I could not find that I should follow its advice. I ask it if it was sure

I apologize, my previous statement was incorrect. The code as written is actually checking if the parent node is less than or equal to its children, which is the correct way to validate a min-heap. The condition cmp (heap.arr.[idx], heap.arr.[left]) checks if the parent node is less than or equal to its left child, and the condition cmp (heap.arr.[idx], heap.arr.[right]) checks if the parent node is less than or equal to its right child. If these conditions are both true for each node in the heap, then the heap is considered to be a valid min-heap.

Ah, that's better. But why did it give me an incorrect bug suggestion with such confidence? I asked it and got a rather generic answer about language models.

ChatGPT: As an AI language model, I sometimes make mistakes in my responses, even though I have been trained on a large corpus of text.

Me: Is it correct to say that me asking you if there was a bug lead you to answer yes, because many conversations about bugs start that way?

ChatGPT: Yes, that is a possibility. As an AI language model, I am trained to recognize patterns in language and respond based on those patterns, but I don't have the ability to understand the context of a conversation or the intention of the user. In this case, my response was influenced by the common pattern of asking if there is a bug in code, and I made an assumption that the code provided had a bug. This highlights the importance of providing clear and concise information when communicating with an AI language model, as well as the limitations of AI technology in understanding the nuances of human language.

But even that answer makes me wonder if ChatGPT isn't just guessing what "I want to hear" and delivering that.

My initial conclusion is that ChatGPT may indeed be incredibly useful as a learning tool, and as an assistant as well. I've noticed I've been putting off some hobby projects because of my unwillingness to learn new APIs and tools during my free time, but perhaps ChatGPT could help me with that.

 

A type provider for IL-2 Sturmovik: Great Battles

Something that would have fit well in this blog is my work on writing a type provider for the mission files of combat flight simulator, IL-2 Sturmovik: Battle of Stalingrad. This game is the first in a series called IL-2 Sturmovik: Great Battles. The series is a reboot of a similarly named very popular game that came out at the turn of the century, I believe. One of the aspects of this game that I like the most is its mission designer, and the file format it uses, which is textual and pretty easy to understand.

The mission designer uses a graph of nodes, where each node can react to the environment or activate AI-controlled objects or visual effects. Each node is positioned in 3d in the game's world, and can be connected via directed edges to other nodes. The expressiveness of this simple system is pretty interesting. There are few node types, all with very simple behaviour. You can do pretty much anything, but not always very easily. Part of the problem is that there is no way to build abstractions and compose them. Copy-paste is your only approach to generate complexity. Although it is possible to create libraries of graphs, once such a group is used, it instantiates a copy of the group. If you change a group in the library, you have to manually find all copies, remove them and reconnect them in their environment. Tedious, as you can guess.

It was natural for a programmer like myself to develop ways to address that, for instance by using F# to generate graphs. There is still value in using the graphical mission editor, if only to put the location-sensitive nodes in the right place. It would therefore be nice to combine programmatic generation with the mission editor. One way to do this is to use the mission files produced by the editor, and to use them to guide the programmatic generation process.

If I remember correctly I looked into the mission file format and how to parse it during Easter 2015. I got going pretty quickly, and it looked like I could make a parser in a week or so. It was a rather tedious job though. I wrote that there were few types of nodes, but it still takes time to handle the 40 or so that are there. They all use a very similar syntax, but with different fields. For instance a timer node has a field for the timeout value, a counter has a field for the max value and whether it wraps around to 0 when the max value is reached. They also share fields for the connections to other nodes, the name of the node and so on...

I set upon using an automated process to infer the fields of all the nodes, using an example mission file that makes use of most of the nodes. The parsing and the inference system were fast enough that I did not need to store the generated parser in generated code. There is an old entry on this blog on parsing 3d models that deals with combining functions that can parse individual bits of data (block delimiters, strings, numbers...) according to a schema and generate a function to parse to whole file. It's the same approach here, except that the schema is inferred from an example.

To represent the inferred types and the values produced by the parser, I used recursive discriminated union. This is nice, but consuming these values would always require match expressions, and what to do when the shape of a value is not what's expected?

type ValueType =
    | Boolean
    | Integer
    | String
    | Float
    | Composite of Map
    | Mapping of ValueType // { 1 = XXX1; 2 = XXX2 }
    | List of ValueType // { entries }
    | IntVector // [1, 2, 3]
    | Pair of ValueType * ValueType
    | Triplet of ValueType * ValueType * ValueType
    | Date
    | FloatPair

type Value =
    | Boolean of bool
    | Integer of int
    | String of string
    | Float of float
    | FloatPair of float * float
    | Composite of (string * Value) list
    | Mapping of (int * Value) list
    | List of Value list
    | IntVector of int list
    | Pair of Value * Value
    | Triplet of Value * Value * Value
    | Date of int * int * int // Day, month, year

It was natural to use a type provider for that. I chose erased types at the time, because it seemed that generative type providers weren't really ready for prime time. It was rather easy, using the unions I mentioned above as underlying types. The solution worked well enough, and I've used that type provider in a number of projects to generate missions with graphs of such complexity that they could not be handled manually in the editor.

The game is primarily a WWI and WWII combat flight simulation, but it also includes ground vehicles: mobile rocket artillery, armoured cars, tanks... I made a mission that could turn the game into a sort of real-time strategy game. Using a web interface, players could take control of platoons and direct them. As mission files are static things, it means I had to pre-generate every possible commands. The web interface would simply pick the command to execute among those. Typical commands were travel N/E/S/W off-road, travel to villages on roads, stop, set fire policy, speed. The graph needed to cover all these had over 10000 nodes.

The mission logic allows you to send convoys of vehicles to specific destinations easily, but a problem shows itself when convoys reach destroyed bridges. As destroying bridges is one of the players' favourite things to do, this problem would show itself often. The problem is namely that the convoy will simply attempt to cross the bridge, and fall down into the river and drown. It is possible to write graphs to handle detection of destroyed bridges and react accordingly (typically stop), but it's non trivial, and must be repeated for every bridge. I have used my type provider to read a template graph that implements bit of the stop-at-bridge logic.

Much of the fun flying online with and against other players relies in the mission design. There must be ground targets, some well defended, others less. Some of these targets should be large and static, to be bombed by level-bombing bombers, others small and moving, to be strafed by nimble low-flying fighter-bombers. A common problem is that players get to know these missions pretty well after playing them several times, which can become monotonous, or turn into a silly race to the well known targets. Moreover, all the struggle to attack and defend targets results in a match win or loss. When a mission ends, the next one starts, and each mission is fixed as made by the designer. Some variation can be achieved with randomly activated targets, but always within the limits of the imagination and efforts of the mission designer.

To counter this, I have built a system where missions are generated automatically, and the result of a mission is used to generate the next missions. Buildings that have been bombed in one mission remain destroyed in the next mission. Buildings have strategic value, and their destruction feeds a complex ground war simulation that decides the conquests and losses of each side. As missions are played, airfields are conquered, and a sense of long-term achievement is felt after each successful flight. It is a step away from what virtual pilots sometimes call "air quake", never-ending dogfights without purpose.

The type provider is available at https://github.com/deneuxj/SturmovikMission and was recently converted from using erased types to generated types. This was a not entirely painless process that I intend to write about on this blog.

Type providers confusion lifted

... at least partially. After looking at the FSharp.Data library and its source on github, I found that the Json type provider clarified the most important point. Namely:

I'm not sure if this design-only type has inadvertently "leaked" into the runtime, or if any code used by the type provider must be present in the run-time component.

It is not the case that all code in the type provider in the design-time component needs to also be in the run-time/reference component. I'm not entirely sure what was the problem in my code, but an AutoOpen attribute on the internal module containing utility types in the type provider might have been the culprit. In other words, the design-time component can use any crazy library you might find useful to generate the code. As long as it's not also used in the generated code, you won't need to have the run-time component include the crazy library in its dependencies. Nice!

Another potentially valid use case I've encountered is to avoid generating code at all when the design-time component is being used by and IDE, for auto-completion. Considering the kind of responsiveness requirements this use case has, leaving out complex generated code is probably a good idea. I'm not sure if that's supported by the existing framework. It sounds like it's something that TypeProviderConfig could take care of, and maybe that's what IsHostedExecution is for.

That's not what IsHostedExecution does. It tells you whether to use the resolution folder at run-time.

Frustration with type providers

I'm currently in the process of trying to port my type provider for IL-2 Sturmovik: Great Battles missions. It's a rather frustrating experience, so here is me ranting about it. Maybe writing down my thoughts will help clarify them, and might also help other people who are also feeling confused.

Type providers have always confused me a bit, maybe because one must keep in mind the boundary between code executed by the compiler, and the generated code which is executed by the application using the type provider.

There is an SDK to develop type providers that contains a number of helper types and functions for the generation of code, but I find it rather hard and confusing to use. The template it offers creates two projects, one called Type Provider Design-Time Component (TPDTC), and another one called Type Provider Reference Component (TPRTC) in the documentation.

Confusing point 1: The acronym does not match the name! Why the extra T in TPRTC?

Confusing point 2: The template uses a different terminology, "Run-time Component"

Wait a second, that must be it: TPRTC really stands for Type Provider Run-Time Component

Those acronyms are a mouthful, and have too many repeating consonants. I don't like them.

Confusing point 3: What is the reason for the need to have two different components?

One important bit of information that's missing from the documentation of the SDK is why you need the two assemblies. I would have thought that the purpose was to avoid including the burden of the types used by the host tool (compiler, F# interactive, IDE), but I'm not sure. If I try to keep my runtime with the bare minimum, I easily run into this kind of error message:

error FS3033 : The type provider 'SturmovikMission.DataProvider.TypeProvider.MissionTypes' reported an error : The design-time type 'SturmovikMission.DataProvider.TypeProvider.Internal+InvokeCodeImplementation' utilized by a type provider was not found in the target reference assembly set

I'm not sure if this design-only type has inadvertently "leaked" into the runtime, or if any code used by the type provider must be present in the run-time component.

If it's the latter, then it means that all design types must be included in the run-time component, and of course all the run-time types used in the generated code will also need to be included in the design-time component. Much code duplication there, something that rings many alarm bells in my head.

One reason to have two different components, or should I say assemblies, is dependencies on other assemblies. The ones available to the host tool (say, the F# compiler) are not necessarily the same as the ones available to the consuming application. I can see cases where the building environment is more feature-rich, say when building an app supposed to run on an exotic device, or less feature rich, e.g. when building with an old version of Visual Studio. I'm, not sure this needs two different F# projects, but sure, it's one rather easy way to do it.

I'd still like to know if the use case I had in mind is valid. For a concrete example, consider for instance that you want to a logging library such as NLog to follow what's going on when the compiler is executing your design-time component. You probably don't want to also include NLog as an implicit dependency in the consuming applications. Some of them might already use a different version of NLog, and having the two coexist is going to cause problems.

Another potentially valid use case I've encountered is to avoid generating code at all when the design-time component is being used by and IDE, for auto-completion. Considering the kind of responsiveness requirements this use case has, leaving out complex generated code is probably a good idea. I'm not sure if that's supported by the existing framework. It sounds like it's something that TypeProviderConfig could take care of, and maybe that's what IsHostedExecution is for. But the comment refers to FSI, does it also apply to the consuming applications that use the type provider?

Confusing point 4: What does TypeProviderConfig.IsHostedExecution do?

"F# Deep Dives" is out

Tomas Petricek gathered a team of authors to write a book about practical uses of F#. The result is "F# Deep Dives",  published by Manning.

I contributed a chapter about programming games using XNA. It demonstrates a number of techniques, using a simple missile-interception game.

The complete source code is available on github.

Understanding variance using functions

Statically typed languages that support parametrized types (generics) and types hierarchies (inheritance) sometimes support covariance and contravariance, concepts which many find confusing.

I think I have finally understood these, thanks to a blog post by Tomas Petricek on the subject.

In this post I'll try to formulate my own understanding, and how I got there using functions instead of classes.

Step 1: values

Let us start easy, with simple values. Consider a base type, for instance IPrintable, and two derived types MyString and MyInt.

I can use a string with any function that accepts a printable object.

type IPrintable =
    interface
    end

type MyInt() =
    interface IPrintable

type MyString() =
    interface IPrintable

// Step 1: simple value
let ``expects an IPrintable``(x : IPrintable) = ()

let n = MyInt()
let s = MyString()

``expects an IPrintable`` n // OK
``expects an IPrintable`` s // OK

Step 2: Parameterless functions

The next step deals with a function that takes another function which doesn't take any parameter and returns an IPrintable. If that's confusing, think of a generic function that creates a new random printable object, then prints it. This function would let the caller be responsible for providing a function which creates the random printable object.

The code below illustrates this, but I've removed the random part. Note also that F# does not support covariance, which forces me to use flexible types.

// Step 2: a function without arguments
// No covariance in F#, see http://msdn.microsoft.com/en-us/library/dd233198.aspx
let ``expects a constructor``(f : unit -> #IPrintable) = ()

let mkInt() = MyInt()
let mkString() = MyString()

``expects a constructor`` mkInt // OK
``expects a constructor`` mkString // OK

Step 3: Functions of a single parameter

Let us now consider a variation of the function described above where the function responsible for creating a random object takes a MyInt (it could be the seed, for instance). Assume I have two functions newRandomMyIntWithSeed and newRandomMyStringWithSeed that both take an IPrintable. Importantly, these two functions are safe to call with any instance of IPrintable. One can imagine that such a function would use the printable representation to generate some number, used as the seed for the random generator.

I can use newRandomMyIntWithSeed and newRandomMyStringWithSeed where a function with signature MyInt -> IPrintable is expected. Notice how the relationship on types for the parameter has been inverted, compared with the case of a value or a return type. This is an example of contravariance.

No code here, but see below for a more complete example.

Step 4: Functions of multiple parameters

It's possible to keep adding more parameters, and currying helps understand which functions are safe to use.
For this last example, I'll switch to another set of types: IScalar and IVector, with their respective implementations Float32 and Vector3. We can imagine there might be other implementations, e.g. Float64 and Vector4. A function which computes the product of a scalar and a vector must return a vector. Using currying, it can also be seen as a function takes a scalar and returns a function which takes a vector and returns a vector.

If I have a function with signature Float32 -> Vector3 -> Vector3, where can I use it?

I can use it where the exact same signature is expected, obviously.

I can use it where a Float32 -> Vector3 -> IVector is expected:

• The final return types match, as shown in step 1.
• The other parameters obviously match.

I cannot use it where a Float32 -> IVector -> Vector3 or a Float32 -> IVector -> IVector is expected. Although the final return types are compatible in either case, the next step in the matching process fails.

A more general function with signature IScalar -> IVector -> Vector3 can be used where a Float32 -> Vector3 -> IVector is expected:

• Vector3 as a simple value can be used anywhere any IVector is expected.
• A function accepting any IVector accepts in particular Vector3, meaning such a function can be used where a function expecting a Vector3 is expected (!), provided their return types match (which was shown above).
• By the same reasoning applied on the first (and only) argument of the function with signature IScalar -> (IVector -> Vector3), we conclude that the more general function can be used.

The code below illustrates this example.

// Step 4: a function with arguments
type IScalar =
    interface
    end

type IVector =
    interface
    end

type Float32() =
    interface IScalar

type Vector3() =
    interface IVector

let prodGeneral (s : IScalar) (v : IVector) : Vector3 =
    failwith "..."

// Interesting: flexible types are needed for the return type (no covariance),
// but not for the parameters (contravariance)
let apply prod (s : Float32) (v : Vector3) : #IVector = prod s v // OK

let k = Float32()
let v = Vector3()
let u = apply prodGeneral k v

Conclusion

I hope that wasn't excessively complex. Other explanations on the subject which I have seen often use container classes instead of functions, which is confusing, as it brings in read-only vs writable and reference-type vs value-type into the picture. Another problem is that using containers tends to mislead readers into thinking that T<B> can always be used where T<A> is expected if B inherits from A. Although that makes sense when T is IEumerable, it doesn't work when T is Action.
Looking at the problem with a functional mindset really helped clarify the picture.

I was a bit disappointed when I first saw F# did not support covariance, but flexible types do the job with very little additional syntax (a single # before the type). I was surprised to notice F# does support contravariance for function parameters, as it's often heard that F# supports neither covariance nor contravariance. That's not quite true, as it turns out.

If functions are powerful enough to model all other types, it may be interesting to see what kind of variance one should expect for unions, tuples, records and eventually classes. That's probably already been done, but it would be an interesting exercise.

Recursive descent parsers using active patterns, part 2

In the previous post, I presented a method to implement a parser relying solely on core F# features, namely active patterns.
In this post, I'll touch on some of advantages and limits of this approach.
Recursive descent parsers are limited to LL(k) grammars, which means that left-recursive grammars cannot be directly handled. It is necessary to rewrite such grammars to remove left recursion.

Consider the common problem of parsing expressions, e.g. Boolean expressions. A typical formulation of the  grammar could be:

Expr := AndExpr | OrExpr | NegExpr | Variable | True | False | "(" Expr ")"
AndExpr := Expr "AND" Expr
OrExpr := Expr "OR" Expr
NegExpr := "~" Expr | Expr

Note there is an ambiguity, as "A AND B OR C" could be parsed as (A AND B) OR C or as A AND (B OR C). In order to lift this ambiguity, priorities can be assigned to rules. Similarly for associativity, allowing to parse "A AND B AND C" as (A AND B) AND C or A AND (B AND C).

Such a grammar, if implemented naively using a recursive descent parser, would loop endlessly on some inputs: The parser would try to match rule AndExpr, which would try to match Expr, which would again try to match AndExpr...

An alternative formulation of the grammar can be used that will generate semantically equivalent results

Expr := OrExpr
OrExpr := AndExpr "OR" OrExpr | AndExpr
AndExpr := NegExpr "AND" AndExpr | NegExpr
NegExpr := "~" AtomExpr | AtomExpr
AtomExpr := Variable | True | False | "(" Expr ")"

Note the hierarchy between Expr, OrExpr, AndExpr, NegExpr and AtomExpr. The left-most rule appearing on an alternative in the right-hand side of each definition is always a "lower" rule: Expr refers to OrExpr, OrExpr to AndExpr, AndExpr to NegExpr, NegExpr to AtomExpr.
AtomExpr refers to the higher rule Expr in "(" Expr ")", but that's OK as Expr does not appear as the left-most rule (the token for a left parenthesis does).

What I like with this formulation is that it captures both associativity and operator precedence within the system of rules.

It is common to split parsers into two stages, using a lexer that processes the input stream in linear time, producing a pre-digested stream of so-called tokens. While this has undeniable advantages when it comes to performance, it prevents composing grammars and rule-specific tokenization. This is why most languages have keywords reserved for future use, and this also explains why you can't use identifiers that are also keywords even in situations where no ambiguity arises.

For these reasons, I personally prefer avoiding the separate lexing stage if performance constraints allow for it.

Regarding performance, it's important to write a recursive descent parser in such a way that decisions on the rule to try can always be done looking at a finite number of tokens.

In the example below, the second implementation performs significantly better:

let (|OrExpr|_|) s =
  match s with
  | AndExpr (e1, Token ("OR", OrExpr(es, s))) -> Some (e1 :: es, s)
  | AndExpr (e, s) -> Some ([e], s)
  | _ -> None

let (|OrExpr|_|) s =
  match s with
  | AndExpr (e1, s) ->
    let rec work s es =
      match s with
      | Token ("OR", AndExpr(e, s)) -> work s (e :: es)
      | _ -> (List.rev es, s)
    let es, s = work s []
    Some(e1 :: es, s)
  | _ -> None

To see what happens, consider the input "~X". This is a "degenerate" OrExpr with a single term. The first implementation will go all the way down through each rule to identify a NegExpr, promoting it to an AndExpr, then will look for "OR", which isn't there. The first match case will therefore fail, and the second will be tried, redoing the work. The same problem exists at all levels in AndExpr, NegExpr and AtomExpr. What makes matters worse is that this kind of "degenerate" case is actually the normal common case in typical expressions.

The second implementation uses the functional equivalent of a while loop, going as far as possible. The trick here is to factorize common prefixes into a single branch, thus avoiding redoing the work in case of a match failure.

An important problem with my simple example code is the lack of error messages. Those are important from a usability point of view, but I'm currently not too sure how to do this with manually-written parsers.

To summarize, using this technique requires some amount of manual work, which is the price to pay for not using smarter parsing frameworks. I wouldn't advise it over using parser generators, but it's interesting nonetheless. I can see it having uses for extremely small grammars, for instance when parsing fragments in a document. Otherwise, go for a parser generator such as fslex+fsyacc or ANTLR (which generates recursive descent parsers), or combinator-based parsers such as FParsec.

Recursive descent parser using active patterns

Today's post isn't specifically about games, but about parsing, which I find is a recurring task in many programming tasks, including game-related tasks.

In F#, the most popular methods for writing parsers are FParsec and fslex/fsyacc. Although parser generators are very useful, I'm always a bit reluctant to depend on third-party software.

In the past I have worked on a development tool for safety-critical systems, which was itself subject to some of the limitations of software for safety-critical systems. In particular, the use of lex and yacc was not accepted.

I fell back on a technique suitable for hand-written parsers, namely recursive descent parsers. I was positively surprised by the inherent simplicity of the method and the clarity of code that resulted.

I was first exposed to the idea of using active patterns for parsing when I read a blog post by Jon Harrop.
Active patterns is a feature specific to F#, and the F# wikibook has a chapter dedicated to them. I'll be using parameterized partial active patterns.

We start by defining a type for the input. The integer denotes the number of lines read so far, the list of strings is the input split at line-breaks.

open System.Text.RegularExpressions

type Stream = Stream of int * string list

A pattern to detect the end of the input, when the list of strings is empty.

let (|EOF|_|) = function
    | Stream(_, []) -> Some()
    | _ -> None

A pattern to detect end-of-lines, by recognizing list of strings which start with the empty string.

let (|EOL|_|) = function
    | Stream(n, "" :: rest) ->
        Some (Stream(n + 1, rest))
    | _ -> None

This pattern eats white space.

let (|OneWS|_|) = function
    | Stream(n, line :: rest) ->
        let trimmed = line.TrimStart()
        if trimmed <> line then
            Some (Stream(n, trimmed :: rest))
        else
            None
    | _ -> None

A convenient pattern to eat sequences of white space and newlines. Note the use of the rec keyword, which allows to refer to the pattern itself in its implementation.

let rec (|WS|_|) = function
    | OneWS (WS s)
    | EOL (WS s) -> Some s
    | s -> Some s

We could also have attempted another variant, where WS uses itself for the first part, which would implement a left-recursive grammar. Unfortunately, this pattern would be useless, as all it would do is raise stack-overflow exceptions.

let rec (|WS1|_|) = function
    | WS1 (OneWS s) -> Some s
    | s -> Some s

My variant of the Regex pattern differs a bit from the one in the wikibook, to avoid re-building Regex objects, which has a non-neglectable cost.

let (|Regex|_|) (regex : Regex) = function
    | Stream(n, line :: rest) ->
        let m = regex.Match(line)
        if m.Success then
            let lineRest = line.Substring(m.Length)
            let values =
                [ for gr in m.Groups -> gr.Value ]
            Some (values, Stream(n, lineRest :: rest))
        else None
    | _ -> None

A sample pattern to illustrate the use of the Regex pattern.

let personRegex = Regex("NAME: (\w+) AGE: (\d+)")
let (|Person|_|) = function
    | WS (Regex personRegex ([_ ; name ; age], s)) -> Some ((name, age), s)
    | _ -> None

A pattern to parse data of a large number of persons. I could have used recursion at the level of the pattern itself, similarly to WS. However, such a pattern would not be tail-recursive, and would cause stack overflows for large numbers of entries.

let (|Persons|_|) s =
    let rec work s persons =
        match s with
        | Person (p, s) -> work s (p :: persons)
        | _ -> (persons |> List.rev, s)
    let persons, s = work s []
    Some (persons, s)

Finally, some utility code to initialize streams, generate one million lines to parse, followed by the parsing itself.

let streamOfLines lines =
    Stream(0, lines |> List.ofSeq)

let streamOfFile path =
    Stream(0, System.IO.File.ReadAllLines(path) |> List.ofArray)

let stream =
    seq { for n in 0..1000000 do
            yield sprintf "  NAME: Anonymous AGE: %d              " (n % 99) }
    |> streamOfLines

#time "on"
match stream with
| Persons (p, WS EOF) -> printfn "Success %A" p
| _ -> printfn "Failed"
#time "off"

Parsing takes about 9 seconds on my PC (18s if I recreate the Regex object repeatedly). I think that's very decent performance.
In a future post, I'll describe how to parse Boolean formulas and expand a bit on the power and performance of this method.

Problems with portable libraries and object-oriented APIs

I've got along well with inheritance for a long time, but this was not peace. Inheritance was preparing, in the dark, cowardly, waiting to byte me. And it just did that!

In my last post, I presented a method to detach libraries from external assemblies and let applications take responsibility for the "linking".

The key was to use interfaces to shadow the API of the external assemblies. Sadly, it falls apart when the API being shadowed, say XNA, relies on inheritance to connect to the user's code.

Take GameComponent, for example. Users are expected to define a type that inherits from GameComponent, overriding a number of methods (Initialize, Update and Draw, typically).

It would be nice if one could declare that XNA provides a type GameComponent with abstract methods (the syntax is made up, that's not valid ML or F#):

signature Xna =
  type GameTime
  type GameComponent with
    abstract new : unit -> unit
    abstract Initialize : unit -> unit
    abstract Update : GameTime -> unit
    abstract Draw : GameTime -> unit

Using the method described in the previous post, this would become in F#:

type XnaImplementation<'GameTime, 'GameComponent>() =
  ...

Then F# code could maybe do something like that:

type MyGameComponent<'GameTime, 'GameComponent>(xnaOps : XnaImplementation<'GameTime, 'GameComponent>) =
  inherit 'GameComponent()
  ...

That is however not valid F# code, as inheriting from generic types is not allowed.
I have a solution for that in my code, but I'm not very happy. It involves a new interface IGameComponent that the API provider has to wrap inside XNA's GameComponent.
Throw into the lot that XNA's GameComponent provides some functionality (properties Visible and Enabled) that MyGameComponent needs to be able to access, and you need to throw another wrapper into the picture. Not pretty at all.

I've been considering whether I should take a different approach and create a so-called reference assembly for XNA. In theory, it shouldn't be hard. Extract the type definitions and methods that are needed from the actual libraries, put them into a reference assembly, and be done with it. Unfortunately, there does not seem to be a tool to do that available to the public. Microsoft should seriously consider including such a tool with VS11, it would allow users to add the little bits that were not portable enough for the portable .NET core, but that are nevertheless available on the platforms that users are targeting.

There are days when I really miss SDL. A simple library that lets itself be called, but doesn't call you. Lesson of the day: object-oriented APIs without proper tooling are painful.

Modular programming for portable F# libraries

I've been battling a few more rounds with F# portable class libraries. Getting them to work on PCs wasn't a walk in the park, but it seems I've got it working at last. Although this particular problem is not the main topic of this post, I expect many will run into the same issue, so I'll dedicate a few lines to its resolution.

The setting

I have a portable F# library which performs some physics calculations. Typical stuff you would expect in a portable library. It's unimaginatively but aptly named PortableLibrary1.

There is also an F# application project to run the simulation in a windows console (as in "text console", no xbox fun involved at this stage yet) application.

The application project refers to the library project.

The problem

The application compiles fine, but crashes when run with an exception stating that some version of FSharp.Core.dll could not be loaded.

The solution

Insert the following lines into the app.config file in the application's project:

<runtime>
  <assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
    <dependentAssembly>
      <assemblyIdentity name="FSharp.Core" publicKeyToken="b03f5f7f11d50a3a" culture="neutral"/>
      <bindingRedirect oldVersion="2.3.5.0" newVersion="4.3.0.0"/>
    </dependentAssembly>
  </assemblyBinding>
</runtime>

Thanks to Brian and his answer on stackoverflow.

We can run portable code on the PC, but the problems I mentioned in my previous post are still there, namely:

1. I can't reference functions and types from Microsoft.Xna.Framework because there is no portable version (that I know of).
2. There are core functions that are not available in the portable core, e.g. Thread constructors.

I will show below a solution to these two problems (my apologies to all bird lovers out there).

Signatures and modules

F# has its origins in ML, and some ML languages (standard ML, Ocaml) offer a module system that separates interfaces (which are called signatures) and implementations (call structures). Unfortunately, the module system of F# isn't as powerful. It's probably difficult, if not impossible, to fully emulate modules in F#. Nevertheless, there may some nice aspects of ML modules that can be imitated in F#.

• The module system distinguishes interfaces and implementations.
• Signatures specify a number of related types and operations operating on them in an abstract way.
• Structures provide a number of concrete types and functions satisfying the specification in the structure they implement.

A signature of vector math could look as shown below:

signature VectorMath
  type V
  val add: V * V -> V
  val dot: V * V -> float32
  val len: V -> float32

In the .NET world, there is something that might play the role of signatures, namely interfaces. The problem is how to express that module VectorMath should have a type V? Interfaces can be used to specify operations, but not nested types. In my solution, I have used generics:

type VectorMath<'V> =
    interface
        abstract Add : 'V * 'V -> 'V
        abstract Subtract : 'V * 'V -> 'V
        abstract Dot : 'V * 'V -> float32
        abstract Scale : float32 * 'V -> 'V
        abstract Len : 'V -> float32
        abstract Len2 : 'V -> float32
        abstract Zero : 'V
        abstract AreEqual : 'V * 'V -> bool
    end

Note that the dimension of the vector type V is not constrained. This signature allows to perform interesting operations on vectors regardless of whether we are working in 2d or 3d.
Operations that depend on the number of dimensions are found in additional signatures:

type Vector2Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> float32
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract Create : float32 * float32 -> 'V
    end

type Vector3Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> 'V
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract UnitZ : 'V
        abstract Create : float32 * float32 * float32 -> 'V
    end

Modules implementing these signatures are written using any .NET type that can implement interfaces. In F#, discriminated unions do the job. As a side note, I tend to use single-discriminant DUs a lot in my F# code. I see them as C's typedefs the way they should have been.

type XnaVector3Math =
    | XnaVector3Math
    interface PortableLibrary1.Vector3Math<Vector3> with
        member this.Add(v1, v2) = v1 + v2
        member this.Subtract(v1, v2) = v1 - v2
        member this.Scale(x, v) = x * v
        member this.Dot(v1, v2) = Vector3.Dot(v1, v2)
        member this.Cross(v1, v2) = Vector3.Cross(v1, v2)
        member this.Len(v) = v.Length()
        member this.Len2(v) = v.LengthSquared()
        member this.AreEqual(v1, v2) = v1 = v2
        member this.UnitX = Vector3.UnitX
        member this.UnitY = Vector3.UnitY
        member this.UnitZ = Vector3.UnitZ
        member this.Zero = Vector3.Zero
        member this.Create(x, y, z) = new Vector3(x, y, z)

Keep in mind the problem I wanted to solve was how to remove the dependency on the XNA dll from the portable library. The interfaces are part of the portable library, the implementation is in the application's code.
The same method can be used to send missing bits of Thread from the application (which has access to the missing bits) to the portable code.

Using signatures

The code for the physics simulation is shown below, not so much for its value as a physics engine, but to judge of the usability of signatures.

type SystemState<'V> =
    { mass : float32[]
      pos : 'V[]
      speed : 'V[] }

let computeForces (ops : #VectorMath<'V>) state =
    let forces =
        [|
            for mass, pos in Array.zip state.mass state.pos do
                let force =
                    Array.zip state.mass state.pos
                    |> Array.map (fun (mass', pos') ->
                        if ops.AreEqual(pos, pos') then
                            ops.Zero
                        else
                            let relPos = ops.Subtract(pos', pos)
                            let dist = relPos |> ops.Len
                            ops.Scale(mass * mass' / (dist * dist * dist), relPos))
                    |> Array.fold (fun x y -> ops.Add(x, y)) ops.Zero
                yield force
        |]

    forces

let update (ops : #VectorMath<'V>) dt state =
    let inline (.*) k v = ops.Scale(k, v)
    let inline (.+.) v1 v2 = ops.Add(v1, v2)

    let forces = computeForces ops state
    let accels =
        Array.zip state.mass forces
        |> Array.map (fun (mass, force) -> (1.0f / mass) .* force)

    let speeds =
        Array.zip state.speed accels
        |> Array.map (fun (speed, accel) ->
            speed .+. (dt .* accel))

    let positions =
        Array.zip state.pos speeds
        |> Array.map (fun (pos, speed) ->
            pos .+. (dt .* speed))

    { state with
        pos = positions
        speed = speeds }

let initialize (ops : #Vector3Math<'V>) =
    let rnd = new System.Random(0)
    let nextFloat() = rnd.NextDouble() |> float32

    let N = 1000

    let masses =
        Array.init N (fun _ -> nextFloat() * 1000.0f)

    let positions =
        Array.init N (fun _ ->
            let len = nextFloat() * 100.0f
            ops.Scale(len, ops.Create(nextFloat(), nextFloat(), nextFloat())))

    let speeds =
        Array.init N (fun _ -> ops.Zero)

    { mass = masses
      pos = positions
      speed = speeds }

let centerOfMass (ops : #VectorMath<'V>) state =
    let wpos =
        Array.zip state.pos state.mass
        |> Array.map (fun (pos, mass) -> ops.Scale(mass, pos))
        |> Array.fold (fun wpos x -> ops.Add(wpos, x)) ops.Zero

    let mass = Array.sum state.mass
    
    ops.Scale(1.0f / mass, wpos)

Discussion

This approach has a number of problems, compared with traditional F# modules.

1. Additional level of indirection when calling operations. In performance-critical situations, this can matter.
2. Additional ops parameter sprinkled in all functions that use the signature. A bit tiresome to write. Call sites aren't as badly affected, thanks to partial application and currying.
3. Need to specify the signatures. Will I need to duplicate all of XNA's API in signatures?

There are a number of non-problems, i.e. problems that have pretty good solutions:

1. Operator overloading: See update for an example on how to use operators to improve the look of expressions involving vector math.
2. Callers need not pass ops explicitly at each call site, as shown below:

In the library:

let mkModule ops =
    (fun () -> initialize ops),
    update ops,
    centerOfMass ops

In the application:

let initialize, update, centerOfMass = PortableLibrary1.mkModule MyVector3Math
let state = initialize()
let center0 = centerOfMass state

The benefits include:

1. Truly write-once-run-everywhere library code. I should be able to use my library code in a game for Sony devices using the Playstation Suite SDK, or for smart phones (actually, not quite, due to limitations regarding generic virtual methods in Mono).
2. Looser coupling between libraries. It's up to the top level, the application, to specify implementations. That's the right thing to do, since that's the only part that should be aware of the target platform and its  specifics.

Programmers with a background in OOP might wonder why I did not use an interface for the vector type itself, instead of providing an interface for a module. Note that would not really help me here, as XNA's Vector3 and Vector2 don't implement this interface (of which they know nothing). I would need some bridging type anyway.
Providing abstraction on the module-level, as opposed to the "object" level allows to group related types in a module specification. A more complete vector math signature would include matrices and operations that operate on vectors and matrices. The OOP approach forces these operations into one of the vector and matrix types, which I have always found a bit arbitrary.

Portable Class Libraries: Are they worth the trouble?

The (initial) problem

Everyone who's been developing games using XNA for the Xbox360, WP7 and the PC platforms knows managing projects and solutions is a bit troublesome. Here is the problem: in theory, all you would need is to have a single solution with three platforms: x86, xbox and wp7.
However, that's not how it works in practice. The various DLLs that you need to reference vary from one platform to the next, meaning you have to create multiple projects for each library. The XNA plugin for Visual Studio helps with the task of managing multiple libraries, but it doesn't work for F# projects.
I have developed a script that generates xbox projects from pc projects, but it's more of a hack than a reliable method. It also requires some amount of manual intervention. Although I am personally relatively satisfied with this solution, I imagine it will be close to no use to anyone but me.

The (supposed) solution

The release of Visual Studio 11 beta has exposed a new type of project: Portable Class Library. Here is what MSDN has to say about them:

Using a Portable Class Library project, you can build portable assemblies that work without modification in .NET Framework, Metro style, Silverlight, Windows Phone 7, and Xbox 360 apps.

That sure sounds interesting. I decided to try this new feature by adopting it for XNAUtils.

The reality (more problems)

No need to maintain the suspense to the end of this post, I can already reveal I'm not positive about these libraries. The rest of this post describes a number of hurdles I have encountered so far.

The screenshots on MSDN don't look like my screen

The MSDN docs state that you can specify which platforms you intend to support. Since each platform has its limitations, limiting support to a number of platforms my allow for larger accessible feature sets.

That's how it's supposed to look. The project properties should have a button "Change" allowing to access the various platforms.

Sadly, that does not apply to F# prjects:

No "Change" button to be seen. Somewhat worryingly, the Xbox platform is not mentioned here.

In any case, I chose to ignore that problem and go ahead...

What kind of libraries can I refer to?

I will need to access at Microsoft.Xna.Framework, and possibly also Graphics. However, those are not available as portable libraries. I referenced the ones for Xbox, and hoped for the best. It might work on the xbox, but I don't see how that could possibly work on the PC?! I haven't come to the point where I could run something, so we'll see how that goes...

Dude, where's my Thread constructor?

One of my functions creates a thread. This code no longer compiles, I have posted a question on stackoverflow on the subject.

Summary: Apparently, the constructor I want to use is not available in portable class libraries, despite the MSDN doc claiming the contrary.

That's not very reassuring. Deciding whether to take the step to PCLs requires some thinking ahead, and the information available from official sources isn't reliable. I know it's still a beta release, but it's unpleasant nevertheless.

There is a feeling of deja-vu with this one. Back in the days when I was working on my asteroids clone, I had a problem with the thread class. I had used the PC dlls of XNA in my xbox build. That worked fine before XNA 3.1, but there was a catch. The code would compile, but crash when run on the xbox. The offender was a method of Thread that was not available on the xbox.

The solution consisted of wrapping the correct method in a delegate in the top-level C# code, and send it down to my F# code, which could invoke it to perform the required operation.

It seems I will have to use the same trick here if I want to be able to create threads. The portable framework doesn't allow creating threads, but the XNA framework, which "implements" the portable framework, has the constructor I need. A solution would therefore be to get the thread constructor from the top-level app (which is aware of the specific platform it will run on) and pass it down to the portable code.

This solution should be usable for any "non-portable" functionality that you know exists on the platforms you target.

Conclusion

The experiment is not conclusive yet, as I haven't gotten to the point where I can run things. I wonder if it's worth the trouble.

This shows linking to implementations is a mistake. What you should link to is signatures. Then it's up to the top level, the application, to specify a set of implementations which satisfy these signatures. Libraries have no business depending on implementations.

The approach consisting of providing implementations that "work everywhere" is probably not going to work well, since they are very likely to lack basic functionality that isn't available everywhere in exactly the same way.