Matemática Funcional em Scheme
Scheme é um dos principais "dialetos" de Lisp, que adere ao paradigma funcional e é a segunda linguagem de programação mais antiga ainda amplamente utilizada. Devido à sua flexibilidade e simplicidade, Scheme é usada para extender e customizar o comportamento de outros softwares e foi adotada como a linguagem de scripting oficial do GNU Project.
Conteúdos explorados
O oficina abordará algumas técnicas de programação funcional em Scheme para algoritmos matemáticos e métodos numéricos, incluindo:
- Tipos de recursão e tail call optimization
- Abstração com funções de alta ordem e closures
- Paradigma de fluxo de dados (streams): ao infinito e além com lazy evaluation
- Processamento simbólico e metalinguagem
É necessário conhecimento prévio de programação, não necessariamente do paradigma funcional. Noções de Matemática Discreta e Cálculo Numérico são recomendadas mas não obrigatórias.
Ferramentas utilizadas
Chez Scheme (preferência pessoal), GNU Guile (disponível na ISO do PET Computação) ou a sua implementação favorita de Scheme.
Bibliografia
-
MIT OpenCourseWare 6.001 SICP lectures
- Abelson H., Sussman G. J. -
How to Design Programs
- Felleisen M., Findler R. B., Flatt M., Krishnamurthi S.
Bibliografia
-
MIT OpenCourseWare 6.001 SICP lectures
- Abelson H., Sussman G. J. -
How to Design Programs
- Felleisen M., Findler R. B., Flatt M., Krishnamurthi S.
Computando com Scheme
Sobre Linguagens
Qualquer notação usada para dar instruções pode ser considerada uma linguagem de programação (Schmidt).
Talvez pela familiaridade com a área e a base formal já existente, a maioria das linguagens de programação de uso geral (incluindo Scheme) se baseia em computar funções matemáticas através de expressões. O mecanismo principal se baseia na "coincidência" de que a expressão que descreve o valor de uma função pode ser interpretada como um procedimento para computar aquele valor (Abelson e Sussman, 1968).
Por exemplo, tendo uma função polinomial expressa em "matematiquês":
\[ x^2 - x - 1 \]
Podemos expressá-la com caracteres padrão em alguma linguagem (por acaso a notação abaixo é código válido de Octave, provavelmente o sendo em mais uma série de outras linguagens):
x ^ 2 - x - 1
Um polinômio equivalente na notação pré-fixada de Lisp seria
(+ (^ x 2) (- x) -1)
Sintaxe e Semântica
Programas devem ser escritos para que pessoas possam os ler, e apenas incidentalmente para que máquinas os executem (Abelson e Sussman, 1968).
A notação das expressões de uma linguagem específica é dita a sua sintaxe; e mesmo que esse tópico não nos interesse no escopo deste minicurso, começamos falando sobre sintaxe pois apenas expressões sintaticamente corretas possuem semântica, ou seja, significado, associado a elas.
Mais importante ainda, falamos da sintaxe de Scheme para destacar seu minimalismo: ela é composta essencialmente pelas chamadas expressões simbólicas (sexprs), cada uma delas caracterizando uma árvore binária, podendo ser:
- Um átomo; ou
- Uma expressão na forma
(head . tail)ondeheadetailsão sexprs.
Pragmática
Aos prospectivos utilizadores de uma linguagem de programação interessa mais um outro elemento: a pragmática, ou seja, os aspectos práticos da linguagem que a tornam útil para alcançar um conjunto de possíveis objetivos (Cameron).
Neste minicurso será dado enfoque especial à aplicações matemáticas de Scheme como linguagem de programação funcional, onde a principal forma de abstração é encontrada na manipulação de funções.
Metalinguagem
Por último, mas não menos importante, temos a ferramenta com a qual falamos sobre uma linguagem, descrevemos suas características e discutimos suas aplicações: a metalinguagem que lhe cabe.
Mais adiante veremos que é possível empregar Scheme como uma linguagem de programação de uso geral que não é especialmente adequada a resolver nenhuma classe de problemas; em vez disso, seu maior potencial está na capacidade de construir e embarcar em si mesma a linguagem mais apta para fazê-lo através de abstrações metalinguísticas (Abelson e Sussman).
Introdução à Scheme
Programas
Os atos pelos quais a mente exerce seu poder sobre as idéias são principalmente três: (1) Combinando várias idéias simples em uma composta e originando assim todas as idéias complexas; (2) Reunindo duas idéias, simples ou complexas, a fim de ter uma visão delas, sem, contudo, unificá-las numa, obtendo por este meio todas as suas noções das relações; (3) Separando-as de todas as outras idéias que lhes integram, no processo chamado abstração: deste modo a mente forma todas as suas idéias gerais. (Locke, 1689)
Toda a linguagem de programação que se preze possui três mecanismos básicos com os quais expressa programas:
- Entidades primitivas: os objetos mais simples dos quais fala a linguagem.
- Meios de combinação: a construção de elementos compostos através de outros mais simples.
- Meios de abstração: pelos quais manipulamos elementos independentemente da sua complexidade.
Interpretação
Para testar os exemplos nas subseções a seguir, utilize alguma implementação de Scheme:
- Chez - Ótimo REPL, possui um dos interpretadores mais rápidos e uma versão adicional minimalista para distribuição de programas interpretados.
- Bigloo - Um exemplo de transpilador Scheme->C que permite gerar binários executáveis e altamente portáveis.
- Guile - É a linguagem de scripting oficial do GNU Project, sendo utilizada como linguagem de extensão e configuração do sistema operacional funcional GuixSD.
- Racket - Tem uma IDE feita para Scheme, o Dr. Racket; oferecendo, além da linguagem padrão, mais um grande conjunto de "dialetos".
- Outros - Procure implementações com comunidade ativa e que se adequem aos padrões Revised^n Report on the Algorithmic Language Scheme (RnRS). Se você deseja alguma feature específica, confira se a sua implementação já a oferece através de algum Scheme Request For Implementation (SRFI).
Saiba consultar a documentação da sua implementação.
Na dúvida, Dybvig e Sitaram podem ajudar.
Estrutura (exemplos)
Primitivas
Alguns exemplos de entidades primitivas em Scheme:
; numeros
42
0.03
12e-4
67+89i
12/40
; booleanos
#t
#f
; funcoes primitivas
+
-
odd?
even?
car
cdr
; simbolos
'a
'λ
'scheme
; caracteres
#\c
#\f
Combinações
Vejamos os meios de combinação presentes em Scheme:
; pares
(cons 'head 'tail)
(car (cons 1 2))
(cdr (cons 1 2))
; listas
'()
(list 1 2 3)
(cdr '(a b c))
; funcoes anonimas
(lambda (x) x)
(lambda (a b) (+ a b))
; strings
"Hello, Scheme World!"
; vetores
#(1 2 3)
Dados vs Código
Listas são encadeamentos de pares (como uma corrente) terminadas em '().
Assim, os dados processados em Scheme possuem exatamente a mesma forma que seu código.
Essa propriedade se chama Homoiconicidade.
Abstrações
São alguns meios de abstração de Scheme:
; nomes temporarios
(let ((x 7)
(y 8))
(+ x y))
(let* ((a 2)
(b (+ a 1))
(c (* a b)))
(+ a b c))
; definicoes
(define x 5)
(define (identity x) x)
(define list
(lambda (first . rest) (cons first rest)))
(define (foo x)
(define (even? n)
(display "even? ") (display n) (newline)
(if (= n 0)
#t
(odd? (- n 1))))
(define (odd? n)
(display "odd? ") (display n) (newline)
(if (= n 0)
#f
(even? (- n 1))))
(cond ((even? x) "EVEN")
((odd? x) "ODD")
(else "????")))
; mix
(let 2^ ((n 10)
(acc 1))
(if (= n 0) acc
(2^ (- n 1) (* acc 2))))
(let ((a 1))
(define (foo x)
(define b (+ a x))
(define a 5)
(+ a b))
(display (foo 10)) (newline)
a)
Sim,
footem vários problemas. Tente corrigi-los.Procure escrever em Scheme a definição de um procedimento que calcula em um ponto
xo valor do polinômio \( x^2 - x -1 \).Em seguida, implemente um procedimento
(list-ref lst n)que retorna o n-ésimo elemento de uma lista.
Sobre Linguagens
Qualquer notação usada para dar instruções pode ser considerada uma linguagem de programação (Schmidt).
Talvez pela familiaridade com a área e a base formal já existente, a maioria das linguagens de programação de uso geral (incluindo Scheme) se baseia em computar funções matemáticas através de expressões. O mecanismo principal se baseia na "coincidência" de que a expressão que descreve o valor de uma função pode ser interpretada como um procedimento para computar aquele valor (Abelson e Sussman, 1968).
Por exemplo, tendo uma função polinomial expressa em "matematiquês":
\[ x^2 - x - 1 \]
Podemos expressá-la com caracteres padrão em alguma linguagem (por acaso a notação abaixo é código válido de Octave, provavelmente o sendo em mais uma série de outras linguagens):
x ^ 2 - x - 1
Um polinômio equivalente na notação pré-fixada de Lisp seria
(+ (^ x 2) (- x) -1)
Sintaxe e Semântica
Programas devem ser escritos para que pessoas possam os ler, e apenas incidentalmente para que máquinas os executem (Abelson e Sussman, 1968).
A notação das expressões de uma linguagem específica é dita a sua sintaxe; e mesmo que esse tópico não nos interesse no escopo deste minicurso, começamos falando sobre sintaxe pois apenas expressões sintaticamente corretas possuem semântica, ou seja, significado, associado a elas.
Mais importante ainda, falamos da sintaxe de Scheme para destacar seu minimalismo: ela é composta essencialmente pelas chamadas expressões simbólicas (sexprs), cada uma delas caracterizando uma árvore binária, podendo ser:
- Um átomo; ou
- Uma expressão na forma
(head . tail)ondeheadetailsão sexprs.
Pragmática
Aos prospectivos utilizadores de uma linguagem de programação interessa mais um outro elemento: a pragmática, ou seja, os aspectos práticos da linguagem que a tornam útil para alcançar um conjunto de possíveis objetivos (Cameron).
Neste minicurso será dado enfoque especial à aplicações matemáticas de Scheme como linguagem de programação funcional, onde a principal forma de abstração é encontrada na manipulação de funções.
Metalinguagem
Por último, mas não menos importante, temos a ferramenta com a qual falamos sobre uma linguagem, descrevemos suas características e discutimos suas aplicações: a metalinguagem que lhe cabe.
Mais adiante veremos que é possível empregar Scheme como uma linguagem de programação de uso geral que não é especialmente adequada a resolver nenhuma classe de problemas; em vez disso, seu maior potencial está na capacidade de construir e embarcar em si mesma a linguagem mais apta para fazê-lo através de abstrações metalinguísticas (Abelson e Sussman).
Introdução à Scheme
Programas
Os atos pelos quais a mente exerce seu poder sobre as idéias são principalmente três: (1) Combinando várias idéias simples em uma composta e originando assim todas as idéias complexas; (2) Reunindo duas idéias, simples ou complexas, a fim de ter uma visão delas, sem, contudo, unificá-las numa, obtendo por este meio todas as suas noções das relações; (3) Separando-as de todas as outras idéias que lhes integram, no processo chamado abstração: deste modo a mente forma todas as suas idéias gerais. (Locke, 1689)
Toda a linguagem de programação que se preze possui três mecanismos básicos com os quais expressa programas:
- Entidades primitivas: os objetos mais simples dos quais fala a linguagem.
- Meios de combinação: a construção de elementos compostos através de outros mais simples.
- Meios de abstração: pelos quais manipulamos elementos independentemente da sua complexidade.
Interpretação
Para testar os exemplos nas subseções a seguir, utilize alguma implementação de Scheme:
- Chez - Ótimo REPL, possui um dos interpretadores mais rápidos e uma versão adicional minimalista para distribuição de programas interpretados.
- Bigloo - Um exemplo de transpilador Scheme->C que permite gerar binários executáveis e altamente portáveis.
- Guile - É a linguagem de scripting oficial do GNU Project, sendo utilizada como linguagem de extensão e configuração do sistema operacional funcional GuixSD.
- Racket - Tem uma IDE feita para Scheme, o Dr. Racket; oferecendo, além da linguagem padrão, mais um grande conjunto de "dialetos".
- Outros - Procure implementações com comunidade ativa e que se adequem aos padrões Revised^n Report on the Algorithmic Language Scheme (RnRS). Se você deseja alguma feature específica, confira se a sua implementação já a oferece através de algum Scheme Request For Implementation (SRFI).
Saiba consultar a documentação da sua implementação.
Na dúvida, Dybvig e Sitaram podem ajudar.
Estrutura (exemplos)
Primitivas
Alguns exemplos de entidades primitivas em Scheme:
; numeros
42
0.03
12e-4
67+89i
12/40
; booleanos
#t
#f
; funcoes primitivas
+
-
odd?
even?
car
cdr
; simbolos
'a
'λ
'scheme
; caracteres
#\c
#\f
Combinações
Vejamos os meios de combinação presentes em Scheme:
; pares
(cons 'head 'tail)
(car (cons 1 2))
(cdr (cons 1 2))
; listas
'()
(list 1 2 3)
(cdr '(a b c))
; funcoes anonimas
(lambda (x) x)
(lambda (a b) (+ a b))
; strings
"Hello, Scheme World!"
; vetores
#(1 2 3)
Dados vs Código
Listas são encadeamentos de pares (como uma corrente) terminadas em '().
Assim, os dados processados em Scheme possuem exatamente a mesma forma que seu código.
Essa propriedade se chama Homoiconicidade.
Abstrações
São alguns meios de abstração de Scheme:
; nomes temporarios
(let ((x 7)
(y 8))
(+ x y))
(let* ((a 2)
(b (+ a 1))
(c (* a b)))
(+ a b c))
; definicoes
(define x 5)
(define (identity x) x)
(define list
(lambda (first . rest) (cons first rest)))
(define (foo x)
(define (even? n)
(display "even? ") (display n) (newline)
(if (= n 0)
#t
(odd? (- n 1))))
(define (odd? n)
(display "odd? ") (display n) (newline)
(if (= n 0)
#f
(even? (- n 1))))
(cond ((even? x) "EVEN")
((odd? x) "ODD")
(else "????")))
; mix
(let 2^ ((n 10)
(acc 1))
(if (= n 0) acc
(2^ (- n 1) (* acc 2))))
(let ((a 1))
(define (foo x)
(define b (+ a x))
(define a 5)
(+ a b))
(display (foo 10)) (newline)
a)
Sim,
footem vários problemas. Tente corrigi-los.Procure escrever em Scheme a definição de um procedimento que calcula em um ponto
xo valor do polinômio \( x^2 - x -1 \).Em seguida, implemente um procedimento
(list-ref lst n)que retorna o n-ésimo elemento de uma lista.
Repetição via Recursão
Quando o meio de abstração para procedimentos consiste quase unicamente em definir, nomear e invocar funções, utilizamos recursão para construir processos iterativos (enquanto que em outras linguagens teríamos laços como while e for).
Recursão Linear
Vejamos o exemplo clássico da função recursiva que calcula o fatorial de um número:
(define (fac n)
(if (= n 0) 1
(* n (fac (- n 1)))))
Como o procedimento fac é unidirecional e não gera efeitos colaterais - uma função pura - podemos computar o processo recursivo através de um modelo simples: basta substituir a definição de fac sempre que encontrarmos uma chamada, trocando também o argumento formal n no esqueleto do procedimento pelo valor passado na evocação.
No exemplo abaixo já foi tomado o branch correto na expressão condicional.
(fac 4)
(* 4 (fac 3))
(* 4 (* 3 (fac 2)))
(* 4 (* 3 (* 2 (fac 1))))
(* 4 (* 3 (* 2 (* 1 (fac 0)))))
(* 4 (* 3 (* 2 (* 1 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
Destaca-se que a computação deve armazenar no contexto do corpo da função fac a associação do valor da variável n.
Isso acontece pois a multiplicação em (* n (fac (- n 1))) é avaliada somente após o retorno da chamada recursiva.
Assim, o processo transcorre tanto em tempo linear (altura da árvore) como em espaço linear (tamanho da pilha de chamadas) em relação à entrada n.
Recursão Iterativa: Tail-Recursion
Um outro exemplo de procedimento recursivo é o algoritmo de Euclides:
(define (gcd a b)
(if (= b 0) a
(gcd b (modulo a b))))
Compare o processo gerado com o anterior.
(gcd 1071 462)
(gcd 462 147)
(gcd 147 21)
(gcd 21 0)
21
Perceba que no caso do gcd, a computação não exige o armazenamento do contexto antes das chamadas recursivas: toda a informação necessária encontra-se nos argumentos da função.
Ambos os procedimentos denotam recursões lineares, ou seja, onde a invocação da função ocorre uma única vez durante a sua avaliação.
Entretanto, enquanto fac toma uma quantidade de memória proporcional ao argumento de entrada, o processo descrito por gcd exige espaço constante e portanto constitui ainda uma iteração linear.
O que diferencia os dois procedimentos é o fato de que a última expressão no corpo de gcd é a invocação de uma função.
Quando isso acontece dizemos que a função possui uma tail-call (chamada de cauda ou terminal) e quando a função evocada é recursiva, dizemos que ela é tail-recursive.
Esse fenômeno possibilida a aplicação da chamada Tail Call Optimization, que elimina a necessidade de ocupar espaço na pilha de execução do programa.
A especificação da linguagem Scheme exige que implementações sejam properly tail-recursive, o que significa que o número de execuções de funções em tail-calls sequenciais é ilimitado.
Recursão Não-Linear e Linearização
Outras classificações de recursão incluem recursão mútua (odd? e even? definidas anteriormente) e recursão múltipla - onde a função é invocada em seu próprio corpo mais de uma vez.
Um exemplo famoso de recursão múltipla binária é a função que calcula os números da sequência de Fibonacci:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
A árvore de chamadas recursivas gerada é bem maior nesse caso:
(fib 4)
(+ (fib 3) (fib 2))
(+ (fib 2) (fib 1) ) (+ (fib 1) (fib 0))
(+ (fib 1) (fib 0)) 1 1 0
1 0
(+ 1 0) 1 (+ 1 0)
(+ 1 1) 1
(+ 2 1)
3
Para estimar a complexidade do processo, observe que o número de vezes em que o caso base da recursão é atingido na execução de (fib n) é exatamente igual ao (n+1)ésimo número de Fibonacci.
Isso significa que esse procedimento é calculado em tempo exponencial proporcional à \( \phi ^ {n+1} \), onde \(\phi\) é o número de ouro.
Um primeiro passo para otimizar a computação é expressar o procedimento em uma iteração linear:
(define (fibo n)
(let iter ((n n) (prev 1) (curr 0))
(if (= n 0) curr
(iter (- n 1) curr (+ prev curr)))))
Compare o tempo de execução de
fibefibopara n = 45.
Aproveite para tentar transformar o procedimentofacem uma iteração linear.
Alguns processos lineares podem ser otimizados ainda mais se explorarmos alguma propriedade que permita realizar, de uma vez, uma certa operação equivalente a múltiplas iterações.
;; recursao O(2^(n-1)) para base 2
;; 2^n = 2 * 2^(n-1) = 2^(n-1) + 2^(n-1)
(define (2^ n)
(cond ((= n 0) 1)
((= n 1) 2)
(else (+ (2^ (- n 1))
(2^ (- n 1))))))
;; recursao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
(if (= n 0) 1 (* b (^ b (- n 1)))))
;; iteracao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
(let iter ((n n) (prod 1))
(if (= n 0) prod
(iter (- n 1) (* b prod)))))
;; recursao O(log2(n))
;; b^n = (b^(n/2))^2
(define (^ b n)
(cond ((= n 0) 1)
((even? n) (square (^ b (halve n))))
(else (* b (^ b (- n 1))))))
;; iteracao O(log2(n))
;; b^n = (b^2)^(n/2)
(define (^ b n)
(define (iter b n prod)
(cond ((= n 0) prod)
((even? n) (iter (square b) (halve n) prod))
(else (iter b (- n 1) (* b prod)))))
(if (< n 0)
(iter (/ 1 b) (- n) 1)
(iter b n 1)))
;; PS:
(define (halve x) (ash x -1))
(define (square x) (* x x))
Tente aplicar a mesma técnica para computar a multiplicação de dois inteiros
benem tempo logarítmico. O procedimento resultante deve se assemelhar ao algoritmo de multiplicação egípcia/russa.
Recursão Linear
Vejamos o exemplo clássico da função recursiva que calcula o fatorial de um número:
(define (fac n)
(if (= n 0) 1
(* n (fac (- n 1)))))
Como o procedimento fac é unidirecional e não gera efeitos colaterais - uma função pura - podemos computar o processo recursivo através de um modelo simples: basta substituir a definição de fac sempre que encontrarmos uma chamada, trocando também o argumento formal n no esqueleto do procedimento pelo valor passado na evocação.
No exemplo abaixo já foi tomado o branch correto na expressão condicional.
(fac 4)
(* 4 (fac 3))
(* 4 (* 3 (fac 2)))
(* 4 (* 3 (* 2 (fac 1))))
(* 4 (* 3 (* 2 (* 1 (fac 0)))))
(* 4 (* 3 (* 2 (* 1 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
Destaca-se que a computação deve armazenar no contexto do corpo da função fac a associação do valor da variável n.
Isso acontece pois a multiplicação em (* n (fac (- n 1))) é avaliada somente após o retorno da chamada recursiva.
Assim, o processo transcorre tanto em tempo linear (altura da árvore) como em espaço linear (tamanho da pilha de chamadas) em relação à entrada n.
Recursão Iterativa: Tail-Recursion
Um outro exemplo de procedimento recursivo é o algoritmo de Euclides:
(define (gcd a b)
(if (= b 0) a
(gcd b (modulo a b))))
Compare o processo gerado com o anterior.
(gcd 1071 462)
(gcd 462 147)
(gcd 147 21)
(gcd 21 0)
21
Perceba que no caso do gcd, a computação não exige o armazenamento do contexto antes das chamadas recursivas: toda a informação necessária encontra-se nos argumentos da função.
Ambos os procedimentos denotam recursões lineares, ou seja, onde a invocação da função ocorre uma única vez durante a sua avaliação.
Entretanto, enquanto fac toma uma quantidade de memória proporcional ao argumento de entrada, o processo descrito por gcd exige espaço constante e portanto constitui ainda uma iteração linear.
O que diferencia os dois procedimentos é o fato de que a última expressão no corpo de gcd é a invocação de uma função.
Quando isso acontece dizemos que a função possui uma tail-call (chamada de cauda ou terminal) e quando a função evocada é recursiva, dizemos que ela é tail-recursive.
Esse fenômeno possibilida a aplicação da chamada Tail Call Optimization, que elimina a necessidade de ocupar espaço na pilha de execução do programa.
A especificação da linguagem Scheme exige que implementações sejam properly tail-recursive, o que significa que o número de execuções de funções em tail-calls sequenciais é ilimitado.
Recursão Não-Linear e Linearização
Outras classificações de recursão incluem recursão mútua (odd? e even? definidas anteriormente) e recursão múltipla - onde a função é invocada em seu próprio corpo mais de uma vez.
Um exemplo famoso de recursão múltipla binária é a função que calcula os números da sequência de Fibonacci:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
A árvore de chamadas recursivas gerada é bem maior nesse caso:
(fib 4)
(+ (fib 3) (fib 2))
(+ (fib 2) (fib 1) ) (+ (fib 1) (fib 0))
(+ (fib 1) (fib 0)) 1 1 0
1 0
(+ 1 0) 1 (+ 1 0)
(+ 1 1) 1
(+ 2 1)
3
Para estimar a complexidade do processo, observe que o número de vezes em que o caso base da recursão é atingido na execução de (fib n) é exatamente igual ao (n+1)ésimo número de Fibonacci.
Isso significa que esse procedimento é calculado em tempo exponencial proporcional à \( \phi ^ {n+1} \), onde \(\phi\) é o número de ouro.
Um primeiro passo para otimizar a computação é expressar o procedimento em uma iteração linear:
(define (fibo n)
(let iter ((n n) (prev 1) (curr 0))
(if (= n 0) curr
(iter (- n 1) curr (+ prev curr)))))
Compare o tempo de execução de
fibefibopara n = 45.
Aproveite para tentar transformar o procedimentofacem uma iteração linear.
Alguns processos lineares podem ser otimizados ainda mais se explorarmos alguma propriedade que permita realizar, de uma vez, uma certa operação equivalente a múltiplas iterações.
;; recursao O(2^(n-1)) para base 2
;; 2^n = 2 * 2^(n-1) = 2^(n-1) + 2^(n-1)
(define (2^ n)
(cond ((= n 0) 1)
((= n 1) 2)
(else (+ (2^ (- n 1))
(2^ (- n 1))))))
;; recursao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
(if (= n 0) 1 (* b (^ b (- n 1)))))
;; iteracao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
(let iter ((n n) (prod 1))
(if (= n 0) prod
(iter (- n 1) (* b prod)))))
;; recursao O(log2(n))
;; b^n = (b^(n/2))^2
(define (^ b n)
(cond ((= n 0) 1)
((even? n) (square (^ b (halve n))))
(else (* b (^ b (- n 1))))))
;; iteracao O(log2(n))
;; b^n = (b^2)^(n/2)
(define (^ b n)
(define (iter b n prod)
(cond ((= n 0) prod)
((even? n) (iter (square b) (halve n) prod))
(else (iter b (- n 1) (* b prod)))))
(if (< n 0)
(iter (/ 1 b) (- n) 1)
(iter b n 1)))
;; PS:
(define (halve x) (ash x -1))
(define (square x) (* x x))
Tente aplicar a mesma técnica para computar a multiplicação de dois inteiros
benem tempo logarítmico. O procedimento resultante deve se assemelhar ao algoritmo de multiplicação egípcia/russa.
Abstração Funcional
Como já foi mencionado, um dos aspectos mais marcantes do paradigma funcional é a abstração através de procedimentos nas chamadas funções de alta ordem. Uma das grandes vantagens destas é que podem encapsular a estrutura de controle do fluxo de execução de forma genérica, reduzindo ao máximo a repetição de código.
A repetição instiga a abstração.
Potenciação Rápida
Por exemplo, ao procurar abstrair a otimização dos procedimentos de exponenciação inteira e da multiplicação egípcia, podemos destacar suas partes comuns. Ao fazê-lo, é possível imaginar que estamos calculando um tipo de "potência" para uma operação básica (onde a potenciação aditiva equivale à multiplicação e a potenciação multiplicativa equivale à exponenciação) em que acumulamos o resultado de consecutivas aplicações dessa operação entre uma base e o resultado acumulado até então. A otimização emerge de alguma propriedade da operação que permite torná-la "mais potente" através de alguma transformação em sua base.
(define (pow power operation basis neutral succession)
(let iter ((b basis) (n power) (acc neutral))
(cond ((= n 0) acc)
((even? n) (iter (succession b) (halve n) acc))
(else (iter b (- n 1) (operation b acc))))))
;; PS:
(define (halve x) (ash x -1))
(define (double x) (ash x 1))
(define (square x) (* x x))
(define (maybe-car lst alt)
(if (null? lst) alt
(car lst)))
O procedimento pow recebe todos os parâmetros necessários para computar a potência, inclusive outros procedimentos que são chamados durante a sua execução.
Entretanto, seria interessante encapsular algumas dessas informações em uma dada operação potencializada, que por conta própria efetuaria a computação para qualquer base e expoente desejados.
Essa tarefa pode ser cumprida por um closure - um tipo de procedimento que "se lembra" do escopo onde foi definido.
Segue abaixo o exemplo de uma função que utiliza pow mas não calcula nada e apenas retorna um closure contendo a operação potencializada.
(define (empower operation neutral . opts-succ)
(let ((succession (maybe-car opts-succ (lambda (x) (operation x x)))))
(lambda (basis power)
(pow power operation basis neutral succession))))
(define times (empower + 0))
(define (mul b n)
(if (< n 0)
(times (- b) (- n))
(times b n)))
(define (^ b n)
(let ((raise (empower * 1)))
(if (< n 0)
(raise (/ 1 b) (- n))
(raise b n))))
(define (fibonacci n)
(let ((fn (cadr (pow ;; n-esima potencia
(abs n)
;; da transformacao
(lambda (coefs fibs)
(let ((p (car coefs)) (q (cadr coefs))
(a (car fibs)) (b (cadr fibs)))
(list (+ (* b q) (* a (+ q p)))
(+ (* b p) (* a q)))))
;; a partir de uma base
'(0 1)
;; acumulada sobre
'(1 0)
;; onde a quadratura da base que
;; regula a potencia da operacao eh
(lambda (coefs)
(let ((p (car coefs)) (q (cadr coefs)))
(list (+ (square q) (square p))
(+ (square q) (* 2 (* p q))))))))))
;; "negafibonacci"
(if (and (< n 0)
(even? n))
(- fn)
fn)))
;; fibonacci matricial
(define (fibona n) ;; n > 0
(define (mul-matrix-2x2 A B)
(let ((a11 (caar A)) (a12 (cadar A))
(a21 (caadr A)) (a22 (cadadr A))
(b11 (caar B)) (b12 (cadar B))
(b21 (caadr B)) (b22 (cadadr B)))
(list (list (+ (* a11 b11) (* a12 b21))
(+ (* a11 b12) (* a12 b22)))
(list (+ (* a21 b11) (* a22 b21))
(+ (* a21 b12) (* a22 b22))))))
(let ((nth-transform (empower mul-matrix-2x2
'((1 0)
(0 1)))))
(caar
(nth-transform '((1 1)
(1 0))
(- n 1)))))
;; forma fechada
(define phi (/ (+ 1 (sqrt 5)) 2)) ;; numero de ouro
(define fi (- 1 phi)) ;; complemento de phi
(define (fibonac n)
(round (/ (- (^ phi n) (^ fi n))
(sqrt 5))))
Compare o tempo de execução de
fibocomfibonaccioufibonapara calcular o milionésimo (n = 1000000) número da sequência. Depois, faça o mesmo parafibonac.
Pontos Fixos
Vejamos agora um procedimento que não define um algoritmo para computar um valor, mas sim um método numérico para aproximar a raíz quadrada de um número:
;; metodo babilonico
(define (sqrt x)
(define (try guess)
(if (good-enough? guess) guess
(try (improve guess))))
(define (improve guess)
(average guess (/ x guess)))
(define (good-enough? guess)
(< (abs (- (square guess) x)) tolerance))
(try 1.0))
;; PS:
(define tolerance 1e-15)
(define (average a b) (/ (+ a b) 2))
(define (square x) (* x x))
Com um procedimento semelhante é possível aproximar uma solução da equação transcedental \( cos(x) = x \).
(define (fixcos)
(define (retry old new)
(if (approx? new old) new
(retry new (cos new))))
(define (approx? a b)
(< (abs (- a b)) tolerance))
(retry 0.0 (cos 0.0)))
(define x (fixcos)) ;; solucao
Um método "manual" para achar esse valor envolve uma calculadora científica e a seguinte sequência de botões:
[1] [=] [COS] [ANS] [=] [=] [=] ...Tendo isso em mente, tente implementar um procedimento
(fixpoint f x)que generalize ambos os métodos apresentados.
Nota-se uma ideia em comum: procuramos um ponto fixo ou ponto invariante k de uma função f(x) tal que \( f(k) = k \). Assim, supondo um valor intermediário c onde \( f(c) \approx k \), temos que \( f(f(...f(c)...)) = f^n(f(c)) = f^n(k) = k \), onde aplicamos f até que não haja mais variação (com uma certa tolerância) no resultado.
(define (fixpoint f x . opts-tol)
(let* ((tolerance (maybe-car opts-tol 1e-9))
(approx? (lambda (a b) (< (abs (- a b)) tolerance))))
(let try ((old x) (new (f x)))
(if (approx? old new) new
(try new (f new))))))
(fixpoint cos 0)
(define (phi-rat tol)
(fixpoint
(lambda (rat)
(let ((fcurr (numerator rat))
(fprev (denominator rat)))
(/ (+ fcurr fprev) fcurr)))
1/1
tol))
(define phi (exact->inexact (phi-rat 1e-15))) ;; => 102334155/63245986 = fib(40)/fib(39)
(define (average-damp f)
(lambda (x) (average (f x) x)))
(define (sqrt x)
(fixpoint (average-damp (lambda (y) (/ x y))) 1.0))
(define (root f x . opts-tol) ;; metodo de Newton
(let* ((dx (maybe-car opts-tol 1e-8))
(df (deriv f dx)))
(fixpoint (lambda (x) (- x (/ (f x) (df x)))) x dx)))
(define (deriv f dx)
(lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))
(define (sqrt x)
(root (lambda (y) (- x (square y))) 1.0))
(define pi (root sin 3))
(define phi (root (lambda (x) (+ (square x) (- x) -1)) 1.0 1e-11))
O Cálculo Lambda de Alonzo Church generaliza a noção de ponto fixo para funções, possibilitando a computação de procedimentos recursivos. Vejamos um exemplo partindo do algoritmo fatorial:
(define (fac n)
(define f fac)
(if (= n 0) 1 (* n (f (- n 1)))))
(define (facto n)
(define f facto)
(define (aux n)
(if (= n 0) 1 (* n (f (- n 1)))))
(aux n))
(define (factor n)
(define (aux f n)
(if (= n 0) 1 (* n (f (- n 1)))))
(aux factor n))
(define (factori n)
(define (aux f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))
((aux factori) n))
(define (factoria n)
(define (aux f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))
(define (rec f)
(lambda (n)
((aux (f f)) n)))
(let ((fact (rec rec)))
(fact n)))
Perceba que a estrutura e o uso do procedimento rec podem ser facilmente generalizados na função de alta ordem ilustrada abaixo.
Esse procedimento também é conhecido como Operador Y.
(define (fix f)
(define (g x)
(lambda (arg)
((f (x x)) arg)))
(g g))
(define fact
(fix (lambda (f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))))
Imagine o processo como uma iteração sobre uma função f que inicialmente não sabe calcular fatoriais: a cada passo f é substituída por uma versão melhorada dela mesma [1].
Podemos representar o estado atual de f como um conjunto de duplas (x,y), onde f associa uma entrada x à saída y.
Fe(x) = {}
F0(x) = { (0,1) }
F1(x) = { (0,1), (1,1) }
F2(x) = { (0,1), (1,1), (2,2) }
F3(x) = { (0,1), (1,1), (2,2), (3,6) }
F4(x) = { (0,1), (1,1), (2,2), (3,6), (4,24) }
F5(x) = { (0,1), (1,1), (2,2), (3,6), (4,24), (5,120) }
...
Fn(x) = fact(x), para x <= n
Na prática, basta aplicar o modelo de substituição para computar a função recursivamente:
(define curryed-fac
(lambda (f)
(lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))))
...
(define fact (fix curryed-fac))
;; substituindo fix(f=curryed-fac)
(define fact
(define (g x)
(lambda (arg) ((curryed-fac (x x)) arg)))
(g g))
;; substituindo g(x=g)
(define fact
(lambda (arg) ((curryed-fac (g g)) arg)))
...
(fact 5)
;; substituindo fact(arg=5)
((curryed-fact (g g)) 5)
;; substituindo g(x=g)
((curryed-fact (lambda (arg) ((curryed-fac (g g)) arg))) 5)
;; perceba que o lambda eh exatamente a definicao de fact
((curryed-fact fact) 5)
;; substituindo curryed-fact(f=fact)
((lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))) 5)
;; substituindo lambda(n=5)
(* 5 (fact 4))
...
Potenciação Rápida
Por exemplo, ao procurar abstrair a otimização dos procedimentos de exponenciação inteira e da multiplicação egípcia, podemos destacar suas partes comuns. Ao fazê-lo, é possível imaginar que estamos calculando um tipo de "potência" para uma operação básica (onde a potenciação aditiva equivale à multiplicação e a potenciação multiplicativa equivale à exponenciação) em que acumulamos o resultado de consecutivas aplicações dessa operação entre uma base e o resultado acumulado até então. A otimização emerge de alguma propriedade da operação que permite torná-la "mais potente" através de alguma transformação em sua base.
(define (pow power operation basis neutral succession)
(let iter ((b basis) (n power) (acc neutral))
(cond ((= n 0) acc)
((even? n) (iter (succession b) (halve n) acc))
(else (iter b (- n 1) (operation b acc))))))
;; PS:
(define (halve x) (ash x -1))
(define (double x) (ash x 1))
(define (square x) (* x x))
(define (maybe-car lst alt)
(if (null? lst) alt
(car lst)))
O procedimento pow recebe todos os parâmetros necessários para computar a potência, inclusive outros procedimentos que são chamados durante a sua execução.
Entretanto, seria interessante encapsular algumas dessas informações em uma dada operação potencializada, que por conta própria efetuaria a computação para qualquer base e expoente desejados.
Essa tarefa pode ser cumprida por um closure - um tipo de procedimento que "se lembra" do escopo onde foi definido.
Segue abaixo o exemplo de uma função que utiliza pow mas não calcula nada e apenas retorna um closure contendo a operação potencializada.
(define (empower operation neutral . opts-succ)
(let ((succession (maybe-car opts-succ (lambda (x) (operation x x)))))
(lambda (basis power)
(pow power operation basis neutral succession))))
(define times (empower + 0))
(define (mul b n)
(if (< n 0)
(times (- b) (- n))
(times b n)))
(define (^ b n)
(let ((raise (empower * 1)))
(if (< n 0)
(raise (/ 1 b) (- n))
(raise b n))))
(define (fibonacci n)
(let ((fn (cadr (pow ;; n-esima potencia
(abs n)
;; da transformacao
(lambda (coefs fibs)
(let ((p (car coefs)) (q (cadr coefs))
(a (car fibs)) (b (cadr fibs)))
(list (+ (* b q) (* a (+ q p)))
(+ (* b p) (* a q)))))
;; a partir de uma base
'(0 1)
;; acumulada sobre
'(1 0)
;; onde a quadratura da base que
;; regula a potencia da operacao eh
(lambda (coefs)
(let ((p (car coefs)) (q (cadr coefs)))
(list (+ (square q) (square p))
(+ (square q) (* 2 (* p q))))))))))
;; "negafibonacci"
(if (and (< n 0)
(even? n))
(- fn)
fn)))
;; fibonacci matricial
(define (fibona n) ;; n > 0
(define (mul-matrix-2x2 A B)
(let ((a11 (caar A)) (a12 (cadar A))
(a21 (caadr A)) (a22 (cadadr A))
(b11 (caar B)) (b12 (cadar B))
(b21 (caadr B)) (b22 (cadadr B)))
(list (list (+ (* a11 b11) (* a12 b21))
(+ (* a11 b12) (* a12 b22)))
(list (+ (* a21 b11) (* a22 b21))
(+ (* a21 b12) (* a22 b22))))))
(let ((nth-transform (empower mul-matrix-2x2
'((1 0)
(0 1)))))
(caar
(nth-transform '((1 1)
(1 0))
(- n 1)))))
;; forma fechada
(define phi (/ (+ 1 (sqrt 5)) 2)) ;; numero de ouro
(define fi (- 1 phi)) ;; complemento de phi
(define (fibonac n)
(round (/ (- (^ phi n) (^ fi n))
(sqrt 5))))
Compare o tempo de execução de
fibocomfibonaccioufibonapara calcular o milionésimo (n = 1000000) número da sequência. Depois, faça o mesmo parafibonac.
Pontos Fixos
Vejamos agora um procedimento que não define um algoritmo para computar um valor, mas sim um método numérico para aproximar a raíz quadrada de um número:
;; metodo babilonico
(define (sqrt x)
(define (try guess)
(if (good-enough? guess) guess
(try (improve guess))))
(define (improve guess)
(average guess (/ x guess)))
(define (good-enough? guess)
(< (abs (- (square guess) x)) tolerance))
(try 1.0))
;; PS:
(define tolerance 1e-15)
(define (average a b) (/ (+ a b) 2))
(define (square x) (* x x))
Com um procedimento semelhante é possível aproximar uma solução da equação transcedental \( cos(x) = x \).
(define (fixcos)
(define (retry old new)
(if (approx? new old) new
(retry new (cos new))))
(define (approx? a b)
(< (abs (- a b)) tolerance))
(retry 0.0 (cos 0.0)))
(define x (fixcos)) ;; solucao
Um método "manual" para achar esse valor envolve uma calculadora científica e a seguinte sequência de botões:
[1] [=] [COS] [ANS] [=] [=] [=] ...Tendo isso em mente, tente implementar um procedimento
(fixpoint f x)que generalize ambos os métodos apresentados.
Nota-se uma ideia em comum: procuramos um ponto fixo ou ponto invariante k de uma função f(x) tal que \( f(k) = k \). Assim, supondo um valor intermediário c onde \( f(c) \approx k \), temos que \( f(f(...f(c)...)) = f^n(f(c)) = f^n(k) = k \), onde aplicamos f até que não haja mais variação (com uma certa tolerância) no resultado.
(define (fixpoint f x . opts-tol)
(let* ((tolerance (maybe-car opts-tol 1e-9))
(approx? (lambda (a b) (< (abs (- a b)) tolerance))))
(let try ((old x) (new (f x)))
(if (approx? old new) new
(try new (f new))))))
(fixpoint cos 0)
(define (phi-rat tol)
(fixpoint
(lambda (rat)
(let ((fcurr (numerator rat))
(fprev (denominator rat)))
(/ (+ fcurr fprev) fcurr)))
1/1
tol))
(define phi (exact->inexact (phi-rat 1e-15))) ;; => 102334155/63245986 = fib(40)/fib(39)
(define (average-damp f)
(lambda (x) (average (f x) x)))
(define (sqrt x)
(fixpoint (average-damp (lambda (y) (/ x y))) 1.0))
(define (root f x . opts-tol) ;; metodo de Newton
(let* ((dx (maybe-car opts-tol 1e-8))
(df (deriv f dx)))
(fixpoint (lambda (x) (- x (/ (f x) (df x)))) x dx)))
(define (deriv f dx)
(lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))
(define (sqrt x)
(root (lambda (y) (- x (square y))) 1.0))
(define pi (root sin 3))
(define phi (root (lambda (x) (+ (square x) (- x) -1)) 1.0 1e-11))
O Cálculo Lambda de Alonzo Church generaliza a noção de ponto fixo para funções, possibilitando a computação de procedimentos recursivos. Vejamos um exemplo partindo do algoritmo fatorial:
(define (fac n)
(define f fac)
(if (= n 0) 1 (* n (f (- n 1)))))
(define (facto n)
(define f facto)
(define (aux n)
(if (= n 0) 1 (* n (f (- n 1)))))
(aux n))
(define (factor n)
(define (aux f n)
(if (= n 0) 1 (* n (f (- n 1)))))
(aux factor n))
(define (factori n)
(define (aux f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))
((aux factori) n))
(define (factoria n)
(define (aux f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))
(define (rec f)
(lambda (n)
((aux (f f)) n)))
(let ((fact (rec rec)))
(fact n)))
Perceba que a estrutura e o uso do procedimento rec podem ser facilmente generalizados na função de alta ordem ilustrada abaixo.
Esse procedimento também é conhecido como Operador Y.
(define (fix f)
(define (g x)
(lambda (arg)
((f (x x)) arg)))
(g g))
(define fact
(fix (lambda (f)
(lambda (n)
(if (= n 0) 1 (* n (f (- n 1))))))))
Imagine o processo como uma iteração sobre uma função f que inicialmente não sabe calcular fatoriais: a cada passo f é substituída por uma versão melhorada dela mesma [1].
Podemos representar o estado atual de f como um conjunto de duplas (x,y), onde f associa uma entrada x à saída y.
Fe(x) = {}
F0(x) = { (0,1) }
F1(x) = { (0,1), (1,1) }
F2(x) = { (0,1), (1,1), (2,2) }
F3(x) = { (0,1), (1,1), (2,2), (3,6) }
F4(x) = { (0,1), (1,1), (2,2), (3,6), (4,24) }
F5(x) = { (0,1), (1,1), (2,2), (3,6), (4,24), (5,120) }
...
Fn(x) = fact(x), para x <= n
Na prática, basta aplicar o modelo de substituição para computar a função recursivamente:
(define curryed-fac
(lambda (f)
(lambda (n) (if (= n 0) 1 (* n (f (- n 1)))))))
...
(define fact (fix curryed-fac))
;; substituindo fix(f=curryed-fac)
(define fact
(define (g x)
(lambda (arg) ((curryed-fac (x x)) arg)))
(g g))
;; substituindo g(x=g)
(define fact
(lambda (arg) ((curryed-fac (g g)) arg)))
...
(fact 5)
;; substituindo fact(arg=5)
((curryed-fact (g g)) 5)
;; substituindo g(x=g)
((curryed-fact (lambda (arg) ((curryed-fac (g g)) arg))) 5)
;; perceba que o lambda eh exatamente a definicao de fact
((curryed-fact fact) 5)
;; substituindo curryed-fact(f=fact)
((lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))) 5)
;; substituindo lambda(n=5)
(* 5 (fact 4))
...
Abstração Metalinguística
A homoiconicidade de Scheme foi brevemente mencionada na seção introdutória. Vejamos agora como utilizar essa característica para facilmente produzir procedimentos. Assim, estaremos utilizando Scheme como uma metalinguagem para Scheme, podendo enfim afirmar que ela é uma linguagem metacircular, ou seja, capaz de falar sobre ela mesma.
Processamento Simbólico
O procedimento eval (complementado por apply) é a principal ferramenta para abstração metalinguística em Scheme.
Para utilizá-lo, basta fornecer uma expressão simbólica válida e um objeto representando o ambiente computacional onde ela será avaliada; o retorno de eval será o valor resultante da interpretação daquela expressão.
(define env (scheme-report-environment 5))
'(+ 1 1) ; => (+ 1 1)
(list '+ 1 1) ; => (+ 1 1)
(+ 1 1) ; => 2
(eval '(+ 1 1) env) ; => 2
(define x 7)
(define y 5)
'(- x y) ; => (- x y)
(list '- x y) ; => (- 7 5)
(- x y) ; => 2
`(- ,x ,y) ; => (- 7 5)
(eval `(- ,x ,y) env) ; => 2
(eval '(- x y) env) ; => Unbound variable: x
Com base nos exemplos anteriores, explique como funcionam as citações parciais com os símbolos
`e,
O método de Horner costuma ser utilizado para calcular o valor de um polinômio de forma a evitar exponenciações; efetua apenas n adições e n multiplicações para um polinômio de grau n.
\[ Pn(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n \] \[ Pn(x) = a_0 + x (a_1 + x (a_2 + x(...a_n...))) \]
Vamos aplicar o método de uma maneira um tanto não-convencional, em um algoritmo que "compila" uma lista de coeficientes e gera um procedimento que calcula o polinômio equivalente na forma de Horner:
(define (horner x pn)
(if (null? (cdr pn))
(car pn)
`(+ ,(car pn) (* ,x ,(horner x (cdr pn))))))
(define (make-polynomial x first-coef . rest-coefs)
(let ((polynomial (horner x (cons first-coef rest-coefs))))
(eval
(list 'lambda (list x) polynomial)
(interaction-environment))))
Diferenciação Analítica
Um outra maneira de utilizar Scheme como metalinguagem circular é na obtenção da derivada analítica de uma função. Nesse caso, não é o procedimento que computa a função que é passado ao gerador (como era o caso na diferenciação numérica utilizada no método de Newton de uma seção anterior), mas sim uma descrição de como seria o código desse procedimento na linguagem Scheme.
(define (differentiate var sexpr)
(cond ((number? sexpr) 0)
((variable? sexpr)
(if (same-variable? sexpr var) 1 0))
((sum? sexpr)
(make-sum (differentiate var (augend sexpr))
(differentiate var (addend sexpr))))
((product? sexpr)
(make-sum
(make-product (multiplier sexpr)
(differentiate var (multiplicand sexpr)))
(make-product (differentiate var (multiplier sexpr))
(multiplicand sexpr))))
(else
(error "unknown expression type -- DERIV" sexpr))))
(define (make-derivative var sexpr)
(let ((deriv (differentiate var sexpr)))
(eval
`(lambda (,var) ,deriv)
(interaction-environment))))
(define (variable? x)
(symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum augend addend)
(cond ((and (number? addend) (number? augend)) (+ augend addend))
((and (number? augend) (= augend 0)) addend)
((and (number? addend) (= addend 0)) augend)
(else (list '+ augend addend))))
(define (sum? x)
(and (list? x) (eq? (car x) '+)))
(define (augend s)
(cadr s))
(define (addend s)
(caddr s))
(define (make-product multiplier multiplicand)
(define (=number? sexpr num)
(and (number? sexpr) (= sexpr num)))
(cond ((or (=number? multiplier 0) (=number? multiplicand 0))
0)
((and (number? multiplier) (number? multiplicand))
(* multiplier multiplicand))
((=number? multiplier 1) multiplicand)
((=number? multiplicand 1) multiplier)
(else (list '* multiplier multiplicand))))
(define (product? x)
(and (list? x) (eq? (car x) '*)))
(define (multiplier p)
(cadr p))
(define (multiplicand p)
(caddr p))
Adicione mais algumas regras de diferenciação no programa acima.
A partir do código dado temos um sistema capaz de gerar procedimentos que computam polinômios arbitrários (de uma variável independente), assim como suas derivadas (incluindo derivadas parciais).
(define coefs '(-1 -1 1))
(define p
(apply horner
(list 'x coefs))) ;; p = x^2 - x - 1
(define f
(apply make-polynomial
(cons 'x coefs))) ;; f(x) = p(x)
(define df
(make-derivative 'x p)) ;; df(x) = p'(x) = 2x - 1
Pense sobre como seria possível expandir esse programa para permitir a geração de polinômios multivariados. Você pode discutir suas ideias na seção de comentários desse site.
Processamento Simbólico
O procedimento eval (complementado por apply) é a principal ferramenta para abstração metalinguística em Scheme.
Para utilizá-lo, basta fornecer uma expressão simbólica válida e um objeto representando o ambiente computacional onde ela será avaliada; o retorno de eval será o valor resultante da interpretação daquela expressão.
(define env (scheme-report-environment 5))
'(+ 1 1) ; => (+ 1 1)
(list '+ 1 1) ; => (+ 1 1)
(+ 1 1) ; => 2
(eval '(+ 1 1) env) ; => 2
(define x 7)
(define y 5)
'(- x y) ; => (- x y)
(list '- x y) ; => (- 7 5)
(- x y) ; => 2
`(- ,x ,y) ; => (- 7 5)
(eval `(- ,x ,y) env) ; => 2
(eval '(- x y) env) ; => Unbound variable: x
Com base nos exemplos anteriores, explique como funcionam as citações parciais com os símbolos
`e,
O método de Horner costuma ser utilizado para calcular o valor de um polinômio de forma a evitar exponenciações; efetua apenas n adições e n multiplicações para um polinômio de grau n.
\[ Pn(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n \] \[ Pn(x) = a_0 + x (a_1 + x (a_2 + x(...a_n...))) \]
Vamos aplicar o método de uma maneira um tanto não-convencional, em um algoritmo que "compila" uma lista de coeficientes e gera um procedimento que calcula o polinômio equivalente na forma de Horner:
(define (horner x pn)
(if (null? (cdr pn))
(car pn)
`(+ ,(car pn) (* ,x ,(horner x (cdr pn))))))
(define (make-polynomial x first-coef . rest-coefs)
(let ((polynomial (horner x (cons first-coef rest-coefs))))
(eval
(list 'lambda (list x) polynomial)
(interaction-environment))))
Diferenciação Analítica
Um outra maneira de utilizar Scheme como metalinguagem circular é na obtenção da derivada analítica de uma função. Nesse caso, não é o procedimento que computa a função que é passado ao gerador (como era o caso na diferenciação numérica utilizada no método de Newton de uma seção anterior), mas sim uma descrição de como seria o código desse procedimento na linguagem Scheme.
(define (differentiate var sexpr)
(cond ((number? sexpr) 0)
((variable? sexpr)
(if (same-variable? sexpr var) 1 0))
((sum? sexpr)
(make-sum (differentiate var (augend sexpr))
(differentiate var (addend sexpr))))
((product? sexpr)
(make-sum
(make-product (multiplier sexpr)
(differentiate var (multiplicand sexpr)))
(make-product (differentiate var (multiplier sexpr))
(multiplicand sexpr))))
(else
(error "unknown expression type -- DERIV" sexpr))))
(define (make-derivative var sexpr)
(let ((deriv (differentiate var sexpr)))
(eval
`(lambda (,var) ,deriv)
(interaction-environment))))
(define (variable? x)
(symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum augend addend)
(cond ((and (number? addend) (number? augend)) (+ augend addend))
((and (number? augend) (= augend 0)) addend)
((and (number? addend) (= addend 0)) augend)
(else (list '+ augend addend))))
(define (sum? x)
(and (list? x) (eq? (car x) '+)))
(define (augend s)
(cadr s))
(define (addend s)
(caddr s))
(define (make-product multiplier multiplicand)
(define (=number? sexpr num)
(and (number? sexpr) (= sexpr num)))
(cond ((or (=number? multiplier 0) (=number? multiplicand 0))
0)
((and (number? multiplier) (number? multiplicand))
(* multiplier multiplicand))
((=number? multiplier 1) multiplicand)
((=number? multiplicand 1) multiplier)
(else (list '* multiplier multiplicand))))
(define (product? x)
(and (list? x) (eq? (car x) '*)))
(define (multiplier p)
(cadr p))
(define (multiplicand p)
(caddr p))
Adicione mais algumas regras de diferenciação no programa acima.
A partir do código dado temos um sistema capaz de gerar procedimentos que computam polinômios arbitrários (de uma variável independente), assim como suas derivadas (incluindo derivadas parciais).
(define coefs '(-1 -1 1))
(define p
(apply horner
(list 'x coefs))) ;; p = x^2 - x - 1
(define f
(apply make-polynomial
(cons 'x coefs))) ;; f(x) = p(x)
(define df
(make-derivative 'x p)) ;; df(x) = p'(x) = 2x - 1
Pense sobre como seria possível expandir esse programa para permitir a geração de polinômios multivariados. Você pode discutir suas ideias na seção de comentários desse site.
Sistemas Computacionais
Até então temos visto programas que operam sobre dados em uma grande composição de funções, onde a saída de um procedimento alimenta a entrada de outro e assim por diante. O fluxo de dados é sempre unidirecional e depende somente do arranjo dos procedimentos e das entradas iniciais, caracterizando programas puramente funcionais. Além disso, o modelo aplicado para computar o resultado de um programa é muito simples, bastando substituir aplicações de procedimentos por sua definição instanciada com os argumentos fornecidos.
Alguns problemas exigem um fluxo de dados diferente. Gostaríamos de introduzir maneiras de alterar o comportamento do programa de formas diferentes dependendo do instante em que o sistema se encontra.
Perceba que, desde o início da oficina até este ponto, jamais fez-se necessário utilizar conceitos como variáveis, atribuições ou estado mutável; é o que faremos agora.
Na medida em que atribuições e ações de mudança são introduzidas na programação, acabamos de nos sujeitar a todos os problemas terríveis que vêm assolando filósofos por milhares de anos. (Sussman, 1968)
Em Scheme, a ferramenta para tal é set! e seus derivados[2]:
(define count 10)
(define (count-down)
(set! count (- count 1))
count)
(define a (cons 1 2))
(define b (cons a a))
(define a (cons 3 2))
b ; = ?
(define a (cons 1 2))
(define b (cons a a))
(set-car! a 3)
b ; = ?
Explique o bug no procedimento
set-fact.
(define (fact n)
(let loop ((i 1) (p 1))
(if (> i n) p
(loop (+ i 1) (* p i)))))
(define (set-fact n)
(let ((i 1) (p 1))
(let loop ()
(if (> i n) p
(begin
(set! i (+ i 1))
(set! p (* p i))
(loop))))))
Memoization com Closures
Se analisarmos a primeira definição do procedimento fib, percebemos que seu principal problema é a computação de resultados que já foram vistos e calculados anteriormente.
Uma forma de contornar esse problema seria fazer com que o processo se lembre desses resultados parciais em um tipo de memória, evitando assim uma computação que pode vir a ser custosa.
Essa técnica de programação dinâmica se chama memoization.
(define (fib n)
(display "Computing Fib of ") (display n) (newline)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))
(define cache (make-table))
(define (memo-fib n)
(let ((hit? (lookup cache n)))
;; hit or miss
(or hit?
(let ((result (fib n)))
(insert! cache n result)
result))))
;; (clear-table! cache)
Scheme adota a convenção de sinalizar procedimentos que geram efeitos colaterais com o sufixo
!.
(define (make-table)
(cons '*table* '()))
(define (lookup table key)
(let ((record (assoc key (cdr table))))
(cond (record => cdr)
(else #f))))
(define (insert! table key value)
(cond ((assoc key (cdr table)) => (lambda (record) (set-cdr! record value)))
(else (set-cdr! table
(cons (cons key value) (cdr table)))))
'ok)
(define (clear-table! table)
(set-cdr! table '())
'ok)
; (define (assoc k a-list)
; (cond ((null? a-list) #f)
; ((equal? k (caar a-list)) (car a-list))
; (else (assoc k (cdr a-list)))))
Tomando a tabela apresentada como exemplo, tente implementar uma pilha (LIFO) com estado mutável. Depois, explique como fazer o mesmo através de programação puramente funcional.
A estrutura de dados implementada é um exemplo de sistema cujos resultados dependem não somente das entradas dadas, mas também do seu estado interno.
Perceba que a única coisa atrelada à sequência de Fibonacci no corpo de memo-fib é a chamada da função fib.
Podemos generalizar essa ideia em uma função de alta ordem que retorna um closure contendo sua própria "memória".
(define (memoize proc)
(let ((cache (make-table)))
(define (delegate . args)
(let ((hit (lookup cache args)))
(or hit
(let ((result (apply proc args)))
(insert! cache args result)
result))))
delegate))
(define memo-fib (memoize
(lambda (n)
(display "Computing Fib of ") (display n) (newline)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(define memo-sqrt (memoize sqrt))
;; <etc>
Apesar de termos melhorado a performance do procedimento antes exponencial para linear, o fizemos em troca de memória da máquina.
Além disso, o sistema de busca de resultados armazenados não é muito eficiente: se na avaliação de (+ (memo-fib (- n 1)) (memo-fib (- n 2))) as entradas na cache estiverem em ordem crescente, seria necessário varrer a lista do início até encontrar a chave (- n 1) e depois recomeçar o processo indo do ínicio da tabela até a entrada (- n 2).
Por causa de situações como estas, implementações sérias de Scheme provêm formas de utilizar estruturas de dados mais eficientes projetadas em outras linguagens. Em Guile, por exemplo, poderíamos utilizar uma hashtable para chegar o mais próximo possível de calcular um dado número de Fibonacci em tempo constante (supondo que já tenha sido pré-computado).
;; GUILE
(define make-table make-hash-table)
(define lookup hash-ref)
(define insert! hash-set!)
Objetos Dinâmicos
No exemplo anterior utilizamos uma lista cujo estado interno era acessado e alterado através de funções auxiliares: os processos são totalmente orientados aos dados manipulados.
A abordagem orientada a objetos em Scheme envolve a utilização de closures que têm acesso ao seu próprio estado e fornecem interfaces para interagir com o ambiente externo.
(define (make-wrapper)
(let ((x 'void))
(define (setter! y)
(set! x y)
'ok)
(define (self method)
(cond ((eq? method 'get) x)
((eq? method 'set) setter!)
(else (error "Undefined operation" method))))
self))
(define (get-value w)
(w 'get))
(define (set-value! w x)
((w 'set) x))
Nesse exemplo, ao passar a mensagem 'set a um objeto criado por make-wrapper o mesmo retorna um procedimento que alterará seu estado interno quando chamado.
Assim, podemos formar sistemas como conjuntos de objetos intercomunicantes. Note que agora o fluxo de dados não têm sentido único, podendo se propagar de qualquer forma em uma rede de objetos conectados arbitrariamente.
Uma aplicação desse tipo de sistema é encontrada em equações algébricas. Por exemplo, a equação \( F = \frac{9}{5} * C + 32 \) determina a relação entre temperaturas das escalas Celsius e Fahrenheit.
(define (c2f x)
(+ (* (/ 9 5) x) 32))
Esse procedimento representa apenas um sentido da igualdade, visto que não permite calcular a temperatura em Celsius dado uma em Fahrenheit. O mesmo se aplicaria se fossêmos representar a relação da lei de Ohm.
\[ I = \frac{V}{R} \Leftrightarrow V = R * I \Leftrightarrow R = \frac{V}{I} \]
A mesma deve valer para quaisquer valores de corrente, resistência e tensão, onde uma alteração de um lado da igualdade será propagada pela equação e causará uma mudança no lado oposto. Portanto, visamos modelar equações algébricas através de um sistema de propagação de restrições. Para isso, vamo inserir em Scheme uma linguagem que trata de conectores e operadores.
(define (make-connector)
(let ((value #f)
(informant #f)
(constraints '()))
(define (set-my-value newval source)
(cond ((not (has-value? self))
(set! value newval)
(set! informant source)
(for-each-except source
inform-about-value
constraints))
((not (= value newval))
(error "Contradiction" (list value newval)))
(else 'ignored)))
(define (forget-my-value retractor)
(if (eq? retractor informant)
(begin
(set! informant #f)
(for-each-except retractor
inform-about-no-value
constraints))
'ignored))
(define (connect new-constraint)
(if (not (memq new-constraint constraints))
(set! constraints
(cons new-constraint constraints)))
(if (has-value? self)
(inform-about-value new-constraint))
'done)
(define (self request)
(cond ((eq? request 'has-value?) informant)
((eq? request 'value) value)
((eq? request 'set-value!) set-my-value)
((eq? request 'forget) forget-my-value)
((eq? request 'connect) connect)
(else (error "Unknown request -- CONNECTOR" request))))
self))
(define (for-each-except exception procedure list)
(let loop ((items list))
(cond ((null? items) 'done)
((eq? (car items) exception) (loop (cdr items)))
(else
(procedure (car items))
(loop (cdr items))))))
(define (has-value? connector)
(if (connector 'has-value?) #t #f))
(define (get-value connector)
(connector 'value))
(define (set-value! connector new-value informant)
((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
((connector 'forget) retractor))
(define (connect connector new-constraint)
((connector 'connect) new-constraint))
(define (inform-about-value constraint)
(constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
(constraint 'I-lost-my-value))
(define (constant value connector)
(define (self request)
(error "Unknown request -- CONSTANT" request))
(connect connector self)
(set-value! connector value self)
self)
(define (adder a1 a2 sum)
(define (process-new-value)
(cond ((and (has-value? a1) (has-value? a2))
(set-value! sum
(+ (get-value a1) (get-value a2))
self))
((and (has-value? a1) (has-value? sum))
(set-value! a2
(- (get-value sum) (get-value a1))
self))
((and (has-value? a2) (has-value? sum))
(set-value! a1
(- (get-value sum) (get-value a2))
self))))
(define (process-forget-value)
(forget-value! sum self)
(forget-value! a1 self)
(forget-value! a2 self)
(process-new-value))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- ADDER" request))))
(connect a1 self)
(connect a2 self)
(connect sum self)
self)
(define (multiplier m1 m2 product)
(define (process-new-value)
(cond ((or (and (has-value? m1) (= (get-value m1) 0))
(and (has-value? m2) (= (get-value m2) 0)))
(set-value! product 0 self))
((and (has-value? m1) (has-value? m2))
(set-value! product
(* (get-value m1) (get-value m2))
self))
((and (has-value? product) (has-value? m1))
(set-value! m2
(/ (get-value product) (get-value m1))
self))
((and (has-value? product) (has-value? m2))
(set-value! m1
(/ (get-value product) (get-value m2))
self))))
(define (process-forget-value)
(forget-value! product self)
(forget-value! m1 self)
(forget-value! m2 self)
(process-new-value))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- MULTIPLIER" request))))
(connect m1 self)
(connect m2 self)
(connect product self)
self)
(define (probe name connector)
(define (print-probe value)
(display name)
(display " = ")
(display value)
(newline))
(define (process-new-value)
(print-probe (get-value connector)))
(define (process-forget-value)
(print-probe "?"))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- PROBE" request))))
(connect connector self)
self)
(define (c+ x y)
(let ((z (make-connector)))
(adder x y z)
z))
(define (c* x y)
(let ((z (make-connector)))
(multiplier x y z)
z))
(define (cv val)
(let ((c (make-connector)))
(constant val c)
c))
(define (c- x y)
(let ((z (make-connector)))
(adder z y x)
z))
(define (c/ x y)
(let ((z (make-connector)))
(multiplier z y x)
z))
Finalmente, para utilizar o sistema:
(define (celsius-fahrenheit-converter x)
(c+ (c* (c/ (cv 9) (cv 5)) x) (cv 32)))
(define c (make-connector))
(probe "Celsius" c)
(define f (celsius-fahrenheit-converter c))
(probe "Fahrenheit" f)
(set-value! c 100 'user)
(define (ohms-law v r) (c/ v r))
(define v (make-connector))
(probe "Voltage" v)
(define r (make-connector))
(probe "Resistance" r)
(define i (ohms-law v r))
(probe "Current" i)
Lazy Streams no Infinito
Tendo observado outros tipos de sistemas, voltemos aos unidirecionais com o intuito de explorar esse paradigma de fluxo de dados: se um programa consiste no encadeamento de funções puras, não importa o momento em que um valor intermediário é computado, desde que quando o resultado final seja requisitado ele se faça presente. Sistemas assim podem se dar ao luxo de serem "preguiçosos", adiando ao máximo o instante em que realizarão uma computação.
Computadores, assim como pessoas, tentam adiar ao máximo possível a ocorrência de eventos desagradáveis. (Tanenbaum, 2011)
A seguir implementaremos um tipo de lista que segue essa ideia de lazy evaluation. Os principais procedimentos pelos quais essas "listas preguiçosas" serão manipuladas estão descritos abaixo.
(define (stream-ref seq n)
(cond ((empty? seq) #f)
((<= n 0) (head seq))
(else (stream-ref (tail seq) (- n 1)))))
(define (stream-for-each proc seq)
(if (not (empty? seq))
(begin
(proc (head seq))
(stream-for-each proc (tail seq)))))
(define (stream-map proc seq)
(if (empty? seq) empty-stream
(stream (proc (head seq))
(stream-map proc (tail seq)))))
(define (stream-filter pred seq)
(cond ((empty? seq) empty-stream)
((pred (head seq)) (stream (head seq)
(stream-filter pred (tail seq))))
(else (stream-filter pred (tail seq)))))
(define (stream-foldr op acc seq) ;; aka reduce
(if (empty? seq) acc
(op (head seq)
(stream-foldr op acc (tail seq)))))
(define (stream-zip-with op sa sb)
(stream (op (head sa) (head sb))
(stream-zip-with op (tail sa) (tail sb))))
Construa um procedimento
(stream-range lo hi)que gera uma stream com todos os inteiros entreloehi.
As primitivas que constroem e acessam as streams são responsáveis por diferenciá-las de listas normais.
(define (memo-proc proc)
(let ((run? #f)
(cached '()))
(lambda ()
(if run? cached
(let ((result (proc)))
(begin
(set! run? #t)
(set! cached result)
result))))))
;; delay
(define-syntax lazy
(syntax-rules ()
((lazy expr)
(memo-proc (lambda () expr)))))
;; force
(define (thunk p) (p))
(define-syntax stream
(syntax-rules ()
((stream x y)
(cons x (lazy y)))))
(define (head s) (car s))
(define (tail s) (thunk (cdr s)))
(define (empty? s) (null? s))
(define empty-stream '())
As macros stream e lazy definem transformações que ocorrem no código antes da sua interpretação.
Assim, uma stream consiste num par onde a computação do segundo elemento foi postergada, deixando apenas uma promessa de que estará lá quando for necessária.
Se um elemento de uma stream nunca for acessado, a promessa não precisa ser cumprida e nenhum processamento é efetuado.
Note que esse mecanismo permite representar sequências infinitas: todos os elementos estarão presentes, mas só existirão de fato quando alguém requisitar.
(define (ints-from n)
(stream n (ints-from (+ n 1))))
(define (sieve seq) ;; crivo de Eratostenes
(define (divisible? a b)
(= 0 (remainder a b)))
(if (empty? seq) seq
(stream (head seq)
(sieve (stream-filter (lambda (x) (not (divisible? x (head seq))))
(tail seq))))))
(define primes (sieve (ints-from 2)))
Podemos afirmar, portanto, que primes é a stream de todos os números primos.
O esquema pode ser aplicado também para séries infinitas, por exemplo na série de Taylor-Maclaurin para o arco tangente
\[ \arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + ... \]
(define (arctan-series x n)
(stream (/ (expt x n) n)
(stream-map - (arctan-series x (+ n 2)))))
Podemos substituir x=1 para poder encontrar a fórmula de Madhava para aproximar o valor de \( \pi \):
\[ \arctan 1 = \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + ... \]
Tente gerar uma stream contendo as aproximações de pi pela fórmula anterior, onde cada n-ésimo elemento equivale à soma parcial de n termos da série.
(define (partial-sums s)
(stream-zip-with + s (stream 0 (partial-sums s))))
(define pi-approximations
(stream-map (lambda (pi/4) (* 4 pi/4))
(partial-sums (arctan-series 1.0 1))))
Por fim, vamos obter a sequência de Fibonacci completa em uma stream infinita.
(define (fibonacci-sequence prev curr)
(stream prev
(fibonacci-sequence curr (+ prev curr))))
(define fibs (fibonacci-sequence 0 1))
Reflita sobre a possibilidade de computar elementos de uma lazy stream paralelamente com técnicas de programação concorrente. Você pode discutir suas ideias na seção de comentários desse site.
Memoization com Closures
Se analisarmos a primeira definição do procedimento fib, percebemos que seu principal problema é a computação de resultados que já foram vistos e calculados anteriormente.
Uma forma de contornar esse problema seria fazer com que o processo se lembre desses resultados parciais em um tipo de memória, evitando assim uma computação que pode vir a ser custosa.
Essa técnica de programação dinâmica se chama memoization.
(define (fib n)
(display "Computing Fib of ") (display n) (newline)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))
(define cache (make-table))
(define (memo-fib n)
(let ((hit? (lookup cache n)))
;; hit or miss
(or hit?
(let ((result (fib n)))
(insert! cache n result)
result))))
;; (clear-table! cache)
Scheme adota a convenção de sinalizar procedimentos que geram efeitos colaterais com o sufixo
!.
(define (make-table)
(cons '*table* '()))
(define (lookup table key)
(let ((record (assoc key (cdr table))))
(cond (record => cdr)
(else #f))))
(define (insert! table key value)
(cond ((assoc key (cdr table)) => (lambda (record) (set-cdr! record value)))
(else (set-cdr! table
(cons (cons key value) (cdr table)))))
'ok)
(define (clear-table! table)
(set-cdr! table '())
'ok)
; (define (assoc k a-list)
; (cond ((null? a-list) #f)
; ((equal? k (caar a-list)) (car a-list))
; (else (assoc k (cdr a-list)))))
Tomando a tabela apresentada como exemplo, tente implementar uma pilha (LIFO) com estado mutável. Depois, explique como fazer o mesmo através de programação puramente funcional.
A estrutura de dados implementada é um exemplo de sistema cujos resultados dependem não somente das entradas dadas, mas também do seu estado interno.
Perceba que a única coisa atrelada à sequência de Fibonacci no corpo de memo-fib é a chamada da função fib.
Podemos generalizar essa ideia em uma função de alta ordem que retorna um closure contendo sua própria "memória".
(define (memoize proc)
(let ((cache (make-table)))
(define (delegate . args)
(let ((hit (lookup cache args)))
(or hit
(let ((result (apply proc args)))
(insert! cache args result)
result))))
delegate))
(define memo-fib (memoize
(lambda (n)
(display "Computing Fib of ") (display n) (newline)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
(define memo-sqrt (memoize sqrt))
;; <etc>
Apesar de termos melhorado a performance do procedimento antes exponencial para linear, o fizemos em troca de memória da máquina.
Além disso, o sistema de busca de resultados armazenados não é muito eficiente: se na avaliação de (+ (memo-fib (- n 1)) (memo-fib (- n 2))) as entradas na cache estiverem em ordem crescente, seria necessário varrer a lista do início até encontrar a chave (- n 1) e depois recomeçar o processo indo do ínicio da tabela até a entrada (- n 2).
Por causa de situações como estas, implementações sérias de Scheme provêm formas de utilizar estruturas de dados mais eficientes projetadas em outras linguagens. Em Guile, por exemplo, poderíamos utilizar uma hashtable para chegar o mais próximo possível de calcular um dado número de Fibonacci em tempo constante (supondo que já tenha sido pré-computado).
;; GUILE
(define make-table make-hash-table)
(define lookup hash-ref)
(define insert! hash-set!)
Objetos Dinâmicos
No exemplo anterior utilizamos uma lista cujo estado interno era acessado e alterado através de funções auxiliares: os processos são totalmente orientados aos dados manipulados.
A abordagem orientada a objetos em Scheme envolve a utilização de closures que têm acesso ao seu próprio estado e fornecem interfaces para interagir com o ambiente externo.
(define (make-wrapper)
(let ((x 'void))
(define (setter! y)
(set! x y)
'ok)
(define (self method)
(cond ((eq? method 'get) x)
((eq? method 'set) setter!)
(else (error "Undefined operation" method))))
self))
(define (get-value w)
(w 'get))
(define (set-value! w x)
((w 'set) x))
Nesse exemplo, ao passar a mensagem 'set a um objeto criado por make-wrapper o mesmo retorna um procedimento que alterará seu estado interno quando chamado.
Assim, podemos formar sistemas como conjuntos de objetos intercomunicantes. Note que agora o fluxo de dados não têm sentido único, podendo se propagar de qualquer forma em uma rede de objetos conectados arbitrariamente.
Uma aplicação desse tipo de sistema é encontrada em equações algébricas. Por exemplo, a equação \( F = \frac{9}{5} * C + 32 \) determina a relação entre temperaturas das escalas Celsius e Fahrenheit.
(define (c2f x)
(+ (* (/ 9 5) x) 32))
Esse procedimento representa apenas um sentido da igualdade, visto que não permite calcular a temperatura em Celsius dado uma em Fahrenheit. O mesmo se aplicaria se fossêmos representar a relação da lei de Ohm.
\[ I = \frac{V}{R} \Leftrightarrow V = R * I \Leftrightarrow R = \frac{V}{I} \]
A mesma deve valer para quaisquer valores de corrente, resistência e tensão, onde uma alteração de um lado da igualdade será propagada pela equação e causará uma mudança no lado oposto. Portanto, visamos modelar equações algébricas através de um sistema de propagação de restrições. Para isso, vamo inserir em Scheme uma linguagem que trata de conectores e operadores.
(define (make-connector)
(let ((value #f)
(informant #f)
(constraints '()))
(define (set-my-value newval source)
(cond ((not (has-value? self))
(set! value newval)
(set! informant source)
(for-each-except source
inform-about-value
constraints))
((not (= value newval))
(error "Contradiction" (list value newval)))
(else 'ignored)))
(define (forget-my-value retractor)
(if (eq? retractor informant)
(begin
(set! informant #f)
(for-each-except retractor
inform-about-no-value
constraints))
'ignored))
(define (connect new-constraint)
(if (not (memq new-constraint constraints))
(set! constraints
(cons new-constraint constraints)))
(if (has-value? self)
(inform-about-value new-constraint))
'done)
(define (self request)
(cond ((eq? request 'has-value?) informant)
((eq? request 'value) value)
((eq? request 'set-value!) set-my-value)
((eq? request 'forget) forget-my-value)
((eq? request 'connect) connect)
(else (error "Unknown request -- CONNECTOR" request))))
self))
(define (for-each-except exception procedure list)
(let loop ((items list))
(cond ((null? items) 'done)
((eq? (car items) exception) (loop (cdr items)))
(else
(procedure (car items))
(loop (cdr items))))))
(define (has-value? connector)
(if (connector 'has-value?) #t #f))
(define (get-value connector)
(connector 'value))
(define (set-value! connector new-value informant)
((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
((connector 'forget) retractor))
(define (connect connector new-constraint)
((connector 'connect) new-constraint))
(define (inform-about-value constraint)
(constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
(constraint 'I-lost-my-value))
(define (constant value connector)
(define (self request)
(error "Unknown request -- CONSTANT" request))
(connect connector self)
(set-value! connector value self)
self)
(define (adder a1 a2 sum)
(define (process-new-value)
(cond ((and (has-value? a1) (has-value? a2))
(set-value! sum
(+ (get-value a1) (get-value a2))
self))
((and (has-value? a1) (has-value? sum))
(set-value! a2
(- (get-value sum) (get-value a1))
self))
((and (has-value? a2) (has-value? sum))
(set-value! a1
(- (get-value sum) (get-value a2))
self))))
(define (process-forget-value)
(forget-value! sum self)
(forget-value! a1 self)
(forget-value! a2 self)
(process-new-value))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- ADDER" request))))
(connect a1 self)
(connect a2 self)
(connect sum self)
self)
(define (multiplier m1 m2 product)
(define (process-new-value)
(cond ((or (and (has-value? m1) (= (get-value m1) 0))
(and (has-value? m2) (= (get-value m2) 0)))
(set-value! product 0 self))
((and (has-value? m1) (has-value? m2))
(set-value! product
(* (get-value m1) (get-value m2))
self))
((and (has-value? product) (has-value? m1))
(set-value! m2
(/ (get-value product) (get-value m1))
self))
((and (has-value? product) (has-value? m2))
(set-value! m1
(/ (get-value product) (get-value m2))
self))))
(define (process-forget-value)
(forget-value! product self)
(forget-value! m1 self)
(forget-value! m2 self)
(process-new-value))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- MULTIPLIER" request))))
(connect m1 self)
(connect m2 self)
(connect product self)
self)
(define (probe name connector)
(define (print-probe value)
(display name)
(display " = ")
(display value)
(newline))
(define (process-new-value)
(print-probe (get-value connector)))
(define (process-forget-value)
(print-probe "?"))
(define (self request)
(cond ((eq? request 'I-have-a-value) (process-new-value))
((eq? request 'I-lost-my-value) (process-forget-value))
(else (error "Unknown request -- PROBE" request))))
(connect connector self)
self)
(define (c+ x y)
(let ((z (make-connector)))
(adder x y z)
z))
(define (c* x y)
(let ((z (make-connector)))
(multiplier x y z)
z))
(define (cv val)
(let ((c (make-connector)))
(constant val c)
c))
(define (c- x y)
(let ((z (make-connector)))
(adder z y x)
z))
(define (c/ x y)
(let ((z (make-connector)))
(multiplier z y x)
z))
Finalmente, para utilizar o sistema:
(define (celsius-fahrenheit-converter x)
(c+ (c* (c/ (cv 9) (cv 5)) x) (cv 32)))
(define c (make-connector))
(probe "Celsius" c)
(define f (celsius-fahrenheit-converter c))
(probe "Fahrenheit" f)
(set-value! c 100 'user)
(define (ohms-law v r) (c/ v r))
(define v (make-connector))
(probe "Voltage" v)
(define r (make-connector))
(probe "Resistance" r)
(define i (ohms-law v r))
(probe "Current" i)
Lazy Streams no Infinito
Tendo observado outros tipos de sistemas, voltemos aos unidirecionais com o intuito de explorar esse paradigma de fluxo de dados: se um programa consiste no encadeamento de funções puras, não importa o momento em que um valor intermediário é computado, desde que quando o resultado final seja requisitado ele se faça presente. Sistemas assim podem se dar ao luxo de serem "preguiçosos", adiando ao máximo o instante em que realizarão uma computação.
Computadores, assim como pessoas, tentam adiar ao máximo possível a ocorrência de eventos desagradáveis. (Tanenbaum, 2011)
A seguir implementaremos um tipo de lista que segue essa ideia de lazy evaluation. Os principais procedimentos pelos quais essas "listas preguiçosas" serão manipuladas estão descritos abaixo.
(define (stream-ref seq n)
(cond ((empty? seq) #f)
((<= n 0) (head seq))
(else (stream-ref (tail seq) (- n 1)))))
(define (stream-for-each proc seq)
(if (not (empty? seq))
(begin
(proc (head seq))
(stream-for-each proc (tail seq)))))
(define (stream-map proc seq)
(if (empty? seq) empty-stream
(stream (proc (head seq))
(stream-map proc (tail seq)))))
(define (stream-filter pred seq)
(cond ((empty? seq) empty-stream)
((pred (head seq)) (stream (head seq)
(stream-filter pred (tail seq))))
(else (stream-filter pred (tail seq)))))
(define (stream-foldr op acc seq) ;; aka reduce
(if (empty? seq) acc
(op (head seq)
(stream-foldr op acc (tail seq)))))
(define (stream-zip-with op sa sb)
(stream (op (head sa) (head sb))
(stream-zip-with op (tail sa) (tail sb))))
Construa um procedimento
(stream-range lo hi)que gera uma stream com todos os inteiros entreloehi.
As primitivas que constroem e acessam as streams são responsáveis por diferenciá-las de listas normais.
(define (memo-proc proc)
(let ((run? #f)
(cached '()))
(lambda ()
(if run? cached
(let ((result (proc)))
(begin
(set! run? #t)
(set! cached result)
result))))))
;; delay
(define-syntax lazy
(syntax-rules ()
((lazy expr)
(memo-proc (lambda () expr)))))
;; force
(define (thunk p) (p))
(define-syntax stream
(syntax-rules ()
((stream x y)
(cons x (lazy y)))))
(define (head s) (car s))
(define (tail s) (thunk (cdr s)))
(define (empty? s) (null? s))
(define empty-stream '())
As macros stream e lazy definem transformações que ocorrem no código antes da sua interpretação.
Assim, uma stream consiste num par onde a computação do segundo elemento foi postergada, deixando apenas uma promessa de que estará lá quando for necessária.
Se um elemento de uma stream nunca for acessado, a promessa não precisa ser cumprida e nenhum processamento é efetuado.
Note que esse mecanismo permite representar sequências infinitas: todos os elementos estarão presentes, mas só existirão de fato quando alguém requisitar.
(define (ints-from n)
(stream n (ints-from (+ n 1))))
(define (sieve seq) ;; crivo de Eratostenes
(define (divisible? a b)
(= 0 (remainder a b)))
(if (empty? seq) seq
(stream (head seq)
(sieve (stream-filter (lambda (x) (not (divisible? x (head seq))))
(tail seq))))))
(define primes (sieve (ints-from 2)))
Podemos afirmar, portanto, que primes é a stream de todos os números primos.
O esquema pode ser aplicado também para séries infinitas, por exemplo na série de Taylor-Maclaurin para o arco tangente
\[ \arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + ... \]
(define (arctan-series x n)
(stream (/ (expt x n) n)
(stream-map - (arctan-series x (+ n 2)))))
Podemos substituir x=1 para poder encontrar a fórmula de Madhava para aproximar o valor de \( \pi \):
\[ \arctan 1 = \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + ... \]
Tente gerar uma stream contendo as aproximações de pi pela fórmula anterior, onde cada n-ésimo elemento equivale à soma parcial de n termos da série.
(define (partial-sums s)
(stream-zip-with + s (stream 0 (partial-sums s))))
(define pi-approximations
(stream-map (lambda (pi/4) (* 4 pi/4))
(partial-sums (arctan-series 1.0 1))))
Por fim, vamos obter a sequência de Fibonacci completa em uma stream infinita.
(define (fibonacci-sequence prev curr)
(stream prev
(fibonacci-sequence curr (+ prev curr))))
(define fibs (fibonacci-sequence 0 1))
Reflita sobre a possibilidade de computar elementos de uma lazy stream paralelamente com técnicas de programação concorrente. Você pode discutir suas ideias na seção de comentários desse site.
Esse é o fim
Ou talvez seja apenas um início.
Os interessados podem continuar seu aprendizado com os tópicos não abordados nessa oficina mas que também são ferramentas muito úteis presentes em Scheme. Para citar algumas:
- Interpretadores Metacirculares
- Macros Higiênicas
- Computação Não-Determinística
- First-class Continuations
- Threads e Concorrência
Agradecimentos
Scripts Anexos
Os trechos de código utilizados na oficina podem ser encontrados no meu repositório do GitHub.
Discussão e Comentários
Podem utilizar o espaço abaixo para tirar dúvidas e discutir implementações, assim como apontar quaisquer erros no conteúdo.
Sinta-se também à vontade para deixar sua opinião sobre a oficina, elogiando ou criticando de forma construtiva.