Deixe a expressão - Let expression

Na ciência da computação, uma expressão "let" associa uma definição de função a um escopo restrito .

A expressão "let" também pode ser definida em matemática, onde associa uma condição booleana a um escopo restrito.

A expressão "let" pode ser considerada como uma abstração lambda aplicada a um valor. Dentro da matemática, uma expressão let também pode ser considerada como uma conjunção de expressões, dentro de um quantificador existencial que restringe o escopo da variável.

A expressão let está presente em muitas linguagens funcionais para permitir a definição local de expressão, para uso na definição de outra expressão. A expressão let está presente em algumas linguagens funcionais em duas formas; deixe ou "deixe rec". Let rec é uma extensão da expressão let simples que usa o combinador de ponto fixo para implementar a recursão .

História

A linguagem LCF de Dana Scott foi um estágio na evolução do cálculo lambda para as linguagens funcionais modernas. Essa linguagem introduziu a expressão let, que apareceu na maioria das linguagens funcionais desde então.

As linguagens Scheme , ML e, mais recentemente, Haskell herdaram expressões let do LCF.

Linguagens imperativas com estado, como ALGOL e Pascal, essencialmente implementam uma expressão let, para implementar escopo restrito de funções, em estruturas de bloco.

A estreitamente relacionadas "onde " cláusula, juntamente com a sua variante recursiva " onde rec ", já apareceu em Peter Landin é A avaliação mecânica de expressões .

Descrição

Uma expressão "let" define uma função ou valor para uso em outra expressão. Além de ser uma construção usada em muitas linguagens de programação funcionais, é uma construção de linguagem natural frequentemente usada em textos matemáticos. É uma construção sintática alternativa para uma cláusula where.

Deixe expressão	Cláusula Where
Deixar ${\ displaystyle a = 3}$ e ${\ displaystyle b = 4}$ no ${\ displaystyle {\ sqrt {a ^ {2} + b ^ {2}}}}$	${\ displaystyle {\ sqrt {a ^ {2} + b ^ {2}}}}$ Onde ${\ displaystyle a = 3}$ e ${\ displaystyle b = 4}$

Em ambos os casos, a construção inteira é uma expressão cujo valor é 5. Como if-then-else, o tipo retornado pela expressão não é necessariamente booleano.

Uma expressão let vem em 4 formas principais,

Forma	E	Recursiva	Definição / Restrição	Descrição
Simples	Não	Não	Definição	Definição simples de função não recursiva.
Recursiva	Não	sim	Definição	Definição de função recursiva (implementada usando o combinador Y ).
Mútuo	sim	sim	Definição	Definição de função mutuamente recursiva.
Matemático	sim	sim	Limitação	Definição matemática que suporta uma condição let booleana geral.

Em linguagens funcionais, a expressão let define funções que podem ser chamadas na expressão. O escopo do nome da função é limitado à estrutura da expressão let.

Em matemática, a expressão let define uma condição, que é uma restrição da expressão. A sintaxe também pode suportar a declaração de variáveis ​​quantificadas existencialmente locais para a expressão let.

A terminologia, sintaxe e semântica variam de idioma para idioma. Em Scheme , let é usado para a forma simples e let rec para a forma recursiva. No ML deixe marcar apenas o início de um bloco de declarações com diversão marcando o início da definição da função. Em Haskell, let pode ser recursivo mutuamente, com o compilador descobrindo o que é necessário.

Definição

Uma abstração lambda representa uma função sem nome. Esta é uma fonte de inconsistência na definição de uma abstração lambda. No entanto, abstrações lambda podem ser compostas para representar uma função com um nome. Neste formulário, a inconsistência é removida. O termo lambda,

${\ displaystyle (\ lambda fz) \ (\ lambda xy)}$

é equivalente a definir a função por na expressão , que pode ser escrita como a expressão let ; ${\ displaystyle f}$${\ displaystyle f \ x = y}$${\ displaystyle z}$

${\ displaystyle \ operatorname {let} f \ x = y \ operatorname {in} z}$

A expressão let é compreensível como uma expressão de linguagem natural. A expressão let representa a substituição de um valor por uma variável. A regra de substituição descreve as implicações da igualdade como substituição.

Vamos definição em matemática

Em matemática, a expressão let é descrita como a conjunção de expressões. Em linguagens funcionais, a expressão let também é usada para limitar o escopo. Em matemática, o escopo é descrito por quantificadores. A expressão let é uma conjunção dentro de um quantificador existencial.

