we are developers

iMaster Developers

iMaster DevelopersPowered by:

Desenvolvimento

4 fev, 2013

Compreendendo monads com JavaScript

Ionut G. Stan

Tem 4 artigos publicados com 1600 visualizações desde 2013

Ionut G. Stan
Publicidade

Nas últimas semanas, eu trabalhei muito estudando monads. Ainda estou aprendendo Haskell e, para ser honesto, eu achava que sabia tudo sobre monads, mas quando eu quis escrever uma simples biblioteca Haskell, apenas para afiar minhas habilidades, eu percebi que enquanto eu entendia a forma como monadic bind (>>=) e return funcionam, eu não tinha conhecimento desse estado. Assim, o mais provável é que eu não tinha nenhum conhecimento afinal. Como resultado disso, eu achei que havia redescoberto monads usando JavaScript. O plano era basicamente o mesmo que usei quando derivei o Y Combinator: começar a partir do problema inicial (lidando com o estado imutável explícito, nesse caso) e trabalhar o meu caminho até a solução aplicando transformações de código simples.

Além disso, eu escolhi JavaScript porque ele te força a escrever um código que o Haskell esconde para você, graças à sua sintaxe concisa ou semântica diferente (expressões lambda, operadores e função currying built-in). Por fim, aprendi melhor por comparação, e é por isso que eu tentei em CoffeeScript e Scheme também. Aqui estão os fundamentos GitHub para os dois últimos:

Constraints

Neste artigo, vou limitar o meu problema ao state monad. Compreendê-lo é o suficiente para ter uma ideia do que são os monads. Então, aqui estão as constraints de solução.

  • Nenhum estado mutável: Haskell faz uso do state monad porque não permite o estado mutável.
  • Nenhum estado explícito: Quando não tem um estado mutável, você tem que fazer uma thread no estado residual ao redor. Não é agradável ter que digitar e ler todos os estados intermediários. Os monads tentam esconder todas essas canalizações. Daqui a pouco você vai ver o que quero dizer.
  • Sem duplicação de código: Isso está lado a lado com o ponto anterior, mas eu ainda o cito aqui porque na minha experiência a remoção de duplicação de código é uma ferramenta poderosa para explorar novas bases.

Versão resumida

Este artigo é um muito denso, então eu achei que deveria adicionar algum material. É por isso que eu gravei um pequeno vídeo com todos os passos que são descritos abaixo. É uma espécie de versão resumida, e deve ajudar a visualizar as transições mais facilmente, mas é provável que ele não faça muito sentido se você ler todo o artigo.

Eu aconselho que você assista diretamente no Vimeo, onde ele está disponível em HD.

Veículo de derivação

Vou usar uma pilha como o meu veículo de derivação porque é fácil de entender a estrutura de dados, e sua aplicação usual é feita usando o estado mutável. Para começar, vamos dar uma olhada em como você normalmente usa uma pilha em JavaScript.

var stack = [];

stack.push(4);
stack.push(5);
stack.pop(); // 5
stack.pop(); // 4

Objetos array JavaScript têm os métodos usuais que se espera da pilha, push e pop. O que não me agrada nisso é que ele sofre mutações de estado. Bem, pelo menos eu não gosto por causa deste artigo.

Cada passo que vou descrever será uma etapa de trabalho. Basta abrir o console do seu navegador e recarregar a página. Você vai ver grupos de console diversos com string 5: 4 logado por dentro. No entanto, no decorrer do artigo, vou apresentar apenas as partes que diferem das etapas anteriores.

Uma pilha com a manipulação explícita do estado

A solução óbvia para evitar o estado mutável é a construção de um novo container state a cada vez que precisarmos de mutação. Veja como ele pode parecer em JavaScript (note que concat e slice são dois métodos Array que não transformam o objeto que for chamado; em vez disso, criam novos objetos Array):

