Cálculo lambda

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Lambda calculus (também escrito como λ-calculus) é um sistema formal em lógica matemática para expressar computação baseada em abstração de função e aplicação usando ligação variável e substituição. É um modelo universal de computação que pode ser usado para simular qualquer máquina de Turing. Foi introduzido pelo matemático Alonzo Church na década de 1930 como parte de sua pesquisa sobre os fundamentos da matemática.

O cálculo lambda consiste em construir termos lambda e realizar operações de redução neles. Na forma mais simples de cálculo lambda, os termos são construídos usando apenas as seguintes regras:

$Não.$ – variável, um caractere ou string representando um parâmetro ou valor matemático/lógico.
$- Sim.$ – abstração, definição de função ( $- Sim.$ é um termo lambda). A variável $- Sim.$ torna-se ligado na expressão.
$(M N)}$ – aplicação, aplicação de uma função $- Sim.$ a um argumento $Não.$ . Ambos $- Sim.$ e $Não.$ são termos lambda.

As operações de redução incluem:

$(lambda x.M[x])rightarrow (lambda y.M[y])}$ – α-conversão, renomeando as variáveis vinculadas na expressão. Usado para evitar colisões de nomes.
$((lambda x.M) E)rightarrow (M[x:=E])}$ – β-redução, substituindo as variáveis vinculadas pela expressão do argumento no corpo da abstração.

Se a indexação De Bruijn for usada, a conversão α não será mais necessária, pois não haverá colisões de nomes. Se a aplicação repetida das etapas de redução eventualmente terminar, então, pelo teorema de Church-Rosser, produzirá uma forma β-normal.

Nomes de variáveis não são necessários se estiver usando uma função lambda universal, como Iota e Jot, que podem criar qualquer comportamento de função chamando-a em várias combinações.

Explicação e aplicações

O cálculo lambda é Turing completo, ou seja, é um modelo universal de computação que pode ser usado para simular qualquer máquina de Turing. Seu homônimo, a letra grega lambda (λ), é usado em expressões lambda e termos lambda para denotar a associação de uma variável em uma função.

O cálculo lambda pode ser não tipado ou digitado. No cálculo lambda digitado, as funções podem ser aplicadas somente se forem capazes de aceitar o "tipo" De dados. Cálculos lambda digitados são mais fracos do que o cálculo lambda não tipado, que é o assunto principal deste artigo, no sentido de que cálculos lambda digitados podem expressar menos do que o cálculo não tipado. Por outro lado, os cálculos lambda digitados permitem que mais coisas sejam provadas. Por exemplo, no cálculo lambda simplesmente digitado, é um teorema que toda estratégia de avaliação termina para cada termo lambda simplesmente digitado, enquanto a avaliação de termos lambda não tipados não precisa terminar. Uma razão pela qual existem muitos cálculos lambda tipados diferentes é o desejo de fazer mais (do que o cálculo não tipado pode fazer) sem desistir de provar teoremas fortes sobre o cálculo.

O cálculo lambda tem aplicações em diversas áreas da matemática, filosofia, linguística e ciência da computação. O cálculo lambda desempenhou um papel importante no desenvolvimento da teoria das linguagens de programação. As linguagens de programação funcional implementam o cálculo lambda. O cálculo lambda também é um tópico de pesquisa atual na teoria das categorias.

História

O cálculo lambda foi introduzido pelo matemático Alonzo Church na década de 1930 como parte de uma investigação sobre os fundamentos da matemática. O sistema original mostrou-se logicamente inconsistente em 1935, quando Stephen Kleene e J. B. Rosser desenvolveram o paradoxo Kleene-Rosser.

Posteriormente, em 1936, Church isolou e publicou apenas a parte relevante para a computação, o que agora é chamado de cálculo lambda não tipado. Em 1940, ele também introduziu um sistema computacionalmente mais fraco, mas logicamente consistente, conhecido como cálculo lambda simplesmente digitado.

Até a década de 1960, quando sua relação com as linguagens de programação foi esclarecida, o cálculo lambda era apenas um formalismo. Graças a Richard Montague e outros linguistas'; aplicações na semântica da linguagem natural, o cálculo lambda começou a desfrutar de um lugar respeitável tanto na linguística quanto na ciência da computação.

Origem do símbolo λ

Há alguma incerteza sobre o motivo do uso da letra grega lambda (λ) por Church como a notação para abstração de função no cálculo lambda, talvez em parte devido a explicações conflitantes do próprio Church. Segundo Cardone e Hindley (2006):

A propósito, por que a Igreja escolheu a notação “λ”? Em [uma carta inédita de 1964 para Harald Dickson] ele afirmou claramente que veio da notação “ $(x)$ ” usado para classificação por Whitehead e Russell, pela primeira vez modificando “ $(x)$ ” para “ $- Sim.$ ” para distinguir função-abstracção de classe-abstracção, e depois mudar “ $Não.$ ” para “λ” para facilidade de impressão.
Esta origem também foi relatada em [Rosser, 1984, p.338]. Por outro lado, em seus últimos anos A Igreja disse a dois inquiridos que a escolha era mais acidental: um símbolo era necessário e λ acabou de ser escolhido.

Dana Scott também abordou esta questão em várias palestras públicas. Scott conta que certa vez fez uma pergunta sobre a origem do símbolo lambda ao ex-aluno e genro de Church, John W. Addison Jr., que então escreveu um cartão postal para seu sogro:

Caro Professor Igreja,
O Russell tinha o operador de iota, o Hilbert tinha o operador de epsilon. Por que escolheu lambda para o seu operador?

De acordo com Scott, toda a resposta de Church consistiu em devolver o cartão postal com a seguinte anotação: "eeny, meeny, miny, moe".

Descrição informal

Motivação

As funções computáveis são um conceito fundamental na ciência da computação e na matemática. O cálculo lambda fornece uma semântica simples para computação que é útil para estudar formalmente as propriedades da computação. O cálculo lambda incorpora duas simplificações que simplificam sua semântica. A primeira simplificação é que o cálculo lambda trata funções "anonimamente;" não lhes dá nomes explícitos. Por exemplo, a função

{displaystyle operatorname {square_sum} (x,y)=x^{2}+y^{2}}

pode ser reescrito em forma anônima como

(x,y)mapsto x^{2}+y^{2}}

(que é lido como "um tupla de $x$ e $Sim.$ é mapeado para ${textstyle x^{2}+y^{2}}$ "). Da mesma forma, a função

(x)=x}

pode ser reescrito de forma anônima como

{displaystyle xmapsto x}

