Intro Ocaml

Introducao à Programacao Funcional
em OCaml
M ario Pereira and Sim ao Melo de Sousa
RELEASE - RELiablE And SEcure computation Group
LIACC & Departamento de Informatica
Universidade da Beira Interior
Documento de Trabalho. Versao de 26 de Fevereiro de 2012
Conte udo
1 Introducao 4
1.1 Heranca ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Compilacao, Execucao e Bibliotecas 7
2.1 Execuc ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Compilac ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Acesso ` as bibliotecas . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Ambiente de Programacao . . . . . . . . . . . . . . . . . . . . 10
3 N ucleo funcional 11
3.1 Linguagens fortemente tipicadas e Polimorsmo . . . . . . . 12
3.1.1 Convers oes explcitas . . . . . . . . . . . . . . . . . . . 13
3.2 Vari aveis e func oes . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Valores, funcoes e tipos de base . . . . . . . . . . . . . . . . . 15
3.3.1 Valores Numericos . . . . . . . . . . . . . . . . . . . . 15
3.3.2 Caracteres e strings . . . . . . . . . . . . . . . . . . . . 17
3.3.3 Booleanos . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.4 Tipo unidade . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.5 Produto Cartesiano, tuplos . . . . . . . . . . . . . . . . 18
1
3.3.6 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Estruturas Condicionais . . . . . . . . . . . . . . . . . . . . . 20
3.5 Declarac ao de valores . . . . . . . . . . . . . . . . . . . . . . . 20
3.5.1 Declara coes globais . . . . . . . . . . . . . . . . . . . . 21
3.5.2 Declara coes locais . . . . . . . . . . . . . . . . . . . . . 22
3.6 Express oes funcionais e func oes . . . . . . . . . . . . . . . . . 22
3.6.1 Declara cao de base . . . . . . . . . . . . . . . . . . . . 22
3.6.2 Sintaxe alternativa para func oes n- arias . . . . . . . . . 25
3.6.3 Declara coes de valores funcionais . . . . . . . . . . . . 25
3.6.4 Declara cao de func oes locais . . . . . . . . . . . . . . . 26
3.6.5 Func oes de ordem superior . . . . . . . . . . . . . . . . 26
3.6.6 Fecho . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6.7 Ordem Superior e Polimorsmo . . . . . . . . . . . . . 33
3.7 Uma digress ao sobre a noc ao de igualdade . . . . . . . . . . . 34
3.8 Declarac ao de tipos e ltragem de motivos . . . . . . . . . . . 35
3.8.1 Pattern matching (ltragem) . . . . . . . . . . . . . . . 35
3.8.2 Declara cao de tipos . . . . . . . . . . . . . . . . . . . 37
3.8.3 Registos . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.8.4 Tipos soma . . . . . . . . . . . . . . . . . . . . . . . . 39
3.9 Excepc oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.9.1 Denic ao . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.9.2 Lan car uma excep cao . . . . . . . . . . . . . . . . . . . 41
3.9.3 Recuperar excepc oes . . . . . . . . . . . . . . . . . . . 41
4 Programacao imperativa 42
4.1 Estruturas de Dados modic aveis . . . . . . . . . . . . . . . . 42
4.1.1 Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.2 Strings como vectores . . . . . . . . . . . . . . . . . . . 44
4.1.3 Registos e campos modic aveis . . . . . . . . . . . . . 44
4.1.4 Referencias . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 Entradas e sadas . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.1 Abertura de cheiro . . . . . . . . . . . . . . . . . . . 47
4.2.2 Fecho de cheiro . . . . . . . . . . . . . . . . . . . . . 47
4.2.3 Leitura e Escrita . . . . . . . . . . . . . . . . . . . . . 47
4.3 Estruturas de controlo . . . . . . . . . . . . . . . . . . . . . . 48
4.3.1 Sequencia . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.2 Blocos de programa . . . . . . . . . . . . . . . . . . . . 49
4.3.3 Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2
4.3.4 Tipagem, aplicacao parcial e fechos . . . . . . . . . . . 50
5 Avaliacao Ansiosa, Avaliacao preguicosa e estruturas de da-
dos innitas 53
5.1 Avaliac ao em OCaml . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 Avaliac ao Preguicosa em OCaml . . . . . . . . . . . . . . . . 56
5.3 O M odulo Lazy . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.4 Streams: uxos ou listas innitas em OCaml . . . . . . . . . 63
5.4.1 Construc ao . . . . . . . . . . . . . . . . . . . . . . . . 64
5.4.2 Consumo e percurso de uxos . . . . . . . . . . . . . . 65
5.4.3 Filtragem destrutiva de uxos . . . . . . . . . . . . . . 66
6 M odulos 69
6.1 Ficheiros e modulos . . . . . . . . . . . . . . . . . . . . . . . . 70
6.2 Encapsulamento . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2.1 Compilac ao separada . . . . . . . . . . . . . . . . . . . 73
6.2.2 Linguagem de m odulos . . . . . . . . . . . . . . . . . . 74
6.3 Functores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.3.1 Aplicac oes . . . . . . . . . . . . . . . . . . . . . . . . . 80
7 Persistencia 81
7.1 Estruturas de dados imut aveis . . . . . . . . . . . . . . . . . . 81
7.2 Interesses pr aticos da persistencia . . . . . . . . . . . . . . . . 86
7.3 Interface e persistencia . . . . . . . . . . . . . . . . . . . . . . 90
8 Exemplos 94
8.1 Produto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . 94
8.2 Brincadeiras a volta da sequencia de Fibonacci . . . . . . . . . 95
8.3 Exercitar a estrategia dividir para conquistar . . . . . . . . . . 100
8.4 Polin omios, e o Metodo de Horner . . . . . . . . . . . . . . . . 101
8.5 Matrizes e cheiros . . . . . . . . . . . . . . . . . . . . . . . . 102
8.6 Memoiza cao automatica . . . . . . . . . . . . . . . . . . . . . 107
8.7 Tipo Soma e Induc ao Estrutural . . . . . . . . . . . . . . . . . 110
8.8 Execuc ao de automatos . . . . . . . . . . . . . . . . . . . . . . 119
8.9 Parsing com uxos e computac ao simb olica . . . . . . . . . . . 124
3
Aviso Previo
A redaccao deste documento baseou-se fortemente na bibliograa indi-
cada. Parece-nos entao obvio que a leitura e a aprendizagem directa
pelas obras originais e recomendada, e mesmo essencial ` a compreens ao
profunda das noc oes aqui apresentadas;
O portugues n ao e a lngua materna do principal autor e o presente
documento encontra-se em fase de elabora cao pelo que se agradece e
ate se incentiva qualquer sugestao ou correcc ao.
Bibliograa
Referencias principais usadas neste documento e das quais se aconselha
leitura s ao [4, 6, 2] (Com a autorizac ao concedida gentilmente por Jean-
Christophe Filliatre e por Xavier Leroy).
As referencias secundaria utilizadas (por consultar igualmente) s ao [7, 3, 9,
8, 5, 10]
1 Introducao
A linguagem LISP, criada no M.I.T. nos anos 1960, e o patriarca das lin-
guagens funcionais. Muitas variantes desta linguagem apareceram, como
o ELISP que e a linguagem de programac ao associada ao editor de texto
Emacs. Outro exemplo e a linguagem Scheme que est a, por exemplo, na
base do sistema de processamento de imagens GIMP.
CAML e o acr onimo para Categorical Abstract Machine Language que
sublinha as ligacoes que esta linguagem alimenta com o calculo e a teoria
das categorias. A CAM (de Categorical Abstract Machine) e uma maquina
abstracta (diz-se tambem maquina virtual) capaz de denir e de executar
funcoes. A outra liac ao do nome OCaml e a linguagem ML (de Meta Lan-
guage). As linguagens da famlia ML foram desenvolvidas no incio dos anos
1980. Na origem esteve a linguagem desenvolvida por Robert Milner em 1978.
Da descendencia destacamos os tres dialectos principais que s ao o SML-NJ
(New-Jersey, USA) , Moscow-ML (R ussia) e o OCaml (Franca). Um ramo
dissidente desta descendencia mas importante e a famlia das linguagens
4
qualicadas de preguicosas
1
como o Haskell, que s ao capazes naturalmente
de trabalhar com tipos de dados de tamanho innito.
O primeiro compilador Caml produzindo c odigo para a m aquina CAM
foi escrito em 1984. Actualmente o compilador OCaml produz c odigo para
uma m aquina virtual diferente e mais eciente, chamada ZINC e escrita pelo
Xavier Leroy. Desde ent ao a linguagem OCaml tem conseguido superar um
desao que poucas linguagens conseguiram: aliar uma boa fundamentac ao
te orica, sinonima de robustez e abilidade, ` a ec acia do c odigo produzido.
Um argumento, subjectivo, e por exemplo o comparativo de linguagens de-
senvolvido em [1] em que a linguagem Caml ca imediatamente atras da
linguagem C. Se a linguagem OCaml e uma linguagem popular nos meios
academicos
2
e no mundo da investigac ao, e tambem uma linguagem utili-
zada em ambiente industrial. Citemos por exemplo o Ocaml Consortium
3
que testemunha tal interesse pelos industriais, a ind ustria das comunica coes
(como a France Telecom), a industria aeron autica (Dassault,...), a nanca
(Janes Street Capital, NY) ou ate mesmo Microsoft (n ao so para a sua divi-
s ao Research, mas tambem desenvolvimento).
1.1 Heranca ML
A linguagem OCaml, como todas as linguagens herdeiras de ML, possu as
caractersticas seguintes:
As fun coes s ao valores deprimeira classe: estas podem ser argumentos
de outras func oes ou mesmo o resultado de um c alculo. Neste sentido
diz-se da linguagem OCaml que e uma linguagem de func oes de ordem
superior.
A linguagem e fortemente tipicada: a qualquer valor esta associado um
tipo. A vericac ao sistem atica e rigorosa da compatibilidade entre os
tipos dos par ametros formais e os tipos dos par ametros efectivos e uma
das caractersticas da linguagem. Tal permite eliminar grande parte
dos erros introduzidos por distracc ao e contribu para uma execucao
segura, avel e robusta.
1
Pregui cosas, no bom sentido: so executam certas tarefas quando estritamente neces-
sarias.
2
O Caml-light e por exemplo uma variante Caml particularmente adaptada à aprendi-
zagem da programacao.
3
http://caml.inria.fr/consortium/.
5
A tipagem e inferida automaticamente: o sistema de tipo de OCaml e
particularmente expressivo e o problema da inferencia de tipo continua
no entanto decidvel. Isto e, o programador nao tem de declarar o tipo
das express oes que dene.

E uma opc ao. O sistema de tipos subjacente
` a linguagem OCaml e sucientemente poderoso para permitir que se
deduza esta informac ao a partir da sintaxe da express ao considerada.
A tipagem e est atica: todos os tipos podem ser (e s ao) deduzidos na fase
da compilac ao. Desta forma tal vericacao n ao e necess aria durante a
execu cao tornando essa ultima mais r apida.
A tipagem e polimorca: o algoritmo de inferencia de tipo do OCaml
sabe reconhecer tipos polim orcos. Voltaremos a este assunto seccao
precedente, mas podemos desde j a realcar que tal caracterstica per-
mite, de forma elegante, uma programac ao modular e generica.
Mecanismos de denicao e de gest ao de excepc oes: permite uma pro-
gramac ao capaz de interferir com uxo de controlo (nome generico para
denir o decorrer de uma execuc ao).
Mecanismos de ltragem de motivos (concordancia de padr ao): este
mecanismo possibilita uma programacao, muito conveniente, baseada
na analise dos casos possveis.
A mem oria e gerida por um recuperador automatico de memoria (Gar-
bage Colector ou GC, em ingles): n ao h a gest ao explcita da mem oria.
O GC trata de tudo automaticamente e de forma eciente.
Alem dessas caractersticas, OCaml:
disp oe de mecanismos proprios à programac ao imperativa;
disp oe de uma camada objecto;
permite uma integracao completa de programas C com programas
OCaml;
suporta a programac ao concorrente, distribuda e paralela;
disp oe de uma base contributiva importante, diversicada e completa
(como atestam o sub-site Hump do site ocial ou ainda o agregador
6
de projectos Caml ocamlforge, etc. ). Estes pontos de entrada permi-
tem, por exemplo, ter acesso a bibliotecas ricas que complementam a
biblioteca standard.
2 Compilacao, Execucao e Bibliotecas
Um programa OCaml apresenta-se como uma sequencia de express oes
OCaml eventualmente colocadas num cheiro .ml e/ou .mli (um cheiro
.mli agrupa a interface do cheiro .ml ao qual est a relacionado, tal como
um cheiro .h e o header relacionado com um cheiro .c na linguagem
C).
Podemos executar programas OCaml de tres formas diferentes. Para
cada uma delas ser ao precisos procedimentos diferentes.
2.1 Execucao
Interpretacao pelo toplevel : O ciclo de interaccao (toplevel na termi-
nologia inglesa) interpreta frase por frase (ou express ao OCaml por
express ao) o programa OCaml. Cada frase termina por dois pontos
e virgulas: ;;. Para cada express ao interpretada o toplevel devolve
o tipo e o valor da expressao em caso de sucesso. O toplevel e um
programa chamado ocaml. Os exemplos deste documento foram todos
escrito e executados utilizando o toplevel.
Para carregar uma biblioteca (OCaml ou pessoal) e preciso dis-
por do cheiro .cmo da biblioteca. O comando no toplevel e
#load ch . cmo;; . Pode-se tambem optar por uma inclus ao textual
(equivalente a um copy-past do cheiro para o toplevel). Neste caso o
comando e #use ch . ml ;;
Dica: preferir o comando ledit ocaml ou rlwrap ocaml ao comando
ocaml se os programas ledit ou rlwrap estiverem instalado na
m aquina hospede. Estes programas permitem guardar um historico
dos comandos/expressoes OCaml introduzidos, ` a semelhanca do
doskey do DOS.
7
Execucao pela maquina virtual: a semelhanca do Java, os programas
OCaml podem ser compilados para serem executados por uma ma-
quina virtual. Temos assim um programa portavel e seguro (a m a-
quina virtual tem mecanismos de seguranca embebidos) que pode ser
executado, sem qualquer modicac ao, numa grande variedade de arqui-
tecturas. Para obter tal programa, a compilac ao ter a de ser efectuada
utilizando o compilador para bytecode. A maquina virtual OCaml
chama-se ocamlrun. A execuc ao dum programa bytecode, digamos
prog, a partir dum terminal pode assim ser realizada alternativamente
de duas formas:
1. ocamlrun prog
2. ./prog
No caso do programa bytecode ter a maquina virtual embebida (gra cas
` a op cao -custom do compilador), basta utilizar a segunda alternativa
para a execuc ao do programa;
Execucao pela maquina hospeda: o utilizador pode querer privilegiar a
eciencia em rela cao a portabilidade do programa denido. Neste caso
preferir a utilizar o compilador nativo ocamlopt para produzir c odigo
m aquina bem mais rapido do que o codigo interpretado. Nesta con-
gurac ao:
o programa produzido e especco ` a m aquina em que foi compilado
mas ganha-se um factor de rapidez à volta de 10;
o c odigo produzido e c odigo m aquina e e executado directamente
pela m aquina hospeda (como qualquer programa execut avel com-
pilado pelo compilador gcc por exemplo).
2.2 Compilacao
Existem dois compiladores (e duas variantes optimizadas de cada um deles,
suxadas por .opt).
ocamlc: este compilador gera codigo intermedio adequado para a m aquina
virtual OCaml;
ocamlopt: este compilador gera c odigo m aquina adequado para ser execu-
tado directamente pela maquina hospeda.
8
Ambos aceitam as op coes habituais dos compiladores da GNU (como o
gcc).
Destacamos as opc oes seguintes:
-i: gera para a sada standard toda a informac ao de tipos contida no
cheiro compilado.

Util para obter um cheiro .mli por defeito;
-c compila mas nao faz a edic ao das ligac oes (n ao faz o linking).
Aquando da utilizac ao do compilador ocamlc, permite gerar o .cmo
correspondente;
-custom permite a criacao de executaveis aut onomos. Aquando da uti-
lizac ao do compilador ocamlc, permite incorporar uma m aquina virtual
ao c odigo produzido. Com um executavel deste tipo n ao e assim neces-
s aria a presenca duma m aquina virtual na m aquina hospeda para que
o programa possa ser executado..
-o nome : indica o nome desejado para o execut avel;
-I caminho : acrescenta o caminho na lista das pastas onde procurar
bibliotecas.
-annot: produz informacao suplementar sobre tipos, tail-calls, bin-
dings, etc... para o cheiro <filename>.annot.

Util para quem utiliza
o editor emacs.
-a: compila para o formato biblioteca.
-pp <command>: activa o preprocessamento <command> via camlp4 ou
camlp5.
-unsafe: gera c odigo sem vericac ao dos acessos a strings e vectores.
2.3 Acesso às bibliotecas
As func oes, valores das bibliotecas (tambem designados de modulos em
OCaml) sao acessveis de duas formas: directamente (se as bibliotecas fo-
ram previamente carregadas por um open ou use) ou por nome qualicados.
Por exemplo: seja f uma func ao da biblioteca B. O acesso directo a f e f, o
acesso qualicado e B.f. Repare que o acesso directo e condicionado ao facto
de n ao haver ambiguidades no nome f. Imagine que duas bibliotecas abertas
9
fornecem uma func ao f, ter a neste caso de qualicar o nome f para ter a
certeza de chamar a func ao realmente desejada. Para ser preciso, quando
dois modulos abertos disponibilizam o mesmo valor f, ent ao, pelas regras ha-
bituais de visibilidade, a invocac ao de f designa o valor f do ultimo modulo
aberto.
Os comandos para o carregamento de bibliotecas s ao, se tomarmos o
exemplo da biblioteca chamada bib:
#use "bib.cmo" no toplevel;
open Bib no cheiro .ml destinado para a compila cao
No caso dos nomes qualicados, o nome da biblioteca comeca sempre por
uma mai uscula.
2.4 Ambiente de Programacao
O ambiente classico para a programac ao OCaml e o editor emacs ou o editor
xemacs equipados com o modo tuareg.
Existe igualmente modos OCaml para os IDEs tradicionais. Citemos por
exemplo o ODT e o OCAIDE para o IDE eclipse.
De uma forma geral, os editores de texto populares como o editor crim-
son ou o notepad++ disponibilizam mecanismos satisfat orios de colorac ao de
sintaxe e de compila cao em linha de comando.
A instalac ao de uma distribuic ao OCaml de base em ambiente Win-
dows necessita de um compilador de assembly tradicionalmente fornecido
por plataformas como o MinGW ou CygWin. Um tutorial de instala cao
neste sistema operativo pode ser visualizado aqui.
O utilizador curioso podera tambem experimentar o site
http://try.ocamlpro.com/ que apresenta um ambiente de execuc ao OCaml
online completo.
A distribuic ao mnima de OCaml encontra-se no site http://caml.inria.fr.
Existe no entanto duas plataformas (complementares e relacionadas) que
permitem gerir a instalacao e a actualizac ao de uma quantidade apreci avel
de ferramentas, aplicac oes, bibliotecas, etc.. ligados à linguagem OCaml.
Essas sao o GODI e o Oasis.
Para a compilac ao de projectos OCaml existam duas formas alternativas
muito praticas disponveis: primeiro, um Makele generico para OCaml e,
segundo, uma ferramenta de compilacao de projecto Ocamlbuild.
10
A biblioteca standard de OCaml e, para o uso geral, relativamente com-
pleta, mas de facto de dimens ao reduzida quando comparada com API de
outras linguagens populares. V arios complementos, que visam colmatar esta
situac ao, existem. Citemos por exemplo o OCaml batteries ou a Janes Street
core Suite.
De uma forma geral, existem varios reposit orios web que agrupam pro-
jectos, informac oes, documentac ao, recursos, apontadores, etc... ligados ao
mundo OCaml. Citemos o Caml Hump, ou ainda Forge OCaml .
3 N ucleo funcional
Comecemos por alguns aspectos fundamentais proprios à linguagem OCaml,
que ser ao em grande parte justicados nesta seccao:
OCaml e uma linguagem funcional fortemente tipicada.
Um programa OCaml e uma sequencia de express oes ou de declarac oes
Uma express ao OCaml reduz-se a um valor
Qualquer express ao OCaml tem um e um s o tipo bem determinado
OCaml e uma linguagem funcional fortemente tipicada. Como tal,
trata-se duma linguagem onde as express oes (nas quais inclumos expressoes
funcionais) tem um papel central. As construcoes essenciais da linguagem
s ao assim mecanismos de denic ao e aplica cao de func oes.
O resultado do calculo duma expressao e um valor da linguagem e a
execu cao dum programa e o c alculo de todas as express oes constituindo o
programa.
E importante realcar de que se trata duma linguagem em que valor e

funcao pertencem à mesma classe. Nao h a diferencas de tratamento, por
exemplo, entre um inteiro e uma fun cao. Ambos s ao valores para OCaml.
Poderao assim ser calculados ou analisados por uma func ao. Isto e, poder ao
ser da mesma forma par ametro ou ate mesmo devolvidos como resultado
de uma func ao. Da a denominac ao de fun coes de ordem superior para as
funcoes de tais linguagens funcionais.
Outro pendente da segunda armac ao (Um programa OCaml e uma
sequencia de expressoes) e a inexistencia de distincao entre instrucoes e ex-
press oes presente tradicionalmente nas linguagens imperativas. O que enten-
demos ser instruc oes no paradigma imperativo s ao express oes como quaisquer
11
outras, devolvem valores e podem ser usadas como sub-express oes.

E assim
possvel escrever express oes como
(1 + (if x>4 then 7 else 9))
Admitindo que x seja o valor 5, esta express ao tem por valor 7 e tipo
inteiro (int em OCaml, como veremos mais adiante).
Apresentaremos os prot otipos de func oes descritas neste documento utili-
zando a notac ao OCaml para as interfaces. De forma resumida, as interfaces
OCaml, agrupadas nos cheiros .mli s ao os equivalente OCaml dos cheiros
headers (os cheiros .h) da linguagem C.
val nome_da_fun c~ao_ou_valor : assinatura
3.1 Linguagens fortemente tipicadas e Polimorsmo
Antes de passar aos tipos de base e ` as construc oes de tipo que OCaml
fornece, e importante voltar a frisar que OCaml e uma linguagem fortemente
tipicada com tipos polimorcos.
Que signica tal arma cao? A primeira parte indica que qualquer va-
lor OCaml tem necessariamente um tipo e que o compilador/toplevel de
OCaml sancionar a qualquer falha a essa regra (com um erro na compilac ao
ou na interpretac ao). Uma propriedade interessante do OCaml e a sua ca-
pacidade em adivinhar (o termo exacto e inferir) o tipo de cada valor. N ao
necessitamos ent ao fornecer explicitamente em cada valor o tipo ao qual ele
pertence. OCaml pode faze-lo por nos. Deveremos no entanto ter o cuidado
em denir funcoes (mais genericamente express oes, valores) que respeitam
essa classicacao em tipo. OCaml rejeitara qualquer denicao, por exem-
plo, em que e dado um real a uma funcao esperando um inteiro, mesmo se
esse real e 1.0!! Realcemos que, embora pareca falta de exibilidade, esta
caracterstica, comum a muitas linguagens modernas que se preocupam com
programac ao avel e robusta, e considerada importante e desejavel.
A segunda parte, o polimorsmo, diz respeito a capacidade de uma funcao
operar correctamente para elementos de varios tipos que tem uma estrutura
em comum. Por exemplo, vectores de inteiros e vectores de reais s ao sequen-
cias de acesso directo que s o diferem nos valores que essas sequencias contem.
De facto, esta informac ao pouco importa ` a func ao comprimento que devolve
o comprimento dum vector. O c alculo deste valor pode perfeitamente se
abstrair do tipo dos elementos. Podemos neste caso considerar o tipo dos va-
lores do vector como uma inc ognita, uma variavel (de tipo). A nossa func ao
comprimento tem assim varias formas, conforme o tipo de vector ao qual e
12
aplicada. Pode adquirir a forma ou ainda especializar-se numa func ao que
calcula comprimentos de vectores de inteiros, ou ainda pode adquirir a forma,
de uma func ao que calcula comprimentos de vectores de caracteres.
Uma linguagem que permite tal abstracc ao e chamada polimorca
(etimologia: que tem varias formas). OCaml e uma tal linguagem.
O polimorsmo surge nos tipos OCaml da seguinte forma: um tipo e
polimorco quando a sua denicao contempla variaveis, chamadas variaveis
de tipo, que podem ser, quando conveniente, instanciadas por outros tipos.
As vari aveis de tipo s ao assinaladas por identicadores prexados por uma
plica. Por exemplo a T denota o tipo OCaml T polimorco numa vari avel
a.
Assumindo, por enquanto, a existencia do tipo int dos inteiros e do tipo
char dos caracteres, exemplos de inst ancias sao int T, char T, (int T) T
ou mesmo (a T) T. Nestes casos a foi instanciado (tomou o valor) res-
pectivamente por int, char, (int T) e (a T). Se imaginarmos que T seja
um tipo pensado para ser contentor de elementos de outros tipos (como os
vectores por exemplo), ent ao tais instanciacoes permitam dispor, respecti-
vamente, de um contentor de: inteiros; caracteres; contentores de inteiros
(à semelhanca de matrizes de duas dimensoes de inteiros); ou nalmente de
contentores de um tipo ainda por denir.
Listas, tuplos, vectores, referencias s ao exemplos de tipos polim orcos
que descrevemos neste documento.
Mais formalmente, este tipo de polimorsmo designa-se por polimorsmo
parametrico e implementa a estrategia de todos para um. Uma func ao, um
tipo, aquando da sua denicao pode visar todos os casos aplicativos possveis
(e introduz assim vari aveis de tipo de acordo com esta vis ao). Mas quando
instanciada, esta e irremediavelmente especializada para o caso do valor da
instancia cao. Um tipo especializado n ao pode voltar a ser generalizado.
3.1.1 Conversoes explcitas
Para terminar sobre generalidades sobre a tipicacao forte, e admitindo a
existencia dos tipos de base int, float, char ou string que descreveremos
j a a seguir, listamos algumas func oes de conversao:
# int_of_char;;
- : char -> int = <fun>
# int_of_string;;
13
- : string -> int = <fun>
# int_of_float;;
- : float -> int = <fun>
# char_of_int;;
- : int -> char = <fun>
# float_of_string;;
- : string -> float = <fun>
# float_of_int;;
- : int -> float = <fun>
Estas sao obviamente uteis quando pretendemos realizar um cast possvel
dos tipos dos valores manipulados
4
. Relembramos que OCaml e fortemente
tipicado e que ajustes explcitos (no sentido, realizados explicitamente pelo
programador) de tipos podem ser requeridos pelo programador. Estas fun-
c oes podem devolver um valor do tipo desejado mas com perdas de precis ao
relativamente ao valor original.x
Por exemplo:
# int_of_char B ;;
- : int = 66
# int_of_float 1.6 ;;
- : int = 1
3.2 Variaveis e fun coes
Vamos nesta seccao introduzir duas caractersticas da linguagem OCaml
(de facto, das linguagens funcionais) que muda fundamentalmente a forma de
desenhar soluc oes algortmicas e programar quando comparado com a pr atica
do habitual paradigma imperativo. O programador habitual de C, Java ou
C++ normalmente dever a cuidadosamente explorar e incorporar estas duas
noc oes para conseguir a transi cao para linguagens funcionais.
De forma resumida, a capacidade dum programa em realizar efeitos co-
laterais para alem do calculo propriamente dito e algo que as linguagens
funcionais suportam de uma forma muito controlada. A linguagem OCaml
n ao foge a esta regra.
4
Em OCaml, estas fun coes nao transformam o tipo dum determinado valor, mas sim,
calculam/devolvem um novo valor do tipo adequado
14
Assim uma caracterstica saliente, para alem das que ja foram referidas,
das linguagens funcionais ` as quais OCaml pertence e o caractere implicita-
mente imut avel das vari aveis.
A imutabilidade das variaveis em OCaml lhes confere um estatuto ou
comportamento semelhante ` as vari aveis matem aticas: representam um e um
s o valor e perten cam a um conjunto (tipo).
Uma vari avel quando e introduzida num programa OCaml e necessaria-
mente inicializada com um valor e, n ao fugindo aos princpios de tipicac ao
forte, esta associada a um s o tipo.
Os processos algortmicos desenhados pelo programador nao podem que-
brar esta regra. Em regra geral quando um algoritmo necessita, dada a sua
formulacao propria, a alterac ao (repetida ou nao) do valor de uma variavel,
isto implica, em primeiro, que a formulac ao n ao e funcional (segue o para-
digma imperativo), logo nao pode directamente ser implementada recorrendo
` a noc ao basica de variaveis OCaml. A soluc ao e entao usar a camada im-
perativa disponvel em OCaml (neste caso as variaveis do algoritmo devem
ser implementadas como referencias OCaml) ou ent ao e necess ario obter
uma formulacao funcional do algoritmo (para poder usar a nocao primitiva
de vari avel ou de valor).
Voltaremos a esta noc ao quando serao apresentados os mecanismos de
denicao de variaveis (secc ao 3.5).
Outra vertente do mesmo fen omeno e o mecanismo de base para a com-
posic ao de acc oes. A sequencia, habitual no paradigma imperativo, n ao e o
mecanismo primitivo em OCaml (isto e: executar A; executar B; etc . . .,
como e habitual em linguagens imperativas). A composic ao de func oes e o
mecanismo de base para encadear as ac coes algortmicas por implementar.
3.3 Valores, funcoes e tipos de base
Nesta sec cao iremos explorar de forma sucinta os diferentes tipos de dados e
as func oes de base associadas.
3.3.1 Valores Numericos
Tipo inteiro: int
Formato: o formato habitual (sequencia dos algarismo denindo o inteiro,
sem ponto nem virgulas)
Limites: entre [2
30
, 2
30
1] nas m aquinas 32 bits e entre [2
62
, 2
62
1] nas
15
m aquinas 64 bits.
Tipo real: float
Formato: OCaml segue a norma IEEE 754 para a representac ao de
utuantes. Como tal, um utuante e um n umero real m 10
n
represen-
tado por um n umero contendo necessariamente um ponto (que representa a
virgula) cujos limites de representacao sao 53 bits para m e n [1022, 1023].
inteiros (tipo int) utuantes (tipo float)
representa cao de um 1 representa cao de um 1.0 ou 1.
adi cao + adi cao +.
subtraccao (ou negacao) subtraccao (ou negacao) .
multiplicacao multiplicacao .
divisao (inteira) / divisao /.
resto mod exponenciacao
algumas fun coes sobre inteiros
valor absoluto val abs : int -> int
maior inteiro representavel val max_int : int
menor inteiro representavel val min_int : int
etc...
algumas funcoes sobre utuantes
arredondamento para o inteiro superior (em formato float) val ceil : float -> float
arredondamento para o inteiro inferior (em formato float) val floor : float -> float
raz quadrada val sqrt : float -> float
exponencial val exp : float -> float
logaritmo base e val log : float -> float
logaritmo base 10 val log10 : float -> float
coseno val cos : float -> float
seno val sin : float -> float
tangente val tan : float -> float
arc-coseno val acos : float -> float
arc-seno val asin : float -> float
arc-tangente val atan : float -> float
etc...
Consultar as bibliotecas standard para uma lista detalhada das fun coes
predenidas. Existem tambem v arias bibliotecas fornecendo alternativas aos
tipos int e float, como a biblioteca aritmetica em precisao innita.
16
3.3.2 Caracteres e strings
Os caracteres OCaml s ao valores ASCII delimitados por plicas. o caracter
b em OCaml e : b.
As strings OCaml s ao cadeias de caracteres delimitadas por aspas
e de comprimento conhecido (menor do que 2
26
6). a string Bom
Dia em OCaml e: Bom Dia. a concatena cao de Bom Dia com
Tudo Bem? e Bom Dia ^ Tudo Bem? o que resulta na string
Bom Dia Tudo Bem?.
algumas fun coes sobre strings
concatena cao val (^) : string -> string -> string
comprimento val length : string -> int
n-esimo caracter val get : string -> int -> char
tudo em mai usculas val uppercase : string -> string
tudo em min usculas val lowercase : string -> string
etc...
As parentesis a volta do operador ^ signicam que ^ e inxo. Consultar
a biblioteca string para mais pormenores.
3.3.3 Booleanos
O tipo bool tem os dois elementos habituais true e false.
Operadores sobre booleanos
nega cao val not : bool -> bool
conjunc ao (e) val (&&) : bool -> bool -> bool
disjun cao (ou) val (||) : bool -> bool -> bool
Operadores de comparac ao
= val (=) : a -> a -> bool
,= val (<>) : a -> a -> bool
val (<=) : a -> a -> bool
< val (<) : a -> a -> bool
val (>=) : a -> a -> bool
> val (>) : a -> a -> bool
3.3.4 Tipo unidade
Existe um tipo particular, chamado em OCaml unit que so possui um
elemento: ().
17
# () ;;
- : unit = ()
Este tipo e particularmente importante quando se trata de escrever fun-
c oes com efeitos colaterais. A o tipo unit e o valor () tem o papel do void
do C
3.3.5 Produto Cartesiano, tuplos
O conjunto (tipo) A
1
A
2
. . . A
n
, formado a partir dos tipos A
1
, A
2
, . . .,
A
n
e representado em OCaml por A1*A2*A3*...*An. Os elementos, tuplos,
s ao representados por (a1,a2,a3,...,an).
No caso de pares (de tipo, por exemplo, A1*A2) dispomos das funcoes de
projecc ao fst e snd
# fst;;
- : a * b -> a = <fun>
# snd;;
- : a * b -> b = <fun>
# fst ( "Outubro", 12 ) ;;
- : string = "Outubro"
# snd ( "Outubro", 12 ) ;;
- : int = 12
# ( 65 , B , "ascii" ) ;;
- : int * char * string = 65, B, "ascii"
Uma caracterstica interessante, que fazem dos tipos produto cartesiano
tipos populares na programac ao OCaml, e a capacidade de serem calcu-
lados e devolvidos sem a necessidade de declarar o seu tipo previamente.
Trata-se assim de uma facilidade muito comoda que permite de agregar in-
formacao pontualmente e naturalmente (por exemplo aquando da denicao
de uma func ao que deve retornar varios valores, que podemos assim agrupar
comodamente num tuplo).
Exemplos sao precisamente o par e o triplo introduzidos na listagem an-
terior.
3.3.6 Listas
As listas s ao colecc oes polim orcas imut aveis e de acesso sequencial de ele-
mentos. Uma lista pode conter elementos de qualquer tipo, a restric ao e que
18
todos os elementos contidos tem de ser do mesmo tipo (fala-se de colecc oes
homogeneas). Podemos ter assim listas de inteiros, listas de caracteres. O
tipo polim orco OCaml correspondente e a list. Assim o tipo das listas
de inteiro e int list.
valores e operadores sobre listas
lista vazia []
construtor de listas ::
concatena cao de listas @
listas por extensao [ 1 ; 2 ; 3 ] ou 1 :: 2 :: 3 :: []
comprimento val length : a list -> int
cabe ca duma lista val hd : a list -> a
lista sem a cabe ca val tl : a list -> a list
n-esimo elemento val nth : a list -> int -> a
inversao de lista val rev : a list -> a list
pertence val mem : a -> a list -> bool
aplicac ao de uma fun cao sobre elementos
duma lista
map f [a1; ...; an] = [f a1; ...; f an] val map : (a -> b) -> a list -> b list
fold_left f a [b1;...; bn] =
f (...(f (f a b1) b2)...) bn val fold_left : (a ->b ->a) ->a ->b list ->a
for_all p [a1; ...; an] =
(p a1) && (p a2) && ... && (p an) val for_all : (a -> bool) -> a list -> bool
exists p [a1; ...; an]=
(p a1) || (p a2) || ... || (p an) val exists : (a -> bool) -> a list -> bool
ltragem,filter p [a1; ...; an]=
a lista de todos os elementos vericando p val filter : (a -> bool) -> a list -> a list
ordena cao val sort : (a -> a -> int) -> a list -> a list
As listas s ao, em OCaml, denidas como um tipo soma (indutivo) poli-
m orca (sobre o tipo dos elementos que contem) da seguinte forma:
type a list = [] | :: of a * a list
Assim a lista vazia e o operador :: s ao os construtores do tipo indutivo.
# [];;
- : a list = []
# [1;2;3];;
- : int list = [1; 2; 3]
# [1.5; 7.9; 9.3];;
- : float list = [1.5; 7.9; 9.3]
# [O;C; a; m; l];;
- : char list = [O; C; a; m; l]
# [(1.5,O); (7.9, C); (9.3,a)];;
19
- : (float * char) list = [(1.5, O); (7.9, C); (9.3, a)]
# length [1.5; 7.9; 9.3];;
- : int = 3
# [1;2;3]@[1;2;3];;
- : int list = [1; 2; 3; 1; 2; 3]
# [1;2;3]@[1.5; 7.9; 9.3];;
Characters 9-12:
[1;2;3]@[1.5; 7.9; 9.3];;
^^^
Error: This expression has type float but an expression was
expected of type int
# fold_left (fun a e -> a+e) 0 ([1;2;3]@[1;2;3]);;
- : int = 12
# sort compare [1;6;2;89;12;8;1;6;2;81];;
- : int list = [1; 1; 2; 2; 6; 6; 8; 12; 81; 89]
Consultar a biblioteca list para mais pormenores.
3.4 Estruturas Condicionais
Sem surpresas, o se entao senao e if then else em OCaml.
Sintaxe:
if express~ ao1 then express~ ao2 else express~ao3.
Restric ao: express~ ao2 e express~ ao3 tem necessariamente o mesmo tipo.
Este facto e devido ao facto de o if ser uma express ao como qualquer outra:
devolve um valor. Logo os dois ramos do if devem ser do mesmo tipo. O
equivalente na linguagem C e de facto a construcao (b)?t:e;.
O else e obrigatorio. Se for omitido e ent ao acrescentado implicitamente
else () (signicado: sen ao n ao fazer nada). Neste caso a expressao do then
de ser tambem do tipo unit.
3.5 Declaracao de valores
J a sabemos que toda a express ao OCaml tem um valor.
Se introduzirmos 4+6*2 num cheiro OCaml ent ao a express ao, aquando
da sua execuc ao, e avaliada (resultando em 16) e o valor e simplesmente
devolvido.
20
# 4+6*2;;
- : int = 16
Se por ventura a expressao e novamente necessaria, e preciso, nestes mol-
des, introduzir novamente a express ao e proceder novamente na sua avaliac ao.
Obviamente num contexto de programa cao a nocao cl assica de (declarac ao
de) vari avel resolve precisamente esta situac ao.
Estas podem ser globais ou locais, mas serao sempre variaveis imutaveis.
3.5.1 Declaracoes globais
Sintaxe:
let nome = express~ ao;;
A sem antica, sem surpresa, e: a express~ ao e avaliada e o tipo t da
express ao e inferido. A seguir um espaco do tamanho dos valores do tipo t
e alocado na memoria. O valor calculado e colocado neste espaco e este ser a
designado (acedido) via o identicado nome.
Esta atribuicao e feita uma e uma s o vez. Usar novamente o mecanismo
de declarac ao nao tem por efeito de alterar o valor da vari avel, mas sim
gerar uma nova vari avel, com o mesmo nome, que se referir a a um novo
espaco mem oria. As regras de visibilidade fazem o resto. A ultima declarac ao
esconde as outras e sera assim acedida.
# let x = 4;;
val x : int = 4
# print_int x;;
4- : unit = ()
# let x = 5;;
val x : int = 5
# print_int x;;
5- : unit = ()
# let x = 5.5;;
val x : float = 5.5
# print_int x;;
Characters 10-11:
print_int x;;
^
Error: This expression has type float but an expression was
expected of type int
21
3.5.2 Declaracoes locais
Sintaxe:
let nome = express~ ao1 in express~ ao2 ;;
Ao contr ario da declara cao global, o identicador nome s o vai, neste caso,
ser visvel (e com o valor da express~ ao1) dentro de express~ ao2.
Existe a possibilidade de declarac oes an onimas. Tais s ao uteis quando so
o valor computado na parte direita do igual interessa (no caso deste conter
efeitos laterais por exemplo):
Sintaxe:
let _ = express~ ao;; ou let _ = express~ ao1 in express~ ao2 ;;
Alguns exemplos:
# let x = 9;;
val x : int = 9
# let x = 2 + 4 in
let y = x + 2 in
y + 7;;
- : int = 15
# let x = 5 in
(let x = x + 3 in x + 1) + ( let y = x + 3 in x + y);;
- : int = 22
Ambas as declaracoes locais e globais tem variantes, consultar as referen-
cias para mais pormenores
3.6 Express oes funcionais e func oes
As func oes sao valores como quaisquer outros. Assim como 5 e um valor (que
pode ser usado directamente como sub-express ao numa outra expressao, como
por exemplo no caso par ametro de uma chamada duma func ao), ou como (if
3>4 then 5 else 8) e o valor 8, a func ao identidade ou a func ao sucessor
s ao valores primitivos e podem ser usados como tal.
3.6.1 Declaracao de base
Sintaxe:
function p -> express~ao
22
Neste caso a func ao contemplada e un aria (um s o parametro).

