Ahora que me empiezo a sentir cómodo programando con Scala y cats-effect, quiero volver a usar tests para guiarme. Una de los primeros resultados que aparecen en Google cuando se busca tdd and functional programming son unas notas de Kent Beck tituladas: “Functional TDD: A Clash of Cultures”. En estas notas Kent Beck afirma que el TDD no funciona de la misma forma con programación funcional que en lenguajes orientados a objetos, y da su propia interpretación sobre cuáles son los principios esenciales de TDD que podrían ser útiles en programación funcional.

Aunque hay otras ideas muy interesantes en las notas de Kent Beck como complementar la seguridad de los tipos con tests, en este post yo me he querido centrar en el principio de outside-in que permite diseñar la solución desde fuera del sistema, teniendo en cuenta solamente el comportamiento que es visible desde el exterior del programa, e intentando evitar que se filtren hacia fuera los detalles internos de la solución.

Leyendo el prólogo del libro Isomorphism – Mathematics of Programming me di cuenta de que yo nunca había programado el juego del tres en raya. Este ejercicio de programación es un clásico, según el autor del libro, así que voy a intentar programar el juego del tres en raya en un estilo funcional mientras aplico TDD.

El código completo está en este repositorio de GitHub.

La Primera Regla del Juego

Voy a ir introduciendo sucesivamente las reglas del juego, en las que me voy a apoyar para darle forma a mi programa. Además, en cada paso voy a intentar razonar solamente con las reglas que conozco en ese momento, haciendo como que desconozco el resto de reglas. Este es mi test que prueba la primera regla:

simpleTest("the game starts with the first player making an X mark in the board") {
  val gen = for {
    player <- crossesGen
    position <- positionGen
  } yield (NonEmptyList.one(Mark(player, position)), none[GameOutcome])

  forall(gen) {
    case (marks, expectedOutcome) =>
      for {
        marksRef <- Ref.of[IO, List[Mark]](List.empty)
        board = FakeInMemoryBoard(marksRef)
        game = Game.start[IO](board)
        outcome <- game.next(marks.head) *> IO { game.solve }
        finalMarks <- marksRef.get
      } yield expect.all(finalMarks == marks.toList, outcome == expectedOutcome)
  }
}

Como en el post de property-based testing, voy a volver a usar generadores de ScalaCheck para crear dinámicamente datos de prueba, y también volveré a usar Weaver Test por la facilidad que me ofrece para escribir tests en los que pruebo efectos de tipo cats.effect.IO.

Antes de definir los casos de prueba, voy a elegir cuál va a ser el cambio de estado que va a probar mi test. Yo decidí comprobar dos cosas: que el tablero contenga la primera jugada de las Crosses, y que el juego no tenga ningún resultado (no hay ganador, ni empate).

Para generar el estado inicial voy a necesitar dos generadores: crossesGen que siempre va a generar al jugador Crosses, y positionGen que va a generar una posición aleatoria en el tablero de juego (TopLeft, RightMid, BottomCenter, etc.). Yo he agrupado estos dos valores en la case class Mark.

Además del jugador y de la posición jugada, mi caso de prueba también va a especificar cuál va a ser el resultado esperado. Como se trata de la primera jugada, aún no espero tener ningún resultado. Yo he decidido representar este escenario con el tipo Option[GameOutcome] y darle valor None.

Y con estas decisiones que acabo de tomar ya empieza a emerger el diseño de la API pública de mi solución. Por una parte, como quiero acceder al estado del tablero desde el test, voy a necesitar inyectar un colaborador que me permita hacerlo. He decidido que utilizaré el doble de prueba FakeInMemoryBoard para representar el tablero en memoria.

Por otra parte, como quiero comprobar el resultado del juego voy a necesitar una operación para consultar si hay un ganador o un empate. Podría hacer que la operación next(mark: Mark): F[Unit] (que sirve para realizar una jugada) también devuelva el estado del juego, pero prefiero no mezclar modificadores con consultas. Éste es un diseño que suelo utilizar cuando hago programación orientada a objetos, y aunque aún no tengo claro si me va a dar alguna ventaja al trabajar con programación funcional, prefiero mantenerlo hasta que tenga claridad.