onde a entrada é simplesmente mapeada para si mesma.

A segunda simplificação é que o cálculo lambda só usa funções de uma única entrada. Uma função comum que requer duas entradas, por exemplo, a $- Não.$ função, pode ser retrabalhado em uma função equivalente que aceita uma única entrada, e como retornos de saída outro função, que por sua vez aceita uma única entrada. Por exemplo,

(x,y)mapsto x^{2}+y^{2}}

pode ser retrabalhado em

(ymapsto x^{2}+y^{2})}

Esse método, conhecido como currying, transforma uma função que recebe vários argumentos em uma cadeia de funções, cada uma com um único argumento.

Aplicação de função do $- Não.$ função para os argumentos (5, 2), rendimentos ao mesmo tempo

(x,y)mapsto x^{2}+y^{2}(5,2)}

{textstyle =5^{2}+2^{2}}

Sim.

enquanto a avaliação da versão ao curry requer mais uma etapa

(}xmapsto (ymapsto x^{2}+y^{2}){bigr(5){Bigr)}(2)}

(ymapsto 5^{2}+y^{2})(2)}

// a definição de

Não.

tem sido usado com

Não. 5

na expressão interior. Isto é como a redução β.

{textstyle =5^{2}+2^{2}}

// a definição de

- Sim.

tem sido usado com

Não. 2

. Mais uma vez, semelhante à β-redução.

Sim.

para chegar ao mesmo resultado.

O cálculo lambda

O cálculo lambda consiste em uma linguagem de termos lambda, que são definidos por uma certa sintaxe formal, e um conjunto de regras de transformação para manipular os termos lambda. Essas regras de transformação podem ser vistas como uma teoria equacional ou como uma definição operacional.

Como descrito acima, sem nomes, todas as funções no cálculo lambda são funções anônimas. Eles aceitam apenas uma variável de entrada, então currying é usado para implementar funções de várias variáveis.

Termos lambda

A sintaxe do cálculo lambda define algumas expressões como expressões de cálculo lambda válidas e algumas como inválidas, assim como algumas cadeias de caracteres são programas C válidos e outras não. Uma expressão de cálculo lambda válida é chamada de "termo lambda".

As três regras a seguir fornecem uma definição indutiva que pode ser aplicada para construir todos os termos lambda sintaticamente válidos:

variável $x$ é um termo lambda válido.
se $)$ é um termo lambda, e $x$ é uma variável, então $(lambda x.t)}$ é um termo lambda (chamado um abstração);
se $)$ e $S$ são termos lambda, então $(T)$ $- Sim.$ é um termo lambda (chamado um aplicação).

Nada mais é um termo lambda. Assim, um termo lambda é válido se e somente se puder ser obtido pela aplicação repetida dessas três regras. No entanto, alguns parênteses podem ser omitidos de acordo com certas regras. Por exemplo, os parênteses mais externos geralmente não são escritos. Consulte §Notação, abaixo, para saber quando incluir parênteses

Um abstração $- Sim.$ denota uma função anônima § que leva uma única entrada $x$ e retorna $)$ . Por exemplo, $(x^{2}+2)}$ é uma abstração para a função $(x)=x^{2}+2}$ usando o termo ${displaystyle x^{2}+2}}$ para $)$ . O nome $(x)}$ é supérfluo ao usar a abstração. $(lambda x.t)}$ liga a variável $x$ no termo $)$ . A definição de uma função com uma abstração simplesmente "ajusta" a função, mas não a invoca. Ver §Notação abaixo para uso de parênteses

Um aplicação $Não.$ $Não.$ representa a aplicação de uma função $)$ para uma entrada $S$ , isto é, representa o ato de chamar função $)$ na entrada $S$ para produzir $(s)}$ .

Não há conceito no cálculo lambda de declaração variável. Em uma definição como $(x+y)}$ (i.e. $(x+y)}$ ), em cálculo lambda $Sim.$ é uma variável ainda não definida. A abstração $(x+y)}$ é sinteticamente válido, e representa uma função que adiciona sua entrada ao ainda desconhecido $Sim.$ .

Parênteses podem ser usados e podem ser necessários para eliminar a ambiguidade dos termos. Por exemplo,

${displaystyle lambda x.((lambda x.x)x)}$ que é de forma ${displaystyle lambda x. B.$ — uma abstracção, e
$(lambda x.(lambda x.x)}$ $Não.$ que é de forma $Não.$ $Não.$ — uma aplicação.

Os exemplos 1 e 2 denotam termos diferentes; exceto pelo escopo dos parênteses, eles seriam os mesmos. Mas o exemplo 1 é uma definição de função, enquanto o exemplo 2 é uma aplicação de função. A variável Lambda $x$ é um espaço reservado em ambos os exemplos.

Aqui, exemplo 1 define uma função ${displaystyle lambda x. B.$ , onde $Não.$ o $(lambda x.x)x)$ , uma função anónima $(lambda x.x)}$ , com entrada $Não.$ ; enquanto exemplo 2, $Não.$ $Não.$ , é M aplicado a N, onde $Não.$ é o termo lambda $(lambda x.(lambda x.x)}$ sendo aplicado à entrada $Não.$ que $Não.$ . Ambos os exemplos 1 e 2 avaliariam a função de identidade ${displaystyle lambda x.x}$ .

Funções que operam em funções

No cálculo lambda, as funções são consideradas 'valores de primeira classe', portanto, as funções podem ser usadas como entradas ou retornadas como saídas de outras funções.

Por exemplo, ${displaystyle lambda x.x}$ representa a função de identidade, ${displaystyle xmapsto x}$ e $(lambda x.x)y}$ representa a função de identidade aplicada $- Sim.$ . Mais adiante, $(lambda x.y)}$ representa o função constante $- Sim.$ , a função que sempre retorna $- Sim.$ Não importa a entrada. No cálculo lambda, a aplicação da função é considerada como a esquerda-associativa, de modo que $Não.$ significa $(st)x}$ .

Existem várias noções de "equivalência" e "redução" que permitem que os termos lambda sejam "reduzidos" para "equivalente" termos lambda.

Equivalência alfa

Uma forma básica de equivalência, definida em termos lambda, é a equivalência alfa. Capta a intuição de que a escolha particular de uma variável vinculada, em uma abstração, não importa (geralmente). Por exemplo, ${displaystyle lambda x.x}$ e $- Sim.$ são termos alfa-equivalentes lambda, e ambos representam a mesma função (a função de identidade). Os termos $Não.$ e $- Sim.$ não são alfa-equivalentes, porque eles não estão ligados em uma abstração. Em muitas apresentações, é habitual identificar termos alfa-equivalentes lambda.