${\ displaystyle (\ exists xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

onde E e F são do tipo Booleano.

A expressão let permite que a substituição seja aplicada a outra expressão. Essa substituição pode ser aplicada dentro de um escopo restrito, a uma subexpressão. O uso natural da expressão let está em aplicação a um escopo restrito (chamado de eliminação de lambda ). Essas regras definem como o escopo pode ser restrito;

${\ displaystyle {\ begin {cases} x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ implica \ operatorname {let} x: G \ operatorname {in} E \ F = E \ (\ operatorname {let} x: G \ operatorname {em} F) \\ x \ in \ operatorname {FV} (E) \ land x \ not \ in \ operatorname {FV} (F) \ implica \ operatorname {let} x: G \ operatorname {in} E \ F = (\ operatorname {let} x: G \ operatorname {in} E) \ F \\ x \ not \ in \ operatorname {FV} ( E) \ land x \ not \ in \ operatorname {FV} (F) \ implica \ operatorname {let} x: G \ operatorname {in} E \ F = E \ F \ end {cases}}}$

onde F não é do tipo Boolean . Desta definição, a seguinte definição padrão de uma expressão let, conforme usada em uma linguagem funcional, pode ser derivada.

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implica (\ operatorname {let} x: x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y}$

Para simplificar, o marcador que especifica a variável existencial,, será omitido da expressão onde é claro no contexto. ${\ displaystyle x:}$

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implica (\ operatorname {let} x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y }$

Derivação

Para derivar este resultado, primeiro suponha,

${\ displaystyle x \ not \ in \ operatorname {FV} (L)}$

então

${\ displaystyle {\ begin {alinhados} L \ (\ operatorname {let} x: x = y \ operatorname {in} z) & \ iff (\ operatorname {let} x: x = y \ operatorname {in} L \ z) \\ & \ iff x = y \ land L \ z \ end {alinhado}}}$

Usando a regra de substituição,

${\ displaystyle {\ begin {alinhado} & \ iff x = y \ land (L \ z) [x: = y] \\ & \ iff x = y \ land (L [x: = y] \ z [x : = y]) \\ & \ iff x = y \ land L \ z [x: = y] \\ & \ implica L \ z [x: = y] \ end {alinhado}}}$

então para todos L ,

${\ displaystyle L \ operatorname {let} x: x = y \ operatorname {in} z \ implica L \ z [x: = y]}$

Deixe onde K é uma nova variável. então, ${\ displaystyle L \ X = (X = K)}$

${\ displaystyle (\ operatorname {let} x: x = y \ operatorname {in} z) = K \ implica z [x: = y] = K}$

Então,

${\ displaystyle \ operatorname {let} x: x = y \ operatorname {in} z = z [x: = y]}$

Mas a partir da interpretação matemática de uma redução beta,

${\ displaystyle (\ lambda xz) \ y = z [x: = y]}$

Aqui, se y é uma função de uma variável x, não é o mesmo x que em z. A renomeação alfa pode ser aplicada. Portanto, devemos ter,

${\ displaystyle x \ not \ in \ operatorname {FV} (y)}$

tão,

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implica \ operatorname {let} x: x = y \ operatorname {in} z = (\ lambda xz) \ y}$

Este resultado é representado em uma linguagem funcional de forma abreviada, onde o significado é inequívoco;

${\ displaystyle x \ not \ in \ operatorname {FV} (y) \ implica (\ operatorname {let} x = y \ operatorname {in} z) = z [x: = y] = (\ lambda xz) \ y }$

Aqui, a variável x é implicitamente reconhecida como parte da equação que define x e a variável no quantificador existencial.

Sem levantamento de Boolean

Uma contradição surge se E for definido por . Nesse caso, ${\ displaystyle E = \ neg}$

${\ displaystyle x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ implica \ operatorname {let} x: G \ operatorname {in} E \ F = E \ (\ operatorname {let} x: G \ operatorname {in} F)}$

torna-se,

${\ displaystyle \ operatorname {let} x: G \ operatorname {in} \ neg F = \ neg \ (\ operatorname {let} x: G \ operatorname {in} F)}$

e usando,

${\ displaystyle (\ exists xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

${\ displaystyle (\ exists xG \ land \ neg F) = \ neg \ (\ exists xG \ land F)}$

${\ displaystyle = (\ existe x \ neg G \ lor \ neg F)}$

Isso é falso se G for falso. Para evitar essa contradição, F não pode ser do tipo Booleano. Para o Booleano F, a declaração correta da regra de eliminação usa implicação em vez de igualdade,

${\ displaystyle x \ not \ in \ operatorname {FV} (E) \ land x \ in \ operatorname {FV} (F) \ implica (\ operatorname {let} x: G \ operatorname {in} E \ F \ to E \ (\ operatorname {let} x: G \ operatorname {in} F))}$

Pode parecer estranho que uma regra diferente se aplique ao Boolean do que outros tipos. A razão para isso é que a regra,

${\ displaystyle (\ exists xE \ land F) \ iff \ operatorname {let} x: E \ operatorname {in} F}$

só se aplica onde F é booleano. A combinação das duas regras cria uma contradição, portanto, onde uma regra é válida, a outra não.

Juntando expressões let

Deixe as expressões podem ser definidas com várias variáveis,

${\ displaystyle (\ exists v \ cdots \ existing w \ exists xE \ land F) \ iff \ operatorname {let} v, \ ldots, w, x: E \ operatorname {in} F}$

então pode ser derivado,

${\ displaystyle x \ not \ in FV (E) \ implica (\ existe v \ cdots \ existe w \ existe xE \ land F) \ iff (\ existe v \ cdots \ existe w (E \ land \ existe xF)) }$

tão,

${\ displaystyle x \ not \ in FV (E) \ implica (\ operatorname {let} v, \ ldots, w, x: E \ land F \ operatorname {in} L \ equiv \ operatorname {let} v, \ ldots , w: E \ operatorname {em} \ operatorname {let} x: F \ operatorname {em} L)}$

Leis relacionadas ao cálculo lambda e às expressões let

A redução Eta fornece uma regra para descrever abstrações lambda. Essa regra, juntamente com as duas leis derivadas acima, definem a relação entre o cálculo lambda e as expressões let.

Nome	Lei
Equivalência Eta-redução	${\ displaystyle f \ x = y \ equiv f = \ lambda xy}$
Equivalência Let-lambda	${\ displaystyle f \ notin FV (E) \ implica (\ operatorname {let} f: f = E \ operatorname {in} L \ equiv (\ lambda fL) \ E)}$(onde é um nome de variável.) ${\ displaystyle f}$
Deixe combinação	${\ displaystyle x \ notin FV (E) \ implica (\ operatorname {let} v, \ dots, w, x: E \ land F \ operatorname {in} L \ equiv \ operatorname {let} v, \ dots, w : E \ operatorname {em} \ operatorname {let} x: F \ operatorname {em} L)}$

Deixe a definição definida a partir do cálculo lambda

Para evitar os problemas potenciais associados à definição matemática , Dana Scott originalmente definiu a expressão let do cálculo lambda. Isso pode ser considerado como a definição de baixo para cima, ou construtiva, da expressão let , em contraste com a de cima para baixo, ou definição matemática axiomática.

A expressão let simples e não recursiva foi definida como sendo um açúcar sintático para a abstração lambda aplicada a um termo. Nessa definição,

${\ displaystyle (\ operatorname {let} _ {s} x = y \ operatorname {in} z) \ equiv (\ lambda xz) \ y}$

A definição simples da expressão let foi então estendida para permitir a recursão usando o combinador de ponto fixo .

Combinador de ponto fixo

O combinador de ponto fixo pode ser representado pela expressão,

${\ displaystyle \ lambda f. \ operatorname {let} x = f \ x \ operatorname {in} x}$

Esta representação pode ser convertida em um termo lambda. Uma abstração lambda não suporta referência ao nome da variável, na expressão aplicada, então x deve ser passado como um parâmetro para x .

${\ displaystyle \ lambda f. \ operatorname {let} x \ x = f \ (x \ x) \ operatorname {in} x \ x}$

Usando a regra de redução eta,

${\ displaystyle f \ x = y \ equiv f = \ lambda xy}$

dá,

${\ displaystyle \ lambda f. \ operatorname {let} x = \ lambda xf \ (x \ x) \ operatorname {in} x \ x}$

Uma expressão let pode ser expressa como uma abstração lambda usando,

${\ displaystyle n \ not \ in FV (E) \ to (\ operatorname {let} n = E \ operatorname {in} L \ equiv (\ lambda nL) \ E)}$

dá,

${\ displaystyle \ lambda f. (\ lambda xx \ x) \ (\ lambda xf \ (x \ x))}$

Esta é possivelmente a implementação mais simples de um combinador de ponto fixo no cálculo lambda. No entanto, uma redução beta fornece a forma mais simétrica do combinador Y de Curry.

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}$

Expressão let recursiva

A expressão let recursiva chamada "let rec" é definida usando o combinador Y para expressões let recursivas.

${\ displaystyle (\ operatorname {let \ rec} x = y \ operatorname {in} z) \ equiv (\ lambda xz) \ (Y \ (\ lambda xy))}$

Expressão let mutuamente recursiva

Essa abordagem é então generalizada para oferecer suporte à recursão mútua. Uma expressão let mutuamente recursiva pode ser composta reorganizando a expressão para remover quaisquer condições e. Isso é obtido substituindo várias definições de função por uma única definição de função, que define uma lista de variáveis ​​igual a uma lista de expressões. Uma versão do combinador Y, chamado combinador de ponto fixo polivariadico Y *, é então usada para calcular o ponto fixo de todas as funções ao mesmo tempo. O resultado é uma implementação mutuamente recursiva da expressão let .

Valores múltiplos

Uma expressão let pode ser usada para representar um valor que é membro de um conjunto,

${\ displaystyle \ operatorname {let} x \ in X \ operatorname {in} x}$

Sob a aplicação da função, de uma expressão para outra,

${\ displaystyle {\ begin {alinhado} & (\ operatorname {let} x \ in X \ operatorname {in} x) \ (\ operatorname {let} y \ in Y \ operatorname {in} y) \\ & = \ operatorname {let} x \ in X \ land y \ in Y \ operatorname {in} x \ y \\ & = \ operatorname {let} (x, y) \ in X \ vezes Y \ operatorname {in} x \ y \ end {alinhado}}}$

Mas uma regra diferente se aplica para aplicar a expressão let a si mesma.

${\ displaystyle {\ begin {alinhado} & (\ operatorname {let} x \ in X \ operatorname {in} x) \ (\ operatorname {let} x \ in X \ operatorname {in} x) \\ & = \ operatorname {let} x \ in X \ operatorname {in} x \ x \ end {alinhado}}}$

Parece não haver uma regra simples para combinar valores. O que é necessário é uma forma geral de expressão que representa uma variável cujo valor é membro de um conjunto de valores. A expressão deve ser baseada na variável e no conjunto.

A aplicação da função aplicada a este formulário deve fornecer outra expressão no mesmo formulário. Desta forma, qualquer expressão em funções de valores múltiplos pode ser tratada como se tivesse um valor.

Não é suficiente que o formulário represente apenas o conjunto de valores. Cada valor deve ter uma condição que determina quando a expressão assume o valor. A construção resultante é um conjunto de pares de condições e valores, denominado "conjunto de valores". Veja o estreitamento dos conjuntos de valores algébricos .

Regras para conversão entre cálculo lambda e expressões let

Serão fornecidas meta-funções que descrevem a conversão entre as expressões lambda e let . Uma metafunção é uma função que recebe um programa como parâmetro. O programa são dados para o metaprograma. O programa e o metaprograma estão em metaníveis diferentes.

As seguintes convenções serão usadas para distinguir o programa do metaprograma,

• Os colchetes [] serão usados ​​para representar a aplicação da função no metaprograma.
• Letras maiúsculas serão usadas para variáveis ​​no metaprograma. Letras minúsculas representam variáveis ​​no programa.
• ${\ displaystyle \ equiv}$ será usado para iguais no metaprograma.

Para simplificar, a primeira regra dada que as correspondências serão aplicadas. As regras também presumem que as expressões lambda foram pré-processadas para que cada abstração lambda tenha um nome exclusivo.

O operador de substituição também é usado. A expressão significa substituir todas as ocorrências de G em L por S e retornar a expressão. A definição usada é estendida para cobrir a substituição de expressões, a partir da definição dada na página de cálculo Lambda . A correspondência de expressões deve comparar expressões para equivalência alfa (renomeação de variáveis). ${\ displaystyle L [G: = S]}$

Conversão de lambda para expressões let

As regras a seguir descrevem como converter de uma expressão lambda em uma expressão let , sem alterar a estrutura.

1. ${\ displaystyle \ operatorname {de-lambda} [V] \ equiv V}$
2. ${\ displaystyle \ operatorname {de-lambda} [M \ N] \ equiv \ operatorname {de-lambda} [M] \ \ operatorname {de-lambda} [N]}$
3. ${\ displaystyle \ operatorname {de-lambda} [F = \ lambda PE] \ equiv \ operatorname {de-lambda} [F \ P = E]}$
4. ${\ displaystyle \ operatorname {de-lambda} [E = F] \ equiv \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$
5. ${\ displaystyle \ operatorname {de-lambda} [(\ lambda FE) L] \ equiv \ operatorname {deixar-combinar} [\ operatorname {deixar} F: \ operatorname {de-lambda} [F = L] \ operatorname { em} E]}$
6. ${\ displaystyle V \ not \ in \ operatorname {FV} [\ lambda FE] \ to \ operatorname {de-lambda} [\ lambda FE] \ equiv \ operatorname {deixar-combinar} [\ operatorname {deixar} V: \ operatorname {de-lambda} [V \ F = E] \ operatorname {em} V]}$
7. ${\ displaystyle V \ neq W \ to \ operatorname {let-combine} [\ operatorname {let} V: E \ operatorname {in} \ operatorname {let} W: F \ operatorname {in} G] \ equiv \ operatorname { let} V, W: E \ land F \ operatorname {in} G}$
8. ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} V: E \ operatorname {em} F] \ equiv \ operatorname {deixar} V: E \ operatorname {em} F}$

