Re: computer-go: Languages for programming go are?

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Sun, Dec 24, 2000 at 11:14:09PM -0800, Bob Myers wrote:
> As far as I know, most existing computer go programs are coded
> in C or C++.  I hear that HandTalk is written in Assembler,
> bless its soul.  I seem to remember hearing of a program written
> in LISP.

I'm the author of a Go program written in Lisp. Alas, I took it off
the computer Go ladder quite a long time ago in order to concentrate
on tactics. Since then, the program has become much smarter about some
kinds of tactical problems, but its general Go playing is still so
weak that I still haven't put it back on the ladder. I think the delay
is because the design approach I've taken stretches my programming
skills to the limit, not that I've chosen the wrong language.
Hopefully my program will be back on the ladder presently, but who
knows? (It remains to be seen whether I've stretched my programming
skills *past* their limit.:-)

> I have two questions for the members of this list.  
> 
> 1) What are the pluses and minuses of writing a go program in
> various existing computer languages?

If your program does a lot of complicated calculations, not just
crunching numbers but crunching dynamically allocated data structures
while doing backtracking search, you probably want something at least
as expressive as C++. C++ or Common Lisp or one of the ML variants
might all be reasonable choices. Maybe something like Prolog would be
reasonable too, but I don't understand Prolog well enough to say. My
personal choices would be Common Lisp (as efficient as possible given
maximum expressiveness) or C++ (as expressive as possible given
maximum efficiency, with the added advantage that everyone knows it
and it's available everywhere).

I started with C++, but I decided to rewrite my Go program in Common
Lisp after my positive experience rewriting much of David Wolfe's
combinatorial game theory calculator in Common Lisp. The CL version
was a *lot* simpler and clearer than the original C version, or even
than a C++ version. And since I found combinatorial game theory to be
nontrivial, that was a major advantage. I think the decision was a
good one: my Go program is significantly easier to express in Lisp
than in C++, enough so that it makes up for other disadvantages.

Common Lisp has garbage collection, an interpreter, lexical closures,
dynamic typing, a very general (but slow) built-in object system, and
extremely expressive macros (not just more expressive than C's, but
more expressive than any other non-Lisp macro processor I'm aware of,
because of the ease of parsing and manipulating Lisp programs as Lisp
data). Many things which are easy to express in Lisp are much more
tedious to express in other languages. (E.g. the CGT calculator I
mentioned; or the textbook example of implementing an OO system, with
encapsulation and polymorphism and inheritance, from scratch.) And the
interpreter makes it very easy to inspect what's going on, and to
experiment with how your algorithms work. Some of the expressiveness
and interactivity comes at an unavoidable efficiency cost (because of
features like GC and dynamic typing), but it doesn't seem to be a huge
cost, perhaps a factor of two relative to C++. Beyond that, the actual
efficiency cost of Common Lisp in current practice is higher than the
unavoidable cost (perhaps by another factor of two), because the
current Common Lisp compilers aren't as good as current C++ compilers.

To me, rewriting a Common Lisp program in C++ is about like rewriting
a C++ program in C, which is in turn about like rewriting a C program
in assembler. It's pretty obvious how to do it, and the result might
well be faster as you hand-craft an implementation of only the
abstractions you need, but the resulting program is larger than the
original, and inferior in clarity and maintainability to the original.

IMHO, the biggest problem with Common Lisp for Go programs is that
Common Lisp programming systems are much less available than C++
systems. Commercial Common Lisp systems are much more expensive than
C++ systems, and while open source alternatives exist, they're all
(including the one I work on, at http://sbcl.sourceforge.net/) much
less mature than GCC.

If you're interested in Common Lisp, check out Paul Graham's book,
_ANSI Common Lisp_. (And when you do the exercises, make sure to use
an editor which supports parenthesis matching and Lisp
auto-indentation!)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C