As seguintes definições são necessárias para poder definir a β-redução:

Variáveis livres

As variáveis livres de um termo são aquelas variáveis não limitadas por uma abstração. O conjunto de variáveis livres de uma expressão é definido indutivamente:

As variáveis livres $Não.$ são só... $Não.$
O conjunto de variáveis livres $- Sim.$ é o conjunto de variáveis livres de $Não.$ , mas com $Não.$ removido
O conjunto de variáveis livres $Não.$ $Não.$ é a união do conjunto de variáveis livres de $Não.$ e o conjunto de variáveis livres de $Não.$ .

Por exemplo, o termo lambda que representa a identidade ${displaystyle lambda x.x}$ não tem variáveis livres, mas a função $- Sim.$ $Não.$ tem uma única variável livre, $- Sim.$ .

Substituições que evitam a captura

Suponha $Não.$ , $Não.$ e $Não.$ são termos lambda, e $Não.$ e $- Sim.$ são variáveis. A notação $- Sim.$ indica substituição de $Não.$ para $Não.$ em $Não.$ em um captura-evitação Bem. Isso é definido de modo que:

$- Sim.$ ; com $Não.$ substituido por $Não.$ , $Não.$ torna-se $Não.$
$- Sim.$ se $- Sim.$ ; com $Não.$ substituido por $Não.$ , $- Sim.$ (o que não é $Não.$ ) Restos $- Sim.$
$(T)$ $[x:=r]=(t[x:=r])(s[x:=r])}$ ; substituição distribui para ambos os lados de uma aplicação
$(lambda x.t)[x:=r]=lambda x.t}$ ; uma variável vinculada por uma abstração não está sujeita à substituição; substituindo tal variável deixa a abstração inalterada
$(lambda y.t)[x:=r]=lambda y.(t[x:=r])}$ se $- Sim.$ e $- Sim.$ não aparece entre as variáveis livres de $Não.$ ( $- Sim.$ é dito ser "fresco" para $Não.$ ); substituindo uma variável que não está vinculada por uma abstração prossegue no corpo da abstração, desde que a variável abstrata $- Sim.$ é "fresco" para o termo de substituição $Não.$ .

Por exemplo, $(lambda x.x)[y:=y]=lambda x.(x[y:=y])=lambda x.x}$ e $((lambda x.y)x)[x:=y]=((lambda x.y)[x:=y])(x[x:=y])=(lambda x.y)y}$ .

A condição de frescura (requerendo que $- Sim.$ não está nas variáveis livres $Não.$ ) é crucial para garantir que a substituição não altere o significado das funções. Por exemplo, uma substituição que ignora a condição de frescura pode levar a erros: $(lambda x.y)[y:=x]=lambda x.(y[y:=x])=lambda x.x}$ . Esta substituição transforma a função constante $- Sim.$ na identidade ${displaystyle lambda x.x}$ por substituição.

Em geral, o não cumprimento da condição de frescura pode ser remediado pela alfa-renaming primeiro, com uma variável fresca adequada. Por exemplo, mudar de volta para a nossa noção correta de substituição, em $(lambda x.y)[y:=x]}$ a abstração pode ser renomeada com uma nova variável $Não.$ , para obter $(lambda z.y)[y:=x]=lambda z.(y[y:=x])=lambda z.x}$ , e o significado da função é preservado por substituição.

Em uma linguagem de programação funcional onde as funções são cidadãs de primeira classe, esta mudança sistemática nas variáveis para evitar a captura de uma variável livre pode introduzir um erro, ao retornar funções como resultados.

Redução Β

A regra de redução β afirma que uma aplicação do formulário $(lambda x.t)s}$ reduz ao termo $- Sim.$ . A notação $(lambda x.t)sto t[x:=s]}$ é usado para indicar que $(lambda x.t)s}$ β-reduces to $- Sim.$ . Por exemplo, para cada $Não.$ , $(lambda x.x)sto x[x:=s)=s}$ . Isso demonstra que ${displaystyle lambda x.x}$ realmente é a identidade. Da mesma forma, $(lambda x.y)sto y[x:=s)=y}$ , que demonstra que $- Sim.$ é uma função constante.

O cálculo lambda pode ser visto como uma versão idealizada de uma linguagem de programação funcional, como Haskell ou Standard ML. Nesta perspectiva, β-redução corresponde a um passo computacional. Esta etapa pode ser repetida por reduções β adicionais até que não haja mais aplicações para reduzir. No cálculo lambda não digitado, como apresentado aqui, este processo de redução pode não terminar. Por exemplo, considere o termo ${displaystyle Omega =(lambda x.xxx)(lambda x.xxx)}$ . Aqui. $(lambda x.xx)(lambda x.xxx)to (xxx)[x:=lambda x.xx)=(x[x:=lambda x.xxx))(x[x:=lambda x.xxx)))=(lambda x.xxx)}$ . Ou seja, o termo se reduz a si mesmo em uma única redução β, e, portanto, o processo de redução nunca terminará.

Outro aspecto do cálculo lambda não tipado é que ele não distingue entre diferentes tipos de dados. Por exemplo, pode ser desejável escrever uma função que opere apenas com números. No entanto, no cálculo lambda não digitado, não há como impedir que uma função seja aplicada a valores de verdade, strings ou outros objetos não numéricos.

Definição formal

Definição

As expressões lambda são compostas por:

variáveis v₁, v₂,...
os símbolos de abstração λ (lambda) e. (ponto);
parentheses ().

O conjunto de expressões lambda, $Λ$ , pode ser definido indutivamente:

Se x é uma variável, então $x \in Λ.$
Se x é uma variável e $M \in Λ,$ então $(em inglês) x . M) \in Λ.$
Se $M, N \in Λ,$ então $(MN) \in Λ.$

As instâncias da regra 2 são conhecidas como abstrações e as instâncias da regra 3 são conhecidas como aplicativos.

Notação

Para manter a notação das expressões lambda organizada, as seguintes convenções são geralmente aplicadas:

Os parênteses mais externos são descartados: M N em vez de (M N).
As candidaturas são consideradas associadas à esquerda: M N P pode ser escrito em vez de ((M N) P).
Quando todas as variáveis são de letra única, o espaço em aplicações pode ser omitido: MNP em vez de M N P.
O corpo de uma abstração estende-se o mais certo possível: λx.MN significa λx...MN) e não (λx.M) N.
Uma sequência de abstrações é contraída: λx.Sim..zangão..N é abreviado como λXyz.N.