La función solve(): Option[GameOutcome] consulta el resultado del juego. A diferencia de next, la función solve no tiene efecto.

El código mínimo que necesito para hacer pasar el primer test es el siguiente:

trait Board[F[_]] {
  def add(mark: Mark): F[Unit]
}

trait Game[F[_]] {
  def next(mark: Mark): F[Unit]
  def solve: Option[GameOutcome]
}

object Game {
  def start[F[_]: Sync](board: Board[F]): Game[F] = new Game[F] {
    override def next(mark: Mark): F[Unit] = board.add(mark)

    override def solve: Option[GameOutcome] = none[GameOutcome]
  }
}

Comprobando los Errores

El segundo test que quiero hacer comprueba el error InvalidMove que se produce al intentar empezar una partida con un 0:

simpleTest("the game cannot start with a 0") {
  val gen = for {
    player <- noughtsGen
    position <- positionGen
  } yield NonEmptyList.one(Mark(player, position))

  forall(gen) { marks =>
      for {
        marksRef <- Ref.of[IO, List[Mark]](List.empty)
        board = FakeInMemoryBoard(marksRef)
        game = Game.start[IO](board)
        errors <- game.next(marks.head).map(_ => List.empty[String]).recoverWith {
          case e: InvalidMove => IO(e.errors.toList)
          case e: Throwable => IO(List(e.getMessage))
        }
      } yield {
        expect(errors == List(s"The game cannot start with ${marks.head.player}"))
      }
  }
}

Para hacer pasar este test necesito validar que el jugador que hace la primera jugada no es Noughts. Hay que hacer otras comprobaciones en el juego, por lo que prefiero no detenerme en esta en particular. Volveré a retomar la validación más adelante en este post.

Únicamente decir que de manera semejante a como hice en el test anterior, he usado un generador que va a generar siempre al mismo jugador. En este caso se trata de noughtsGen que va a generar al jugador Noughts.

Compartiendo Código entre los Tests

Con los dos tests que he hecho hasta ahora tengo un ejemplo de cómo probar un resultado, y otro de cómo probar un error. Tengo preferencia por esperar a escribir algún test más que me ayude a identificar el código que se repite en mis test antes de empezar a generalizar, pero como hoy estoy practicando puedo aventurarme a extraer las partes comunes que utilizan mis test:

final case class GameState(marks: List[Mark])

object GameState {
  def newGame: GameState = GameState(marks = List.empty)
}

def withGameContext[A](initialState: GameState)(
  runTest: Game[IO] => IO[A]
): IO[(GameState, A)] = for {
    marksRef <- Ref.of[IO, List[Mark]](initialState.marks)
    board = FakeInMemoryBoard(marksRef)
    game = Game.start[IO](board)
    testResult <- runTest(game)
    finalMarks <- marksRef.get
  } yield (initialState.copy(marks = finalMarks), testResult)

Por comodidad, también he creado la función extractErrors[E <: Throwable]: IO[List[String]] que extrae el error de una IO.

Así queda el último test después de refactorizar el código y aprovechar las partes comunes que acabo de extraer:

simpleTest("the game cannot start with a 0") {
  // generators omitted for brevity

  forall(gen) { marks =>
      withGameContext(newGame) { game =>
        game.next(marks.head).extractErrors[InvalidMove]
      } map {
        case (_, errors) =>
          expect(errors == List(s"The game cannot start with $player"))
      }
  }
}

Validando que se Cumplen las Reglas

Además de que jugador que juega con la X empieza la partida, hay otras 2 reglas que se deben cumplir en cualquier partida de tres en raya:

  • players alternate taking turns to play / players must wait their turn to play
  • there can only be one mark for each position on the board

Por suerte, la librería cats ofrece una forma ergonómica de realizar varias comprobaciones y acumular los errores. Apoyándome en el data type Validated de esta librería, he escrito el siguiente código para realizar todas las validaciones necesarias en el juego:

trait InMemoryBoard extends Board[IO] {
  type ValidationResult[A] = ValidatedNec[String, A]