var push = function (element, stack) {
  var newStack = [element].concat(stack);

  return newStack;
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var stack1 = push(4, stack0);
var stack2 = push(5, stack1);
var result0 = pop(stack2);        // {value: 5, stack: [4]}
var result1 = pop(result0.stack); // {value: 4, stack: []}

Como você pode ver, tanto push quanto pop retornam uma pilha residual, o resultado estado. Além disso, pop retorna o valor retirado. Cada operação seguinte da pilha usa a pilha anterior, mas isso pode não ser fácil de observar por causa das diferenças na representação de valores de retorno. No entanto, a duplicação de código pode ser enfatizada normalizando os valores de retorno. Nós teremos push retornando um valor undefined fictício.

var push = function (element, stack) {
  var value = undefined;
  var newStack = [element].concat(stack);

  return { value: value, stack: newStack };
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var result0 = push(4, stack0);
var result1 = push(5, result0.stack);
var result2 = pop(result1.stack); // {value: 5, stack: [4]}
var result3 = pop(result2.stack); // {value: 4, stack: []}

Esse é o tipo de duplicação sobre o qual falei antes. Duplicação que também significa lidar explicitamente com o estado.

Transformando para o estilo Passing-Continuation

Agora, vou substituir essas variáveis ​​de resultados intermediários com funções e parâmetros. Farei isso porque considero mais fácil de abstrair por meio de funções e parâmetros do que por variáveis simples. Para isso, vou criar uma pequena função auxiliar, chamada bind, que não faz nada mais do que apenas aplicar uma continuação callback para o resultado da operação de pilha. Em outros trabalhos, ele liga a continuação à uma operação de pilha.

var bind = function (value, continuation) {
  return continuation(value);
};

var stack0 = [];

var finalResult = bind(push(4, stack0), function (result0) {
  return bind(push(5, result0.stack), function (result1) {
    return bind(pop(result1.stack), function (result2) {
      return bind(pop(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

O valor de retorno de toda a expressão, armazenado em finalResult, tem o mesmo tipo que o valor de retorno de uma única operação push ou ou operação pop. Queremos ter interfaces consistentes.

Currying push e pop

Em seguida, nós queremos ser capazes de separar os argumentos de pilha de push e pop. Queremos isso porque a intenção é ter a thread bind vinculada aos bastidores.

Para isso, vamos aplicar outro truque de cálculo lambda chamado de função currying. Um nome alternativo poderia ser adiamento de  aplicação de função.

Agora, em vez de chamar push(4, stack0), vamos chamar push(4)(stack0). Em Haskell, nem precisaríamos desse passo, pois suas funções são curried por padrão.

var push = function (element) {
  return function (stack) {
    var value = undefined;
    var newStack = [element].concat(stack);

    return { value: value, stack: newStack };
  };
};

var pop = function () {
  return function (stack) {
    var value = stack[0];
    var newStack = stack.slice(1);

    return { value: value, stack: newStack };
  };
};

var stack0 = [];

var finalResult = bind(push(4)(stack0), function (result0) {
  return bind(push(5)(result0.stack), function (result1) {
    return bind(pop()(result1.stack), function (result2) {
      return bind(pop()(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

Preparando bind para manipular pilhas intermediárias

Como já mencionei na seção anterior, eu gostaria que bind lidasse com a passagem dos argumentos de pilha explícitos. Primeiro, vamos fazer com que o bind aceite uma pilha como seu último parâmetro, mas de uma forma curried, ou seja, bind agora retorna uma função que tem uma pilha. Além disso, push e pop são agora aplicados parcialmente, ou seja, nós não precisamos mais passá-los para a pilha manualmente. Em vez disso, bind vai desempenhar esse papel.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    return continuation(stackOperation(stack));
  };
};

var stack0 = [];

var finalResult = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      })(result2.stack);
    })(result1.stack);
  })(result0.stack);
})(stack0);

Removendo stacks trailing

Agora somos capazes de esconder as pilhas intermediárias, modificando o bind para inspecionar o valor de retorno de um stackOperation. Extraia a pilha e use-a como um argumento para o valor de retorno da continuação callback, a qual deve ser uma função que recebe uma pilha. É por isso que também temos que empacotar o resultado final (return result2.value + ” : ” + result3.value) dentro de uma função anônima que receberá uma pilha.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    var newStack = result.stack;
    return continuation(result)(newStack);
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;

        // We need this anonymous function because we changed the protocol
        // of the continuation. Now, each continuation must return a
        // function which accepts a stack.
        return function (stack) {
          return { value: value, stack: stack };
        };
      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Ocultando a pilha residual final

Na etapa anterior, ocultamos várias pilhas intermediárias, mas expusemos uma nova na função que envolve o valor do resultado final. Nós podemos ocultar esse traço de uma pilha screvendo outra função auxiliar, que vou chamar de result. Além disso, ela também ocultará a representação interna do estado que estamos mantendo, ou seja, uma estrutura com dois campos, value e stack.

var result = function (value) {
  return function (stack) {
    return { value: value, stack: stack };
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {

        return result(result2.value + " : " + result3.value);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Isso é exatamente o que as funções return fazem em Haskell. Ela envolve o resultado de computação dentro de um monad. No nosso caso, ela envolve o resultado em um closure que aceita uma pilha. Mas isso é basicamente o que o monoid state é, uma função que aceita o seu estado. Outra forma de ver o result/return é como uma função factory que cria um novo contexto de estado em torno do valor que fornecemos com ele.

Mantendo o estado interno

Nós não queremos que nossos callbacks de continuação tenham que percorrer ou até mesmo conhecer a estrutura retornada por push ou pop, que na verdade representam os internos da monad. Então, vamos modificar bind para transmitir apenas os dados mínimos necessários para o callback.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    return continuation(result.value)(result.stack);
  };
};

var computation = bind(push(4), function () {
  return bind(push(5), function () {
    return bind(pop(), function (result1) {
      return bind(pop(), function (result2) {

        return result(result1 + " : " + result2);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Avaliando o cálculo da pilha

Uma vez que somos capazes de compor operações de pilha dessa forma, nós também vamos querer executar esses cálculos e fazer algo com o resultado. Isso é geralmente chamado de avaliação monad. Em Haskell, o monad state fornece três funções para a avaliação do estado de monad: runState, evalState, e execState.

Entretanto, para este artigo, eu vou substituir o sufixo “State” por “Stack”.

// Returns both the result and the final state.
var runStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack);
};

// Returns only the computed result.
var evalStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).value;
};

// Returns only the final state.
var execStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).stack;
};

var stack0 = [];

console.log(runStack(computation, stack0));
// { value="5 : 4", stack=[]}

console.log(evalStack(computation, stack0));
// 5 : 4

console.log(execStack(computation, stack0));
// []

Se tudo o que nos interessa é o valor final calculado, então precisamos do evalStack. Ele acionará todo o cálculo monádico, soltará o state resultante final e retornará. Usando essa função, podemos extrair um valor fora de seu contexto de monad.

Se você já ouviu falar que não se pode escapar de um monad, então vou te contar que isso é verdade apenas em um pequeno número de casos, como monad IO. Mas isso é outra história. O ponto é que você pode se livrar do monad state.

Feito

Se você ainda está comigo, então deixa eu te dizer que essa é a aparência do monad state em JavaScript. Provavelmente não parece muito legível em comparação com uma versão semelhante Haskell, mas é o máximo que eu posso sair do JavaScript hoje.

Um monad é um conceito bastante abstrato, porque especifica pouco sobre o que você tem que escrever. Principalmente, ele diz que você precisa projetar uma função que vai requerer alguns argumentos (o estado, no caso do monad state), e duas funções adicionais: result e bind. A primeira irá atuar como um factory para a função que você acabou de projetar. A segunda será responsável por expor apenas detalhes suficientes sobre seu monad para o mundo exterior, além de executar algumas coisas chatas como transmitir estado por aí. A exposição é feita por meio de uma função de continuação, que terá o valor que monad calcula. Tudo o que é interno ao monad será mantido interno, assim como em programação orientada a objetos. E é até possível ter getters/setters de monad para esses internos.

Apenas para registrar, aqui está um exemplo de como a função computation seria em Haskell.

computation = do push 4
                 push 5
                 a <- pop
                 b <- pop
                 return $ (show a) ++ " : " ++ (show b)

A razão principal de a versão em Haskell parecer melhor é porque o Haskell tem suporte sintático built-in para monads na forma da notação do. Ela é só um facilitador para a versão seguinte, que ainda se parece melhor do que o JavaScript. Na minha opinião, o Haskell, tendo suporte para definições de operador e expressões lambda concisas, permite que a implementação de monads seja mais legível.

computation = push 4 >>= \_ ->
              push 5 >>= \_ ->
              pop    >>= \a ->
              pop    >>= \b ->
              return $ (show a) ++ " : " ++ (show b)

O que eu chamei de bind em JavaScript é >>= em Haskell, e o que eu chamei de result em JavaScript é o return em Haskell. Sim, o return em Haskell é uma função, não uma palavra-chave. Em outras ocasiões, ele é chamado unit. Brian Marick chamou >>= de um decisor em seus vídeos sobre monads em Clojure. Claro que o patcher foi return.

Vamos adoçar um pouco o JavaScript

Acontece que existe uma maneira melhor de fazer cálculos de monads em JavaScript usando uma pequena função de chamada sequence. Graças à natureza dinâmica do JavaScript, ela pode ter um número variável de argumentos que representam as ações de monads que ela deve executar em sequência, salvo o argumento final que é um callback que contém o cálculo sobre o resultado das ações de monads. O callback é chamado com todos os resultados não-undefined das ações de monads.

var sequence = function (/* monadicActions..., continuation */) {
  var args           = [].slice.call(arguments);
  var monadicActions = args.slice(0, -1);
  var continuation   = args.slice(-1)[0];

  return function (stack) {
    var initialState = { values: [], stack: stack };

    var state = monadicActions.reduce(function (state, action) {
      var result = action(state.stack);
      var values = state.values.concat(result.value);
      var stack  = result.stack;

      return { values: values, stack: stack };
    }, initialState);

    var values = state.values.filter(function (value) {
      return value !== undefined;
    });

    return continuation.apply(this, values)(state.stack);
  };
};

var computation = sequence(
  push(4), // <- programmable commas :)
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var initialStack = [];
var result = computation(initialStack); // "5 : 4"

Os autores do Real World Haskell compararam os monads a um ponto e vírgula programável. Nesse caso, posso dizer que temos vírgulas programáveis, porque isso foi o que eu usei quando chamei sequence para separar ações de monads.

Monads como cálculos suspensos

Você vai ver muitas vezes monads sendo chamados de cálculos. No começo, eu não entendia o porquê. Você pode dizer: “Isso é porque eles calculam coisas”, mas ninguém diz “monads calculam alguma coisa”. Eles dizem “monads são cálculos“. Depois de terminar um primeiro rascunho deste artigo, acho que finalmente entendi o que é isso (ou acho que entendi). Todo o encadeamento de ações de monads e os valores realmente não calculam nada até que você diga a eles para fazerem isso. É tudo uma grande cadeia de funções parcialmente aplicadas, o que representa uma computação suspensa que vai finalmente ser desencadeada por chamá-lo com o estado inicial. Mais uma vez, aqui está o trecho:

var computation = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

Será que ele calcula qualquer coisa quando é avaliado? Não. Você tem que acionar o cálculo com runStack, execStack ou evalStack.

var initialStack = [];
evalStack(computation, initialStack);

Parece que as funções push e pop agem em algum valor global, enquanto que na verdade estão sempre esperando que esse valor venha. É quase como em OOP, em que this este é o contexto da computação. No nosso caso, porém, this é implementado por meio de currying e da aplicação parcial. Ele também aponta para um novo contexto em cada expressão. E, se no contexto OO é considerado implícito, em seguida, usando monads, você o torna ainda mais implícito (se existe mesmo tal coisa).

A vantagem de monads (e da programação funcional em geral) é que você tem blocos de construção altamente combináveis​​. E é tudo por causa da função currying. Cada vez que duas ações de monads são encadeadas, uma nova função é criada e aguarda para ser executada.

var computation1 = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var computation2 = sequence(
  push(2),
  push(3),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var composed = sequence(
  computation1,
  computation2,

  function (a, b) {
    return result(a + " : " + b);
  }
);

console.log( evalStack(composed, []) ); // "5 : 4 : 3 : 2"

Isso pode parecer inútil para a realização de operações de pilha, mas na concepção de uma biblioteca de elementos de combinação parser monádicos, por exemplo, isso se torna muito útil. Ele permite que o autor da biblioteca forneça apenas algumas funções “primitivas” em seu monad Parser e, em seguida, o usuário da biblioteca é capaz de misturar e combinar esses primitivos como bem entender, acabando, finalmente, com um domínio integrado de linguagem específica (EDSL).

Fim

Bem, eu espero que você tenha achado este artigo útil. Escrevê-lo definitivamente me ajudou a ter uma melhor compreensão de monads.

Referências

***

Texto original disponível em http://igstan.ro/posts/2011-05-02-understanding-monads-with-javascript.html

Ionuț G. Stan

De 0 a 10, o quanto você recomendaria este artigo para um amigo?

Ionut G. Stan
Saiba mais

Ionut G. Stan

edit4 Artigo(s)

É um desenvolvedor de software autodidata com vários anos de experiência na área. Seus interesses incluem paradigmas da programação, e design de linguagem de programação, teoria e implementação.