E a sintaxe
OCaml para o conhecido x.expr do clculo . Este mecanismo introduz a
noc ao de funcao anonima (no sentido de que representa um valor uma
funcao, sem nome).
Por exemplo:
# function x -> x;;
- : a -> a = <fun>
# function x -> x + 1;;
- : int -> int = <fun>
# function v -> if v > 10 then true else false;;
- : int -> bool = <fun>
# let x = 7;;
val x : int = 7
# if x > 5 then (function x -> x + 2) x else (function z -> z - 7) (x + 1);;
- : int = 9
Obviamente, estas denicoes n ao fogem ` a regra das outras express oes e, se
n ao lhes forem atribudas um nome, cam utiliz aveis uma s o vez no momento
da avaliacao cando assim perdidas no limbo.
Para tal podemos usar o mecanismo de declarac ao global j a introduzido
# let f = function x -> x;;
val f : a -> a = <fun>
# f 7;;
- : int = 7
Um aspecto por realcar ja nestes exemplos simples e a ausencia da men cao
do valor de retorno, cl assica no paradigma imperativo. Tal se deve, mais uma
vez, ao facto de que fun coes sao expressoes. Avaliam-se em valores e s ao estes
que constituem os valores de retorno.
# let u = function x -> (if x>4 then (function v -> x+v) 6 else 3;;
val u : int -> int = <fun>
# u 7;;
- : int = 13
# u 2;;
- : int = 3
23
Para fun coes bin arias (por exemplo) ser a preciso usar a sintaxe:
function p -> function q -> express~ao
Apesar de parecer relativamente pesada, esta nota cao representa a forma
mais primitiva de deni cao de fun cao mas tambem introduz uma das mais
interessantes perspectiva desta noc ao, quando comparada a nocao de func ao
no paradigma imperativo: a curryca cao (currying, em ingles, em referencia
` a Haskell Curry) e o seu pendente, a avalia cao parcial.
Por exemplo a func ao function (p,q,r) -> p * q +r (um so parame-
tro formal, um triplo (p,q,r)) na sua vers ao currycada e
function p -> function q -> function r -> p * q +r
Esta versao denota uma fun cao que espera um parametro inteiro p e
que devolve uma func ao que por seu turno espera um inteiro q e devolve
uma terceira fun c ao que nalmente do seu parametro r devolve p q + r.
Vantagens? vejamos o exemplo seguinte:
# let g = function (p,q,r) -> p * q + r;;
val g : int * int * int -> int = <fun>
# let h = function p -> function q -> function r -> p * q + r;;
val h : int -> int -> int -> int = <fun>
# g (1, 2, 3);;
- : int = 5
# h 1 2 3;;
- : int = 5
# h 1;;
- : int -> int -> int = <fun>
# h 1 2;;
# let a = h 1;;
val a : int -> int -> int = <fun>
# a 2 3;;
- : int = 5
Enquanto a avaliacao de uma chamada a func ao g obriga ` a referencia
explcita de todos os seus parametros (ou ao contr ario a ausencia completa
deles), a func ao h revela-se muito mais exvel.

E possvel fornecer parcial-
mente os seus par ametros. Assim (h 1 2) e avaliada na funcao que espera
um par ametro r e que devolve entao 1 2 + r.
24
3.6.2 Sintaxe alternativa para funcoes n-arias
Por raz oes de conveniencia e possvel utilizar a sintaxe seguinte:
fun p1 p2 ... pn -> express~ao
para as func oes n- arias. Esta deni cao e o ac ucar sint actico para
function p1 -> function p2 -> ... -> function pn -> express~ ao
3.6.3 Declaracoes de valores funcionais
Tal como qualquer valor, e possvel declarar nomes para funcoes.
Sintaxes:
let nome = function p -> express~ao
ou ainda
let nome = fun p1 p2 ... pn -> express~ao
ou ainda
let nome p1 p2 ... pn = express~ao
No caso de uma funcao recursiva a sintaxe e:
let rec nome p1 p2 ... pn = express~ ao
E aqui importante realcar a necessidade da palavra chave rec. Esta e

realmente necess aria (nao pode ser omitida e assim o seu efeito inferido em
tempo de execucao), como mostra o exemplo seguinte.
# let fact n = n;;
val fact : a -> a = <fun>
# fact 4;;
- : int = 4
# let fact n = if n<=1 then 1 else n * fact (n - 1);;
val fact : int -> int = <fun>
# fact 4;;
- : int = 12
# let rec fact n = if n<=1 then 1 else n * fact (n - 1);;
val fact : int -> int = <fun>
# fact 4;;
- : int = 24
Destaquemos nalmente o caso das func oes sem retorno (procedimentos)
ou sem argumentos. Estes dois casos s ao possveis e expressam-se com o
recurso ao tipo uni, porque anal sao express oes tipicadas como as restantes
express oes OCaml.
25
# let x = 9;;
val x : int = 9
# let f () = x + 2;;
val f : unit -> int = <fun>
# let g n = print_int (n + (f ()));;
val g : int -> unit = <fun>
# f();;
- : int = 11
# g 6;;
17- : unit = ()
3.6.4 Declaracao de funcoes locais
Como para qualquer outra express ao, podemos declarar func oes locais com
o recurso, sem surpresa, da expressao let..in
# let f n =
let g x = x + x*3 in
let rec h x = if x > 0 then 2*x + x*3 else h (-x) in
h (g n);;
val f : int -> int = <fun>
# f 6;;
- : int = 120
# g 7 ;;
Characters 0-1:
g 7;;
^
Error: Unbound value g
3.6.5 Funcoes de ordem superior
Aquando da introducao da noc ao de curryca cao introduziu-se sem mais
justicac oes a nocao de func ao que devolve uma fun cao. Tal func ao e dita,
de forma geral, de ordem superior.
A ordem de uma func ao qualica a sua natureza relativamente ao tipo dos
par ametros de que necessita ou ao tipo do valor devolvido. De uma forma
geral uma fun cao que recebe par ametros de ordem i e devolve um valor de
ordem j e de ordem max(i, j) + 1.
26
No contexto do estudo das func oes, uma fun cao sem par ametro e uma
(func ao) constante ou de ordem 0, um valor inteiro (ou string, char etc ...)
e tambem de ordem 0. Uma fun cao que recebe como parametro um valor
de ordem 0 e que devolve um valor de ordem 0 (as fun coes como habitual-
mente as entendemos) s ao de ordem 1 (primeira ordem). Uma fun cao que
recebe parametros de ordem 1 e devolve um valor de ordem 1 e de segunda
ordem. Uma fun cao que devolve (ou que aceita em parametro) uma func ao
de primeira ordem e de segunda ordem etc ...
No limite, uma func ao que aceita ou devolve valores de ordem i qualquer
que seja i e dita de ordem superior. Este e o caso mais geral e e um caso
comum em programac ao funcional.
Imaginemos o caso simples da funcao identidade.
# let id = fun x -> x;;
val id : a -> a = <fun>
O facto de ser polimorca sobre o seu argumento permite-lhe receber um
argumento de qualquer tipo e devolve-lo. Este pode ser uma func ao, um
valor numerico etc... ou seja, de qualquer ordem. A func ao id e uma fun cao
polimorca de ordem superior.
# id (fun x -> x + 1);;
# id 5;;
- : int = 5
Algumas Aplicacoes. As func oes de ordem superior conseguem capturar
de forma elegante padr oes algortmicos, tornando-as num dos mecanismos
cl assicos e elegantes para a modularidade e reutilizac ao de c odigo no para-
digma funcional.
Por exemplo a func ao de ordem superior fold_left, denido no modulo
List e cuja deni cao pode ser
#(*fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn. *)
let rec fold_left f a l =
match l with
| [] -> a
| el::li -> fold_left f (f a el) li;;
val fold_left : (a -> b -> a) -> a -> b list -> a = <fun>
27
captura a noc ao de calculo sobre uma sequencia de valores (a lista) e
cujo valor, inicializado, e acumulado ate esgotar os elementos da sequencia.
O padr ao algortmico e, concretamente, o da varredura da esquerda para a
direita dos elementos acompanhado da aplicac ao da fun cao f sobre o elemento
visitado.
Se ligarmos este conceito ` a algebra da programac ao, o mecanismo imple-
mentado pela funcao fold_left e um caso particular de catamorsmo.
Em termos de comparac ao com o estilo imperativo, trata-se simplesmente
do padr ao algortmico seguinte (em pseudo-c odigo):
v := a;
for i:=0 to (length l) - 1 do
v := f v (nth i l);
done;
return v;
Visualmente podemos resumir este padr ao com a ajuda alternativa das
guras 1 e 2.
Figura 1: fold left, vizualmente - versao mecanica
Figura 2: fold left, vizualmente - vers ao algebrica
Na pr atica esta func ao pode ser usada para calcular valores que envolvem
potencialmente todos os elementos da lista. Por exemplo,
28
# let somal l = fold_left (fun a e -> a + e) 0 l;;
val somal : int list -> int = <fun>
# somal [1;2;3;4;5;6;7;8;9];;
- : int = 45
# let inverte l = fold_left (fun a e -> e::a) [] l;;
val inverte : a list -> a list = <fun>
# inverte [1;2;3;4;5;6;7;8;9];;
- : int list = [9; 8; 7; 6; 5; 4; 3; 2; 1]
# let filtra pred l =
fold_left
(fun (a,b) e -> if (pred e) then (e::a,b) else (a,e::b))
([],[]) l;;
val filtra : (a -> bool) -> a list -> a list * a list = <fun>
# filtra (fun i -> i mod 2 = 0) [1;2;3;4;5;6;7;8;9];;
- : int list * int list = ([8; 6; 4; 2], [9; 7; 5; 3; 1])
# let existe pred l =
fold_left (fun a e -> if pred e then true else a ) false l;;
val existe : (a -> bool) -> a list -> bool = <fun>
# existe (fun i -> (i mod 2 = 0) && (i mod 3 = 0)) [1;2;3;4;5;6;7;8;9];;
- : bool = true
Func oes como fold_left designam-se de classicamente de combinadores.
Notemos igualmente que as fun coes inverte, filtra e existe s ao igual-
mente combinadores e constam da biblioteca standard no m odulo List sob
os nomes, respectivamente, rev, partition e exists.
Um combinador muito utilizado no contexto da manipula cao de estruturas
de dados da categoria dos contentores (como as listas, ou vectores ou ainda
arvores) e a fun cao map. Gracamente, o padr ao algortmico que implementa
e representado pela gura 3.
# map;;
- : (a -> b) -> a list -> b list = <fun>
# map (fun a -> a + 2) [1;2;3;4;5;6;7;8;9];;
- : int list = [3; 4; 5; 6; 7; 8; 9; 10; 11]
# map (fun i -> (i mod 2 = 0) && (i mod 3 = 0)) [1;2;3;4;5;6;7;8;9];;
- : bool list =
[false; false; false; false; false; true; false; false; false]
29
Figura 3: map, vizualmente
Alias, e bastante simples reformular a fun cao map a custa da fun cao
fold_left.
# let mapa f l = rev (fold_left (fun a e -> (f e)::a) [] l);;
val mapa : (a -> b) -> a list -> b list = <fun>
# mapa (fun i -> (i mod 2 = 0) && (i mod 3 = 0)) [1;2;3;4;5;6;7;8;9];;
- : bool list =
[false; false; false; false; false; true; false; false; false]
Outro exemplo pode ser a noc ao de composic ao de func oes
# let ( *+) f g = fun x -> f (g x);;
val ( *+ ) : (a -> b) -> (c -> a) -> c -> b = <fun>
# let f = (fun x -> 2 * x) *+ (fun x -> x + 3);;
# f 6;;
- : int = 18
Para terminar, ilustremos a noc ao de construc ao incremental de func oes.
Imaginemos que pretendemos construir uma fun cao a medida que se ca a
conhecer informac ao sobre o seu domnio e co-domnio (i.e. os dados que a
denam).
# let f x = raise Not_found;;
val f : a -> b = <fun>
# f 5;;
Exception: Not_found.
# let f x = if x = 5 then 7 else f x;;
30
# f 5;;
- : int = 7
# f 3;;
# f 5;;
- : int = 7
# f 3;;
- : int = 1
# f 5;;
- : int = 2
# f 3;;
- : int = 1
# f 2;;
Neste exemplo, a medida que conhecemos os pares
(valor de entrada, valor devolvido) sobrecarregamos (` a custa da noc ao
de fecho e de porte) a funcao de base let f x = raise Not_found;; que
representac ao a func ao cujo domnio e vazio.
Este exemplo exemplica uma forma, que pode parecer original para quem
descobre a noc ao de fun cao de ordem superior, de encarar as funcoes. Estas
podem ser vistas como mapas (maps em ingles) ou suporte a estruturas de
tipo tabela de hash sem colisoes (repare como o par 5 7 foi substitudo
pelo par 5 2).
3.6.6 Fecho
Em OCaml as func oes s ao fechadas. Isto e, todas as vari aveis contidas na
denicao e que nao s ao par ametros s ao avaliadas e substitudas pelos seus
valores por forma a permitir uma denic ao da funcao que tire proveito mas
que que independente do ambiente global no qual foi denida.
Por exemplo:
# let m = 3 ;;
val m : int = 3
31
# let f= (function x -> x + m);;
# f 5;;
- : int = 8
# let m = 8;;
val m : int = 8
# f 5;;
- : int = 8
Este exemplo p oe em evidencia como s ao de facto consideradas e mani-
puladas as funcoes em OCaml: uma fun cao e denida pelo seu codigo e pelo
ambiente ao qual ela tem acesso. Este ambiente faz parte integrante da sua
denicao. Fala-se assim, para este par de informac ao (ambiente e c odigo) de
fecho de uma funcao.
Diferencas com os apontadores de funcao (à la C). A func oes de
ordem superior s ao mais gerais do que as fun coes que usam o mecanismo dos
apontadores de func ao.
Para a maioria dos casos (simples), de facto o mecanismo de apontadores
de func ao, como o encontramos na linguagem C, permite uma express ao
equivalente do conceito de fun cao de ordem superior.
Mas, se misturarmos os fenomenos de valores locais, fecho e avaliac ao
parcial, a situa cao muda completamente.
Por exemplo
# let f x = let x2 = 2 * x + x * x in function y -> x2 + y;;
val f : int -> int -> int = <fun>
# let g x = f x;;
val g : int -> int -> int = <fun>
# let g1 = g 3;;
val g1 : int -> int = <fun>
# let g2 = g 4;;
val g2 : int -> int = <fun>
# g1 2;;
- : int = 17
# g2 2;;
- : int = 26
32
De facto cada instanciac ao parcial de f permite a reduc ao da express ao
local x2 para um valor particular, diferente em cada uma delas. A func ao
un aria resultante tem ent ao no seu fecho uma c opia do valor de x2. Este fen o-
meno de fecho n ao tem equivalente no uso dos apontadores de fun cao. Para
disponibilizar de tal comportamento numa linguagem imperativa, ser a neces-
s aria codicar e manipular explicitamente a nocao de fecho de uma func ao
(a func ao e os dados a que ela tem acesso para a sua adequada execuc ao).
3.6.7 Ordem Superior e Polimorsmo
O polimorsmo parametrico do OCaml segue a seguinte poltica: para todos
ou para um. Assim a func ao id que e de tipo a -> a aceita qualquer
par ametro, e devolve na identica este. Neste caso a variavel de tipo a sofre
uma instanciacao para o tipo do seu par ametro. Neste sentido a funcao
id funciona para todos. No entanto, apos instanciada, a vari avel de tipo
a manter a o seu vnculo. let id_int = function (x:int) -> id x e
de tipo int -> int e s o funcionar a doravante como a funcao identidade
para inteiro, exclusivamente ou seja para um. Outro exemplo pode ser o
valor [] que na sua generalidade e de tipo a list, enquanto o [] da lista
1::2::3::[] e int list.
# tl [1];;
- : int list = []
# [];;
- : a list = []
# tl [1] = tl [a];;
Characters 9-17:
tl [1] = tl [a];;
^^^^^^^^
Error: This expression has type char list
but an expression was expected of type int list
A tipagem de OCaml e estatica, ou seja, e exclusivamente realizada em
tempo de compilac ao. O polimorsmo parametrico na sua generalidade pode
levar a situa coes em que e impossvel inferir o tipo (mais geral) de um valor
e neste momento incorrecto atribui-lhe um tipo sem alguma cautela. Para
tal existe a noc ao de polimorsmo fraco.
Veremos ilustra coes deste mesmo fen omenos mais adiante com a nocao
de referencias. Concentremo-nos aqui num exemplo intrigante com func oes.
33
Misturar polimorsmo, ordem superior e tipos funcionais (tipos que repre-
sentam funcoes) leva-nos a algumas situa coes limites na inferencia de tipos
que o sistema de tipos de OCaml detecta perfeitamente e trata com o devido
cuidado (de uma forma diferente ao que esperaramos num contexto em que
n ao haveria tipos funcionais envolvidos).
# let f = fun x -> x;;
val f : a -> a = <fun>
# f f;;
- : _a -> _a = <fun>
# f (f f);;
- : _a -> _a = <fun>
# let g = f (f f);;
val g : _a -> _a = <fun>
# g 6 ;;
- : int = 6
# g;;
A vari avel de tipo _a e uma variavel de tipo fraco. Ainda n ao e conhecida
o seu valor, mas o resto do programa poder a permitir ganhar este conheci-
mento. E nesta altura ser a inequivocamente instanciada.

E o que demonstra
o exemplo da fun cao g. A fun cao g tem o tipo _a -> _a aquando da sua
denicao. O que signica que no momento da sua denic ao o tipo (mais
geral) de g ainda n ao e conhecido (mas j a se sabe que e uma funcao de um
tipo para ele proprio) e que a decis ao nal e adiada. Quando esta decis ao e
conhecida (anal _a e int), entao e aplicada retro-activamente.
3.7 Uma digressao sobre a nocao de igualdade
Notemos que emOCaml existem dois smbolos para a igualdade. o predicado
= que permite expressar a igualdade (estrutural) dos valores comparados,
e == que representa a igualdade fsica, ou seja que testa se dois objectos
representam o mesmo espaco memoria.
Ambas s ao polim orcas
# (==);;
- : a -> a -> bool = <fun>
# (=);;
34
- : a -> a -> bool = <fun>
No entanto, e à semelhanca da considerac oes de tipagem no contexto de
ordem superior e de tipos funcionais, o suporte às func oes obrigam alguma
cautela.
# a = b;;
- : bool = false
# 1 = 1;;
- : bool = true
# "ola" == "ola";;
- : bool = false
# "ola" = "ola";;
- : bool = true
# [1;2;3]=[3;2;1];;
- : bool = false
# [1;2;3] = [1;2;3];;
- : bool = true
# [1;2;3] == [1;2;3];;
- : bool = false
# (function x -> x + 5) == (function y -> y + 5);;
- : bool = false
# (function x -> x + 5) = (function y -> y + 5);;
Exception: Invalid_argument "equal: functional value".
#
let f = (function x -> x + 5);;
# f == f;;
- : bool = true
# f = f;;
Exception: Invalid_argument "equal: functional value".
3.8 Declaracao de tipos e ltragem de motivos
3.8.1 Pattern matching (ltragem)
A ltragem de motivos, ou concord ancia de padr ao, permite uma programa-
c ao baseada em analise de casos.
Sintaxe:
35
match expr with
| p1 -> expr1
.
.
.
| pn -> expr
Signica: olhar para o valor de expr, se este valor se assemelha com p1
ent ao avaliar expr1 sen ao vericar semelhanca com p2, etc...
Considerac oes:
os motivos p1...pn tem de cobrir todos os casos;
os motivos tem de ser lineares. Isto e, se conterem vari aveis, ent ao essas
s o ocorrem uma unica vez.
quando dois motivos cobrem o mesmo caso (isto e, quando existe uma
sobreposic ao entre dois motivos e que o caso avaliado e coberto por
ambos), e ent ao escolhido o motivo que aparece primeiro.
Motivo universal (que se assemelha sempre) e denotado pelo caracter
_. O motivo _ signica outros casos ou ainda tudo. A constru cao let
pode ser vista como um caso particular de ltragem quando existe uma s o
possibilidade de concord ancia.
As construc oes de concord ancia de padr ao, e os proprios padroes podem
ser aninhados.
Exemplos de ltragem:
# let rec fold_left f a l =
match l with
[] -> a
| cabeca::resto -> fold_left f (f a cabeca) resto ;;
val fold_left : (a -> b -> a) -> a -> b list -> a = <fun>
# fold_left (+) 0 [8;4;10];;
- : int = 22
# let vazio l =
match l with
[] -> true
| _ -> false;;
val vazio : a list -> bool = <fun>
36
# vazio [1;2;3];;
- : bool = false
# let soma_par c =
let (esq,dir) = c in
esq+dir;;
val soma_par : int * int -> int = <fun>
# soma_par (1,2);;
- : int = 3
# let has_two_elements l =
match l with
[] -> false (*|l| = 0*)
| el::li -> match li with
[] -> false (*|l|=1*)
| el2 :: lli -> match lli with
[] -> true (* |l| = 2 *)
| el3 :: _ -> false;;
val has_two_elements : a list -> bool = <fun>
# let has_two_elements l =
match l with
| [el1;el2] -> true
| _ -> false;;
val has_two_elements : a list -> bool = <fun>
# has_two_elements [1;2];;
- : bool = true
# has_two_elements [1;2;4];;
- : bool = false
Existem extens oes interessantes aos mecanismos de concord ancia aqui
apresentados, para conhece-los consultar a bibliograa.
3.8.2 Declaracao de tipos
E possvel estender os tipos de base com tipos denidos pelo programador.

Sintaxe:
type nome = definicao_do_tipo;;
No caso de tipos mutuamente recursivos (que dependem mutuamente uns
dos outros) a sintaxe e estendida em:
37
type nome1 = definicao_do_tipo1
and nome2 = definicao_do_tipo2
.
.
.
and nome_n = definicao_do_tipo_n;;
No caso dos tipos serem polim orcos, e necess ario indicar as variaveis de
tipo.
Sintaxe:
type (a1,...,an) nome = defini c~ ao_do_tipo;;
Obviamente, podemos denir tipos polim orcos mutuamente recursivos.
Quais sao as possibilidades para definic~ao_do_tipo? composicao de
tipos de base (como por exemplo pares de listas de inteiros, etc...), registos,
tipos soma.
Exemplos:
# type param par_inteiro = int * param ;;
type a par_inteiro = int * a
# type par_totalmente_instanciado = float par_inteiro ;;
type par_totalmente_instanciado = float par_inteiro
# let (x:par_totalmente_instanciado) = (3, 3.14) ;;
val x : par_totalmente_instanciado = 3, 3.14
3.8.3 Registos
Sintaxe:
type (a1,...,an) nome =
{ nome_campo1 : tipo1; ...; nome_campo_n : tipo_n };;
Um exemplo:
# type complex = { re:float; im:float } ;;
type complex = { re: float; im: float }
38
Criacao de registos Sintaxe:
{ nome_campo1 = valor1; ...; nome_campo_n = valor_n };;
N ao e necessario listar os campos na ordem da denic ao, mas e preciso
que todos sejam referidos.
# let c = {re=2;im=3};;
val c : complex = {re=2; im=3}
# c = {im=3.;re=2.} ;;
- : bool = true
Acesso aos campos Sintaxe:
expr.nome_campo
Consulte a bibliograa para mais pormenores.
3.8.4 Tipos soma
Estes tipos codicam o que usualmente referimos por tipos ou conjuntos
indutivos.
Sintaxe:
type nome_tipo =
| Nome_construtor_1 of t11 * ...* t1k.
.
.
.
| Nome_construtor_n of tn1 * ...* tnk
Os identicadores de construtores comecam sempre por uma mai uscula.
A parte of t1 * ...* tk na declaracao dum construtor n ao e obrigat oria.
S o e requerida se o construtor tiver argumentos.
Exemplos de tipo soma:
# type natural = Z | S of natural;;
type natural = Z | S of natural
# let rec (+.+) x = function Z -> x | S p -> S (x +.+ p);;
val ( +.+ ) : natural -> natural -> natural = <fun>
# S Z +.+ S (S Z);;
39
- : natural = S (S (S Z))
# type (a, b) list2 =
Nil
| Acons of a * (a, b) list2
| Bcons of b * (a, b) list2 ;;
# type semana =
Domingo | Segunda | Terca | Quarta | Quinta | Sexta | Sabado;;
# type tarefas =
Chemistry | Companhia | Trabalho_de_Casa
| Armazem | Faculdade_da_Cerveja;;
# type actividade =
Trabalho of tarefa | Compras | Descanco;;
e exemplos de func ao com ltragem sobre elementos de tipos soma
# let rec extract_odd l =
match l with
Nil -> []
| Acons(_, x) -> extract_odd x
| Bcons(n, x) -> n::(extract_odd x) ;;
val extract_odd : (a, b) list2 -> b list = <fun>
# let que_faco_hoje dia =
match dia with
Segunda-> Trabalho Faculdade_da_Cerveja
| Terca -> Trabalho Companhia
| Quarta -> Trabalho Chemistry
| Quinta -> Trabalho Trabalho_de_Casa
| Sexta -> Trabalho Armazem
| Sabado -> Compras
| Domingo-> Descanco;;
val que_faco_hoje : semana -> actividade = <fun>
# que_faco_hoje Quinta;;
- : actividade = Trabalho Trabalho_de_Casa
3.9 Excepcoes
3.9.1 Denicao
Sintaxe:
40
exception Nome of parâmetros;;
Regras:
os identicadores de excepc oes s ao de facto construtores, logo devem
comecar por uma mai uscula;
o polimorsmo n ao e aceite nas excep coes.
# exception MINHA_EXCEPCAO;;
exception MINHA_EXCEPCAO
# MINHA_EXCEPCAO;;
- : exn = MINHA_EXCEPCAO
# exception Depth of int;;
exception Depth of int
# Depth 4;;
- : exn = Depth(4)
3.9.2 Lancar uma excepcao
Sintaxe:
raise (Nome t1 ... tn)
Exemplos:
# raise ;;
- : exn -> a = <fun>
# raise MINHA_EXCEPCAO;;
Uncaught exception: MINHA_EXCEPCAO
# 1+(raise MINHA_EXCEPCAO);;
Uncaught exception: MINHA_EXCEPCAO
# raise (Depth 4);;
Uncaught exception: Depth(4)
3.9.3 Recuperar excepcoes
Sintaxe:
41
try express~ ao with
| motivo_excepcao1 -> expr1
.
.
.
| motivo_excepcao_n -> expr_n
No caso da avaliac ao de express~ ao levantar uma excep cao ent ao h a l-
tragem com os diferentes motivos listados. no caso de haver concord ancia a
express ao correspondente e avaliada.
Exemplos:
# exception Found_zero ;;
exception Found_zero
# let rec mult_rec l = match l with
[] -> 1
| 0 :: _ -> raise Found_zero
| n :: x -> n * (mult_rec x) ;;
val mult_rec : int list -> int = <fun>
# let mult_list l =
try mult_rec l with Found_zero -> 0 ;;
val mult_list : int list -> int = <fun>
# mult_list [1;2;3;0;5;6] ;;
- : int = 0
4 Programacao imperativa
4.1 Estruturas de Dados modicaveis
4.1.1 Vectores
Os vectores em OCaml tem por delimitadores os smbolos [| e |].
Exemplo:
# let v = [| 3.14; 6.28; 9.42 |] ;;
val v : float array = [|3.14; 6.28; 9.42|]
Acesso Sintaxe:
expr1 . ( expr2 )
42
Atribuicao Sintaxe:
expr1 . ( expr2 ) <- expr3
Exemplos:
# v.(1) ;;
- : float = 6.28
# v.(0) <- 100.0 ;;
- : unit = ()
# v ;;
- : float array = [|100; 3.14; 9.42|]
# let t = [|
[|1|];
[|1; 1|];
[|1; 2; 1|];
[|1; 3; 3; 1|];
[|1; 4; 6; 4; 1|];
[|1; 5; 10; 10; 5; 1|]
|] ;;
val t : int array array =
[|[|1|]; [|1; 1|]; [|1; 2; 1|]; [|1; 3; 3; 1|];
[|1; 4; 6; 4; ...|]; ...|]
# t.(3) ;;
- : int array = [|1; 3; 3; 1|]
Operadores usuais sobre vectores
Comprimento val length : a array -> int
criacao val make : int -> a -> a array
make n x = [|x; ...(n vezes)... ;x|]
inicializa cao val init : int -> (int -> a) -> a array
init n f = [|f 1; ... ;f n|]
concatena cao de vectores val append : a array -> a array -> a array
duplicacao de vectores val copy : a array -> a array
Conversoes de/para listas val to_list : a array -> a list
val of_list : a list -> a array
map para vectores val map : (a -> b) -> a array -> b array
fold_left para vectores val fold_left :
(a -> b -> a) -> a -> b array -> a
ordena cao val sort : (a -> a -> int) -> a array -> unit
Consultar a biblioteca array para mais pormenores.
43
4.1.2 Strings como vectores
Acesso directo Sintaxe: expr1 . [expr2]
Atribuicao Sintaxe: expr1 . [expr2] <- expr3
Exemplos
# let s = "Ola Tudo Bem?";;
val s : string = "Ola Tudo Bem?"
# s.[2];;
- : char = a
# s.[2]<-Z;;
- : unit = ()
# s;;
- : string = "OlZ Tudo Bem?"
4.1.3 Registos e campos modicaveis
O OCaml permite que campos de registos possam ser modicaveis. Para
tal e preciso que os referidos campos sejam declarados com a palavra chave
mutable.
Declaracao Sintaxe: type nom = { ...; mutable nome_campo_i : t ; ...}
Atribuicao Sintaxe: expr1 . nom <- expr2
Exemplos:
# type ponto = { mutable xc : float; mutable yc : float } ;;
type ponto = { mutable xc: float; mutable yc: float }
# let p = { xc = 1.0; yc = 0.0 } ;;
val p : ponto = {xc=1; yc=0}
# p.xc <- 3.0 ;;
- : unit = ()
# p ;;
- : ponto = {xc=3; yc=0}
# let moveto p dx dy =
let () = p.xc <- p.xc +. dx
in p.yc <- p.yc +. dy ;;
val moveto : ponto -> float -> float -> unit = <fun>
44
# moveto p 1.1 2.2 ;;
- : unit = ()
# p ;;
- : ponto = {xc=4.1; yc=2.2}
4.1.4 Referencias
O conceito de vari aveis OCaml difere do conceito de vari aveis de linguagens
s como o C. De facto assemelham-se do conceito de variaveis em matem atica:
uma variavel, um valor.
Existe no entanto a possibilidade de ter variaveis como em C. Estas sao
consideradas como referencias para valores e devem ser declaradas como
sendo do tipo ref.
Denicao Na sua base o tipo ref e denido da seguinte forma:
type a ref = {mutable contents:a}
Declaracao Sintaxe: ref expr
Acesso Sintaxe: !nome
Atribuicao Sintaxe: nome:= expr
Exemplos:
# let x = ref 3 ;;
val x : int ref = {contents=3}
# x ;;
- : int ref = {contents=3}
# !x ;;
- : int = 3
# x := 4 ;;
- : unit = ()
# !x ;;
- : int = 4
# x := !x+1 ;;
- : unit = ()
# !x ;;
- : int = 5
45
Fecho, referencias e func oes

E possvel tirar proveito do fen omeno de
fecho para obter func oes que partilham e manipulam valores escondidos ao
utilizador (fala-se de encapsulamento). A ideia e declarar tais fun coes e as
vari aveis por esconder simultaneamente e devolver simplesmente as funcoes
por disponibilizar ao programador. De facto, no fecho de cada func ao devol-
vida estara uma referencia para os valores locais escondidos (inacessveis) ao
programador.
Eis um exemplo:
# let (inicializa, afecta, incrementa, mostra) =
let valor_por_esconder : int ref =
ref 0 in
let elt_init () =
valor_por_esconder := 0 in
let elt_get () =
!valor_por_esconder in
let elt_incr () =
valor_por_esconder := 1+ !valor_por_esconder in
let elt_set n =
valor_por_esconder := n in
( elt_init,elt_set,elt_incr,elt_get);;
val inicializa : unit -> unit = <fun>
val afecta : int -> unit = <fun>
val incrementa : unit -> unit = <fun>
val mostra : unit -> int = <fun>
# inicializa();;
- : unit = ()
# mostra();;
- : int = 0
# incrementa();;
- : unit = ()
# mostra();;
- : int = 1
# afecta 5;;
- : unit = ()
# mostra();;
- : int = 5
# valor_por_esconder;;
46
Unbound value valor_por_esconder
4.2 Entradas e sadas
As entradas e sadas, de forma geral, sao efectuadas por funcoes que n ao
calculam nenhum valor em particular mas que efectuam efeitos colaterais.
Assim uma fun cao de entradas e sadas devolvera habitualmente um elemento
do tipo unit.
As entradas e sadas em OCaml s ao geridas a custa de canais de co-
municacao. Existem dois tipos predenidos de canais: o tipo dos canais de
entrada in_channel e o tipo dos canais de sada out_channel. Quando o
m de cheiro e atingido a excepcao End_of_file e lancada. Existem tres
canais predenidos, a semelhanca do C: stdin, stdout e stderr.
4.2.1 Abertura de cheiro
# open_in;;
- : string -> in_channel = <fun>
# open_out;;
- : string -> out_channel = <fun>
4.2.2 Fecho de cheiro
# close_in ;;
- : in_channel -> unit = <fun>
# close_out ;;
- : out_channel -> unit = <fun>
4.2.3 Leitura e Escrita
Eis algumas func oes de leitura e escrita em canais abertos:
# input_line ;;
- : in_channel -> string = <fun>
# input ;;
- : in_channel -> string -> int -> int -> int = <fun>
# output ;;
- : out_channel -> string -> int -> int -> unit = <fun>
# read_line ;;
47
- : unit -> string = <fun>
# read_int ;;
- : unit -> int = <fun>
# read_float ;;
- : unit -> float = <fun>
# print_string ;;
- : string -> unit = <fun>
# print_newline ;;
- : unit -> unit = <fun>
# print_endline ;;
- : string -> unit = <fun>
Exemplo:
# let () = print_string "um," in
let () = print_string " dois," in
let () = print_string " e tres" in
let () = print_string " zero" in
print_newline ();;
um, dois e tres zero
- : unit = ()
As func oes da famlia scanf e printf familiares ` a programac ao existem
numa declinac ao particular em OCaml. Ver as bibliotecas associadas.
4.3 Estruturas de controlo
4.3.1 Sequencia
E possvel pedir ao OCaml que uma lista de express oes sejam avali-
ados sequencialmente, tal como aconteceria em C. Tal sequencia segue
o seguinte formato: expr1;expr2; ...;expr_n.

E importante perceber
que esta n ao foge ` as regras da programacao funcional. Uma sequencia
expr1;expr2; ...;expr_n e uma e uma so express ao como tal tem um
valor.
O valor da sequencia e o valor da ultima expressao (neste caso expr_n).
O tipo das expressoes expr1;expr2;...;expr_(n-1) deve ser unit. Se tal
n ao for o caso, uma mensagem de aviso (Warning) e mostrada.
A funcao val ignore: a -> unit permite remediar este problema.
48
Ao permitir mecanismos tradicionalmente imperativos, mesmo de forma
controlada como e o caso aqui, e necessario disponibilizar (tambem de forma
controlada) a sequencia para poder permitir o encadeamento de efeitos cola-
terais. A sequencia e o mecanismo para este efeito.
Exemplos:
# print_int 1; 2 ; 3;;
Characters 13-14:
print_int 1; 2 ; 3;;
^
Warning S: this expression should have type unit.
1- : int = 3
# print_int 1; ignore 2; 3 ;;
1- : int = 3
# print_string ("1+1 = "^string_of_int (1+1));print_newline (); 4+1 ;;
1+1 = 2
- : int = 5
4.3.2 Blocos de programa
Para delimitar grupos de expressoes podemos utilizar alternativamente as
construc oes seguintes:
( expr )
ou
begin expr end
4.3.3 Ciclos
Sintaxe:
for nome = expr1 to expr2 do expr3 done
for nome = expr1 downto expr2 do expr3 done
while expr1 do expr2 done
Exemplos:
49
# let rec emais_emenos n =
print_string "Introduza um numero : ";
let i = read_int () in
if i = n then print_string "BRAVO\n\n"
else
begin
if i < n
then print_string "E+\n" else print_string "E-\n";
emais_emenos n
end ;;
val emais_emenos : int -> unit = <fun>
# for i=10 downto 1 do
print_int i; print_string " "
done;
print_newline() ;;
10 9 8 7 6 5 4 3 2 1
- : unit = ()
# let r = ref 1
in while !r < 11 do
print_int !r ;
print_string " " ;
r := !r+1
done ;;
1 2 3 4 5 6 7 8 9 10 - : unit = ()
4.3.4 Tipagem, aplicacao parcial e fechos
Voltemos agora ao conceito de tipagem fraca, mas desta vez na presenca de
referencias.
Imaginemos que queremos denir e utilizar uma referencia para uma lista.
A sua denic ao podera ser
# let rl = ref [];;
val rl : _a list ref = {contents = []}
# let reset () = rl := [];;
val reset : unit -> unit = <fun>
Nesta situac ao, e de facto impossvel prever o tipo dos elementos da lista
50
referenciada. Tal poder a acontecer quando se juntara o primeiro elemento a
lista referenciada por rl.
Imaginemos que estamos numa situac ao em que nao haja o mecanismo
dos tipos fracos. Ap os a primeira introduc ao de elemento (digamos um in-
teiro, como em rl := 1 ::rl!), ent ao a lista referenciada passa a ser de tipo
int list (ou seja rl teria agora por tipo int list ref).
Se utilizarmos a seguir a func ao reset, a referencia rl apontaria para uma
lista totalmente nova, vazia, logo com a vari avel de tipo por instanciar (de
tipo a list).
Nesta situac ao seria totalmente viavel juntar um caracter ` a lista
(rl := a ::rl!) e assim instanciar o tipo da lista referenciada para
char list.
Neste caso rl teria agora por tipo char list ref ou que introduziria
uma inconsistencia no sistema de tipo: a referencia rl n ao pode ser de dois
tipos fechados (fechados = completamente instanciados) diferentes.
O tipo de val rl : _a list ref = {contents = []} permite evitar
exactamente esta situac ao.
# let rl = ref [];;
val rl : _a list ref = {contents = []}
# let reset () = rl := [];;
val reset : unit -> unit = <fun>
# rl := 1 :: !rl;;
- : unit = ()
# rl ;;
- : int list ref = {contents = [1]}
# reset ();;
- : unit = ()
# rl ;;
- : int list ref = {contents = []}
# rl := a :: !rl;;
Error: This expression has type char but an expression was expected of type
int
Para terminar, vejamos porque os tracos imperativos devem ser mistura-
dos com processos funcionais com muita cautela.
# let f x = rl := x :: !rl; fun y -> y + 1;;
51
# f 5 2;;
- : int = 3
# rl ;;
- : int list ref = {contents = [5]}
# f 6 4;;
- : int = 5
# rl;;
- : int list ref = {contents = [6; 5]}
# let g x = f x;;
val g : int -> int -> int = <fun>
# g 8;;
# rl;;
- : int list ref = {contents = [8; 6; 5]}
# let h = f 9;;
val h : int -> int = <fun>
# rl;;
- : int list ref = {contents = [9; 8; 6; 5]}
# h 7;;
- : int = 8
# rl;;
# h 10;;
- : int = 11
# rl;;
Como podemos ver no exemplo anterior, cada aplica cao completa de f
permite, para alem de devolver o valor inteiro desejado, a execuc ao do efeito
colateral declarada no corpo da funcao. A aplicac ao parcial de f resultante
na func ao h faz com que a execuc ao do efeito colateral seja efectuada uma
s o vez (no momento da denic ao de h), cando assim separada do calculo do
valor inteiro consecutivo. A avaliacao parcial quando combinada com efeitos
colaterais pode dar resultados surpreendentes ` a primeira vista.
Outra manifestac ao dos efeitos subtis da avalia cao quando combinada
com efeitos colaterais e o efeito da ordem de avaliac ao das express oes.
#print_int 1; print_int 2; print_int 3; print_int 4 ;;
52
1234- : unit = ()
# let a = (print_int 1; 1) * (print_int 2; 2) in
let b = (print_int 3; 3) * (print_int 4; 4) in
a + b;;
2143- : int = 14
# let b = (print_int 3; 3) * (print_int 4; 4) in
let a = (print_int 1; 1) * (print_int 2; 2) in
a + b;;
4321- : int = 14
# (print_int 1; 1) * (print_int 2; 2) +
(print_int 3; 3) * (print_int 4; 4);;
4321- : int = 14
Conclus ao, a ordem de avaliac ao de expressoes nao e especicada nos do-
cumento de referencia de OCaml e resulta numa escolha de desenho do com-
pilador utilizado. O programador dever a evitar assim que os seus programas
dependem desta ordem de avaliacao, ou ent ao conhecer bem o compilador
usado.
5 Avaliacao Ansiosa, Avaliacao preguicosa e
estruturas de dados innitas
Uma caracterstica fundamental das linguagens de programac ao e a estrategia
de avaliacao.

E tao fundamental que molda por completo o desenho da
linguagem em causa e ate mesmo a forma de programar na dita.
N ao vamos nesta introducao explicitar toda a envolvente, deveras muito
instrutiva. Aconselhamos o leitor curioso em consultar os manuais classicos
de sem antica das linguagens de programac ao, ou os tratados cl assicos sobre
o calculo lambda.
O conceito de estrategia da avaliacao resume-se ` a escolha de desenho feita
pelo designer da linguagem sobre a forma de calcular (avaliar) uma chamada
a uma funcao. Comecamos por avaliar os parametros ou aguardamos que
estes sejam necessarios na aplicac ao da func ao?.
Por exemplo, para obter o valor de Ackermann (x + 2) (fact 4), op-
tamos por dar prioridade ` a func ao ackermann ou aos seus par ametros?
A primeira escolha nos daria uma redu cao (i.e. um passo de calculo) para:
53
if (x + 2) = 0
then (fact 4) + 1
else if (x + 2) >= 0 && (fact 4) = 0
then ackermann ((x + 2) - 1) 1
else ackermann ((x + 2) - 1) (ackermann (x + 2) ((fact 4) - 1))
enquanto a segunda nos levaria ` a avaliac ao de ackermann x+2 24.
A primeira escolha e designada por avaliac ao preguicosa (lazy evaluation;
no sentido seguinte: avaliamos uma express ao so quando o seu uso se revela
necess ario)
A segunda escolha e designada de avalia cao ansiosa (eager evaluation).
No que diz respeito a avaliacao das chamadas ` a func oes, o desenho da lin-
guagem OCaml repousa, ` a semelhanca de uma vasta gama de linguagens de
programac ao, sobre esta ultima avaliac ao. A avaliac ao ansiosa e mecanismo
de avaliacao por defeito (i.e. implcito). Veremos mas adiante que podemos
no entanto optar explicitamente pela primeira.
Assim antes de explicar mais em detalhe o mecanismo de avaliac ao em
OCaml, citemos um exemplo famoso que abona na avalia cao preguicosa (que
no entanto tem tambem os seus desaos por resolver).
# let ciclo n = while true do () done; n;;
val ciclo : a -> a = <fun>
# let tricky n m = n + 1;;
val tricky : int -> a -> int = <fun>
#(* N~ ao tente isso em casa, esta avalia c~ ao
e feita por especialistas treinados*)
tricky (5 + 2) (ciclo 7);;
Numa linguagem, como Haskell, onde a avalia-
c ao e por defeito preguicosa o resultado teria sido
tricky (5 + 2) (ciclo 7) -> (5 + 2) + 1 -> 8.
5.1 Avaliacao em OCaml
Comecemos por relembrar as regras que oportunamente ao longo deste docu-
mento foram dadas sobre a ordem de avaliac ao em OCaml. Completaremos
este lembrete com alguns aspectos tecnicos relevantes para esta secc ao.
A avaliac ao de uma sequencia de instruc oes (que, lembremos, e separada
por ;) e avaliada da esquerda para a direita.
54
# print_string "1 "; print_string "2 ";print_string "3 "; print_string "4 ";;
1 2 3 4 - : unit = ()
Recordemos os efeitos, de aparencia esoterica, da mistura de efeitos late-
rais (com base por exemplo nestas sequencias) com avaliac ao parcial.
A expressao let x = e1 in e2 e avaliada na seguinte ordem: primeiro
e1, depois a atribui cao do valor e1 ` a variavel x e nalmente e avaliada a
express ao e2. Este caso e mais uma ilustrac ao da avaliacao ansiosa.
# let x = 8;;
val x : int = 8
# let x = print_int x; x + 1 in
let x = print_string "ola"; x + 2 in
print_string ("-->"^string_of_int x^"\n"); x+3;;
8ola-->11
- : int = 14
A express ao if b then e1 else e2 avalia-se da seguinte forma: pri-
meiro e avaliado a expressao b e depois, consoante o valor da avaliac ao de b,
e avaliada a express ao e1 ou (de forma exclusiva) entao e2.
# if true then print_string "ola" else (raise Not_found);;
ola- : unit = ()
Podemos dizer aqui que na express ao if b then e1 else e2 a expres-
s ao b e avaliada de forma ansiosa enquanto e1 e e2 s ao avaliados de forma
preguicosa.
Encontramos este tipo de desenho em outras situacoes em OCaml.
# (true) || (print_string "ola\n"; false);;
- : bool = true
# (false) || (print_string "ola\n"; false);;
ola
- : bool = false
# (false) && (print_string "ola\n"; false);;
- : bool = false
55
A avaliacao de uma express ao, como em f x y z, segue a regra seguinte:
primeiro e avaliada a lista de expressoes (x,y, e z) depois e avaliado a funcao
f com os valores resultantes da avaliac ao de x,y, e z.
Um ponto subtil e importante e referente ` a ordem de avaliac ao da sequen-
cia de expressoes x,y, e z. Esta ordem n ao e especicada. Uma das raz oes
e deixar espaco aos designers de compiladores OCaml para optimiza coes
futuras que podem ser sensveis ` a ordem de avaliac ao destas situac oes.
# let f a b = a + b;;
# let v = f ((1 * 2) + (3 + 4)) ((5 * 6) + (7 + 8));;
val v : int = 54
# let v1 = f (print_string "A"; ( ( print_string "B";1) *
( print_string "C";2)) + (( print_string "D";3) +
( print_string "E";4)))
(print_string "F"; ( ( print_string "G";5) *
( print_string "H";6)) + (( print_string "I";7) +
( print_string "J";8)));;
FJIHGAEDCBval v1 : int = 54
#
Como vemos neste exemplo a vers ao actual da distribui-
c ao de OCaml utilizada avalia listas de express oes (como em
((1 * 2) + (3 + 4)) ((5 * 6) + (7 + 8))) da direita para esquerda.
Esta escolha, num contexto puramente funcional, n ao tem importancia
nenhuma. De facto, em (5 + 6) (7 + 8), avaliar (5 + 6) antes de (7 + 8),
ou vice versa, e irrelevante. Infelizmente num contexto em que se mistura
efeitos co-laterais com computa cao, tal deixa de ser sem consequencias. O
programador dever a ter consciencia desse fenomeno.
5.2 Avaliacao Preguicosa em OCaml
E no entanto possvel, e mesmo facil, ter avaliac ao preguicosa de fun coes em

OCaml de forma ad-hoc.
Para tal pode se usar o mecanismo originalmente designado por thunk
(em ingles designac oes alternativas sao suspension, suspended computation
ou ainda delayed computation, em portugues optaremos por mecanismo de
avaliacao atrasada).
56
Este mecanismo baseia-se na percepc ao de que ambas as expressoes expr e
fun() expr se avaliam sempre para o mesmo valor. A diferenca, essencial,
e que a avalia cao de expr tem lugar no momento da denic ao enquanto a
avaliac ao de fun() expr n ao e realizada no momento da denic ao, mas
sim no momento da sua invocac ao/aplicac ao.
Assim, podemos denir uma func ao preg (para preguica) que transforma
qualquer expressao fechada (i.e. express ao que toma um valor n ao funcional)
em expressao com avaliac ao atrasada. Adaptando igualmente a func ao ciclo
previamente denida por forma a atrasar a sua avaliacao (basta juntar um
ultimo par ametro de tipo unit) ent ao temos de forma ad-hoc a avaliacao
preguicosa.
# let preg x = fun () -> x;;
val preg : a -> unit -> a = <fun>
# let ciclo2 n () =
while true do () done; n;;
val ciclo2 : a -> unit -> a = <fun>
# let tricky2 n m = (n()) + 1;;
val tricky2 : (unit -> int) -> a -> int = <fun>
# tricky2 (preg (5 + 2)) (ciclo2 7);;
- : int = 8
Se este exemplo pode parecer excessivamente articial para ter a avaliacao
preguicosa explicitamente OCaml, citemos dois argumentos que poder ao
aumentar o interesse do programador.
Primeiro, a avaliac ao preguicosa possibilita em certos cen arios optimiza-
c oes obvias (calcular o que e estritamente necess ario calcular e evitar calcular
o que e desnecessario). Permite tambem trabalhar com estruturas de dados
potencialmente innitas.
Segundo, existe um suporte nativo ` a avaliac ao preguicosa em OCaml.
Este e feito com a ajuda ao m odulo Lazy descrito mais adiante.
Mas, antes de descrever este suporte nativo, continuamos com a nossa
explorac ao do innito e mais alem em OCaml. Desta vez ao nvel das
estruturas de dados.
E possvel denir de forma simples estrutura de dados

