Representando números negativos e complexos usando o cálculo Lambda

14

A maioria dos tutoriais sobre o Cálculo Lambda fornece um exemplo em que números inteiros positivos e booleanos podem ser representados por funções. E quanto a -1 e eu?

zcaudate
fonte

Respostas:

18

Primeiro codifique números e pares naturais, conforme descrito por jmad.

Represente um número inteiro como um par de números naturais tal que . Em seguida, você pode definir as operações usuais em números inteiros como (usando a notação Haskell para -calculus):( a , b ) k = a - b λk(uma,b)k=uma-bλ

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

O caso de números complexos é semelhante no sentido em que um número complexo é codificado como um par de reais. Mas uma pergunta mais complicada é como codificar reais. Aqui você tem que fazer mais trabalho:

  1. Codifique um número racional como um par que é um número inteiro, é natural e .( k , a ) k a q = k / ( 1 + a )q(k,uma)kumaq=k/(1+uma)
  2. Codifique um número real por uma função tal que para cada natural , f k codifique um número racional q tal que | x - q | < 2 - k . Em outras palavras, um real é codificado como uma sequência de racionais convergindo para ele na taxa k 2 - k .f k NxfkNfkq|x-q|<2-kk2-k

Codificar reais é muito trabalhoso e você não deseja realmente fazê-lo no -calculus. Mas veja, por exemplo, o subdiretório Marshall, para uma simples implementação de reais em puro Haskell. Isso poderia, em princípio, ser traduzido para o λ- cálcio puro .λetc/haskellλ

Andrej Bauer
fonte
1
Uau =) Estou me perguntando intuitivamente o que isso significa ... por exemplo, usando os números da igreja que codificam ... ie. um número de igreja de valor inteiro n é representado por uma função que aplica uma função a um valor n vezes. Os pares e valores lambda negativos têm uma sensação intuitiva semelhante sobre eles?
Zcaudate 8/06
1
A codificação de igreja codifica números naturais , 1 , 2 , ... Não codifica números negativos. Na resposta acima, assumi que você já sabia sobre uma codificação de números naturais, então expliquei como obter números inteiros. Os números inteiros, como os codifiquei, são uma construção mais formal, diferentemente dos numerais da Igreja, que são mais intrinsecamente conectados ao λ- cálcio. Não acho que "valores lambda negativos" sejam uma frase significativa. 0 012λ
Andrej Bauer
@zcaudate [Tipo anotações: i:ℤ, x:a, f,u,s:a→a, p:(a→a,a→a)] Se codificar ℤ como (Sign,ℕ)em seguida, dado um par de funções (s,f)como p, o termo λi.λp.λx.(fst i) (fst p) id ((snd i) (snd p) x)irão produzir tanto f(…f(x)…)ou s(f(…f(x)…))(se o resultado for negativo). Se você codificar ℤ como (ℕ,ℕ), precisará de uma função que tenha um inverso - dado um par (f,u)e x, a função λi.λp.λx.(snd i)(snd p)((fst i)(fst p) x)produzirá a u(…u(f(…f(x)…))…)qual deixará os tempos faplicados . Ambos funcionam em contextos diferentes (o resultado pode ser "invertido" || é invertível). ixf
ninguém
@zcaudate As funções extras são necessárias, pois os números codificados pela Igreja "recursam por conta própria", mas os pares entregam apenas seus componentes. As funções auxiliares apenas colam os componentes na ordem "correta" (o que ocorre automaticamente para nats.) Veja também: en.wikipedia.org/wiki/… - A codificação da igreja é basicamente fold . ctorpara qualquer construtor e esse tipo fold( r). (É por isso que, para os tipos de recursiva, os dados serão "recurse por conta própria" Para os tipos não-recursiva é mais como um. case/ Correspondência de padrão.)
ninguém
13

O cálculo lambda pode codificar a maioria das estruturas de dados e tipos básicos. Por exemplo, você pode codificar um par de termos existentes no cálculo lambda, usando a mesma codificação da Igreja que você normalmente vê para codificar números inteiros não negativos e booleanos:

fst = λ p . p ( λ x y . x ) snd = λ p . p ( λ x y . y )

par=λxyz.zxy
primeiro=λp.p(λxy.x)
snd=λp.p(λxy.y)

Em seguida, o par é p = ( emparelhar  um b ) e se você quiser voltar a e b que você pode fazer ( FST  p ) e ( SND  p ) .(uma,b)p=(par umab)umab(primeiro p)(snd p)

Isso significa que você pode facilmente representar números inteiros positivos e negativos com um par: o sinal à esquerda e o valor absoluto à direita. O sinal é um booleano que especifica se o número é positivo. O direito é um número natural usando a codificação da Igreja.

(sEugn,n)

E agora que você tem números inteiros relativos. A multiplicação é fácil de definir, basta aplicar a função xor no sinal e a multiplicação em números naturais no valor absoluto:

mult=λumab.par  (xor(primeiro uma)(primeiro b))  (mult(snd uma)(snd b))

Para definir a adição, você deve comparar dois números naturais e usar subtração quando os sinais forem diferentes; portanto, esse não é um termo λ, mas você pode adaptá-lo se realmente quiser:

adicionar=λumab.{(verdade,adicionar(snd uma)(snd b))E se uma0 0b0 0(falso,adicionar(snd uma)(snd b))E se uma<0 0b<0 0(verdade,sub(snd uma)(snd b))E se uma0 0b<0 0|uma||b|(falso,sub(snd b)(snd uma))E se uma0 0b<0 0|uma|<|b|(verdade,sub(snd b)(snd uma))E se uma<0 0b0 0|uma|<|b|(falso,sub(snd uma)(snd b))E se uma<0 0b0 0|uma||b|

mas a subtração é realmente fácil de definir:

menos=λuma.par(não(primeiro uma))(snd uma)
sub=λumab.adicionar(uma)(menosb)

(uma,b)uma+bEu

adicionar[Eu]=λz1z2.par(adicionar(primeiro z1)(primeiro z2))(adicionar(snd z1)(snd z2))
jmad
fonte
6
k(uma,b)k=uma-b
Inteiros complexos, tudo bem, mas ele estava pedindo números complexos. Por outro lado, é claro que eles nunca podem ser representados, pois são incontáveis.
HdM
@AndrejBauer: truque muito bom (talvez não tão simples) HdM: com certeza eles podem, mesmo em nem todos eles. Mas achei que o método para construir coisas no cálculo-λ com codificação da Igreja era mais importante / apropriado aqui.
Jmad
Eu gostaria de poder dar duas respostas corretas =) Eu nem estava pensando que os reais pudessem ser representados quando perguntei sobre números complexos, mas aí está!
Zcaudate 16/06/2012