game of life w/functional JS style

design.html

<a href="game_of_life.html">Game of Life</a>


<h3>Computer Programs are...</h3>

Poetry for Robots?  Maybe...but how about?

<ul>
  <li>Algorithms</li>
  <li>Configuration</li>
  <li>Data Structures</li>
  <li>Execution and Events</li>
  <li>Functions</li>
  <li>Models/Views</li>
  <li>Objects</li>
  <li>Procedures</li>
  <li>Tests</li>
</ul>

<h3>How to Build...</h3>

<ul>
  <li>Scratch an itch</li>
  <li>Reflect on the problem</li>
  <li>Start coding!</li>
  <li>Have a design plan
    <ul>
      <li>Don't miss the forest for the trees</li>
      <li>Eventually you have to plant a tree</li>
      <li>Write the view code first! (or not)</li>
      <li>Expect the code to evolve.</li>
      <li>Code, verify, test, examine, repeat.</li>
    </ul>
  </li>
</ul>

<p><i>"In preparing for battle I have always found that plans 
are useless, but planning is indispensable."</i></p> -- Dwight Eisenhower

<h4>Core ideas of the Game of Life</h4>

<h5>INITIAL CONFIGURATION</h5>
One interacts with the Game of Life by creating an initial configuration and observing how it evolves.
<table>
  <tr>
  <td>
  <img src="http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Game_of_life_infinite1.svg/162px-Game_of_life_infinite1.svg.png">
  </td>
  <td>
  <pre>
        var seed = [
          "X      ",
          "       ",
          "XX     ",
          "       ",
          "  XXX  ",
          "       ",
          "   XXX ",
          "    X  ",
        ];
  </pre>
  </td>
  </tr>
</table>

<h5>THE UNIVERSE</h5>
The universe of the Game of Life is a (...) two-dimensional grid of square cells,
each of which is in one of two possible states, live or dead.

<pre>
    function data_2d() {
      var hash = {};

      function key(point) {
        var x = point[0];
        var y = point[1];
        return x.toString() + ',' + y.toString();
      };

      return {
        alive: function (point) {
          return hash[key(point)];
        },

        set: function (point, on) {
          hash[key(point)] = on;
        }
      }
    }
</pre>

<h5>THE GEOMETRY</h5>
Every cell interacts with its eight neighbors...
<pre>
      var x_deltas = [
        -1,  0,  1,
        -1,      1,
        -1,  0,  1
      ]
      var y_deltas = [
        -1, -1, -1,
         0,      0,
         1,  1,  1
      ]
</pre>

<h5>THE RULE</h5>
At each step in time, the following transitions occur...
<pre>
    function point_lives_next_gen(alive, num_neighbors) {
      var n = num_neighbors;
      if (alive) {
        return (n == 2 || n == 3)
      } else {
        return (n == 3)
      }
    }
</pre>

<h5>EVOLUTION</h5>
<pre>
    var new_world = world_factory();
    old_world.cells().forEach( function (cell) {
      var is_alive = old_world.alive(cell);
      var n        = old_world.num_alive_neighbors(cell)
      var on       = point_lives_next_gen(is_alive, n);
      new_world.set(cell, on);
    });
</pre>

<h3>Program Design is...</h3>

<ul>
  <li>Wikipedia-Driven Development?</li>
  <li>Understanding the essence of the problem</li>
  <li>Working in multiple paradigms</li>
  <li>Divide and conquer</li>
  <li>Math + Language + Engineering + Intuition</li>
  <li>Evolutionary Design (or emergent design)</li>
  <li>Quality</li>
</ul>


<h5>Resources</h5>
  <ul>
    <li><a href="http://www.ibiblio.org/lifepatterns/">Advanced Simulator</a></li>
    <li><a href="http://www.math.com/students/wonders/life/life.html">Wonders of Math</a></li>
    <li><a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Wikipedia: Conway's Game of Life</a></li>
    <li><a href="https://gist.github.com/908317#file_game_of_life.html">Steve's Implementation in Javascript</a></li>
  </ul>

