Jardinagem de Árvores Abstratas

Link da palestra

Um pouco sobre o jardineiro

Bairro Felicidade, Belo Horizonte

PSL-MG, Minas Livre, Encontro Mineiro de Software Livre

Ministério da Cultura, Cultura Digital

Governo do Rio Grande do Sul, Gabinete Digital

Uma meia dúzia de startups, Burnout

Recurse Center, reaprendendo a programar

https://recurse.com

DataDog, atual

Façamos uma pequena linguagem de programação

Por que? Pra que? Pra quem?

Este é um papo informal

Expressões Aritméticas

1 + 2 * 3 = 7
(1 + 2) * 3 = 9

Primeiros Arbustos

Propriedades de Operadores

• Aridade
• Precedência
• Associatividade

Notações de Expressões

• infix
• prefix
• postfix

Prefix

+ 1 * 2 3 = 7
* + 1 2 3 = 9

Quem usa notação prefix?

lisp é um exemplo

(+ 1 (* 2 3))
(* 3 (+ 1 2))

Postfix

3 2 * 1 + = 7
1 2 + 3 * = 9

Quem usa notação postfix?

Máquina de Pilha

push 3
push 2
mul
push 1
add

push 2
push 1
add
push 3
mul

Pilhas

Array.push() e Array.pop()

Uma pausa pra falar de arquitetura

Compilação

A linguagem alvo pode ser ou uma linguagem textual, ou código de máquina (Bytecode, Assembly).

Execução

• Interpretador de Árvores: Exemplo
• Interpretador de Bytecode: Exemplo
• Código de Máquina (Assembly): Intel x86, ARM, RISC-V, etc

Exemplos

texto pra texto

texto pra bytecode

texto pra bytecode

A JVM é alvo de vários compiladores: Java, Clojure, Kotlin, Scala, Groovy, Jython, etc…

Chrome's v8: everything all at once

fonte da imagem

Funções Primitivas

print("a")
print(25)

push "a"        ; copia a constante "a" pro topo do stack
prim "print" 1  ; chama a função primitiva "print"
                ; que tem 1 parâmetro

push 25         ; copia a constante 25 pro topo do stack
prim "print" 1

Variáveis

a = 1
print(a)

push 1     ; coloca o valor 1 no topo da pilha
store 0    ; remove o valor no topo da pilha
           ; e salva na variavel 0

load 0     ; copia a variável 0 pro topo da pilha
prim "print" 1

Condicionais: Galhos (Branches)

if (a == b) {
  print("oi!")
}

      push b
      push a
      ; compara os dois valores no topo da pilha
      cmp
      ; Jump If Not Equal: Pula pro rótulo "exit"
      ; se a comparação não for igual
      jne exit
      push "oi!"
      prim "print" 1
exit: halt

Repetições

a = 0
while (a < 10) {
  print(a)
  a++
}

      push 0
      store 0
loop: load 0
      push 10
      cmp
      jnb exit      ; Jump if not below
      load 0
      prim "print" 1
      load 0
      incr
      store 0
      jmp loop      ; Unconditional Jump
exit: halt

Funções

function sum() {
  a = 2
  return 40 + a
}

print(sum())

     call sum 0
     prim "print" 1
     halt

sum: push 2
     store 0
     push 40
     load 0
     sum
     ret

Extra: Parsing

Top Down Recursive Parsing

Parsing Expression Grammars

Gramáticas

e.g.: parser de CSV

File <- Line*
Line <- Val (',' Val)* '\n'
Val  <- (![,\n] .)*

Expressões

Recursos aleatórios

• https://github.com/clarete/dojo
• https://github.com/clarete/langlang/tree/main/go

O que não falamos sobre

Tipos

Biblioteca Padrão (stdlib)

Muuuita coisa 😅

Gradicido!