Design

I recently found a good series of articles on LtU, on the Ghosts of UNIX past. The author reflects on some successes and failures of Unix, trying to find patterns. I enjoyed reading the articles, they teach you a few things, and are generally good food for thought.

The first article describes the "full exploitation" pattern, successfully achieved in UNIX with files. The next articles describe various failures of UNIX design, classifying them in "conflated", "unfixable" and "high-maintenance" designs. While I don't have the culture to do the proposed exercises, I tried to relate this to programming language design -- which suprisingly hasn't been done on LtU.

• Full exploitation is when you manage to re-use a concept a lot. This is good because it avoids inventing new things: it's hard enough to get a few concepts right. In programming languages, a good first-class notion of functions can be fully exploited to model control, event handlers, lazy computation, etc.
• Conflated designs mix up several concepts. This is bad only if the two concepts cannot be separated. Otherwise, it's just syntactic sugar. Object oriented programming comes to mind: Methods are a conflated design, mixing functions and record members. Also, inheritance mixes record extension and dynamic binding -- which makes it hard for people to think about the latter aspect, a very important source of bugs.
• Unfixable designs are unfixable designs. This is a bad definition, but sometimes it is hard to say why something is unfixable. Often, this has to do with the wide adoption of the wrong design. Note that conflated designs may often be fixable, essentially by creating ways to access conflated notions in isolation. I'm not sure what's a good programming language example here. Perhaps dynamic binding, probably stuck forever in emacs lisp. (By the way, a fun fact according to Olivier Danvy: dynamic binding was born from exagerated exploitation of a single stack in the implementation of Lisp -- in those old days, people were psyched about stacks and got a bit carried away.)
• High-maintenance designs have nothing wrong in themselves but interfere with other things in such a way that requires a lot of care and work in those areas. With programming, various difficult things come to mind: state, concurrency, dynamic binding... Those aspects make it very hard to reason locally about a piece of code. In themselves, state and concurrency are cool, but their interaction leads to many problems.

More than programming languages, liquidsoap was in the back of my mind. But there does not seem to be interesting examples of those patterns in liquidsoap. In fact, it is not an exceptionally good design. It's just a first shot at making an end-user streaming application that is not just one object/tool but rather a system/language for building tools. Liquidsoap introduces an abstract notion of source, which is good, but does not fully exploit it. For instance, blank detection operators are black boxes that encapsulate the computation of the average audio volume, but a more flexible and efficient design would be achieved by isolating the computation of the volume stream as a source, then write operators that act depending on the characteristics of the volume source. Liquidsoap does not have unfixable designs because we give ourselves the liberty to change things when needed. It does have high-maintenance designs: the source protocol is complex, and we've had many bugs because it wasn't properly followed.

Beyond those not-so-good design examples, liquidsoap is broken in several ways. But I'm comfortable to admit it because it works good enough for many people and we know how to fix it. The code name for that exciting new line of work is, quite straightforwardly, Liquidsoap 2.0. Until now, we've been writing sources by hand in OCaml. Liquidsoap users write scripts in our own scripting language, and can only compose sources, never write a new one. In other words, Liquidsoap is an interpreter for a dedicated script language that manipulates an abstract/opaque notion of source. But liquidsoap 2.0 will be a compiler that lets you write sources, and not only compose them, and will produce optimized code. It will be as simple as it is today for beginners, but will enable much more for power users. Importantly, it will allow us developers to not write as much bug-prone code. There is a lot to say about what could be in liquidsoap 2.0, but I'll start with a simple down-to-earth story... next post!

Illumination

For some reason, I've found myself implementing bits of a text-mode rogue-like game. In a nutshell, this is a turn-based kind of game where the player moves on a grid which usually depicts a dungeon or a cave. Some cells of that grid/map might contain a wall/rock, in which case the player cannot see or walk through them. All this is rather straightforward to implement, but the computation of what the player sees deserves some attention.

I started thinking of casting rays, but only found clumsy, costly solutions. So I did a little research. Some people (including crawl) actually developed algorithms along these lines for computing what is called a permissive field of view:

A destination square is visible from a source square if there is any unobstructed line from some point in the source square to some point in the destination square.

It's apparently a modern notion of field of view, that has one advantage over older techniques: it ensures symmetry, i.e., if I can see you, you can see me.

The same article on roguebasin points to several algorithms, including the one implemented in crawl. They all seemed unsatisfyingly complicated to me. I eventually came up with a different idea that looks good and ensures symmetry. It might have been considered already and discarded for some of its funny aspects, but those are interested to look at.

