Uma Introdução a Mônadas para Schemers
Table of Contents
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 1, 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:
- Garantir a ordem de evaluação
- 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
| 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 |
Nenhum comentário:
Postar um comentário