A regra 6 cria uma variável única V, como um nome para a função.

Exemplo

Por exemplo, o combinador Y ,

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}$

é convertido para,

${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ operatorname {in} f \ (x \ x) \ operatorname {in} p }$

Regra	Expressão lambda
6	${\ displaystyle \ operatorname {de-lambda} [\ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]}$ ${\ displaystyle V \ not \ in \ operatorname {FV} [\ lambda FE] \ to \ operatorname {de-lambda} [\ lambda FE]}$ ${\ displaystyle V = p, F = f, E = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}$ ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} V: \ operatorname {de-lambda} [V \ F = E] \ operatorname {em} V]}$
4	${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]}$ ${\ displaystyle \ operatorname {de-lambda} [E = F]}$ ${\ displaystyle E = p \ f, F = (\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))}$ ${\ displaystyle \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]}$ ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$
5	${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))] \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-lambda} [(\ lambda xf \ (x \ x)) \ (\ lambda xf \ (x \ x))]}$ ${\ displaystyle \ operatorname {de-lambda} [(\ lambda FE) L]}$ ${\ displaystyle F = x, E = f \ (x \ x), L = (\ lambda xf \ (x \ x))}$ ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} F: \ operatorname {de-lambda} [F = L] \ operatorname {em} E]}$ ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} x: \ operatorname {de-lambda} [x = \ lambda xf \ (x \ x)] \ operatorname {in} f \ (x \ x) ]}$
3	${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {deixar-combinar} [\ operatorname {deixar} x: \ operatorname {de -lambda} [x = \ lambda xf \ (x \ x)] \ operatorname {em} f \ (x \ x)] \ operatorname {em} p]}$ ${\ displaystyle \ operatorname {de-lambda} [x = \ lambda xf \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [F = \ lambda PE]}$ ${\ displaystyle F = x, P = x, E = f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-lambda} [F \ P = E]}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x = f \ (x \ x)]}$
8	${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {deixar-combinar} [\ operatorname {deixar} x: \ operatorname {de -lambda} [x \ x = f \ (x \ x)] \ operatorname {em} f \ (x \ x)] \ operatorname {em} p]}$ ${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {em} f \ (x \ x) ]}$ ${\ displaystyle \ operatorname {let-combine} [Y]}$ ${\ displaystyle Y = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle Y}$ ${\ displaystyle \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x)}$
8	${\ displaystyle \ operatorname {deixar-combinar} [\ operatorname {deixar} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {deixar} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {let-combine} [Y]}$ ${\ displaystyle Y = \ operatorname {let} p: \ operatorname {de-lambda} [p \ f = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x) ] \ operatorname {em} f \ (x \ x)] \ operatorname {em} p}$ ${\ displaystyle Y}$ ${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$
4	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x = f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x = f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [E = F]}$ ${\ displaystyle E = x \ x, F = f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-lambda} [E] = \ operatorname {de-lambda} [F]}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x] = \ operatorname {de-lambda} [f \ (x \ x)]}$
2	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p \ f] = \ operatorname {let} x: \ operatorname {de-lambda} [x \ x] = \ operatorname {de-lambda} [f \ (x \ x)] \ operatorname {in} f \ (x \ x) \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [x \ x], \ operatorname {de-lambda} [f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-lambda} [p \ f], \ operatorname {de-lambda} [M_ {1} \ N_ {1}], \ operatorname {de-lambda} [M_ {2} \ N_ { 2}],}$ ${\ displaystyle M_ {1} = p, N_ {1} = f, M_ {2} = x, N_ {2} = x, M_ {3} = f, N_ {3} = x \ x}$ ${\ displaystyle \ operatorname {de-lambda} [M_ {1}] \ \ operatorname {de-lambda} [N_ {1}], \ operatorname {de-lambda} [M_ {2}] \ \ operatorname {de lambda} [N_ {2}], \ operatorname {de-lambda} [M_ {3}] \ \ operatorname {de-lambda} [N_ {3}]}$ ${\ displaystyle \ operatorname {de-lambda} [p] \ \ operatorname {de-lambda} [f], \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x], \ operatorname { de-lambda} [f] \ \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x]}$
1	${\ displaystyle \ operatorname {let} p: \ operatorname {de-lambda} [p] \ \ operatorname {de-lambda} [f] = \ operatorname {let} x: \ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x] = \ operatorname {de-lambda} [f] \ (\ operatorname {de-lambda} [x] \ \ operatorname {de-lambda} [x]) \ operatorname {em} f \ (x \ x)] \ operatorname {in} p}$ ${\ displaystyle \ operatorname {de-lambda} [V]}$ ${\ displaystyle V}$
	${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ x = f \ (x \ x) \ operatorname {in} f \ (x \ x)] \ operatorname {in} p}$