game_of_life.html

<h3>Game of Life</h3>
<canvas id="canvas" width="520" height="420" style="border: 1px blue solid">
</canvas>

<script>
  (function () {
    
    //- ALGORITHM (iteration)
    // 
    // Define the Game of Life as f: World -> World.
    //
    // We make no assumption about the topology here.  The "space"
    // could be 2D, 3D, finite, toroidal, hexagonal, or infinite.
    //
    // An instance of World needs only supply these methods:
    //     cells: return collection of opaque cell references
    //     num_alive_neighbors(cells)
    //     alive(cell)
    //     set(cell, on/off)
    //
    // (A small note: f() only talks directly to World, not its cells.)
    //
    // Our abstract_game_of_life() returns a function with the contract
    // f: W -> W.  For the "Game" part of the simulation, you would repeatedly
    // apply the function and render each new instantiation of the World.
    //
    // You configure the topology of the world with world_factory.
    //
    // You configure the evolutionary algorithm with point_lives_next_gen,
    // which determines the fate of the cell in the next generation.
    //    
    function abstract_game_of_life(
      world_factory,
      point_lives_next_gen
      )
    {
      function f(old_world) {
        var new_world = world_factory();
        old_world.cells().forEach( function (cell) {
          var is_alive = old_world.alive(cell);
          var n        = old_world.num_alive_neighbors(cell)
          var on       = point_lives_next_gen(is_alive, n);
          new_world.set(cell, on);
        });
        return new_world;
      }
      return f;
    };

    //- TEST UTILITY
    // We do some primitive testing inline.
    function assert(c, msg) {
      msg = typeof(msg) != 'undefined' ? msg : "see stack trace";
      if (!c) {
        console.log("assertion failure");
        debugger;
        throw("test fails: " + msg);
      }
    }

    //- TEST W/STUBS
    // Test abstract_game_of_life.  We use a world that has only one cell,
    // and our evolutionary principle is that you die, then you are reborn,
    // toggling every generation.
    (function() {
      var world_factory = function () {
        var cells = [false];
        return {
          "cells":
            function() { return [0] },

          "num_alive_neighbors":
            function(i) { return 0 },

          "alive":
            function(i) { return cells[i] },

          "set":
            function(i, fate) { cells[0] = fate },

          "status":
            function() { return cells[0] }
        }
      }
      function toggle(alive, num_neighbors) {
        return alive ? false : true;
      }
      var f = abstract_game_of_life(world_factory, toggle);
      var w = world_factory();
      assert(!w.status(), "init");
      w = f(w);
      assert(w.status(), "gen 2");
      w = f(w);
      assert(!w.status(), "gen 3");
      w = f(w);
      assert(w.status(), "gen 4");

    })();

    //- FUNCTION w/no side effects
    //
    // This is the classic configuration of the Game of Life.
    // The notation is B3/S23, where B describes the number of
    // neighbors required for Birth, and S describes the number
    // of neighbors required for Survival.
    // http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
    function point_lives_next_gen(alive, num_neighbors) {
      var n = num_neighbors;
      if (alive) {
        return (n == 2 || n == 3)
      } else {
        return (n == 3)
      }
    }

    //- TEST
    // Test point_lives_next_gen.  It's not super complicated,
    // nor likely to change much, so this is just a smoke test.
    (function() {
      assert( point_lives_next_gen(true, 2));
      assert( point_lives_next_gen(true, 3));
      assert( point_lives_next_gen(false, 3));

      assert(!point_lives_next_gen(false, 1));
      assert(!point_lives_next_gen(true, 1));
      assert(!point_lives_next_gen(false, 2));
    })();

    //- DATA STRUCTURE: hash
    //
    // This defines our core data structure for representing
    // a set of 2D points.
    // We use a hash, although arguably a 
    // set or array would be better.
    function data_2d() {
      var hash = {};

      function key(point) {
        var x = point[0];
        var y = point[1];
        return x.toString() + ',' + y.toString();
      };

      return {
        alive: function (point) {
          return hash[key(point)];
        },

        set: function (point, on) {
          hash[key(point)] = on;
        }
      }
    }

    //- TEST
    //
    // Test data_2d.
    (function() {
      d = data_2d();
      assert(!d.alive([5,7]));
      d.set([5,7], true);
      assert(d.alive([5,7]));
      d.set([5,7], false);
      assert(!d.alive([5,7]));
    })();

    //- FUNCTION w/no side effects
    //
    // This defines how we find neighbors for a cell. We use a 
    // 2D toroidal geometry, a la PacMan.
    function get_toroidal_neighbors(point, width, height) {
      var x = point[0];
      var y = point[1];

      var x_deltas = [
        -1,  0,  1,
        -1,      1,
        -1,  0,  1
      ]
      var y_deltas = [
        -1, -1, -1,
         0,      0,
         1,  1,  1
      ]

      return x_deltas.map(function(dx, i) {
        var dy = y_deltas[i];
        var xx = (x + dx + width) % width;
        var yy = (y + dy + height) % height;
        return [xx, yy];
      });
    }

    //- MODEL OBJECT
    //
    // The broader World object supports a finite 2D topology and
    // provides the interface methods that abstract_game_of_life
    // wants on it.
    function world(width, height) {
      var data = data_2d();

      function cells() {
        points = []
        for (var x = 0; x < width; ++x) {
          for (var y = 0; y < height; ++y) {
            points.push([x,y]);
          }
        }
        return points;
      }

      function num_alive_neighbors(loc) {
        var num = 0;

        var neighbors = get_toroidal_neighbors(loc, width, height);
        for (var i in neighbors) {
          if (data.alive(neighbors[i])) {
            num += 1;
          }
        };
        return num;
      }

      return {
        "alive": data.alive,
        "set": data.set,
        "cells": cells,
        "num_alive_neighbors": num_alive_neighbors
      }
    }

    //- TEST
    //
    // Test the world class
    (function () {
      w = world(10, 10);
      assert(w.cells().length == 100);
      w.set([5,5], true);
      assert(w.alive([5,5]));
      assert(w.num_alive_neighbors([5,5]) == 0);
      w.set([5,6], true);
      assert(w.num_alive_neighbors([5,5]) == 1);
      w.set([6,6], true);
      assert(w.num_alive_neighbors([5,5]) == 2);
      // try to fool us with a far-off cell
      w.set([9,9], true);
      assert(w.num_alive_neighbors([5,5]) == 2);
      // kill thy neighbor
      w.set([6,6], false);
      assert(w.num_alive_neighbors([5,5]) == 1);
    })();


    //- FUNCTION (concrete)
    //
    // This returns the function that is used to transform our
    // board for this demo.  It mostly configures a concrete geometry
    // for the Game of Life.
    function board_transform_function(width, height) {
      function create_world() {
        return world(width, height);
      }

      return abstract_game_of_life(
        create_world,
        point_lives_next_gen
      );
    }

    //- PROCEDURE (event-based)
    //
    // This is crude, but can be extended without regards
    // to the underlying algorithm.  (You could add pause
    // buttons, speed sliders, etc.).
    function animate(
      initial_data,
      step_function,
      render_func,
      delay,
      max_ticks)
    {
      var tick = 0;
      var current_data = initial_data;

      function pulse() {
        tick += 1
        render_func(current_data);
        if (tick < max_ticks) {
          current_data = step_function(current_data);
          render_func(current_data);
          setTimeout(pulse, delay);
        }
      }

      pulse();
    }


    //- VIEW (abstract)
    //
    // Warning: this is not well-test, but the interface should be
    // apparent. Scaling was trial and error.
    function view_2d (width, height) {
      var canvas = document.getElementById("canvas");
      var ctx = canvas.getContext("2d");

      function draw(x, y, on) {
        ctx.fillStyle = on ? 'black' : 'white';
        var w = 10;
        var h = 10;
        x = x * w;
        y = y * h;
        ctx.fillRect(x, y, w, h);
      }

      return {
        'draw': draw
      }
    }

    //- VIEW (concrete)
    function display(width, height) {
      var view = view_2d(width, height);

      return {
        'render_board': function(board) {
          for (var y = 0; y < height; ++y) {
            for (var x = 0; x < width; ++x) {
              on = board.alive([x, y]);
              view.draw(x,y, on);
            }
          }
        }
      }
    }

    //- DATA INITIALIZATION
    function seed_world(world) {
      var seed = [
        "X      ",
        "       ",
        "XX     ",
        "       ",
        "  XXX  ",
        "       ",
        "   XXX ",
        "    X  ",
      ];
      var points = []
      for (var x = 0; x < seed.length; ++x) {
        s = seed[x]
        for (var y = 0; y < s.length; ++y) {
          if (s.charAt(y) != ' ') {
            points.push([x,y]);
          }
        }
      }

      for (var i = 0; i < points.length; ++i) {
        var point = points[i];
        var x = point[0];
        var y = point[1];
        world.set([x+5,y+5], true);
      }
    }

    //- CONFIGURATION
    var WIDTH = 50;
    var HEIGHT = 40;
    var MAX_TICKS = 800;
    var DELAY = 5; // milliseconds

    //- MAIN EXECUTION LOOP
    function run() {
      initial_world = world(WIDTH, HEIGHT);
      seed_world(initial_world);
      animate(
        initial_world,
        board_transform_function(WIDTH, HEIGHT),
        display(WIDTH, HEIGHT).render_board,
        DELAY,
        MAX_TICKS
      );
    }
    run();
  })();