Variáveis livres e ligadas

Diz-se que o operador de abstração, λ, liga sua variável onde quer que ela ocorra no corpo da abstração. As variáveis que se enquadram no escopo de uma abstração são ditas limitadas. Em uma expressão λx.M, a parte λx costuma ser chamada de fichário, como uma dica de que o a variável x está sendo vinculada ao preceder λx a M. Todas as outras variáveis são chamadas de grátis. Por exemplo, na expressão λy.x x y, y é uma variável vinculada e x é uma variável livre. Além disso, uma variável é limitada por sua abstração mais próxima. No exemplo a seguir, a única ocorrência de x na expressão é limitada pelo segundo lambda: λx.y (λx .z x).

O conjunto de variáveis livres de uma expressão lambda, M, é denotado como FV(M) e é definido por recursão no estrutura dos termos, como segue:

FV(x) = {xOnde? x é uma variável.
FV (em inglês)x.M) = FV(M)x}
$FV(MN) = FV(M) Ligação FV(N).$

Uma expressão que não contém variáveis livres é considerada fechada. As expressões lambda fechadas também são conhecidas como combinadores e são equivalentes aos termos da lógica combinatória.

Redução

O significado das expressões lambda é definido pela forma como as expressões podem ser reduzidas.

Existem três tipos de redução:

α-conversão: mudança de variáveis vinculadas;
β-redução: aplicar funções aos seus argumentos;
Redução: que capta uma noção de extensão.

Também falamos das equivalências resultantes: duas expressões são α-equivalentes, se puderem ser convertidas em α na mesma expressão. A equivalência β e a equivalência η são definidas de forma semelhante.

O termo redex, abreviação de expressão redutível, refere-se a subtermos que podem ser reduzidos por uma das regras de redução. Por exemplo, (λx.M) N é um β-redex ao expressar a substituição de N por x em M. A expressão à qual um redex reduz é chamada de reduct; a redução de (λx.M) N é M[x: = N].

Se x não é livre em M, λx.M x também é um η-redex, com redução de M.

Α-conversão

a-conversão, às vezes conhecida como α-renomeação, permite que os nomes das variáveis vinculadas sejam alterados. Por exemplo, a conversão α de λx.x pode resultar em λy.y. Os termos que diferem apenas pela conversão α são chamados equivalentes a α. Freqüentemente, em usos de cálculo lambda, os termos α-equivalentes são considerados equivalentes.

As regras precisas para a conversão α não são completamente triviais. Primeiro, ao converter uma abstração em α, as únicas ocorrências variáveis que são renomeadas são aquelas que estão vinculadas à mesma abstração. Por exemplo, uma conversão α de λx.λx.x pode resultar em λy.λ x.x, mas pode não resultar em λy.λx.y. Este último tem um significado diferente do original. Isso é análogo à noção de programação de sombreamento variável.

Em segundo lugar, a conversão α não é possível se resultar em uma variável sendo capturada por uma abstração diferente. Por exemplo, se substituirmos x por y em λx.λy.x, obtemos λy.λy.y, que não é a mesma coisa.

Em linguagens de programação com escopo estático, a conversão α pode ser usada para simplificar a resolução de nomes, garantindo que nenhum nome de variável mascare um nome em um escopo recipiente (consulte α-renomeação para tornar a resolução de nomes trivial).

Na notação de índice De Bruijn, quaisquer dois termos equivalentes a α são sintaticamente idênticos.

Substituição

Substituição, escrita M[x:= N], é o processo de substituição de todas as ocorrências livres da variável x na expressão M com a expressão N. A substituição nos termos do cálculo lambda é definida pela recursão na estrutura dos termos, como segue (nota: x e y são apenas variáveis enquanto M e N são qualquer expressão lambda):

xNão.x? NNão. N

Sim.Não.x? NNão. Sim., se x ≠ Sim.

(M₁ M₂)x? NNão. M₁Não.x? N] M₂Não.x? N]

(em inglês)x.M)x? NO quê?x.M

(em inglês)Sim..M)x? NO quê?Sim....MNão.x? N]), se x ≠ Sim. e Sim. FV(N) Ver acima para o FV

Para substituir em uma abstração, às vezes é necessário converter a expressão em α. Por exemplo, não é correto para (λx.y)[y:= x] resultar em λx.x, porque o x substituído deveria ser livre, mas acabou sendo vinculado. A substituição correta neste caso é λz.x, até a equivalência α. A substituição é definida exclusivamente até a equivalência α.

Redução Β

A redução de β captura a ideia de aplicação de função. A β-redução é definida em termos de substituição: a β-redução de (λx.M) N é M[x:= N].

Por exemplo, assumindo alguma codificação de 2, 7, ×, temos a seguinte redução β: (λn.n × 2) 7 → 7 × 2.

β-redução pode ser vista como sendo o mesmo que o conceito de redutibilidade local na dedução natural, através do isomorfismo de Curry-Howard.

Redução Η

η-redução (eta redução) expressa a ideia de extensionalidade, que neste contexto é que duas funções são iguais se e somente se elas derem o mesmo resultado para todos os argumentos. η-reduction converte entre λx.f x e f sempre que x o fizer não aparece livre em f.

η-redução pode ser visto como o mesmo que o conceito de completude local na dedução natural, através do isomorfismo de Curry-Howard.

Formas normais e confluência

Para o cálculo lambda não digitado, a redução β como uma regra de reescrita não é nem fortemente normalizadora nem fracamente normalizadora.

No entanto, pode ser demonstrado que a redução β é confluente ao trabalhar até a conversão α (ou seja, consideramos duas formas normais iguais se for possível converter α uma na outra).

Portanto, tanto os termos de normalização forte quanto os termos de normalização fraca têm uma forma normal única. Para termos de normalização forte, qualquer estratégia de redução é garantida para produzir a forma normal, enquanto para termos de normalização fraca, algumas estratégias de redução podem falhar em encontrá-la.

Codificação de tipos de dados

O cálculo lambda básico pode ser usado para modelar booleanos, aritmética, estruturas de dados e recursão, conforme ilustrado nas subseções a seguir.

Aritmética em cálculo lambda

Existem várias formas possíveis de definir os números naturais no cálculo lambda, mas de longe as mais comuns são os numerais da Igreja, que podem ser definidos da seguinte forma:

0:= λf.x.x

1: = λf.x.f x

2:= λf.x.f (f x)

