As funções também podem ser argumentos para outras funções

Prévia do material em texto

As funções também podem ser argumentos para outras funções, como essa função
"Aplique-a-mickey-rato":
lambda f. (f) mickey mouse-
Podemos então chamar esta função com o "pintado amarelo" para pintar
mickey mouse-amarelo:
(Lambda f. (F) mickey-mouse) lambda I x.pintado-amarelo x
-> (Lambda x.pintado-amarelo x) mickey mouse-
-> Pintado mickey-mouse-amarelo
Avaliando expressões lambda é baseada em dois argumentos regras de substituição
formal, por argumentos reais, chamado de redução de alfa e beta redução. Nós não vamos
para vê-la em pormenor, apenas comentar a regra de redução de beta:
Aplicando um argumento para uma expressão lambda é conseguida substituindo o
expressão corporal-lambda a variável vinculada pelo argumento:
(Lambda x.P) Q -> [Q / x] P
onde
[Q / X] P
Isso significa que a substituição de
X
por
Q
em qualquer ocorrência livre
X
em
P
.
Para obter mais informações sobre o cálculo lambda:
Um
Introdução
para
Lambda
Cálculo
e
Esquema
(Http://www.jetcafe.org/jim/lambda.html) e
lambda
cálculo
em
o
Wikipedia
(Http://en.wikipedia.org/wiki/Lambda_calculus).
1.4. Modelo de substituição
Durante a aula de hoje temos vindo a falar sobre o paradigma declarativo, o paradigma
funcional e que apresentou um modelo formal que tem sido a fonte de paradigma
funcional. Vamos terminar com o modelo de computador que irá explicar a semântica
Nós escrever programas dentro do paradigma funcional. Esta é a
modelo
substituição
.
Um modelo computacional é um formalismo (conjunto de regras) que definem o
operação de um programa. Para Scheme e linguagens funcionais
com base na avaliação das expressões, o modelo computacional define o que será o
resultado da avaliação de uma expressão particular.
O modelo de substituição baseia-se numa versão simplificada da regra redução
cálculo lambda.
Regras para avaliação de uma expressão
e
Esquema:
1.
Se
e
É um valor primitivo, retorna este valor.
Tema 2: Características de programação funcional
Page 6
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
2.
Se
e
é uma variável, retornar seu valor associado.
3.
Se
e
é uma expressão do tipo (
f arg1
...
argn
), Onde
F
o nome de um procedimento
primitiva ('+', '-', ...), avaliando
arg1
...
argn
e aplicar o método para o resultado.
4.
Se
e
é uma expressão do tipo (
f arg1
...
argn
), Onde
F
o nome de um procedimento
composto (definido com 'definir'), substitua
F
seu corpo, substituindo cada
parâmetro formal do procedimento para o argumento correspondente avaliada. Avaliar
a expressão resultante.
Para ilustrar estas regras, vamos definir uma função:
(Definir (double x) (x + x))
(Definir (y quadrado) (x e y))
(Definir (f z) (+ quadrado (z duplo)) 1))
E agora vamos ver o que acontece quando executamos
(F (1 + 2))
utilizando o modelo
Substituição:
1.
Avaliaram a expressão: f é um procedimento; o que é
(2 + 1)
? ->
(F 3)
)
2.
Agora vamos levar o corpo
F
e substituímos
3
por
z
:
(+ Square (duplo 3))
1)
3.
Agora vamos avaliar a expressão resultante:
+
indica o procedimento
soma
,
1
Ele avalia a
1
. O que é
(Square (duplo 3))
?
quadrado
É um procedimento composto; e
o que é
(Duplo 3)
?
único
É um outro composto e procedimento
3
Ele avalia a
3
.
Assim, uma vez que nós avaliamos todos, podemos começar a implementar procedimentos.
Começamos
único
substituindo o corpo da função:
(+ (Square (+ 3
3)) 1)
4.
Agora, o que é (3 + 3)? ->
(+ (Praça 6) 1)
5.
Agora, o corpo é substituído
quadrado
:
(+ (* 6 6) 1)
6.
O que é
(* 6 6)
? ->
(36 + 1)
7.
O que
(36 + 1)
? ->
37
1.4.1. Vs. ordem de avaliação normal, Aplicação
A exemplo do padrão de substituição que vimos foi feito usando o "fim
aplicação ", onde todos os procedimentos e argumentos são avaliados antes
executar a chamada de função.
Outra forma de avaliar expressões está usando a "ordem normal" expandir completamente
os procedimentos até que tudo é expressa por operações primitivas e
auto-avaliações, e, em seguida, avaliar a expressão.
O mesmo problema como antes:
(F (1 + 2))
1.
Ampliamos
F
Deixando
(2 + 1)
unevaluated:
(+ (Square (duplo (+ 2 1)))
1)
Tema 2: Características de programação funcional
Página 7
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
2.
Agora vamos expandir
quadrado
:
(+ (* (Duplo (2 + 1)) (duplo (+ 2 1)))
1)
3.
E agora nós expandimos
único
:
(+ (* (+ (2 + 1) (2 + 1)) (2 + 1) (+ 2
1))) 1)
4.
Finalmente, temos expandido em torno dos operadores primitivos e valores autoevaluamos. Eles
Faz um por um
(+ (* (+ 3 (2 + 1)) (+ (2 + 1) (2 + 1))) 1)
(+ (* (3 + 3) (+ (2 + 1) (2 + 1))) 1)
(+ (* (3 + 3) (+ 3 (2 + 1)) 1))
(+ (* (3 + 3) (3 + 3))) 1)
(+ (* 6 (3 + 3)) 1)
(+ (* 6 6) 1)
(36 + 1)
37
Vimos as duas formas de avaliação: a ordem de aplicação, avaliar
todos os argumentos completamente antes de aplicar o procedimento. Considerando que, no
ordem normal, o primeiro completamente expandido até que todos os procedimentos são
expressa por operações e os valores primitivos. Em seguida, em um e outro, que podemos
encontrar a solução de expressão.
Uma consideração muito importante é que a programação funcional, em que uma função
sempre retorna o mesmo valor quando chamado com os mesmos argumentos, a ordem
ordem aplicativo normal e sempre retornam o mesmo resultado. No entanto, este não faz
Isso acontece quando estamos em uma linguagem não-funcional. Considere o seguinte exemplo:
Vamos definir uma função que sempre deve retornar 0:
(Definir (zero x) (- x)); Essa função sempre
; Você deve retornar 0.
Agora vamos avaliar
(Zero (aleatório 10))
com a ordem normal e fim aplicativo.
Ordem aplicativo:
(Zero (aleatório 10))
(Random 10) ==> 5
(Zero 5) ---->
(- 5 5) ==> 0
0; A ordem de aplicação retorna 0
Ordem normal:
(Zero (aleatório 10))
(Zero (aleatório 10)) ---->
(- (Random 10) (10 aleatório))
(Random 10) ==> 4
(Random 10) ==> 8
Tema 2: Características de programação funcional
Page 8
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
(- 08 abril) ==> -4
-4; A ordem normal não
A regra é que se você está fazendo a programação funcional, você recebe as mesmas respostas, quer
que é a ordem de avaliação. Por que não é assim no caso de
(Zero (aleatório
10))
? Porque não é uma função pura pois ele pode retornar valores diferentes em diferentes
invocações.
Outra diferença entre a avaliação aplicativo normal e avaliação é a eficiência. Ver
Um exemplo. Tente computação
(Square (praça (+ 2 3)))
em ordem de avaliação normal. Neste caso, a ordem de aplicação é mais eficiente proque
adicionar 2 e 3 apenas uma vez, e não quatro. (Mais tarde, porém, vemos que esta não é uma regra
Geralmente, por vezes, a fim normal é mais eficiente).
2. Abordagem Prática à PF
2.1. Atrações do paradigma funcional
Um dos primeiros modelos de computador, o cálculo lambda (Alonzo Church, 1930)
É completamente baseado em uma abordagem funcional, criação e utilização de funções
matemática. Este modelo computacional lançou as bases teóricas do que mais tarde
seria linguagens de programação funcional.
A popularidade do paradigma funcional tem sido em grande parte devido ao sucesso da linguagem
Programação Lisp (e seus dialetos, como Scheme). Ambos são Lisp e Scheme
idiomas que estão agora a ser utilizados (como um exemplo de utilização de, como Lisp
projetos reais de linguagem de programação, conversa ler
Paul
Graham
(Http://www.paulgraham.com) intitulado
Espancamento
o
Médias
(Http://www.paulgraham.com/avg.html), que explica como usou o Lisp
construir
Viaweb
(Http://www.paulgraham.com/vwfaq.html), uma das primeiras lojas
On-line adquirida em 1998 pela Yahoo).
Note-se que tanto Lisp e Scheme não são linguagens funcionais puras (a
Ao contrário de outras linguagens como Haskell). Nestas primeiras classes que você vai usar
apenas o Esquema carracterísticas funcional. Sua licença para mais tarde
construções imperativas.
Entre as características do paradigma funcional que incluem:
•
A programação declarativa
•
Definição e avaliação de funções
Tema 2: Características de programação funcional
Page 9
Copyright © 2006 Departamento.CCIA, da Universidade de Alicante Todos os direitos reservados.
•
Usando a recursão
•
Funciona como dados primitivo
Nós discutimos na aula anterior alguns conceitos de programação declarativas em
aula hoje vamos tentar os outros três características. Nós vamos fazer a partir de um
bastante prático, com numerosos exemplos em Scheme.
2.2. Definição e avaliação de funções
Qualquer linguagem funcional permite a definição de novas funções como uma forma de
abstracção, e a avaliação da expressão como uma forma de computação.
Vimos como definir e avaliar funções no Esquema:
(Definir (praça x)
(X * x))
(+ (Praça 3) (Praça 2))
Estamos definindo uma função com um
argumento formal
(X) como tendo
corpo
o
expressão (* xx) e nós estamos dando o nome de
quadrado
. Depois de avaliar um
expressão que nós chamamos a função recém-definido e função primitiva '+'.
2.3. Usando a recursão
Outro elemento comum a todas as línguas funcionais é o uso de recursão de
funções expressas em outros idiomas são expressos iterações. Muitas vezes mais
simples e natural para utilizar uma recursividade na definição de uma função. Hoje vamos ver alguns
exemplo simples. Em aulas posteriores nós recursão mais Scheme.
Fatorial
Um bom exemplo é a função típica
fatorial
que calcula o fatorial de um número.
Matematicamente, o factorial de um número pode ser expressa com a seguinte formulação:
Esta expressão tem um esquema de tradução direta:
(Definir (fatorial x)
(Se (x = 0)
1
Tema 2: Características de programação funcional
Page 10
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
(* X (fatorial (- x 1)))))
> (Factor 8)
40320
> (Factor 30)
265252859812191058636308480000000
Sumatorio
Outro exemplo de uma função recursiva é a soma de um número inicial de até um limite.
Matematicamente é expressa com a seguinte fórmula:
No Esquema:
(Definir (soma min max)
(Se (> min-max)
0
(+ Min (soma (+ 1 min) max))))
> (Soma de Março de 12)
75
Finalmente um exemplo usando símbolos e funções que vimos em uma classe anterior
vazio?
,
primeiro
,
bf
e
igual?
.
Lembre-se que cada uma destas funções:
•
(Vazio? Word)
: Verifica
palavra
É uma cadeia vazia
•
(Primeira palavra)
: Retorna o primeiro caractere de um símbolo (como seu símbolo
tempo)
•
(Palavra Bf)
: Retorna o resto de um símbolo, depois de retirar a sua primeira
personagem
•
(Equal? ​​Pal1 PAL2)
: Verifica se dois símbolos são iguais
Função
(Elemento? Palavra X)
retornos
#t
ou
#f
consoante
X
é um
símbolo está dentro
palavra
:
(Definir (elemento? Palavra X)
(Condici
((Vazio? Word) #f)
((Equal? ​​X (primeira palavra)) #t)
(Else (elemento? X (palavra bf)))))
> (Elemento? 'A' Olá)
#t
Tema 2: Características de programação funcional
Page 11
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
No caso geral, a primeira função aplicada ao resultado da chamada recursiva
Todas as outras funções para aplicar o número
X
.
2.4.1. Esquema Lambda
Os tipos de dados primitivos podem ser tratados diretamente línguas
programação, sem dar nome (atribuí-los a variáveis). Por exemplo, quando queremos
chamar qualquer função (como
quadrado
) Com o número "4" como um argumento,
diretamente escrever "4" e, portanto, nós nos referimos a esse número "4":
(Round 4)
Não há necessidade de fazer:
(Define quatro 4)
(Quatro quadrado)
Dissemos que as funções são primitivos Esquema tipos de dados. Será que eles atender, em seguida,
o proprietário anterior? Você pode usar uma função sem dar-lhe um nome? A resposta é que
Sim, através do formulário especial
lambda
.
Sintaxe
lambda
Ela é:
(Lambda (<arg1> ... <argn>) <body>)
A forma lambda especial constrói uma função sem nome e devolve-lo.
Seus argumentos e seu corpo: Para definir uma função de dois elementos são necessários. Estes
dois elementos são então definido a palavra
lambda
.
Por exemplo, na seguinte expressão:
(Lambda (X)
(X * x))
uma função que tem um único argumento é definido (
X
), E cuja expressão corporal
(X * x)
. É a função
quadrado
.
Se nós executarmos essa expressão no interpretador Scheme vai ver que o resultado de sua
A avaliação é uma
procedimento
:
> (Lambda (X) (x * x))
#procedure: 3: 2
Com este procedimento, que retorna Esquema (o chamado procedimento com o críptico
nome
#procedure: 3: 2
) Nós podemos fazer muitas coisas. Exemplos:
1.
Podemos dar-lhe um nome e ter uma função chamada que então podemos usar:
Tema 2: Características de programação funcional
Page 15
Copyright © 2006 Departamento. CCIA, da Universidade de Alicante Todos os direitos reservados.
> (Definir quadrado (lambda (x) (x * x)))
> (Praça 3)
9
2.
Passá-lo como um argumento para outra função que suporta outras funções como parâmetro:
> (Definir (aplicar-2 f g x)
(F (x g)))
> (Definir (SUM-5 x)
(X + 5))
> (Aplicar-2 soma-5 (lambda (X) (x * x)) 3)
14
3.
Podemos avaliar imediatamente colocar um parêntese de abertura (lembre-se que
discutido na primeira semana de classe que abrir parênteses "(" serviu para
funções ou formas especiais que os seguem) lançar:
> ((Lambda (X) (x * x)) 3)
9
3. As referências,
Para saber mais sobre as questões que discutimos nesta classe você pode verificar o seguinte
Referências:
•
Estrutura
e
Interpretação
de
Computador
Programas
(Http://mitpress.mit.edu/sicp/full-text/book/book.html), Abelson e Sussman, MIT Press
1996 (pp. 13-17). Disponível biblioteca politécnico (
acesso
ao
catálogo
(Http://gaudi.ua.es/uhtbin/boletin/285815))
•
Enciclopédia de Ciência da Computação (Wiley, 2000). Disponível na biblioteca Politécnica
(POE R0 / E / I / NCS / RAL). Verifique as entradas:
• A programação funcional
• cálculo Lambda
• Lisp
• Lista de processamento
•
Conceitos de Linguagens de Programação, John C. Mitchel, Cambridge University Press,
2003. Cap. 3, 4.2 e 4.4. Disponível biblioteca politécnico (POE I.062 / MIT / CON).
•
Lambda
cálculo
(Http://en.wikipedia.org/wiki/Lambda_calculus) (Wikipedia)
•
Funcional
programação
(Http://en.wikipedia.org/wiki/Lambda_calculushttp://en.wikipedia.org/wiki/Lambda_calculus)
(Wikipedia)
•
Espancamento
o
Médias
(Http://www.paulgraham.com/avg.html) ensaio
Paul
Graham
(Http://www.paulgraham.com)
	Item 3: Recursos de Programação
funcional
Sessão 5: O paradigma funcional (1)
Terça-feira 22 de fevereiro de 2011
Referências
•
Capítulo 1.1.5 SICP: [[
http://mitpress.mit.edu/sicp/full-text/book/book-Z-
H-10.html #% _ sec_1.1.5] [O
 Substituição Modelo de Procedimento para Aplicação]]
•
PLP Capítulo 10: linguagens funcionais
Terça-feira 22 de fevereiro de 2011
Hoje vamos ver
•
História do paradigma funcional
•
Paradigma funcional características puro
•
Modelo de computação baseada na substituição
Terça-feira 22 de fevereiro de 2011
Ordem Applicative ordem normal vs
•
Ordem Applicative (Esquema): os argumentos são avaliados em primeiro lugar, em seguida,
substituído
•
Ordem normal: todas as substituições são feitas até que tem um longo
expressões formados por expressão primitiva; Ele é então avaliado
•
Avaliamos
(F (1 + 2))
 ordem normal
Na programação funcional a ordem normal e ordem aplicativo
sempre retornam o mesmo resultado
Terça-feira 22 de fevereiro de 2011
Ordem Applicative ordem normal vs
•
A ordem não importa se temos de programação funcional pura:
(Definir (zero x) (- x))
(Zero (aleatório 10))
Terça-feira 22 de fevereiro de 2011
Esquema de simulação
(Load "simply.scm")
(Load "order.scm")
(Def (double x) (x + x))
(Def (praça x) (* xx))
(Def (f z) (+ (quadrado (z casal) 1)))
(Applic (F (1 + 2)))
(Normal (F (1 + 2)))
Terça-feira 22 de fevereiro de 2011
Treinamento
•
Dada a função:
•
Avaliação da expressão
(Duplo (3 * 4))
 em ordem e ordem de aplicação
Normal. O que é mais eficiente?
•
Dada a função:
•
Avaliação da expressão
(Switch -1 (1 + 2) (2 + 3) (3 + 4))
 em ordem
aplicação ea ordem normal. O que é mais eficiente?