</script>

reader.rb

require 'pp'

lines = []
def indent(line)
  # return 99 if line.strip == ''
  line.rstrip =~ /(\s*)/
  $1.size
end

SECTIONS = []

def new_section
  section = Array.new
  SECTIONS << section
  section
end

File.open(ARGV[0]) do |f|
  state = 'prelude'
  section = new_section
  f.each_line do |line|
    if line.strip != ''
      nesting = indent(line)
      case state
      when 'prelude'
        if nesting == 4
          state = 'start'
          section = new_section
        end
      when 'start'
        if nesting > 4
          state = 'middle'
        end
      when 'middle'
        if line[4..4] == '}'
          section << line
          state = 'start'
          section = new_section
          next
        end
      end
    end
    section << line
  end
end

i = 0
while i < SECTIONS.size do
  system('clear')
  section = SECTIONS[i]
  puts "Page #{i+1}"
  puts "------------"
  puts section.join('')
  puts
  user_input = STDIN.gets
  i += 1
end

tree.txt

  abstract_game_of_life
    -> world_factory
    -> old_world.cells
    -> old_world.alive
    -> old_world.num_alive_neighbors
    -> point_lives_next_gen
  
  point_lives_next_gen

  data_2d
    key
      -> x.toString
      -> y.toString
    alive
    set

  world
    -> data_2d
    num_alive_neighbors
      -> neigbors
      -> data.alive
    alive
    set
    cells

  board_transform_function
    create_world
      -> world
    -> abstract_game_of_life

  animate
    pulse
      -> render_func
      -> step_function
      -> setTimeout
    -> pulse

  view_2d
    -> document.getElementById
    -> canvas.getContext
    draw
    on
      -> draw
    off
      -> draw

  display
    -> view_2d
    render_board
      -> board.alive
      -> view.on
      -> view.off

  seed_world
    -> world.set

  run
    -> world
    -> seed_world
    -> animate
    -> board_transform_function
    -> display(...).render_board