3:= λf.x.f (f (f x)

e assim por diante. Ou usando a sintaxe alternativa apresentada acima em Notação:

0:= λfx.x

1: = λfx.f x

2:= λfx.f (f x)

3:= λfx.f (f (f x)

Um numeral Church é uma função de ordem superior — ele usa uma função de argumento único f e retorna outra função de argumento único. O numeral da Igreja n é uma função que assume uma função f como argumento e retorna a n-ésima composição de f, ou seja, a função f composta consigo mesma n vezes. Isso é denotado f⁽ⁿ⁾ e é de fato o n-ésima potência de f (considerado como um operador); f⁽⁰⁾ é definido para ser a função de identidade. Essas composições repetidas (de uma única função f) obedecem às leis dos expoentes, razão pela qual esses numerais podem ser usados para aritmética. (No cálculo lambda original de Church, o parâmetro formal de uma expressão lambda deveria ocorrer pelo menos uma vez no corpo da função, o que tornava a definição acima de 0 impossível.)

Uma maneira de pensar sobre o numeral da Igreja n, que geralmente é útil ao analisar programas, é como uma instrução 'repita n vezes'. Por exemplo, usando as funções PAIR e NIL definidas abaixo, pode-se definir uma função que constrói uma lista (vinculada) de n elementos todos iguais a x repetindo 'preceder outro elemento x' n vezes, começando de uma lista vazia. O termo lambda é

λn.x.n (PAIR) x) NIL

Variando o que está sendo repetido, e variando a que argumento aquela função que está sendo repetida é aplicada, muitos efeitos diferentes podem ser alcançados.

Podemos definir uma função sucessora, que recebe um numeral Church n e retorna n + 1 adicionando outro aplicativo de f, onde '(mf)x' significa a função 'f' é aplicado 'm' vezes em 'x':

SUCC:= λn.f.x.f (n f x)

Porque a m-ésima composição de f composta com a n-ésima composição de f fornece o m+n-ésima composição de f, a adição pode ser definida da seguinte forma:

PLUS:= λm.n.f.x.m f (n f x)

PLUS pode ser pensado como uma função que recebe dois números naturais como argumentos e retorna um número natural; pode-se verificar que

PLUS 2 3

são expressões lambda β-equivalentes. Como adicionar m a um número n pode ser feito adicionando 1 m vezes, uma definição alternativa é:

PLUS:= λm.n.m SUCC n

Da mesma forma, a multiplicação pode ser definida como

- Sim.m.n.f.m (n f)

Alternativamente

- Sim.m.n.m (PLUS) n) 0

já que multiplicar m e n é o mesmo que repetir a função adicionar n m vezes e, em seguida, aplicá-la a zero. A exponenciação tem uma representação bastante simples nos numerais da Igreja, ou seja,

POW:= λb).e.e b)

A função predecessora definida por PRED n = n − 1 para um inteiro positivo n e PRED 0 = 0 é consideravelmente mais difícil. A fórmula

PRED:= λn.f.x.n (em inglês)g.h.h (g f)u.x)u.u)

pode ser validado mostrando indutivamente que se T denota (λg.λh.h (g f)), então T⁽ⁿ⁾(λu.x) = (λh.h(f⁽ⁿ⁻¹⁾(x))) para n > 0. Duas outras definições de PRED são dadas abaixo, uma usando condicionais e a outra usando pares. Com a função predecessora, a subtração é direta. Definindo

ASSINAR:m.n.n PREÇO m,

SUB m n produz m − n quando m > n e 0 caso contrário.

Lógica e predicados

Por convenção, as duas definições a seguir (conhecidas como booleanos da Igreja) são usadas para os valores booleanos TRUE e FALSE:

TRUE:= λx.Sim..x

FALSE:= λx.Sim..Sim.

Então, com esses dois termos lambda, podemos definir alguns operadores lógicos (essas são apenas possíveis formulações; outras expressões são igualmente corretas):

E...p.q.p q p

OU:p.q.p p q

Não.p.p VERDADEIRO

IFTHENELSE:= λp.um.b).p um b)

Agora podemos calcular algumas funções lógicas, por exemplo:

E VERDADE

≡ (em inglês)p.q.p q p) TRUE FALSE →_β VERDADEIRO VERDADEIRO

≡ (em inglês)x.Sim..x) TRUE DE FALSE →_β FALSO

e vemos que AND TRUE FALSE é equivalente a FALSE.

Um predicado é uma função que retorna um valor booleano. O predicado mais fundamental é ISZERO, que retorna TRUE se seu argumento for o numeral da Igreja 0 e FALSE se o argumento for qualquer outro numeral da Igreja:

:n.n (em inglês)x.FALSE) TRUE

O seguinte predicado testa se o primeiro argumento é menor ou igual ao segundo:

LEQ:= λm.n.ISZERO (SUB) m n),

e como m = n, se LEQ m n e LEQ n m, é simples construir um predicado para a igualdade numérica.

A disponibilidade de predicados e a definição acima de TRUE e FALSE tornam conveniente escrever "if- então-senão" expressões em cálculo lambda. Por exemplo, a função predecessora pode ser definida como:

PRED:= λn.n (em inglês)g.k.ISZERO (em inglês)g 1) k (PLUS)g k) 1)v0

que pode ser verificado mostrando indutivamente que n (λg.λk.ISZERO (g 1) k (MAIS (g k) 1)) (λv.0) é a função adicionar n − 1 para n > 0.

Pares

Um par (2 tuplas) pode ser definido em termos de TRUE e FALSE, usando a codificação Church para pares. Por exemplo, PAIR encapsula o par (x,y), FIRST retorna o primeiro elemento do par e SECOND retorna o segundo.

- Sim.x.Sim..f.f x Sim.

Imediatamente.p.p TRÊS

SEGUNDO:= λp.p FALSO

Não.x. TRÊS

NULL:= λp.p (em inglês)x.Sim..FALSE)

Uma lista encadeada pode ser definida como NIL para a lista vazia ou o PAR de um elemento e uma lista menor. O predicado NULL testa o valor NIL. (Como alternativa, com NIL:= FALSE, a construção l (λh. λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) evita a necessidade de um teste NULL explícito).

Como exemplo do uso de pares, a função shift-and-increment que mapeia (m, n) para (n, n + 1) pode ser definido como

δ:= λx. PAIR (SECOND x(SUCC) x)

o que nos permite dar talvez a versão mais transparente da função predecessora:

PRED:= λn. Primeiro...n Φ (PAIR 0).

Técnicas de programação adicionais

