Snakes! On a Yeti!

Continuing on my Lisp kick, I have been reading Programming Clojure, by Stuart Halloway. But that fact is a red herring for the moment; I have also been looking at a language called Yeti. In order to take a pass at Yeti, I was casually trying to find a good sample program, which I finally found in Programming Clojure: the Snake game from section 6.6.

Yeti is a ML-style programming language for the JVM, featuring Hindley-Milner type inference with structurally-typed records and open variant types similar to O'Caml. It also provides reasonable access to Java and compiles to JVM bytecode. Yeti is similar to Scala, and andrewcooke posted what I believe is a good comparison on Hacker News; the key point is, "scala is baroque; yeti minimal."

As described by Halloway, "The snake game features a player-controlled snake that moves around a game grid hunting for an apple. When your snake eats an apple, it grows longer by a segment, and a new apple appears. If your snake reaches a certain length, you win. But if your snake crosses over its own body, you lose." The implementation is simple Swing and Halloway lists a number of other implementations for comparison:

• Typed Scheme
• Small and readable Java
• Tiny Clojure
• Partially verified in ACL2
• Readable Clojure

Bear in mind that this is literally my second Yeti program, following hello-world. I have fiddled with ML a bit and O'Caml a lot (for a while, it was my official favorite programming language). I have also done rather a lot of Java lately, but only a small amount of Swing. Comments and suggestions are more than welcome.

Given that, this is my version of Snake, snake.yeti.

import java.util.Random;
import java.awt: Color, Dimension, Graphics;
import java.awt.event: ActionEvent, KeyEvent, ActionListener, KeyListener;
import javax.swing: JFrame, JPanel, JOptionPane, Timer;

The program begins with a stack of imports, for the Java classes needed later. Each class can be imported separately or multiple classes from the same package can be listed together.

A functional model

width = 75;
height = 50;
pointSize = 10;
turnMillis = 75;
winLength = 5;
dirs =
  [ KeyEvent#VK_LEFT :  {x = -1, y = 0},
    KeyEvent#VK_RIGHT : {x = 1,  y = 0},
    KeyEvent#VK_UP :    {x = 0,  y = -1},
    KeyEvent#VK_DOWN :  {x = 0,  y = 1} ];

These variables (in the mathematical sense) describe the width and height of the game grid, the conversion factor between the grid and pixels, the length of a game time step in milliseconds, and the number of segments required to win. (5 is a "boringly small number suitable for testing.") dirs is a map from numbers, given by static constants in the Java class KeyEvent, to points, as represented by a record or structure with x and y fields. dirs will be used to map key press events to changes in direction for the snake.

Using the Yeti REPL, I captured Yeti's inference of dirs' type:

dirs is hash<number, {`x is number, `y is number}> = [38:{x=0, y=-1},...elided...]

Similar to Java's Map<K,V>, dirs is a map from number (Yeti's only numeric type, as far as I know), representing the key event values, to structurally-typed x,y pairs where each field is also a number.