  private[this] def validatePlayer(
    mark: Mark,
    currentMarks: List[Mark]
  ): ValidationResult[Player] = {
    val player = mark.player
    currentMarks.headOption match {
      case Some(lastMark) =>
        if (!player.eq(lastMark.player)) player.validNec
        else s"Player $player plays twice in a row".invalidNec
      case None =>
        if (player.eq(Crosses)) player.validNec
        else s"The game cannot start with $player".invalidNec
    }
  }

  private[this] def validatePosition(
    mark: Mark,
    currentMarks: List[Mark]
  ): ValidationResult[Position] = {
    val position = mark.position
    currentMarks.find(_.position.equals(position)) match {
      case None => position.validNec
      case Some(_) => 
        s"A mark already exist in the position: $position".invalidNec
    }
  }

  private[this] def validateMove(
    mark: Mark, currentMarks: List[Mark]
  ): ValidationResult[Mark] = (
    validatePlayer(mark, currentMarks), validatePosition(mark, currentMarks)
  ).mapN(Mark)
}

Decir que para no alejarme del TDD, como en los casos anteriores fui introduciendo cada regla por separado hasta que conseguí tener todos los tests en verde, y entonces fue que pude hacer un refactor del código hasta dejarlo como lo muestro aquí.

Buscando al Ganador

La última cosa que me queda por probar es el resultado del juego. Para esto voy a tener que generar partidas completas, en las que uno de los dos jugadores va a ganar (el caso del empate lo voy a probar en un test diferente que no he incluido en este post, pero que sí está en el repositorio).

Esta es la parte que más me ha costado programar porque quería que siguiera siendo property-based testing, así que he terminado creando un pequeño caos de estructuras de datos en las que apoyarme. Aún así, creo que la intención del test ha quedado bastante bien reflejada en el código:

simpleTest(
  """to win the game, a player must place three of their marks in a horizontal, 
    |vertical, or diagonal row""".stripMargin
) {
  val gen = for {
    players <- nDistinct(2, playerGen)
    (winner, loser) = (players.head, players.last)
    winningStrategies = diagonals combine rows combine columns
    winnerPositions <- Gen.oneOf(winningStrategies.map(_.toList).toList)
    loserPositions <- nDistinct(2, Gen.oneOf(
      allPositions.filterNot(winnerPositions.contains_))
    )
    untiePosition <- Gen.oneOf(
      allPositions
        .filterNot((winnerPositions ++ loserPositions).contains_)
        .find(x =>
          winningStrategies.find((x :: loserPositions).toSet.subsetOf)
            .fold(true)(_ => false)
        )
        .toList
    )
    (winnerMarks, loserMarks) = (
      asMarks(List.fill(3)(winner), winnerPositions),
      asMarks(List.fill(3)(loser), untiePosition :: loserPositions)
    )
    allMarks = winner match {
      case Crosses => winnerMarks.intersperse(loserMarks)
      case Noughts => loserMarks.intersperse(winnerMarks)
    }
  } yield (NonEmptyList.fromListUnsafe(allMarks), Winner(winner).some)

  forall(gen) {
    case (marks, expectedOutcome) =>
      withGameContext(newGame) { game =>
        marks.foldMap(game.next) *> game.solve
      } map {
        case (finalState, outcome) =>
          expect.all(
            finalState.marks == marks.toList.reverse, outcome == expectedOutcome
          )
      }
  }
}

En la explicación de los tests anteriores empecé contando cuál es el cambio de estado que probaban mis tests, y de ahí fui bajando a los detalles de cómo estaba montado el caso de prueba. Esta vez prefiero seguir el orden del código porque creo que así conseguiré que me quede una explicación más clara.

Lo primero que hago en el test es elegir a los jugadores de forma aleatoria, para así asegurarme que se prueban algunos casos en los que ganan las Crosses, y también algunos en los que ganan las Noughts. Lo siguiente es elegir la estrategia ganadora de entre todas las posibles: diagonales, filas y columnas.

He creado el siguiente ADT (Algebraic Data Type) para representar las posiciones del tablero:

object board {
  sealed trait Position extends Product with Serializable

  case object TopLeft extends Position
  case object TopCenter extends Position
  case object TopRight extends Position
  case object LeftMid extends Position
  case object Center extends Position
  case object RightMid extends Position
  case object BottomLeft extends Position
  case object BottomCenter extends Position
  case object BottomRight extends Position
}

