Tic-Tac-Toe

Comparison

There are two basic approaches to consolidating similar function definitions. One is to construct a template, or "macro", that can be customized with extra information to define each function separately. The other method is to define a single overall function that does what all of the similar functions do, except it takes one or more other functions as arguments, and calls them as needed to produce the custom behavior. A function-defining macro generates faster but larger code, because it constructs several unified functions. The functional approach requires switching back and forth between the main function and the customization functions, but only requires one copy of each piece of compiled code. The main function is called a "higher-order" function.

In most languages, macros are hard to write, because the language's syntax is so complicated that it's hard to write macros that reliably generate correct code. The single exception to this rule is Lisp, in which macros work reliably and are used wherever they're needed. Even beginning Lisp programmers can write simple macros without too much trouble.

In the examples below, syntactic macros are used in Lisp, and C-style text/token macros are used in C and C++. C-style macros are hard to work with, so their use is generally discouraged. Many C and C++ programmers would rather write full separate copies of the functions, resulting in more places for bugs to occur.

The scripting languages Perl, Python, and Ruby all have a function, usually called "eval", that can convert simple text into a function. This has the same problems as C-style macros. Python, interestingly, is so compact that the program is fairly small even without consolidation. This is due to python's use of indentation rather than extra words or punctuation marks to indicate the structure of a function. It works well for a small number of similar small functions.

While OCaml has a way of writing templates, OCaml is a functional language, so the functional approach is typically used wherever possible. This is easy to do in OCaml. Defining the small customization functions is simple, takes up very little space, and works just as well for large numbers of large functions as for a couple small ones.

Lisp is the only language whose macros can be automatically checked for syntactic correctness before the program runs. They're reliable, and Lisp programmers use them often. Easy-to-write macros are the reason Lisp source code has such an unusual appearance. Even an average Lisp programmer can write macros that analyze and generate Lisp code, because the syntax is trivially simple.

Haskell takes functional programming even farther than OCaml does. As bizarre as Lisp's surface syntax is, Haskell's functional programming model is even more extreme. Haskell is hard to learn, and debugging recursive code can be unpleasant. It's annoying having to pass the grid to every function. That said, Haskell's a blast once you learn it (if you can learn it), and it's great for writing complex, large-scale programs that don't require too much I/O or mutable state (global variables).

The two positive Haskell features that affect this program are DiffArray and lazy evaluation. DiffArray automatically resets the grid when each called function is done using it, so you don't have to worry about undoing moves in the NAB code. Laziness is necessary to define lazy operators in terms of functions. The Haskell version of T3 defines a ternary test operator in the same way that any other operator would be defined, and it works the way it should, because the branch expressions aren't evaluated before being passed to the operator.

Overall program control

In Haskell and OCaml, continuation-passing style (CPS) is used to make the next move, and mutual tail recursion is used to start a new game. With CPS, when one function calls another function, the calling function passes a third function to the function being called. This third function is the continuation, which the called function will call when it's done. CPS makes it easy to consolidate code used by both the human player and the computer.

Mutual tail recursion makes it easy to start a new game, because the programmer doesn't have to worry about the call stack. When the user wants to play another game, just call play again, even if the current game isn't finished yet. There's no need to unwind the stack with null return values or exceptions, because compilers for functional languages convert all the tail calls into jumps. So the call stack doesn't get built up in the first place. The program just keeps jumping from one function to the next.

Exceptions are used in Lisp and Perl to start a new game. Compiled Lisp could probably use CPS, but some Lisp interpreters don't optimise tail calls. Exceptions are more concise and convenient than trying to unwind the stack manually by returning null values all the way up to the top level.