Conversão de expressões let para lambda

Essas regras revertem a conversão descrita acima. Eles convertem de uma expressão let em uma expressão lambda, sem alterar a estrutura. Nem todas as expressões let podem ser convertidas usando essas regras. As regras pressupõem que as expressões já estão organizadas como se tivessem sido geradas por de-lambda .

1. ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E] = \ operatorname {get-lambda} [F, G = \ lambda VE]}$
2. ${\ displaystyle \ operatorname {get-lambda} [F, F = E] = \ operatorname {de-let} [E]}$
3. ${\ displaystyle \ operatorname {de-let} [\ lambda VE] \ equiv \ lambda V. \ operatorname {de-let} [E]}$
4. ${\ displaystyle \ operatorname {de-let} [M \ N] \ equiv \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$
5. ${\ displaystyle \ operatorname {de-let} [V] \ equiv V}$
6. ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} V] \ equiv \ operatorname {get-lambda} [V, E]}$
7. ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L] \ equiv (\ lambda V. \ operatorname {de-let} [L]) \ \ operatorname {get-lambda} [V, E]}$
8. ${\ displaystyle W \ not \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V, W: E \ land F \ \ operatorname {em} G] \ equiv \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} \ operatorname {let} W: F \ \ operatorname {em} G]}$
9. ${\ displaystyle V \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L ] \ equiv \ operatorname {de-let} [\ operatorname {let} V: V \ V = \ operatorname {get-lambda} [V, E] [V: = V \ V] \ \ operatorname {in} L [ V: = V \ V]]}$
10. ${\ displaystyle W \ in \ operatorname {FV} [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V, W: E \ land F \ \ operatorname {in} L] \ equiv \ operatorname {de-let} [\ operatorname {let} V: V \ W = \ operatorname {get-lambda} [V, E] [V: = V \ W] \ \ operatorname {in} \ operatorname {let} W: F [V: = V \ W] \ \ operatorname {in} L [V: = V \ W]]}$