Because any key event will wind up looking in dirs, it is convenient to set a default for unrecognized key event values using setHashDefault. The first argument to setHashDefault is the map to be updated, while the second is an anonymous function (using Yeti's do notation) which ignores the argument (which is the unrecognized key) and always returns a null direction. (This will have the effect of pausing the game, if your snake has not eaten any apples. If your snake has eaten apples, you will lose immediately. But at least it doesn't throw any exceptions. Don't like it? Submit a bug report.)

setHashDefault dirs do _: {x = 0, y = 0} done;

See below for more about functions and do.

When I originally wrote this, I needed a couple of list utility functions, which I knew might be part of the standard library (the only documentation I had was a cached copy of the Yeti tutorial), or better expressed another way. The lists I am working with are the segments of the snake, which will not be terribly long, so I figured it did not matter much.

// butLast lst =
//     if (length lst) <= 1 then [] else (head lst) :: (butLast (tail lst)) fi;

// member? v lst =
//     if empty? lst then false
//     elif v == (head lst) then true
//     else member? v (tail lst)
//     fi;

butLast copies a list, excluding the last element. member? (and yes, Yeti allows the question mark in function names) tests whether the value v is an element of the list. Both written written using basic recursion, although Yeti is reputed to support better tail call optimization than Scala. Also, at the time, I could not figure out how to do pattern-matching destructuring on lists; instead, I used head, tail, length, and empty?.

Fortunately, Madis pointed out

1. that the standard library does contain member?, known as "contains", and
2. that Yeti does do pattern-matching destructuring on lists, very cleanly.

butLast lst = case lst of
    [_] : [];
    h :: t : h :: butLast t;
    _ : [];
    esac;

The underscore '_' is an anonymous variable; a placeholder that requires a value in the destructuring, but which cannot be referenced later. In the first case the underscore indicates that the lst should have exactly one element; the third that anything is acceptable. See below for more on case and destructuring.

The basic form of a function definition in Yeti is

var = do args... : expressions... done

Since the form of the bare lambda expression in Yeti is

do args... : expressions... done

the basic form is just assigning a function expression to a variable. However, because function definitions are fairly common in Yeti code, there is a shorthand syntax illustrated by butLast:

fcn args... = expressions...

Another simple function is addPoints, which adds two x,y points together, producing another point.

addPoints m n = {x = m.x + n.x, y = m.y + n.y};

The type of addPoints is

addPoints is {.x is number, .y is number}
 -> {.x is number, .y is number}
 -> {x is number, y is number} = <snake$addPoints>

The type indicates that addPoints takes two structures containing (at least) numeric fields x and y and returns another structure with fields x and y. Because Yeti uses structural typing, the structure representing points is actually anonymous; any structure containing suitable x and y fields could be added by addPoints.

Because Yeti supports the ML-style definition of new operators, addPoints could have been written as

// (.+.) m n = {x = m.x + n.x, y = m.y + n.y};

The resulting operator could be used like:

> {x=4,y=3} .+. {x=1,y=1}
{x=5, y=4} is {x is number, y is number}

I chose instead to remain consistent with Halloway's code.

pointToScreenRec converts a game board point to a rectangle in screen coordinates for the display functions.

pointToScreenRec pt =
  { x = (pt.x * pointSize),
    y = (pt.y * pointSize),
    w = pointSize,
    h = pointSize };

Once again, this function just builds and returns a new structure, with x, y, width, and height fields. The fields in the argument are accessed pretty traditionally, by a period followed by the field name.

Yet another pseudo-constant is the random number generator used to place apples on the game board.

r = new Random();

r's value will be an instance of java.util.Random, illustrating some of Yeti's Java integration.

The next two functions create apples and snakes, both of which are also structures.

createApple () =
   { location = {x = r#nextInt(width), y = r#nextInt(height)},
     color = new Color(210,50,90) };

createSnake () =
  { body = [{x = 1, y = 1}],
    dir = {x = 1, y = 0},
    color = new Color(15,160,70) };

Both also illustrate Java integration: the location of the apple is set randomly, by calling the nextInt(n) method. '#' replaces '.' in this use for Yeti. As well, the color of both apples and snakes is defined using java.awt.Color.

createApple and createSnake take the special Yeti 'unit', (), as an argument. If they were defined without taking something as an argument, they would be evaluated immediately as variables. The unit argument allows them to be defined as functions while simultaneously indicating that they do not take any interesting arguments. () indicates both a type and the single, uninteresting value of that type.

The function turn is simply used to replace the direction the snake is traveling. Originally, I wrote it as:

// turn snake newdir =
//   { dir = newdir,
//     body = snake.body,
//     color = snake.color };

Madis also pointed out that Yeti

1. has a with syntax to create a new structure based on an existing one, and
2. has a shortcut for associating variables and fields within a structure.

As a result, turn is:

turn snake dir = snake with {dir};

The value of turn is a copy of the structure snake, with modifications. The form "{dir}" is equivalent to "dir = dir", meaning that the dir field in the new structure is given the value of the dir parameter.

On the other hand, move is slightly more complex.

move snake grow =
  ( newhead = addPoints (head snake.body) snake.dir;
    newbody = if grow then snake.body else (butLast snake.body) fi;
    snake with {body = newhead :: newbody} );

newhead is computed to be the location of the snake's head plus the current direction. newbody is the either current body of the snake (if the snake is growing a new segment) or the current body without the terminal segment---if the snake is growing, it does so by extending at the head; if the snake is simply moving, a new head segment is added at one end while a tail segment is removed.

Since the move function uses two local variables, newhead and newbody, and thus multiple expressions, the expressions in the function's body are enclosed in parentheses.

This part of the program completes with a number of predicates used to determine if the player has won, lost, or if the snake can eat an apple.

win? snake = length (snake.body) >= winLength;

headOverlapsBody? body = member? (head body) (tail body);

lose? snake = headOverlapsBody? snake.body;

eats? snake apple = (head snake.body) == apple.location;

Mutable state

The state of the game is kept in two mutable variables, snake and apple.

var snake = createSnake ();
var apple = createApple ();

The addition of the 'var' to the definition allows the two variables to be modified by assignment.

There are three functions which update the state of the game.

resetGame () =
  ( snake := createSnake ();
    apple := createApple () );

updateDirection newdir = snake := turn snake newdir;

updatePositions () =
    if eats? snake apple
    then apple := createApple ();
         snake := move snake true;
    else snake := move snake false
    fi;

resetGame returns the game to something like it's initial state (remember, apple placement is random). updateDirection is a simple wrapper for turn, replacing the value of snake with a new snake traveling in the new direction. Finally, updatePositions tests whether the snake and apple are co-located; if they are, a new apple is created and the snake moves and grows a new segment; if they are not, the snake simply moves.

resetGame and updatePositions also take the Yeti unit value to prevent the expression from being evaluated immediately. All three functions return unit:

resetGame is () -> () = <snake$resetGame>
updateDirection is {`x is number, `y is number} -> () = <snake$updateDirection>
updatePositions is () -> () = <snake$updatePositions>

Since () indicates both a type and the single value of that type, these typings indicate that these three functions do not return a useful value; any effect they have must be done via side effects, in this case by updating variables.

GUI

In comparison with the mutable state, the GUI is a bit more complex and fancy, due to its integration with Java Swing.

My first step is to define a type name, point, for the structure containing fields x and y.

typedef point = { x is number, y is number };

The reason I did it is the next function, fillPoint.

fillPoint g pt c is ~Graphics -> point -> ~Color -> () =
   ( {x,y,w,h} = pointToScreenRec pt;
     g#setColor(c);
     g#fillRect(x,y,w,h) );

fillPoint is the first function I have used that needs a type specification. It takes an argument, g, which is a Graphics context (marked with a '~' to indicate it is a raw Java class instead of a Yeti type), a point structure, and a Java Color. This function needs the type declaration because Yeti's type inference is unable to do anything with g, since the only thing I do is call the methods setColor and fillRect. fillPoint is also the first function in which I have used a destructuring bind, which picks apart the structure returned by pointToScreenRec into variables x, y, w, and h. These variables are then used to provide the necessary arguments to Graphics#fillRect. That statement also makes use of the "{x}" == "{x=x}" equivalence shortcut.

I used the point type definition to clean up the fillPoint type declaration. Because it acts as a simple alias, the type of fillPoint reported by the REPL is

fillPoint is ~java.awt.Graphics -> {`x is number, `y is number} -> ~java.awt.Color -> () = <snake$fillPoint>

Next, I have a bug. I left it in the code because it is instructive.

paintApple g a = fillPoint g apple.location apple.color;

paintApple draws an apple using fillPoint, but it should take graphics context and the apple as an argument. Instead, it is using the apple variable. I noticed the type of paintApple is

paintApple is ~java.awt.Graphics -> 'a -> () = <snake$paintApple>

The interesting part is the 'a; that is a raw type variable. Type variables appear with parametric polymorphism, as in Java's List<t> or the equivalent Yeti's list<'a>. However, in this case it indicates something seriously wrong with paintApple since a type variable can take any type. Specifially in this code, it means that the parameter a is never used.

paintSnake does not have the bug.

paintSnake g s =
    for s.body do segment: fillPoint g segment s.color done;

Its type is

paintSnake is ~java.awt.Graphics
 -> {.body is list?<{`x is number, `y is number}>, .color is ~java.awt.Color}
 -> () = <snake$paintSnake>

paintSnake also shows a for loop, the use of the function for to iterate through the segments of the snake, calling the anonymous function do...done to draw each segment.

At this point things get a little hairy. To display the game board and interact with the player, I need to create a subclass of JPanel and an implementation of ActionListener and KeyListener. That is, I need GamePanel.

class GamePanel(JFrame frame) extends JPanel, ActionListener, KeyListener
    void paintComponent(Graphics g)
        super#paintComponent(g);
        g#clearRect(0,0,(width+1) * pointSize,(height+1)*pointSize);
        paintSnake g snake;
        paintApple g apple,

    void actionPerformed(ActionEvent e)
        updatePositions ();
        if lose? snake
        then resetGame();
             JOptionPane#showMessageDialog(frame,"You lose!")
        elif win? snake
        then resetGame();
             JOptionPane#showMessageDialog(frame,"You win!")
        fi;
        this#repaint(),

    void keyPressed(KeyEvent e)
        updateDirection dirs.[e#getKeyCode()],

    Dimension getPreferredSize()
        new Dimension((width + 1) * pointSize,
                      (height + 1) * pointSize),

    void keyReleased(KeyEvent e),

    void keyTyped(KeyEvent e)
end;

GamePanel is a Java class defined in Yeti code. The methods it implements are paintComponent (JPanel), actionPerformed (ActionListener), keyPressed (KeyListener), getPreferredSize (JPanel), keyReleased (KeyListener), and keyTyped (KeyListener).

paintComponent clears the game board's window and draws the snake and the apple. It also shows how to make a call to a superclass' method, the call to the superclass' paintComponent.

actionPerformed is called based on a timer; it updates positions and tests whether the win or loss conditions are satisfied and completes by updating the game board.

keyPressed is used to change the direction of the snake, based on arrow-key input. getPreferredSize returns a Dimension containing the on-screen size of the game board. keyReleased and keyTyped are ignored and do nothing.

An instance of GamePanel is created using the gamePanel function, which accepts a JFrame as the constructor argument.

gamePanel frame = new GamePanel(frame);

Like Scala, Yeti uses an implicit constructor scheme, where the arguments to the constructor are stored as members of the instance. Unlike Scala, bizarre do-what-I-mean semantics do not seem to be involved.

Finally, the game function itself is relatively simple imperative code:

game () =
  ( frame = new JFrame("Snake");
    panel = gamePanel frame;
    timer = new Timer(turnMillis,panel);
    panel#setFocusable(true);
    panel#addKeyListener(panel);
    frame#add(panel);
    frame#pack();
    frame#setVisible(true);
    timer#start() );

Endgame

To play the game, fire up the Yeti REPL, load the module, and invoke game:

$ java -jar yeti.jar
Yeti REPL.

> load snake
...elided...
> game ()

Miscellanea

The remaining part of Yeti which I explored, but did not ultimately use in the snake game, is open variant types. To use these, the record returned by createApple could be tagged with 'Apple':

// createApple () = Apple {
//              location = {x = r#nextInt(width),
//                          y = r#nextInt(height)},
//              color = new Color(210,50,90),
//              };

Using that, I could define a single function, paint, to replace paintApple and paintSnake:

// paint g object =
//     case object of
//         Snake s : for s.body do segment: fillPoint g segment s.color done;
//         Apple a : fillPoint g a.location a.color;
//     esac;

The type of paint is:

paint is
    ~java.awt.Graphics
 ->   Apple {.color is ~java.awt.Color, .location is {`x is number, `y is number}}
    | Snake {.body is list?<{`x is number, `y is number}>, .color is ~java.awt.Color}
 -> () = <snake$paint>

The second argument of paint is either an appropriate structure tagged with Apple or an appropriate structure tagged with Snake; the tag determines which branch is expected.

Conclusion

I like Yeti. It seems a pretty nice representative of the ML family on the JVM. The integration with Java seems to be a little clunky, but not irritatingly so.

• Yeti
• Chrisichris's Blog posts on Yeti
• A short introduction to Yeti
• The yeti-lang mailing list
• My snake code

Madis made several excellent suggestions about this posting (and code changes to yeti). Thanks!

Copyright © 2007-2017 Tommy M. McGuire