Pattern matching a ZMachine

Question

Anyone following Eric Lippert's blog will know that he has an on going series where he is building a ZMachine in OCaml.

C# 7 is another step forward in adding features normally found in functional languages, native tuple support, pattern matching, local functions, etc., so I decided to port Eric's implementation to start learning the new cool stuff in C# 7 and how it would hold up when porting code from a purely functional language.

The port has been rather standard up to the ZString class where Eric starts leveraging the power of OCaml's pattern matching. You can find his implementation here. My port to C# 7 is the following:

internal static class ZString
{
 private abstract class StringState
 {
 }
 private class AlphabetState : StringState
 {
 public AlphabetState(int value)
 {
 Value = value;
 }
 public int Value { get; }
 }
 private class AbbreviationState : StringState
 {
 public AbbreviationState(AbbreviationNumber number)
 {
 Value = number;
 }
 public int Value { get; }
 }
 private class TrailingState : StringState
 {
 public TrailingState(int value)
 {
 Value = value;
 }
 public int Value { get; }
 }
 private class LeadingState : StringState
 {
 public LeadingState()
 {
 }
 }
 private static readonly AbbreviationState abbrev0 = new AbbreviationState(new AbbreviationNumber(0));
 private static readonly AbbreviationState abbrev32 = new AbbreviationState(new AbbreviationNumber(32));
 private static readonly AbbreviationState abbrev64 = new AbbreviationState(new AbbreviationNumber(64));
 private static readonly AlphabetState alphabet0 = new AlphabetState(0);
 private static readonly AlphabetState alphabet1 = new AlphabetState(1);
 private static readonly AlphabetState alphabet2 = new AlphabetState(2);
 private static readonly LeadingState leading = new LeadingState();
 private static readonly int abbreviationTableLength = 96;
 private static readonly string[] alphabetTable =
 new[] { " ?????abcdefghijklmnopqrstuvwxyz",
 " ?????ABCDEFGHIJKLMNOPQRSTUVWXYZ",
 " ??????\n0123456789.,!?_#'\"/\\-:()" };
 private static ZStringAddress GetAbbreviationZStringAddress(Story story, AbbreviationNumber n)
 {
 if (story == null)
 throw new ArgumentNullException(nameof(story));
 if (n < 0 || n >= abbreviationTableLength)
 throw new ArgumentOutOfRangeException(nameof(n), n, "Offset into abbreviation table is out of range.");
 var baseAddress = new WordAddress(story.AbbreviationTableBase);
 var abbreviationAddress = baseAddress.IncrementBy(n);
 var wordAddress = new WordZStringAddress(story.ReadWord(abbreviationAddress));
 return wordAddress.DecodeWordAddress();
 }
 public static string Read(Story story, ZStringAddress address)
 {
 return buildZString("", alphabet0, new WordAddress(address));
 (string, StringState) processZchar(int zchar, StringState state)
 {
 switch (state) 
 {
 case AlphabetState a when zchar == 1: return ("", abbrev0);
 case AlphabetState a when zchar == 2: return ("", abbrev32);
 case AlphabetState a when zchar == 3: return ("", abbrev64);
 case AlphabetState a when zchar == 4: return ("", alphabet1);
 case AlphabetState a when zchar == 5: return ("", alphabet2);
 case AlphabetState a when (zchar == 6 && a.Value == 2): return ("", leading);
 case AlphabetState a: return (alphabetTable[a.Value][zchar].ToString(), alphabet0);
 case AbbreviationState a:
 var abbrv = new AbbreviationNumber(a.Value + zchar);
 var addr = GetAbbreviationZStringAddress(story, abbrv);
 return (Read(story, addr), alphabet0);
 case LeadingState _: return ("", new TrailingState(zchar));
 case TrailingState high:
 var c = (char)(high.Value * 32 + zchar);
 return (c.ToString(), alphabet0);
 case null:
 throw new ArgumentNullException(nameof(state));
 default:
 throw new ArgumentException();
 }
 }
 string buildZString(string accumulated, StringState state1, WordAddress currentAddress)
 {
 var word = story.ReadWord(currentAddress);
 var isEnd = Utility.FetchBit(word, BitNumber.Bit15);
 var zChar1 = Utility.FetchBits(word, BitNumber.Bit14, BitSize.Size5);
 var zChar2 = Utility.FetchBits(word, BitNumber.Bit9, BitSize.Size5);
 var zChar3 = Utility.FetchBits(word, BitNumber.Bit4, BitSize.Size5);
 var (text1, state2) = processZchar(zChar1, state1);
 var (text2, state3) = processZchar(zChar2, state2);
 var (text3, nextState) = processZchar(zChar3, state3);
 accumulated = string.Concat(accumulated, text1, text2, text3);
 if (isEnd)
 return accumulated;
 return buildZString(accumulated, nextState, currentAddress.Increment());
 }
 }
}

Now I won't post all helper classes (unless someone thinks they might be relevant) but suffice to say that Utility is a static class that provides helper methods to fiddle with bits and WordAddress, ZStringAddress, AbbreviationNumber etc., are all simple semantic wrappers around int. In OCaml they are trivial to define, in C# the boilerplate code is rather substantial; they all have the following template:

