Desenvolvendo o jogo 2048 usando programação funcional (part 1)
Após começar a trabalhar com Redux (+React), fiquei intrigado como o Redux funcionava. Era um paradigma completamente novo que tive interesse de conhecer a fundo.
Um dos conceitos básicos que me deixou confuso no início foi o de variáveis imutáveis (variáveis que não variam?). Inicialmente não fez o menor sentido para mim, além de não conseguia ver vantagem alguma em usar esse conceito. Como seria possível escrever um software sem atribuir um novo valor para uma variável? Estudando descobri o conceito dos estados, pure functions, HOFs (High Order Functions) e composições, além de descobrir que o paradigma é mais antigo do que a programação orientada a objetos e a programação estruturada.
Li diversos artigos e alguns livros sobre o assunto, resolvi sair da parte teórica e decidi criar algum projeto divertido que me forçasse utilizar os paradigmas aprendidos. Criei um jogo simples rodando no terminal e decidi expor as dificuldades e a maneira de como pensar de forma funcional.
Recomendo alguns livros que li nas referências desse artigo.
Pra quem não conhece o jogo, segue o link: http://2048game.com/
Nesses artigos, usarei Node Js para desenvolver o jogo, mas farei comentários sobre outras linguagens como Elixir e Rust.
O jogo e as regras (Se você já conhece, pode pular essa parte)
Sobre o jogo e as regras:
Primeiramente, existe uma matriz 4x4 com números inteiros.
O jogo começa com dois blocos, escolhidos aleatoriamente, preenchidos com o número 2.
A partir disso, você pode fazer movimentos na vertical e na horizontal.
Cada vez que você faz o movimento, todos os blocos se movimentam até o máximo que conseguem (ex: movimentei os blocos para cima, todos os blocos com números serão movimentados até o topo).
Se existir um número no meio do caminho e ele for diferente, ele fica no bloco anterior, caso contrário, eles se somam formando um único bloco.
Após cada movimento, é adicionado um número de valor 2 em algum bloco aleatório que esteja vazio.
O jogo termina em dois momentos:
- Quando se consegue formar um único bloco com o valor 2048 e você vence o jogo.
- Quando não existem mais blocos vazios para adicionar números e você perde o jogo.
Algumas regras básicas de programação funcional
A programação funcional possui alguns conceitos que serão abordados durante esse tutorial. O primeiro conceito é de variáveis imutáveis, ou seja, variáveis (que não variam) que não podem receber um novo valor, portanto, chamá-las de variáveis é um termo errado, o termo correto é valor. Exemplo:
# Pseudo code
var value := 2;
value := 3; // Error!Obs: Em Elixir o pseudo-código acima funcionaria, porém o que você está fazendo é apenas criando uma nova variável e perdendo a referência da antiga, fazendo ficar lixo em memória.
Obs2: Em linguagens como Rust é possível definir a variável como mutável. Existem diversas discussões sobre isso ser uma boa prática ou não entre a comunidade.
Portanto, vamos comparar um algoritmo simples estruturado com o mesmo algoritmo em programação funcional. Vamos fazer um código que pesquisa em uma lista de objetos, pessoas que tem a idade igual ou superior a 21 anos.
Estruturado:
// Count all persons with age greater than 21
const getAllPeople() => {/* Here get a list of people... */}// Non funcional
const people = getAllPeople(); // Function to return people
let counter = 0;
for (let i = 0, qt = people.length; i < qt; i++) {
if (people[i].age >= 21) {
counter++;
}
}
console.log(counter);
Funcional:
// Functional way
const people = getAllPeople();
const counter = people
.filter((person) => person.age >= 21) // return obj when true
.count(); // Count listconsole.log(counter);
Temos o mesmo resultado sem redefinir nenhuma variável.
Obs3: Não se utiliza o nome variável, visto que não variam. As “variáveis” são chamadas de valores. Mas no tutorial usarei o termo “variável” para não confundir a cabeça de ninguém.
Getting started
Para começar nosso jogo, iremos criar uma matriz 4x4.
ATENÇÃO: É muito fácil confundir as linhas com colunas ao visualizar o array montado (no código). Note que o array tem o formato [coluna][linha], portanto, a visualização no código não é válida (a não ser que você vira a cabeça 90 graus para a esquerda).
Obs: Vamos chamar o conjunto [coluna][linha] de bloco no artigo.
Primeiramente, para facilitar a visualização do board, como citado no exemplo acima, iremos criar uma função que faz o desenho do board:
Não iremos explicar o funcionamento dessa função, pois ela existe apenas para nos auxiliar a visualização do board. Ela apenas irá desenhar o board.
No início do jogo são adicionados dois números de valor 2 em locais aleatórios no board.
Pensando de forma funcional
Uma ideia inicial que muitas pessoas teriam seria algo como: "Fazer uma função que descubra quais blocos estão com o valor 0, selecionar um deles aleatoriamente e adicionar o valor 2".
Qual a implicação nesse pensamento acima? Um deles é que essa função faz muita coisa. As responsabilidades que ela teria seriam:
- Descobrir quais os blocos que estão com valor 0
- Selecionar um valor aleatório
- Trocar o valor por 2
Uma das boas práticas de programação é o princípio de responsabilidade única (o S do conceito de SOLID). Além disso, o ideal é trabalhar com as Pure Functions.
Pure Functions
Mas o que são Pure Functions *[5]? Segue uma breve definição no Wikipedia:
Pure function. In computer programming, a pure function is a function that has the following properties: Its return value depends only on its parameters and not on any internal or external state (such as local static variables, non-local variables or inputs from I/O devices).
Ou seja, se eu chamar a mesma função infinitas vezes com os mesmos parâmetros, deve retornar sempre o mesmo valor, portanto, não pode depender de nada externo (como uma consulta no banco de dados, ou api, por exemplo).
Vamos então dividir essas funções em três partes.
A primeira função irá apenas descobrir quais os blocos estão com o valor 0 definido.
First function — Descobrindo os zeros
Primeiramente iremos criar essa função de um modo estruturado para mostrar como exemplo.
A função getEmptyBlocks itera sobre a matriz e verifica todos os números do board do jogo. Para cada número 0 encontrado, adiciona em um outro array uma "tupla" contendo o valor do índice da coluna e o índice da linha (ex: [<column>, <line>]). O retorno será um array de tuplas (Na verdade um array de arrays, pois Node não possui tuplas).
Note que precisamos criar uma variável mutável chamada "positions" na linha 3 que vai sendo adicionado na linha 7.
Agora vamos apresentar uma solução possível para o método acima, sem ter uma variável mutável usando um método chamado reduce *[9].
O método reduce itera sobre um array como um forEach, porém os parâmetros que são recebidos na função são diferentes. O primeiro parâmetro é uma função e o segundo parâmetro é o valor default.
Nessa função (primeiro parâmetro) que é criada, são recebidos três parâmetros, sendo eles:
1. recebe o valor default na primeira iteração e nas próximas iterações, recebe o retorno da função que foi chamada.
2. o valor corrente da iteração
3. e o terceiro parâmetro é o índice.
Vamos explicar linha a linha.
- Line 2: chamamos o método reduce que irá iterar sobre as colunas do board. Note, na linha 9, que ele está definindo o valor default como um array vazio, portanto, na primeira iteração o primeiro parâmetro será esse array. Já o segundo parâmetro corresponde a linha do board e o terceiro, o índice da coluna do board.
- Line 3: usamos novamente o reduce, mas dessa vez, estamos iterando sobre a linha da coluna do board (
[column][<line>]). O primeiro parâmetro será o valor default (definido na linha 6) ou o retorno da última iteração. O segundo será o valor do bloco da linha e o terceiro é o índice da linha. - Line 4: verificamos se o valor do bloco é 0, se não, retornamos o mesmo valor do último retorno.
- Line 5: juntamos o retorno da última iteração e adicionamos um novo array, contendo como primeiro valor o índice da coluna e como segundo valor o índice da linha (
[[column][line]]). - Line 8: juntamos o que conseguimos de índices das colunas e linhas em um array e retornamos para a próxima iteração (que será sobre a coluna seguinte, se existir).
Agora temos um método que resgata todos os índices de valor 0 em nosso board. Note que não trocamos o valor de nenhuma variável. Os valores são sempre novos estados criados.
Second Function — Resgatando um índice aleatório
Vamos criar uma simples função que, ao passar a lista de índices, selecione um aleatoriamente e retorne.
Essa função seleciona um índice e retorna.
Agora, temos uma função que retorna todos os zeros disponíveis no board e temos uma função que retorna apenas um deles, selecionado de forma aleatória utilizando o Math.random() do Javascript.
Podemos agora criar uma função que, ao passar um índice e um board, retorne um novo board com o número adicionado.
Para essa nova função, será necessário criar um novo board, onde, somente o bloco com o índice da coluna e da linha forem iguais ao do ponto passado como parâmetro será "alterado".
Third Function — Adicionando um número no Board
Na primeira vez que pensei nessa função tive a ideia de uma solução muito simples em poucas linhas.
Primeira solução:
Na primeira linha da função usamos o iterador map* [6]. O map itera sobre cada item do array e chama uma função, o retorno dessa função será o novo valor correspondente ao item corrente.
// Example of map usage:
const numbers = [1, 2, 3];
const doubleNumbers = numbers.map((number) => number * 2;
console.log(doubleNumbers);
// [2, 4, 6]Porém, essa solução é pouco performática, pois a função precisa iterar sobre cada item do board (4*4 items) e para cada um comparar se o índice é o correto para fazer a substituição. Pouco código, porém, baixa performance.
A segunda maneira que pensei para ser mais performática, foi utilizando a função slice.
Recebemos como segundo parâmetro o número da coluna e da linha, “cortaremos” o array de colunas, separando somente a linha que teremos que substituir e faremos o mesmo com a linha.
Na linha, iremos cortar até um valor antes do índice que precisa ser substituído. Iremos adicionar o número correto no array e depois iremos juntar com o que resta do mesmo.
Essa função é um pouco mais complexa, mas não é tão difícil de entender.
Explanation:
- Line 4 (considerando os comentários): pegamos a linha que iremos substituir o bloco.
- Line 6: estamos criando uma nova linha, onde, fazemos o destructing *[7] dos itens antes do índice.
- Line 7: (ainda na definição da variável) estamos adicionando no array o número que deve ser atribuído (2 por padrão).
- Line 8: inserimos via destructing *[7] o resto do array, gerando uma nova linha. Essa nova linha deve substituir a linha da coluna.
- Line 12: é feito basicamente o mesmo processo que o anterior, onde é feito o slice das colunas antes do índice, é inserido a nova linha e depois é adicionado o resto das colunas.
- O retorno será um novo board com o valor atualizado.
Sobre a diferença de performance entre as duas funções, fiz um teste simples utilizando a lib Benchmark *[8] do node e os resultados que obtive foram (rodando por 20 segundos):
Test Using slice
Runned 35.860 times
=======================
Test Using map
Runned 16.783 times
=======================Fastest is Using slice
Coloquei o resultado do benchmark nessa url.
Sources and references
- KUMAR, K Anand. The Magical World of Functional Programming: Part I: Thinking Functional. Edition: 1
Publication Date: November 20, 2014. - BURCHARD, Evan. Refactoring JavaScript: Turning Bad Code Into Good Code. Edition: 1
Publication Date: April 3, 2017 - FOGUS, Michael. Functional JavaScript - Introducing Functional Programming with Underscore.js
Publication Date: June 2013 - WILSON, Jim. Node.js 8 the Right Way
Publication Date: February 2, 2018 - Pure Function: https://en.wikipedia.org/wiki/Pure_function
Access in: August 18, 2018 - Function Map: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map
Access in: August 18, 2018 - Destructing: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment
Access in: August 18, 2018 - Benchmark JS: https://www.npmjs.com/package/benchmark
Access in: August 18, 2018 - Reduce: https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Array/reduce
Access in: August 18, 2018