Não há equivalente estrutural exato no cálculo lambda para expressões let que possuem variáveis ​​livres que são usadas recursivamente. Neste caso, alguma adição de parâmetros é necessária. As regras 8 e 10 adicionam esses parâmetros.

As regras 8 e 10 são suficientes para duas equações mutuamente recursivas na expressão let . No entanto, eles não funcionarão para três ou mais equações recursivas mutuamente. O caso geral precisa de um nível extra de loop, o que torna a metafunção um pouco mais difícil. As regras a seguir substituem as regras 8 e 10 na implementação do caso geral. As regras 8 e 10 foram deixadas para que o caso mais simples possa ser estudado primeiro.

1. forma lambda - Converte a expressão em uma conjunção de expressões, cada uma na forma variável = expressão .
   1. ${\ displaystyle \ operatorname {lambda-form} [G \ V = E] = \ operatorname {lambda-form} [G = \ lambda VE]}$
   2. ${\ displaystyle \ operatorname {lambda-form} [E \ land F] = \ operatorname {lambda-form} [E] \ land \ operatorname {lambda-form} [F]}$
   3. ${\ displaystyle \ operatorname {lambda-form} [V = E] = V = E}$...... onde V é uma variável.
2. lift-vars - Obtenha o conjunto de variáveis ​​que precisam de X como parâmetro, porque a expressão tem X como variável livre.
   1. ${\ displaystyle X \ in \ operatorname {FV} [E] \ to \ operatorname {lift-vars} [X, V = E] = \ {V \}}$
   2. ${\ displaystyle X \ not \ in \ operatorname {FV} [E] \ to \ operatorname {lift-vars} [X, V = E] = \ {\}}$
   3. ${\ displaystyle \ operatorname {lift-vars} [X, E \ land F] = \ operatorname {lift-vars} [X, E] \ cup \ operatorname {lift-vars} [XF]}$
