Movimentum - A severe grammar problem

When I looked through the grammar, I saw that I had made a small mistake: The rule for the X and Y selectors is as follows:

    scalarexpr4
      : ...
      | anchor
        ( X
        | Y
        )
      ...
      ;

This means that I can only attach .x and .y to anchors. However, I certainly also would like to write things like

    (Engine.P + [a,b]).x

I.e., I want to attach .x and .y to any vector expression. Not a big problem, I thought, and replaced anchor with vectorexpr4, which includes anchor as well as parenthesized vector expressions. But now ANTLR complains as follows:

[fatal] rule scalarexpr4 has non-LL(*) decision due to recursive rule invocations reachable from alts 1,8.

And after a minute of head scratching, the problem is clear: Assume that we are parsing along in a scalarexpr, and we see a few left parentheses and some stuff behind it:

    (((Identifier....

Now: Is this going to be

• a scalar subexpression - e.g. just variables and numbers added = the first alternative of scalarexpr4;
• or a vector expression, which then is ended with .x = the eighth alternative of scalarexpr4;

ANTLR3 tries to solve that puzzle by running a regular expression over the following symbols (which is much more powerful than classic LL(k) parsing, where only a fixed number k of symbol were "looked ahead"), but with the recursive nature of  my expression, a regular grammar cannot decide this! What can we do? Here are seven(!) possibilities to solve the problem - the first three are suggested by ANTLR after the error message above, the others are standard:

1. Resolve by left-factoring. This is essentially impossible if I want to keep vector expressions and scalar expressions separate: It would require that all those "left sides" where it is not yet clear whether we are "scalar" or "vector" need to be put into a "generic expression" rule. I drop that option.
2. Resolve by using backtrack=true option. Here, ANTLR runs the alternatives of a rule from top to bottom in a sort of "test mode" without actions and without error output until it succeeds with parsing.
3. Resolve by using syntactic predicates. This is almost the same as 2., but for this, you must add a hand-crafted piece of "selection grammar" that moves the parser into the right direction. This is more work than 2., but may be much more efficient if there is e.g. a simple context-free grammar to decide on the issue. One can also say that option 2. is like option 3. with the specified alternatives used as "selection grammar". In our small grammar and - hopefully - small expressions, I don't see a reason to hand-craft a "selection grammar", so I drop this option.
4. Use LR parsing. With LR parsing, the postfix .x might help to decide whether the elements below are going to be collapsed into a vectorexpr or a scalarepxr. However, I stick with ANTLR ... so I drop this option.
5. Use type-free expressions. If our expressions were "just parenthesized expressions" without a syntactic distinction between vector and scalar expressions, the problem would vanish on the syntactic level. Of course, one could then write expressions like ((4)).x, i.e., add .x to a scalar - but this would have to be handled in a semantic layer. Almost all programming languages do this. This is essentially a more abstract view on the advice "left factor". Still, I would like to keep that syntactic distinction. I drop this also.
6. Use .x as prefix. Prefixes are obviously great in LL parsing - but I don't want to write .x(Engine.P), so I drop this.
7. Use different sort of parentheses, e.g. {...}.x. This will also help the parser to distinguish vector and scalar expressions on the left side - and also humans! It seems a worthwhile option, as it would force the user to always clearly state whether an expression is a vector or a scalar.

So the two alternatives that survive are 2. and 7.: Should I clearly distinguish the expression types in the language? Or should ANTLR "try what works"? I lean heavily towards 7., I must say - still, using parentheses (and not e.g. braces) for vector expressions is so common that it's had to break with that convention. Ok - let's take 2. for this time; but maybe reverse that (pure syntactical) decision if there arise more problems later - e.g. when the grammar is extended.

To keep the problem as local as possible, I extract the relevant alternatives to separate rules. For the vectorexpr4, I extract the following to vectorexpr5 and allow the .x, .y and .l suffixes only on these:

    vectorexpr4
      : INTEGRAL
          '(' vectorexpr ')'
      | DIFFERENTIAL
          '(' vectorexpr ')'
      | vectorexpr5
      ;

    vectorexpr5
      : '('
        vectorexpr
        ')'
      | vector
      | anchor
      ;

For the scalarexpr4, I extract a scalarexpr4Ambiguous rule which gets the backtrack option. In the backtracking rule, we put the vector expression with its trailing operators first. The reason is that syntactically, the second alternative can be a prefix of the first one - for example, (a) might be a scalarexpr or a vectorexpr5. When we put the second alternative first, it will not look at those .x or .y or .l suffixes and hence parse into a parenthesized scalarexpr - and then fail on the suffix. We will definitelyhave to test this thouroghly!

     scalarexpr4
      : scalarexpr4Ambiguous
      | ...
      ;

    scalarexpr4Ambiguous options { backtrack = true; }
     :  vectorexpr5
        ( X
        | Y
        | LENGTH
        )
      | '('
        scalarexpr
        ')'
      ;

The modified grammar file can be seen here!

Movimentum - The script model

Now that we can parse scripts, we ... should test the parser. However, we wouldn't get more than a "yes/no" information whether the parse succeeded. So we continue straight to building a model from the input - we will use these models then also for a few unit tests for the parser.

ANTLR (and probably other parser generators) have the ability to create standard parse trees with little code. These trees, however, then consist of nodes of a single type which contain their children in generic collections - similar to the DOM and Linq.Xml structures for XML. However, I want to program against "full-featured" classes, so I write my own model classes. Using ReSharper, this is not much work. Let's do it for the top-level element script: First, I define a raw class like this

    class Script {
        public Config Config { get { return _config; } }
        public IEnumerable<Thing> Things { get { return _things; } }
        public IEnumerable<Step> Steps { get { return _steps; } }
    }

R# complains in red about all those missing things. With Alt+Enter on _config, _things, and _steps, we do "Create field ...":

    class Script {
        private Config _config;
        private IEnumerable<Thing> _things;
        private IEnumerable<Step> _steps;
        public Config Config { get { return _config; } }
        public IEnumerable<Thing> Things { get { return _things; } }
        public IEnumerable<Step> Steps { get { return _steps; } }
    }

R# now complains (with a wavy line) that each "Field is never assigned" - Alt+Enter on each field allows us to "Initialize Field from constructor(s) parameter":

    class Script {
        private Config _config;
        private IEnumerable<Thing> _things;
        private IEnumerable<Step> _steps;
        public Script(Config config, IEnumerable<Thing> things,
                      IEnumerable<Step> steps) {
            _config = config;
            _things = things;
            _steps = steps;
        }

        public Config Config { get { return _config; } }
        public IEnumerable<Thing> Things { get { return _things; } }
        public IEnumerable<Step> Steps { get { return _steps; } }
    }

(My) R# now complains that the fields could be made readonly - Alt+Enter on each field corrects that, and we are done:

    class Script {
        private readonly Config _config;
        private readonly IEnumerable<Thing> _things;
        private readonly IEnumerable<Step> _steps;
        public Script(Config config, IEnumerable<Thing> things,
                      IEnumerable<Step> steps) {
            _config = config;
            _things = things;
            _steps = steps;
        }

        public Config Config { get { return _config; } }
        public IEnumerable<Thing> Things { get { return _things; } }
        public IEnumerable<Step> Steps { get { return _steps; } }
    }

Question: Why don't I use auto properties - which would reduce the number of lines by one-third? Or auto-properties with setters, reducing the line number to one-third?
Answer: Because I always enforce immutability in my programs, even in private methods: Things that should not change should not change. And if that boiler-plate code gets too "noisy", I separate the classes into two partial classes, one with the boiler-plate, the other one with the "useful" code.

I do this same process now for all constructs from the grammar. Along the way, I think a little bit about abstraction, but not too much. Here is an example: Class Thing needs a source and the anchors.

• For the source, I use type System.Drawing.Image - i.e., we read the images already during parsing. This will lead to "file not found" errors during parsing ... I live with that.
• For the list of anchors, I want a simple Dictionary: The key is the name of the anchor, the value is the computed vector. This has a few semantic implications: (a) Anchors that use other anchors in their definition must come after the definition of the used ones. (b) We must be able to add and subtract ConstVectors already during parsing. I'll show the corresponding code when I write it.

Here is a piece of code that shows the "raw" model for step and constraints. Instead of the operator in the ScalarInequalityConstraint, I could also have

• provided four subclasses; or
• reduced the number of operators to two by reversing the left-hand-side and right-hand-side e.g. for GT and GE.

If I have to write more than one or two switches later, I might return to one of these ideas.

    class Step {
        public decimal Time { get { return _time; } }
        public IEnumerable<Constraint> Constraints {
            get { return _constraints; }
        }
    }

    abstract class Constraint {}

    class VectorEqualityConstraint : Constraint {
        public VectorExpr Lhs { get { return _lhs; } }
        public VectorExpr Rhs { get { return _rhs; } }
    }

    class ScalarEqualityConstraint : Constraint {
        public string Variable { get { return _variable; } }
        public ScalarExpr Rhs { get { return _rhs; } }
    }

    class ScalarInequalityConstraint : Constraint {
        public string Variable { get { return _variable; } }
        public ScalarInequalityOperator Operator { get { return _operator; } }
        public ScalarExpr Rhs { get { return _rhs; } }
    }

    enum ScalarInequalityOperator { LT, LE, GT, GE }

Here is the raw structure of the vector expressions. Again, I use operators instead of too many subclasses - but I might reconsider this later, when we get methods in these classes. The Vector class is already fully implemented, as I copied and adapted it from the ConstVector:

    abstract class VectorExpr {}

    class BinaryVectorExpr : VectorExpr {
        public VectorExpr Lhs { get { return _lhs; } }
        public BinaryVectorOperator Operator { get { return _operator; } }
        public VectorExpr Rhs { get { return _rhs; } }
    }

    enum BinaryVectorOperator { PLUS, MINUS, TIMES }

    class VectorScalarExpr : VectorExpr {
        public VectorExpr Lhs { get { return _lhs; } }
        public VectorScalarOperator Operator { get { return _operator; } }
        public ScalarExpr Rhs { get { return _rhs; } }
    }

    enum VectorScalarOperator { ROTATE }

    class UnaryVectorExpr : VectorExpr {
        public UnaryVectorOperator Operator { get { return _operator; } }
        public VectorExpr Inner { get { return _inner; } }
    }

    enum UnaryVectorOperator { MINUS, INTEGRAL, DIFFERENTIAL }

    class Vector : VectorExpr {
        private readonly ScalarExpr _x;
        private readonly ScalarExpr _y;
        public Vector(ScalarExpr x, ScalarExpr y) {
            _x = x;
            _y = y;
        }

        public ScalarExpr X { get { return _x; } }
        public ScalarExpr Y { get { return _y; } }
    }

    class Anchor : VectorExpr {
        public Thing Thing { get { return _thing; } }
        public string Name { get { return _name; } }
    }

Finally, here are the definitions for scalar expressions:

    abstract class ScalarExpr { }

    class BinaryScalarExpr : ScalarExpr {
        public ScalarExpr Lhs { get { return _lhs; } }
        public BinaryScalarOperator Operator { get { return _operator; } }
        public ScalarExpr Rhs { get { return _rhs; } }
    }

    enum BinaryScalarOperator { PLUS, MINUS, TIMES, DIVIDE }

    class UnaryScalarExpr : ScalarExpr {
        public UnaryScalarOperator Operator { get { return _operator; } }
        public ScalarExpr Inner { get { return _inner; } }
    }

    enum UnaryScalarOperator { MINUS, INTEGRAL, DIFFERENTIAL }

    class BinaryScalarVectorExpr : ScalarExpr {
        public VectorExpr Lhs { get { return _lhs; } }
        public BinaryScalarVectorOperator Operator { get { return _operator; } }
        public VectorExpr Rhs { get { return _rhs; } }
    }

    enum BinaryScalarVectorOperator { ANGLE }

    class UnaryScalarVectorExpr : ScalarExpr {
        public VectorExpr Inner { get { return _inner; } }
        public UnaryScalarVectorOperator Operator { get { return _operator; } }
    }

    enum UnaryScalarVectorOperator { LENGTH, X, Y }

    class Constant : ScalarExpr {
        public decimal Value { get { return _value; } }
    }

    class ScalarVariable : ScalarExpr { // Also _
        public string Name { get { return _name; } }
    }

    class T : ScalarExpr {
    }

    class IV : ScalarExpr {
    }

Now, I have to add the boiler-plate code. Bear with me ...

... two minutes later, everything is done (ReSharper is a fantastic tool!). Here is the created model file.
All classes in one file is not really ok. I have to decide later which code I leave in there (the boiler-plate code), and which I move out to separate files.

Movimentum - ANTLR grammar for the timeline

The timeline is, of course, the interesting thing about animation - the script to which our actors dance. It consists of sections that start with a point in time. I allow relative times and absolute times:

    time 
      : '@' NUMBER
      | '@' '+' NUMBER
      ;

The rest of each section is a set of constraints. Now, I start to get afraid a little bit of the constraint satisfaction, so I restrict constraints to "what we probably need." That may be a bad mistake, because it introduces ad-hoc restrictions to the expressiveness of the language; or it may be a very good idea, because it makes constraint satisfaction possible at all. We'll see ...

I try to separate vector and scalar expressions as far as possible; and I try to separate equality constraints from looser constraints, so I start like that:

    constraint
      : vectorexpr
        '='
        vectorexpr
        ';'
      | scalarexpr
        '='
        scalarexpr
        ';'

      | IDENT
        ('<' | '>' | '<=' | '>=')
        scalarexpr
        ';'
      ;
   
For the expressions, we define a standard hierarchy to capture operator precedence:

    vectorexpr
      : vectorexpr2
        ( ( '+'
          | '-'
          )
          vectorexpr2
        )*
      ;
     
    vectorexpr2
      : vectorexpr3
        ( ROTATE
          '(' 

          scalarexpr 

          ')'
        )*
      ;
     
    vectorexpr3
      : '-' vectorexpr4
      | vectorexpr4
      ;
     
    vectorexpr4
      : '('
        vectorexpr
        ')'

      | ...simple vector expressions...

      ;

and

    scalarexpr
      : scalarexpr2
        ( ( '+'
          | '-'
          )
          scalarexpr2
        )*
      ;
     
    scalarexpr2
      : scalarexpr3
        ( ( '*'
          | '/'
          )
          scalarexpr3
        )*
      ;
     
    scalarexpr3
      : '-' scalarexpr4
      | scalarexpr4
      ;
   
    scalarexpr4
      : '('
        scalarexpr
        ')'

      | ...simple scalar expressions...

      ;

What simple expressions do we need? Let us start with the vector expressions:

• A constant vector.
• An "anchor" which was defined in the object definitions.
• And an integral and differential.

More will come, I'm sure - scaling a vector comes to mind:

      | INTEGRAL
          '(' vectorexpr ')'
      | DIFFERENTIAL
          '(' vectorexpr ')'
      | constvector
      | anchor
      ;

We have already defined a constvector. An anchor, right now, is simply an object IDENT and an anchor IDENT (but I think that I have to introduce compound objects later, when the number of moved objects increases):

    anchor
      :  object '.' IDENT
      ;
   
    object
      : IDENT
      ;
     
For the simple scalar expressions, we should at least provide the following:

      | INTEGRAL
          '(' scalarexpr ')' 
      | DIFFERENTIAL
          '(' scalarexpr ')' 
      | ANGLE 

          '('
          vectorexpr
          ','
          vectorexpr
          ')'
      | NUMBER
      | IDENT
      | '_'        // the dont care variable
      | anchor 

        ( X

        | Y

        )

      | object COLOR

      | T
      | IV 
      ;

With this, it should now be possible to run our complete script for the slider-crank mechanism throught the parser!

UPDATE: The test revealed two errors:

The first one is a "syntactical" one: ANTLR uses the rule names as method names. But this creates a C# syntax error for the rule object (which is a keyword in C#). So I replaced object with thing.

The other error is a too restrictive rule for vector expressions: As one possibility of a simple vector expression, I took constvector. However, in the timeline, we obviously also want to use non-const vectors, e.g. in the constraint Engine.Q = Engine.P + [_,0]. Therefore, the rule actually is

    ...

    | DIFFERENTIAL

        '(' vectorexpr ')'

    | vector

    | anchor

    ...

with

    vector
      : '['
        scalarexpr
        ','
        scalarexpr
        ']'
      ;

The grammar at this stage can be downloaded here.

Movimentum - ANTLR grammar for setup

I use ANTLR as a grammar tool. And I use .Net for development. In my old days, I keep to things I know.

Here is an ANTLR grammar for Movimentum. First, we need some ANTLR and .Net noise:

    grammar Movimentum;
   
    options {
        language=CSharp2;
    }
   
    @parser::header {
        using System.Collections.Generic;
    }
   
    @parser::namespace { Movimentum.Parser }
   
    @lexer::namespace  { Movimentum.Lexer }

Then, I like to start grammars top down:

    script
      : config
        objectdefinition*
        ( time
          constraint*
        )*
        EOF
      ;

    config
      : CONFIG '('
            NUMBER  // frames per time unit
        ',' unit    // angular unit
        ')'
      ;

At this time, we must start with the lexer definitions also:

    CONFIG : '.config';

    NUMBER  
      : ('0'..'9')+
        ( '.'
          ('0'..'9')*
        )?
        ( ('E'|'e')
          ('-')?
          ('0'..'9')+
        )?
      ;

And before we forget it, we add rules for whitespace and comments:

    WHITESPACE
      : ( '\t' | ' ' | '\r' | '\n' )+ { $channel = HIDDEN; }
      ;
   
    COMMENT
      : '/' '/' .* ( '\r' | '\n' )    { $channel = HIDDEN; }
      ;

The next important thing are the objectdefinitions:

    objectdefinition
      :  IDENT
        ':'
        source
        anchordefinition+

        ';'
      ;

We now need an IDENT in the lexer. For the moment, we restrict ourselves to ASCII letters in its definition:

    IDENT   
      : ('a'..'z'|'A'..'Z')('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
      ;

For the source, we currently define only a "filename" (I suspect I want plain texts later, and maybe even some standard forms like arrows and lines):

    source
      : FILENAME
      ;

and

    FILENAME
      : '\''
        (~('\''))*
        '\''
      ;
   
Finally, we need anchordefinitions. We allow only constant vectors in them:

    anchordefinition
      : IDENT
        '='
        ( constvector
        | IDENT '+' constvector
        | IDENT '-' constvector
        )
      ;
   
where constvector is defined as

    constvector
      : '['
        ('-')? constscalar

        ','
        ('-')? constscalar

        ']'
      ;

    constscalar
      : NUMBER
      | constvector X
      | constvector Y
      ;

This requires our first operator definitions in the lexer:

    X : '.x';
    Y : '.y';

This should suffice to define objects and their anchors for the moment. Time to set up a .Net project, write the setup part of our crank-slider mechanism into a file and check whether we can read it (after we comment out the time and constraint references in script)!

UPDATE: Setting up the project and writing the first test case revealed two errors in the grammar above. First, a semicolon is missing at the end of the config.rule - it must be:

    config

      : CONFIG '('

            NUMBER  // frames per time unit

        ',' unit    // angular unit

        ')'

        ';'

      ;
The second is an LL problem: The constscalar rule cannot decide whether to take the second or the third alternative. Therefore, the common prefix has to be factored out:

    constscalar
      : NUMBER
      | constvector
        ( X
        | Y
        )
      ;

In a test case, I can now parse the object definitions for the slider-crank mechanism flawlessly!

Movimentum - Design of the language - Notation

Thinking a little bit about the implementation, the vector constraints we have written are actually constraints on scalar variables. For example,

    Crank.Q = Crank.P + [_,0];

actually means

    Crank.Q.x = Crank.P.x + _;
    Crank.Q.y = Crank.P.y;

Here, we can view .x and .y as predefined operators. Similiarly, the .rotate in

    Crank.Q = Crank.P + [c,0].rotate(180° * t)

is a predefined operator. From this meager data, I infer that I want "predefined things" to have the form dot-identifier. Therefore, I change the integral operator such that the "braking constraint" reads

    w = .integral(b) + 180;

Similarly, we can define additional operators:

    .angle(vector,vector)

    .differential(scalar)

    .differential(vector)

    .length(vector)

For lazyness, I would also allow single-letter abbreviations for the most important operators: .a for angle, .i for integral, .d for differential, .l for length.

In the same vein, I also change t to .t:

    Crank.Q = Crank.P + [c,0].rotate(180° * .t)

When I thought about more things that should be animated, I found that I might want to change the color of something over time - e.g. to show that somthing gets hotter. A simple idea is to give each object something like

    .red

    .green

    .blue

which are scalars that are added to or subtracted from each (non-transparent) pixel in a picture. Or maybe there's a different way to change the color - e.g. along a line of rainbow colors. For the simulation, this is simply another variable that takes part in the constraint satisfaction machinery.

A last  problem: We will need some sort of initial parameters - e.g., the number of frames per time unit or a unit for angles (when we use trigonometric functions). For this, I define a construct

.config(12, // number of  frames per time unit

        °); // unit of angles

The order of the parameters is fixed, and there are no keywords. This is as inconvenient as it gets, but for a construct used only once per animation, I don't care.

Movimentum - Design of the language - Calculus

Let us now apply the brakes to our pump: It should stop, but not abruptly, but rather slowly slide to a standstill. Instead of thinking about a formula for the angular velocity, I'd like to use simple integrals:

@+08.0   b = -180 / 6; // angular acceleration

180 is the current angular velocity (in °/s). We want the crank to stop after 6 seconds - therefore, the angular acceleration is 180/6, and it is negative because the angular velocity should decrease. In standard physics, integrating this value over t will yield the required changing angular velocity. So I want to write (w should be pronounced "omega" here ;) ):

         w = integral(b);

The integral is implicitly over a variable τ, and its integration range is from 0 to t. However, w has to start at is current value, so we have to add 180:

         w = integral(b) + 180;

(I suspect that instead of the constant 180, in more complex scenarios it is necessary to get the current value from the model - e.g., if an accelerating object has to brake down again in the middle of the acceleration. But I'll think about this later.) The slowing movement now can be described as

         Crank.Q = Crank.P + [_,0].rotate(w * t);

There is a small problem with this: If we do not stop this segment after exactly 6 seconds, the crank will start to rotate backwards. And even if we do this, we'll have rounding errors in the real implementation. Hence, it is probably useful to add

@+06.0   w = 0;

Movimentum - Design of the language - Movement; and constraint lifetime

Our pump should now start to move.

We need an item that defines the time. Let's call it t, and we assume its unit is "second". It is not the absolute time, but the time relative to the previous time marker (the @). Our crank should rotate, so its point Q needs to go somewhere else. Let us assume that it should turn 180° in one second - i.e., take two seconds for a complete revolution. I'd like to write a rotating unit vector like this:

[1,0].rotate(180° * t)

If we add this to the crank's center, we get a rotating point - and we can use this to pull Q. However, Q does not have distance 1 from P, but some other distance, and so the equation would be over-constrained. But if we leave the length of the vector open, the equations should be uniquely solvable. Here is the resulting constraint, where c is that "dont care" variable:

@+02.0    Crank.Q = Crank.P + [c,0].rotate(180° * t);

Now our crank moves!

What about the conrod and the piston? Well, the original constraints that (a) connect crank and conrod, (b) force the other eye of the conrod on the center line of the piston, and (c) connect the piston to the conrod are still valid. Therefore, we shouldn't be forced to add any other contraints!

However, this creates a problem: If earlier constraints just remain in force, then also the constraint would still hold that put the crank in an upright position in the first place ...

... oops: When I placed the engine and the crank at the beginning, I was too lazy. I wrote

@000.0    Engine.P = [20,80]; // middle line of cylinder: y=80

@+02.0    Crank.P = Engine.P + [200,70];

But I did not restrict the direction of the engine and the crank! So the engine could be rotated around [20,80] in an arbitrary direction! There are two ways out of this:

• Either we request that additional constraints fix the position. In the case of the engine, we need an additional point for this.
• Or the initial placement "defaults" to a "horizontal" image.

Because the default behavior would have to be programmed, I want to avoid it. So we have to change the initial definitions:

Engine : 'engine.gif' P = [30,50] Q = P+[1,0];
Crank  : 'crank.gif'  P = [20,20] Q = P+[0,30];

Piston : 'piston.gif' P = [30,50] Q = P+[1,0];
Conrod : 'conrod.gif' P = [0,50] 
                      Q = P+[100,50]; // lies horizontally in gif

@000.0    Engine.P = [20,80]; Engine.Q = Engine.P+[_,0];

@+02.0    Crank.P = Engine.P + [200,70]; 
          Crank.Q = Crank.P + [_,0];

The engine and the piston now each have an additional point Q, horizontally from P. And the setup places these points horizontally from the location of the respective Ps. I have added another feature: A single underscore means a "dont care" variable - i.e., a new variable at each place where _ occurs.

... end of oops.

Now, we must return to the problem of the lifetime of constraints. Above, we wanted earlier constraints to hold also later - I think this will come in very handy with larger machines! However, for moving our crank we wrote

@+02.0    Crank.Q = Crank.P + [c,0].rotate(180° * t);

But there is this earlier constraint from the setup

...; Crank.Q = Crank.P + [_,0];

Obviously, we do not want to hold that constraint now! - our machine cannot move and not move at the same time! What to do?

Idea: Each constraint has a "key". If the key is used for another constraint, the earlier constraint is dropped. And if a constraint has on its left side only a single variable, that variable is the key. So the key "Crank.Q" first referenced the constraint from the setup, and then was overwritten with the constraint for the movement. Let's hope this simple rule holds out for some time.

Movimentum - Design of the language - What I want

So we are going to design a little language for moving mechanical objects. For this, we need a few example machines. As I said, there is that great page www.animatedengines.com. But the examples there are too complex for a first step - let us use a simpler example. What do we want? The machine  should be small - have only a few parts, it should be realistic, yet it should be "mathematically hard". Astonishingly, one of the simplest machines has all these properties - here is a quick sketch of a simple crank-and-piston mechanism (a pump, for example):

Let us assume that the crank turns with a constant angular velocity. The coordinates of its endpoint can readily be computed as [Rsin(t), Rcos(t)] where R is length of the crank, and t is the time, suitably scaled and shifted. Now, what are the coordinates of the piston? Because of the limited length of the connection rod, this is not a simple sine function: It is much more complicated - see for example http://en.wikipedia.org/wiki/Piston_motion_equations.

Our movement model language could require that the closed form solution is entered so that the positions of the piston can be computed directly. However, for more complex linkages, this is much work (which I sometimes love - but not always) ... aren't computers intended to solve such problems? With this consideration in mind, let us start with that language.

The following considerations already went through one round of "cleansing the language". It is actually a little hard to present the initial rough thought processes, so I start just here.

Here are a few concepts I want to have:

• Vectors. Many kinetic equations are much simpler if written as vectors.
• Scalars. Like e.g. time or angles.
• Rigid objects. These are objects that will move "as a whole" according to two points whose movement is known.
• Not-closed kinetic formulae. This comes from the example above.
• 2D only. Maybe we have 3D ideas later - not now (however, I think I'll give them vectors 3 coordinates from the start).
• Z-ordering. A 2d-object should be able to obscure another 2d object.
• Cartesian coordinates. Also polar ones?
• Time. Measured in seconds, preferably; maybe also in frames.
• "Segmented movements". From instant t1 to t2, an object does not move; from t2 to t3, it moves on the trajectory jA; from t3 to t4, it moves on trajectory jB (e.g. back).
• Units. We can measure angles in degrees or radians; time in seconds or frames; maybe length in pixels, meters, or inches (really?? well ...).
• Free format language (i.e., not line-oriented; not column-oriented).
• Comments in the language.

Ok - let's stop here and try to start with our example.

We want to set up a few objects. We assume we have them in GIF files somewhere. To get a "handle" on the objects, we can define points in them, relative to the [0/0] of the GIF:

Crank : 'crank.gif' P = [20,20] Q = P+[0,30];

The crank is in file crank.gif, and we define two points on it: P and Q (which is defined relatively to P). More objects:

Piston : 'piston.gif' P = [30,50];
Conrod : 'conrod.gif' P = [0,50] 
                      Q = P+[100,50]; // horizontally in gif 
Engine : 'engine.gif' P = [30,50];

Now we place the objects. For the fun of it, we want them to appear in 2 second intervals (but we not yet think how we might let them "fly into the scene"!). We need a time axis - I use @ as a prefix to times on that axis:

@000.0    Engine.P = [20,80]; // middle line of cylinder: y=80

@+02.0    Crank.P = Engine.P + [200,70];
@+02.0    Piston.P = Engine.P + [0,70]; // 70 above ground line
@+02.0    Conrod.P = Crank.Q; Conrod.Q = ...oops...

Conrod.Q cannot be placed easily. After all, the length of the conrod is fixed (by its image). So we cannot just "stretch" it to the piston's eye. But even if we put the conrod's eye into the piston travel line, the piston will most  probably be at the wrong position!

To keep things simple, we reverse the order and deal with the conrod first:

@000.0    Engine.P = [20,80];

@+02.0    Crank.P = Engine.P + [200,70];
@+02.0    Conrod.P = Crank.Q; Conrod.Q = ...still unclear...

What about Conrod.Q? Isn't the position of Conrod.Q uniquely fixed if only its y coordinate is fixed? After all, the fixed length of the conrod will place its Q on a defined point on the travel line of the piston! So we happily write:

... Conrod.Q = [x, 70];

x is some "unknown variable." But now, we have suddenly entered the area of "constraint satisfaction:" Our equations are not assignments, that compute a right hand side and assign it to the left hand side. Rather, they express a constraint between both sides, and therefore could be reversed: The following

... [x, 70] = Conrod.Q;

therefore means just the same as the line above.

There is one problem with the formulation above: Actually, there are two solutions for x! - the reason being that a circle (with center Crank.Q and radius equal to the length of the conrod) intersects the y=70 line at two places. We can easily fix this in our new constraint mechanism by requiring

... Conrod.Q = [x, 70]; x < Crank.P.x;

("But how,  by Jove, are the actual places of the objects computed?", you might ask. Answer: I don't know - we'll find a way when we are there!).

Let's go on and place the piston: Its eye should link to the conrod, so we simply write

@+02.0    Piston.P = Conrod.Q;

And this finishes the setup of our little machine. Next posting: Let's move it!

Movimentum - Analysis

I am in a hurry. So I do not want to write the all-encompassing, every-feature-included animation solution. Actually, I'd like to write a program with as little code as possible. Therefore, most work should be done by other programs. Here is my idea of a simple setup:

First, I need the parts of the machine that will be animated. They are simple GIFs or BMPs that can come from at least two sources:

1. Output of CAD program
2. Dressed-up cut-out of some picture.

Here are examples of each of these:

• Drawing from a CAD program:

• In the following picture, I am not yet done with cutting out a lever from a scanned photo and patching missing parts—but you get the idea:

When I have the parts, they need to be moved around according to my ideas, and the results are written into separate image files. Before that can be done, I have to create some description of the intended movements. And last, but not least, in a third step these separate images must be assembled into a complete animation. The following diagram shows these activities:

Now the question is: Which activities should be supported by which programs? There are many possibilities, e.g. using a program that does all the above (Synfig has been suggested for this); or using a program that does only the central "column" (define movements, create animation images, and assemble them into an animation). I opt for a radical decomposition: A separate program for each activity. This increases the reuse of existing programs, and minimizes work. For three of the activities, the programs are obvious:

• Create images with CAD—use a CAD program;
• Cut parts from images—use a photo editor;
• Assemble animation—use a program like Windows Movie Maker or ImageMagick.

The program for creating the movement model depends on the interface to the central animation activity. What could that interface look like? Here are some obvious alternatives (that should be in the toolbox of every software architect):

1. Writing some sort of code in a standard programming language.
2. Writing text—i.e., we describe the model in some new model language.
3. Writing serializable, text-based structures—nowadays, this mostly means "XML."
4. Writing serializable binary structure.
5. Writing database-based structures.

Which one to choose? Essentially, the question hinges on whether the interface should be of a form that can be read and written by humans, or not. If not, then we have immediately decided that we need a separate program to capture the model and writing the "bytes" to the interface. This is legitimate, but that program costs up-front money. So I discard—in my context—4. and 5. This leaves us with 1., 2., and 3.

My experience here is to go with alternative 2. as often as possible.

• "But isn't that the hardest one? After all, for both 1. and 3., the parsers and the converters to internal models are ready-made, whereas 2. requires writing a new parser."

This reasoning is seriously flawed. Creating that parser is easy with the right tools (I use ANTLR, but there's GoldParser and others). Our main concern right now is to find a description that "fits the problem." And for this, I do not want too many restrictions.

• XML is obviously a horrible language for humans—its "readability" is so bad that it can just be used for debugging purposes; or for very simple interfaces (people who do not see this are IMHO already "brainwashed" by "XML for everything" proponents).
• With alternative 1., one gets distracted by the idiosyncracies of the concrete programming language, and various design concepts (e.g. a fluent API design vs. a statement-level API). The limitations of an API modelling approach sometimes even lead people to design "string based APIs", i.e., functions with string parameters that are parsed to define the model. But this is obviously a poor man's version of alternative 2, with the disadvantages of 1 and 2 combined.

Alternative 2 is not without problems:

• Language design needs considerable freedom of thinking; one must not fall into the trap of including existing language concepts, like "there must be an if-statement in every language."
• Text-based languages are one- or at most two-dimensional—this can lead to awkward formulations of complex relationships (think of the contortions needed to describe a general graph in XML).

On the other hand,

• thinking about and in a new language is the most liberal way to attack a problem (there is an old mathematical saying: The correct notation is half of the solution);
• languages allow easy insertion of comments, so there is no high pressure to make everything easily usable in the first place;
• and finally, any standard text editor can be used to write text in the new language—with modern editors, there's even easy highlighting and other such features included.

So the tool infrastructure follows the activity model above 1:1:

Before we accept this as a good solution, let's think a little bit more about the activities. If we are honest, the process above is far too idealized: When creating the various inputs, I'll certainly make mistakes—place the pictures at the wrong place, define an unintended movement like too fast or too slow movements. And, moreover—maybe I should have placed this first -, I want to work incrementally: Get the objects for the intial part of the animation, have them move around, adding more objects and more moving, maybe adding text at some place etc. Therefore, the actual process is much more iterative; there is a flow of information from the various outputs to the input:

This means that I need to use all these tools at the same time (this is, of course, the argument for "big integrated software solutions"). But of course, this is not a problem per se—it just requires a little caution in the design of the tools (so that e.g. a tool does not lock a file for its use only). Then all work will flow freely.

Movimentum - Animating Mechanical Explanations

I think I'm going to write a program. A program for creating small movies—"animations for machines."

Why?

Well, I'm writing a blog on Austrian signalling equipment. And like the few web sites that I know with that topic, I use pictures and text to explain the various machinery used in that field. However, even people who know much about railways have a hard time to understand this sort of things. So, in these modern times, it seems obvious to show the actual movement of such apparatus in an explanation: Animate the explanation!

Now, I must obviously be more concrete about the scope of these explaining movements.
For example, couldn't I simply show an actual film clip of the workings of some machine? First of all, I do not have those clips. But more important, if you know descriptions in technical books, you know that this is not the way to go: Actual machinery is rusty and painted and obscured by housings—all great ways of hiding the important parts. So we need abstract drawings which we assemble into a "moving model."
Next question: Shouldn't one allow user interaction with the model—i.e., provide a simulation? No, for two reasons: When I explain something, I am the director who defines what is going to happen. The user may come in at a later stage, e.g. in an "exercise"—but not during the initial explanation. And, moreover, and honestly, simulation (i.e., providing "n" ways of what can happen) is much more work than animation (i.e., providing one way of what happens).

To be very concrete, here is a website that has exactly the sort of animations I'd like to provide: www.animatedengines.com. My only wish is that creating such an animation should be at most two hours of work—one hour for drawing the parts, another one for animating them. That's why I need a program.

I asked and looked around (a little) whether there is some software that can do this. Obviously, there are real simulation packages that can do all that and much (much much) more; but they are expensive, and—I suppose—hard to learn. Then, there are animation packages (Blender comes to mind, [Update:] Synfig has been suggested)—but they have huge disadvantages from my point of view:
(a) They are integrated systems—whereas I want to create my drawings in a CAD program (everything else is useless with technical systems);
(b) They have, as far as I know, only limited trajectories (linear, constant, maybe spline).

In principle, modern CAD programs can do animation—but not my somewhat cheap CAD program (derived from the German CAD program Caddy++).

So I'll try to outline (in the next posting), and then develop, a new animation process for my purposes.