Cálculo Lambda é um sistema formal em lógica matemática para expressar cálculos baseados em abstração e aplicar funções usando vinculação e substituição de variáveis. Este é um modelo universal que pode ser aplicado ao projeto de qualquer máquina de Turing. O cálculo lambda foi introduzido pela primeira vez por Church, um matemático famoso, na década de 1930.
O sistema consiste em construir membros lambda e realizar operações de redução neles.
Explicações e Aplicações
A letra grega lambda (λ) é usada em expressões lambda e termos lambda para denotar a ligação de uma variável em uma função.
Cálculo Lambda pode ser digitado ou não digitado. Na primeira variante, as funções só podem ser usadas se forem capazes de receber dados desse tipo. Os cálculos lambda digitados são mais fracos, podem expressar um valor menor. Mas, por outro lado, eles permitem que você prove mais coisas.
Uma razão pela qual existem tantos tipos diferentes é o desejo dos cientistas de fazer mais sem perder a oportunidade de provar teoremas fortes do cálculo lambda.
O sistema tem aplicações em diversas áreas da matemática, filosofia, linguística e ciência da computação. Em primeiro lugar, o cálculo lambda é um cálculo que desempenhou um papel importante no desenvolvimento da teoria das linguagens de programação. São os estilos de criação funcional que os sistemas implementam. Eles também são um tema quente de pesquisa na teoria dessas categorias.
Para manequins
O cálculo lambda foi introduzido pelo matemático Alonzo Church na década de 1930 como parte de sua pesquisa sobre os fundamentos da ciência. O sistema original mostrou-se logicamente inconsistente em 1935, quando Stephen Kleen e J. B. Rosser desenvolveram o paradoxo de Kleene-Rosser.
Mais tarde, em 1936, Church destacou e publicou apenas a parte que é relevante para os cálculos, o que agora é chamado de cálculo lambda não tipado. Em 1940, ele também introduziu uma teoria mais fraca, mas logicamente consistente, conhecida como sistema de tipos primos. Em seu trabalho, ele explica toda a teoria em termos simples, então pode-se dizer que Church publicou o cálculo lambda para manequins.
Até a década de 1960, quando sua relação com as linguagens de programação ficou clara, λ era apenas um formalismo. Graças às aplicações de Richard Montagu e outros linguistas na semântica da linguagem natural, o cálculo ocupou um lugar de destaque tanto na linguística quanto na ciência da computação.
Origem do símbolo
Lambda não significa uma palavra ou acrônimo, vem de uma referência na Matemática Principal de Russell seguida de duas mudanças tipográficas. Exemplo de notação: para uma função f com f (y)=2y + 1 é 2ŷ + 1. E aqui usamos um acento circunflexo (“hat”) sobre y para rotular a variável de entrada.
A igreja originalmente pretendia usar símbolos semelhantes, mas os tipógrafos não conseguiam colocar o símbolo do "chapéu" acima das letras. Então, em vez disso, eles o imprimiram originalmente como "/\y.2y+1". No próximo episódio de edição, os digitadores substituíram "/ \" por um caractere visualmente semelhante.
Introdução ao cálculo lambda
O sistema consiste em uma linguagem de termos, que são escolhidos por uma certa sintaxe formal, e um conjunto de regras de transformação que permitem manipulá-los. O último ponto pode ser considerado como uma teoria equacional ou como uma definição operacional.
Todas as funções no cálculo lambda são anônimas, o que significa que não têm nomes. Eles recebem apenas uma variável de entrada, e currying é usado para implementar gráficos com múltiplas variáveis.
Termos Lambda
A sintaxe do cálculo define algumas expressões como válidas e outras como inválidas. Assim como diferentes strings de caracteres são programas C válidos e alguns não são. A expressão real do cálculo lambda é chamada de "termo lambda".
As três regras a seguir fornecem uma definição indutiva que pode seraplicam-se à construção de todos os conceitos sintaticamente válidos:
A própria variável x é um termo lambda válido:
- se T é LT e x não é constante, então (lambda xt) é chamado de abstração.
- se T e s são conceitos, então (TS) é chamado de aplicação.
Nada mais é um termo lambda. Assim, um conceito é válido se e somente se pode ser obtido pela aplicação repetida dessas três regras. No entanto, alguns colchetes podem ser omitidos de acordo com outros critérios.
Definição
As expressões lambda consistem em:
- variáveis v 1, v 2, …, v n, …
- símbolos de abstração 'λ' e ponto '.'
- colchetes ().
O conjunto Λ pode ser definido indutivamente:
- Se x é uma variável, então x ∈ Λ;
- x não é constante e M ∈ Λ, então (λx. M) ∈ Λ;
- M, N ∈ Λ, então (MN) ∈ Λ.
Designação
Para manter a notação das expressões lambda organizada, as seguintes convenções são comumente usadas:
- Parênteses externos omitidos: MN em vez de (MN).
- Assume-se que as aplicações permanecem associativas: pode-se escrever MNP em vez de ((MN) P).
- O corpo da abstração se estende mais à direita: λx. MN significa λx. (MN), não (λx. M) N.
- A sequência de abstrações é reduzida: λx.λy.λz. N pode ser λxyz. N.
Variáveis livres e vinculadas
O operador λ conecta sua não constante onde quer que esteja no corpo da abstração. As variáveis que se enquadram no escopo são chamadas de vinculadas. Na expressão λ x. M, a parte λ x é muitas vezes referida como um aglutinante. Como se insinuando que as variáveis se tornam um grupo com a adição de X x a M. Todas as outras instáveis são chamadas de livres.
Por exemplo, na expressão λ y. x x y, y - ligado não permanente, e x - livre. E também vale a pena notar que a variável é agrupada por sua abstração "mais próxima". No exemplo a seguir, a solução de cálculo lambda é representada por uma única ocorrência de x, que está relacionada ao segundo termo:
λ x. y (λ x. z x)
O conjunto de variáveis livres M é denotado como FV (M) e é definido por recursão sobre a estrutura de termos como segue:
- FV (x)={x}, onde x é uma variável.
- FV (λx. M)=FV (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
Uma fórmula que não contém variáveis livres é chamada de fechada. Expressões lambda fechadas também são conhecidas como combinadores e são equivalentes a termos em lógica combinatória.
Abreviatura
O significado das expressões lambda é determinado pela forma como elas podem ser encurtadas.
Existem três tipos de cortes:
- α-transform: alterando variáveis vinculadas (alfa).
- β-redução: aplicando funções aos seus argumentos (beta).
- η-transform: cobre a noção de extensionalidade.
Aqui tambémestamos falando das equivalências resultantes: duas expressões são β-equivalentes se podem ser β-transformadas no mesmo componente, e α / η-equivalência é definida de forma semelhante.
O termo redex, abreviação de turnover redutível, refere-se a subtópicos que podem ser reduzidos por uma das regras. Cálculo lambda para manequins, exemplos:
(λ x. M) N é um beta redex na expressão para substituir N por x em M. O componente ao qual um redex reduz é chamado de redutor. A redução (λ x. M) N é M [x:=N].
Se x não é livre em M, λ x. M x também em-REDEX com regulador M.
α-transformação
As renomeações Alfa permitem que você altere os nomes das variáveis vinculadas. Por exemplo, x. x pode dar λ y. sim Os termos que diferem apenas na transformação alfa são chamados de α-equivalentes. Muitas vezes, ao usar o cálculo lambda, os α-equivalentes são considerados recíprocos.
As regras exatas para conversão alfa não são totalmente triviais. Primeiro, com essa abstração, apenas as variáveis associadas ao mesmo sistema são renomeadas. Por exemplo, a transformação alfa λ x.λ x. x pode levar a λ y.λ x. x, mas isso pode não levar a λy.λx.y Este último tem um significado diferente do original. Isso é análogo ao conceito de programação de sombreamento variável.
Segundo, uma transformação alfa não é possível se resultar em ser capturada por uma outra abstração não permanente. Por exemplo, se você substituir x por y em λ x.λ y. x, então você pode obterλy.λy. u, que não é a mesma coisa.
Em linguagens de programação com escopo estático, a conversão alfa pode ser usada para simplificar a resolução de nomes. Ao mesmo tempo, cuidando para que o conceito de variável não mascare a designação na área de contenção.
Na notação de índice de De Bruyne, quaisquer dois termos equivalentes a alfa são sintaticamente idênticos.
Substituição
As mudanças escritas por E [V:=R] são o processo de substituir todas as ocorrências livres da variável V na expressão E pelo turnover R. A substituição em termos de λ é definida pelo lambda da recursão cálculo na estrutura do conceito da seguinte forma (nota: x e y - somente variáveis, e M e N - qualquer expressão λ).
x [x:=N] ≡ N
y [x:=N] ≡ y se x ≠ y
(M 1 M 2) [x:=N] ≡ (M 1 [x:=N]) (M 2 [x:=N])
(λ x. M) [x:=N] ≡ λ x. M
(λ y. M) [x:=N] y λ y. (M [x:=N]) se x ≠ y, desde que y ∉ FV (N).
Para substituição em uma abstração lambda, às vezes é necessário transformar α em uma expressão. Por exemplo, não é verdade que (λ x. Y) [y:=x] resulte em (λ x. X) porque o x substituído deveria estar livre, mas acabou sendo vinculado. A substituição correta neste caso é (λ z. X) até α-equivalência. Observe que a substituição é definida exclusivamente até lambda.
β-redução
Redução Beta reflete a ideia de aplicar uma função. Beta-redutivo é definido em termossubstituição: ((X V. E) E ') é E [V:=E'].
Por exemplo, assumindo alguma codificação 2, 7, ×, existe a seguinte β-redução: ((λ n. N × 2) 7) → 7 × 2.
Redução beta pode ser vista como o mesmo conceito de redutibilidade local sob dedução natural via isomorfismo de Curry-Howard.
η-transform
Esta conversão expressa a ideia de extensionalidade, que neste contexto é que duas funções são iguais quando dão o mesmo resultado para todos os argumentos. Esta conversão troca entre λ x. (F x) e f sempre que x não parece livre em f.
Esta ação pode ser considerada a mesma do conceito de completude local na dedução natural através do isomorfismo de Curry-Howard.
Formas normais e fusão
Para um cálculo lambda não tipado, a regra de β-redução geralmente não é normalização forte nem fraca.
No entanto, pode-se mostrar que a redução β se funde ao ser executada antes da transformação α (ou seja, duas formas normais podem ser consideradas iguais se for possível uma transformação α de uma para a outra).
Portanto, tanto os termos de normalização forte quanto os termos de ajuste fraco têm uma única forma normal. Para os primeiros termos, é garantido que qualquer estratégia de redução resultará em uma configuração típica. Considerando que para condições de normalização fraca, algumas estratégias de redução podem não encontrá-lo.
Métodos de programação adicionais
Existem muitos idiomas de criação para o cálculo lambda. Muitos deles foram desenvolvidos originalmente no contexto do uso de sistemas como base para a semântica de uma linguagem de programação, aplicando-os efetivamente como uma construção de baixo nível. Como alguns estilos incluem um cálculo lambda (ou algo muito semelhante) como um trecho, essas técnicas também são usadas na criação prática, mas podem ser percebidas como obscuras ou estrangeiras.
Contantes nomeadas
No cálculo lambda, uma biblioteca assume a forma de um conjunto de funções previamente definidas, onde os termos são apenas constantes concretas. O cálculo puro não tem conceito de imutáveis nomeados, pois todos os termos atômicos lambda são variáveis. Mas eles também podem ser imitados tomando o mutável como o nome da constante, usando uma abstração lambda para vincular esse volátil no corpo e aplicando essa abstração à definição pretendida. Então, se você usar f para representar M em N, você poderia dizer
(λ f. N) M.
Os autores geralmente introduzem um conceito sintático como let para permitir que as coisas sejam escritas de uma forma mais intuitiva.
f=M para N
Ao encadear tais definições, pode-se escrever um "programa" de cálculo lambda como zero ou mais definições de função seguidas por um único membro lambda, usando as definições que compõem a maior parte do programa.
Uma limitação notável deste let é que o nome f não é definido em M,já que M está fora do escopo de ligação da abstração lambda f. Isso significa que um atributo de função recursiva não pode ser usado como M com let. A sintaxe letrec mais avançada, que permite escrever definições de funções recursivas neste estilo, usa adicionalmente combinadores de ponto fixo.
Análogos impressos
Este tipo é um formalismo tipado que usa um símbolo para representar uma abstração de função anônima. Nesse contexto, os tipos geralmente são objetos de natureza sintática que são atribuídos a termos lambda. A natureza exata depende do cálculo em questão. De um certo ponto de vista, o LI tipado pode ser considerado como refinamento do LI não tipado. Mas, por outro lado, eles também podem ser considerados uma teoria mais fundamental, e o cálculo lambda não tipado é um caso especial com apenas um tipo.
Typed LI são a base das linguagens de programação e a espinha dorsal de linguagens funcionais como ML e Haskell. E, mais indiretamente, estilos imperativos de criação. Cálculos lambda tipados desempenham um papel importante no desenvolvimento de sistemas de tipos para linguagens de programação. Aqui, tipabilidade geralmente captura as propriedades desejadas do programa, por exemplo, não causará uma violação de acesso à memória.
Os cálculos lambda tipados estão intimamente relacionados à lógica matemática e à teoria da prova através do isomorfismo de Curry-Howard, e podem ser pensados como uma linguagem interna de classes de categorias, por exemplo, quesimplesmente é o estilo de fechamentos cartesianos.