3. sub-vars - Para cada variável no conjunto substitua-a pela variável aplicada a X na expressão. Isso torna X uma variável passada como um parâmetro, em vez de uma variável livre no lado direito da equação.
   1. ${\ displaystyle \ operatorname {sub-vars} [E, \ {V \} \ cup S, X] = \ operatorname {sub-vars} [E [V: = V \ X], S, X]}$
   2. ${\ displaystyle \ operatorname {sub-vars} [E, \ {\}, X] = E}$
4. de-let - Eleve cada condição em E para que X não seja uma variável livre no lado direito da equação.
   1. ${\ displaystyle {\ begin {alinhados} L & = \ operatorname {lambda-form} [E] \ land S = \ operatorname {lift-vars} [X, L] \ to \ operatorname {de-let} [\ operatorname { let} V \ ldots W, X: E \ land F \ \ operatorname {in} G] \\ & \ equiv \ operatorname {de-let} [\ operatorname {let} V \ ldots W: \ operatorname {sub-vars } [L, S, X] \ \ operatorname {in} \ operatorname {let} \ operatorname {sub-vars} [\ operatorname {lambda-form} [F], S, X] \ \ operatorname {in} \ operatorname {sub-vars} [G, S, X]] \ end {alinhado}}}$

Exemplos