simples innitas. A questao aqui e que o seu uso num contexto habitual
em OCaml pouco interessante e porque muito limitado ou sujeitos a muitos
riscos...
# let rec l = 1 :: l;;
57
val l : int list =
[1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
...]
# hd l;;
- : int = 1
# tl l;;
- : int list =
[1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...]
# (* J a foi avisado, nada disso em casa...*)
length l;;
(* \infty + 1 ...*)
Uma ilustrac ao destes limites pode ser a seguinte.
# let rec l = let n = ref (-1) in (n:=!n+1; !n)::l;;
val l : int list =
58
[0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0;
...]
# let rec l = let v = try hd l with _ -> 0 in (v+1)::l;;
Characters 13-53:
let rec l = let v = try hd l with _ -> 0 in (v+1)::l;;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This kind of expression is not allowed as right-hand side of let rec
Ent ao, ` a semelhanca da avaliacao preguicosa de fun coes, como podemos
denir estruturas de dados innitas e manipula-las de forma segura?
# type a fluxo = Nil | Cons of a * (unit -> a fluxo);;
type a fluxo = Nil | Cons of a * (unit -> a fluxo)
# let rec de n = Cons (n, fun () -> de (n+1));;
val de : int -> int fluxo = <fun>
# let cab s = match s with Nil -> failwith "cab" | Cons (x,_) -> x;;
val cab : a fluxo -> a = <fun>
# let cau s = match s with Nil -> failwith "cau" | Cons (_,y) -> y();;
val cau : a fluxo -> a fluxo = <fun>
# let rec n_esimo s n = if n=0 then cab s else n_esimo (cau s) (n-1);;
val n_esimo : a fluxo -> int -> a = <fun>
# let from_list l = fold_right (fun x s -> Cons (x, fun () -> s)) l Nil;;
val from_list : a list -> a fluxo = <fun>
# let rec from_function f = Cons (f(), fun () -> (from_function f));;
val from_function : (unit -> a) -> a fluxo = <fun>
# let rec toma s n =
if n <= 0 then [] else
59
match s with
Nil -> []
| _ -> cab s :: toma (cau s) (n -1);;
val toma : a fluxo -> int -> a list = <fun>
# let rec map f s = match s with Nil -> Nil
| _ -> Cons (f (cab s), fun () -> map f (cau s));;
val map : (a -> b) -> a fluxo -> b fluxo = <fun>
# let rec filtro f s =
match s with
Nil -> Nil
| Cons (x,g) ->
if f x then Cons (x,fun () -> filtro f (g ()))
else filtro f (g ());;
val filtro : (a -> bool) -> a fluxo -> a fluxo = <fun>
Experimentemos estas funcoes sobre os uxos.
# let rec uns = Cons (1,(fun () -> uns));;
val uns : int fluxo = Cons (1, <fun>)
# toma uns 10;;
- : int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1]
# cab uns;;
- : int = 1
# n_esimo uns 4;;
- : int = 1
# let cont = ref 0;;
val cont : int ref = {contents = 0}
# let incr () = cont:= !cont +1 ; !cont;;
val incr : unit -> int = <fun>
# let fl = from_function incr;;
val fl : int fluxo = Cons (1, <fun>)
# n_esimo fl 8;;
- : int = 9
# let inteiros = de 0;;
val inteiros : int fluxo = Cons (0, <fun>)
# toma inteiros 15;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14]
# toma (map fact inteiros) 14;;
60
- : int list =
[1; 1; 2; 6; 24; 120; 720; 5040; 40320; 362880; 3628800; 39916800; 479001600;
-215430144]
# let par n = n mod 2 = 0;;
val par : int -> bool = <fun>
# toma (filtro par inteiros) 20;;
- : int list =
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24; 26; 28; 30; 32; 34; 36; 38]
# let fib =
let rec fibgen a b = Cons (a,fun () -> fibgen b (a+b)) in fibgen 1 1;;
val fib : int fluxo = Cons (1, <fun>)
# toma fib 15;;
- : int list = [1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610]
# n_esimo fib 12345;;
- : int = 351394967
#(*remover multiplos de n do fluxo*) let del_mult n = filtro (fun m -> m mod n <> 0);;
val del_mult : int -> int fluxo -> int fluxo = <fun>
# let rec crivo s =
match s with Nil -> Nil
| Cons (p,g) -> Cons (p , fun () -> crivo (del_mult p (g())));;
val crivo : int fluxo -> int fluxo = <fun>
# let primos = crivo (de 2);;
val primos : int fluxo = Cons (2, <fun>)
# toma primos 30;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97; 101; 103; 107; 109; 113]
# n_esimo primos 10000;;
- : int = 104743
5.3 O Modulo Lazy
Reconsideremos o nosso exemplo tricky e tentemos generalizar o nosso tra-
tamento das avaliacoes atrasadas.
# type a pregv =
Avaliado of a
| Atrasado of (unit -> a);;
61
type a pregv = Avaliado of a | Atrasado of (unit -> a)
# type a pregt = {mutable c: a pregv};;
type a pregt = { mutable c : a pregv; }
# let avalia e =
match e.c with
Avaliado x -> x
| Atrasado f -> let u = f () in e.c <- Avaliado u; u;;
val avalia : a pregt -> a = <fun>
# let preg = fun x -> {c = Atrasado (fun () -> x)};;
val preg : a -> a pregt = <fun>
o tipo pregv agrupa os valores avaliados de forma preguicosa. Ou estes
est ao avaliados ou est ao a espera de serem avaliados.
O tipo pregt encapsula um valor pregui coso, ou seja representa um fecho
de um valor preguicoso.
Dotamo-nos tambem de duas func oes. Uma, que nos e j a familiar, preg
permite encapsular uma expressao numa envolvente preguicosa. A funcao
avalia trata de forcar a avaliac ao de uma express ao pregui cosa. Se esta ja
se encontra avaliada entao o valor e novamente retornado.
Equipado com estas denicoes podemos, assim o esperamos, denir fun-
c oes com avaliacao preguicosa de uma forma menos ad-hoc. Para ns de
ilustra cao, tentemos redenir a func ao factorial nestes termos. Para isso
redenimos igualmente a condicional if then else de forma preguicosa.
# let se_atrasado b e1 e2 = if avalia b then avalia e1 else avalia e2;;
val se_atrasado : bool pregt -> a pregt -> a pregt -> a = <fun>
# let rec fact_atrasado1 n =
se_atrasado
(preg (n=0))
(preg 1)
(preg (n*(fact_atrasado1 (n-1))));;
val fact_atrasado1 : int -> int = <fun>
# fact_atrasado1 3;;
Stack overflow during evaluation (looping recursion?).
Correu inesperadamente mal (ser a???)... mas porque?
O fenomeno, j a presentes em exemplos anteriores, explica-se pelo facto de
estarmos a misturar avaliac ao ansiosa com avaliacao preguicosa. De facto a
62
avaliac ao de (preg (n*(fact_atrasado1 (n-1)))) e feito de forma ansiosa,
mesmo se o retorno e uma expressao preguicosa. Logo looping recursion...
Se queremos evitar este fen omeno, temos de optar pela denic ao seguinte:
# let rec fact_atrasado n =
se_atrasado
{c=Atrasado (fun () -> (n=0))}
{c=Atrasado (fun () -> 1)}
{c=Atrasado (fun () -> (n*(fact_atrasado (n-1))))};;
val fact_atrasado : int -> int = <fun>
# fact_atrasado 3;;
- : int = 6
O que torna a utilidade de preg muito relativa.

E para contrariar este
fen omeno que o m odulo Lazy providencia um tipo Lazy.t (em todo seme-
lhante ao nosso tipo pregt), a construcao lazy e a fun cao force (para alem
de algumas variantes, que podem ser consultadas no manual de referencia).
Esta ultima e equivalente ` a funcao avalia. A construc ao lazy (e uma pa-
lavra chave providenciada por este m odulo, nao e uma func ao no sentido
cl assico) tem o mesmo papel do que a func ao preg mas sem o seu grande
inconveniente: o seu par ametro n ao e avaliado.
Tal n ao deve ser considerado pelo leitor como uma excepc ao ao meca-
nismo de avalia cao de chamadas ` a func oes de OCaml. A expressao lazy x
e simplesmente entendido como uma directiva ao preprocessador de OCaml
para a sua substitui cao em algo como {c=Atrasado (fun () -> x)}.
# open Lazy;;
# let ciclo = fun n -> (while true do () done; n);;
val ciclo : a -> a = <fun>
# let tricky = fun n m -> (force n) + 1;;
val tricky : int Lazy.t -> a -> int = <fun>
# tricky (lazy (5 + 2)) (lazy (ciclo 7));;
- : int = 8
5.4 Streams: uxos ou listas innitas em OCaml
Os uxos (stream na terminologia OCaml) s ao listas polimorcas de ele-
mentos de mesmo tipo, potencialmente innitas.
63
S ao a solu cao OCaml para as listas innitas que descrevemos anterior-
mente nesta secc ao. Como tal s ao tambem preguicosas.
OCaml oferece esta funcionalidade pelo intermedio do seu preprocessa-
dor, o camlp4. Como tal a opcao -pp camlp4o dever a estar presente na linha
de comando de qualquer compilacao de programa usando uxos.
O tipo dos uxos em si e abstracto (encapsulado no m odulo Stream). Este
comportamento e uma consequencia evidente do seu estatuto preguicoso (ou
a sua natureza innita). O valores s ao fornecido à pedido explcito. Para ter
acesso aos uxos e as suas diversas constru coes deveremos ent ao recorrer às
funcoes oferecidas por este m odulo.
5.4.1 Construcao
O uxo vazio tem sintaxe por [<>]. Um uxo apresentando a sequencia 1,
2, 3 e 4 dene-se por [<1; 2; 3; 4>].
Qualquer expressao que n ao seja precedida por uma ap ostrofe e conside-
rada como um sub-uxo do uxo considerado.
Assim [<1; 2; [< 3 ; 4; 5>]; 6 ; 7>] =
[<1; 2; 3 ; 4; 5; 6 ; 7>]
# #load "dynlink.cma";;
# #load "camlp4o.cma";;
Camlp4 Parsing version 3.11.2
# let concat a b = [<a;b>];;
val concat : a Stream.t -> a Stream.t -> a Stream.t = <fun>
# concat [<1; 2; [< 3 ; 4; 5>] >] [<6 ; 7>];;
- : int Stream.t = <abstr>
# let rec nat_from n = [<n ; nat_from (n+1) >];;
val nat_from : int -> int Stream.t = <fun>
# let inteiros = nat_from 0;;
val inteiros : int Stream.t = <abstr>
O modulo Stream apresenta 4 func oes de base para a construc ao de uxos
a partir de produtores de elementos externos.
val from : (int -> a option) -> a Stream.t
val of_list : a list -> a Stream.t
val of_string : string -> char Stream.t
64
val of_channel : in_channel -> char Stream.t
Stream.from f devolve um uxo alimentado pela funcao f. A func ao em
causa tem por requisito principal devolver Some x enquanto houver elemento
por considerar, e devolver None quando o uxo tem de terminar.
As funcoes of_list, of_string e of_channel funcionam da forma espe-
rada (um uxo e criado com base no parametro, e a ordem dos elementos e
conservada).
5.4.2 Consumo e percurso de uxos
Para a explorac ao de um uxo o modulo nos fornece a func ao next que
devolve o elemento ` a cabeca do uxo considerado. De reter o efeito lateral
que e o consumo do elemento extrado.
# next inteiros;;
- : int = 0
# next inteiros;;
- : int = 1
# next [<>];;
Exception: Stream.Failure.
De forma geral, o percurso de um uxo e destrutivo. Cada valor extrado
e consumido (removido do uxo).
Assim se explica o comportamento da funcao empty que testa se o uxo
em parametro e vazio ou n ao.
# empty [<>];;
- : unit = ()
# empty inteiros;;
Neste caso este comportamento assegura que o uxo em par ametro nao e
consumido (pela forma com que esta func ao e implementada e se comporta).
Uma fun cao util e a fun cao iter (com a assinatura seguinte
val iter : (a -> unit) -> a Stream.t -> unit) que varre o uxo
todo, aplicando a fun cao f a cada elemento consumido. Obviamente o seu
uso requer algumas precauc oes (o uxo pode ser innito...).
65
# let v = [<1;2;3;4>];;
val v : int Stream.t = <abstr>
# Stream.iter (fun x -> print_endline (string_of_int x)) v;;
1
2
3
4
- : unit = ()
# next v;;
Vamos ilustrar algumas outras func oes disponveis com base em exemplos
simples. Para mais informa cao, convida-se o leitor à consulta do manual de
referencia.
# let v = [<1;2;3;4;5;6;7;8;9;10;11;12;13>];;
val v : int Stream.t = <abstr>
# peek v;;
- : int option = Some 1
# next v;;
- : int = 1
# junk v;;
- : unit = ()
# next v;;
- : int = 3
# (* how many element where discarded until now*)
count v;;
- : int = 3
# next v;;
- : int = 4
# npeek 3 v;;
- : int list = [5; 6; 7]
# next v;;
- : int = 5
5.4.3 Filtragem destrutiva de uxos
Para programar sobre uxos OCaml fornece um mecanismo de ltragem
adaptado ` as particularidades desta estrutura, a ltragem destrutiva. Realca-
66
se que qualquer motivo ltrado e consumido do uxo.
A sintaxe e
match fluxo with parser
[< p1 >] -> expr1
| ...
| [<pn >] -> exprn
Em alternativa, e a semelhanca do mecanismo de l-
tragem na denic ao de func ao, podemos usar a sintaxe
parser [< p1 >] -> expr1 | ... | [<pn >] -> exprn.
Com base neste mecanismo, podemos redenir a func ao next.
# let prox s = match s with parser [< x >] -> x;;
val prox : a Stream.t -> a = <fun>
# prox v;;
- : int = 6
# let new_prox = parser [< x >] -> x;;
val new_prox : a Stream.t -> a = <fun>
# new_prox v;;
- : int = 7
Uma consequencia interessante da natureza destrutiva dos uxos e a l-
tragem do uxo vazio. De facto dado um uxo s, este e sempre igual a
[< [<>]; s >]. Logo e sempre possvel encontrar o motivo [<>] ` a cabeca
de qualquer uxo.
Assim, o motivo [<>] tem o papel do motivo wildcard _ nas ltragens
tradicionais. Logo, num conjunto de motivos, o motivo [<>] tem de ser
considerado em ultima posi cao. Assim:
# let rec aplica f s = match s with parser
[<x ; cont>] -> f x ; aplica f cont
| [<>] -> ();;
val aplica : (a -> b) -> a Stream.t -> unit = <fun>
# let rec aplica f s = match s with parser
[<x >] -> f x ; aplica f s
| [<>] -> ();;
val aplica : (a -> b) -> a Stream.t -> unit = <fun>
67
Real ca-se o facto da segunda vers ao de aplica (uma variante da func ao
iter) tirar proveito do consumo de x do uxo (ou seja s e de facto igual a
cont depois da ltragem do primeiro motivo).
Vejamos agora outro fen omeno interessante. Tentemos denir a func ao
que nos diz se o comprimento de um uxo e par ou n ao. Obviamente esta
funcao tem uma utilidade duvidosa em casos de uxo innito.
# let rec comp_par s = match s with parser
[<x ;y>] -> comp_par s
| [<z >] -> false
| [<>] -> true;;
Characters 78-80:
| [<z >] -> false
^^
Warning U: this match case is unused.
val comp_par : a Stream.t -> bool = <fun>
# comp_par [<1; 1; 1; 1;1>];;
Exception: Stream.Error "".
A mensagem de aviso j a deveria nos preocupar... e de facto uma execuc ao
simples revela o problema.
A origem e simples, mas subtil. Ao tentar emparelhar o uxo nal (no
qual s o resta um unico 1) o primeiro motivo e experimentado. Claro este
falha porque s o h a um elemento. De facto o que acontece e o seguinte:
O emparelhamento e destrutivo. Logo o ultimo 1 foi consumido, com su-
cesso, via o padr ao x e a tentativa de emparelhar o y fracassa.
E esta situac ao
que provoca a excepcao (e o aviso de que o padrao seguinte nao serve para
nada).
A soluc ao e Nunca ignorar uma mensagem de aviso e aninhar ltragens.
# let rec comp_par s = match s with parser
[<x >] ->
(match s with parser
[<y >] -> comp_par s
| [<>] -> false)
| [<>] -> true;;
val comp_par : a Stream.t -> bool = <fun>
# comp_par [<1; 1; 1; 1;1>];;
- : bool = false
68
Para terminar mostramos uma caracterstica muito interessante da ltra-
gem de motivo: o consumo Cavaco Silva. Ou seja o consumo interno, porque
o que e nosso e bom.
# let rec comprimento s = match s with parser
[<x; c = comprimento >] -> 1 + c
| [<>] -> 0;;
val comprimento : a Stream.t -> int = <fun>
# comprimento [<1; 1; 1; 1;1>];;
- : int = 5
Esta func ao poderia ter sido escrita classicamente como:
# let rec comprimento s = match s with parser
[<x >] -> 1 + (comprimento s)
| [<>] -> 0;;
val comprimento : a Stream.t -> int = <fun>
# comprimento [<1; 1; 1; 1;1>];;
- : int = 5
Veremos mais adiante, na sec cao dos exemplos completos, que esta pe-
quena caracterstica torna o uso dos uxos muito interessante.
6 Modulos
Esta secc ao e fortemente baseada nos apontamentos cedidos gen-
tilmente por Jean-Christophe Filli atre (Initiation ` a la programma-
tion fonctionnelle. Master Informatique M1, Universite Paris-Sud.
http://www.lri.fr/~filliatr/m1/cours-ocaml.en.html).
Quando os programas tornam-se grandes,e importante que a linguagem
de programac ao de suporte forneca boas ferramentas de Engenharia de Soft-
ware. Tais ferramentas dever ao, em particular, permitir uma estruturac ao
do codigo em unidades de tamanho razoavel (modularidade), ocultar a re-
presentac ao concreta de certos dados (encapsulamento) e evitar da melhor
forma a duplicac ao de c odigo.
Existe diversas formas para atingir tais objectivos. Na programac ao ori-
entada ` a objectos, as classes e os conceitos associados asseguram esse suporte.
Em OCaml, para alem da camada objecto existente, estas funcionalidades
s ao alternativamente suportadas pelo sistemas de modulos.
69
Como o nome de modulo o sugere, um m oduloe essencialmente uma forma
de introduzir modularidade num programa, i.e. de o estruturar em unidades
de tamanho razo avel.
6.1 Ficheiros e modulos
A unidade programatica mais simples no contexto dos m odulose o cheiro.
Em OCaml, cada cheiro constitu um m odulo diferente. Se este, digamos
arith.ml, conter um determinado n umero de declarac oes,
let pi = 3.141592
let round x = floor (x +. 0.5)
ent ao a compilac ao deste cheiro, visto como um m odulo, faz-se invocando
uma compilac ao sem edic ao de liga coes gra cas à op cao -c do compilador
(como no caso do gcc).
% ocamlc -c arith.ml
O resultado desta compila cao e composta por dois cheiros: arith.cmo
contendo o c odigo e arith.cmi contendo a sua interface (.i.e. uma constante
pi de tipo float e uma func ao round de tipo float -> float).
O nome do moduloe o nome do cheiro, iniciado por uma mai uscula. No
caso concreto do exemplo,e Arith.
Podemos assim referenciar os elementos deste m odulo noutro cheiro
OCaml pelo uso da notac ao Arith.x. Assim podemos utilisar o m odulo
Arith num cheiro main.ml :
let x = float_of_string (read_line ());;
print_float (Arith.round (x /. Arith.pi));;
print_newline ();;
e compilar este ultimo da seguinte forma:
% ocamlc -c main.ml
70
Para que esta compila cao seja bem sucedidae necessario que o m odulo
Arith esteja previamente compilado. De facto, quandoe encontrada uma
referencia a um elemento do modulo, como aqui Arith.pi, o compilador
procura um cheiro de interface arith.cmi. Podemos assim realizar a edicao
das ligac oes, fornecendo os dois cheiros de c odigo ao compiladorOCaml:
% ocamlc arith.cmo main.cmo
Uma forma alternativa possvel teria sido compilar directamente
omain.ml e assim realizar a compilac ao do cheiro de uma s o vez.
% ocamlc arith.cmo main.ml
Ou ainda realizar a compilac ao de ambos os cheiros fontes e a edi cao
das ligac oes de uma s o vez.
% ocamlc arith.ml main.ml
Neste ultimo caso os cheiros sao compilados na ordem apresentada, logo
a dependencia do ultimo cheiro sobre o primeiroe respeitada e produz assim
o efeito desejado.
6.2 Encapsulamento
Os m odulos, na sua vers ao cheiro, permitam a estrutura cao de um programa
(em unidades de codigo). Mas os modulos permitam muito mais do que isso,
por exemplo o encapsulamento, i.e. a ocultac ao de determinados detalhes
de c odigo. De facto,e possvel fornecer uma interface aos m odulos denidos.
Neste caso so os elementos declarados na interface ser ao visveis, à semelhan ca
do mecanismo Java representado pela palavra chave private que permite
controlar (limitar, aqui) a visibilidade dos atributos ou dos metodos.
Para tal, coloca-se a interface num cheiro com a extensao .mli na mesma
pasta onde se encontra o cheiro fonte (de extens ao .ml).
Assim podemos querer exportar somente a func ao round do m odulo Arith
previamente denido, criando o cheiro arith.mli com o conte udo:
val round : float -> float
71
Constata-se que a sintaxee a mesma que a sintaxe utilizada pelo toplevel
de OCaml na sua interacc ao (na resposta para ser mais preciso) com o
programador.
Este cheiro interface deve ser convenientemente compilado antes do -
cheiro c odigo.
% ocamlc -c arith.mli
% ocamlc -c arith.ml
Aquando da compilac ao do codigo, o compilador vericar a a adequac ao
dos tipos entre os elementos declarados na interface e os elementos de facto
fornecidos no codigo.
No caso do exemplo anterior, compilar o modulo main.ml resultar a no
erro:
% ocamlc -c main.ml
File "main.ml", line 2, characters 33-41:
Unbound value Arith.pi
No entanto a constante pi permanece obviamente visvel e acessvel aos
elementos presentes no cheiro arith.ml.
A interface n ao se limita na restric ao dos valores exportados. Permite
tambem restringir os tipos exportados ou ate mesmo na denicao destes.
Suponhamos que queiramos programar uma pequena biblioteca sobre con-
juntos de inteiros representados por listas. O c odigo poderia ser constitudo
pelo cheiro ensemble.ml seguinte:
type t = int list
let vazia = []
let junta x l = x :: l
let pertence = List.mem
e uma interface possvel seria:
type t = int list
val vazia : t
val junta : int -> t -> t
val pertence : int -> t -> bool
72
Aqui a denic ao do tipo t n aoe de nenhuma utilidade, excepto, eventu-
almente, facilitar a leitura da interface pela identicac ao dos conjuntos ao
tipo t. Sem a mencao do tipo, o compilador teria inferido ele pr oprio esta
informacao e poderia ter entao atribudo um tipo mais geral mas compatvel
com as func oes vazia, junta e pertence.
Mas podemos tambem querer esconder a representac ao escolhida do tipo
t, dando na interface o conte udo seguinte:
type t
val vazia : t
val junta : int -> t -> t
val pertence : int -> t -> bool
Um tal tipo designa-se de tipo abstracto. Dentro do cheiro ensemble.ml
a representac ao do tipo te conhecida, forae desconhecida.

E uma noc ao
essencial sobre a qual nos debrucaremos mais adiante aquando da exploracao
da nocao de persistencia.
O facto de abstrair o tipo t esconde por completo a forma como os va-
lores deste tipo s ao formados. Se procuramos processar um valor do tipo
Ensemble.t como uma lista de inteiros fora do dito cheiro, obteremos um
erro.
Assim, podemos modicar a codicac ao da nocao de conjunto sem nunca
perturbar os programas que usam as funcionalidades fornecidas pelo modulo
Ensemble.
6.2.1 Compilacao separada
A linguagem OCaml permite de facto a compilacao separada. Isto e, a
compila cao dum cheiro so depende das interfaces dos modulos que menciona
e n ao do codigo que lhe estao associadas.
Assim se um m odulo B utiliza um m odulo A, uma altera cao do c odigo
do m odulo A n ao obriga a recompilac ao do m odulo B. Somente uma altera-
c ao da interface de A justicaria tal recompilac ao. Isto porque seria, neste
caso, necessario vericar se altera coes aos tipos dos valores exportados por A
preservam a boa tipicacao de B.
A compilac ao separada representa um ganho de tempo consider avel para
o programador. Neste contexto e para um projecto constitudo por cem -
73
cheiros OCaml, uma altera cao do codigo s o implicar a uma unica compila cao
e uma edic ao de ligac oes para reconstruir o execut avel.
6.2.2 Linguagem de modulos
Uma das for cas do sistema de m odulos de OCaml e ele nao se limitar aos
cheiros. Podemos de facto denir um novo m odulo da mesma forma que
podemos denir um tipo, uma constante, uma func ao ou uma excepc ao.
Assim pode mos escrever:
module M = struct
let c = 100
let f x = c * x
end
A palavra chave module introduz aqui a declaracao de um novo m odulo,
M, cuja denicaoe o bloco iniciado por struct e concludo por end.
Tal blocoe designado de estrutura (o que justica a palavra chave struct)
ee composto de uma sequencia de declarac oes e/ou de expressoes OCaml,
exactamente como no caso dum programa OCaml. Tais declara coes de
m odulos podem ser misturadas com outras declarac oes e ate mesmo serem
aninhadas e assim conter outras declaracoes de modulos. Poderamos assim
escrever algo como:
module A = struct
let a = 2
module B = struct
let b = 3
let f x = a * b * x
end
let f x = B.f (x + 1)
end
Tais m odulos locais ganham particular import ancia com a utiliza cao
dos functores que serao abordados mais adiante na seccao seguinte. Mas
podemos desde j a constatar que estes permitam uma organizac ao do espaco
de nomes. Assim no exemplo anterior, pudemos denir duas func oes de nome
f, porque a func ao denida no m odulo B n aoe imediatamente visvel no corpo
do m odulo A.

E necess ario qualicar, com a notacao B.f, para de facto ter
acesso a tal funcao dentro do modulo A.
74
Podemos assim servirmo-nos dos m odulos locais para agrupar determina-
dos tipos e func oes interligados e dar-lhes nomes genericos (como add, find,
etc.) porque a qualicac ao permite-lhes serem distinguidos de outras fun coes
com o mesmo nome.
Quando tais valores s ao referenciados frequentemente, podemos evitar
a qualicac ao sistematica pelo nome do m odulo abrindo explicitamente o
m odulo com a ajuda do comando open. A consequencia desta aberturae
tornar visveltodos os elementos deste m odulo.
Assim, no lugar da invocacao sistem atica Printf.printf, preferiremos
abrir o modulo Printf no inicio do cheiro :
open Printf
...
let print x y = printf "%d + %d = %d\n" x y (x+y)
...
Assinaturas
`
A semelhanca de qualquer outra declarac ao, as declarac oes de m odulos sao
tipicadas (i.e. os m odulos tem tipos).
O tipo de um m odulo designa-se por assinatura. A sintaxe de uma assina-
turae identica à de uma interface (os cheiros .mli) ee iniciada pela palavra
chave sig e terminada pela palavra chave end. Constatamo-lo na seguinte
declara cao no toplevel:
# module M = struct let a = 2 let f x = a * x end;;
module M : sig val a : int val f : int -> int end
E l ogico que a sintaxe seja identica a de uma interface porque uma inter-
face n aoe nada mais de que o tipo de um m odulo-cheiro.
Da mesma forma que se pode denir modulos locais, podemos denir
assinaturas:
# module type S = sig val f : int -> int end;;
module type S = sig val f : int -> int end
Podemos ent ao servirnos de tais assinaturas para tipicar explicitamente
as declaracoes de m odulos:
# module M : S = struct let a = 2 let f x = a * x end;;
module M : S
75
O interesse de tais declara coese o mesmo que o interesse das interfaces:
rstringir os valores ou tipos exportados (que designamos anteriormente de
encapsulamento). Aqui o valor M.a deixou de ser visvel:
# M.a;;
Unbound value M.a
Resumo
O sistema de modulos OCaml permite
modularidade, pela estruturacao do c odigo em unidades designadas de
modulos;
encapsulamento de tipos e valores, e em particular da denic ao de tipos
abstractos;
uma verdadeira compilacao separada;
uma organizac ao do espaco de nomes.
6.3 Functores
Da mesma forma que uma func ao OCaml pode ser generica relativamente
aos tipos dos seus par ametros (polimorsmo) ou às func oes em par ametro
(ordem superior), um modulo pode ser parametrizado por um ou mais outros
m odulo. Um tal m odulo designa-se por functor.
Para devidamente justicar a utilidade dos functores, o mais simples e
ilustra-los por um exemplo.
Suponhamos que queiramos codicar em OCaml uma tabela de hash da
forma mais generica possvel por forma a que esse c odigo possa ser utilizado
em qualquer circunstancia em que uma tabela de hash possa ser util.
Para issoe preciso parametrizar o codigo por uma fun cao de de hash (para
a insercao na tabela e a pesquisa) e por uma func ao de igualdade (para a
pesquisa)
5
.
Poderamos ent ao imaginar utilizar a ordem superior e parametrizar todas
as func oes do nosso m odulo por estas duas funcoes, o que resultaria numa
interface da forma:
5
Acontece que OCaml predene uma fun cao de igualdade e uma funcao de hash poli-
morca, mas em algumas situa coes o programador pode desejar utilizar funcoes diferentes.
76
type a t
(* o tipo abstracto das tabelas de hash contendo elementos de
tipo "a" *)
val create : int -> a t
(* "create n" cria uma nova tabela de hash de tamanho inicial "n" *)
val add : (a -> int) -> a t -> a -> unit
(* "add h t x" junta o valor "x" na tabela "t" com a ajuda da
func~ ao de hash "h" *)
val mem : (a -> int) -> (a -> a -> bool) -> a t -> a -> bool
(* "mem h eq t x" testa a ocorr^ encia de "x" na tabela "t" para a
func~ ao de hash "h" e a igualdade "eq" *)
Para alem do aspecto pesado, esta interface tem os seus perigos: de facto
podemos juntar um elemento na tabela com uma certa fun cao de hash e de-
pois pesquisar nesta mesma tabela com outra funcao de hash. O resultado
seria errado, mas o sistema de tipos de OCaml n ao teria excludo esta utili-
zac ao incorrecta (de facto, apesar do argumento apresentado, esta utilizac aoe
bem tipicada).
Uma solu cao mais satisfat oria consistiria em atribuir uma fun cao de hash
no momento da criac ao da tabela de hash. Estas seriam entao agrupadas
na estrutura de dados e utilizadas pelas operacoes de cada vez que seria
necess ario.
A interface caria ent ao mais razo avel:
type a t
(* o tipo abstracto das tabelas de hash contendo elementos de
tipo "a" *)
val create : (a -> int) -> (a -> a -> bool) -> int -> a t
(* "create h eq n" cria uma nova tabela de hash de tamanho
inicial "n", com "h" como func~ao de hash e "eq" como
func~ ao de igualdade *)
val add : a t -> a -> unit
(* "add t x" junta o dado "x" na tabela "t" *)
val mem : a t -> a -> bool
(* "mem t x" testa a ocorr^ encia de "x" na tabela "t" *)
A representa cao interna da codicac ao poderia se assemelhar a algo como:
77
type a t = { hash : a -> int; eq : a -> a -> bool; data : a list array }
let create h eq n = { hash = h; eq = eq; data = Array.create n [] }
...
No entanto, tal codicac ao ainda tem os seus defeitos. Por comecar,
o acesso às func oes de hash e de igualdade fazem-se necessariamente pelo
intermedio de fechos e como tal penaliza a execuc ao relativamente a fun coes
conhecidas estaticamente. Por outro lado a estrutura de dados codicando
a tabela contem agora func oes e por esta raz ao torna-se complicado escrever
tal representacao em dispositivos fsicos, como o disco, e reler posteriormente
(e tecnicamente possvel, mas com recurso a importantes restri coes).
Felizmente, os functores trazem aqui uma soluc ao muito satisfatoria. Por-
que pretendemos parametrizar as nossas tabelas de hash por um tipo (o dos
seus elementos) e duas fun coes, vamos escrever um m odulo parametrizado
por um outro m odulo contendo estes tres requisitos. Tal functor F, parame-
trizado por um m odulo X com assinatura S, introduz-se com a sintaxe
module F(X : S) = struct ... end
No caso do nosso exemplo a assinatura Se a seguinte:
module type S = sig
type elt
val hash : elt -> int
val eq : elt -> elt -> bool
end
e a codicacao das tabelas de hash pode entao se escrever da seguinte
forma:
module F(X : S) = struct
type t = X.elt list array
let create n = Array.create n []
let add t x =
let i = (X.hash x) mod (Array.length t) in t.(i) <- x :: t.(i)
let mem t x =
let i = (X.hash x) mod (Array.length t) in List.exists (X.eq x) t.(i)
end
78
Constatamos que no corpo do functor, acedemos aos elementos do
m odulo-parametro X exactamente como se de um m odulo (como denido
mais acima) se tratasse. O tipo do functor F explicita o par ametro X com a
mesma sintaxe:
module F(X : S) : sig
type t
(* O tipo abstracto das tabelas de hash contendo elemento de tipo
"X.elt" *)
val create : int -> t
(* "create h eq n" cria uma nova tabela de tamanho inicial "n" *)
val add : t -> X.elt -> unit
(* "add t x" junta o valor "x" na tabela "t" *)
val mem : t -> X.elt -> bool
(* "mem t x" testa a ocorr^ encia de "x" na tabela "t" *)
end
Podemos ent ao instanciar o functor F com um qualquer modulo escolhido
pelo programador, desde que respeite as assinaturas pretendidas.
Assim se desejamos uma tabela de hash para arquivar inteiros, podemos
comecar por denir um m odulo Integers com assinatura S :
module integers = struct
type elt = int
let hash x = abs x
let eq x y = x=y
end
Podemos, a seguir, aplicar o functor F sobre este module :
module Hintegers = F(Integers)
Constatamos assim que a denic ao de um m odulo n ao est a limitado a
uma estrutura: trata-se de uma aplicac ao de um functor.
Podemos entao utilizar o m odulo Hintegers como qualquer outro m odulo
:
79
# let t = Hintegers.create 17;;
val t : Hintegers.t = <abstr>
# Hintegers.add t 13;;
- : unit = ()
# Hintegers.add t 173;;
- : unit = ()
# Hintegers.mem t 13;;
- : bool = true
# Hintegers.mem t 14;;
- : bool = false
...
6.3.1 Aplicacoes
As aplicacoes dos functores s ao m ultiplas. Utilizam-se em particular para
denir:
1. estruturas de dados parametrizadas por outras estruturas de dados
OCaml oferece tres deste functores na sua biblioteca standard:
Hashtbl.Make : tabelas de hash semelhantes ` as do exemplo ante-
rior;
Set.Make : conjuntos nitos codicados com base em arvores ba-
lenceadas;
Map.Make : tabelas de associa cao codicadas com base em arvores
balenceadas.
2. algoritmos parametrizados por estruturas de dados
Podemos por exemplo escrever o algoritmo de Dijkstra de procura de
caminho mais curto num grafo sob a forma de um functor parametri-
zado pela estrutura de dados representando o grafo em si. O tipo de
tal functor poderia ser:
module Dijkstra
(G : sig
type graph (* tipo dos grafos *)
type vertice (* tipo dos vertices *)
80
val vizinho : graph -> vertice -> (vertice * int) list
(* conjunto dos vizinhos com peso nas arestas *)
end) :
sig
val shortest_path :
G.graph -> G.vertice -> G.vertice -> G.vertice list * int
(* "shortest_path g a b" procura o caminho mais curto de
"a" para "b" em "g" *)
end
Vemos assim que os functores sao uma ferramenta poderosa para a reu-
tilizac ao de c odigo, porque permite a sua escrita de forma muito generica.
Os functores podem ser comparados, em certos aspectos, aos templates de
C++,mesmo se ha tambem diferencas numerosas e not orias.
De notar que o sistema de modulos de OCaml e, na realidade, indepen-
dente da linguagem de base. Forma uma linguagem por si s o, que poderia
ser aplicado a outra linguagem. Em particular ele poderia ser desdobrado
estaticamente para dar um c odigo sem m odulos nem functores, mesmo se na
pratica naoe isso que acontece.
7 Persistencia
Esta secc ao e fortemente baseada nos apontamentos cedidos gen-
tilmente por Jean-Christophe Filli atre (Initiation ` a la programma-
tion fonctionnelle. Master Informatique M1, Universite Paris-Sud.
http://www.lri.fr/~filliatr/m1/cours-ocaml.en.html).
Nesta sec cao abordaremos um aspecto essencial das estruturas de dados,
a persistencia. Esta nocao nao e especca à programacao OCaml, nem, ate,
da programa cao funcional, mas e de facto natural nesta famlia de linguagens.
7.1 Estruturas de dados imutaveis
Como ja foi referido, muitas das estruturas de dados OCaml s ao imuta-
veis. Isto e, nao s ao alteraveis uma vez construdas. Este facto tem uma
consequencia muito importante: um valor de tal tipo nao e afectado pelas
81
operacoes das quais e par ametro. Novos valores s ao construdos e devolvidos
por estas ultimas.
Ilustremos este facto por exemplos simples.
Se denirmos uma lista l por let l = [1; 2; 3] ent ao l e, em termos
de representac ao memoria, um apontador para o primeiro bloco contento 1 e
um apontador para o segundo bloco, etc. :
1 2 3 []
l
Como referido previamente, se denirmos agora a lista l como a junc ao de
um outro elemento à lista l, com a ajuda da declarac ao let l = 0 :: l,
temos agora a situacao seguinte:
0 1 2 3 []
l l
Isto e, a aplicac ao do construtor :: teve por efeitos alocar um novo bloco,
cujo primeiro elemento e 0 e o segundo um apontador cujo valor e igual à l.
A vari avel l continua a apontar para os mesmos blocos.
De uma forma geral, qualquer fun cao denida que manipule listas tera
esta propriedade de n ao alterar as listas que lhe sao passadas como parame-
tros.
E esta (propriedade) das estruturas de dados que designamos por persis-

tencia.
E muito importante perceber aqui que existe partilha. A declara cao de l

aloca no maximo um bloco suplementar (j a que um so construtor foi aplicada
aqui). Os bloco seguintes sao meramente re-utilizados mas nao sao alterados.
Temos bem duas listas de 3 e 4 elementos respectivamente ([1;2;3] e
[0;1;2;3] para ser mais preciso). Mas somente 4 blocos mem oria alocados.
Em particular nao houve copia. De uma forma geral OCaml nunca copia
valores, excepto se se escreve explicitamente uma func ao para tal operac ao.
Por exemplo:
let rec copie = function [] -> [] | x :: l -> x :: copie l
82
Mas, par ser realista, pouca utilidade tem tal funcao porque as listas n ao
s ao alter aveis in-place.
Assim percebe-se que nao e tao facil juntar um elemento na cauda de
uma lista como juntar a cabeca. Isto porque tal signicaria uma modicacao
in-place da lista l.
1 2 3 0 []
l
Para juntar um elemento em m de lista, e necessario copiar todos os
blocos da lista. Tal procedimento e seguindo, em particular, pela fun cao
append seguinte que constroi a concatenac ao de duas listas:
let rec append l1 l2 = match l1 with
| [] -> l2
| x :: l -> x :: append l l2
Constatamos que esta fun cao cria tantos blocos quanto os ha na lista l1.
Os blocos de l2 s ao partilhados. Assim, se declaramos let l = [4; 5] e
que calculemos a seguir a concatenac ao l e de l com let l = append l
l teremos a situac ao seguinte:
1 2 3 []
l
1 2 3
l
4 5 []
l
Os blocos de l foram copiados e os de l caram partilhados.
E por esta raz ao que as listas devem ser usadas quando o contexto do
seu uso considera juntar e retirar elementos na cabe ca (` a semelhanca das
estruturas de tipo pilha). Quando os acessos e/ou as modica coes devem ser
realizadas em posicoes arbitrarias na sequencia considerada, entao e prefervel
outra estrutura de dados.
e importante notar que os elementos proprios da lista n ao sao copiados
pela func ao append. De facto, x designa um elemento de tipo qualquer e
nenhuma c opia e realizada sobre o proprio x. No caso duma lista de inteiros,
isto pouca relevancia tem. Mas se consider assemos uma lista l contendo
83
tres elementos de um tipo mais complexo, por exemplo triplos de inteiros
como no caso de let l =[(1,2,3); (4,5,6); (7,8,9)], ent ao estes car ao
partilhados por l e append l [(10,11,12)] .
[]
l
[]
l
1 2 3 4 5 6 7 8 9 10 11 12
Isto por parecer articialmente custoso quando se tem o habito de traba-
lhar com estruturas de dados modicaveis localmente, come tradicionalmente
o caso no contexto de linguagens imperativas. Mas isto seria sub-estimar o
interesse pr atico da persistencia.
E alias importante notar que o conceito da persistencia pode ser realizado

de forma f acil numa linguagem imperativa. Basta manipular as listas ligadas
exactamente como o compilador OCaml o faz. De forma inversa, podemos
perfeitamente em OCaml manipular listas modic aveis localmente. Por
exemplo, denindo:
type a lista = Vazia | Elemento of a element
and a element = { valor : a; mutable seguinte : a lista };;
Podemos ate mesmo tornar o campo valor mutavel se o desejarmos. Mas
ao contr ario das linguagens imperativas, OCaml oferece a possibilidade de
denir as estruturas de dados imut aveis de forma natural e segura (porque
mesmo se codicamos uma estrutura persistente em C ou Java, o sistema de
tipo n ao poder a impedir a sua modica cao local, sendo as variaveis natural-
mente mut aveis).
Finalmente e preciso n ao esquecer que a mem oria nao utilizada e auto-
maticamente recuperada pelo GC (Garbagge Collector) de OCaml. Assim
numa express ao como:
let l = [1;2;3] in append l [4;5;6]
84
os tres blocos de l s ao efectivamente copiados aquando da construcao da
lista [1;2;3;4;5;6] mas sao imediatamente apagados (recuperados) pelo
GC porque n ao s ao mais referenciadas.
Outro exemplo ilustrativo destes fen omenos pode ser o das arvores.
# type tree = Empty | Node of int * tree * tree;;
type tree = Empty | Node of int * tree * tree
# let rec add v ab =
match ab with
Empty -> Node (v,Empty,Empty)
| Node (n,esq,dir) ->
if v > n then Node (n,esq,(add v dir))
else Node (n,(add v esq), dir);;
val add : int -> tree -> tree = <fun>
# let (ab1,ab2,ab3) = Empty, Empty,Empty;;
val ab1 : tree = Empty
# let ab = Node (12,ab1,(Node (20,ab2,ab3)));;
val ab : tree = Node (12, Empty, Node (20, Empty, Empty))
# add 42 ab;;
- : tree = Node (12, Empty, Node (20, Empty, Node (42, Empty, Empty)))
A funcao add pouco copia, mas sim partilha.
Figura 4: Partilha em arvores
85
7.2 Interesses praticos da persistencia
Os interesses pr aticos da persistencia s ao m ultiplos. De forma imediata
percebe-se que a persistencia facilita a leitura do c odigo e a sua correcc ao.
De facto podemos raciocinar sobre valores manipulados por programas em
termos matematicos, j a que estes sao imut aveis, de forma equacional e sem se
preocupar da ordem da avalia cao. Assim e sempre facil car convencido da
correcc ao da func ao append apresentada anteriormente e dos seus requisitos
funcionais (i.e. append l1 l2 constroi a lista formada dos elementos de l1
seguidos dos elementos de l2).
Um simples raciocnio indutivo sobre a estrutura de l1 chega. Com listas
alter aveis localmente, a adapta cao da func ao append que redireccione (modi-
ca) o apontador do ultimo bloco de l1 para o bloco em cabe ca de l2 torna
o argumento de correcc ao muito mais complicado. Um exemplo ainda mais
agrante e o de uma fun cao, num contexto mutavel, que devolve de uma
lista.
A correcc ao de um programa n ao e um aspecto menor e deve sempre ser
priorit ario a sua ecacia. Quem se importa com um programa super r apido
se este est a errado?
A persistencia n ao e somente util para facilitar a correcc ao dos programas.
e igualmente uma ferramenta poderosa em contextos em que a tecnica do
retrocesso (backtracking) e necessaria.
Supomos, por exemplo que procuremos escrever um programa que pro-
cura a sada de um labirinto, na forma de uma func ao procura que aceita
em entrada um estado (persistente) e devolvendo um booleano indicando o
sucesso (ou n ao) da pesquisa.
as deslocac oes possveis a partir de um estado sao dadas na forma de uma
lista por uma fun cao movimentacoes e uma outra fun cao movimenta calcula o
resultado de uma movimentac ao a parti de um determinado estado, na forma
de um novo estado ja que pertence a um tipo de dado persistente. Vamos
supor que uma func ao booleana saida indica se um estado corresponde ou
n ao a uma sada do labirinto.
Ent ao escreve-se trivialmente a fun cao procura da forma seguinte:
let rec procura e =
saida e || tenta e (movimentacoes e)
and tenta e = function
| [] -> false
86
| d :: r -> procura (movimenta d e) || tenta e r
onde tenta e uma func ao auxiliar testando uma por uma as movimenta-
c oes possveis de uma lista de movimentac oes.

E a natureza persistente da
estrutura de dados representando os estados que permite uma tal concisao
de codigo. De facto, se o estado teria de ser alterado no lugar, precisaramos
ent ao realizar a deslocac ao antes de efectuar a chamada recursiva a procura
mas tambem cancelar esta deslocacao no caso de esta se revelar um beco sem
sada e antes de considerar movimentos alternativos. O c odigo passaria a ser
algo como:
let rec procura () =
saida () || tenta (movimentacoes ())
and tenta = function
| [] -> false
| d :: r -> (desloca d; procura ()) || (retrocessa d; tenta r)
O que e sem margem para d uvida menos claro e mais propcio a erros.
Este exemplo, infelizmente, nao e articial: a tecnica de backtracking e
frequentemente utilizada em informatica (percurso de grafos, colora cao de
grafo, contagem de soluc oes, etc.)
Um outro exemplo tpico e o do porte em manipulacoes simb olicas de
programas (ou formulas).
Supondo, por exemplo, que se pretenda manipular programas Java triviais
compostos exclusivamente por blocos, vari aveis locais inteiras, de testes de
igualdade entre duas vari aveis e de return. Isto e, programas parecidos com:
{
int i = 0;
int j = 1;
if (i == j) {
int k = 0;
if (k == i) { return j; } else { int i = 2; return i; }
} else {
int k = 2;
if (k == j) { int j = 3; return j; } else { return k; }
87
}
}
Tais programas podem ser representados em OCaml pelo tipo instr
list onde o tipo soma instr dene-se como
type instr =
| Return of string
| Var of string * int
| If of string * string * instr list * instr list
Suponhamos agora que pretendemos vericar que as vari aveis mani-
pulados em tais programas sao sempre previamente declaradas adequada-
mente. Para tal podemos escrever duas func oes mutuamente recursivas
verifica_instr e verifica_prog que vericam respectivamente que uma
instruc ao e uma lista de instruc oes sao bem formadas (no sentido da ade-
quada declarac ao de vari aveis manipuladas). Para esse efeito, estas duas
funcoes tomam como par ametro a lista das vari aveis que sao no momento
visveis (estao no porte/ ambito). O codigo e assim evidente:
let rec verifica_instr vars = function
| Return x ->
List.mem x vars
| If (x, y, p1, p2) ->
List.mem x vars && List.mem y vars &&
verifica_prog vars p1 && verifica_prog vars p2
| Var _ ->
true
and verifica_prog vars = function
| [] ->
true
| Var (x, _) :: p ->
verifica_prog (x :: vars) p
| i :: p ->
verifica_instr vars i && verifica_prog vars p
88
A simplicidade deste c odigo resulta da utiliza cao de uma estrutura de
dados persistente para o conjunto das vari aveis (uma lista).
Se tivessemos utilizado uma tabela imperativa no lugar da lista, seria
ent ao preciso retroceder entre o primeiro ramo de um if e a segunda, por
forma a que possamos esquecer as vari aveis locais ao primeiro ramo. O c odigo
n ao teria assim sido tao simples.
Este exemplo e relativamente simples, mas encontramos muitas manifes-
ta coes deste fen omeno na pratica, mal facamos manipulac oes simbolicas e
que mecanismos de porte intervenham (tabela de smbolos, ambientes de ti-
picac ao, etc.).

E assim muito agrad avel e conveniente utilizar estruturas de
dados persistentes.
Vamos abordar uma ultima ilustra cao da utilidade da persistencia. Ima-
ginemos um programa manipulando uma coleccao de dados S o existe uma
inst ancia desta coleccao de dados a cada instante e entao nao h a a priori
razao nenhuma para utilizar uma estrutura persistente para a sua codica-
c ao. Mas supomos agora que as actualizacoes por realizar nesta base sejam
complexas, isto e implicam cada uma delas um grande n umero de operac oes
cujo algumas podem falhar.
Encontramo-nos numa situac ao em que e preciso saber anular os efeitos
da actualizacao iniciada. De uma forma esquem atica, o codigo poder a se
assemelhar a:
try
... realizar a actualizac~ ao ...
with e ->
... restabelecer a base para um estado coerente ...
... tratar do erro ...
Se utilizarmos uma estrutura de dados persistente para a colec cao, basta
arquivar a base numa referencia, por exemplo bd. Assim a actualiza cao
torna-se simplesmente na actualizacao desta referencia:
let bd = ref (... base inicial ...)
...
try
bd := (... actualiza c~ao de !bd ...)
with e ->
89
... tratar do erro ...
Assim, n ao h a absolutamente nenhuma necessidade anular qualquer coisa.
De facto, a actualizac ao, por t ao complexa que seja, nao faz mais do que cons-
truir uma nova base e, uma vez esta terminada, a referencia bd e modicada
para apontar para esta nova colecc ao. Esta ultima operac ao e at omica e n ao
pode falhar. Se h a uma qualquer excepcao levantada durante a actualiza cao
propriamente dita, ent ao a referencia bd permanecer a inalterada.
7.3 Interface e persistencia
A estrutura de dados que codica as listas e persistente de forma evidente
porque e um tipo soma da qual conhecemos a denic ao: concreto e imutavel.
Quando um modulo OCaml implementa uma estrutura de dados na
forma de um tipo abstracto, a sua natureza persistente (ou nao) n ao e imedi-
ata. Evidentemente, um coment ario apropriado na interface pode esclarecer
o programador/utilizador deste facto. Mas na pratica sao os tipos das ope-
ra coes disponveis que fornecem esta informa cao. Tomemos o exemplo de
uma estrutura persistente representando os conjuntos nitos de inteiros. A
interface de um tal modulo poderia ser:
type t (* o tipo abstracto dos conjuntos *)
val empty : t (* o conjunto vazio *)
val add : int -> t -> t (* juntar um elemento *)
val remove : int -> t -> t (* remover um elemento *)
...
A natureza persistente desta representa cao dos conjuntos e implcita nesta
interface.
De facto, a opera cao add devolve um valor de tipo t, isto e, um novo
conjunto. Neste ponto, em tudo semelhante e a func ao remove. Mais subtil-
mente e a situac ao do conjunto vazio: empty e um valor e nao uma func ao.
Assim todas as ocorrencias de empty ser ao partilhadas, qualquer que seja a
sua representac ao.
No entanto, uma estrutura de dados alter avel in-place para os conjuntos
de inteiros (por exemplo sob a forma de tabelas de hash) poderia tomar a
forma de:
90
type t (* O tipo abstracto dos conjuntos *)
val create : unit -> t (* o conjunto vazio *)
val add : int -> t -> unit (* juntar um elemento *)
val remove : int -> t -> unit (* remover um elemento *)
...
Aqui a func ao add n ao devolve nada, porque o novo elemento foi acrescen-
tado directamente (in-place...) na estrutura de dados. Tal tambem acontece
com as outras operac oes que alteram a estrutura.
A func ao create aceita um argumento de tipo unit porque de cada vez
que create e invocada, esta deve construir uma nova instancia da estrutura
de dados para que as modicac oes in-place n ao alterem outras estruturas
criadas.
Infelizmente, nada impede dar a uma estrutura de natureza imperativa
uma interface persistente (devolvendo o valor passado em par ametro). De
forma inversa, nada impede dar uma interface imperativa a uma estrutura
persistente (que deite fora os valores construdas). nos dois casos, e in util e
perigoso...
Mas tal n ao signica no entanto que uma estrutura de dados persistente
seja necessariamente implementada sem efeitos colaterais. Assim a boa de-
nic ao da no cao de persistencia e:
persistencia = imutavel por observacao
e n ao puramente funcional (no sentido de ausencia de efeitos co-laterais).
Temos uma implicac ao num s o sentido
puramente funcional persistente
A recproca e falsa. Existem estruturas de dados persistentes que nao s ao
puramente funcionais, devido ao seu uso dos efeitos co-laterais.
A situac ao e a seguinte:
Estructuras persistentes
Estructuras
immutveis
Estructuras no persistentes
91
Um exemplo de estrutura persistente, apesar de alteravel in-place, e o
das arvores bin arias de pesquisa que evoluem à medida das pesquisas para
optimizar as pesquisas dos elementos mais requisitados, as Splay trees.
Isto pode ser concretizado implementando a estrutura de dados como
uma referencia para uma arvore. A arvore optimizada por entao substituir a
arvore actual por uma simples modicac ao desta referencia.
A estrutura completa permanece observacionalmente persistente, j a que
n ao ha modica coes observ aveis do conte udo, mas sim da performance.
Um outro exemplo, simples, e o exemplo das las (rst-in rst-out ou
queue em ingles).
Se procuramos uma solucao persistente com base em listas, a performance
n ao ser a satisfatoria. Juntar um elemento ` a cabeca nao coloca problemas,
mas remover ecazmente um elemento ` a cauda e outra hist oria. O custo e
proporcional ao n umero de elementos, em tempo e em espa co.
Uma alternativa astuta consiste em representar uma la por duas listas.
A primeira contem os elementos acabados de entrar e a segunda os elementos
prestes a sair (logo arquivado no sentido contr ario). As operac oes de acres-
cimo ou de remoc ao terao ent ao sempre um custo constante (O(1)) excepto
no caso particular em que a lista de sada se encontra vazia. Neste caso in-
vertemos a lista de entrada para poder agora utiliza-la como lista de sada.
A lista de entrada car a, neste contexto, vazia. O custo desta invers ao e
proporcional ao comprimento da lista por inverter, mas isto e feito uma so
vez sobre a lista considerada. A complexidade amortecida (amortized com-
plexity, em ingles, i.e. a complexidade limitada ao conjunto de opera coes de
acrescimo e de remo cao) permanece em O(1).
A interface mnima para as las persistentes pode ser:
type a t
val create : unit -> a t
val push : a -> a t -> a t
exception Empty
val pop : a t -> a * a t
Podemos propor o codigo seguinte, com base nas ideias apresentadas mais
acima:
type a t = a list * a list
let create () = [], []
92
let push x (e,s) = (x :: e, s)
exception Empty
let pop = function
| e, x :: s -> x, (e,s)
| e, [] -> match List.rev e with
| x :: s -> x, ([], s)
| [] -> raise Empty
Mas e ainda possvel que sejamos obrigado a devolver repetidamente a
lista de entrada e se a operacao pop e efectuada repetidamente sobre uma
mesma la da forma (e,[]). Tal situa cao sempre e susceptvel de acontecer
j a que pretendemos construir las persistentes.
Para remediar esta situa cao, vamos associar o retorno de uma lista de
entrada e a um efeito co-lateral na estrutura de dados. Isto nao alterar a
o conte udo a la (e,[]) contem exactamente os mesmos elementos que
([],List.rev e) evitar a a devoluc ao da mesma lista na vez seguinte.
Substitumos assim o par de listas por um registo composto de dois cam-
pos entrada e saida, ambos mutable:
type a t = { mutable entrada : a list; mutable saida : a list }
let create () = { entrada = []; saida = [] }
let push x q = { entrada = x :: q.entrada; saida = q.saida }
exception Empty
e o c odigo da funcao pop e apenas mais complexo:
let pop q = match q.saida with
| x :: s ->
x, { entrada = q.entrada; saida = s }
| [] -> match List.rev q.entrada with
| [] ->
raise Empty
| x :: s as r ->
q.entrada <- []; q.saida <- r;
x, { entrada = []; saida = s }
93
A unica diferenca est a nas duas modicac oes in-place dos campos da la
q. Notemos a utilizac ao da palavra chave as no ltro que permite nomear a
totalidade do valor ltrado por m a sua reconstru cao.
8 Exemplos
8.1 Produto Cartesiano
O exemplo simples seguinte ilustra um uso combinado da criac ao on-the-y
de tuplos, consoante a necessidade, com o mecanismo de ltragem. A func ao
calcula recebe uma lista de inteiros e calcula simultaneamente o menor
elemento da lista, o maior elemento, a soma dos elementos, o n umero de
inteiros mpares presentes e o n umero de pares. A funcao calcula2 apresenta
uma versao que usa o combinador fold_left.
let rec calcula l menor maior soma impares pares =
match l with
[] -> (menor,maior, soma, impares, pares)
| el::li ->
calcula li (*li = resto da lista por processar*)
(**cada par^ ametro representa o estado tempor ario
do conhecimento sobre os valores por calcular.
Cada chamada recursiva debru ca-se sobre um
elemento da lista, logo estes par^ ametros s~ ao
actualizados de acordo *)
(if el < menor then el else menor)
(if el > maior then el else maior)
(soma + el)
((if el mod 2 = 0 then 0 else 1) + impares )
((if el mod 2 = 0 then 1 else 0) + pares )
;;
let calcula2 l =
fold_left (fun (menor,maior,soma,impares,pares) el ->
((if el < menor then el else menor),
(if el > maior then el else maior),
(soma + el),
94
((if el mod 2 = 0 then 0 else 1) + impares),
((if el mod 2 = 0 then 1 else 0) + pares )))
((hd l),(hd l),0,0,0) l;;
8.2 Brincadeiras a volta da sequencia de Fibonacci
Para comecar vamos denir a fun cao fib1 que calcula de forma simples e
recursiva o n-esimo elemento da sequencia de Fibonacci. Caso o par ametro
seja negativo, a func ao dever a lancar uma excepc ao.
open Scanf;;
open Printf;;
(* Excep c~ ao *)
exception Input_Negativo;;
let rec fib1 x =
if (x<0)
then raise Input_Negativo
else
if (x <= 1)
then 1
else fib1 (x-1) + fib1 (x-2)
;;
O passo seguinte e a denic ao da func ao f1 que se encarrega em pedir
um valor adequado ao utilizador.
let rec f1 () =
(** a variavel local [valor] recebe um inteiro introduzido pelo utilizador *)
let valor = print_string " \nVALOR? "; read_int () in
try
let res = (fib1 valor) in
printf ("\nResultado 1 -> fib(%d) = %d\n") valor res
with Input_Negativo ->
(print_string "Queira recomecar...\n";
f1 ());;
(*execu c~ ao*)
95
f1 ();;
A fun cao seguinte, f2, obtem o parametro da fun cao fib1 da linha de
comando.
let f2 () =
(* [valor] recebe um inteiro extrado da linha de comando *)
let valor = int_of_string (Sys.argv.(1)) in
printf "valor lido da linha de comando=%d\n" valor ;
try
(printf "\nResultado 2 -> fib(%d) = %d\n" valor res)
print_string "Queira recome car...\n"
;;
(* execu c~ ao *)
f2 ();;
A func ao f3 opta por recolher o par ametro do cheiro dados.txt. Este
dever a ser previamente aberto e associado a um canal de leitura, para ser
depois fechado quando o processo terminar.
let f3 () =
(** [fich]: canal de leitura *)
let fich = open_in "dados.txt" in
(** [valor] recebe o inteiro extrado da primeira linha do canal*)
let valor = int_of_string (input_line fich) in
printf "valor lido do ficheiro=%d\n" valor ;
begin
try
printf "\nResultado 3 -> fib(%d) = %d\n" valor res
print_string "Queira recome car...\n"
end;
close_in fich;;
96
(*execu c~ ao*)
f3 ();;
A func ao fib2 calcula de forma iterativa o n-esimo elemento da sequencia
de Fibonacci.
let fib2 n =
if (n<0)
else
let temp = ref 0 in
(* [resa] = fib (n-2) - inicialmente fib 0*)
let resa = ref 1 in
(* [resb] = fib (n-1) - inicialmente fib 1*)
let resb = ref 1 in
for v = 1 to (n-1) do
(** Cada itera c~ ao obriga a actualiza c~ ao de fib (n-2) e de fib (n-1)*)
temp:= !resa;
resa := !resb;
resb := !temp + !resa
done;
(** [resb] = fib n*)
!resb;;
let rec f4 () =
let valor = print_string " \nVALOR? " ; read_int () in
try
printf "\nResultado 4 -> fib(%d) = %d\n" valor res
(print_string "Queira recomecar...\n"; f4 ())
;;
(*execu c~ ao*)
f4 ();;
Nesta versao da func ao Fibonacci, optamos por uma vers ao recursiva ter-
minal. Para tal precisaremos de dois acumuladores. De reparar a semelhanca
97
dos par ametros acc1 e acc2 com as referencias resa e resb da versao itera-
tiva. A estrategia de c alculo, como em fib2 consiste em desenrolar (do inicio
ate ao m) os valores da sequencia ate chegar ao patamar desejado.
(** [acc1] = fib (n-2) - inicialmente fib 0
[acc3] = fib (n-1) - inicialmente fib 1
Enquanto [x] decresce, [acc1] e [acc2] v~ao sendo actualizados.
Quando [x] <= 1 ent~ ao [acc2] tem o valor pretendido
*)
let rec fib3_aux x acc1 acc2 =
if (x<0)
else
if (x <= 1)
then acc2
else fib3_aux (x-1) acc2 (acc1+acc2)
;;
let fib3 n = fib3_aux n 1 1;;
let rec f5 () =
let _ = print_string " \nVALOR? " in
let valor = read_int () in
try
(printf "\nResultado 5 -> fib(%d) = %d\n" valor res)
(print_string "Queira recomecar...\n"; f5 ())
;;
(*execu c~ ao*)
f5 ();;
Se juntamos estas varia coes num s o programa obtemos o c odigo seguinte.
Nesta versao o valor pretendido e calculado consoante a congurac ao da
linha de comando e dos par ametros extrados.
98
open Arg
open Sys
exception Input_Negativo;;
(** vers~ ao recursiva terminal *)
let rec fib_fast x acc1 acc2 =
if x<0 then raise Input_Negativo
else
if x=0 then acc2
else fib_fast (x-1) acc2 (acc2+acc1)
let fib n = fib_fast n 1 1
let calcula () =
(** primeiro verificamos quantos argumentos temos na
linha de comando *)
let narg = Array.length Sys.argv in
(** se houver s o um (o nome do execut avel), ent~ ao, o
inteiro deve ser proveniente da interacc~ao directa
com o utilizador *)
if nargv = 1 then
begin
let x = print_string "Queira introduzir um valor inteiro: ";
read_int() in
fib x
end
else
(** Se tivermos 2 argumentos, ent~ ao o segundo argumento e o inteiro *)
if narg = 2 then
begin
fib (int_of_string Sys.argv.(1))
end
else
(** tivermos mais do que 3 argumentos, e erro *)
if n>3 then failwith "Bad Use\n"
else
99
(** no caso de haver 3 argumentos e os dois ultimo serem da
forma [-f ficheiro], ent~ao o inteiro est a no
ficheiro [ficheiro] *)
if ((Sys.argv.(1) = "-f") & (Sys.file_exists (Sys.argv.(2)))) then
begin
let fich= open_in Sys.argv.(2) in
let v = fib (int_of_string (input_line fich)) in
(close_in fich; v)
end
else failwith "Bad Use\n";;
print_int (calcula ());;
8.3 Exercitar a estrategia dividir para conquistar
Pretendemos aqui calcular a lista de todas as sub-listas de uma lista l com
os elementos na ordem presente na lista original (ou seja [a;c] e sub-lista
de [a;b;c] mas nao [c;a]).
A estrategia que pretendemos seguir e a cl assica Dividir para Conquistar.
O objectivo do presento exemplo e perceber como usar o resultado para
uma solu cao menor para calcular a solucao para um problema maior.
Vamos aqui usar recursividade estrutural (tenha em atenc ao que nem
todos os problemas se conseguem resolver com este tipo de recursividade) ou
seja perceber como uma soluc ao para [a1;a2;a3;...;an] pode contribuir
para a solu cao para [a0;a1;a2;a3:...;an].
Comecemos assim por determinar o resultado para os casos de base: [],
e depois para [c], para [b;c] e para [a;b;c], etc...
O objectivo e tentar perceber que padrao existe entre a soluc ao dum caso
para o caso imediatamente maior. Vamos assim tentar organizar o resultado
por forma a facilitar a descoberta deste padrao.
Descoberto, este padr ao formar a a soluc ao para o caso recursivo.
sublista [] = [[]]
sublista [c] = [[];[c]]
sublista [b;c] = [[];[c];[b];[b;c]]
sublista [a;b;c]= [[];[c];[b];[b;c];[a];[a;c];[a;b];[a;b;c]]
Ou seja
100
sublista el::li =
sublista li @ el::(todos os elementos de (sublista li))
O codigo OCaml subjacente e o seguinte.
let rec sublists = function
[] -> [[]]
| x::xs ->
let subl = (sublists xs) in
subl @ (map (fun l -> x::l) subl)
Pretendemos agora calcular a lista de todas as listas possveis que resul-
tam da insercao de um elemento e numa lista l.
A funcao por implementar e: val insertions e l : a -> a list -> a list list
Como no exemplo anterior, podemos tentar descobrir o padr ao subjacente
pela an alise dos casos iniciais.
insertions e [] = [[e]]
insertions e [c] = [[e;c];[c;e]]
insertions e [b;c] = [[e;b;c];[b;e;c];[b;c;e]]
insertions e [a;b;c] = [[e;a;b;c];[a;e;b;c];[a;b;e;c];[a;b;c;e]]
logo
insertions e el::li =
juntar e::el::li a (el::(todos os elementos de (insertion e li)))
Assim o c odigo OCaml e o seguinte:
let rec insertions e = function
[] -> [[e]]
| x::xs -> (e::l) :: (map (fun li -> x::li) (insertions e xs))
8.4 Polinomios, e o Metodo de Horner
Podemos representar um polinomio P de grau n por uma sequencia p de reais
em que uma celula de ndice i representa o coeciente associado à potencia
de grau i.
Podemos entao calcular P(x) usando o metodo de Horner, i.e.
P
n
(x) = ( ((p
n
x + p
n1
)x + p
n2
)x + + p
1
)x + a
0
101
open Printf;;
(*
horner r gr x n (pi,pr)=
r: valor do ndice de Pr desejado
gr: grau do polin omio
x: valor da variavel x
n: grau actualmente por explorar (de 0 a gr)
pi: valor do Pn por calcular
pr: valor de Pr por calcular (se n<=r) ou ja calculado (se r<n)
se n > grau
ent~ao devolver (pi,pr)
sen~ao seja v um valor real obtido da entrada standard (do teclado)
seja p o valor x*pi + v
se n=r ent~ao horner r gr x (n+1) (p,p)
sen~ao horner r gr x (n+1) (p,pr)
*)
let rec horner r gr x n (pi,pr) =
if n> gr then (pi,pr)
else
let v = read_float () in
let p = x*.pi +. v in
let new_pr = if n = r then p else pr in
horner r gr x (n+1) (p,new_pr);;
let grau = read_int () in
let x = read_float () in
let r = read_int () in
let (p_x,pr_x) = horner r grau x 0 (0.0,0.0) in
(printf "%.3f\n%.3f\n" p_x pr_x);;
8.5 Matrizes e cheiros
Para comecar, ilustremos de forma muito simples a redirec cao de um canal
de leitura para um buer de leitura, muito pr atico quando queremos evitar
102
as habituais diculdades de leitura via scanf.
Assim o objectivo deste pequeno exemplo e ler inteiros dum cheiro,
coloca-los numa lista e calcular para todos eles o factorial.
Sendo a func ao leitura a fun cao mais adequada para tratar dos er-
ros de argumentos que podem surgir (porque esta funcao e responsavel pela
extrac cao dos valores fornecidos ` a func ao fact), esta tratara da excep cao
Minha mensagem eventualmente lan cada pela funcao fact.
let leitura name =
let fich = open_in name in
let sb = Scanf.Scanning.from_channel fich in
let l = ref [] in
try
while (true) do
let x = Scanf.bscanf sb " %d" (fun a -> a) in
l:= x::!l
done; []
with End_of_file ->
try
List.map fact List.rev(!l)
with Minha st ->(
prerr_string ("Problema com dados inv alidos: "^st^"\n");[])
;;
Vamos neste exemplo introduzir uma utilizac ao b asica da leitura e escrita
em cheiro. Pretendemos assim ler uma sequencia de inteiros presentes num
determinado cheiro (pedido ao utilizador) e escrever a soma destes inteiros
num segundo cheiro (tambem previamente escolhido pelo utilizador).
let iname = print_endline "Nome de ficheiro de input"; read_line() in
let oname = print_endline "Nome de ficheiro de output"; read_line() in
(** Func~ao auxiliar de leitura.
Cada inteiro lido e somado a um acumulador.
O processo e recursivo, e pela defini c~ao ing enua do padr~ao
recursiva, parece sugerir um padr~ao recursivo sem fim.
Tal n~ ao acontece visto que os ficheiros s~ ao finitos e que
103
necessariamente o processo de leitura ir a debater-se contra o
fim de ficheiro (que ocasionara a excepc~ao End_of_file).
Caso a leitura corra mal (leitura de um valor que n~ao e inteiro)
outra excep c~ ao sera lan cada.
A recupera c~ao destas duas situac~oes excepcionais devolver a o
valor do acumulador actual.
*)
let rec leitura fich acc =
begin
try
let n = int_of_string (input_line fich) in
leitura fich (n+acc)
with _ -> acc
end
in
(** testamos aqui se os identificadores de ficheiros
introduzidos representam ficheiros v alidos*)
if Sys.file_exists iname && Sys.file_exists oname
then
(** Neste caso abrimos os ficheiros e damos inicio ao processo
de leitura (com o acumulador inicializado a 0)*)
let ic = open_in iname in
let oc = open_out oname in
let v = leitura ic 0 in
begin
(** Escrevemos a soma no ficheiro destino e fechamos
a seguir os respectivos canais*)
output_string oc (string_of_int v);
close_in ic;
close_out oc
end
else failwith "File error"
No exemplo seguinte introduzimos um pequeno exerccio e ilustramos o
uso dos buers de leitura (scanning buer).
O objectivo e ler uma matriz n n de inteiros de um cheiro (primeiro
le-se o n e depois o conte udo da matriz) e calcular para cada linha e cada
coluna a sua soma. No nal calcula-se a soma global dos valores da matriz.
104
Todos estes valores s ao colocados numa matriz (n + 1) (n + 1). Por m,
visualiza-se a matriz nal.
O estilo imperativo, propositado, segue naturalmente da escolha da matriz
como suporte aos calculos.
open Scanf;;
open Printf;;
open Array;;
(** um conjunto de func~ oes que inicializam uma matriz n x n com valores
lidos dum ficheiro e devolve a soma das linhas e colunas **)
let calcula name =
let fich = open_in name in
(** cria c~ ao dum buffer para scanf (melhor no caso do uso repetido
de scanf, como vai ser o caso)**)
let sb = Scanning.from_channel fich in
(** leitura do tamanho da matriz *)
let n = int_of_string (input_line fich) in
(** func~ao auxiliar que lê uma linha de n valores e devolve um vector
de n+1 posi c~ao com os valores lidos mais o 0 final **)
let fill i =
if i<n
then
Array.init (n+1)
(fun j -> if j < n then bscanf sb " %d" (fun a -> a) else 0)
else Array.make (n+1) 0
in
(** Inicializar a grelha **)
let grelha = Array.init (n+1) fill in
(** c alculo da coluna da direita **)
let _ =
for i = 0 to n-1 do
105
let acc = ref 0 in
for j = 0 to n-1 do
acc := !acc + grelha.(i).(j)
done;
grelha.(i).(n) <- !acc
done in
(** c alculo da linha final **)
let _ =
for j = 0 to n-1 do
let acc = ref 0 in
for i = 0 to n-1 do
acc := !acc + grelha.(i).(j)
done;
grelha.(n).(j) <- !acc
done in
(** c alculo do valor extremo grelha.(n).(n) **)
let _ =
let i = ref 0 in
let acc = ref 0 in
while (!i <= n) do
acc := !acc + grelha.(!i).(n);
i:= !i + 1
done; grelha.(n).(n)<- !acc
in
(** visualiza c~ ao**)
for i = 0 to n do
for j = 0 to n do
printf " %3d" grelha.(i).(j)
done;
print_newline ()
done
;;
(**** test.txt=2
4
106
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
*****)
calcula "test.txt";;
(**** Resultado
1 2 3 4 10
5 6 7 8 26
9 10 11 12 42
13 14 15 16 58
28 32 36 40 136
*****)
8.6 Memoizacao automatica
Vamos aqui exemplicar de forma simples a denic ao ad-hoc de funcoes re-
cursivas optimizadas com memoiza cao
6
.
Relembremos sucintamente que a memoizac ao, para uma funcao f, e uma
tecnica de optimizacao, simples mas ecaz, que consiste no registo numa
estrutura adequada de chamadas previas à funcao f.
Por exemplo, se pretendemos calcular f(x), o princpio e ver se o resultado
de f(x) ja n ao foi previamente guardado na estrutura. No caso positivo,
devolvemos directamente o valor (porque esse ja foi calculado e arquivado).
No caso negativo ent ao procedemos ao calculo de forma tradicional. Quando
este for nalizado, arquivamos o par (x, f(x)) na estrutura e devolvemos o
resultado f(x). Nesta congurac ao, se f(x) for novamente requisitado, a
estrutura podera devolve-lo imediatamente sem necessidade de c alculo.
Vamos exemplicar aqui duas formas de denir func oes com memoiza cao.
A primeira ilustrara o uso do m odulo Map.
A estrutura de dados fornecida pelo modulo Map e funcional (n ao e mu-
tavel). Fornece assim um mecanismo puramente funcional para a denic ao
de tabelas de associac oes (chave, valor) implementado com base em arvores
bin arias de pesquisa equilibradas.

E neste tipo de tabela que vamos guardar
6
Consulte Wikipedia: Memoization para mais detalhes sobre a tecnica da memoiza cao.
107
os valores calculados da sequencia de Fibonacci.
As funcionalidade do m odulo Map e acessvel via o functor Make que e
instanciado por um m odulo que estabelece a estrutura do tipo das chaves.
(** o functor Make do modulo Map precisa de um conjunto
ordenado para as suas chaves. Usemos os inteiros. *)
module OrderedInt =
struct
type t = int
let compare n1 n2 = compare n1 n2
end ;;
(** Tabela de associac~ oes com chaves inteiras *)
module AssocInt = Map.Make (OrderedInt) ;;
(** Fibonacci, com memoizac~ ao - Usamos aqui a tecnica baseada no fecho.
[fib_memo] e a func~ao local [f_m] que tem refer^ encia a uma tabela
de associa c~ao.
*)
let fib_memo =
let table = ref AssocInt.empty in
let rec f_m n =
(** primeiro: ver se [n] ja esta na tabela.
No caso positivo devolver a associa c~ ao encontrada*)
try AssocInt.find n !table
with Not_found ->
(** no caso positivo, calcular o valor de forma classica,
recursivamente, e actualizar a tabela de acordo *)
let ret = if n <= 1 then 1 else f_m (n-1) + f_m (n-2) in
table := AssocInt.add n ret !table; ret in
f_m;;
(* instant^ aneo...
# fib_memo 5;;
- : int = 8
# fib_memo 1234;;
108
- : int = 424361
*)
A desvantagem do metodo apresentado e a sua ligac ao forte ao tipo de
funcao denida. Cada caso a sua denic ao. Obviamente podemos fazer bem
melhor e mais generico.
Vamos agora mostrar uma forma generica de obter uma func ao com me-
moiza cao. Este metodo foi-nos sugerido por Jean-Christophe Filli atre.
No lugar de uma tabela de associa cao, vamos nesta vers ao preferir tabelas
de hash, alter aveis in-place.
A func ao chave nesta denic ao e a func ao memo que aceita a funcao alvo
da memoizacao e que devolve assim uma funcao provida deste mecanismo.
A parte interessante desta versao e a deni cao da funcao alvo, se essa
tem de ser ligeiramente alterada (para ser alvo da funcao memo), car muito
proxima da versao que qualquer programador teria escrito de forma natural.
Outra vantagem e a sua generalidade. A chave da associacao guardada e o
tuplo formado pelos parametros da fun cao alvo, quaisquer que sejam esses.
let memo func =
let table = Hashtbl.create 999 in
let rec f v =
try Hashtbl.find table v
with Not_found ->
let ret = func f v in
Hashtbl.add table v ret; ret
in
f;;
let fibm = memo (fun fib2 n ->
if n <=1 then 1 else (fib2 (n-1) + fib2 (n-2)));;
(* instant^ aneo igualmente ... Mas muito estranho ;)
# fibm 5000;;
- : int = -126665694
*)
let ackm = memo (fun ack (m,n) ->
if m <=0
109
then n+1
else if n <= 0
then ack ((m-1),1)
else ack ((m-1),(ack (m,(n-1))))
) ;;
(*** instantâneo, mas nunca estamos longe da explos~ ao....
# ackm (1,7);;
- : int = 9
# ackm (2,8);;
- : int = 19
# ackm (3,6);;
- : int = 509
# ackm (4,6);;
Stack overflow during evaluation (looping recursion?).
*)
8.7 Tipo Soma e Inducao Estrutural
Vamos neste exemplo ilustrar a proximidade do estilo funcional da progra-
mac ao com a formaliza cao e o raciocnio matematico (indutivo).
N ao pretendemos aqui expor um tratado completo da relac ao entre tipos
soma, a inducao e a recurs ao estrutural. Para um tratamento mais formal
e completo, queira consultar os manuais habituaisde matem atica discreta,
l ogica e teoria da computac ao.
Um exemplo habitual de conjunto denido por induc ao estrutural e o
conjunto das f ormulas da l ogica proposicional.
Classicamente tal conjunto assenta na existencia de um conjunto nu-
mer avel (potencialmente innito) 1 de vari aveis proposicionais (i.e. 1 =
A, B, C, . . . , P, Q, R, . . .), de duas constantes particulares (o valor
verdade) e (o valor falso) e nalmente de um conjunto de conectivas
l ogicas (de forma razoavel, , , , , ).
A denic ao indutiva do conjunto Trop das formulas proposicionais pode
ser dada classicamente da seguinte forma. O conjunto Trop das formulas
proposicionais e o menor sub-conjunto X de (1 (, ), , , , , , , )
tal que
Caso de Base
110
1 X
, X
Construtores
F X, F X
F, G X, (F G) X
F, G X, (F G) X
F, G X, (F G) X
F, G X, (F G) X
Dois benefcios imediatos da deni cao por induc ao estrutural das formulas
proposicionais s ao a existencia de um principio de prova por induc ao (estru-
tural) e um princpio de recurs ao (estrutural) util para a programac ao sobre
estas estruturas.
O princpio de inducao para as f ormulas proposicionais pode ser descrito
resumidamente da seguinte forma.
Seja P uma propriedade sobre os elementos de Trop. Para provar
x Trop, P(x)
basta provar:
Casos de Base.
v 1, P(v)
P()
P()
Construtores
F Trop, se P(F) ent ao P(F)
F, G Trop, se P(F) e P(G) ent ao P((F G))
111
O mecanismo de denic ao de func oes (estruturalmente) recursivas, desig-
nado de princpio de recorrencia para as f ormulas proposicionais, expoe-se
da seguinte forma.
Para denir uma fun cao f : Prop
a (total) sobre f ormulas proposicio-

nais, basta saber (fornecer):
Casos de Base.
a func ao fv que para todo o v 1 devolve o valor pretendido
para a variavel v. (ou seja f(v) = fv(v)).
o valor vb da func ao em (ou seja f() = vb)
o valor vt da func ao em (ou seja f() = vt)
Construtores
a func ao fn que para cada formula F e valor v, se f(F) = v ent ao
f(F) = fn(v)
a funcao fa que para cada formulas F e G e valores v1 e v2, se
f(F) = v1 e f(G) = v2 ent ao f((F G)) = fa(v1, v2)
a fun cao fo que para cada formulas F e G e valores v1 e v2, se
f(F) = v1 e f(G) = v2 ent ao f((F G)) = fo(v1, v2)
a fun cao fi que para cada formulas F e G e valores v1 e v2, se
f(F) = v1 e f(G) = v2 ent ao f((F G)) = fi(v1, v2)
a funcao fe que para cada formulas F e G e valores v1 e v2, se
f(F) = v1 e f(G) = v2 ent ao f((F G)) = fe(v1, v2)
Este princpio merece uma pequena explica cao. Vamos olhar para dois
casos particulares, o caso e o caso F G.
O que este princpio diz e que
Se e sabido o valor particular vt da func ao f no caso de base e
Se, sabendo o valor de f para duas f ormulas quaisquer F e G (digamos
que f(F) = v1 e f(G) = v2), e sabido que o valor de f((F G)) e dado
pela func ao fa, isto e f((F G)) = fa(v1, v2)
112
(para alem dos outros casos, obviamente) entao sabe-se calcular o valor desta
funcao f para todas as formulas possveis. Ou seja f ca totalmente de-
nida. Mais, esta termina comprovadamente desde que os seus parametros
(vt, vb, etc.) terminam. De facto, a classe das func oes estruturalmente re-
cursivas termina!
Vamos agora apresentar o c odigo OCaml que corresponde ao conjunto
das f ormulas proposicionais assim como ilustrar estes conceitos.
(***************************************)
(**** Definic~oes Indutivas e OCaml *****)
(***************************************)
type variavel = string;;
type formula =
| Implica of formula*formula
| Equivale of formula*formula
| Ou of formula*formula
| E of formula*formula
| Nao of formula
| Var of variavel
| Verdade
| Falso;;
(*exemplo de elemento do conjunto das formulas proposicionais
(A <-> ~ ( B -> C))
*)
(*exemplo de elemento do conjunto das formulas proposicionais*)
let exemplo = (Equivale ((Var "A"), Nao ( Implica (Var "B", Var "C"))));;
(* Princ pio de recorr^ encia para as f ormulas proposicionais *)
let rec formularec
(fv : variavel -> a)
(vt : a)
(vb : a)
113
(fn : a -> a)
(fa : a -> a -> a)
(fo : a -> a -> a)
(fi : a -> a -> a)
(fe : a -> a -> a)
(f: formula)
= match f with
| Var (v) -> fv v
| Verdade -> vt
| Falso -> vb
| Nao (p) -> fn (formularec fv vt vb fn fa fo fi fe p)
| Ou (p,q) -> fo (formularec fv vt vb fn fa fo fi fe p)
(formularec fv vt vb fn fa fo fi fe q)
| E (p,q) -> fa (formularec fv vt vb fn fa fo fi fe p)
| Implica (p,q) -> fi (formularec fv vt vb fn fa fo fi fe p)
| Equivale(p,q) -> fe (formularec fv vt vb fn fa fo fi fe p)
;;
(* exemplo de fun c~ao estruturalmente recursiva sobre as formulas
proposicionais
Esta fun c~ ao recursiva e estruturalmente recursiva. Porqu^ e? porque
os argumentos das chamadas recursivas s~ao "explicitamente"
sub-f ormulas do argumento.
Outra forma de ver isso: as f ormulas (as defini c~ oes indutivas) s~ ao
arvores (mais precisamente: termos). Se as chamadas recursivas tem
sempre lugar sobre uma sub- arvore do argumento inicial, ent~ ao temos
uma defini c~ao estruturalmente recursiva (i.e. a recursividade
permitiu descer explicitamente na estrutura do termo em
parâmetro. Sendo os termos arvores finitas, de certeza que este
processo chegar a a uma folha---> as func~oes estruturalmente
recursivas terminam sempre).
114
O seguinte exemplo introduz uma fun c~ ao que conta os numero de
vari aveis que ocorrem numa f ormula
*)
(* Comecemos por usar o princpio de recorr^ encia definido
previamente. Para tal vamos definir as func~ oes e constantes
necessarias. Estas s~ ao obvias e n~ao merecem uma explicac~ ao alongada.
A contagem para uma vari avel e 1. Para os outros casos de base, e
0. A contagem para a conjun c~ao, por exemplo, e a soma da contagem
de variaveis das suas duas sub-f ormulas, etc.
*)
let fv = fun v -> 1
let vt = 0
let vb = 0
let fn = fun v -> v
let fa = fun v1 v2 -> v1 + v2
let fo = fun v1 v2 -> v1 + v2
let fi = fun v1 v2 -> v1 + v2
let fe = fun v1 v2 -> v1 + v2
let rec conta_var form = formularec fv vt vb fn fa fo fi fe form;;
conta_var exemplo;;
(* devolve 3*)
(* Vers~ao "user-friendly", usando directamente os mecanismos cl assicos
de OCaml*)
let rec conta_var f =
match f with
Var x -> 1
| Verdade | Falso -> 0
| Nao g -> conta_var g
| E (g,h) -> conta_var g + conta_var h
| Ou (g,h) -> conta_var g + conta_var h
115
| Equivale (g,h) -> conta_var g + conta_var h
| Implica (g,h) -> conta_var g + conta_var h;;
conta_var exemplo;;
(* devolve 3*)
Outras ilustra coes possveis sao os seguintes exemplos.
(*Outro exemplo de tipo/conjunto indutivo: a listas*)
type a lista =
Vazia | Cons of (a* a lista);;
(*Outro exemplo de tipo indutivo: as arvores bin arias*)
type a arvore =
AVazia | Nodo of (a arvore*a*a arvore);;
(*As 5 func~ oes seguintes s~ ao estruturalmente recursiva sobre listas
(as 2 primeiras) e sobre arvores (as restantes)*)
let rec length (l:a lista) =
match l with
| Vazia -> 0
| Cons (x,li) -> 1 + length li;;
let rec concat (l1: a lista) (l2: a lista) =
match l1 with
| Vazia -> l2
| Cons (x,l) -> Cons (x,concat l l2);;
let rec nodos (a: a arvore) =
match a with
| AVazia -> 0
| Nodo (e,x,d) -> 1 + nodos e + nodos d
;;
116
(*fun c~ ao auxiliar...*)
let max a b = if a>b then a else b
let rec altura (a : a arvore)=
match a with
| AVazia -> 0
| Nodo (e,x,d) -> 1 + (max (altura e) (altura d))
;;
let rec percurso_infixo (a:a arvore) =
match a with
| AVazia -> []
| Nodo (e,x,d) -> (percurso_infixo e) @ (x::(percurso_infixo d))
;;
Ap os termos visto como programar sobre tipos indutivos, debrucemo-nos
agora sobre as demonstrac oes e sobre os princpios de induc ao. Alem de
poder programar, podemos demonstrar que programamos bem e sem bug!
O princpio de induc ao para as listas pode ser resumido da seguinte forma.
Para demonstrar que qualquer que seja a lista l, P(l) basta:
(Base) Provar que P(V azia).
(Indutivo) Provar que para todo o l lista e x elemento, se P(l) ent ao
P(Cons(x, l)).
De forma semelhante, o princpio de indu cao para as arvores e o seguinte.
Para demonstrar que qualquer que seja a arvore ar, P(ar) basta:
(Base) P(AV azia)
(Indutivo) Provar que para todo os ar1 e ar2 arvores e x elemento, se
P(ar1) e P(ar2) ent ao P(Nodo(ar1, x, ar2)).
Ilustremos assim estes dois princpios.
1. Para todas as listas l1 e l2, demonstrar que length l1 + length l2 =
length (concat l1 l2).
Vamos proceder por demonstrac ao indutiva sobre a lista l1.
117
Caso de base:
length V azia + length l2 = length (concat V azia l2).
Ora, length V azia = 0
e, concat V azia l2 = l2.
logo length (concat V azia l2) = length l2. Done.
Passo Indutivo:
Hip otese de induc ao:
Dado uma lista l, length l + length l2 = length (concat l l2).
Veriquemos agora que para todo o x elemento temos en-
tao necessariamente length (Cons (x, l)) + length l2 =
length (concat (Cons (x, l)) l2).
Vejamos:
length (Cons (x, l)) + length l2 = length l + length l2 + 1
(por deni cao de length)
length (concat (Cons (x, l)) l2) = length Cons (x, (concat l l2))
(por deni cao de concat)
ou seja = 1 + length (concat l l2) = length l + length l2 + 1
(por hip otese de induc ao). Done.
Prova concluda . . . QED.
2. Para toda a arvore ar, nodos ar altura ar
Demonstrac ao por induc ao sobre a arvore ar.
(Caso de Base)
nodos AV azia = 0 = altura AV azia. Done.
(Passo Indutivo)
Sejam ar1 e ar2 duas arvores, x um elemento.
Hip oteses de Inducao :
(a) nodos ar1 altura ar1
(b) nodos ar2 altura ar2
Ser a que temos:
nodos (Nodo(ar1, x, ar2)) altura (Nodo(ar1, x, ar2))?
Vejamos.
118
nodos (Nodo (ar1, x, ar2)) = nodos ar1 + nodos ar2 + 1 (por
denicao de nodos)
altura (Nodo (ar1, x, ar2)) = 1 + max(altura ar1, altura ar2)
(por deni cao de altura)
Dois casos possveis. a) altura ar1 > altura ar2 ou
b) altura ar1 altura ar2
No caso a) altura (Nodo(ar1, x, ar2)) = 1 + altura ar1 assim
sendo, porque nodos ar1 altura ar1 (por hip otese 1) temos
nodos (Nodo (ar1, x, ar2)) altura (Nodo (ar1, x, ar2)). Done.
o caso b) e identico.
Assim, a demonstracao esta concluda.
8.8 Execucao de automatos
Para ilustrar a programac ao sobre grafos de uma forma simples com base em
listas de adjacencias, podemos nos debrucar sobre a execucao de aut omatos
de estados nitos deterministas. Um bom exerccio pode ser transformar este
exemplo por forma a utilizar estruturas de dados mais escal aveis e ecientes.
O leitor podera reparar no uso da biblioteca Str que fornece func oes
de manipulac ao de strings e expressoes regulares muito convenientes e aqui
utilizadas para facilitar a leituras dos dados. A compilacao dever a incluir na
linha de comando a referencia a str.cma ou str.cmxa consoante o compilador
utilizado.
open List
open Str
open Scanf
open Printf
(**
Execu c~ ao de aut omatos deterministas
*)
(**
119
O tipo [simbolo] representa o tipo das letras (o alfabeto -
presentes nas fitas mas tambem nas transic~ oes). Aqui fixamos o tipo
char como sendo o alfabeto usado nestes automatos.
*)
type simbolo = char
(**
a fita de entrada e simplesmente uma lista de smbolos
*)
type fita = simbolo list
(**
Escolhemos representar os estados por inteiros. Em particular
tentaremos respeitar o invariante seguinte sobre a representac~ao dos
estados: Se houver [n] estados ent~ao estes s~ ao [0 1 2 3 .. n-1].
*)
type estado = int
(**
As transic~ oes [q1 --a--> q2] s~ ao representadas como [((q1,a),q2)] ao
detrimento da representa c~ao mais natural [(q1,a,q2)].
Esta pequena "nuance" permite uma pesquisa melhorada de uma transi c~ao
no conjunto das poss veis transic~oes (de tipo hash table, em que a chave e
[(q1,a)] e o conte udo e estado destino [q2])
*)
type transicao = ((estado*simbolo)*estado)
(**
Neste cenario, um aut omato (ou maquina) e dado pela relac~ ao de
120
transic~ao (a listas de adjacência, ou seja a lista das transic~oes),
*o* estado inicial e o conjunto dos estados finais. Sendo que o
alfabeto e conjunto dos estados se deduz automaticamente dos dados
anteriores.
*)
type maquina = (transicao list * estado * estado list)
(**
As configurac~oes da m aquina (determinista), aqui designada de
memoria, e simplesmente o par *do* estado actualmente activo (onde
a m aquina se encontra no momento a execuc~ao) e o buffer que resta
ainda por processar.
*)
type memoria = (estado * fita)
(**
uma excepc~ ao para assinalar o fim de uma execu c~ ao
*)
exception FIM of memoria
(**
[next] calcula o proximo estado, ou seja o estado [q] destino da
transic~ao [esta---simb--->q], se esta transi c~ao existir. Sen~ ao
(i.e. a excepc~ao [Not_found] foi lan cada) esta situa c~ ao configura
o fim da execuc~ao.
*)
let next simb maquina memo =
let (esta, restante) = memo in
try
let transicoes,b,c = maquina in
(assoc (esta,simb) transicoes)
with Not_found -> raise (FIM memo)
121
(**
[step] realiza um passo de execu c~ao do aut omato [maq] a partir da
configura c~ao [memo].
*)
let step memo maq =
let (aqui, restante) = memo in
(** se o buffer de entrada for vazio, ent~ ao acabou, sen~ao tratamos
do primeiro caracter do buffer. Ou seja, vamos ver que novo
estado atingimos com este caracter a partir do estado
actualmente activo (onde a execu c~ ao actualmente se encontra, o
estado [aqui]). Chamamos aqui a fun c~ ao [next] que trata deste
calculo. *)
match restante with
[] -> raise (FIM memo)
| el::li -> (next el maq memo,li)
(** [is_accepted] e um predicado que detecta se uma configura c~ ao
[memo] da execuc~ ao do aut omato [maq] prefigura a aceita c~ ao. Ou seja o
buffer de entrada encontra-se vazio e h a pelo menos um estado final na
configura c~ao
*)
let is_accepted memo maq =
let (aqui, restante) = memo in
let (trans,init,accept)= maq in
(mem aqui accept)&&(restante=[])
(** func~oes utilitarias simples*)
let em_par a b c = ((a, b),c)
let char_of_string s = s.[0]
(**
Lê no formato texto a palavra por reconhecer e o aut omato por executar.
A leitura devolve as estruturas correspondentes.
122
*)
let leitura () =
let dados = map (fun x -> char_of_string x)
(Str.split (Str.regexp "[ \t]+") (read_line ())) in
let initl = read_int () in
let finl = map (fun x -> int_of_string x)
(Str.split (Str.regexp "[ \t]+") (read_line ())) in
let input = ref [] in
try
while (true) do
input:= (scanf " %d %c %d " em_par)::!input
done; (dados,(!input,initl,finl))
with _ -> (dados,(!input,initl,finl))
(** a fun c~ ao [print_output] analisa a configura c~ ao final e imprime na
sa da standard o veredicto.
*)
let print_output memo maq=
if (is_accepted memo maq)
then printf "YES\n"
else printf"NO\n"
let main () =
let dados,maquina = leitura () in
let (a,b,c) = maquina in
try
let memor = ref (b,dados) in
(** Enquanto houver passos de execu c~ ao por realizar, executar. A
excep c~ ao [FIM] e lan cada para assinalar o fim da
execu c~ ao. *)
while true do
memor := (step !memor maquina)
done
with
FIM x -> print_output x maquina
;;
123
main ();;
(** exemplo de entrada:
a a b a
0
1 2
0 a 0
0 b 1
0 a 3
1 a 2
2 a 3
3 a 1
3 a 2
*)
8.9 Parsing com uxos e computacao simbolica
Neste exemplo, ilustramos as facilidades que a linguagem OCaml, ` a seme-
lhanca das linguagens do mesmo paradigma, nos oferece para a programacao
simb olica. Um exemplo cl assico e assim a unica cao de termos de primeira
ordem. Utilizaremos o formato classico dos concursos de programacao ACM
para a apresentac ao do enunciado (do exerccio).
O objectivo deste exerccio e a implementa cao de um dos mais famosos
e importantes algoritmo em informatica: o algoritmo de unicacao de pri-
meira ordem. Historicamente o primeiro estudo formal e algoritmo para este
problema foram denidos e apresentados por Robinson em 1965 (Robinson
J. A. [1965], A machine oriented logic based on the resolution principle, J.
of the ACM 12(1), 23-41) e permitiu avancos fundamentais em Ciencia da
Computacao, L ogica, Inteligencia Articial, Demonstracao por Computador
e ate mesmo em Compiladores. O problema e no entanto relativamente sim-
ples de enunciar e trata essencialmente de encontrar formas de tornar dois
termos, digamos u e v, iguais via uma instanciac ao adequada, designada de
substituicao, das vari aveis presentes em cada termo. Mais formalmente esta
substituic ao, digamos , permite identicar os dois termos, i.e. (u) = (v).
Tais substituic oes, quando existam, s ao chamadas de unificadores.
Para claricar as ideias, imagine que se pretenda unicar
f(f(X, a), g(f(b, Y ))) com f(Y, g(Z)). (note que os identicadores em
mai usculas s ao vari aveis (i.e. podem ser instanciadas) e os outros identica-
124
dores s ao funcoes ou constantes (designados de atomos neste contexto)). A
notac ao utilizada e:
f(f(X, a), g(f(b, Y )))
?
= f(Y, g(Z))
A resposta e sim. De facto se se escolher a substituic ao =
Y := f(X, a); Z := f(b, f(X, a)) ent ao (f(f(X, a), g(f(b, Y )))) =
f(f(X, a), g(f(b, f(X, a)))) (o Y foi substitudo pelo valor indicado na subs-
tituic ao) e (f(Y, g(Z))) = f(f(X, a), g(f(b, f(X, a)))) (o Y e o Z foram
substitudos pelos valores indicados em ). Logo (f(f(X, a), g(f(b, Y )))) =
(f(Y, g(Z))).
No contexto deste exerccio estamos interessado no que chamamos os
unicadores principais (most general unier, em ingles). Por exemplo os
dois termos X e f(Y ) tem varios unicadores: X := f(Y ), mas ainda
X := f(a); Y := a ou X := f(f(b)); Y := f(b). No entanto so X :=
f(Y ) nos interessa aqui por esse unicador ser o mais geral de todos.
Apresentamos aqui um algoritmo para a unicac ao (uma versao melho-
rada do algoritmo original apresentado pelo proprio Robinson): o algoritmo
de Martelli-Montanari.
Este algoritmo processa conjuntos nitos de equa coes
E = s
1
?
= t
1
, . . . , s
n
?
= t
n
e uma substitui cao . Inicialmente E = s

?
= t, onde s e t s ao os dois
termos por unicar, e = . ent ao o algoritmo escolhe arbitrariamente uma
equac ao de E (por exemplo se este conjunto for codicado por uma lista, a
escolha pode ser o primeiro elemento da lista). Esta equac ao e processada
da seguinte forma:
Equacao retirada de E Ac cao por realizar
1 f(s
1
, . . . , s
n
)
?
= f(t
1
, . . . , t
n
) substituir em E pelas equa coes s
1
?
=
t
1
, . . . , s
n
?
= t
n
2 f(s
1
, . . . , s
n
)
?
= g(t
1
, . . . , t
n
) falhar
3 X
?
= X retirar a equacao de E
4 X
?
= t ou t
?
= X onde X nao occorre em t juntar X := t a , aplicar a substitui cao
X := t a E e ao termos de e nalmente
retirar esta equacao de E
5 X
?
= t ou t
?
= X onde X occorre em t e X ,= t falhar (o chamado occur check)
125
O procedimento deve ser repetido ate E car vazio ou este falhar.
V arios algoritmos para a unicac ao (alem do al-
goritmo apresentado) podem ser encontrados em
http://lat.inf.tu-dresden.de/research/papers/2001/BaaderSnyderHandbook.ps.gz
ou ainda http://www.dcs.kcl.ac.uk/staff/endriss/cs3aur-02/pdf/unification.pdf
(google e aqui e mais uma vez o vosso amigo....).
Aqui vao alguns exemplos (retirados do wikipedia) :
A
?
= A : unicac ao bem sucedida (a substituic ao e vazia, ja que os
termos sao iguais)
A
?
= B, B
?
= abc : unicac ao bem sucedida, = A := abc; B := abc
xyz
?
= C, C
?
= D : a unicacao e simetrica, ou seja = C := xyz; D :=
xyz
abc
?
= abc : unicac ao bem sucedida (a substituic ao e vazia, j a que os
termos sao iguais)
abc
?
= xyz : a unica cao falha j a que os atomos s ao diferentes
f(A)
?
= f(B) : unicac ao bem sucedida, = A := B
f(A)
?
= g(B) : a unicac ao falha visto que f ,= g
f(A)
?
= f(B, C) : a unicac ao falha ja que f apresenta aridades dife-
rentes
f(g(A))
?
= f(B) : unicac ao bem sucedida, = B := g(A)
f(g(A), A)
?
= f(B, xyz) : unicac ao bem sucedida, = A :=
xyz; B := g(xyz)
A
?
= f(A) : Unica cao innita. A e unicada com f(f(f(f( )))).
Em logica de primeira ordem esta situac ao e proibida, e neste exerccio
tambem. Este caso e detectado vericando que a substituic ao A :=
f(A) tem A a ocorrer em ambos os lados. Este teste e designado de
occurs check.
A
?
= abc, xyz
?
= X, A
?
= X : a unicacao falha porque de facto abc ,=
xyz.
126
Input
O input organizado em duas linhas. Na primeira linha e apresentada o pri-
meiro termo, na segunda linha o segundo termo. Por convenc ao as func oes e
as constantes s ao introduzidas por identicadores sem mai usculas e as varia-
veis s ao introduzidas por identicadores em letras mai usculas.
Output
A palavra NO se os dois termos n ao se unicam. A palavra YES caso
contr ario. Neste caso a lista das variaveis instanciadas e apresentada uma
por linha, no formato nome da vari avel = termo". Esta lista e ordenada
pelo nome das variaveis.
Sample Input 1
f(a,g(Y))
f(Y,X)
Sample Output 1
YES
X = g(a)
Y = a
Sample Input 2
f(X,g(b,h(X)))
f(X,g(b,h(X)))
Sample Output 2
YES
Sample Input 3
f(X,g(b,h(X)))
f(a,g(X,h(X)))
127
Sample Output 3
NO
Sample Input 4
f(X,g(b,h(X)))
f(b,g(X,t(X)))
Sample Output 4
NO
Uma solu cao pode ser a seguinte. O leitor reparara no uso da biblioteca
Genlex e no uso dos uxos. Para essa ultima o leitor devera incluir no
comando de compilac ao as devidas opcoes de compilac ao.
(** Unifica c~ ao de termos de primeira ordem -
Inspirada de "Term Rewriting and All That -
Franz Baader and Tobias Nipkow -
http://www4.in.tum.de/~nipkow/TRaAT/**)
open List
open Genlex
open Str
open String
open Char
open Printf
type vname = string
type term = V of vname | T of (string * (term list))
type subst = (vname * term) list
(* indom: vname -> subst -> bool *)
(* Testa se a vari avel x esta na substituic~ ao s *)
let indom x s = exists (fun (y,_) -> x = y) s
128
(* app: subst -> vname -> term *)
(* Aplica uma substitui c~ ao a uma vari avel. *)
(* Isto e: se existe "x:= t" em substit
ent~ao (app substit x) devolve t *)
let rec app substit x =
match substit with
[] -> V x
| ((y,t)::s) -> if x=y then t else app s x
(* lift: subst -> term -> term *)
(* A func~ao lift generaliza a func~ao app. *)
(* Ou seja: lift s t devolve s(t). i.e.
devolve t em que todas as variaveis que est~ao
em s foram substitudas pelo valor indicado em s *)
let rec lift s = function
(V x) -> if indom x s then app s x else V x
| (T(f,ts)) -> T(f, map (lift s) ts)
(* occurs: vname -> term -> bool *)
(* (occurs x t) testa se a variavel x occorre em t *)
let rec occurs x = function
(V y) -> x=y
| (T(_,ts)) -> exists (occurs x) ts
exception UNIFY
(* solve: (term * term) list * subst -> subst *)
(* Fun c~ ao principal.
solve E,s --> E e o conjunto de equac~oes por explorar *)
(* --> s e a substitui c~ ao actualmente calculada *)
(* Algoritmo utilizado: o exposto no enunciado *)
(* Olhamos para a primeira equac~ ao de E, *)
(* 4 casos gerais -----> *)
(* 1) E esta vazio *)
(* 2) equac~ ao da forma X = termo *)
(* 3) equac~ ao da forma termo = X *)
129
(* 4) equac~ ao da forma termo1 = termo2 *)
(* No final: *)
let rec solve = function
([], s) -> s
| ((V x, t) :: li, s) ->
if V x = t then solve(li,s) else elim(x,t,li,s)
| ((t, V x) :: li, s) -> if V x = t then solve(li,s) else elim(x,t,li,s)
| ((T(f,ts),T(g,us)) :: li, s) ->
if f = g
then
if List.length ts = List.length us
then
solve((combine ts us) @ li, s)
else raise UNIFY
else raise UNIFY
(* elim: vname * term * (term * term) list * subst -> subst *)
and elim (x,t,su,s) =
if occurs x t then raise UNIFY
else let xt = lift [(x,t)]
in solve(map (fun (t1,t2) -> (xt t1, xt t2)) su,
(x,t) :: (map (fun (y,u) -> (y, xt u)) s))
(* unify: term * term -> subst *)
(* invoca a fun c~ ao principal de unifica c~ ao: a fun c~ ao solve*)
(* Inicialmente E={t1=t2} *)
let unify(t1,t2) = solve([(t1,t2)], [])
let maiuscula s = let v = s.[0] in
((code v >= code A) && (code v <= code Z))
let trata s e =
match e with
[] ->
if maiuscula s then V s
else T (s,e)
| _ -> T (s,e)
130
(**
Vamos construir um lexer simples, com base no lexer generico
fornecido pela biblioteca Genlex.
A fun c~ao make_lexer precisa, para construir tal lexer, que lhe
seja fornecido o conjunto de palavras chaves (que ser~ ao distinguidas
dos identificadores) *)
let lexer = make_lexer ["("; ")"; ","]
(* Constru c~ao do parser com base nos fluxos e num parser descendente LL(1)
A gram atica LL(1) e:
E ::= id F
F ::= \epsilon
F ::= (E EL)
EL ::= ,E EL
EL ::= \epsilon
*)
let rec parse_expr = parser (* corresponde a entrada E da gramatica *)
[< Ident s; e = parse_F>] -> trata s e
and parse_F = parser (* corresponde a entrada E da gramatica *)
[< Kwd "("; e = parse_expr; el = parse_EL; Kwd ")" >] -> e::el
| [< >] -> []
and parse_EL = parser (* corresponde a entrada T da gram atica *)
[< Kwd ","; e = parse_expr; el = parse_EL >] -> e::el
| [< >] -> []
let parse_expression = parser [< e = parse_expr; _ = Stream.empty >] -> e;;
(* fun c~ ao principal de leitura usando streams*)
let expression_of_string s = parse_expression(lexer(Stream.of_string s));;
let rec string_of_expression e =
131
match e with
V s -> s
| T (e,el) -> (e^(if el = [] then "" else "("^(aux el)^")"))
and aux l =
match l with
[] -> ""
| [e] -> (string_of_expression e)
| e::li ->
( (string_of_expression e)^","âux li)
let main () =
let e1 = (expression_of_string (read_line ())) in
let e2 = (expression_of_string (read_line ())) in
try
let unific =(List.sort
(fun (a,b) (c,d) -> String.compare a c)
(unify (e1,e2))) in
print_string "YES\n";
(List.iter (fun x -> printf "%s\n" x)
(map (fun (x,e) -> x^" = "^(string_of_expression e)) unific))
with UNIFY -> printf "NO\n";;
main ()
Referencias
[1] D. Bagley. The great computer language shootout.
http://www.bagley.org/~doug/shootout
[2] E. Chailloux, P. Manoury, and B. Pagano. Developing applications with
objective caml. http://caml.inria.fr/oreilly-book, 2003.
[3] G. Cousineau and M. Mauny. The functional approach to programming.
Cambridge University Press, 1998.
132
[4] J.-C. Filli atre. Initiation ` a la programmation fonctionnelle.
Master Informatique M1, Universite Paris-Sud. Available at
http://www.lri.fr/~filliatr/m1/cours-ocaml.en.html, 2006.
[5] J. Hickey. Introduction to objective caml. Under publication, available
at http://files.metaprl.org/doc/ocaml-book.pd, 2008.
[6] X. Leroy. Functional programming and type systems. Master Pa-
risien de Recherche en Informatique (MPRI), Paris, available at
http://gallium.inria.fr/~xleroy/mpri/2-4/, 2011-2012.
[7] L. Pequet. Programmation fonctionelle
- introduction illustree en objective caml.
http://www-rocq.inria.fr/~pecquet/pro/teach/teach.html,
2002.
[8] D. Remy. Understanding, and Unraveling the OCaml Lan-
guage, volume LNCS 2395 of Applied Semantics. Advanced
Lectures, chapter ?, pages 413537. Springer-Verlag, 2002.
http://pauillac.inria.fr/~remy/cours/appsem/ocaml.pdf
[9] OCaml Development Team. The Objective Caml
system:Documentation and users manual, 2002.
http://caml.inria.fr/ocaml/htmlman/index.html
[10] P. Weis and X. Leroy. Le langage Caml. InterEditions, 1993. Available
at caml.inria.fr/pub/distrib/books/llc.pdf
133

Intro Ocaml

Enviado por

Dados do documentoclique para ver informações do documento

Direitos autorais:

Formatos disponíveis

Intro Ocaml

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Intro Ocaml

Enviado por

Direitos autorais:

Formatos disponíveis

Introducao `a Programacao Funcional

E importante realcar de que se trata duma linguagem em que valor e

E aqui importante realcar a necessidade da palavra chave rec. Esta e

E possvel estender os tipos de base com tipos denidos pelo programador.

E no entanto possvel, e mesmo facil, ter avaliac ao preguicosa de fun coes em

E possvel denir de forma simples estrutura de dados

E esta (propriedade) das estruturas de dados que designamos por persis-

E muito importante perceber aqui que existe partilha. A declara cao de l

E alias importante notar que o conceito da persistencia pode ser realizado

a (total) sobre f ormulas proposicio-

e uma substitui cao . Inicialmente E = s

Você também pode gostar