Entendendo o Combinador Y [hishamhm]

Entendendo, Finalmente, o Combinador Y - Uma Abordagem de uma Perspectiva Amigável a Programadores

Table of Contents

• 1. META

Este post é destinado a estudantes de Computação que estudaram cálculo lambda mas nunca entenderam o Combinador Y, o mais conhecido combinmador de ponto fixo. O cálculo lambda não tem recursão embutida, mas usando combinadores de ponto fixo podemos produzir facilmente funções recursivas, tornando o cálculo lambda capaz de descrever todas as funções computáveis (e outras palavras, equivalente a uma Máquina de Turing universal). Eis nosso amigo Y:

\[ Y = \lambda f \cdot (\lambda x \cdot f (x x)) (\lambda x \cdot f (x x)) \]

Com isso, você pode escrever uma função não-recursiva de uma função, aplicar Y a ela, e obter a funcionalidade recursiva funcionalmente, mesmo que o cálculo lambda não forneça funções recursivas. Não é difícil entender o que isso faz, mas o mistério para mim era sempre como isso funciona.

Em minha experiência, a principal barreira para entender o combinador era lidar com diversas coisas nao-familiares ao mesmo tempo, cada uma delas deixando uma parte diferente do meu cérebro desconfortável: a semântica do cálculo lambda, a sintaxe do cálculo lambda e o problema em mãos.

Então, para focarmos no problema em mãos, vamos dar um jeito no restante.

Semântica do cálculo lambda: cálculo lambda não-tipado resume-se (grosso modo) a uma linguagem bem simples com evaluação preguiçosa. Tudo o que temos são funções, mas mediante encodações espertas podemos representar números e booleanos com cadeias belamente projetadas de funções. Para simplificar as coisas, então, vamos apenas assumir que já temos números, aritmética e if/then/else. A seguir, vamos nos livrar da evaluação preguiçosa e trocá-la pela evaluação antecipada, que é o que costumamos usar em linguagens de programação imperativas típicas. Para fazer isso, vamos usar uma variante do Y, que é chamada de Z:

\[ Z = \lambda f \cdot (\lambda x \cdot f (\lambda y \cdot x x y)) (\lambda x \cdot f (\lambda y \cdot x x y)) \]

Sim, este é um pouco maior (adicionamos as partes com y), mas vai por mim, é mais fácil de entender, e uma vez que tenha entendido, é só uma questão de re-invoicar a evaluação preguiçosa daquelas classes de programação funcional e aplicar a mesma lógica a Y.

A seguir, a sintaxe: o cálculo lambda é feito de termos, abstrações e aplicações, o que no jargão de linguagens de programação são meramente variáveis, declarações de função e chamadas de função. Portanto, podemos simplesmente reescrevê-lo usando alguma notação familiar e livrando-nos das estranhas sintaxe e regras de precedência por ora. Eu nem mesmo vou usar uma linguagem funcional: vamos usar uma forma restrita de Lua, usando apenas características fornecidas pelo cálculo lambda a fim de tornar a sintaxe mais clara

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

Ok, Ok, isso não está muito legível. Mas já vamos chegar lá. Assumindo que você esteja confortável com funções como valores de primeira classe que podem ser retornados e passados como argumentos, a coisa mais estranha aqui é que no primeiro retorno temos uma função sendo declarada e chamada "em linha", recebendo como parâmetro outra função idêntica a si mesma. Vamos deixar esse fluxo mais claro usando variáveis locais, mas estritamente como "alias". Em outras palavras, isto vai executar sem nenhuma diferença, então não vamos usar nenhuma característica extra que não seja parte do cálculo lambda - note que o nosso uso de variáveis locais aqui será equivalente a uma substituição de macros:

Z = function(f)
       local f1 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       local f2 = function(x)
                     return f(function (y)
                                 return (x(x))(y)
                              end)
                  end
       return f1(f2)
    end

Ok, então esta é a função que queremos entender. Ela ainda não faz sentido, mas podemos ver que Z chama uma função (f1) passando para ela uma função idêntica (f2). Estas funções idênticas retornam o resultado de invocar f (a coisa que queremos tornar recursiva), mas dando como seu argumento outra função que usa algo que chama a si mesmo (x(x)). Um cheiro forte de auto-referência nisso tudo - não é de se espantar, dado que sabemos que a chave para a recursão está aí em algum lugar. Mas vamos parar de brincar de engenharia reversa. Vamos construí-la em vez disso.

