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

14 comments:

zack said...

Definitely an interesting problem. I can see this sending some candidates running screaming from the interview, but I guess if that happens you don't really want them anyhow :-)

Jeff Moser said...

zack: I don't think I'd be mean enough to actually ask the Meta-FizzBuzz problem in an interview... yet :)

The current state of language-oriented thinking is seems a bit too niche right now for people to take it seriously.

However, I keep coming back to the thoughts that Alan Kay said to the effect of "if you really understand something, you should be able to craft a language for it" going off the Plato idea of being able to "divid[e a problem] at the joints, as nature directs, not breaking any limb in half as a bad carver might"

It just seems that a Moore's Law increase in software expressiveness is going to spread the notion that languages are cheap and can be crafted to ideally suit whatever business or inquisitive problem you want to solve.

MaysonicWrites said...

The Lisp Way - on steroids.

Jeff Moser said...

maysonicwrites:

I thought about doing a Meta-Lisp, but it's already been done in OMeta, so I went with Meta-FizzBuzz instead.

As it turned out, Meta-FizzBuzz turned out to be Pascal-ish. The fact that I have statements and global variables makes it a very imperative language. However, these were just arbitrary decisions, you could have gone with a functional approach instead.

Alexey said...

One thing that I really don't like about the current incarnation of OMeta# is the constant struggle with the static type system. Wouldn't

int Number = Number:int n Digit:int d -> { n * 10 + d }

or something like that fit .NET better than

Number = Number:n Digit:d -> { n.As<int>() * 10 + d.As<int>() }

?

Jeff Moser said...

alexey: Thanks for taking the time to leave a comment!

The latest commit of OMeta# is much closer to what you're talking about because of the notion of being able to specify a default type as well as specifying the type at point of variable declaration.

Here's a line from the latest Calculator grammar that exploits this feature:

Number ^= Number:n Digit:d -> { n * 10 + d } | Digit,

This is made possible because of this declaration: "ometa Calculator<char, int> : Parser<char> {" which states that by default it is mapping char streams to integer objects.

Alternatively, you could have been explicit and said

Number ^= Number:n<int> Digit:d<int> -> { n * 10 + d } | Digit,

You're absolutely right that it's a struggle against the static type system. My goal is to keep doing as much as I can to make things feel more dynamic while keeping the goodness properties that static typing allows.

I'm just making gut feel guesses as to what seems best based on my own usage of OMeta#. I love any and all feedback on these decisions.

Alexey said...

I've looked at the latest commit (just after leaving my comment), and it is much nicer in this respect. But consider a grammar where several output types are widely used, say, a calculator which should work on ints, doubles, and decimals. One of them may be used as a default, and variable capture helps too.

But all the casting is still going on under the surface. I've tried to make HostExpression generic in the m_value type, and Rule in the output type, but haven't had much progress so far.

Jeff Moser said...

alexey: Thanks for looking at the code. Let me know if you need help understanding something. I haven't yet done a pass to make the code more readable yet. Unfortunately the code is still in a "braindump" state. I'm hoping that I'll be able to actually add syntax sugar so that you don't have to explicitly say "Sugar" in the host actions.

You're right in calling out that defaults and variable capture type definitions are hacks. They help, but aren't perfect. I think the long term solution might be to accept static typing where possible and then allow for reflection-based (e.g. dynamic) where you don't want to do type annotations.

At least.. that seems easier than a foolproof duck type-inference algorithm.

Alexey said...

The difficulty I've run into is typing ApplyWithArgs and SuperApplyWithArgs. And I've no idea how I could get around it without a) making a lot of generic rule types for different number of arguments, which breaks down once someone needs one argument more than I've supplied; or b) making them generic in output argument only and taking an array of objects as arguments, which gets us right back to doing a lot of casting.

Jeff Moser said...

alexey: You're right; arguments go onto an argument stack that is difficult to type. I mentioned this in my last post. OMeta/JS does this and is fine since types sort of melt away in a dynamic way. I could achieve the same in C# by using Reflection everywhere at the expense of some speed. I think that with C# 4.0, I could put all of the semantic actions in a dynamic { ... } block and let the compiler worry about emitting optimal DLR expressions to make it most efficient.

Mark Miller said...

After a recent post I did I feel like I understand your post a little better now. I came upon an article by Chris Crawford that I think relates real well to your use of the term "it" in your language. In his essay he talks about abstraction, both in natural language and in programming. He said that abstraction exists in natural language, but it's "loosey-goosey". It's arbitrary, but our brains are sophisticated enough to figure it out (usually). He said that programming introduces precise notions of abstraction, enabling us to "think about issues of abstraction more clearly and powerfully, just as a strongly conjugated language allows one to express ideas of action with greater clarity."

Jeff Moser said...

Mark Miller: I found your post to be a good review of the philosophy behind The Computer Revolution Hasn't Happened Yet. I also liked Crawford's analogy to the need for an alphabet to democratize what Kay might call "computering" for all.

Meta-Fizzbuzz was just a very basic attempt to demonstrate what might happen if we allow scoping rules to be a bit less conventional (e.g. a global state that remembers variable references).

To be fair, I don't think "it" would be useful in large blocks of code as you'd lose contexts, but I think the design would force "programmers" to be brief, which would be a good feature.

The larger overall context is that bootstrapping to a world where you can experiment with these ideas keeps getting cheaper. This trend just might eventually allow "Revolution."

WildWil said...

Interesting notion indeed.
We didn't go that far, just made it an iPhone app with a score attack mode. Beer not included :) And certainly can be used as a weed out tool too. Though I have to admit we hadn't thought of that one....

Feel free to check it out here:

http://buzzyteam.wordpress.com/fizzbuzz/

Jeff Moser said...

WildWil: Meta-programming is its own game for me :)