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

(ezzeriesa.notion.site)

2 pontos por GN⁺ 2024-11-18 | 1 comentários | Compartilhar no WhatsApp

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.

1 comentários

GN⁺ 2024-11-18

Opiniões no Hacker News

Fica o aviso: se você mergulhar fundo em SICP/Lisp/Scheme, isso pode mudar sua forma de pensar sobre programação, e esse tipo de estímulo intelectual é sempre bem-vindo.
Mas aplicar essas ideias por inteiro a uma base de código orientada a objetos geralmente acaba sendo contraproducente ou provoca resistência da equipe.
Por exemplo, depois de Lisp, você pode ficar com vontade de trocar todos os loops for por forEach ou transformar tudo em cadeias de map/reduce, mas, se a linguagem não abraça plenamente a programação funcional, isso pode prejudicar tanto a legibilidade quanto o desempenho.
No fim, lembrar que memória mutável e CPUs processam o código ajuda a manter os pés no chão; hoje em dia, vejo design orientado a dados e “empatia mecânica” alinhada à realidade do hardware como mais práticos no dia a dia do que abstrações como números de Church.
- Vejo imutabilidade como algo mais seguro.
  Quanto menos efeitos colaterais, mais previsível fica; e orientação a objetos é usada com frequência até onde funções simples seriam suficientes.
  No desenvolvimento de jogos, há muitos cálculos e código arriscado, então orientação a objetos se encaixa bastante bem; mas, no desenvolvimento web, programação funcional é muito mais natural e, em SaaS, linguagens como Elixir permitem escrever código mais confiável, com menos bugs e mais fácil de testar.
- Também existe algo como o Common Lisp Object System, não?
  Além disso, coisas como forEach e map/reduce já existiam nas coleções do Smalltalk e foram copiadas para Object Pascal e C++, mesmo não sendo sintaxe de primeira classe.
  Como a memória subjacente é mutável, quando isso é realmente necessário, até linguagens da família ML têm mecanismos para lidar com mutação.
- A única forma como a CPU implementa fluxo de controle é algo próximo de goto, mas goto é ainda menos popular que Lisp.
  O mais estranho é que, em CPUs modernas, cache é essencial para desempenho, mas ainda não existe uma linguagem que trate a hierarquia de memória como cidadã de primeira classe.
  O mais próximo parece ser o C no estilo Linux, com sublinhados transbordando como um mar.
Oferece uma boa introdução a como codificar estado com funções puras.
Na prática, há muito mais codificações puramente funcionais para todo tipo de dado: árvores, inteiros, tipos soma/produto, imagens, mônadas etc.
A codificação pode ser um pouco confusa, mas ao mesmo tempo é elegante e pequena.
Por exemplo, uma implementação funcional da mônada Maybe em JavaScript ficaria assim:
Nothing = nothing => just => nothing
Just = v => nothing => just => just(v)
pure = Just
bind = mx => f => mx(mx)(f)
evalMaybe = maybe => maybe("Nothing")(v => "Just " + v)
console.log(evalMaybe(bind(Nothing)(n => pure(n + 1)))) // Nothing
console.log(evalMaybe(bind(Just(42))(n => pure(n + 1)))) // Just 43
- Esse tipo de implementação pode ser derivado do princípio de recursão do respectivo tipo.
  data Maybe a = Nothing | Just a
  foldMaybe :: (Unit -> r) -> (a -> r) -> Maybe a -> r
  As duas funções de ordem superior passadas para foldMaybe correspondem, respectivamente, a Nothing e Just.
  Só que, no lado de Nothing, foi adicionado um parâmetro Unit para ficar um pouco mais preciso.
- Dá para ver isso como transformar um tipo indutivo no tipo de sua função recursora.
  Em teoria dos tipos, é bem bacana, mas, para programação prática, não é lá muito bom.
