This repository has been archived by the owner on Aug 10, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
/
10.01-recursion
170 lines (146 loc) · 5.5 KB
/
10.01-recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
VARIÁVEIS
==========
Para criarmos variáveis, TIRAMOS as opções de box/setbox/unbox de
dentro do parser. Nosso id's viram var's.
LET
====
Como poderíamos criar um 'let' na nossa linguagem?
O objetivo do let é:
1) Criar um novo símbolo;
2) Salvar o valor neste símbolo;
3) Executar alguma ação com este símbolo associado
a este valor.
Em Racket, temos a analogia:
((λ(x) corpo) val) ↔ (let [x val] corpo)
Na nossa linguagem, podemos ter o açúcar:
[letS (s : symbol) (v : value) (b : body)]
No Desugar, transformaríamos para o λ:
[letS (id val expr) (appC (lamC if (desugar expr)) (desugar val))]
O interpretador é o mesmo (pois o let é açúcar), mas precisamos
colocar algo no parser:
[(def) (letS (s-exp->symbol (second sl))
(parse (third sl)) (parse (fourth sl))
)]
Usando isso, podemos ter, por exemplo:
> (parse '(def b b b))
(letS 'b (varS 'b) (varS 'b))
> (desugar (parse '(def b b b)))
(appC (lamC 'b (varC 'b)) (varC 'b))
> (interp (desugar (parse '(def b b b))))
ERROR: lookup: b não foi encontrado
RECURSÃO
=========
- Dados → referenciar { outro elemento do mesmo tipo
{ a si mesmo
- Controle → função recursiva
.-----. |
| | | .---. .---. .---. .---.
|--.--| | | *-:-->| *-:-->| *-:-->| *-:--.
| | | | '---' '---' '---' '---' |
'--'--' | ^----------------------------'
/ \ |
/ \ |
.-----. .-----. | .---.
| | | | | | *-:-.
|--.--| |--.--| | '---' |
| | | | | | | ^---'
'--'--' '--'--' |
Para criarmos AUTORREFERÊNCIAS, precisaremos de dois passos:
1) Criar uma associação (variável/box) não definida;
2) Depois, tricar o valor para a localização da própria variável.
As duas 'dependências' necessárias são:
1) Criar MUTAÇÕES na variável;
2) Usar SEQUENCIAMENTO de ações.
Esse procedimento nos permitiria CORRIGIR o exemplo do let da
seção anterior. Se pudermos PEGAR o próprio 'endereço' da
variável b (guardando em b a chave da tabela de símbolos store).
Um outro problema de autorreferência seria:
> (interpS
'(def fat 1729 (func n (if n (* n (call fat (-n 1))) 1)))
)
ERROR: lookup: fat não foi encontrado
Poderíamos tentar resolver usando um SEQUENCIAMENTO. Com ele,
podemos alterar o STORE de modo que,
> (interpS '(def fat 1729 ; define fat com um valor dummy
(seq
; Troca 'fat' pelo valor que ela deveria ter: o
; corpo da função fatorial. Não temos o problema,
; pois fat já foi definido no início.
(:= fat (func n (if n (* n (call fat (-n 1))) 1)))
; Agora, com o corpo definido, e sabendo que nós
; já tínhamos o símbolo definido, a recursão funciona.
(call (fat 10))
)))
O resultado desta mudança é que acabaremos definindo 'n' várias
vezes, pois cada vez que entramos numa nova chamada, definimos
um novo número 'n'. Se tivéssemos otimização, dado que esta é
uma recursão de cauda, não precisaríamos criar estes environments
várias vezes: apenas reutilizaríamos o já existente - e ele se
tornaria um laço.
Essa solução que encontramos usa, de certa maneira, uma recursão
implícita. Usamos a alteração de ESTADO para criar a recursão.
Haveria alguma maneira de criarmos a recursão SEM STORE.
; Um Fibonacci tradicional seria este.
; O que devemos colocar no passo para criar a recursão?
(λ (n)
(if (zero? n)
1
(* n (? (- n 1)))
))
; Precisamos usar um "duplicador", chamado de GERADOR Y.
; Ele consiste de uma fábrica de funções, que pode ser
; recriada pelo corpo da função recursiva.
(
.- Este primeiro λ serve APENAS para dar o "chute
............' inicial" e começar o processo recursivo.
(λ (m) (m m)) <-----. Parâmetro desta closure
(λ (f) ---' <-----. O que é gerado por esta closure:
>> (λ (n) ---' nosso fibonacci
>> (if (zero? n)
>> 1
>> (* n ((f f) (- n 1)))
>> ))
)
)
; Para não precisarmos mais colocar o '(f f)' no meio da função,
; e abstrairmos o código do fatorial de dentro do gerador Y,
; podemos chamar o (f f) de 'g'.
;
(
(λ (m) (m m)) <-----. Parâmetro desta closure
(λ (f) ---'
>> (λ (g)
>> (λ (n)
>> (if (zero? n)
>> 1
>> (* n (g (- n 1)))
>> )))
(f f)
)
)
; Agora, podemos simplesmente chamar nossa função recursiva de
; de "p". Então, para usar o fatorial, bastará colocá-lo como
; ARGUMENTO da nossa primeira função:
(
(λ (p)
(
(λ (m) (m m))
(λ (f) (p (f f) ))
)
)
(λ (g) (λ (n) (if (zero? n) 1 (* n (g (- n 1)))
)
; A última versão, porém, entra em LOOP INFINITO, pois nossa
; função '(f f)' é calculada na hora em que a lista é interpretada.
; Assim, já na nossa primeira execução, entraríamos em loop.
; Para POSTERGAR a execução de (f f), criamos um dummy λ, que chama
; a função (f f) com parâmetro 'a'. Mas isso não faz nada.
(
(λ (p)
(
(λ (m) (m m))
(λ (f) (p (λ (a) ((f f) a))))
)
)
(λ (g) (λ (n) (if (zero? n) 1 (* n (g (- n 1)))
)