No desenvolvimento de programas é importante ter em conta como é que um programa é executado e, em particular, como é que o processo computacional inerente à execução do programa evolui. Vamos agora analisar alguns padrões típicos de evolução de programas e funções.
Recursão linear
Exemplo:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)Tal como vimos em aulas anteriores, a execução/avaliação desta função implica a geração de vários ambientes locais diferentes, todos referentes a esta função (ou bloco). Em cada ambiente ficamos com uma operação adiada, nomeadamente a multiplicação no segundo return, até atingirmos a o caso base, i.e., n == 0.
Esta sequência de ambientes encadeados começa com expansão dos mesmos até chegarmos ao ambiente final, envolvendo simultaneamente uma expansão na memória necessária para alojar os ambientes criados. Uma vez atingido o caso terminal ou base, ocorre uma contracção em que as operações adiadas são realizadas e os ambientes vão sendo libertados.
O processo gerado pelo encadeamento de chamadas à função factorial:
factorial(4) | factorial(3) | | factorial(2) | | | factorial(1) | | | | factorial(0) | | | | return 1 | | | return 1 | | return 2 | return 6 return 24
Exercício 1: Apresente o encadeamento de chamadas à função potencia.
def potencia(x, n):
if n == 0:
return 1
else:
return x * potencia(x, n - 1)Exercício 2: Apresente o encadeamento de chamadas à função soma.
def soma(lst):
if lst == []:
return 0
else:
return lst[0] + soma(lst[1:]Todas estas funções geram processos computacionais com um comportamento semelhante, são caracterizados por uma fase de crescimento e por uma fase de contracção. Estes processos são denominados de processos recursivos, nos quais é criada uma sequência de ambientes correspondente à sequência de chamadas à função.
Em geral cada chamada recursiva deixa operações em espera ou adiadas, embora possam existir situações em que tal não acontece.
Nos casos vistos até agora, o número de ambientes cresce linearmente em função de um determinado valor, pelo que este tipo de processo recursivo é denominado por processo recursivo linear.
Iteração linear
Vejamos implementações alternativas para as funções anteriores que geram processos com um padrão de evolução denominado iteração linear.
def factorial(n):
res = 1
for i in range(1, n+1):
res = res * i
return resExercício: Providencie implementações iterativas para as funções potencia e soma.
Este tipo de implementação gera um processo denominado de processo iterativo. Este tipo de processo é caracterizado por um conjunto de variáveis, variáveis de estado, e por regras que especificam como actualizá-las. Estas variáveis determinam uma descrição completa do estado do processo computacional em cada momento.
Nos exemplos anteriores o número de operações sobre as variáveis de estado cresce linearmente com um valor associado à função, e.g., no caso da função factorial cresce com o parâmetro n. Um processo iterativo cujo número de operações cresce linearmente em função de um valor designa-se por processo iterativo linear.
Recursão de cauda
Mesmo quando definimos funções recursivamente, podemos utilizar variáveis de estado e gerar processos idênticos aos processos iterativos. Em particular, dependendo dos interpretadores e compiladores de cada linguagem de programação, estas funções geram de facto processo iterativos sem ambientes encadeados ou operações adiadas.
O estado em funções recursivas pode ser mantido através do uso de parâmetros formais extra. Exemplo:
def factorial(n, acc):
if n == 0:
return acc
else:
return factorial(n - 1, n * acc)Notar que neste exemplo, assim como na maior parte dos casos em que aplicamos esta técnica, a chamada recursiva é a última operação realizada pela função, não existindo operações adiadas. Este padrão de computação é em geral denominado de recursão de cauda.
Utilizando técnicas que vimos em aulas anteriores, podemos reescrever a função factorial como:
def factorial(n):
def factorial_aux(n, acc):
if n == 0:
return acc
else:
return factorial_aux(n - 1, n * acc)
return factorial_aux(n, 1)Notar que o acumulador na função auxiliar é inicializado com o valor a retornar no caso base.
Exercício: Providencie implementações recursivas de cauda para as funções potencia e soma.
O processo gerado pelo encadeamento de chamadas à função factorial é neste caso:
factorial(4) | factorial_aux(4, 1) | | factorial_aux(3, 4) | | | factorial_aux(2, 12) | | | | factorial_aux(1, 24) | | | | | factorial_aux(0, 24) | | | | | return 24 | | | | return 24 | | | return 24 | | return 24 | return 24 return 24
Ainda que não existam operações adiadas, como em Python não temos a optimização de recursão de cauda, a sequência de ambientes gerada, assim como a criação e eliminação dos mesmos, é em tudo idêntica ao que acontece nos processos recursivos que vimos acima. Isto poderá levar em particular à exaustão da pilha de execução. Noutras linguagens, como LISP, quer as funções iterativas quer as funções que recorrem a recursão de cauda geram automaticamente processos iterativos.
Na realidade podemos utilizar um truque em Python para que funções com recursão de cauda gerem processos "iterativos".
def tco(arg):
while True:
try:
arg = arg()
except TypeError:
return arg
def factorial(n):
def factorial_aux(n, acc):
if n == 0:
return acc
else:
return lambda: factorial_aux(n - 1, n * acc)
return tco(factorial_aux(n, 1))O truque é retornar uma função anónima sem parâmetros na função auxiliar para que não ocorra a acumulação de ambientes e, portanto, não ocorra a exaustão da pilha de execução.
O processo gerado pelo encadeamento de chamadas é neste caso:
factorial(4) | tco(factorial_aux(4, 1)) | | factorial_aux(4,1) | | | return lambda: factorial_aux(3,4) | | factorial_aux(3,4) | | | return lambda: factorial_aux(2,12) | | factorial_aux(2,12) | | | return lambda: factorial_aux(1,24) | | factorial_aux(1,24) | | | return lambda: factorial_aux(0,24) | | factorial_aux(0,24)() | | | return 24 | | return 24 | return 24 return 24
Em alternativa, tendo por base um fixed-point combinator (existem várias alternativas) e o truque anterior, podemos reescrever a função factorial utilizando recursão de cauda da seguinte forma:
def Y_combinator(f):
Yf = (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args))))(f)
return lambda *args: tco(Yf(*args))
factorial = Y_combinator(lambda f: lambda n, acc: acc if n == 0 else f(n-1, n*acc))
factorial(10000,1)Neste caso temos uma evolução idêntica a:
F = lambda f: lambda n, acc: acc if n == 0 else f(n-1, n*acc) G = lambda y: F(lambda *args: lambda: y(y)(*args)) (lambda x: x(x))G(10000, 1) G(G)(10000, 1) F(lambda *args: lambda: G(G)(*args))(10000, 1) (lambda n, acc: acc if n == 0 else (lambda *args: lambda: G(G)(*args))(n-1, n*acc))(10000, 1) (lambda *args: lambda: G(G)(*args))(9999, 10000) lambda: G(G)(9999, 10000) G(G)(9999, 10000) ...
Mais detalhes em https://github.com/baruchel/tco, incluindo módulos para Python com esta implementação e outras mais avançadas e optimizadas. Em alternativa, uma vez que já identificámos as variáveis de estado, podemos sempre transformar a nossa implementação numa função iterativa. :-)