Clojure: Entendendo (Infinite) Lazy Sequences

Ao iniciar recentemente meus estudos em Clojure enfrentei alguma dificuldade para entender o funcionamento de sequências infinitas. Especificamente, o simples código a seguir (retirado do livro Clojure For The Brave And True) me deixou intrigado:

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (cons n (lazy-seq (even-numbers (+ n 2))))))

(take 10 (even-numbers))
; => (0 2 4 6 8 10 12 14 16 18)

O objetivo do código é simples: ele define uma função even-numbers que retorna uma sequência infinita de números pares. Mas a implementação me deixou confuso…

A primeira coisa que me intrigou foi a chamada recursiva na função. Isso não deveria resultar em um stack overflow??? Afinal, a função não parece conter nenhuma condição de parada…

Depois de quebrar um pouco a cabeça, concluí (com razão) que eu ainda não possuía o domínio básico da linguagem necessário para compreender o que estava se passando. Decidi prosseguir com a leitura do livro e retornar depois.

Primeira pista: lazy-seq é uma Macro

Após ler o capítulo de Macros achei que finalmente poderia compreender o que estava se passando. Acontece que o operador lazy-seq é uma Macro, não uma função.

Uma das principais diferenças entre macros e funções é que as funções tem seus argumentos completamente avaliados antes de serem invocadas; Já as macros recebem seus argumentos como estruturas de dados (normalmente listas). Ou seja, provavelmente a chamada recursiva (que é passada como argumento para a macro lazy-seq) não é avaliada até que a primeira execução de even-numbers já tenha retornado.

Ahá!

Mas… alguma coisa ainda não batia. Eu não entendia completamente como a sequência infinita estava sendo gerada. Se a chamada recursiva não era executada durante a chamada atual de even-numbers, o que exatamente a função cons estava retornando no trecho de código a seguir?

(cons n (lazy-seq (even-numbers (+ n 2)))))

Eu sabia que lazy-seq retorna uma sequência lazy, cujos elementos não são “realizados” (computados) até que algum código cliente tente acessá-los. Ou seja, a chamada recursiva de even-numbers em:

(cons n (lazy-seq (even-numbers (+ n 2)))))

seria executada somente quando outro código tentasse acessar pela primeira vez os valores da lazy sequence retornada por lazy-seq.

Ora, mas não é isso que a função cons está fazendo?? No meu entendimento, para que o código (cons n (lazy-seq …)) pudesse ser executado, seria necessário que a lazy sequence fosse completamente realizada, para só então “juntar” com o elemento n !

E se fosse assim, a realização da lazy sequence deveria acarretar na chamada recursiva de even-numbers, o que eventualmente causaria o stack overflow…

Segunda pista: cons não força a realização da Lazy Sequence!

Depois de gastar algum tempo pesquisando no Google e me deparar com essa ótima resposta de Alex D no StackOverflow (ironicamente), eu finalmente compreendi: Acontece que cons NÃO FORÇA a realização da lazy sequence!

Isso não acontece por exemplo com a funçãoconj. Se reescrevermos a função even-numbers utilizando conj ao invés de cons, ocorrerá o stack overflow como esperado:

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (conj (lazy-seq (even-numbers (+ n 2))) n )))
(take 10 (even-numbers))
; => StackOverflowError

Os detalhes do porquê de cons não forçar a realização da sequência estão explicados na resposta do link. Em resumo, tem a ver com o fato de cons retornar objetos da classe clojure.lang.Cons;

Os objetos dessa classe representam sequências (implementam a interface clojure.lang.ISeq) e são estruturados internamente com duas referências: um objeto “_first” (o primeiro item da sequência) e um objeto “_more” (o restante da sequência, que é também uma sequência). O objeto Cons não precisa saber se seu “_more” consiste em uma lista, um vetor ou mesmo uma Lazy Sequence; Tudo o que importa é que seja um objeto que também implemente ISeq. Além disso, o objeto Cons não precisa saber nada sobre os elementos da sequência “_more”. Portanto, ele não precisa realizar a sequência (ao contrário de conj, que precisa realizar a sequência para completar sua execução).

Conclusão

Retornando à função even-numbers:

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (cons n (lazy-seq (even-numbers (+ n 2))))))
(take 10 (even-numbers))

Quando essa função é invocada, os seguintes passos são executados:

1. Primeiramente, a macro lazy-seq cria e retorna um objeto do tipo clojure.lang.LazySeq. Esse objeto representa uma lazy sequence que ainda não possui nenhum elemento realizado (computado), mas que vai executar o código (even-numbers (+ n 2)) para obter uma sequência real assim que seus elementos forem requisitados.
2. Em seguida, a função cons cria um objeto do tipo clojure.lang.Cons , seta sua propriedade “_first” para o valor n e sua propriedade “_more” para o objeto LazySeq retornado anteriormente por lazy-seq. Até o momento, o objeto LazySeq não precisou realizar nenhum elemento da sequência.
3. A função even-numbers retorna o objeto Cons.
4. A função take tenta acessar o primeiro elemento da sequência, e o objeto Cons retorna o seu “_first” (o valor n = 0).
5. A função take tenta acessar o segundo elemento da sequência, e o objeto Cons delega o acesso a esse elemento para o seu “_more”, que é a lazy sequence. O objeto LazySeq executa o código que foi passado para a macro: (even-numbers (+ n 2)) . O retorno desse código é um novo objeto Cons, cujo “_first” é o valor 2 e cujo “_more” é uma nova lazy sequence. O valor 2 é retornado para a função take.
6. O processo se repete.

Portanto, esse método de construção de sequências infinitas em Clojure é possível não apenas por causa da macro lazy-seq mas também pelo comportamento da função cons que representa uma sequência em termos de um elemento “_first” e outra sub-sequência “_more”.