Hacker News Reader

Comment by btilly | Hacker News Reader

That would be the implementing your own version of laziness part of the modularity argument.

In a language like Haskell you never have to do that. Ever. Because the language is lazy.

"Implementing your own version of laziness" makes it sound error-prone and difficult. In fact it's this pattern:

  def move(board, position, player):
    """
      board is a 11-character string which is 3 lengths of 3 of the characters
        X, O or _, separated by newlines
      turn is either X or O, depending on who moves
    """
    return board[:position] + player + board[position+1:]

  def getNextStates(board, player):
    spaces = [ i for i,c in enumerate(board) if c == '_' ]
    return [ move(board, i, player) for i in spaces ]

  >>> print board
  X_O
  _OX
  X_O 
  
  >>> for state in getNextStates(board, 'O'):
  ...   print state
  ...   print
  ... 
  XOO
  _OX
  X_O
 
  X_O
  OOX
  X_O
  
  X_O
  _OX
  XOO

I doubt most programmers exposed only to imperative programming would even notice that there was a pattern in what they were implementing, let alone identify it as laziness.

The problem comes in when you want to write a search function for the game tree. Your search function will make assumptions about how the tree is constructed, i.e. assuming that the children can be produced given only the current board and player, which isn't true for all games.

Your search function will wind up actually having two responsibilities, that is 1) creating the tree and 2) traversing/searching the tree. If you want to do anything else, like add pruning functions (maximum depth, for example), then your search function will also wind up having to manage that.

The problem is, a search algorithm such as breadth-first or A* really has no reason to need know any of those things. If you passed the search function a pre-computed tree already pruned (i.e. capped at a max-depth) the resultant search function would do one thing: search. It would have no need to prune or compute the tree, as that was already taken care of.

This lets you re-use that search function for many other use-cases, rather than tailoring it to a specific game or use-case. In a lazy language, you can pass the search function an infinite tree, and the search function doesn't need to know that it is infinite. It can treat it just as though it's already been computed. Similarly, you can do the same thing with pruning the tree before passing it to the search function.

The end result is that rather than having to intertwine all of these unrelated concepts (generating the data structure, pruning the data structure, and searching the data structure), a lazy language makes it extremely natural (and in fact the default) to write programs where these building blocks are separate entities that can be composed with other pieces of code.

Hopefully that helps make sense of why laziness is a requirement for truly modular code. Note that you can always emulate lazy evaluation with closures (or often, simply using generators), but it's never as natural as just having it be built into the language by default.

The difficulty depends on the language and on what you're trying to do.

In Python the correct translation is usually to replace return with yield and work with iterators. In a language without that feature, well, http://perl.plover.com/Stream/stream.html demonstrates what a solution looks like in Perl. A Java solution to the same issue is going to be..verbose.

I avoided generators because implementing ersatz laziness with lazy language features seemed like cheating - you can read my Python lists as C arrays, but it's much harder to map that onto coroutines without significant handwaving.

Replace the []s by ()s so only generators are returned and the expressions evaluated when consuming the generators.

They wouldn't identify it as laziness because there isn't anything lazy about that code.

You have just perfectly shown that it is indeed "error-prone and difficult" congratulations.

Reply on news.ycombinator.com