Existe um conjunto considerável de idiomas de programação para cálculo lambda. Muitos deles foram originalmente desenvolvidos no contexto do uso do cálculo lambda como base para a semântica da linguagem de programação, usando efetivamente o cálculo lambda como uma linguagem de programação de baixo nível. Como várias linguagens de programação incluem o cálculo lambda (ou algo muito semelhante) como um fragmento, essas técnicas também são usadas na programação prática, mas podem ser percebidas como obscuras ou estranhas.

Constantes nomeadas

No cálculo lambda, uma biblioteca assumiria a forma de uma coleção de funções previamente definidas, que como termos lambda são apenas constantes particulares. O cálculo lambda puro não tem um conceito de constantes nomeadas, uma vez que todos os termos lambda atômicos são variáveis, mas pode-se emular ter constantes nomeadas deixando de lado uma variável como o nome da constante, usando abstração para ligar essa variável no corpo principal e aplique essa abstração à definição pretendida. Portanto, usar f para significar N (algum termo lambda explícito) em M (outro termo lambda, o "programa principal"), pode-se dizer

(em inglês)f.M) N

Os autores geralmente introduzem açúcar sintático, como let, para permitir a escrita acima na ordem mais intuitiva

Deixa-me. f = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =N em M

Ao encadear tais definições, pode-se escrever um "programa" como zero ou mais definições de função, seguidas por um termo lambda usando essas funções que constituem o corpo principal do programa.

Uma restrição notável deste let é que o nome f não deve ser definido em N, para N estar fora do escopo da ligação de abstração f; isso significa que uma definição de função recursiva não pode ser usada como N com let. A construção letrec permitiria escrever definições de funções recursivas.

Recursão e pontos fixos

Recursão é a definição de uma função usando a própria função. Uma definição contendo-se dentro de si, por valor, faz com que todo o valor seja de tamanho infinito. Outras notações que suportam recursão nativamente superam isso referindo-se à definição da função por nome. O cálculo lambda não pode expressar isso: todas as funções são anônimas no cálculo lambda, então não podemos nos referir pelo nome a um valor que ainda não foi definido, dentro do termo lambda que define esse mesmo valor. No entanto, uma expressão lambda pode receber a si mesma como seu próprio argumento, por exemplo em (λx.x x) E. Aqui E deve ser uma abstração, aplicando seu parâmetro a um valor para expressar a recursão.

Considere a função fatorial F(n) definida recursivamente por

F(n) = 1, se n = 0; n × F(n - 1).

Na expressão lambda que deve representar esta função, um parâmetro (normalmente o primeiro) será assumido para receber a própria expressão lambda como seu valor, de modo que chamá-la – aplicá-la a um argumento – equivalerá a recursão. Portanto, para obter recursão, o argumento pretendido como auto-referenciado (chamado r aqui) deve sempre ser passado para si mesmo dentro do corpo da função, em um ponto de chamada:

G:= λR.nSe n = 0; n ×R R (n-1))

com R R x = F x = G R x para segurar, então R = G e

F:= G G = (λx.x x) G

A autoaplicação realiza a replicação aqui, passando a expressão lambda da função para a próxima invocação como um valor de argumento, tornando-a disponível para ser referenciada e chamada lá.

Isso resolve, mas requer reescrever cada chamada recursiva como autoaplicação. Gostaríamos de ter uma solução genérica, sem a necessidade de reescrever:

G:= λR.nSe n = 0; n ×R (n-1))

com R x = F x = G R x para segurar, então R = G R =: FIX G e

F FIX G Onde? FIX g:R Onde? R = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = g R) = g (FIX) g)

assim FIX G = G (FIX G) = (λnSe n = 0; n × (FIX G) (n-1))

Dado um termo lambda com o primeiro argumento representando a chamada recursiva (por exemplo, G aqui), o combinador de ponto fixo FIX retornará uma expressão lambda autorreplicante representando a função recursiva (aqui, F). A função não precisa ser explicitamente passada para si mesma em nenhum momento, pois a auto-replicação é previamente arranjada, quando ela é criada, para ser feita toda vez que for chamada. Assim, a expressão lambda original (FIX G) é recriada dentro de si mesma, no call-point, obtendo auto-referência.

Na verdade, existem muitas definições possíveis para este operador FIX, sendo a mais simples delas:

Y:gNão.x.g (x x)x.g (x x)

No cálculo lambda, Y g é um ponto fixo de g, à medida que se expande para:

Y g

(em inglês)hNão.x.h (x x)x.h (x x) g

(em inglês)x.g (x x)x.g (x x)

g (em inglês)x.g (x x)x.g (x x)

g (Y g)

Agora, para realizar nossa chamada recursiva para a função fatorial, simplesmente chamaríamos (Y G) n, onde n é o número do qual estamos calculando o fatorial. Dado n = 4, por exemplo, isso dá:

(Y G) 4

G (Y G) 4

(em inglês)R.nSe n = 0; n ×R (n-1)) (Y G) 4

(em inglês)nSe n = 0; n (Y G) (n-1)) 4

1, se 4 = 0; mais 4 × ((Y G) (4−1)

4 × (G)Y G) (4−1)

4 × ((λ)nSe n = 0; n (Y G) (n-1))) (4−1))

4 × (1, se 3 = 0; mais 3 × ((Y G) (3−1))

4 × (3 × (G)Y G) (3−1))

4 × (3 × ((λ)nSe n = 0; n (Y G) (n-1))) ((3−1)))

4 × (3 × (1, se 2 = 0; mais 2 × ((Y G) (2−1)))

4 × (3 × (2 × (G)Y G) (2−1)))

4 × (3 × (2 ×)nSe n = 0; n (Y G) (n-1))) (2−1)))

4 × (3 × (2 × (1, se 1 = 0; mais 1 × ((Y G) (1−1))))

4 × (3 × (2 × (1 × (G)Y G) (1−1))))

4 × (3 × (2 × (1 ×)nSe n = 0; n (Y G) (n-1))) ((1−1))))

4 × (3 × (2 × (1 ×, se 0 = 0; mais 0 × ((Y G) (0−1)))))

4 × (3 × (1 × (1)))

24.

Toda função definida recursivamente pode ser vista como um ponto fixo de alguma função definida adequadamente fechando a chamada recursiva com um argumento extra e, portanto, usando Y, toda função definida recursivamente pode ser expressa como uma expressão lambda. Em particular, agora podemos definir claramente o predicado de subtração, multiplicação e comparação de números naturais recursivamente.

Termos padrão

Alguns termos têm nomes comumente aceitos:

Eu...:x.x

S:x.Sim..zangão..x zangão. (Sim. zangão.)

KK:x.Sim..x

B:x.Sim..zangão..x (Sim. zangão.)

C:x.Sim..zangão..x zangão. Sim.

