chrishowie.com

I wrote a while ago about a project I had started to develop a universal trainer for Linux. I’ve been intentionally delaying the public release because I wrote it as one of my first C# projects and the codebase was less than maintainable, and probably had a lot of memory leaks. Additionally, the UI was created using Glade and instantiated using Glade#.

I’ve been working over Thanksgiving break to bring it up to par with my other projects. Basically this means a complete rewrite, except for the C glue library. Surprisingly, much of the codebase is identical, but the pieces that have changed have changed dramatically. The UI has been rewritten with MonoDevelop’s Stetic designer, and there should be no major memory leaks. The UI is more streamlined and search speed has been improved. In fact, where it used to use several MB of memory at a time during searching, it should now use next to none.

This is why I haven’t released for over a year. I knew this had to be done first, but I hadn’t got around to it. I expect a beta release by the end of next week. Two more things remain to be implemented: search result narrowing (important) and freezing (less important but still cool).

If I haven’t already said so, the project will be released under the GPLv2.

Over two nights of hacking I implemented a movement filter that’s compatible with the AVS Dynamic Movement effect.

Google Video was giving me grief, so I posted it on YouTube this time:

Lately I’ve taken to hacking Affe quite a bit. Just a quick list of a few changes:

• Value types can now be the target of invocations.
• A value type will be automatically boxed when being cast to an interface that it implements.
• Any object type can now be unboxed. This fixes the case where a value type boxed into an interface type could not be unboxed without being cast to System.Object first.
• Any expression can be used as a boolean. Reference types will be compared to null, and numeric values will be compared to 0.
• Added the &&, ||, and ?: operators.
• null is now a keyword.
• Fixed a parser bug that would cause syntax errors when the sequence “(identifier)” was encountered and did not begin a CastExpression.
• The == and != operators can now be applied to reference types.
• OperatorExpression now checks for operator overloads and uses them when present.
• Arrays and types with indexers can now be indexed.
• Added support for single-line (//) comments.
• Added a “local bag” which is used when building locals.

The last item could use some explanation. It’s a size optimization really, and probably unneeded, but I’ve always thought something like this would be neat for mcs to have. This implementation is my proof-of-concept.

There are a lot of things that require extra locals to be defined. For example, if some method returns a value type and you’re directly invoking on it (for example, somestring.Length.ToString()) then there are two IL sequences that could be used. Assuming the int is on the top of the stack, the first is box System.Int32; callvirt instance string object::ToString();. This is what seems intuitive, but there’s a reason mcs does not do this. Boxing creates a new object, and that object must now be garbage collected. It’s much more efficient to use the stack for value types. So instead of boxing, a new local is declared, say “temp”, and this IL is used: stloc temp; ldloca temp; call instance string int32::ToString();. No boxed object, no virtual method resolution, no additional strain on the GC, no wasted heap. But now we have another local.

What if you hard-coded ten such calls? That’s right, you get ten locals. The JIT may be smart enough to optimize them out, but the IL is still going to be bloated. That’s where my local bag comes in. When such an expression is compiled in Affe, it asks the compiler state object for a local from the bag, for temporary use. The state will look through a list of unused locals it has and will return the first it finds of the same type, but will keep it in the unused list (since the callee said it’s temporary). If none can be found then it will create one and add it to the list. (If the local was requested for permanent use then it would be removed from the list if it was there, or if it wasn’t then it won’t be added to the list.)

The upshot of this is that if you make 10 hardcoded invocations against a value type that’s being returned from somewhere (or even a constant) they will all use the same local, assuming they’re all the same value type.

Now consider the case where you have this code in C#: if (foo) { object o; ... } else { object o2; ... }. This is admittedly contrived, but it does the job. We have two scopes with a variable of the same type. With mcs you get two locals. With Affe you get one.

To maintain scoped variables, the Affe compiler state maintains a stack of symbol tables. Each block has its own table that is pushed prior to analysis, then popped, and again for the compile pass. When a table is pushed, the state will check for symbols that correspond to locals and will remove them from the local bag if present. Then when popped, all the locals are added to the bag. So in the example above, the “if” block’s table is pushed during analysis and a new local symbol is added. Then it’s popped, and the local gets put in the bag. When the “else” block’s analysis is run and it asks for a local of type object, the one from the bag is handed to it.

It’s not a terribly major optimization, and I expect in Affe’s case it actually takes more time during compilation than it saves during runtime, but I’m interested if this would be interesting for the mcs hackers. I imagine it would eliminate a fair amount of IL bloat.

I have finished removing Lua from Kaffeeklatsch and have enhanced Affe with the ability to bind field, property, and method calls at runtime. I noticed this gap when rewriting some of the key binding scripts; where I could just set a field before, my compiler threw an exception since it could not find the field on the IEffect interface. After wrestling with this for a while I finally came up with another hackish solution: a new operator.

The period operator binds during compilation, and the new dollar sign operator binds during runtime. Instead of the standard target-arguments-call emission, it emits a call to a static method declared inside Affe that takes the target object, the member name, and an object[] containing the call parameters. This method performs logic similar to a compiler-bound call (in fact, basically identical logic) except using the target’s runtime type. One annoying pitfall of this technique is that since the return type cannot be known at compile time, a late-bound invoke necessarily returns an object. And, of course, to unbox a primitive you must perform an exact cast.

Since I didn’t unbox automatically I added a parenthetical cast operator to Affe so that late-bound return values can be unboxed or converted. (Note that boxing is automatic.)

So where something like Effect("fountain").Rotate = true; would make Affe choke, this can now be written as Effect("fountain")$Rotate = true;.

I am toying with the idea of flagging certain types to be intelligently bound. For example, if IEffect was so flagged, the compiler would try resolving the call and if it could not bind it, would convert the expression to a late-bound call. This would give all the speed of compile-time binding where possible, and fall back on runtime binding when that failed. Since I’m trying to make Affe basically a fast scripting language for .NET, this is optimal. It may make debugging harder since errors are not caught at compile time, but you’d have that problem with the $ operator anyway.

I got Kaffeeklatsch back out of the toy box the other day and started integrating the Affe compiler into it. The goal is to remove Lua entirely, as it’s an unmanaged dependency and has been giving some odd errors as of late, crashing mono after a few seconds.

The SuperScope effect has been completely converted over from Lua to Affe. (Keybindings and the Custom effect are next on the list.) To celebrate this achievement I have posted a teaser video on Google Video. The quality is pretty horrible and there is no audio, but you get the general idea:

There are a few effects you are seeing here:

• Clear screen is responsible for the slow fadeout to black.
• The flames, blue scope, and neon lines are all instances of the SuperScope effect with different Affe scripts.
• The multicolored star is a FountainScope effect.
• About 13 seconds in I turned the Laser effect on. This instance draws moving black rays from the center.

Every effect is a managed object; SuperScope is the only one in this video that uses user-supplied scripts; the others can have other parameters tweaked from the Gtk# preset designer.

But not motivation to code.

Since my last post, the following changes have been made to Affe:

• The AffeCompiler class has been split into two classes. AffeCompiler stores information about the configuration (host type and symbol table) and passes copies to AffeCompilerState for actual compilation. This allows the host class information to be cached when compiling repeatedly against the same class, and for changes to the symbol table to be retained.
• The parse tree is no longer immutable. It became apparent that to perform optimizations and other tweaks to the compiler output changing the tree is desired.
• Added type system. Expressions are automatically cast between required types. Methods and fields on the host class can now accept and return any type.
• Added support for string literals.
• Moved the tree classes into their own namespace.
• Transform methods have been improved. The AffeTransform attribute now takes a Type instead of an int. This type specifies the “return type” (actually the type of the object left on top of the stack). This allows for a primitive form of vararg methods, and the method can simply throw an exception if the count of expressions is incorrect.
• Refactored the DefineLocals tree of calls into an AnalyzeTree tree, which not only finds locals but adds casts where required and does some other nifty optimizations.
• All tree classes except Root now inherit from Node, which provides a property for accessing the node’s location in the input text.
• Added better error support. Exceptions now contain the Node causing the error. Combined with the Node’s property this allows the location of the error to be displayed.
• Added TypeSymbol, which maps an identifier to a Type.
• Added support for method, field, and property access, both for objects (instance invocation) and types (static invocation).

Type systems can be complex. jchambers summed it up pretty well:

12:33 < SerajewelKS> whew, writing compilers is easy until you decide to add support for types besides float

12:34 <@jchambers> until then I think you just have a calculator.

Look for the next post, where hopefully I’ll have typed variable declaration and a customizable default variable type. After that there are a few fringe cases I might address such as invoking members on value types, which require special treatment in IL.

Today I added:

• Variable persistence. If a field of type ScriptState is tagged [AffeBound] on the host class, it will be used to store the state of all of the variables local to the script. If no such field is found, no state preserving IL will be emitted.
• Bound methods can now return anything, but only methods returning float can be used in expressions. Others can be used in call statements.
• The return keyword is now supported. In the case of a state-preserved script, it will cause a jump to the code that stores variable state.

The library is also in my public Subversion repository: svn co https://layla.chrishowie.com/svn/Cdh.Affe.

Well, the plan was to have Affe be a simple language. I guess it still is, but I’ve been adding support for many C-style language features and tweaking other features over the past day. Specifically, the following:

• Added if/else support, with the same nesting rules as C.
• Added the following operators:
  • ! (boolean not)
  • == (equality)
  • != (inequality)
  • < (less than)
  • <= (less than or equal to)
  • > (greater than)
  • >= (greater than or equal to)
• The tree is now scanned for variables before compilation, since with conditionals it’s no longer sufficient to initialize an unassigned variable the first time the compiler sees it. All variables local to the script are initialized to zero before the tree is compiled. This may be optimized later if the performance impact is really all that bad.
• A call can now be used as a statement instead of just in an expression.
• Added support for while loops, including the continue and break keywords.
• The library is now licensed under the LGPL.

The next two planned features are:

• A state preserving mechanism, like I discussed in my last post. I’ve been putting this off because I’m having trouble coming up with a clean way to pass the state object around.
• Subroutine support. The subroutine would be compiled into its own dynamic method (meaning that it would not share scope with the enclosing script) and would be called from the main script.

Subroutine support brings up two interesting points. One is that variable state persistence would probably not be able to extend to them, as storing its state on the same object would not make sense considering that the scope would be different. Presumably one could chain the states together using the subroutine names, but I’m not sure that persistence would really be needed in the case of nested subroutines anyway.

The other point is about the lifetime of a DynamicMethod. These objects are eligible for garbage collection, which is kind of their point. But if I call one DynamicMethod from another, and then discard the reference, could the GC destroy the method while the method that calls it is still alive? (And do Mono and MS.NET agree what should happen?) This is an important question to answer right now, because it would be pointless to implement this if the GC will ruin it.

(Actually if the GC would destroy the method, it could be worked around by maintaining a mapping between weak references to caller methods and strong references to the callee methods. The callee method would be discarded when its caller weak reference is collected.)

Okay, enough rambling.

Introducing my new CLI language, Affe. While not exactly flexible, the language will be useful to me.

Since the goal was to have an expression-evaluating language that targets DynamicMethod instead of Assembly, it’s not used the same way most other languages are. It cannot be used to define subroutines or manipulate objects. In fact the only supported variable type is float.

Methods and variables are provided by a class that the embedder provides. Attributes are used to control which members are exposed to Affe.

A picture is worth a thousand words, so here is an example of how it could be used:

public class AffeTest {
	private delegate void AffeCall(AffeTest t);

	[AffeBound]
	public float X = 0;

	[AffeBound]
	public static readonly float Y = 10;

	[AffeBound]
	public static float abs(float a) {
		if (a < 0)
			return -a;

		return a;
	}

	public static void Run() {
		DynamicMethod dm = new AffeCompiler().Compile(
			typeof(AffeTest), "X = abs((5 - Y) * 3);");

		AffeTest obj = new AffeTest();

		// Invoke with reflection -- slow.
		dm.Invoke(null, new object[] { obj });
		Console.WriteLine(obj.X);

		obj.X = 0;

		// Invoke with a delegate -- very fast.
		AffeCall d = (AffeCall)
			Delegate.CreateDelegate(typeof(AffeCall), dm);

		d(obj);

		Console.WriteLine(obj.X);
	}
}

While not much, this serves to illustrate most of Affe’s features. A class is created and various fields and methods are bound (note that Affe correctly handles static fields and methods), a script is compiled against the class, and run against an instance of the class.

Note that any field whose type is not float and any method whose return type and all parameter types are not float will be ignored. There is one special exception to this case. A method tagged [AffeTransform(n)] is a sort of “virtual” method taking n parameters. It will be called with two parameters, an AffeCompiler and an Expression[]. The method can then use the compiler object to emit IL. Therefore these are compile-time methods and can be used to make up for the otherwise limited language features without requiring method calls during run-time.

In case I forgot anything, here is a feature list:

• Implicit variable declaration. (Variables used prior to assignment are set to 0.)
• Binding of variables and calls to class members.
• Compile-time transform methods.
• Operators +, -, /, *, |, &, and %.

The next feature on the list to add is variable state persistence. In other words, the ability for the values in local variables to persist from call to call, possibly by way of a state object passed by the caller. Of course values in bound fields will persist, but this will allow all variables to persist without prior knowledge of their existence.