Mônadas em Scheme (comp.lang.functional)

Erann Gat escreveu:

Minha questão é: é possível apresentar e/ou explicar o conceito de mônada em Scheme? E se não, por que não? É porque Scheme não tem sistema de tipos, e tipos são parte e parcela do que mônadas são? Ou a essência das mônadas pode ser divorciada da teoria dos tipos?

É possível, mas não é a coisa mais divertida do mundo. Mônadas surgem da teoria das categorias, que é um ramo inerentemente tipado da matemática, e existem ligações bem próximas entre teoria das categorias e cálculo lambda tipado. Claro, você pode fazer isso em Scheme, mas será algo mais difícil de entender, dado que você terá que manter mais do código na sua mente e menos no código-fonte.

Mas vou dar uma palhinha – eu tenho pensado em escrever o que sei a fim de solidificar, e você me deu uma boa desculpa :)

• Questão: O que é uma mônada?
  • Resposta: Mônadas são um conceito de teoria das categorias, que programadores funcionais adaptaram para criar um padrão de implementação ¹ para bibliotecas de combinadores.
• Q: Então elas são nada mais que um padrão de implementação para funções de ordem superior?
  • R: Sim, basicamente. Elas são uma das ideias unificadoras em semântica de linguagens de programação, mas para hackers é basicamente um padrão de implementação.
• Q: Então, qual é a sintonia, Kenneth?
  • R: Um, OK. Qualquer mônada consiste de quatro coisas:

    1. Um construtor de tipo M que envia um tipo a para os tipos M[a].

       Estes tipos não devem ser pensados como os tipos de Scheme como string? ou procedure?; em vez disso pense nelas mais como os tipos que programadores Scheme usam para especificar os argumentos para as funções (e.g. "uma lista de inteiros"). [{1}] Você pode ler a como "o tipo a" e M[a] como "o tipo de computações do tipo a".

    2. Uma função unit que tem tipo a -> M[a]. Isto é, toma um valor do tipo a e o injeta no tipo monádico.

    3. Uma função bind do tipo (M[a], a -> M[b]) -> M[b].

       bind é uma função que toma dois argumentos - o primeiro é um valor monádico do tipo M[a] e o segundo é uma função que dado um a retorna um valor monádico do tipo M[b].

    4. Há três leis algébricas que bind e unit devem obedecer. Em Scheme, estas equivalências são

       (bind (unit x) f) == (f x)
       (bind M unit) == M
       (bind (bind M f) g) == (bind M (lambda (x) (bind (f x) g)))
       

• Q: Me dá um exemplo?

  • R: Claro! Eis a mônada mais simples possível - a mônada identidade:

    (define (unit x) x)
    (define (bind m f) (f m))    
    

    Vou deixar a verificação de que bind e unit satisfazem as leis das mônadas como exercício.