internal struct ZStringAddress : IEquatable<ZStringAddress>
{
 public static implicit operator int(ZStringAddress address) => address.value;
 public ZStringAddress(int value)
 {
 this.value = value;
 }
 private readonly int value;
 public override int GetHashCode() => value.GetHashCode();
 public bool Equals(ZStringAddress other) => value == other.value;
 public override bool Equals(object obj)
 {
 switch (obj)
 {
 case ZStringAddress n:
 return Equals(n);
 default:
 return false;
 }
 }
}

Ok, so enough chit chat. My question is rather simple. Is this the best I can do to leverage as good as I can the new features of C# 7? Can anything be simplified with some syntax or feature I'm missing? The code works well but I'm interested in knowing if it can be improved. Also, I've read that some pattern matching features were cut from C# 7, would any of these have made matching somewhat easier? Like for example, matching value tuples directly by deconstructing their values? Is that in the pipeline of what may come in the future?

• Eric Lippert: I'll finish that series eventually I hope!

Answer 1

Let's look at just this block of code objectively.

public static string Read(Story story, ZStringAddress address)
{
 return buildZString("", alphabet0, new WordAddress(address));
 (string, StringState) processZchar(int zchar, StringState state)
 {
 switch (state) 
 {
 case AlphabetState a when zchar == 1: return ("", abbrev0);
 case AlphabetState a when zchar == 2: return ("", abbrev32);
 case AlphabetState a when zchar == 3: return ("", abbrev64);
 case AlphabetState a when zchar == 4: return ("", alphabet1);
 case AlphabetState a when zchar == 5: return ("", alphabet2);
 case AlphabetState a when (zchar == 6 && a.Value == 2): return ("", leading);
 case AlphabetState a: return (alphabetTable[a.Value][zchar].ToString(), alphabet0);
 case AbbreviationState a:
 var abbrv = new AbbreviationNumber(a.Value + zchar);
 var addr = GetAbbreviationZStringAddress(story, abbrv);
 return (Read(story, addr), alphabet0);
 case LeadingState _: return ("", new TrailingState(zchar));
 case TrailingState high:
 var c = (char)(high.Value * 32 + zchar);
 return (c.ToString(), alphabet0);
 case null:
 throw new ArgumentNullException(nameof(state));
 default:
 throw new ArgumentException();
 }
 }
 string buildZString(string accumulated, StringState state1, WordAddress currentAddress)
 {
 var word = story.ReadWord(currentAddress);
 var isEnd = Utility.FetchBit(word, BitNumber.Bit15);
 var zChar1 = Utility.FetchBits(word, BitNumber.Bit14, BitSize.Size5);
 var zChar2 = Utility.FetchBits(word, BitNumber.Bit9, BitSize.Size5);
 var zChar3 = Utility.FetchBits(word, BitNumber.Bit4, BitSize.Size5);
 var (text1, state2) = processZchar(zChar1, state1);
 var (text2, state3) = processZchar(zChar2, state2);
 var (text3, nextState) = processZchar(zChar3, state3);
 accumulated = string.Concat(accumulated, text1, text2, text3);
 if (isEnd)
 return accumulated;
 return buildZString(accumulated, nextState, currentAddress.Increment());
 }
}

This whole thing screams for adjustments.

Since C# it constantly trying to become more functional (why? we have F# for that...) we should take those same functional paradigms and apply them.

That first line in the method (return buildZString) should be the last. Define your functions before you use them like we would in F#. (Not sure if you have experience with it or not, but that's what is required.)

Next:

 case AlphabetState a when zchar == 1: return ("", abbrev0);
 case AlphabetState a when zchar == 2: return ("", abbrev32);
 case AlphabetState a when zchar == 3: return ("", abbrev64);
 case AlphabetState a when zchar == 4: return ("", alphabet1);
 case AlphabetState a when zchar == 5: return ("", alphabet2);
 case AlphabetState a when (zchar == 6 && a.Value == 2): return ("", leading);
 case AlphabetState a: return (alphabetTable[a.Value][zchar].ToString(), alphabet0);

I saw that and died on the inside a little, considering what you're doing with this you should rewrite that to one case for AlphabetState and then sub-cases for zchar. It's nice that you're trying to use the new C#7.0 features, but let's not abuse the new C#7.0 features. You can make the first case AlphabetState a and then test zchar from there.

This little guy:

private static readonly int abbreviationTableLength = 96;

Should be a const instead of readonly. The purpose of readonly is to allow for setting the value in the constructor, and making values which cannot be const immutable. If the value (such as an int) can be a const it should be.

In this Equals:

public override bool Equals(object obj)
{
 switch (obj)
 {
 case ZStringAddress n:
 return Equals(n);
 default:
 return false;
 }
}

There's no need for the switch, none at all:

public bool Equals(object obj) => obj is ZStringAddress && Equals((ZStringAddress)obj);

Let's try to keep it simple, less work is better, for the programmer and the system.

• InBetween: Thanks! All good advice. About the const, the reason it isn't is because I'm not sure that's true throughout all zmachine versions. It was a conscious decision.
• Der Kommissar: @InBetween In that case, you may be fine with readonly, but I would still use const until you find that it is too restrictive.
• InBetween: I'm changing some of the code based on your advice and I'm not sure handling Alphabet a and then inside handling zchar is that straightfoward; the case case AlphabetState a when (zchar == 6 && a.Value == 2) breaks up that nice independent world between both matching crtierias. I'd need to create some spaghetti code because alpabet a when a.Value == 2 only has a special meaning when zchar is 6, how would I implement that clearly with your proposal?