Primeiro, vamos relembrar de para que esta função serve, O que queremos ter é funções recursivas, como esta que calcula fatoriais:

fact = function(n)
          if n == 0 then
             return 1
          else
             return n * fact(n-1)
          end
       end

Mas não dá para ter isso em cálculo lambda. Na realidade, tudo isso está certo, exceto pela chamada recursiva a fact(). Nós não temos recursão ainda.

O melhor que podemos fazer é escrever uma função que faz um passo da recursão e deixa o próximo passo para ser feito por outrem. Como isso:

stepper = function(next_step, n)
             if n == 0 then
                return 1
             else
                return n * next_step(n-1)
             end
          end

Porém, eu disse que deveríamos usar apenas características fornecidas pelo cálculo lambda, o que significa que não temos múltiplos argumentos. Felizmente, usando curry, podemos obter o equivalente a múltiplos argumentos. Este é um aspecto do cálculo lambda que eu não vou esconder na sintaxe Lua porque será útil para nosso entendimento. Precisamos fazer um stepper como esse:

stepper = function(next_step)
             return function(n)
                       if n == 0 then
                          return 1
                       else
                          return n * next_step(n-1)
                       end
                    end
          end

A diferença é que agora, em vez de fazer stepper(some_next_step,5) teremos que fazer stepper(some_next_step)(5).

O que esta construção stepper deixa claro é que agora temos uma "fábrica" de funções que retorna nossa função-futuramente-recursiva, exceto que ela só executa um passo e usa outra função que sabe como executar o próximo passo. Você pode pensar que stepper(next_step) na realidade retorna um "passo", que então é executado chamando-o com o parâmetro (5).

Mas precisamos de uma função para executar o próximo passo para passar para o stepper. Como obtê-la? Chamamos a fábrica para obter o próximo passo. Sim, como stepper(stepper).

De fato, note que se executarmos stepper(stepper(stepper(stepper(stepper(stepper())))))(5), obteremos o resultado equivalente a fact(5). (Você pode experimentar no interpretador Lua!)

É claro, nós não queremos escrever isso dessa forma. O plano, portanto, é obter uma função que combine todas essas chamadas. Está na hora do combinador:

combinator = function(stepper)
                -- ?
             end

Esta função deve retornar algo para substituir todos estes steppers aninhados, então queremos que ela retorne uma função que aceita nosso argumento de entrada:

combinator = function(stepper)
                return function(arg)
                          -- ?
                       end
             end

E ela precisa executar stepper() no argumento, claro, daí ela computa nossa função desejada. Mas o que passaremos como próximo passo?

combinator = function(stepper)
                return function(arg)
                          return stepper( --[[ ? ]] )(arg)
                       end
             end