- Matematicamente pode ser elegante, mas, quando é transmitido por uma linguagem composta apenas pelo conjunto de caracteres ASCII, sem ordenação nem justificação interna, fica bastante doloroso de olhar.
- Em resumo, o cálculo lambda não tipado é Turing-completo.
Há algum tempo, assisti às aulas reais de SICP, isto é, às gravações de 1986 do MIT OCW.
Elas são frequentemente elogiadas pela alta densidade de informação, mas, na prática, bastante tempo é desperdiçado com perguntas e respostas dos alunos, com o instrutor chamando atenção para tentativas de apresentação “multimídia” em sala de aula, e com partes em que o planejamento geral do curso não estava totalmente organizado de antemão, então ele não conseguia antecipar e evitar certas perguntas.
O tempo gasto escrevendo no quadro também fica considerável quando acumulado.
Claro, a ordem do material pode ser discutida e reorganizada à vontade, e algum dia também pretendo criar eu mesmo uma série de vídeos explicando esse conteúdo de um jeito que combine com a minha intuição.
Fico feliz que este curso pareça manter as raízes mesmo usando uma linguagem mais moderna como Python, e, como Python é uma linguagem multiparadigma prática, acho que as pessoas não reconhecem suficientemente sua expressividade por meio de idiomas funcionais, ainda que não haja pureza completa.
- Este curso implementa Scheme em Python e depois implementa Scheme novamente em Scheme.
  Acho que Python poderia e deveria ser removido deste curso.
  Python tem suporte muito fraco a programação funcional.
  Listas não são baseadas em cons, lambdas têm muitas restrições, pattern matching é horrível e nem é baseado em expressões, e os namespaces também são estranhos.
  Python também dificilmente pode ser considerado uma linguagem moderna; ele ficou preso nos anos 1990 e só cresceu, infelizmente sacrificando linguagens melhores, porque tem uma C-API decente.
- A programação funcional em Python é bastante fraca e, nesse aspecto, acho que JavaScript é até melhor.
  Como não há otimização de chamadas de cauda, alguns exercícios de código exigem soluções completamente diferentes das de Scheme.
  Quando um código traduzido 1:1 falha, fico pensando se o instrutor deve dizer aos alunos para simplesmente acreditarem que ele se comporta assim por causa da linguagem escolhida, ou se deve tratar tudo como um problema de externalizar a pilha e resolver dessa forma.
  Enfiar SICP à força em Python parece bastante tolo.
- Também há as aulas da ArsDigita University.
  O site está offline agora, mas é possível ver as aulas no archive.org.
  https://en.m.wikipedia.org/wiki/ArsDigita#ArsDigita_Foundati...
  https://archive.org/details/arsdigita_01_sicp/
  Eles vendiam um pendrive com o currículo completo; seria ótimo se alguém disponibilizasse a ISO.
  https://web.archive.org/web/20190222145553/aduni.org/drives/
- O problema de Python e da maioria das linguagens não Lisp é que elas não permitem facilmente tratar programas como dados.
  Coisas que são expressas de forma simples em Scheme viram exercícios complicados em outras linguagens.
  Em vez de se concentrarem nos conceitos subjacentes, os alunos acabam se concentrando em detalhes da linguagem de implementação com os quais não precisariam se preocupar em Scheme.
Quando vi pela primeira vez cons/car/cdr implementados com lambdas, pareceu mágica.
No fim, porém, vejo isso como uma demonstração de que o runtime da linguagem implementa um dicionário chave/valor, e que é possível pegar emprestada essa implementação para criar outras estruturas de dados.
- Acho a lógica de desestruturação do Elixir muito mais interessante, e a versão enfraquecida do ES6 muito mais prática.
  Em Elixir, você pode retirar quantos elementos quiser do começo.
- Não é necessário um dicionário chave/valor, apenas ponteiros.
  Uma closure sem comportamento é apenas um ponteiro para variáveis fechadas, e uma closure com dois ponteiros é um par do qual se pode obter car e cdr.
  O runtime precisa permitir que o alvo apontado seja usado fora da definição, então são necessários análise de escape, garbage collection etc., mas não um dicionário.
Recentemente me deparei, em prova de teoremas, com a ideia de que para provar algo como 0 != 1 não basta a codificação de Church; são necessários tipos de dados indutivos.
Coloquei algum conteúdo relacionado aqui de forma meio aproximada, junto com uma crítica separada a SICP: https://intellec7.notion.site/Drinking-SICP-hatorade-and-why...
Quero entender melhor os limites da perspectiva de que “tudo é apenas função”.
- Se houver algum outro fato concreto utilizável sobre desigualdade, acho que seria possível provar 0 ≠ 1.
  Pode-se inferir a partir do teorema f = g -> f x = g x para criar um fato de desigualdade no lado direito e então tomar a contrapositiva.
  Parece correto dizer que desigualdades entre numerais de Church não podem ser provadas diretamente sem outros fatos sobre desigualdade.
  Já em tipos de dados indutivos, o sistema de prova consegue “observar” diretamente igualdade ou desigualdade entre duas instâncias concretas do mesmo tipo indutivo, removendo recursivamente a aplicação do construtor mais externo.
