Monday, August 25, 2008

Meta-FizzBuzz

By itself, solving the "FizzBuzz" problem won't get you a new job. If it does, you probably wouldn't want that job. It's a weed out type of question that doesn't say much about your skill if you get it right, but it hurts your credibility as a programmer if you can't do it. It asks:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

By rearranging the words in the problem statement and adding a few programmer keywords, you can create this simple pseudocode solution:

for every number from 1 to 100                          
if the number is a multiple of 3 and it is a multiple of 5 then
print "FizzBuzz"
else if it is a multiple of 3 then
print "Fizz"
else if it is a multiple of 5 then
print "Buzz"
else
print the number

See? Simple and boring.

But what if the bar were raised in the future to be this "Meta-FizzBuzz" problem:

Create a language implementation and write a solution to the FizzBuzz problem using it.

It sounds crazy at first, but if you take it seriously, it is way more interesting than the original FizzBuzz problem. It forces you to have a deeper understanding of languages rather than just getting by with the basics. It also shows that languages are full of many design choices that often have several alternatives.

I decided to create a language implementation that would execute the above "pseudocode" solution. While working on the implementation, I discovered that needed to handle cases that I hadn't seen in "real" languages:

  • Variables can be prefixed by "the" to make the code more readable.
  • Instead of having a modulo operator (e.g. %), I picked the phrase "is a multiple of".
  • This language supports the special "it" variable that always refers to the last variable that was explicitly referenced.

These were just arbitrary decisions that I made to make the actual FizzBuzz program easy to read. Even though I'm still in the early stages of the development of OMeta#, it wasn't too difficult to write a complete "Meta-FizzBuzz" implementation in about 100 lines of code with generous use of comments and whitespace:

ometa MetaFizzBuzz : Parser {
// Basic literals come first:

// We override the Parser's version of "Number" which returns a string
// to instead return the integer value of the string.
Number ^= Spaces ('+' '-' Empty):prefix
Digit+:ds -> { int.Parse(((prefix.Count > 0) ? prefix.As<string>() : "") + ds.As<string>()) },

// Allow literal strings surrounded by quotes (e.g. "FizzBuzz")
QuotedString = Spaces '"' (~'"' :c)*:inner '"' -> { inner.Count == 0 ? "" : inner.As<string>() },

// For more natural sounding code, we allow "the" in front of a variable name.
// In addition, we keep track of the last variable name used so that we can refer to
// it as "it" later on.
VariableName = ("the" Empty) Spaces
FirstAndRest("Letter", "LetterOrDigit"):n
!{ Set("_it", n.As<string>()) } -> { n },

// Expressions are functions that evaluate to some object.
// We don't return the value directly since expressions can depend on
// global variables that could be change while executing.
Exp = AndExp
BinExp
NumExp
QuotedString:qs -> { (Func<object>) (() => qs.As<string>()) },

// An "and" expression is the highest level of a function that returns
// a boolean value. This left-recursive definition allows for an arbitrary
// number of boolean expressions to be and-ed together.
AndExp = AndExp:l "and" BoolExp:r -> { (Func<object>)(
() => (
(bool)l.As<Func<object>>()()
&&
(bool)r.As<Func<object>>()()
))
}
BoolExp,

// This rule looks at what the expression returns and then tries to
// convert non-boolean values by declaring that non-zero values and
// non-empty strings are true and everything else is false.
BoolExp = Exp:e -> { (Func<object>)(
() => {
object o = e.As<Func<object>>()();
return o is bool ? (bool)o
: o is int ? ((int)o) != 0
: !string.IsNullOrEmpty(o as string) && (o != OMetaList<HostExpression>.Nil);
})
},

// Binary expressions take two arguments (left and right).
// Here we just have the one that is relevant to FizzBuzz
BinExp = NumExp:left
"is" "a" "multiple" "of"
NumExp:right -> { (Func<object>)(
() => {
var l = (int)left.As<Func<object>>()();
var r = (int)right.As<Func<object>>()();
return (l%r) == 0;
})
},

// Number expressions are functions that just return an integer.
// Note that "it" resolves to the *value* of the variable that was last referenced by name.
NumExp = Number:n -> { (Func<object>) (() => n.As<int>()) }
"it" -> { (Func<object>) (() => Get<int>(Get<string>("_it"))) }
VariableName:vn -> { (Func<object>) (() => Get<int>(vn.As<string>())) },

// Statements are the things that actually do work in this language.
Stmt = "print" Exp:e -> { (Action) (() => { Console.WriteLine(e.As<Func<object>>()()); }) }
"if" AndExp:b "then" Stmt:t
("else" Stmt Empty):f -> { (Action) (
() => {
if((bool)b.As<Func<object>>()())
t.As<Action>()();
else if(f.Count > 0)
f.As<Action>()();
})
}
"for" "every" VariableName:n "from"
Number:low "to" Number:high
Stmt:s -> { (Action) (
() => {
int lowerBound = low.As<int>();
int upperBound = high.As<int>();
string iterationVar = n.As<string>();
Action iterationStmt = s.As<Action>();
for(int i = lowerBound; i <= upperBound; i++)
{
Set(iterationVar, i);
iterationStmt();
}
})
},

// A "block" is zero or more statements.
Block = Stmt*:s -> { (Action) (
() => {
foreach(var currentStatement in s)
{
currentStatement.As<Action>()();
}
})
},

// And finally, a "program" is just a series of statements, which is a "block"
Program = Block
}

Full disclosure: It took some debugging to get this implementation to work right.

If I had been beamed into the future and had to write this solution on a whiteboard, I would have been a bit nervous that I wouldn't have gotten it right and would have taken noticeably more time than I now take to write a FizzBuzz solution.

In order to keep the code size down, I directly execute the "pseudocode" rather than convert it to an intermediate tree. I also simplified things by making all variables in this language global. The latest version of the source code has a slightly more elaborate version of Meta-FizzBuzz that also allows an alternative pseudocode implementation.

The current implementation of OMeta# uses C# 3.0 as the host language. This makes everything inside of the { }'s two to three times uglier and larger than it might have been if I had used a more dynamic host language like JavaScript, Python, Ruby, or possibly C# 4.0. As I mentioned in my last post, my hope is that eventually I'll be able to use clever techniques to make the host code appear more dynamic even though it might need to be strongly typed.

In the end, the Meta-FizzBuzz problem is just a thought experiment to guess what the low bar might look like in the future. That is, a future where it's so easy to create a language that perfectly fits your problem that people actually do. As an industry, we're not there yet, but it's fun to dream of the STEPS needed to get there.

Feedback: What do you think the low bar will be in an upcoming era of Moore's Law Software? What do you think of the Meta-FizzBuzz problem? Feel free to post your own solution (or outline of a path that you'd take towards a solution) in the comments. Comments are also encouraged about OMeta#'s current syntax in general.


kick it on DotNetKicks.com