INE5363-Programação Funcional
Prof. João Bosco da Mota Alves
2001/1 - INE/CTC/UFSC
Bacharelado em Ciência da Computação
Ementa
–
–
–
–
–
–
–
Introdução
O Paradígma de Programação Funcional
A linguagem LISP
O dialeto XLISPWIN
Exemplo de Uso de XLISPWIN
Linguagem funcional moderna: CLEAN
Cálculo Lâmbda (l - Calculus)
Material didático
– Notas de aula
– OAKEY, S. Lisp para Micro. Rio de Janeiro,
Editora Campus, 1986.
– FRIEDMAN, D.; FELLEISEN, M. The Little
LISPer
(Third
Edition).
NJ,
Macmllan
Publishing, 1989.
– GORDAN, G. J. Common LISP Hints (Adaptado
para XLISPWIN ). Original
– Software CLEAN,
– STEELE, G. L. Common LISP: the Language.
Digital Press, 1984.
Introdução
• Linguagens de programação
– Visão geral
– Pontos de vista
– Implicações em eficiência/produtividade
• Linguagem de programação como forma
de comunicação entre o usuário e o
computador
Introdução
Máquina
Usuário
Assembly
Fortran
Paradígmas de Programação
• Procedimental ou Procedural
– Assembly, Fortran, Pascal, ...
• Orientado por Objeto
– Smaltalk, C++, VisualAge, Java, Delphi, ...
• Programação em Lógica
– Prolog, Trilogy, Parlog, ...
• Funcional
– Lisp, Hugs, Clean, Haskel, ...
Independência de Plataformas
• Independência de plataforma
– Não gerar código objeto direto
– Gerar código C padrão
– Compilar para máquina alvo
• Vantagem
– Código escrito uma única vez
• Desvantagem
– Trabalho adicional
Paradígma de Programação
Funcional
• Estuda-se paradígmas de programação
comparando-se com o procedimental, pois
– Foi o primeiro paradígma
– É o mais difundido
– Há algo com o qual comparar-se
• Faremos assim
Paradígma de Programação
Procedimental
• Seqüência de comandos permite a
transição de um estado da máquina a
outro
• Estado da máquina
– Conjunto de valores que define a situação
ou comportamento de um sistema
• Exemplo
– Estado1, (1, 2); estado2, (1, -4)
Paradígma de Programação
Procedimental
• Transição de estado
 0  1   2  ...   n
Um programa C
int fact(int n)
{ int x = 1;
while (n > 0)
{ x = x * n;
n = n - 1;
}
return x;
}
Paradígma de Programação
Procedimental
Estado
(n, x)
(6, 1)
(6, 6)
(5, 6)
(5, 30)
(4, 30)
(4, 120)
(3, 120)
(3, 360)
(2, 360)
(2, 720)
(1, 720)
(1, 720)
(0, 720)
Comando
x=16
n=61
x=65
n=51
x = 30  4
n=41
x = 120  3
n=31
x = 360  2
n=21
x = 720  1
n=11
Comentário
Estado inicial, 
2o estado, 1
3o estado, 2
4o estado, 3
5o estado, 4
6o estado, 5
7o estado, 6
8o estado, 7
9o estado, 8
10o estado, 9
11o estado, 10
12o estado, 12
Estado final, 13
Paradígma de Programação
Procedimental
• O conceito de estado está vinculado,
implicitamente, ao paradígma de
programação procedimental
• Não possuindo significado explícito
nos demais paradígmas
Paradígma Funcional
• Um programa é simplesmente uma
função, ou expressão, daí o nome
• Sua execução significa a avaliação
dessa função
• Comparando com o procedimental,
onde f é a função (programa)
 n  f  0 
