Ridgun

The language itself: a compiler that compiles itself, the stable project tool, the specification and the book

04-pattern-matching-e-guardas.md208 lines · 10.5 KBRaw

1	# Capítulo 04: Adeus ao `if/else`, adeus ao `while` (Pattern Matching, Guardas e TCO)
2
3	Quando conta a alguém que em Ridgun não existe a palavra-chave `if`, nem `else`, nem `switch`, nem `for`, nem `while`, a pessoa costuma olhar para si como se lhe tivesse dito que vai construir uma casa sem martelo nem pregos:
4
5	> "Como assim não há `if` nem `while`? E como raio tomo uma decisão ou percorro um milhão de dados?"
6
7	Pois acontece que `if/else` e `while` são ferramentas bastante toscas herdadas de como funcionavam os saltos (`GOTO`) nos anos 50. Em Ridgun substituímo-los por três peças que encaixam como uma luva:
8	1. *Pattern Matching* (quando decide segundo a forma ou valor exato do dado).
9	2. Guardas booleanas `\|` (quando decide segundo uma condição ou intervalo).
10	3. Recursão de cauda com TCO (que o compilador converte por baixo num ciclo `loop` nativo ultrarrápido).
11
12	Vamos vê-las em ação.
13
14	---
15
16	## 4.1. Pattern Matching: Quando o argumento já lhe dá a resposta
17
18	No capítulo anterior já vimos uma amostra. Em vez de receber uma variável genérica `x` e abrir dentro da função cinco `if (x == ...)`, em Ridgun coloca os casos diretamente à porta de entrada da função:
19
20	```ridgun
21	codigo http Int => String
22	codigo http 200 = "OK: Tudo correu sobre rodas"
23	codigo http 301 = "Movido permanentemente"
24	codigo http 404 = "Não encontrado (já procuraste debaixo do sofá?)"
25	codigo http 500 = "Fogo no servidor"
26	codigo http n = "Código desconhecido: {n}"
27	```
28
29	O Ridgun testa as linhas de cima para baixo:
30	- Se entrar `404`, salta direto para a terceira linha.
31	- Se entrar `418`, nenhuma das quatro primeiras linhas coincide, pelo que cai na última (`n`), que apanha qualquer inteiro e lhe dá o nome `n` para que o possa imprimir.
32	- E se no último caso nem sequer lhe importar que número era? Põe um sublinhado `_` (wildcard) e esquece: `codigo http _ = "Outro código"`.
33
34	---
35
36	## 4.2. Guardas booleanas (`\|`): O seu bisturi para intervalos, variáveis condicionais e árvores de decisão
37
38	"Certo, o pattern matching é ótimo quando procuro o `200` ou o `404`. Mas o que faço se quiser verificar se `nota >= 5` ou se `idade > 18 and idade < 65`? Não vou escrever 47 linhas com todos os números de 18 a 65!"
39
40	Claro que não! Para isso existem as guardas (`\|`).
41
42	Quando o resultado depende de uma desigualdade ou de uma combinação lógica, depois do `=` da função (ou de qualquer variável local) abre uma escada de barras verticais `\|`:
43
44	```ridgun
45	classificar Int => String
46	classificar nota =
47	\| nota < 0 = "Nota impossível (pontos negativos?)"
48	\| nota < 5 = "Reprovado"
49	\| nota < 7 = "Suficiente"
50	\| nota < 9 = "Bom"
51	\| nota <= 10 = "Excelente"
52	\| otherwise = "Ultrapassaste a escala"
53	```
54
55	Repare bem:
56	- O sinal `=` do cabeçalho (`classificar nota =`) alinha-se debaixo de `=>` tal como em qualquer outra função.
57	- Por baixo lê-se de cima para baixo tal como uma tabela de preços: cada linha `\| condicao = resultado` é verificada por ordem. Assim que uma dá `True`, devolve esse resultado e acabou.
58	- No final põe `\| otherwise = ...`, que significa literalmente "em qualquer outro caso" (a sua rede de segurança para que nunca fique um caminho sem retorno).
59
60	### Lógica booleana em minúsculas claras (`and`, `or`, `xor`, `not`)
61	Já reparou que muitas linguagens usam `\|` para bits, `\|\|` para booleanos, `!` para negar... e quando lê uma condição complexa parece que um gato caminhou sobre o teclado (`if (!a && (b \|\| c))`)?
62
63	Em Ridgun, como `\|` já é o símbolo sagrado das guardas e dos tipos algébricos, e `\|\|` é o operador de paralelismo, os operadores booleanos escrevem-se com palavras claras em minúsculas:
64
65	- `and`: cumprem-se as duas coisas com avaliação em curto-circuito (`idade >= 18 and tem_carta`).
66	- `or`: cumpre-se pelo menos uma com avaliação em curto-circuito (`dia == "sabado" or dia == "domingo"`).
67	- `xor`: cumpre-se uma ou outra, mas não as duas ao mesmo tempo.
68	- `not`: inverte o booleano (`not (esta vazio texto)`).
69	- `<`, `>`, `<=`, `>=`: comparam tanto números (`Int`, `Float`) como cadeias `String` em ordem lexicográfica UTF-8 (`"alfa" < "beta"`).
70
71	Veja como fica limpo o clássico problema dos anos bissextos:
72
73	```ridgun
74	e bissexto Int => Bool
75	e bissexto a =
76	\| (a % 400) == 0 = True
77	\| (a % 4) == 0 and (a % 100) != 0 = True
78	\| otherwise = False
79	```
80
81	Zero símbolos crípticos. Alguém que não conhece Ridgun lê isto e entende à primeira.
82
83	### Variáveis locais condicionais (`x =` + `\|`)
84	Como em Ridgun todo o `=` segue a mesma regra, também pode usar `\|` para atribuir uma variável local sem ter de criar uma função auxiliar à parte:
85
86	```ridgun
87	preco bilhete Int Bool => Int
88	preco bilhete base e_familia_numerosa =
89	desconto =
90	\| e_familia_numerosa = 20
91	\| base > 100 = 10
92	\| otherwise = 0
93	base - (base * desconto / 100)
94	```
95
96	### Árvores de decisão aninhadas e o delimitador compacto `\|.`
97	"E se dentro de um ramo `\| cond =` ou `\| otherwise =` eu quiser abrir outra subárvore de guardas `\|` de 3 ou 4 níveis de profundidade e depois voltar a um nível superior?"
98
99	Pode aninhar `\|` dentro de `\|` tantos níveis quantos quiser. E quando um bloco `\|` aninhado termina mas por baixo continuam mais ramos de um nível pai (ou mais instruções do bloco), coloca `\|.` no final da sua última linha (`\| otherwise = valor \|.`) para indicar sem qualquer ambiguidade que essa subárvore fecha e volta ao nível anterior:
100
101	```ridgun
102	encaminhar pedido Int Int Bool Bool Int Int => Int
103	encaminhar pedido metodo papel assinado e_admin tamanho_kb limitado =
104	\| metodo == 0 =
105	\| tamanho_kb == 0 = 204
106	\| otherwise = 200 \|.
107	\| metodo == 1 =
108	\| not assinado = 401
109	\| otherwise =
110	-- Nível 2: pedido POST assinado
111	\| limitado > 0 =
112	-- Nível 3: controlo de rate-limit
113	\| e_admin =
114	-- Nível 4: exceção para administradores
115	\| tamanho_kb > 10000 = 413
116	\| otherwise = 202 \|.
117	\| otherwise = 429 \|.
118	\| tamanho_kb > 1000 =
119	-- Nível 3: voltámos do Nível 4 graças a `\|.`
120	\| papel >= 2 and e_admin = 201
121	\| otherwise = 413 \|.
122	\| otherwise = 201 \|.
123	\| otherwise = 405
124	```
125
126	Repare como é limpo:
127	- Numa árvore simples de 1 nível (ou no final de toda a função) nunca é preciso pôr `\|.` (seria ruído desnecessário).
128	- Só escreve `\|.` ao fechar um ramo aninhado quando por baixo continua um ramo de um nível superior.
129
130	### Blocos de várias linhas dentro de uma guarda (`\| cond =` + bloco indentado)
131	Tal como depois do `=` de uma função normal pode abrir um bloco indentado de várias linhas, depois do `=` de qualquer guarda `\| cond =` ou `\| otherwise =` também pode fazer uma quebra de linha e abrir um bloco sequencial:
132
133	```ridgun
134	ajustar janela Int Int => Int
135	ajustar janela idx limite =
136	\| idx >= limite =
137	topo = limite - 1
138	escalado = topo * 2
139	escalado + 10
140	\| otherwise =
141	seguinte = idx + 1
142	seguinte * 2
143	```
144
145	Cada ramo da guarda tem o seu próprio bloco local limpo e a sua última linha é o valor que esse ramo devolve.
146
147	---
148
149	## 4.3. "Sem `while`? E não vai rebentar a pilha se eu percorrer um ficheiro grande?"
150
151	Falemos do elefante na sala.
152
153	Se vem de Python, Java ou JavaScript, ensinaram-lhe desde pequenino que "a recursão é elegante no quadro da universidade, mas no mundo real transborda a pilha (`StackOverflowError`) às 1.000 voltas; use um ciclo `while`".
154
155	Isso é verdade em linguagens que não otimizam as chamadas de cauda. Mas numa linguagem funcional de sistemas como o Ridgun, uma recursão de cauda É um ciclo `while` disfarçado de função pura.
156
157	### Que diferença há entre uma recursão normal e uma recursão de cauda?
158	Repare nestas duas funções que contam para trás desde `n` até `0` somando os números:
159
160	```ridgun
161	-- Versão A: Recursão NORMAL (deixa trabalho pendente para o regresso)
162	somar lento Int => Int
163	somar lento 0 = 0
164	somar lento n = n + (somar lento (n - 1))
165
166	-- Versão B: Recursão DE CAUDA (leva a conta em dia em `acumulado`)
167	somar rapido loop Int Int => Int
168	somar rapido loop 0 acumulado = acumulado
169	somar rapido loop n acumulado = somar rapido loop (n - 1) (acumulado + n)
170	```
171
172	- Na Versão A, antes de poder somar `n + ...`, a função tem de esperar que termine `somar lento (n - 1)`. Isso obriga o computador a guardar `n` na pilha em cada passo.
173	- Na Versão B, a chamada a `somar rapido loop` é a última coisa que acontece na linha. Não fica nada pendente atrás dela. Já lhe passa a soma atualizada em `acumulado + n`.
174
175	### O truque de magia do `ridgunc` (TCO: Tail-Call Optimization)
176	Quando o `ridgunc` compila `somar rapido loop`, vê que a função se chama a si mesma no final da cláusula e diz:
177
178	> "Para que vou criar um novo registo de pilha se o atual já não serve para nada? Vou sobrescrever `n` com `n - 1`, sobrescrever `acumulado` com `acumulado + n` e saltar para o princípio com um `loop { ... continue; }` nativo."
179
180	Resultado:
181	1. Pode chamar `somar rapido loop 100_000_000 0` (cem milhões de voltas) e gastará exatamente 0 bytes extra de pilha.
182	2. É tão rápido quanto um ciclo `while` escrito à mão em Rust ou C, mas sem ter tido de declarar uma única variável mutável no seu código Ridgun.
183
184	---
185
186	## 4.4. O padrão mestre que usará em todo o programa Ridgun
187
188	Sempre que noutra linguagem pensaria "vou fazer um ciclo `while` com um índice `i` e um acumulador", em Ridgun escreve um par de funções como este (a função principal limpa e a sua ajudante `_loop` de cauda):
189
190	```ridgun
191	procurar caracter loop String Int Int Int => Int
192	procurar caracter loop texto pos fim procurado =
193	\| pos >= fim = -1
194	\| (str char at texto pos) == procurado = pos
195	\| otherwise = procurar caracter loop texto (pos + 1) fim procurado
196
197	procurar caracter String Int => Int
198	procurar caracter texto procurado = procurar caracter loop texto 0 (str len texto) procurado
199	```
200
201	Repare nas três guardas de `procurar caracter loop`:
202	1. Cheguei ao fim (`pos >= fim`)? Devolvo `-1` (fim do ciclo).
203	2. Encontrei o carácter em `pos`? Devolvo `pos` (fim do ciclo).
204	3. Não é este? Passo ao seguinte (`pos + 1`) com uma chamada de cauda (que o compilador converte em `continue;`).
205
206	Limpo, impossível de ter bugs de variáveis globais atropeladas e rápido como um raio.
207
208	No Capítulo 05 vamos pôr as mãos na massa com as coleções de dados: listas, tuplas, funções que aceitam infinitos argumentos (`...`) e as máscaras de sequências ao estilo J/APL.