W:x.Sim..x Sim. Sim.

ω ou ? ou U:x.x x

Ω? ω ω

I é a função identidade. SK e BCKW formam sistemas de cálculo combinatório completos que podem expressar qualquer termo lambda - ver a próxima seção. Ω é UU, o menor termo que não tem forma normal. YI é outro desses termos. Y é padrão e definido acima e também pode ser definido como Y=BU(CBU), de modo que Yg=g(Yg). TRUE e FALSE definidos acima são geralmente abreviados como T e F.

Eliminação da abstração

Se N é um termo lambda sem abstração, mas possivelmente contendo constantes nomeadas (combinadores), então existe um termo lambda T(x,N) que é equivalente a λx.N mas carece de abstração (exceto como parte das constantes nomeadas, se estas forem consideradas não atômicas). Isso também pode ser visto como variáveis anônimas, como T(x,N) remove todas as ocorrências de x de N, enquanto ainda permite que valores de argumento sejam substituídos nas posições onde N contém um x. A função de conversão T pode ser definida por:

T(x, x: Eu...

T(x, N: KK N se x não é livre em N.

T(x, M N: S T(x, M) T(x, N)

Em qualquer um dos casos, um termo na forma T(x,N) P pode reduzir fazendo com que o combinador inicial I, K ou S pegue o argumento P , assim como β-redução de (λx.N) P faria. I retorna esse argumento. K descarta o argumento, assim como (λx.N) faria se x não tivesse ocorrência livre em N. S passa o argumento para ambos os subtermos do aplicativo e, em seguida, aplica o resultado do primeiro ao resultado do segundo.

Os combinadores B e C são semelhantes a S, mas passam o argumento para apenas um subtermo de uma aplicação ( B para o subtermo "argumento" e C para o subtermo "função"), salvando assim um K subsequente se não houver ocorrência de x em um subtermo. Em comparação com B e C, o combinador S na verdade combina duas funcionalidades: reorganizar argumentos e duplicar um argumento para que possa ser usado em dois lugares. O combinador W faz apenas o último, produzindo o sistema B, C, K, W como uma alternativa ao cálculo do combinador SKI.

Cálculo lambda digitado

A cálculo lambda tipo é um formalismo digitado que usa o lambda-symbol ( $- Sim.$ ) denotar a abstração da função anónima. Neste contexto, os tipos geralmente são objetos de natureza sintática que são atribuídos aos termos lambda; a natureza exata de um tipo depende do cálculo considerado (ver Tipos de cálculo lambda tipo). De um certo ponto de vista, cálculos lambda tipo pode ser visto como refinamentos do cálculo lambda não digitado, mas de outro ponto de vista, eles também podem ser considerados a teoria mais fundamental e cálculo de lambda não digitado um caso especial com apenas um tipo.

Cálculos lambda digitados são linguagens de programação fundamentais e são a base de linguagens de programação funcionais tipadas como ML e Haskell e, mais indiretamente, linguagens de programação imperativas digitadas. Os cálculos lambda digitados desempenham um papel importante no projeto de sistemas de tipos para linguagens de programação; aqui a tipabilidade geralmente captura as propriedades desejáveis do programa, por ex. o programa não causará uma violação de acesso à memória.

Os cálculos lambda digitados estão intimamente relacionados à lógica matemática e à teoria da prova por meio do isomorfismo de Curry-Howard e podem ser considerados como a linguagem interna de classes de categorias, por exemplo, o cálculo lambda simplesmente digitado é a linguagem das categorias cartesianas fechadas (CCCs).

Estratégias de redução

Se um termo está normalizando ou não, e quanto trabalho precisa ser feito para normalizá-lo, se estiver, depende em grande parte da estratégia de redução usada. As estratégias comuns de redução do cálculo lambda incluem:

Ordem normal: O redx mais esquerdo, mais externo é sempre reduzido em primeiro lugar. Ou seja, sempre que possível os argumentos são substituídos no corpo de uma abstração antes que os argumentos sejam reduzidos.
Pedido aplicado: O redex mais esquerdista, mais interno é sempre reduzido primeiro. Intuitivamente isso significa que os argumentos de uma função são sempre reduzidos antes da própria função. A ordem aplicativa sempre tenta aplicar funções a formas normais, mesmo quando isso não é possível.
Total β-reduções: Qualquer redex pode ser reduzido a qualquer momento. Isso significa, essencialmente, a falta de qualquer estratégia de redução em particular, no que diz respeito à redutibilidade, "todas as apostas estão desligadas".

Estratégias de redução fraca não reduzem sob abstrações lambda:

Chamada por valor: Um redex é reduzido apenas quando seu lado direito tem reduzido a um valor (variável ou abstração). Apenas os redexes mais externos são reduzidos.
Chamada por nome: Como ordem normal, mas nenhuma redução é realizada dentro de abstrações. Por exemplo, λxNão.Sim..Sim.)x está em forma normal de acordo com esta estratégia, embora contenha o redex (em inglês)Sim..Sim.)x.

Estratégias com compartilhamento reduzem cálculos que são "o mesmo" em paralelo:

Redução ótima: Como ordem normal, mas as computações que têm o mesmo rótulo são reduzidas simultaneamente.
Chamada por necessidade: Como chamada por nome (daí fraco), mas aplicações de função que duplicariam termos em vez nomeiam o argumento, que é então reduzido apenas "quando é necessário".

Computabilidade

Não há algoritmo que tome como entrada quaisquer duas expressões lambda e imprima TRUE ou FALSE dependendo se uma expressão reduz para o outro. Mais precisamente, nenhuma função computável pode decidir a questão. Este foi historicamente o primeiro problema para o qual a indecidibilidade pôde ser provada. Como de costume para tal prova, computável significa computável por qualquer modelo de computação que seja Turing completo. De fato, a própria computabilidade pode ser definida por meio do cálculo lambda: uma função F: N → N de números naturais é uma função computável se e somente se existe uma expressão lambda f tal que para cada par de x, y em N, F(x)=y se e somente se f x =_β y, onde x e y são os numerais da Igreja correspondentes a x e y, respectivamente e =_β significando equivalência com β-redução. Veja a tese de Church-Turing para outras abordagens para definir computabilidade e sua equivalência.

A prova de incomputabilidade de Church primeiro reduz o problema para determinar se uma determinada expressão lambda tem uma forma normal. Em seguida, ele assume que esse predicado é computável e, portanto, pode ser expresso em cálculo lambda. Com base no trabalho anterior de Kleene e construindo uma numeração de Gödel para expressões lambda, ele constrói uma expressão lambda e que segue de perto a prova de Gödel' s primeiro teorema da incompletude. Se e for aplicado ao seu próprio número de Gödel, ocorrerá uma contradição.

Complexidade

A noção de complexidade computacional para o cálculo lambda é um pouco complicada, porque o custo de uma redução β pode variar dependendo de como ela é implementada. Para ser preciso, deve-se encontrar de alguma forma a localização de todas as ocorrências da variável vinculada V na expressão E, implicando um custo de tempo, ou deve-se acompanhar as localizações de variáveis livres de alguma forma, implicando um custo de espaço. Uma busca ingênua pelos locais de V em E é O (n) no comprimento n de E. As strings do diretor foram uma abordagem inicial que trocou esse custo de tempo por um uso de espaço quadrático. De forma mais geral, isso levou ao estudo de sistemas que usam substituição explícita.

Em 2014, foi demonstrado que o número de etapas de redução β tomadas pela redução de ordem normal para reduzir um termo é um modelo de custo de tempo razoável, ou seja, a redução pode ser simulada em um Turing máquina em tempo polinomial proporcional ao número de passos. Este foi um problema em aberto de longa data, devido à explosão de tamanho, a existência de termos lambda que crescem exponencialmente em tamanho para cada β-redução. O resultado contorna isso trabalhando com uma representação compartilhada compacta. O resultado deixa claro que a quantidade de espaço necessária para avaliar um termo lambda não é proporcional ao tamanho do termo durante a redução. Não se sabe atualmente qual seria uma boa medida da complexidade do espaço.

Um modelo irracional não significa necessariamente ineficiente. A redução ótima reduz todos os cálculos com o mesmo rótulo em uma etapa, evitando trabalho duplicado, mas o número de etapas de redução β paralelas para reduzir um determinado termo à forma normal é aproximadamente linear no tamanho do termo. Isso é muito pequeno para ser uma medida de custo razoável, pois qualquer máquina de Turing pode ser codificada no cálculo lambda em tamanho linearmente proporcional ao tamanho da máquina de Turing. O verdadeiro custo de reduzir os termos lambda não é devido à β-redução per se, mas sim ao tratamento da duplicação de redexes durante a β-redução. Não se sabe se as implementações de redução ótima são razoáveis quando medidas em relação a um modelo de custo razoável, como o número de etapas mais à esquerda para a forma normal, mas foi demonstrado para fragmentos do cálculo lambda que o algoritmo de redução ideal é eficiente e tem no máximo uma sobrecarga quadrática em comparação com o mais à esquerda. Além disso, a implementação do protótipo BOHM de redução ideal superou Caml Light e Haskell em termos lambda puros.

Cálculo lambda e linguagens de programação

Como apontado pelo artigo de Peter Landin de 1965 "A Correspondence between ALGOL 60 and Church's Lambda-notation", as linguagens de programação procedural sequencial podem ser entendidas em termos do cálculo lambda, que fornece os mecanismos básicos para abstração de procedimento e aplicação de procedimento (subprograma).

Funções anônimas

Por exemplo, em Python, o "quadrado" função pode ser expressa como uma expressão lambda da seguinte forma:

(Lambda x: xNão.2)

O exemplo acima é uma expressão que resulta em uma função de primeira classe. O símbolo lambda cria uma função anônima, dada uma lista de nomes de parâmetros, x – apenas um único argumento neste caso, e uma expressão que é avaliada como o corpo do função, x**2. As funções anônimas às vezes são chamadas de expressões lambda.

Por exemplo, Pascal e muitas outras linguagens imperativas há muito suportam a passagem de subprogramas como argumentos para outros subprogramas através do mecanismo de ponteiros de função. No entanto, os ponteiros de função não são uma condição suficiente para que as funções sejam tipos de dados de primeira classe, porque uma função é um tipo de dados de primeira classe se e somente se novas instâncias da função puderem ser criadas em tempo de execução. E esta criação de funções em tempo de execução é suportada em Smalltalk, JavaScript e Wolfram Language, e mais recentemente em Scala, Eiffel ("agentes"), C# ("delegados") e C+ +11, entre outros.

Paralelismo e simultaneidade

A propriedade de Church-Rosser do cálculo lambda significa que a avaliação (redução β) pode ser realizada em qualquer ordem, mesmo em paralelo. Isso significa que várias estratégias de avaliação não determinísticas são relevantes. No entanto, o cálculo lambda não oferece nenhuma construção explícita para paralelismo. Pode-se adicionar construções como Futuros ao cálculo lambda. Outros cálculos de processos foram desenvolvidos para descrever a comunicação e a simultaneidade.

Semântica

O fato de os termos do cálculo lambda atuarem como funções em outros termos do cálculo lambda, e até neles mesmos, levou a questões sobre a semântica do cálculo lambda. Poderia um significado sensato ser atribuído aos termos do cálculo lambda? A semântica natural era encontrar um conjunto D isomórfico ao espaço de funções D → D, de funções sobre ele mesmo. No entanto, nenhum D não trivial pode existir, por restrições de cardinalidade porque o conjunto de todas as funções de D a D tem cardinalidade maior que D, a menos que D seja um conjunto singleton.

Na década de 1970, Dana Scott mostrou que, se apenas funções contínuas fossem consideradas, um conjunto ou domínio D com a propriedade necessária poderia ser encontrado, fornecendo assim um modelo para o cálculo lambda.

Este trabalho também formou a base para a semântica denotacional das linguagens de programação.

Variações e extensões

Estas extensões estão no cubo lambda:

Cálculo lambda digitado – Cálculo Lambda com variáveis digitadas (e funções)
Sistema F – Um cálculo tipo lambda com variáveis tipo
Cálculo de construções – Um cálculo tipo lambda com tipos como valores de primeira classe

Esses sistemas formais são extensões do cálculo lambda que não estão no cubo lambda:

cálculo de lambda binário – Uma versão de cálculo de lambda com I/O binário, uma codificação binária de termos e uma máquina universal designada.
Cálculo Lambda-mu – Uma extensão do cálculo lambda para tratar a lógica clássica

Esses sistemas formais são variações do cálculo lambda:

Cálculo Kappa – Um análogo de primeira ordem de cálculo lambda

Esses sistemas formais estão relacionados ao cálculo lambda:

Lógica combinada – Uma notação para lógica matemática sem variáveis
cálculo combinador SKI – Um sistema computacional baseado no S, KK e Eu... combinadores, equivalentes ao cálculo lambda, mas redutíveis sem substituições variáveis

Contenido relacionado

Más resultados...