- Para prova de teoremas, são necessários tipos Sigma e tipos Pi, além de alguma forma de noção de igualdade.
  Fico curioso se isso pode ser alcançado com codificação de Scott ou codificação de Church.
- Link corrigido: https://goosetaco.notion.site/Drinking-SICP-hatorade-and-why...
O livro em si já está sendo discutido aqui: https://news.ycombinator.com/item?id=42157558
Fico me perguntando se há algum motivo para o link ir para a discussão mais abaixo, em vez de para o início daquela página.
Talvez este post pudesse ser mesclado à discussão existente.
David Beazley é uma figura bastante lendária no mundo Python, e embora esta palestra inicialmente parecesse uma ideia surpreendente, depois de pensar por uns 2 segundos ela me pareceu uma combinação perfeita, então me inscrevi na próxima aula
O ponto central é que esse formato parece ser o futuro da educação continuada em engenharia de software
- Se não abordaram a compilação do capítulo 5, então não cobriram a melhor parte do SICP
Há um erro de digitação no código da seção “the substitution model”
("+", ("fib", ("-", "n", 2)), ("fib", ("-", "n", 1))),
O que foi definido é fibonacci, e fib não foi definido; portanto, as duas chamadas a fib claramente deveriam ser fibonacci
O código no repositório real do GitHub está correto: https://github.com/savarin/pyscheme/blob/0f47292c8e5112425b5...
Acho SICP excelente
Mas, quanto mais aprendo e estudo matemática, mais me aproximo da conclusão de que relações são um conceito primitivo mais fundamental
Toda função pode ser expressa como uma forma restrita de relação, mas o inverso não vale sem acrescentar uma quantidade considerável de aparato extra
Bancos de dados relacionais e SQL são os exemplos mais conhecidos e bem-sucedidos de programação relacional, mas vejo essa área como ainda amplamente inexplorada
Hoje meu interesse está mais em ensinar fundamentos de matemática a crianças bem pequenas do que em design de linguagens de programação
Curiosamente, ensinar predicados como “é grande” como relações unárias, e “maior que” como relações binárias, é muito mais fácil do que tentar capturar os mesmos conceitos como funções
Não gosto muito da perspectiva de que “tudo é função”, porque ela é simplificada demais e muitas vezes não ajuda
Por exemplo, há funções que não cabem em cache, RAM, disco etc.; funções cuja complexidade Big O explode, como em JOIN N-way ou busca/casamento; e funções com efeitos colaterais, incluindo não idempotência
Quase ninguém pensa em ataques de canal lateral contra funções
Há também funções não determinísticas que dependem de datas, horários, durações etc., e funções podem falhar no meio ou não falhar de forma elegante
Também é difícil presumir que elas não consomem recursos que afetam outras “funções” usando um pool de recursos compartilhado
Os argumentos de uma função podem ser arbitrariamente grandes ou complexos, mas no mundo real há limites; então você precisa de ponteiros e, de novo, de referências remotas como a web ou o disco
Seria bom me avisar quando parar; posso continuar falando
- Simplificações excessivas às vezes podem ser ótimas
  Neste caso, o modelo de cálculo lambda é a base da abordagem “tudo é apenas função” e é um bom modelo de computação por ser muito simples e, ao mesmo tempo, mais fácil de manipular e raciocinar do que máquinas de Turing etc.
  Por isso ele está na base da maior parte da lógica computacional e dos sistemas de prova
- Muitas dessas coisas podem ser modeladas como funções; na verdade, basta que sejam escritas assim
  Se uma função precisa de um recurso, faça com que ela exija esse recurso; se depende de data/hora, faça com que dependa de data/hora; se retorna um valor não determinístico, faça com que retorne um valor não determinístico
  Um dos motivos pelos quais a abordagem de programação funcional brilha é que ela força você a tratar essas coisas com seriedade
  Se você quer usar um recurso compartilhado implicitamente, precisa modelá-lo, e uma “função” que depende de um recurso compartilhado implícito fica explicitamente diferenciada de uma função real
- Metade do que foi chamado aqui de função na verdade não é função, e muita gente no mundo da programação funcional também não chamaria de função
  Está mais para procedimento
  Uma função é um procedimento, mas nem todo procedimento é uma função
- Para fins teóricos, acho que essa é a única esperança