Por exemplo, a expressão let obtida do combinador Y ,

${\ displaystyle \ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) \ \ operatorname {in } p}$

é convertido para,

${\ displaystyle \ lambda f. (\ lambda xf \ (x \ x)) \ (\ lambda qf \ (q \ q))}$

Regra	Expressão lambda
6	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p: p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) \ \ operatorname {in} p]}$ ${\ displaystyle \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} V]}$ ${\ displaystyle V = p, E = p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {get-lambda} [V, E]}$
1	${\ displaystyle \ operatorname {get-lambda} [p, p \ f = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E]}$ ${\ displaystyle F = p, G = p, V = f, E = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {get-lambda} [F, G = \ lambda VE]}$
2	${\ displaystyle \ operatorname {get-lambda} [p, p = \ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x) ]}$ ${\ displaystyle \ operatorname {get-lambda} [F, F = E]}$ ${\ displaystyle F = p, E = \ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ operatorname {de-let} [E]}$
3	${\ displaystyle \ operatorname {de-let} [\ lambda f. \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda VE]}$ ${\ displaystyle V = f, E = \ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)}$ ${\ displaystyle \ lambda V. \ operatorname {de-let} [E]}$
7	${\ displaystyle \ lambda f. \ operatorname {de-let} [\ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [\ operatorname {let} x: x \ q = f \ (q \ q) \ \ operatorname {in} f \ (x \ x)]}$ ${\ displaystyle V \ not \ in FV [\ operatorname {get-lambda} [V, E]] \ to \ operatorname {de-let} [\ operatorname {let} V: E \ \ operatorname {in} L]}$ ${\ displaystyle V = x, E = x \ q = f \ (q \ q), L = f \ (x \ x)}$ ${\ displaystyle (\ lambda V. \ operatorname {de-let} [L]) \ \ operatorname {get-lambda} [V, E]}$
4	${\ displaystyle (\ lambda x. \ operatorname {de-let} [f \ (x \ x)]) \ \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [f \ (x \ x)]}$ ${\ displaystyle \ operatorname {de-let} [M \ N]}$ ${\ displaystyle M = f, N = (x \ x)}$ ${\ displaystyle \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$ ${\ displaystyle \ operatorname {de-let} [f] \ \ operatorname {de-let} [x \ x]}$
4	${\ displaystyle (\ lambda x. \ operatorname {deletar} [f] \ \ operatorname {deletar} [x \ x]) \ \ operatorname {get-lambda} [x, x \ q = f \ ( q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [x \ x]}$ ${\ displaystyle \ operatorname {de-let} [M \ N]}$ ${\ displaystyle M = x, N = x}$ ${\ displaystyle \ operatorname {de-let} [M] \ \ operatorname {de-let} [N]}$ ${\ displaystyle \ operatorname {de-let} [x] \ \ operatorname {de-let} [x]}$
5	${\ displaystyle (\ lambda x. \ operatorname {de-let} [f] \ (\ operatorname {de-let} [x] \ \ operatorname {de-let} [x])) \ \ operatorname {get-lambda } [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [V]}$ ${\ displaystyle V}$
1	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x \ q = f \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, G \ V = E]}$ ${\ displaystyle F = x, G = x, V = q, E = f \ (q \ q)}$ ${\ displaystyle \ operatorname {get-lambda} [F, G = \ lambda VE]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$
2	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [x, x = \ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {get-lambda} [F, F = E]}$ ${\ displaystyle F = x, E = \ lambda qf \ (q \ q)}$ ${\ displaystyle \ operatorname {de-let} [E]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$
3	${\ displaystyle (\ lambda xf \ (x \ x)) \ \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda qf \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [\ lambda VE]}$ ${\ displaystyle V = q, E = f \ (q \ q)}$ ${\ displaystyle \ lambda V. \ operatorname {de-let} [E]}$ ${\ displaystyle \ lambda q. \ operatorname {de-let} [f \ (q \ q)]}$
4	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda q. \ operatorname {de-let} [f \ (q \ q)])}$ ${\ displaystyle \ operatorname {de-let} [f \ (q \ q)]}$ ${\ displaystyle \ operatorname {de-let} [M_ {1} \ N_ {1}]}$ ${\ displaystyle M_ {1} = f, N_ {1} = q \ q}$ ${\ displaystyle \ operatorname {de-let} [M_ {1}] \ \ operatorname {de-let} [N_ {1}]}$ ${\ displaystyle \ operatorname {de-let} [f] \ \ operatorname {de-let} [q \ q]}$ ${\ displaystyle \ operatorname {de-let} [M_ {2} \ N_ {2}]}$ ${\ displaystyle M_ {2} = q, N_ {2} = q}$ ${\ displaystyle \ operatorname {de-let} [q] \ \ operatorname {de-let} [q]}$
5	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda q. \ operatorname {de-let} [f] \ (\ operatorname {de-let} [q] \ \ operatorname {de-let} [q]))}$ ${\ displaystyle \ operatorname {de-let} [V]}$ ${\ displaystyle}$ ${\ displaystyle V}$
	${\ displaystyle (\ lambda xf \ (x \ x)) \ (\ lambda qf \ (q \ q))}$

Para um segundo exemplo, pegue a versão elevada do combinador Y ,

${\ displaystyle \ operatorname {let} p, q: p \ f \ x = f \ (x \ x) \ land q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p}$

é convertido para,

${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ lambda p. \ lambda f. (p \ f) \ (p \ f)) \ \ lambda f. \ lambda xf \ (x \ x) }$