The basic idea is to forget about those lines. We are talking about a discrete universe, let's try to make its physics discrete too. Geometrical optics is only a convenient metaphor, that is justified by more elementary principles such as Fermat's:

The path taken between two points of a ray of light is the path that can be traversed in the least time.

This is in fact a definition of a ray of light that we can take literally in our discrete rogue world:

A cell is visible from another if one of the shortest paths between them is unobstructed.

Let's look at a simple example. For now, suppose that the movements are only allowed along the axis (no diagonals):

.# 
@#y
.x.

The player is represented by @, and # are walls/rocks. The cell marked y is not visible: it is at distance 2, there is only one path of length 2 that connects it to the player but it is obstructed. Cell x is also at distance 2, but it is visible since one of the two paths of length 2 that connects it to the player is not obstructed.

A funny thing happens when you consider the traditional rogue movements which include diagonals: cell y becomes visible! Indeed, the light can take a path of length 2 through x.

I would tend to adopt rules where the topology is the same for players and light. Either embrace the diagonal movements but accept the surprising effect on light, or remove them both for the light and the player. I chose the less experimental way for now. But it is also possible to use different topologies for the two entities.

To finish, I will give the last reason why I like this solution: the code is stupid simple. Assuming that the radius of the field of view will always be within a fixed bound, we can compute once and for all the map of shortest paths with their dependencies.

(** The maps will be used to associate
  * the coordinates of the destination of a path
  * to the lists of the coordinates of possible previous step
  * in shortest paths leading to that destination. *)
module M = Map.Make (struct type t = int*int let compare = compare end)

let neighbors (x,y) =
  [ x-1,y ;
    x,y-1 ;
    x+1,y ;
    x,y+1 ]

let shortest_paths max =
  (** Map of distances to the center of the matrix. *)
  let dist = Array.make_matrix (2*max+1) (2*max+1) max_int in
  (** At each step we compute the shortests paths to cells
    * at distance [d=n+1] from those for distance [n]. *)
  let step d paths_n =
    M.fold
      (fun (x,y) _ m ->
         List.fold_left
           (fun m (x',y') ->
              if dist.(max+x').(max+y') < d then
                (* Seen in a previous iteration. *)
                m
              else if dist.(max+x').(max+y') = d then
                (* We already found a path of length n+1,
                 * but we need to keep track of this new one too. *)
                M.add (x',y') ((x,y)::M.find (x',y') m) m
              else begin
                (* First time we see it: first shortest path. *)
                dist.(max+x').(max+y') <- d ;
                M.add (x',y') [x,y] m
              end)
           m
           (neighbors (x,y)))
      paths_n
      M.empty
  in
  let rec aux d frontiers =
    if d=max then frontiers else
      aux (d+1) (step d (List.hd frontiers) :: frontiers)
  in
    List.rev (aux 1 [M.add (0,0) [] M.empty])

Then, it only remains to parse dependencies:

(** Takes a radius (d) and returns a field of view function
  * for that radius. *)
let fov d =
  let frontiers = shortest_paths d in
    (* The field of view function,
     * which takes a function and calls it on each visible cell.
     * The function [f] returns whether a cell is transparent or not. *)
    fun f ->
      let transparent = Array.make_matrix (2*d+1) (2*d+1) false in
        transparent.(d).(d) <- true ;
        List.iter
          (fun frontier ->
             M.iter
               (fun (x',y') deps ->
                  if
                    List.exists (fun (x,y) -> transparent.(d+x).(d+y)) deps
                  then
                    transparent.(d+x').(d+y') <- f x' y')
               frontier)
          (List.tl frontiers)

Hurray to (impure) functional programming! I leave it to you to glue this to whatever testing code you want. I'll finish with "screenshots".

Without diagonal moves, notice that it is possible to see through a wall on a diagonal:

              .
       .      ..
      ..    ##...
     #.. ###...# .
     #..#......##.#
     #.....@......#
     #...##........
     ...#.........
      ###........
        #.......
        ..####.
         .

With diagonal moves, we now have shadows along the diagonals, but we can see around walls placed along the axis:

        ..#..#...
         .......
   .######.....
   ...........
   .##.......
    #.......#
    #.......####   #
    #..........## ..
   .##..##.@....#...
   #...  ##...##..##
   ###    .......###
         ...........
        ............
       .............
      ###...........
        ............
       .##.####.....