This page contains a few of my recent programming experiments. Everything you find on this page is hereby released to the public domain, but if you happen to use anything you find here for something interesting, I would appreciate it if you could mention the origin and/or notify me.

RASCAL - a .NET compiler for a tiny Pascal sub-set

The Rascal project wasn't created with the intention of using the compiler for production. Rather, I wrote it to familiarize myself with C# and the CLR in general, and the Reflection.Emit namespace in particular.

The Rascal language has the following key features (and omissions):

- Data types: The simple data types 'integer' and 'boolean' are supported - none other. No user-defined types are supported. Arrays are supported, but only zero-based, one-dimensional ones.

- Supported flow control statements:

 - if <condition> then <statement(s)> [else <statement(s)> ] endif,

 - while <condition> do <statement(s)> endwhile,

 - repeat <statement(s)> until.

There are lots of other omissions as well. In fact, I designed the syntax for Rascal sort of backwards by first writing the (rather naive) program that I wanted the compiler to be able to compile:

program Primes;
        
  procedure ComputePrimes;
  var
    Divisor : integer;
    Candidate : integer;
    DivPtr : integer;
    Fail : boolean;
    I : integer;
    Found : integer[500];
  begin
    Found[0] := 5;
    I := 0;
    Candidate := 5;
  
    repeat 
      Fail := false;
      DivPtr := 0;
      Divisor := 3;
      
      while not Fail and ((Divisor * Divisor) <= Candidate) do
      
        Fail := (Candidate mod Divisor) = 0;
        Divisor := Found[DivPtr];
        DivPtr := DivPtr + 1;
        
      endwhile;
      
      if not Fail then
      
        write(Candidate);
        Found[I] := Candidate;
        I := I + 1; 
        
      endif;
      
      Candidate := Candidate + 2;
      
    until Candidate > 3000;
    
  end; 
  
begin
  ComputePrimes;
end.

The scanner and parser for the Rascal compiler was built using a generator program, Coco/r for C#. You can find a link to it on the links page. The Rascal grammar in Coco/r format is included in the archive (rascal.atg) along with the syntax tree definition and the actual code emitter (both in rasdef.cs), as well as the source for the prime number generator code above (prim.ras). I don't include binaries as you can easily reproduce Rascal.exe - the compiler - with any C# compiler, and with that in hand, you can then compile prim.ras into prim.exe, and verify that it works.

Beyond these comments, the source is the documentation.

Enjoy.

MoveStats - a unit for logging arguments to the Move standard RTL function in Delphi

The unit came about because the nice folks at the borland.public.delphi.language.basm newsgroup had written an optimized replacement function for the standard RTL Move procedure. I wanted to get some metrics that could tell me whether using the replacement function in my projects was worthwhile.

To use MoveStats, you mention it as the first unit in your project's USES list. This ensures that the unit gets initialization service before any other unit, and that is a requirement if you want Move stats for the entire project.

Once you've recompiled, you run your application as normally. There's a slight overhead associated with MoveStats' logging, but it should not be noticeable. When your app terminates, MoveStats will emit a log file to the current directory with the name MoveStats.txt.

Currently, the MoveStats unit supports two logging modes, RecordSizeCaller and RecordSizeAlign. One of the two modes is enabled using a compiler define at the top of the unit. The default is RecordSizeCaller.

The RecordSizeCaller mode causes MoveStats to collect statistics on the calls to Move based on bytes moved, the caller, whether the source and target data is identical before the move, and whether the source and target buffers overlap.

The data is represented in a list like the following:

Move stats
----------
      Size    Caller     Count      Same   Overlap
         1   404891h    875332         0         0
         1   404B6Ah    402194         0         0
         1   404B6Ah    265050         1         0
         2   404891h    226659         0         0
         3   404891h    144242         0         0
        11   404891h     54860         0         0
         4   404B6Ah     48580         0         0
        11   404A37h     47186         0         0
        11   4047F4h     46754         0         0
        18   404891h     27167         0         0
        ....

In this instance, the most calls to Move with a particular size came from location 404891h with a size of 1 byte. The source and target data was not the same before the move and the source and target buffers did not overlap. Inspection of the .MAP file for the project reveals that location 404891h lies in the LStrFromPCharLen RTL function. As it turns out, many of the calls to Move will tend to come from inside Delphi's own string and PChar handling routines in the RTL.

The second highest activity was also a one-byte call to Move and came from 402194h, which is LStrCatN, another Delphi RTL function related to PChars and strings.