Paradígma Funcional
• Exemplo
– O mesmo problema do fatorial de n, n!
– Em linguagem funcional
fatorial (n) = prod [1..n]
• Veja que não faz sentido algum o
conceito de estado da máquina
Paradígma Funcional
• Sob essa visão
–
–
–
–
Não
Não
Não
Não
há estados
há atribuições
há seqüência de comandos
há repetições
• Mas há recursão e funções de alta
ordem
Paradígma Funcional
• Pode parecer impraticável uma
linguagem sem
– Variáveis
– Atribuições
– Seqüência de comandos
• Como visto aqui, isso não é verdade
• Pelo contrário: facilita em muitos
casos
A linguagem LISP
• Principais idéias que sustentam o
paradígma de programação funcional,
datam da década de 30
– Cálculo Lâmbda: um formalismo
matemático criado por Alonzo Church
• A mais antiga implementação foi
LISP, desenvolvida por McCarthy na
segunda metade da década de 50
A linguagem LISP
• Vamos às suas principais características
• Tipos de dados
– O átomo e a lista
– É com apenas esses dois tipos de dados que
se constroem as expressões-S, as
estruturas basilares de LISP
Exemplos de átomos
• atom
– É um átomo, pois é um string de
caracteres que começa com a letra a.
Nota: Em algumas implementações, escreve-se
(quote atom), ou 'atom.
• carnaval
– É um átomo, pois é um string de
caracteres que começa com uma letra.
Exemplos de átomos
• 1500
– É um átomo, pois é um string de
caracteres que começa com um dígito.
• 150carnavais
– É um átomo, pois é um string de
caracteres que começa com um dígito.
• b
– É um átomo, pois é um string de 1
caracter começando com letra ou dígito.
Exemplos de átomos
• *figueirense$
– É um átomo, pois é um string de caracteres
que começa com uma letra, um dígito ou um
caracter especial que não é abre parênteses,
(, ou fecha parênteses, ).
• 6!
– É um átomo, pois é um string de caracteres
que começa com uma letra, um dígito ou um
caracter especial que não é abre parênteses,
(, ou fecha parênteses, ).
Exemplos de listas
• (atom)
– É uma lista: um átomo entre parênteses
• (atom carnaval 1500)
– É uma lista: coleção de átomos entre
parênteses.
• (atom carnaval) 1500
– Não é uma lista: duas expressões-S que
não estão entre parênteses. A primeira é
uma lista e a segunda é um átomo
Exemplos de listas
• ((atom carnaval) 1500)
– É uma lista, pois as duas expressões-S
estão entre parênteses. A primeira é
uma lista e a segunda é um átomo
• Tente fazer alguns exercícios para
fixar os conceitos de átomos e listas
Expressão-S (S-expresssion)
• jbma
– É uma expressão-S, pois todo átomo é
uma expressão-S
• (j b m a)
– É uma expressão-S, pois é toda lista é
uma expressão-S
• ((j b m) a)
• É uma expressão-S, pois é uma lista
Expressão-S
• (o que seria do musica baiana se
inexistisse eh oh eh oh)
– É uma lista, pois é uma coleção de
expressões-S entre parênteses
• ((j b m) a)
– Nessa lista há duas expressões-S. A lista
(j b m) e o átomo a
Expressão-S
• ()
– É uma lista, pois contém zero
expressões-S. Essa expressão-S especial
é chamada de lista nula ou lista vazia, as
vezes chamada, também, nil
• ()
– É um átomo, pois ( ) é ambos, uma lista e
um átomo
Expressão-S
• (()()()())
– É uma lista, pois é uma coleção de
expressões-S entre parênteses
• Agora vejamos como se representa
funções em LISP
Representação de funções
• LISP
– Processamento de listas
– Representa funções através de listas
– O nome da função é sempre o primeiro
elemento da lista
• Veja alguns exemplos de funções
representadas em LISP
Funções em LISP
• f(x,y), na notação usual matemática
– (f x y)
– Nome da função, f, como o primeiro
elemento e os demais elementos, x e y,
representam os seus argumentos
• (nome-da-funcao argumento1
argumento2 ...)
Funções em LISP
• 3*7, usando-se a notação infixa
• Em LISP, notação pré-fixa
– (* 3 7)
Funções em LISP
• A origem do nome LISP
– LISt Processing (processamento de listas)
– Exemplos de execução LISP
> (+ 3 4)
7
> (- 6 4)
2
; operador adição
; retorno da função
; operador subtração
; retorno da função
> (car '(6 4))
6
; função car
; retorno da função
> (cdr '(6 4))
(4)
; função cdr
; retorno da função
Funções em LISP
• LISP só pensa naquilo
– Toda vez que você fornece uma lista, a
executa, a menos que você o alerte para
não o fazer
• Por exemplo, se você fornecer a lista
(6 5 7) e a mandar executar, LISP irá
retornar mensagem de erro
– 6 não é uma função
• Como alertá-lo, então?
Funções em LISP
• Em um dos exemplos acima, solicitouse a execução de
> (car '(6 4))
• Veja que a lista que é fornecida como
argumento da função car é precedida
pelo símbolo “ ’ ”
• Esse é o alerta: proibido avaliar
• Veja histórico sobre Expressão-S nas
notas de aula
Função universal como
interpretador LISP
• Na Teoria da Computação, é comum
investigar funções universais
• Exemplo, a máquina universal de Turing
– É uma máquina de Turing que pode simular
qualquer outra máquina de Turing que voce
possa descrever
• McCarthy fez exatamente isso com
LISP
Função universal como
interpretador LISP
• Definiu uma função universal LISP
– Que poderia interpretar qualquer outra
função LISP
• Em outras palavras
– Escreveu um interpretador LISP, em LISP
• Como LISP manipula apenas listas
– Escrever uma função universal iria requerer
desenvolver-se uma forma de representar
programas LISP como estruturas de listas
Função universal como
interpretador LISP
• Exemplo
f(x+y; u*z)
• Pode ser representada na forma de lista
(f (+ x y) (* u z))
• Em Algol, esse artifício era chamado de
Expressão-M (M-Expression)
• Aqui, M significava metalangue
(metalinguagem)
Função universal como
interpretador LISP
• Em LISP, a expressão acima passou a
ser chamada de Expressão-S (SExpression)
• Em LISP, S siginificava simbolic
language (linguagem simbólica)
• Nesse momento, um dos membros do
grupo constatou que tinham em mãos,
de fato, um interpretador
Função universal como
interpretador LISP
• Traduziram a função universal para
Assembly e a linkaram com as subrotinas de manuseio de listas
• E esse foi o primeiro sistema LISP
• Isso requeria o uso de Expressão-S,
considerado uma inconveniência
temporária
Função universal como
interpretador LISP
• Tentaram uma melhor notação, mas
nunca conseguiram completá-la, e
continuaram a usar a Expressão-S
• Hoje, sabe-se, que essa
representação é uma das principais
vantagens de LISP
• LISP tornou-se a principal linguagem
para IA, até os anos 70
O dialeto XLISPWIN
• Símbolos representam átomos
• Se você usar letras, dígitos e hífens,
você estará seguro de não errar
• Restrições
– Não use apenas dígitos (inteiro?)
– Não use um hífen inicial (inteiro negativo)
• Veja alguns exemplos em XLISPWIN
O dialeto XLISPWIN
a
foo
bar
baaz-quux-garply
• São exemplos de átomos em XLISPWIN
• O caractere ; é para comentário
– Tudo, após o mesmo e até o final da linha, é
considerado comentário
– É ignorado pelo interpretador
O dialeto XLISPWIN
• Exemplos de funções XLISPWIN
> (setq a 5) ; armazena um número, 5
; como o valor de um símbolo, a
5
>a
; pega o valor, 5, de um símbolo, a
5
Funções XLISPWIN
> (let ((a 6)) a)
6
>a
5
; faz o valor de um
; símbolo, a
; temporariamente
; igual a 6
; retorna 5, pois o
; let já foi interpretado
Funções XLISPWIN
> (+ a 6)
; Usa o valor de um símbolo como
; um argumento para a função
11
; Tenta pegar o valor de um símbolo sem valor
>b
error: unbound variable - b
if continued: try evaluating symbol again
• Note a mensagem de erro: algo deu errado
Símbolos especiais
• O símbolo t (de true, verdadeiro)
• O símbolo nil (em LISP, utilizado para
representar o valor lógico falso)
– Também, como visto, pode representar a
lista vazia
> (if t 5 6)
5
Símbolos especiais
> (if nil 5 6)
6
> (if 4 5 6)
5
• A função if é aplicada a 3 argumentos
– Quando o 1o é nil, retorna o 3o
– Quando o 1o é t (ou qq. outro, retorna o
3o
• Retorna o argumento ou sua avaliação
Símbolos especiais
• Símbolos como t e nil são chamados
de auto-avaliantes, porque eles
mesmos se avaliam
• Há toda uma classe de símbolos autoavaliantes denominados keywords
• Qualquer símbolo cujo nome começa
com dois pontos, :, é uma keyword
Símbolos especiais
> :this-is-a-keyword
:THIS-IS-A-KEYWORD
> :so-is-this
:SO-IS-THIS
> :me-too
:ME-TOO
Números (átomos numéricos)
• XLISPWIN suporta 4 tipos de números
– Inteiro
– Real (com ponto decimal e, também, na
notação científica)
– Racional
– Complexo