Tudo é função: impressões sobre o curso de David Beazley e o SICP

Impressões sobre o curso de David Beazley e o SICP: uma experiência de 1 semana

Compartilho a experiência de ter participado, no fim de 2022, do curso de SICP do David Beazley. Embora existam vários materiais gratuitos, o curso do Dave foi muito eficaz ao selecionar tópicos específicos e explicá-los em profundidade.

Ponto de partida

O curso de SICP foi conduzido na linguagem Scheme, e aqui isso é explicado implementando em Python um interpretador simples de Scheme, para apresentar o conceito básico do modelo de substituição.

Fundamentos da linguagem Scheme

• Primitivos (Primitive): valores básicos (ex.: inteiros)
• Operadores: operações básicas como +, -, *, / usando notação prefixa
• define: definição de variáveis

> (define x 2)  
> (+ x 3) ; resultado: 5  

• if: condicional
• lambda: definição de função anônima

> ((lambda (x) (* x x)) 3) ; resultado: 9  

Interpretador de Scheme em Python

Implementação de um interpretador simples para avaliar código Scheme usando Python. As operações básicas são definidas como funções Python.

definitions = {  
    "+": lambda x, y: x + y,  
    "*": lambda x, y: x * y,  
}  

Exemplo:

> evaluate(("+", 2, 3)) # resultado: 5  

Também inclui a implementação de define e lambda, além do tratamento da condicional if.

Modelo de substituição (Substitution Model)

O modelo de substituição é uma forma simples de interpretar programas, avaliando-os ao substituir variáveis por valores. Porém, esse modelo falha quando há atribuição (assignment).

Estado (State)

Um exemplo de quebra do modelo de substituição é a atribuição (assignment). Por exemplo, ao modelar o saldo de uma conta bancária, usa-se set! para atualizar a variável.

(define balance 100)  
  
(define (withdraw amount)  
  (set! balance (- balance amount))  
  balance)  

Nesse caso, o modelo de substituição não consegue distinguir o estado do saldo antes e depois.

Passa a ser necessário o modelo de ambiente (Environment). As variáveis são definidas dentro de um ambiente, e cada procedimento possui seu próprio ambiente.

Streams

Outra forma de modelar estado é com streams. Streams podem modelar até valores futuros por meio de avaliação preguiçosa (lazy evaluation).

Loop infinito e ordem de avaliação

Diferença na ordem de avaliação: a maioria das linguagens usa avaliação de ordem aplicativa (applicative-order evaluation), avaliando primeiro os argumentos.

> (square (+ 1 2)) ; resultado: 9  

Mas a avaliação de ordem normal (normal-order evaluation) adia a avaliação dos argumentos até que eles sejam realmente necessários. Isso pode evitar loops infinitos.

> (define (p) (p))  
> (define (test x y) (if (= x 0) 0 y))  
> (test 0 (p)) ; em ordem normal retorna 0, em ordem aplicativa entra em loop infinito  

Cálculo lambda e numerais de Church

Com Church encoding, é possível representar números como procedimentos. Esse é um conceito importante da programação funcional.

(define (zero f) (lambda (x) x))  
(define (increment n) (lambda (f) (lambda (x) (f ((n f) x)))))  

• zero é uma função que retorna o argumento como está (função identity).
• increment aplica uma chamada de função a mais.

Exemplo

> ((zero (lambda (x) (+ x 1))) 0) ; resultado: 0  
> (((increment zero) (lambda (x) (+ x 1))) 0) ; resultado: 1  

Iteração vs recursão

Em Scheme, em vez de for loops, usa-se recursão para realizar tarefas repetitivas.

Exemplo de recursão: fatorial

(define (factorial n)  
  (if (= n 1)   
    1   
    (* n (factorial (- n 1)))))  

Essa chamada recursiva pode usar a pilha e consumir bastante memória.

Otimização de chamada em cauda (Tail-call optimization)

Scheme reduz o uso de memória com otimização de chamada em cauda, fazendo o processo se comportar como um processo iterativo.

(define (factorial n)  
  (define (iter product counter)  
    (if (> counter n)  
        product  
        (iter (* product counter) (+ counter 1))))  
  (iter 1 1))  

Encerrando

O curso de David Beazley aborda em profundidade os principais conceitos do SICP ao selecionar temas centrais. Em especial, ajuda a compreender diferentes paradigmas de programação, como programação funcional, cálculo lambda e ordem de avaliação.

Citação de Knuth

Se você estuda apenas teoria, isso significa que chegou a hora de se concentrar na prática; se faz apenas prática, isso significa que chegou a hora de se concentrar na teoria.

[GN⁺]

Comentários do Hacker News

• A aula de SICP tem alta densidade de informação, mas consome muito tempo por causa das perguntas e respostas dos alunos e do uso do quadro. A ordem das aulas também pode ser reorganizada. Pessoalmente, estou planejando uma nova série de vídeos

  • A aula de SICP usa uma linguagem moderna como Python, mas mantém a intenção original
  • Python, como linguagem multiparadigma, tem grande expressividade

• Foi apresentada uma forma de codificar estado como funções puras. Existem várias codificações puramente funcionais para diferentes tipos de dados

  • As codificações podem ser confusas, mas são elegantes e concisas
  • Foi mostrado um exemplo de implementação funcional da mônada Maybe em JavaScript

• Fiquei confuso porque a âncora/hash da URL do post me levava direto ao postscript

• Implementar cons/car/cdr com lambdas pareceu magia quando vi pela primeira vez. Isso mostra que o runtime da linguagem precisa implementar um dicionário de chave/valor

• David Beazley é uma figura lendária no mundo Python, e essa aula foi surpreendente no início, mas logo pareceu uma combinação perfeita. Já me inscrevi na próxima aula

  • Isso mostra como deve ser a educação continuada para engenheiros de software

• Conheci o conceito de que tipos de dados indutivos são necessários. Só com codificação de Church não é possível provar teoremas como 0 != 1

  • Publiquei conteúdo relacionado no Notion

• O artigo em si era interessante, mas foi difícil navegar pela página. Não dava para rolar com as setas do teclado

• Há um erro de digitação no código da seção "modelo substituto". Deve usar fibonacci em vez de fib. O código no repositório do GitHub está correto

• Há um link para uma discussão em andamento sobre o livro. Fiquei curioso por que o link leva direto para a discussão no fim da página. Também me pergunto se isso pode ser integrado a outra discussão

• Foi fornecido um link do YouTube