Esta forma de representar las posiciones tiene la ventaja de que los estados ilegales no pueden ser representados. Además, agrupando posiciones con un Set puedo representar las diagonales, filas y columnas del tablero de juego. Por ejemplo, el siguiente código representa las diagonales:

val diagonals: NonEmptyList[Set[Position]] =
  NonEmptyList.of(
    Set(TopLeft, Center, BottomRight),
    Set(TopRight, Center, BottomLeft)
  )

Volviendo al test, después de elegir las posiciones en las que va a jugar el ganador, voy a elegir las posiciones del perdedor. Para ello, elijo 2 posiciones cualquiera de entre las restantes posiciones. Para asegurarme de que sólo hay un jugador que puede ganar la partida, voy a elegir la última posición del perdedor comprobando que junto a las 2 posiciones que ya había elegido en el paso anterior, no esté en la misma fila, columna o diagonal.

Para terminar de organizar la partida, lo primero va a ser generar todas las tuplas (Player, Position) a partir de los datos generados anteriormente, y con ayuda de la función:

private[this] def asMarks(
  players: List[Player], positions: List[Position]
): List[Mark] = (players zip positions).map {
  case (player, position) => Mark(player, position)
}

La función intersperse sirve para intercalar las tuplas generadas en el paso anterior. Con esto voy a asegurarme que los jugadores se alternan para jugar.

El resto del código reutiliza la misma estructura que ya había usado en los tests anteriores.

En este caso, compruebo en el test que la función solve() identifica al ganador en todos los escenarios de prueba generados por ScalaCheck.

Anteriormente había supuesto que la función solve() no tenía efecto. Desde fuera de mi programa no parece haber nada que indique que esta función realiza un efecto. Sin embargo, para encontrar quién ha ganado necesito acceder a las posiciones del tablero. Esta operación forma parte del álgebra Board[F], y puede tener efectos antes de devolver un valor. Por esta razón, he cambiado la función solve() para que devuelva el tipo: F[Option[GameOutcome]].

Mi código de producción usa una representación en memoria del tablero de juego, creada mediante una referencia mutable de tipo cats.effect.concurrent.Ref:

trait InMemoryBoard extends Board[IO] {
  val findPlayerWithThreeMarksInARow: Ref[IO, List[Mark]] => IO[Option[Player]] =
    (ref: Ref[IO, List[Mark]]) =>
      for {
        currentMarks <- ref.get
        positionsGroupedByPlayer = currentMarks.groupBy(_.player).map {
          case (player, marks) => player -> marks.map(_.position).toSet
        }
        maybePlayer = positionsGroupedByPlayer
          .find {
            case (_, positions) =>
              (diagonals combine rows combine columns)
                .find(_.subsetOf(positions))
                .fold(false)(_ => true)
          }
          .map { case (player, _) => player }
      } yield maybePlayer
}

Finalmente, una vez añadidos todos los cambios, el código del intérprete del álgebra Game[F] queda como sigue:

object Game {
  def start[F[_]: Sync](board: Board[F]): Game[F] = new Game[F] {
    override def next(mark: Mark): F[Unit] = board.add(mark)

    override def solve: F[Option[Outcome]] = {
      val F = Monad[F]
      F.ifM(board.marksLeft.map(_ == 0))(
        ifTrue = F.pure(Draw.some),
        ifFalse = board.playerWithThreeMarksInARow
          .map {
            case Some(player) => Winner(player).some
            case None => none[GameOutcome]
          }
      )
    }
  }
}

Reflexiones Finales

Esta cita de la Wiki de Test Double me ha sacado una buena risa, porque me ha recordado la forma en que llegué yo a la programación funcional:

London-school TDD is commonly referred to as a gateway drug to functional programming, because it encourages separating code with side effects and maximizing pure functions.

Me ha costando bastante cambiar la forma de probar los errores porque tenía muy asumido que para ello era necesario comprobar la excepción en el test, y me causó confusión cuando no encontré una forma de hacerlo con Weaver Test. A partir de ahí me di cuenta de que sólo necesito comprobar el resultado de la ejecución del código que estoy probando, y que en algunos casos también necesito comprobar algún efecto secundario como puede ser que se hayan guardado las jugadas en el tablero de juego.

Weaver Test