Bem, se o que queremos produzir é stepper(stepper(stepper(stepper(... então talvez o que precisamos é passar stepper() novamente?

combinator = function(stepper)
                return function(arg)
                          return stepper(stepper)(arg) -- no!
                       end
             end

Isto está errado porque só vai executar stepper duas vezes (e, claro, nós sabemos que o combinador não tem essa aparência). Pense na execução de stepper(stepper). Se passarmos 5 como argumento, obteremos stepper(stepper)(5). Isso terá 5 como n e stepper como argumento para next_step. Eventualmente isto invocará next_step(n-1), isto é, stepper(4). Mas stepper espera uma função como argumento, e não um número. De fato, se executarmos isto no interpretador Lua, obteremos um erro de tipo. (Em cálculo lambda não-tipado, não temos uma noção de "erro de tipo", é claro; o que obtemos é apenas uma expressão lambda que não nos faz sentido algum.)

Precisamos dar ao stepper uma função, então parece que vamos ter que fazer uma.

combinator = function(stepper)
                local some_function = function()
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

(Mais uma vez, estou usando uma variável local aqui estritamente como "substituição de macro", apenas a fim de tornar as coisas mais legíveis.)

Para determinar o que colocar em some_function, vamos pensar em para o que ela seria útil. Ela será passada para stepper, e portanto usada como o next_step. Isto significa que ela precisa tomar o argumento numérico então?

combinator = function(stepper)
                local some_function = function(arg)
                                         -- ?
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

Se estamos recebendo um parâmetro, é justo assumir que teremos que fazer algo com ele. O que queremos fazer com nossos argumentos de entrada é executar passos neles, então vamos obter um passo com stepper e fazer isso.

combinator = function(stepper)
                local some_function = function(arg)
                                         return stepper( --[[ ? ]] )(arg)
                                      end
                return function(arg)
                          return stepper(some_function)(arg)
                       end
             end

Oh-oh, voltamos ao problema do que passar para stepper! Isto significa que estamos presos num loop? Bem, note que se simplesmente mantivermos fazendo o mesmo, acabaremos obtendo o equivalente a stepper(stepper(stepper(...))):

combinator = function(stepper)
                local and_yet_another_step = -- ... !!!
                local yet_another_step = function(arg)
                                            return stepper(and_yet_another_step)(arg)
                                         end
                local another_step = function(arg)
                                        return stepper(yet_another_step)(arg)
                                     end
                return function(arg)
                          return stepper(another_step)(arg)
                       end
             end

Mas não, isto não quer dizer que estamos presos num loop. Quer dizer que estamos chegando perto.

O que estamos deixando passar é que quando consideramos o que passar para o primeiro stepper, nós simplesmente dizemos que tinha que ser uma função recebendo um argumento numérico. Mas o que queremos é uma função que retorne o resultado da computação de stepper, mas também produza a função para o passo seguinte! O que queremos é outra função no estilo fábrica como quando transformamos fact em stepper. Em vez de descer um passo, vamos fazer uma função fábrica que gera outra função que desce um passo. Enquanto estamos nisso, e este é o ponto chave, removeremos dela a responsabilidade de calcular como descender para o nível seguinte. Vamos fazer isso assim como quando nos livramos da recursão - simplesmente assuma que você tem o que precisa como parâmetro:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step)(arg)
                       end
             end

Com uma função como make_step, podemos produzir quantos step s quanto quisermos. Se você tem um traquejo matemático, deve estar pensando agora em indução; sim, nós construímos uma forma de resolver um passo de nosso problema assumindo que temos a solução para o seguinte. Este é o espírito.

Então, já chegamos? Isso funciona?

Ainda não. Lembra quando tentamos fazer stepper(stepper)? Isso não funcionou porque stepper não quer uma fábrica como argumento. Ele quer um passo real (lembre que em nosso exemplo ela o usará para obter o fatorial de n-1). Em outras palavras, não queremos passar para ele uma fábrica como make_step. Queremos que make_step nos faça um passo. Então vamos chamá-lo!

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step)(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step( --[[ ? ]] ))(arg)
                       end
             end

Ok, vamos chamá-la, mas o que entregamos a ela? Vamos olhar para o que o argumento de make_step costumava ser usado.

Espere um segundo, ele é usado para fazer um passo também! Então vamos simplesmente passar … ele mesmo?

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return function(arg)
                          return stepper(make_step(make_step))(arg)
                       end
             end

Sim, nós passamos ele mesmo para ele mesmo. E fazemos o mesmo com next_step também, dado que estamos fazendo exatamente a mesma coisa. Veja, aqui está onde tudo se ajunta: para ter recursão, precisamos de auto-referência; e em cálculo lambda, enquanto um termo lambda não pode referenciar a si mesmo em uma abstração (definição de função), nós temos que um termo lambda, quando atrelado a uma variável, pode ser aplicado a si mesmo. A função acima é de verdade um combinador de ponto fixo.

Você pode achar estranho que make_step passa a si mesmo como um parâmetro, então chama a si mesmo passando a si mesmo como parâmetro… seria esse um loop infinito? Não necessariamente, porque no meio de casa passo, não executamos stepper(next_step(next_step)) de cara, imediatamente. Ele vem "embalado" dentro de um function(arg) ... end. (estes são os lambdas extras que o combinador Z tem em comparação ao combinador Y.)

Falando disso, este código é o mesmo que a transformação Lua direta do combinador Z que apresentei acima? Vamos recapitular:

Z = function(f)
       return (function(x)
                  return f(function (y)
                              return (x(x))(y)
                           end)
               end)(function(x)
                       return f(function (y)
                                   return (x(x))(y)
                                end)
                    end)
    end

Não parece muito, né? Mas vamos dar uma olhada mais de perto em nosso combinador. Acontece que neste retorno final, em vez de construir esta função passo explicitamente, podemos simplesmente chamar make_step e obter os mesmos resultados:

combinator = function(stepper)
                local make_step = function(next_step)
                                     return function(arg)
                                               return stepper(next_step(next_step))(arg)
                                            end
                                  end
                return make_step(make_step)
             end

(Em jargão de compiladores, é como se a primeira iteração já tivesse sido desenrolada antes.)

Lembra quando dissemos que as variáveis locais eram meras substituições de macro? Se expandirmos as duas instâncias de make_step, obtemos isso:

combinator = function(stepper)
                return (function(next_step)
                           return function(arg)
                                     return stepper(next_step(next_step))(arg)
                                  end
                        end)(function(next_step)
                                return function(arg)
                                          return stepper(next_step(next_step))(arg)
                                       end
                             end)
             end

Agora, a única diferença é que stepper está sendo chamada de dentro de function(arg) ... end, enquanto na outra está sendo chamada de fora. O funcionamento é o mesmo, porque o propósito de function(arg) ... end é "conter" a expansão dos argumentos entre cada chamada de stepper. Precisamos disso porque Lua não tem evaluação preguiçosa. Para que nossa função se assemelhe a Z, fazemos isto:

combinator = function(stepper)
                return (function(next_step)
                           return stepper(function(arg)
                                             return (next_step(next_step))(arg)
                                          end)
                        end)(function(next_step)
                                return stepper(function(arg)
                                                  return (next_step(next_step))(arg)
                                               end)
                             end)
             end

Aqui estamos! A mesma exata função, só com nomes de variáveis diferentes.

Finalmente, para testá-la:

local factorial_step = function(f)
                          return function (n)
                             if n == 0 then
                                return 1
                             else
                                return n * f(n - 1)
                             end
                          end
                       end
local factorial = combinator(factorial_step)

print(factorial(5))

Aqui obtemos 120, mesmo assim nenhuma função no nosso código chamou a si mesma.

Como podemos ver, não existe nada de mágico sobre o combinador Y: ele produz recursão usando a única forma de auto-referência fornecida pelo cálculo lambda, que é a auto-aplicação de variáveis. Para iniciar o loop, dado que não há forma de atrelar a abstração mais externa (função) a um termo (variável) para que possamos aplicá-la (chamar) a si mesma, ela é simplesmente escrita duas vezes.

Eu tentei explicar isso o mais claro que pude (dadas as suposições que assumi acerca de conhecimento anterior sobre linguagens de programação e cálculo lambda básico). Este foi de fato o fluxo que eu segui quando entendi o combinador. Ele segue claramente uma mentalidade de "programador", o que pode não ser melhor método para todos, mas espero que seja útil para outros como foi útil para mim.

---

1 META

Table 1: META

Título	Understanding, at last, the Y Combinator - a programmer-friendly perspective
Autor	hishamhm
Link	https://hisham.hm/2011/04/04/understanding-at-last-the-y-combinator-a-programmer-friendly-perspective/
Arquivo	http://archive.is/rTf0Z

Created: 2018-12-16 dom 20:13

Validate

Mônadas para Schemers [Dave Herman]

Uma Introdução a Mônadas para Schemers

Table of Contents

• 1. Introdução
• 2. Estilo de Passagem de Continuação
• 3. Estilo de Passagem de Acumulador
• 4. Sumário
• 5. Mais
• 6. META

1 Introdução

Esta será uma introdução a mônadas da perspectiva Lisp/Scheme, com a suposição que o leitor está acostumado a continuações, estilo de passagem de continuações ¹, acumuladores e estilo de passagem de acumuladores.

O principal discernimento de mônadas é que todos os efeitos colaterais, de mutação a E/S a não-terminação, têm uma coisa em comum: a ordem da evaluação é importante. Em expressões lambda puras, simples e com terminação, a ordem da evaluação é completamente irrelevante: não importa como você a reduz, o resultado final é o mesmo sem diferença observável. Mas quando você tem efeitos colaterais, eles devem ocorrer na ordem correta. (Mônadas não são o único formalismo para lidar com isso – EPC e forma normal A também servem. Mas eles estão todos correlacionados.)

2 Estilo de Passagem de Continuação

Assim, mônadas são sobre falar de efeitos no contexto de uma semântica pura. Considere tentar implementar o programa impuro a seguir num subconjunto puro de Scheme:

(begin (turn-on-safety!)
       (pull-trigger!))  

Em nosso Scheme puro, devemos definir BEGIN para evaluar ambos os argumentos (vamos simplesmente nos fixar numa definição de dois argumentos) e evaluar para o valor do segundo. Com a definição ingênua:

(define (begin v1 v2) v2)

Um Scheme puro pode evaluar o programa em ordem arbitrária:

   (begin (turn-on-safety!)
          (pull-trigger!))
-> (begin (turn-on-safety!)  ; effect: pull-trigger!
          #<void>)
-> (begin #<void>            ; effect: turn-on-safety!
          #<void>)
-> #<void>

Isso não é bom. Acabamos de acidentalmente atingir um dos membros de nosso comitê de teses. Ops. Vamos fazer um EPC de nossos programas de tal forma que possamos garantir a ordem de evaluação (estou usando o infixo \[\[–]] para representar a tradução para EPC de uma expressão):

\[\[(begin (turn-on-safety!)
           (pull-trigger!))]] =
(lambda (k)
  (\[\[turn-on-safety!]] (lambda (res1)
                           (\[\[pull-trigger!]] (lambda (res2)
                                                 (k res2))))))

Então, em um programa escrito em EPC, podemos definir BEGIN como

(define (begin cps-exp1 cps-exp2)
  (lambda (k)
    (cps-exp1 (lambda (res1)
                (cps-exp2 (lambda (res2)
                            (k res2)))))))

Note que o resultado da primeira expressão é recebido no argumento res1, e subsequentemente ignorado (nenhuma subexpressão refere-se a res1).

3 Estilo de Passagem de Acumulador

Agora nós também sabemos como escrever programas em estilo de passagem de acumulador, onde todos os procedimentos têm que ter uma entrada extra que representa um "registrador" que é atualizado enquanto a computação avança. Considere um pequeno gerador de números aleatórios:

(define seed (current-time))

(define (rand)
  (let ([ans (modulo (* seed 16807) 2147483647)])
    (begin (set! seed ans)
           ans)))

A cada aplicação de RAND, ele atualiza a semente para o novo número aleatório gerado. Se fôssemos implementar isso em Scheme puro, teríamos que passar a semente como um argumento extra ao longo de quaisquer procedimentos que possam atualizar este valor. Todos os procedimentos também teriam que retornar um par de valores: o real resultado do procedimento, mais a nova semente, em caso de ela ter sido atualizada durante a computação do resultado do procedimento.

;; rand : number -> (number x number)
(define (rand seed)
  (let ([ans (modulo (* seed 16807) 2147483647)])
    (cons ans ans)))

;; rand-point : number -> (point x number)
(define (rand-point seed)
  (let* ([r1 (rand seed)]
         [r2 (rand (cdr r1))]
         [r3 (rand (cdr r2))])
    (cons (make-point (car r1) (car r2) (car r3))
          (cdr r3))))

;; rand-segment : number -> (segment x number)
(define (rand-segment seed)
  (let* ([r1 (rand-point seed)]
         [r2 (rand-point (cdr r1))])
    (cons (make-segment (car r1) (car r2))
          (cdr r2))))
;;; ...

O programa todo iniciaria com uma semente primária mais ou menos assim:

(run-my-program (current-time))  

Cada um destes procedimentos têm um par de características em comum, a saber, eles tomam um parâmetro "semente" e retornam um par consistindo de seu resultado e da nova semente. Vamos começar abstraindo isto pelo currying do parâmetro semente:

;; rand : -> (number -> (number x number))
(define (rand)
  (lambda (seed)
    (let ([ans (modulo (* seed 16807) 2147483647)])
      (cons ans ans))))

;; rand-point : -> (number -> (point x number))
(define (rand-point)
  (lambda (seed)
    (let* ([r1 ((rand) seed)]
           [r2 ((rand) (cdr r1))]
           [r3 ((rand) (cdr r2))])
      (cons (make-point (car r1) (car r2))
            (cdr r2)))))

;; rand-segment : -> (number -> (segment x number))
(define (rand-segment)
  (lambda (seed)
    (let* ([r1 ((rand-point) seed)]
           [r2 ((rand-point) (cdr r1))])
      (cons (make-segment (car r1) (car r2))
            (cdr r2)))))

Qualquer procedimento que não pode ver ou mudar o valor da semente pode ser deixado intocado. Chamamos os procedimentos que podem ter efeitos colaterais de "operações", e procedimentos que não podem de "puros". Por exemplo, podemos escrever uma função distância:

(define (distance pt1 pt2)
  (sqrt (+ (sqr (- (point-x pt1) (point-x pt2)))
           (sqr (- (point-y pt1) (point-y pt2)))
           (sqr (- (point-z pt1) (point-z pt2))))))  

Esta função não afeta a semente, então ela permanece pura. Ela não toma um parâmetro extra para representar a semente corrente, e não retorna um par. Isto significa que qualquer procedimento potencialmente com efeitos pode invocar distance, mas distance não pode invocar nenhum procedimento potencialmente com efeitos (dado que descartaria o efeito e não o passaria para a próxima operação).

Poderíamos simular a obtenção e atribuição de um valor para a semente como operações:

;; get-seed : -> (number -> (number x number))
(define (get-seed)
  (lambda (seed)
    (cons seed seed)))

;; set-seed : number -> (number -> (void x number))
(define (set-seed new)
  (lambda (old)
    (cons (void) new)))

Podemos abstrair o padrão comum nos tipos também: dizemos que uma operação que retorna um valor de tipo alpha tem o tipo T(alpha), onde

T(alpha) = number -> (alpha x number)  

Então nossas operações terão os tipos a seguir:

get-seed     : -> T(number)
set-seed     : number -> T(void)
rand         : -> T(number)
rand-point   : -> T(point)
rand-segment : -> T(segment)  

A seguir tentamos definir BEGIN como antes, só que em vez de EPC é apenas a costura do acumulador:

;; begin : T(alpha) T(beta) -> T(beta)
(define (begin comp1 comp2)
  (lambda (seed0)
    (let* ([res1 (comp1 seed0)]
           [val1 (car res1)]
           [seed1 (cdr res1)])
      (comp2 seed1))))  

Como a versão EPC, este BEGIN é um "combinador de operadores": ele toma duas operações e retorna uma nova. Isso não é muito útil para implementar nossas operações, porém:

(define (rand)
  (begin (get-seed)
         (let ([ans (modulo (* ??? 16807) 2147483647)])
           (begin (set-seed ans)
                  (lambda (seed)
                    (cons ans ans))))))

Como a segunda operação em RAND obtém a semente corrente da operação GET-SEED? O problema é que BEGIN descarta o resultado da primeira operação. Vamos escrever um novo combinador que faz o resultado da primeira operação disponível na segunda:

;; pipe : T(alpha) (alpha -> T(beta)) -> T(beta)
(define (pipe comp1 build-comp2)
  (lambda (seed0)
    (let* ([res1 (comp1 seed0)]
           [val1 (car res1)]
           [seed1 (cdr res1)])
      ((build-comp2 val1) seed1))))

Este novo combinador toma uma operação e uma função que recebe o resultado da primeira operação e constrói uma segunda operação baseada no resultado da primeira. Finalmente, ele executa a segunda operação:

(define (rand)
  (pipe (get-seed)
        (lambda (seed)
          (let ([ans (modulo (* seed 16807) 2147483647)])
            (begin (set-seed ans)
                   (lambda (seed)
                     (cons ans ans)))))))  

Também abstraímos a operação de "elevar" um valor puro como uma operação:

;; lift : alpha -> T(alpha)
(define (lift v)
  (lambda (seed)
    (cons v seed)))  

Agora podemos limpar o fim de RAND:

(define (rand)
  (pipe (get-seed)
        (lambda (seed)
          (let ([ans (modulo (* seed 16807) 2147483647)])
            (begin (set-seed ans)
                   (lift ans))))))  

Cada mônada tem um construtor de tipo T para comunicar-se sobre suas "operações", bem como duas operações:

lift : alpha -> T(alpha)
pipe : T(alpha) (alpha -> T(beta)) -> T(beta)  

\[As operações recebem outros nomes: algumas vezes pipe é conhecido como bind, >>=, * ou let. A operação lift é geralmente chamada unit ou return.]

Além disso essas operações devem satisfazer as três leis seguintes:

(pipe (lift x) f)   = (f x)
(pipe m lift)       = m
(pipe (pipe m f) g) = (pipe m (lambda (x) (pipe (f x) g)))  

\[Estou cansado e não me sinto a fim de provar se as leis da mônada valem para nosso exemplo. Na realidade eles provavelmente não estão porque nossa versão de pipe tem dois argumentos (em vez de ser uma versão com curry completo) – a não-terminação ferraria tudo. Oh, bem.]

A mônada pode ter quaisquer outras operações enquanto não invalidar as leis.

Note que uma operação na nossa mônada é na verdade uma função que precisa de uma semente inicial a fim de produzir um valor. Note também que o resultado de executar uma operação produz um par de valores contendo o valor final mais a semente acumulada. Desde que estamos realmente apenas interessados no valor final, podemos construir um procedimento "run" para executar uma operação monádica e extrair seu valor final:

;; T(alpha) -> alpha
(define (run m)
  (car (m (current-time))))  

Note também que essa é a única maneira de "sair" da mônada, i.e., de ir de T(alpha) para alpha. Uma operação monádica é feita de combinadores para produzir uma longa cadeia de operações e então "executar" com um procedimento de nível mais alto. Este procedimento de nível mais alto é bastante semelhante ao processo de rodar um programa em EPC com uma continuação inicial.

4 Sumário

Os dois maiores conceitos de mônadas como eu descrevi aqui são:

1. Garantir a ordem de evaluação
2. Abstrair acumuladores

A operação PIPE é um combinador para montar uma operação de composição a partir de duas operações menores; ela força as operações a serem realizadas em uma ordem de maneira muito semelhante a EPC. (De fato, ocorre que EPC é um caso especial de mônada.)

Isto nos permite adicionar efeitos a uma linguagem de núcleo puro de tal forma que é garantido que os efeitos acontecerão na ordem correta. isto é útil para a semântica de linguagens de programação, porque nos permite modelar características úteis da linguagem tais como estado mutável e continuações de primeira classe em uma semântica puramente funcional (i.e., cálculo lambda), e nos permite raciocinar abstratamente sobre execução sequencial dos efeitos.

Ela também é usada em Haskell como uma maneira de realizar operações sequenciais em uma linguagem preguiçosa. Em particular, usa-se mônadas para realizar E/S de forma que é garantido que todas as operações de E/S ocorrem na ordem correta. Haskell também usa mônadas para simular diversos tipos de efeito que foi decidido deixar de fora da linguagem base (e.g., estado mutável e continuações de primeira classe).

5 Mais

Eu me ative a uma visão de programador acerca das mônadas. Eu não descrevi o uso de leis algébricas, nem a matemática por detrás delas. De fato, eu nem mesmo defini mônadas. A razão é que uma mônada é realmente um objeto semântico, que é difícil de apontar quando se está observando o código bruto. Decidi então ficar apenas nas intuições e deixar as definições precisas para outro dia. Então, tem muito mas para se aprender.

6 META

Table 1: META

Título	A Schemer's Introduction to Monads
Autor	Dave Herman
Link	http://www.ccs.neu.edu/home/dherman/research/tutorials/monads-for-schemers.txt
Arquivo	http://archive.is/QHSkG

Footnotes:

¹

EPC, ou CPS, de "continuation passing style"

Date: Draft of 13 July 2004

Author: Dave Herman

Created: 2018-12-16 dom 18:58

Validate