O cálculo-λ lida apenas com um tipo de dado: funções. Porém, com funções, o tipo numérico mais simples de ser representado, portanto o mais importante, são os números naturais.

A representação de números naturais pode parecer estranha à primeira vista, mas se torna muito simples depois de entendida:

0 ≡ λsz.z
1 ≡ λsz.sz
2 ≡ λsz.s(sz)
3 ≡ λsz.s(s(sz))
4 ≡ λsz.s(s(s(sz)))

A lógica é a seguinte: são funções que recebem dois argumentos. O primeiro (s) deve ser uma função de incremento – cuja resposta é chamada “sucessor”, enquanto o segundo uma função que represente o zero (z).

Para o zero, o sucessor não é aplicado (z); para o um é aplicado apenas uma vez (sz, sucessor de zero); para o dois são feitos dois passos de sucessão (s(sz), sucessor do sucessor de zero); para o três, três passos (s(s(sz))); e assim por diante.

Algumas linguagens de programação já incorporaram esse conceito para a representação de números. Por exemplo, Idris define números naturais da seguinte forma (suprimindo docstrings):

data Nat : Type where
  Z : Nat
  S : Nat -> Nat

Então Z é zero, S Z é um, S (S Z) é 2, S (S (S Z)) é três, e assim por diante.

Prolog

Podemos emular esse comportamento em Prolog.

Primeiro precisamos de um predicado que informe o que são números naturais segundo o cálculo-λ. Podemos usar nat/1, seguindo a referência de Idris.

Precisamos informar que z (zero) é um número natural, e que o sucessor de um número natural também é um número natural:

nat(z).
nat(s(N)) :- nat(N).

Resolvido!

Conversão para inteiro

Precisamos agora de um predicado que faça a conversão para números inteiros.

A forma mais simples seria:

to_int(z, 0).
to_int(s(N), R) :- to_int(N, R1), R is R1 + 1.

Estaria resolvido, não fosse um problema: esta implementação pode gerar um estouro de pilha, já que cada instância de to_int/2 precisa aguardar que todas suas filhas de recursão terminem para liberar memória.

A forma de resolver isso é usando um acumulador para aproveitar o recurso de tail-call optimisation.

Então o predicado to_int/2 vai apenas verificar se o valor verificado é natural, e delegar a resolução para o predicado to_int/3.

Esse outro predicado lida com os seguintes parâmetros: o número natural, oacumulador (que deve ser iniciado como zero) e a resposta.

Daí to_int/2 vira:

to_int(N, R) :- nat(N), to_int(N, 0, R).

Já to_int/3 responde o acumulador quando N for z, caso contrário incrementa o acumulador e delega para a próxima instância da recursão resolver:

to_int(z, A, A).
to_int(s(N), A, R) :- succ(A, A1), to_int(N, A1, R).

Essa construção mágica onde o último parâmetro de um predicado é ligado aopenúltimo do próximo predicado numa cadeia de conjunção lógica possui um açúcar sintático em Prolog com o operador -->, que suprimi do código os dois últimos parâmetros do predicado:

to_int(z, A, A).
to_int(s(N)) --> succ, to_int(N).

Conversão a partir de inteiro

Podemos criar também um predicado que converta um número inteiro em natural. Oprincípio é muito similar. Precisamos apenas de um predicado equivalente ao succ/2 que calcule o sucessor natural:

nsucc(N, s(N)) :- nat(N).

Agora podemos fazer from_int/2 e from_int/3:

from_int(I, R) :- integer(I), I >= 0, from_int(I, z, R).

from_int(0, A, A).
from_int(I) --> { I1 is I - 1 }, nsucc, from_int(I1).

Tornando utilizável

Já podemos usar nosso natural.pl:

sh$ swipl -q

:- [natural].
true.

:- natural:to_int(z, X).
X = 0.

:- natural:to_int(s(s(s(z))), X).
X = 3.

:- natural:from_int(8, X).
X = s(s(s(s(s(s(s(s(z)))))))) .

:-

Mas podemos gerar um executável. Primeiro precisamos de um predicado pra servir de meta:

go :- current_prolog_flag(argv, [Argv]),
      atom_to_term(Argv, I, []),
      from_int(I, N),
      writeln(N), !.
go :- current_prolog_flag(os_argv, [_, '-x', Path | _]),
      file_base_name(Path, Script),
      format('use: ~w <zero_or_positive_integer>~n', [Script]).

Agora precisamos converter o script em executável:

sh$ swipl -q

:- [library(qsave)].
true.

:- [natural].
true.

:- qsave_program(natural, [init_file('natural.pl'), goal(natural:go), toplevel(halt)]).
true.

:-

Finalmente é só executar:

sh$ ./natural 12
s(s(s(s(s(s(s(s(s(s(s(s(z))))))))))))
sh$

Bônus: par ou ímpar

Como bônus, seguem dois predicados para calcular se o número natural é par ouímpar:

even(z).
even(s(N)) :- odd(N).
odd(N) :- \+ even(N).

Observação: \+ é negação lógica em Prolog; a parada tanto de even/1 quanto de odd/1 é even(z), que informa que zero é par.

Código para baixar: natural.pl.