Regra	Expressão lambda
8	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p, q: p \ f \ x = f \ (x \ x) \ land q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p]}$
7	${\ displaystyle \ operatorname {de-let} [\ operatorname {let} p: p \ f \ x = f \ (x \ x) \ \ operatorname {in} \ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p]}$
1, 2	${\ displaystyle (\ lambda p. \ operatorname {de-let} [\ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p] ) \ \ operatorname {get-lambda} [p, p \ f \ x = f \ (x \ x)]}$
7, 4, 5	${\ displaystyle (\ lambda p. \ operatorname {de-let} [\ operatorname {let} q: q \ p \ f = (p \ f) \ (p \ f) \ \ operatorname {in} q \ p] ) \ \ lambda f. \ lambda xf \ (x \ x)}$
1, 2	${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ operatorname {get-lambda} [q, q \ p \ f = (p \ f) \ (p \ f)]) \ \ lambda f. \ lambda xf \ (x \ x)}$
	${\ displaystyle (\ lambda p. (\ lambda qq \ p) \ \ lambda p. \ lambda f. (p \ f) \ (p \ f)) \ \ lambda f. \ lambda xf \ (x \ x) }$

Para um terceiro exemplo, a tradução de,

${\ displaystyle \ operatorname {let} x: x \ f = f \ (x \ f) \ \ operatorname {in} x}$

é,

${\ displaystyle (\ lambda xx \ x) \ (\ lambda x. \ lambda ff \ (x \ x \ f))}$

Regra	Expressão lambda
9	${\ displaystyle \ operatorname {let} x: x \ f = f \ (x \ f) \ \ operatorname {in} x}$
1	${\ displaystyle \ operatorname {let} x: \ operatorname {get-lambda} [x, x \ f = f \ (x \ f)] [x: = x \ x] \ \ operatorname {in} x [x: = x \ x]}$
2	${\ displaystyle \ operatorname {let} x: \ operatorname {get-lambda} [x, x = \ lambda ff \ (x \ f)] [x: = x \ x] \ \ operatorname {in} x \ x}$
	${\ displaystyle \ operatorname {let} x: (x = \ lambda ff \ (x \ f)) [x: = x \ x] \ \ operatorname {in} x \ x}$
7	${\ displaystyle \ operatorname {let} x: (x \ x = \ lambda ff \ (x \ x \ f)) \ \ operatorname {in} x \ x}$
1	${\ displaystyle (\ lambda xx \ x) \ \ operatorname {get-lambda} [x, x \ x = \ lambda ff \ (x \ x \ f)]}$
2	${\ displaystyle (\ lambda xx \ x) \ \ operatorname {get-lambda} [x, x = \ lambda x. \ lambda ff \ (x \ x \ f)]}$
	${\ displaystyle (\ lambda xx \ x) \ (\ lambda x. \ lambda ff \ (x \ x \ f))}$

Pessoas chave

• Dana Scott

Veja também

• Escopo (ciência da computação)
• Lambda levantando
• Combinador de ponto fixo
• Cálculo lambda
• Paradoxo de curry
• Cálculo dedutivo lambda
• Programação de lógica de restrição
• Estreitamento de conjuntos de valores algébricos

Referências