• Q: Isto foi trivial demais para ser útil. Que tal um exemplo menos inútil?

  • R: Que exigente. Temos a opção da mônada maybe, que representa computações que podem ou retornar um valor ou falhar com um erro.

    (define fail (vector 'fail)) ; fail não é eq? a nenhuma outra coisa
    (define (unit x) x)
    (define (bind m f)
      (if (eq? m fail)
          fail
          (f m)))
    

    Novamente, eu deixarei a verificação das leis das mônadas para você, leitor.

• Q: Poderia explicar por que eu iria querer usar isso?

  • R: Tudo bem. Suponha que você tenha três funções foo, bar, baz, cada uma delas recebendo um valor (com fail fora do domínio), e ou retornam ou falham retornando fail. Agora, suponha que você quer compor estas três funções, de forma que qualquer falha cause a falha da composição. Assim, você escreve

    (define (foo-bar-baz x)
      (let ((foo-val (foo x)))
        (if (eq? foo-val fail)
            fail
            (let ((bar-val (bar foo-val)))
              (if (eq? bar-val fail)
                  fail
                  (baz bar-val))))))
    

    Então você olha para esse código e suspira, pois ele é feio e não casa o conceito simples que você tinha em mente:

    (define (concept-of-foo-bar-baz x) (baz (bar (foo x))))    
    

    Mas, já que você é um programador funcional, você sabe que pode usar o poder das funções de ordem superior:

    (define (compose* f x)
      (if (eq? x fail)
          fail
          (f x)))
    
    (define (foo-bar-baz x)
      (compose* baz (compose* bar (foo x))))
    

    Bem melhor. Mas espera! A função compose* é precisamente a operação bind da mônada maybe!

• Q: Muito bonito. Mas você adicionou fail a esta API de uma maneira bem ad-hoc. Você tem que fazer isso com todas as mônadas?
  • R: É claro, todas as mônadas precisam ter algumas operações específicas para o que quer que seja que você esteja empregando a mônada. Mas no caso da mônada option, fail é uma instância de um padrão muito comum chamado "mônadas com zeros". Uma mônada com zero tem dois elementos extras em sua API:
    1. Um valor zero, do tipo M[a].
    2. Uma função plus do tipo (M[a], M[a]) -> M[a].

    3. plus e zero precisam obedecer as leis algébricas a seguir:

       (plus m zero) == (plus zero m) == m
       (bind m (lambda (x) zero)) == zero
       (bind zero f) == zero
       

       Assim podemos escrever para a mônada maybe:

       (define zero (vector 'Fail)) ; basta renomear 'fail' para 'zero'
       
       (define (plus a b)
         (if (eq? a zero) b a))
       

       O plus da mônada maybe deveria ser um padrão bastante familiar para o programador Scheme; é exatamente como a forma especial or funciona, exceto que seu valor zero é #f. É por isso que é tão reconfortante usar APIs que retornam #fr em caso de falha e retornem um valor útil caso contrário.

• Q: Existe algum outro exemplo de mônada com zero? Não é seguro generalizar de um exemplo.

  • R: Certamente. Listas formam uma mônada com zero também. Observe:

    (define (unit x) (list x))
    (define (bind m f)
      (apply concatenate (map f m)))
    (define zero '())
    (define (plus a b)
      (append a b))
    

    Verifique as leis das mônadas e do zero!

• Q: Opções e listas são legais, tudo bem. Mas que papo é esse que eu ouço sobre usar mônadas para tratar estado de maneira pura?

  • R: Comecemos com um exemplo. Suponha que você quer escrever uma função que recebe uma árvore binária e então numere as folhas. Para fazer isso com estado imperativo, você pode fazer uma caminhada na árvore e incrementar um contador a cada folha:

    (define state 0)
    
    (define (number-tree tree)
      (if (pair? tree)
          (let* ((left-subtree (number-tree (car tree)))
                 (right-subtree (number-tree (cdr tree))))
            (cons left-subtree right-subtree))
          (let ((n state))
            (set! state (+ state 1))
            n)))
    

    Isto funciona mas não nos permite renumerar duas árvores começando do mesmo número. Então, se tentarmos fazer isso puramente, precisaremos escrever nosso laço em "estilo de passagem de estado", e entremear um contador ao longo do programa.

    (define (number-tree tree state)
      (if (pair? tree)
          (let-values ((lft state-1) (number-tree (car tree) state))
            (let-values ((rgt state-2) (number-tree (cdr tree) state-1))
              (values (cons lft rgt) state-2)))
          (values (+ state 1) (+ state 1))))
    

    A aparência disso é bem desagradável, e seria muito ruim se acidentalmente usássemos o estado atualizado errado. Porém, podemos usar uma mônada para automatizar o trabalho pesado, e obter o benefício de ambas as abordagens.

    ;; O construtor de tipo M[a] = state -> (a, state)
    
    (define (unit x) (lambda (state) (values x state)))
    
    ;; tudo o que bind faz é entremear o state (estado) 
    ;; ao longo de algumas chamadas
    
    (define (bind m-a f)
      (lambda (state)
        (let-values ((a state*) (m-a state))
          ((f a) state*))))
    
    ;; get toma um state e o retorna como valor
    
    (define (get state) (values state state))
    
    ;; set toma um state, e retorna um valor monádico
    ;; que substitui o velho state pelo novo
    
    (define (set new-state) (lambda (state) (values #f new-state)))
    
    ;; run toma um valor monádico state, e então
    ;; o executa com um estado inicial para obter um estado atual
    
    (define (run m state) (m state))
    

    Agora vou definir o programa de numeração da árvore usando uma mônada state. Para torná-lo legível, eu vou usar uma indentação bastante excêntrica:

    (define (number-tree tree)
       (if (pair? tree)
           (begin (bind (number-tree (car tree)) (lambda (left-subtree)
                  (bind (number-tree (cdr tree)) (lambda (right-subtree)
                  (unit (car left-subtree right-subtree)))))))
           (begin (bind get (lambda (n)
                  (bind (set (+ n 1)) (lambda (dont-care)
                  (unit n))))))))
    

    Compare esta com a versão iterativa:

    (define state 0)
    
    (define (number-tree tree)
      (if (pair? tree)
          (let* ((left-subtree (number-tree (car tree)))
                 (right-subtree (number-tree (cdr tree))))
            (cons left-subtree right-subtree))
          (let ((n state))
            (set! state (+ state 1))
            n)))
    

    Estamos usando bind + lambda para simular o uso de let*. Existe uma correspondência um-para-um entre os códigos monádico e imperativo! Neste ponto, a indentação excêntrica do código monádico sugere que seria útil definir uma macro para simplificar as coisas. (Esta macro eu roubei de um artigo do Oleg.)

    (define-syntax do
      (syntax-rules (def)
        ((do (v <- expr) rest) (bind expr (lambda (v) rest)))
        ((do expr)             expr)
        ((do expr expr)        (bind (set expr) (lambda (dummy) expr)))
        ((do expr expr* ...)   (do expr (do expr* ...)))))
    

    Isto emula a notação do de Haskell, que podemos usar assim:

    (define (number-tree tree)
      (if (pair? tree)
          (do (left-subtree <- (number-tree (car tree)))
              (right-subtree <- (number-tree (cdr tree)))
            (unit (cons left-subtree right-subtree)))
          (do (n <- get)
              (set (+ n 1))
            (unit n))))
    

    Legal, né?

• Q: Mó legal. Então um compilador Haskell toma programas usando a mônada state puramente funcional e internamente otimiza para um programa usando mutação?
  • R: Exatamente.
• Q: O que mais as mônadas podem fazer?
  • R: Você também pode transformar programas no estilo de passagem de continuação em forma monádica. De fato, é um resultado significativo (devido a Andrezj Filinski) que todos os programas interativos utilizando call/cc e estado podem ser traduzidos para o estilo monádico, e vice-versa. Assim, exceções, não-determinismo, co-rotinas, dentre outros, têm todos uma expressão monádica.
• Q: Por que as descrições Haskell de mônadas focam tão pesadamente nesta conversa estranha de "classes de tipos"?

  • R: Classes de tipos são apenas sobrecarga com esteroides, e cada mônada neste artigo tem suas próprias operações bind e unit. Assim, haskelleiros sobrecarregam bind e unit (que eles chamam >>= e return) para cada mônada que escrevem, de tal forma que seus códigos monádicos comprometam-se o mínimo possível com a mônada específica. É apenas uma prática boa e sólida de engenharia de software.

    Isso seria difícil de fazer em LISP (e.g. com o CLOS), por causa da operação unit – você teria que selecionar a operação unit apropriada baseada no tipo esperado de return, e isso é algo que inerentemente precisa de um sistema de tipos estático para funcionar.

• Autor: Neelakantan Krishnaswami
• Link: nome para o link
• Arquivo: http://archive.is/tlnh0