The third entry has a one in the Same column. What that indicates is that the data in the source and destination buffers was identical. In this case, where the move is a one-byte move, it's highly probably that the fact that the data is identical is a coincidence. The Same column was included to identify situations where a buffer is being unnecessarily reinitialized. In fact, there were a few cases in this analysis but none were very significant.

The final column, Overlap, could potentially be used for identifying call sites where a simpler Move procedure - one, which doesn't take the possibility of overlapping source and destination buffers into account - could be used.

The second mode, RecordSizeAlign, causes data to be logged based on slightly different metrics, namely size and the four combinations of source buffer aligned/unaligned and target buffer aligned/unaligned.

Move stats
----------
       Size      ua/ua       a/ua       ua/a        a/a      total
        967          0          0          0          2          2
       3868          0          0          0          1          1
          0       2095          3        507       3284       5889
        968          0          0          0          3          3
        ....

It's interesting to note that this report includes almost 6,000 calls to Move with a size of zero. FYI, these come originate almost exclusively in the RTL string/PChar handling routines as well.

DeltaLib - a patch generator/application tool in C#

The original version consisted of two tools, COMPARE.EXE, and MODIFY.EXE. 

COMPARE.EXE generated a binary script from two source file names. The script encapsulated the difference between the source files. 

MODIFY.EXE, generated the modified file from a copy of the original file, and the script.

This version combines the functionality of both COMPARE and MODIFY in one .NET assembly, DeltaLib.

The source is fully managed C# and is a fairly trivial port of the original TurboPascal code. 

DeltaLib's most significant limitation is that it can resynchronize over at most 16K of differing bytes. If DeltaLib fails to resync between the original and the modified, it will include the entire modified file in the script.

I do not claim that this tool is better than other, similar tools out there, and that it can't be optimized (it can), but it is reasonably efficient as is, and it is my original work.

Reversi

For years, a fellow programmer - and old friend of mine - and I have been informally competing in the discipline of writing the best Reversi-playing algorithm. We would write new 'thinking' DLLs which adhered to an agreed upon interface and play the various versions against each other using a shell program. The archive below contains the current .NET reversi shell as well as one of my better playing engines. 

You can use the game purely as entertainment, either by playing against the built-in engine, or by watching it play against itself. You can also take on the supplied engine by writing your own Reversi game-play engine and install it in the shell.

The archive contains the following files:

- Reversi.exe: The actual game program (does not contain any 'thinking' logic).

- RevInt.dll: Defines the binary interface between Reversi.exe (the shell) and the thinking engines.

- RevInt.cs: The C# source code for the interface definition.

- RevThink0.dll: A very basic C# Reversi-playing engine. It simply picks a valid move at random.

- RevThink0.zip: The C# source code and VS project for RevThink0.dll.

- DRevThink0.dll: Same as RevThink0.dll but written in Borland Delphi 8.

- DRevThink0.dpr: The source code for DRevThink0.dll.

- RevThink06.dll: A reasonably strong Reversi player - written in C#.

- Engines.xml: Contains a list of the available engines in XML format. Reversi.exe parses this on startup. Please refer to the file for information on how to specify additional engines for the shell.

How to write and use your own Reversi-playing engines

Basically, you must create a new .NET DLL in your favorite .NET language, add a reference to RevInt.dll, and implement a class, which implements either IReversiPlayer or IReversiPlayer2.

IReversiPlayer is defined as follows:

public enum GameColor
{ gcEmpty = 0, gcBlack = 1, gcWhite = 2 }
        
public enum GameMode
{ gmGameTime = 0, gmMoveTime = 1, gmFixedPly = 2 }
        
public interface IReversiPlayer
{
  int BestMove(GameColor[,] Board,
    GameColor PlayColor, GameMode Mode, int TimeOrPly,
    bool RandomPlay, string CustomArguments,
     out string ReturnMessage, out int x, out int y);
}

Please see revint.cs for documentation of the various parameters.

IReversiPlayer2 is identical to IReversiPlayer except that the Board argument is defined as an array of array of GameColor instead of a two-dimensional array as Delphi for .NET currently does not support multi-dimensional arrays directly.

Once you have a Reversi engine, which compiles, you must add an entry for it to the Engines.xml file and restart the  shell to make it aware of the new DLL's existence. Please see the comment section in Engines.xml for details.

It was my intention to add some more generic advice on writing game playing algorithms in general - and Reversi games in particular - here, but I'm out of time for now. I'll come back later.

If you write a DLL that consistently beats the RevThink06.dll included (not easy, but by no means impossible), please send it to me and I'll add it to the archive with appropriate credits.