DEV Community: Jefferson Quesado

Implementando uma pilha a partir de uma fila

Jefferson Quesado — Tue, 19 May 2026 03:43:45 +0000

Em uma conversa despretenciosa com o Leandro Proença no LinkedIn, mencionei que dá pra implementar pilha usando apenas uma fila.

Bem, vamos fazer isso? Primeiro, vamos definir exatamente o que é "implementar uma estrutura X com uma estrutura Y", então vamos pro caso mais trivial que é implementar uma fila usando duas pilhas, então vamos implementar uma pilha usando apenas uma fila.

Nota importante aqui, muitos desses resultados e das estratégias usadas são decorrentes de conversas que já tivemos aqui no Computaria, como por exemplo:

Definindo pilhas e filas

Já definimos antes essas estruturas, né? Como em Criando filas e pilhas "apenas" com funções em java, mas ali tinha algumas limitações diferentes (como a questão dos efeitos colaterais) que me levaram a decisões de design... diferentes... do que se encontraria em um código Java selvagem em seu habitat natural.

No caso, aqui vamos usar algo mais parecido com as estruturas de dados que foram usadas para percorrer os grafos em Meu take sobre o algoritmo de Dijkstra:

push(element: T) => void
pop() => T
empty() => boolean

Aqui tanto pilha como fila vão seguir esse mesmo shape: um container que eu posso inserir objetos, recuperar objetos de lá de dentro e verificar se está vazio.

Uma fila com duas pilhas

Bem, aqui a implementação básica é a pilha, então vou precisar instanciar ela. Vou fazer de modo bem simples: um ArrayList que eu insiro e removo do final:

public class Pilha<T> {
    private final ArrayList<T> elementos = new ArrayList<>();

    public void push(T t) {
        elementos.addLast(t);
    }

    public T pop() {
        return elementos.removeLast();
    }

    public boolean empty() {
        return elementos.isEmpty();
    }
}

Ok, agora vamos fazer a partir disso uma Fila<T>. Eu posso simplesmente quando chegar um novo elemento colocar na pilha? Posso, só preciso tomar cuidado na hora de remover o elemento: não posso remover com um simples pop, preciso garantir que seja o primeiro a entrar!

O jeito clássico de fazer isso é usando uma pilha secundária: ao chegar uma requisição de pop, eu recoloco os elementos da pilha principal na pilha secundária. O último elemento removido da pilha principal equivale à parte da frente da fila, portanto precisa ser retornado. Após isso, só colocar de volta no lugar os elementos que foram deslocados (em tese daria para otimizar para muitos pop seguidos, mas aqui o foco não é otimização):

public class Fila<T> {
    private final Pilha<T> elementos = new Pilha<>();
    private final Pilha<T> secundaria = new Pilha<>();

    public void push(T t) {
        elementos.push(t);
    }

    public T pop() {
        while (!elementos.empty()) {
            secundaria.push(elementos.pop());
        }
        final var v = secundaria.pop();
        while (!secundaria.empty()) {
            elementos.push(secundaria.pop());
        }
        return v;
    }

    public boolean empty() {
        return elementos.isEmpty();
    }
}

Existe uma outra maneira de imoplementar isso, que seria pegar o elemento antes do fim. Vai sacando os valores e, ao detectar o fim, retornar o elemento encontrado:

public class Fila<T> {
    private final Pilha<T> elementos = new Pilha<>();
    private final Pilha<T> secundaria = new Pilha<>();

    public void push(T t) {
        elementos.push(t);
    }

    public T pop() {
        while (true) {
            final var candidato = elementos.pop();
            if (elementos.empty()) {
                // devolve os elementos de volta
                while (!secundaria.empty()) {
                    elementos.push(secundaria.pop());
                }
                return candidato;
            }
            secundaria.push(candidato);
        }
    }

    public boolean empty() {
        return elementos.isEmpty();
    }
}

Uma pilha com duas filas

Bem, já que estamos trocando de empurrar no começo pro empurrar no fim, será que dá para pegar o exato mesmo algoritmo de duas pilhas simulando uma fila e fazer duas filas simulando uma pilha? Na real... dá sim!

Não importa o como vai ser implementada a fila em si, apenas que siga a convenção de comportamento. Então, podemos até assumir que vamos usar a fila desenvolvida na seção anterior.

Com isso fora de preoucupação, vamos seguir o mesmo formato de algoritmo:

public class Pilha<T> {
    private final Fila<T> elementos = new Fila<>();
    private final Fila<T> secundaria = new Fila<>();

    public void push(T t) {
        elementos.push(t);
    }

    public T pop() {
        while (true) {
            final var candidato = elementos.pop();
            if (elementos.empty()) {
                // devolve os elementos de volta
                while (!secundaria.empty()) {
                    elementos.push(secundaria.pop());
                }
                return candidato;
            }
            secundaria.push(candidato);
        }
    }

    public boolean empty() {
        return elementos.empty();
    }
}

Uma pilha com uma fila

Vamos pensar aqui qual o objetivo de se usar a fila secundária? Vamos fazer um desenho de como está sendo a questão do uso dessas coisas?

eu diminuo a fila principal
se eu cheguei no final da fila principal, o último elemento removido precisa ser retornado
se eu não cheguei no final da fila principal, preciso guardar o que foi removido
após detectar o momento do retorno, tudo que foi removido preciso ser inserido de volta na fila principal

Ou seja, eu preciso de:

indicador de fim
um buffer para restaurar a fila

E se... eu conseguir fazer isso usando apenas uma única fila? Bem, pra isso eu preciso trabalhar com a fila de modo... especial... No lugar da fila ter apenas elementos do tipo T, preciso que ela tenha um elemento tal que não seja do tipo T que eu possa diferenciar. As operações que eu faço via pilha são todas em cima de T, a API externa não muda. Mas internamente eu preciso de um novo elemento que seja incompatível com os elementos que estou inserindo. Algo semelhante foi usado para poder transformar função parcial em função total no artigo Criando mapas "apenas" com funções em java.

A minha primeira ideia seria fazer com que o backbone da implementação de Pilha<T> fosse Fila<Object> e eu iria inserir forçosamente um new Object(), que ficaria marcado no momento da criação como "elemento de diferenciação". Mas então lembrei que eu posso fazer algo semelhante a um sum-type usando sealed interface (exploro mais isso no artigo Usando Java moderno para fazer aritmética de Peano):

sealed interface Elemento<V> {
    record Demarcador<V>() implements Elemento<V> {}
    record Container<V>(V v) implements Elemento<V> {}
}

Agora vou usar uma instância Demarcador para indicar que cheguei no final da fila. Se eu tenho um final forte, isso significa que eu posso simplesmente readicionar os elementos que eu tinha após o final da fila. Logo, isso significa que manter uma estrutura secundária apenas por buffer de elementos de torna desnecessário.

Agora, ao dar um pop, preciso verificar se o elemento é o demarcador. Se for, preciso retornar o elemento que foi sacado logo antes dele. Se não for um demarcador, preciso guardar o penúltimo elemento de volta na fila, e reservar o elemento que acabei de sacar para a próxima iteração:

public class Pilha<T> {

    private sealed interface Elemento<V> {
        record Demarcador<V>() implements Elemento<V> {}
        record Container<V>(V v) implements Elemento<V> {}
    }

    private final Fila<Elemento<T>> elementos = new Fila<>();

    public void push(T t) {
        elementos.push(new Elemento.Container<>(t));
    }

    public T pop() {
        elementos.push(new Elemento.Demarcador<>());
        Elemento.Container<T> penultimo = null;
        while (true) {
            final var candidato = elementos.pop();
            if (candidato instanceof Elemento.Container<T> anotherValue) {
                if (penultimo != null) {
                    elementos.push(penultimo);
                }
                penultimo = anotherValue;
            } else {
                return penultimo.v();
            }
        }
    }

    public boolean empty() {
        return elementos.empty();
    }
}

Como teste, adicionei 4 elementos e depois saquei até o esgotamento da pilha:

final var p = new Pilha<String>();
p.push("a");
p.push("b");
p.push("c");
p.push("d");
while (!p.empty()) {
    System.out.println(p.pop());
}

Note algumas coisas interessantes:

o elemento Demarcador só é inserido durante o processo de pop, e o processo de pop só termina após sacar o Demarcador
eu só preciso fazer a reinserção dos elementos após o segundo saque

Essa observação do "segundo saque" me leva a uma implementação alternativa, que incondicionalmente faz o primeiro saque e reserva o valor, antes mesmo de sequer cogitar inserir o demarcador. A ideia é:

saca o elemento
se estiver vazio, retorna o elemento
se não estiver vazio, reserva esse elemento
insere o demarcador
continue sacando próximos elementos
se o elemento sacado for demarcador, retorne o elemento reservado
se não, insira o elemento reservado de volta e reserve o elemento sacado

public T pop() {
    var reservado = (Elemento.Container<T>) elementos.pop();
    if (elementos.empty()) {
        return reservado.v();
    }
    elementos.push(new Elemento.Demarcador<>());
    while (true) {
        final var candidato = elementos.pop();
        if (candidato instanceof Elemento.Container<T> anotherValue) {
            elementos.push(reservado);
            reservado = anotherValue;
        } else {
            return reservado.v();
        }
    }
}

[Boost]

Jefferson Quesado — Sat, 21 Feb 2026 22:44:24 +0000

Carlos Nogueira

Feb 6

[PT-BR] Pois é! Um post sobre o hype.

#webdev #programming #ai #softwareengineering

Comments

7 min read

Pequeno template em Node para programação competitiva

Jefferson Quesado — Sat, 21 Feb 2026 22:35:14 +0000

Abri o Spoj e resolvi fazer um pouco de flex com Node pelo bel prazer de resolver as coisas com JavaScript, quick n'dirt. E, bem... me deparei com um problema que eu não havia ainda cuidado: como faço para ler da entrada padrão no Node?

Objetivo

Agora, eu preciso fazer um template para usar no Spoj. A ideia é ter uma espécie de mini-boilerplate estilo o que foi fornecido nessa resposta. Por que fazer um template distinto? Porque não gostei desse, achei pouco intuitivo para mim.

Aqui a solução que o autor publicou:

// Source - https://stackoverflow.com/a/79416756
// Posted by bikeman868
// Retrieved 2026-02-20, License - CC BY-SA 4.0

const partialLine = '';
const lines = [];
const emitter = new EventEmitter()

process.stdin.on('data', (data) => {
  const buffer = this._partialLine + data
  const newLines = buffer.split('\n')
  partialLine = newLines.pop() || ''
  lines.push(...newLines)
  if (lines.length) this._emitter.emit('data')
})

Por que eu não gostei? Porque aqui eu preciso fazer uma magia com o emitter, tem muito estado do boilerplate que tá como estado global. Enfim, eu queria algo mais direto, algo como:

// resolve o problema

// define a magica

process.stdin.on('data', magica.on(solveProblemLinePerLine))

E nessa brincadeira a função solveProblemLinePerLine recebe uma linha de cada vez.

Ah, por que esse process.stdin.on('data', ...)?

Vamos por partes:

process é um objeto que carrega dados sobre o processo em si
stdin é a stream que representa a entrada padrão
.on('data', ...) é uma reação de evento de quando recebeu um dado (ou seja, de fato fez uma leitura)

Então, se eu não puser um wrapper bonito na frente, é com isso que eu preciso lidar. E, bem, meu objetivo é passar a linha inteira para frente, né? Vamos abstrair como isso é feito e pensar em soluções de problemas?

A vida, o universo e tudo mais

O primeiro problema do Spoj é um problema bem simples: repita o número informado, até encontrar o primeiro 42. A partir de então, ignore todos os números até o fim, incluindo o 42. Por exemplo, para a entrada:

A saída será:

1
2
88

Como fazer isso? Podemos fazer uma máquina de estados, em que tem um estado inicial GO e que, ao receber o valor 42, transita para o estado STOP. Se a transição não ocorrer, emite o mesmo símbolos que recebeu.

let state = "GO";
function solveProblemLinePerLine(line) {
    if (line == "42") {
        state = "STOP";
    }
    if (state == "STOP") {
        return;
    }
    console.log(line);
}

Como posso testar isso? Simples: passo cada linha manualmente!

solveProblemLinePerLine("1");
solveProblemLinePerLine("2");
solveProblemLinePerLine("88");
solveProblemLinePerLine("42");
solveProblemLinePerLine("99");

Essa questão aceita que você submeta uma resposta em Node para ela!

Gerador de primos

Aqui estou me baseando no problema Prime Generator, mas que infelizmente não aceita submissão em Node.

Na primeira linha, é informada a quantidade de casos de casos de teste, T. Para cada uma das T linhas seguintes, é informado um caso de teste que consiste de 2 números, m e n. A ideia é imprimir, para cada caso de teste, todos os primos p tal que m <= p <= n, e, ao final de um caso de testes, imprimir uma linha em branco.

Por exemplo, para a entrada:

2
1 10
3 5

Temos a saída:

Como fazer isso? Bem, no primeiro momento, temos o estado INIT, então eu entro no estado INSTANCE. Eu todo T vezes no estado INSTANCE, então após esse tempo irei para o estado END e encerro o processo.

Então, posso colocar essa máquina de estados de modo geral na função solveProblemLinePerLine:

let state = "INIT";
let nProblems = 0;

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            readNProblems(Number(line));
            state = "INSTANCE";
            break;
        case "INSTANCE":
            const s = line.split(" ")
            readInstance(Number(s[0]), Number(s[1]));
            console.log();
            nProblems--;
            if (nProblems == 0) {
                state = "END";
                process.exit(0)
            }
            break;
    }
}

Na primeira leitura, eu transformo essa linha em um número e passo para quem de fato lida com o estado. Então, altero o estado para INSTANCE.

Nas próximas leituras, eu sei que são 2 números, separados por um espaço. Então eu separo a linha pelo espaço e transformo em números essas duas partes, transmitindo esses números para quem de fato lida com isso. Após isso, eu imprimo a linha vazia que separa cada instância e subtraiu da quantidade de instâncias restante. Se a quantidade chegou em zero, muda o status para END e termino a execução do programa.

Agora, com isso em mente, como lidamos com as partes abertas? Bem, não vou tratar de modo esperto. No caso de readNProblems eu simplesmente povoo a variável nProblems. Poderia colocar isso no switch do solveProblemLinePerLine? Claro! Mas meu pensamento estava em tratar os estados, eu quis separar isso por design mesmo.

Então, eu tenho o readInstance. Aqui eu preciso iterar do começo ao fim (incluso) e, para cada primo encontrado, imprimir ele. Vou para a solução mais tosca mesmo:

function readInstance(menor, maior) {
    for (let i = menor; i <= maior; i++) {
        if (isPrime(i)) {
            console.log(i);
        }
    }
}

Agora eu preciso resolver isPrime. Bem, aqui eu poderia usar o Crivo de Eratótenes, algumas soluções mais interessantes, ou simplesmente validar dividindo pelos números menores. Como a ideia é ser simples, não vou focar em como fazer isso, vou pelo jeito bruto. Se é menor do que ou igual a 1, não é primo. Se é 2, é primo. Se é par, não é primo. Depois, de i a partir do 3 e incrementando de 2 em dois até que i*i seja maior do que o número em questão; se em algum momento esse i dividir o número em questão, então o número em questão não é primo. Se chegou no final dessa iteração, então o número é primo:

function isPrime(p) {
    if (p <= 1) {
        return false;
    }
    if (p == 2) {
        return true;
    }
    if (p % 2 == 0) {
        return false;
    }
    for (let i = 3; i * i <= p; i += 2) {
        if (p % i == 0) {
            return false;
        }
    }
    return true;
}

Juntando tudo:

let state = "INIT"
let nProblems = 0

function readNProblems(n) {
    nProblems = n
}

function isPrime(p) {
    if (p <= 1) {
        return false;
    }
    if (p == 2) {
        return true;
    }
    if (p % 2 == 0) {
        return false;
    }
    for (let i = 3; i * i <= p; i += 2) {
        if (p % i == 0) {
            return false;
        }
    }
    return true;
}

function readInstance(menor, maior) {
    for (let i = menor; i <= maior; i++) {
        if (isPrime(i)) {
            console.log(i);
        }
    }
}

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            readNProblems(Number(line));
            state = "INSTANCE";
            break;
        case "INSTANCE":
            const s = line.split(" ")
            readInstance(Number(s[0]), Number(s[1]));
            console.log();
            nProblems--;
            if (nProblems == 0) {
                state = "END";
                process.exit(0)
            }
            break;
    }
}

Testando:

solveProblemLinePerLine("2");
solveProblemLinePerLine("1 10");
solveProblemLinePerLine("3 5");

Implementando a mágica

Beleza, eu preciso pegar os eventos de dados, transformar ele em linhas e passar essas linhas adiante. Eventualmente meus dados não terão uma linha completa, então sempre o último elemento fica como resíduo. Felizmente, para os casos de programação competitiva tradicionais, a entrada é bem formatada e sempre termina com uma quebra de linha, não tem resíduo após a última quebra de linha.

Então eu preciso de uma função, que internamente tenha um eventual resíduo que se aproveita entre runs seguidas. Essa função recebe os dados e emite linhas para outra função. Como a mágica precisa ser uma coisa só, então eu preciso de uma função que retorne a função, e que mantenha dentro dela o resíduo entre linhas. Algo assim:

function splitLines() {
    let buff = "";
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            console.log(atom)
        }
        buff = parts[parts.length - 1];
    }
    return f;
}

Aqui, eu primeiro junto o resíduo da rodada anterior (começa com resíduo vazio) com a entrada, então eu separo as linhas e envio todas as linhas completas (parts.slice(0, -1)). A última parte é o resíduo, então após enviar as linhas eu atualizo o resíduo e fico pronto para receber mais dados.

Agora, eu preciso indicar o que vai acontecer com essas linhas, como se fossem "eventos". Por isso sinalizei com o .on(). Vamos usar o esquema de adicionar atributos/métodos em funções? Estilo o que foi mostrado em Recursão a moda clássica em TS: auto referência do tipo de função e em Funções como padrões de projeto: do GoF pro Computaria:

function splitLines() {
    let buff = "";
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            console.log(atom)
        }
        buff = parts[parts.length - 1];
    }
    f.on = (action) => {
        // registra a ação
        return f;
    }
    return f;
}

Nota que o .on retorna a própria função, visto que o retorno dele que vai ser usado para o process.stdin.on('data', magica.on(...)).

Ok, agora eu preciso ligar a ação passada com o laço. E... bem, por que não manter as ações anteriores? Isso pode facilitar minha vida (inclusive me ajudou a debugar a geração de primos (eu tinha esquecido de mudar o estado após a primeira leitura)). E qual seria a ação neutra para poder juntar? A noop: (linha) => {}. E agora para juntar? Eu posso executar a função anterior e depois a função nova:

let action = (linha) => {}

//...

const addAction = (newAction) => {
    const oldAction = action;
    action = (linha) => {
        oldAction(linha);
        newAction(linha);
    }
}

addAction(console.log)
addAction(linha => console.error(`recebi como entrada: >>>${linha}<<<`))

Juntando tudo isso:

// solveProblemLinePerLine definido

function splitLines() {
    let buff = "";
    let _action = (el) => {};
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            _action(atom)
        }
        buff = parts[parts.length - 1];
    }
    f.on = (action) => {
        const oldAction = _action;
        _action = (el) => {
            oldAction(el);
            action(el);
        };
        return f;
    }
    return f;
}

process.stdin.on('data', splitLines().on(solveProblemLinePerLine))

Exemplo do gerador de primos

O código completo fica assim:

let state = "INIT"
let nProblems = 0

function readNProblems(n) {
    nProblems = n
}

function isPrime(p) {
    if (p <= 1) {
        return false;
    }
    if (p == 2) {
        return true;
    }
    if (p % 2 == 0) {
        return false;
    }
    for (let i = 3; i * i <= p; i += 2) {
        if (p % i == 0) {
            return false;
        }
    }
    return true;
}

function readInstance(menor, maior) {
    for (let i = menor; i <= maior; i++) {
        if (isPrime(i)) {
            console.log(i);
        }
    }
}

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            readNProblems(Number(line));
            state = "INSTANCE";
            break;
        case "INSTANCE":
            const s = line.split(" ")
            readInstance(Number(s[0]), Number(s[1]));
            console.log();
            nProblems--;
            if (nProblems == 0) {
                state = "END";
                process.exit(0)
            }
            break;
    }
}

// boilerplate abaixo!!

function splitLines() {
    let buff = "";
    let _action = (el) => {};
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            _action(atom)
        }
        buff = parts[parts.length - 1];
    }
    f.on = (action) => {
        const oldAction = _action;
        _action = (el) => {
            oldAction(el);
            action(el);
        };
        return f;
    }
    return f;
}

process.stdin.on('data', splitLines().on(solveProblemLinePerLine))

Durante a execução, note que o programa para (devido ao process.exit(0)) quando é informado os casos de teste. Isso favorece o teste manual, ao executar o código, ele para no momento que se espera.

Exemplo da vida, o universo e tudo mais

Aqui, o código executa eternamente até o fim da entrada, por mais que chegue o 42 em algum momento:

let state = "GO";
function solveProblemLinePerLine(line) {
    if (line == "42") {
        state = "STOP";
    }
    if (state == "STOP") {
        return;
    }
    console.log(line);
}

// boilerplate abaixo!!

function splitLines() {
    let buff = "";
    let _action = (el) => {};
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            _action(atom)
        }
        buff = parts[parts.length - 1];
    }
    f.on = (action) => {
        const oldAction = _action;
        _action = (el) => {
            oldAction(el);
            action(el);
        };
        return f;
    }
    return f;
}

process.stdin.on('data', splitLines().on(solveProblemLinePerLine))

Usando o template: macaco prego

Bem, para usar o template, precisamos entender como ele funciona. Basicamente, para usar corretamente o modelo, precisamos pensar na máquina de estados e em como ela vai reagir às entradas.

Como motor de exemplo, vamos pegar a questão Macaco Prego. Basicamente aqui a entrada vai se dividir em dois blocos:

primeira linha: N, a quantidade de quadrados
próximas N linhas: descrições de quadrados

tl;dr da questão: ele precisa da interseção de todos os quadrados. Se não houver, imprimir nenhum. Os quadrados são definidos por quatro números: LEFT, TOP, RIGHT, BOTTOM.

Ah, o N pode ser 0 para indicar saída (na saída não se imprime nada).

Para cada caso de teste, a impressão deve ser Teste X, onde X é o número do teste sendo executado (começa do 1), seguido da interseção (ou nenhum) e seguido de uma linha em branco.

Bem, vamos analisar como resolver?

Basicamente, temos o estado INIT. Quando recebe 0, vamos para o estado de END. Caso contrário, vamos para as leituras. Aqui, a primeira leitura vou tratar como especial, pois precisamos da interseção e a interseção de todos os retângulos sempre vai ser uma parte do retângulo inicial. Então, vamos para o estado READ_0. Após essa leitura, contamos N-1 vezes a leitura no estado READ, após isso imprimimos a resposta e voltamos para o estado INIT.

Isso já deve dar um bom esqueleto para o solveProblemLinePerLine:

let state = "INIT";
let testNumber = 1;

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            leQuantidade(Number(line));
            if (quantidadeRestante == 0) {
                state = "END";
                process.exit(0);
            } else {
                state = "READ_0";
            }
            break;
        case "READ_0": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            state = "READ";
            break;
        }
        case "READ": {
            const [left, top, right, bottom] = line.split(" ");
            leituraInc(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            if (quantidadeRestante == 0) {
                imprimeResposta(testNumber);
                testNumber++;
                state = "INIT";
            }
            break;
        }
        case "END":
            process.exit(0);
            break;
    }
}

Vamos preencher as lacunas? Começar por leituraZero. Aqui, a melhor solução é preencher um objeto chamado intersec com o valor left, top, right, bottom, sem segredo:

let intersec = {};

function leituraZero(left, top, right, bottom) {
    intersec = { left, top, right, bottom }
}

Bem tranquilo, né? Bem, agora vamos na leitura incremental. Aqui, ao descobrir que a interseção é impossível, eu posso simplesmente sobrescrever o objeto intersec com o valor nenhum. Agora posso fazer uma tratativa especial para esse valor. De resto, se a nova esquerda estiver mais pra lá do que a velha esquerda, escolhe a nova. Vai ter uma tratativa dessas para cada um:

function leituraInc(left, top, right, bottom) {
    if (intersec == "nenhum") {
        // caso especial, precisa fazer nada
        return;
    }
    const leftR = Math.max(left, intersec.left);
    const topR = Math.min(top, intersec.top);
    const rightR = Math.min(right, intersec.right);
    const bottomR = Math.max(bottom, intersec.bottom);

    intersec = {
        left: leftR,
        top: topR,
        right: rightR,
        bottom: bottomR
    };
}

É isso? Bem, não, preciso validar antes se a interseção existe. Em que caso a interseção pode não existir? No caso em que a esquerda está depois da direita, ou que o topo está debaixo do fundo:

function leituraInc(left, top, right, bottom) {
    if (intersec == "nenhum") {
        // caso especial, precisa fazer nada
        return;
    }
    const leftR = Math.max(left, intersec.left);
    const topR = Math.min(top, intersec.top);
    const rightR = Math.min(right, intersec.right);
    const bottomR = Math.max(bottom, intersec.bottom);

    if (leftR > rightR || topR < bottomR) {
        intersec = "nenhum";
        return;
    }

    intersec = {
        left: leftR,
        top: topR,
        right: rightR,
        bottom: bottomR
    };
}

Finalmente, a impressão. Se for nenhum, só imprime o nenhum e seja feliz. Caso contrário, precisa imprimir left, top, right, bottom nessa ordem separado por espaços. E então uma linha em branco a mais:

function imprimeResposta() {
    console.log(`Teste ${testNumber}`);
    if (intersec == "nenhum") {
        console.log(intersec);
    } else {
        const { left, top, right, bottom } = intersec;
        console.log(`${left} ${top} ${right} ${bottom}`)
    }
    console.log();
}

É isso? Bem, na real esqueci de um caso. Se for informada apenas uma única área, a resposta vai ser exatamente a entrada, já que a interseção de todos os retângulos, quando tem somente um único retângulo, é ele mesmo. Posso lidar com isso como caso especial? Posso. Posso lidar com isso no READ_0? Posso.

Me parece mais trivial criar um caso especial: READ_UNICO!

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            leQuantidade(Number(line));
            if (quantidadeRestante == 0) {
                state = "END";
                process.exit(0);
            } else if (quantidadeRestante == 1) {
                state = "READ_UNICO";
            } else {
                state = "READ_0";
            }
            break;
        case "READ_UNICO": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            imprimeResposta(testNumber);
            testNumber++;
            state = "INIT";
            break;
        }
        case "READ_0": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            state = "READ";
            break;
        }
        case "READ": {
            const [left, top, right, bottom] = line.split(" ");
            leituraInc(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            if (quantidadeRestante == 0) {
                imprimeResposta(testNumber);
                testNumber++;
                state = "INIT";
            }
            break;
        }
        case "END":
            process.exit(0);
            break;
    }
}

Juntando tudo:

let state = "INIT";
let testNumber = 1;
let intersec = {};
let quantidadeRestante = 0;

function leQuantidade(quantidade) {
    quantidadeRestante = quantidade;
}

function leituraZero(left, top, right, bottom) {
    intersec = { left, top, right, bottom }
}

function leituraInc(left, top, right, bottom) {
    if (intersec == "nenhum") {
        // caso especial, precisa fazer nada
        return;
    }
    const leftR = Math.max(left, intersec.left);
    const topR = Math.min(top, intersec.top);
    const rightR = Math.min(right, intersec.right);
    const bottomR = Math.max(bottom, intersec.bottom);

    if (leftR > rightR || topR < bottomR) {
        intersec = "nenhum";
        return;
    }

    intersec = {
        left: leftR,
        top: topR,
        right: rightR,
        bottom: bottomR
    };
}

function imprimeResposta() {
    console.log(`Teste ${testNumber}`);
    if (intersec == "nenhum") {
        console.log(intersec);
    } else {
        const { left, top, right, bottom } = intersec;
        console.log(`${left} ${top} ${right} ${bottom}`)
    }
    console.log();
}

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            leQuantidade(Number(line));
            if (quantidadeRestante == 0) {
                state = "END";
                process.exit(0);
            } else if (quantidadeRestante == 1) {
                state = "READ_UNICO";
            } else {
                state = "READ_0";
            }
            break;
        case "READ_UNICO": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            imprimeResposta(testNumber);
            testNumber++;
            state = "INIT";
            break;
        }
        case "READ_0": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            state = "READ";
            break;
        }
        case "READ": {
            const [left, top, right, bottom] = line.split(" ");
            leituraInc(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            if (quantidadeRestante == 0) {
                imprimeResposta(testNumber);
                testNumber++;
                state = "INIT";
            }
            break;
        }
        case "END":
            process.exit(0);
            break;
    }
}

// boilerplate abaixo!!

function splitLines() {
    let buff = "";
    let _action = (el) => {};
    const f = (data) => {
        buff += data;
        const parts = buff.split("\n")

        for (const atom of parts.slice(0, -1)) {
            _action(atom)
        }
        buff = parts[parts.length - 1];
    }
    f.on = (action) => {
        const oldAction = _action;
        _action = (el) => {
            oldAction(el);
            action(el);
        };
        return f;
    }
    return f;
}

process.stdin.on('data', splitLines().on(solveProblemLinePerLine))

E... voi là! Estamos prontos! Vamos submeter!

E claro que agora eu descubro que o Spoj não aceita Node para essa questão em específico! Triste...

Mas, sabe o que ele aceita? SpiderMonkey JS! Vamos lá!

Quais são as transformações a serem feitas? Bem, para começar, não temos a leitura daquele jeito. A leitura da linha é uma função chamada readline() que devolve uma linha lida (ou null se chegar no final da stream, o que não acontece aqui porque para sair se informa 0).

Além disso, o console.log é substituído por print. E finalmente não tem o process.exit(0). No lugar, vou coloar um loop de leitura infinita até o estado ser END, aí para a execução:


let state = "INIT";
let testNumber = 1;
let intersec = {};
let quantidadeRestante = 0;

function leQuantidade(quantidade) {
    quantidadeRestante = quantidade;
}

function leituraZero(left, top, right, bottom) {
    intersec = { left, top, right, bottom }
}

function leituraInc(left, top, right, bottom) {
    if (intersec == "nenhum") {
        // caso especial, precisa fazer nada
        return;
    }
    const leftR = Math.max(left, intersec.left);
    const topR = Math.min(top, intersec.top);
    const rightR = Math.min(right, intersec.right);
    const bottomR = Math.max(bottom, intersec.bottom);

    if (leftR > rightR || topR < bottomR) {
        intersec = "nenhum";
        return;
    }

    intersec = {
        left: leftR,
        top: topR,
        right: rightR,
        bottom: bottomR
    };
}

function imprimeResposta() {
    print(`Teste ${testNumber}`);
    if (intersec == "nenhum") {
        print(intersec);
    } else {
        const { left, top, right, bottom } = intersec;
        print(`${left} ${top} ${right} ${bottom}`)
    }
    print();
}

function solveProblemLinePerLine(line) {
    switch (state) {
        case "INIT":
            leQuantidade(Number(line));
            if (quantidadeRestante == 0) {
                state = "END";
                return;
            } else if (quantidadeRestante == 1) {
                state = "READ_UNICO";
            } else {
                state = "READ_0";
            }
            break;
        case "READ_UNICO": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            imprimeResposta(testNumber);
            testNumber++;
            state = "INIT";
            break;
        }
        case "READ_0": {
            const [left, top, right, bottom] = line.split(" ");
            leituraZero(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            state = "READ";
            break;
        }
        case "READ": {
            const [left, top, right, bottom] = line.split(" ");
            leituraInc(Number(left), Number(top), Number(right), Number(bottom));
            quantidadeRestante--;
            if (quantidadeRestante == 0) {
                imprimeResposta(testNumber);
                testNumber++;
                state = "INIT";
            }
            break;
        }
        case "END":
            break;
    }
}

// boilerplate abaixo!!

while (state != "END") {
    const linha = readline();
    solveProblemLinePerLine(linha);
}

Beleza, aparentemente agora lembra o que o SpiderMonkey aceita. Agora, que tal antes validar? Felizmente descobri um sandbox online para experimentar: https://mozilla-spidermonkey.github.io/sm-wasi-demo/.

Mas, bem, roda no browser, né? Não aceita bem o readline, como comportar? Ora, ora, ora... lembra ainda antes de implementar o loop em cima do process.stdin.on('data', ...)? Que testamos passando as strings linha a linha para a função solveProblemLinePerLine? Façamos isso! No lugar do loop de leitura do boilerplate:

const linhas = [
    "3",
    "0 6 8 1",
    "1 5 6 3",
    "2 4 9 0",
    "3",
    "0 4 4 0",
    "3 1 7 -3",
    "6 4 10 0",
    "0"
]

for (const linha of linhas) {
    //const linha = readline();
    solveProblemLinePerLine(linha);
}

Só como teste de sanidade mesmo, e funcionou. Vamos submeter?

Bem, a submissão foi com suceso. O boilerplate funciona, e adaptar ele para SpiderMonkey também deu certo.

Nota sobre leitura de dados vs programação competitiva

Particularmente eu estou bem mais acostumado com ter domínio do fluxo do programa quando estou em uma questão de programação competitiva. No lugar de definir uma máquina de estados manualmente, eu simplesmente deixo o código fazer isso diretamente. Por exemplo, seria muito mais natural fazer assim:

function calculaIntersec(intersec, left, top, right, bottom) {
    if (intersec == "nenhum") {
        // caso especial, precisa fazer nada
        return "nenhum";
    }
    const leftR = Math.max(left, intersec.left);
    const topR = Math.min(top, intersec.top);
    const rightR = Math.min(right, intersec.right);
    const bottomR = Math.max(bottom, intersec.bottom);

    if (leftR > rightR || topR < bottomR) {
        return "nenhum";
    }

    return {
        left: leftR,
        top: topR,
        right: rightR,
        bottom: bottomR
    };
}

function resolveProblema(quantidadeRestante) {
    let intersec;
    let [left, top, right, bottom] = readline().split(" ");
    intersec = { left, top, right, bottom };
    quantidadeRestante--;

    while (quantidadeRestante > 0) {
        [left, top, right, bottom] = readline().split(" ");

        intersec = calculaIntersec(intersec, left, top, right, bottom);
        quantidadeRestante--;
    }
    return intersec;
}

function imprimeResposta(intersec, testNumber) {
    print(`Teste ${testNumber}`);
    if (intersec == "nenhum") {
        print(intersec);
    } else {
        const { left, top, right, bottom } = intersec;
        print(`${left} ${top} ${right} ${bottom}`)
    }
    print();
}

let testNumber = 1;
while (true) {
    const quantidadeRestante = Number(readline())
    if (quantidadeRestante == 0) {
        break;
    }
    const intersec = resolveProblema(quantidadeRestante);
    imprimeResposta(intersec, testNumber);
    testNumber++;
}

Aqui tá muito mais direto, a "máquina de estados" agora é o while (true) no programa, tenho muito mais controle da submissão, consigo controlar muito melhor como eu faço a leitura. Mas, bem, o ponto era mostrar o boilerplate em Node, e isso foi demonstrado que funciona. E que é possível adaptar para rodar com SpiderMonkey em cima da mesma mentalidade.

Estou estudando isso aqui, recursão e otimização de função de cauda

Jefferson Quesado — Thu, 07 Aug 2025 22:51:45 +0000

Leandro Proença

Jun 23 '23

Entendendo fundamentos de recursão

#programming #ruby #braziliandevs

Comments 5

7 min read

Sobre operações comutativas e associativas

Jefferson Quesado — Sat, 10 May 2025 18:18:20 +0000

Alexandre Pierre for cataploft

May 10 '25

Comutativa Não-Associativa e Associativa Não-Comutativa

#computerscience #learning

Comments

3 min read

Fazendo um proxy reverso em Go

Jefferson Quesado — Wed, 19 Mar 2025 00:41:19 +0000

Vamos fazer um proxy reverso em Gox?

Objetivos

Recebe e envia HTTP 1.1
Não se preocupa com método de requisição
- Por exemplo, GET não tem body
- Métodos HTTP fora do standard (MKCOL, por exemplo, ou QUERY, futuro)
Não fazer buffer a priori de todo o body antes de fazer a requisição
reencaminhar parte significativa do PATH
Zero dependências externas

Hello world

Existem algumas maneiras para se estabelecer um servidor em Go para servir conexões HTTP. As mais simples dela envolvem o server padrão, o DefaultServerMux.

Basicamente, você simplesmente pede para manusear a chamada HTTP, e pode ser de dois jeitos:

http.HandleFunc: aqui você só passa uma função que vai lidar com suas questões
http.Handle: aqui você passa um objeto que possui o método público ServeHTTP adequado para a interface http.Handler

Depois de você pedir para o servidor HTTP lidar com as requisições passando o handler, você precisa criar um tipo adequado. Por exemplo, adaptado da documentação:

package main

import (
    "fmt"
    "html"
    "log"
    "net/http"
)

type hello struct {
}

func (s hello) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "Hello, %q\n", html.EscapeString(r.URL.Path))
}

func main() {
    fooHandler := hello{}
    http.Handle("/oie", fooHandler)

    log.Fatal(http.ListenAndServe(":8080", nil))
}

Go até aceita que você cria structs anônimas, e pode atribuir a elas campos como funções. Mas nesse caso aqui uma interface não espera um campo (diferente de uma interface no TS), mas sim métodos:

package main

import (
    "fmt"
    "html"
    "log"
    "net/http"
)

func main() {

    fooHandler2 := struct{
        ServeHTTP func (w http.ResponseWriter, r *http.Request)
    } {
        func (w http.ResponseWriter, r *http.Request) {
            fmt.Fprintf(w, "Hello, %q\n", html.EscapeString(r.URL.Path))
        },
    }
    http.Handle("/oie", fooHandler2)

    log.Fatal(http.ListenAndServe(":8080", nil))
}

Isso gera esse erro:

Escutar e servir

Após adicionar os http.Handle ou http.HandleFunc, pedir por http.ListenAndServe irá levantar o servidor na porta adequada.

Claro que você também tem a opção de prover a sua própria implementação do servidor HTTP, não restrito ao DefaultServerMux. Por exemplo:

s := &http.Server{
    Addr: ":8080", 
    //... params
}

log.Fatal(s.ListenAndServe())

Então, temos este "endereço". Que no http.ListenAndServe é passado como parâmetro, já no (*http.Server) ListenAndServe é um campo de http.Server. Ele serve para indicar o quê, afinal?

Além de indicar a porta, ele também indica como o servidor pode ser acessado. Por exemplo:

log.Fatal(http.ListenAndServe(":8080", nil))

Torna o servidor acessível através do meu celular, na mesma rede:

Porém, uma pequena mudança torna isso inacessível:

E qual foi a mudança que fez isso? Simplesmente colocar como o endereço localhost:8080:

log.Fatal(http.ListenAndServe("localhost:8080", nil))

Isso serve para fechar o servidor a escutar uma requisição pelo endereço usado para identificar o servidor. Colocar o algo antes da porta, eu impeço que seja escutado quando a requisição não chega usando o DNS adequado.

Uma revisão em HTTP

Recentemente escrevi um post sobre HTTP, mas o foco da postagem foi mais uma pegada geral sobre solução de problemas e estratégia de estudo. Em breve retornarei a escrever sobre HTTP em minúncias, especificando o que implementei e como.

Uma mensagem HTTP é basicamente dividida em duas partes:

uma requisição
uma resposta

Ambas as partes da mensagem HTTP1.1 são divididas, em grosso modo, da mesma maneira:

uma primeira linha (aqui requisição e resposta são absurdamente distintas)
headers (até uma linha em branco)
body
headers de fim (apenas para chunked encoding, omitido na explicação abaixo)

Na requisição, a primeira linha consiste das seguintes partes (separadas por espaço):

método
path
protocolo

Por exemplo:

GET /oie HTTP/1.1

Isso significa que o agente (normalmente o navegador) está requisitando com GET a página de caminho /oie para o servidor, usando o protocolo HTTP/1.1 (que eu grafei anteriormente como HTTP1.1, mas aqui é mais estrito o uso).

Isso serve para diferenciar, por exemplo, de quando a requisição é o clássico HTTP/1.0. Para simplesmente receber uma requisição de modo similar ao HTTP 1.X, o HTTP2 usa como primeira linha:

PRI * HTTP/2.0

Que não tem nenhuma semântica. HTTP2 usa outra estratégia para as informações de requisição, nominalmente chamdas de pseudo-header :method e :path.

Após essa linha, vem os headers. Um header tem pela RFC um jeito bem flexível de ser declarado, mas costumeiramente é contido em uma linha (inclusive descobri escrevendo este post que um header ocupando diversas linhas foi marcado como deprecado na RFC 7230).

Basicamente, um header tem o seguinte formato:

header: value

E o header pode aparecer várias vezes durante a listagem:

header1: value
header2: value for 2
header1: other value for 1

No caso de envios "repetidos" de headers, o recipiente da mensagem precisa interpretar como se fosse uma lista continuada, algo mais ou menos assim:

{
    header1: ["value", "other value for 1"],
    header2: "value for 2"
}

ou assim:

{
    header1: "value, other value for 1",
    header2: "value for 2"
}

E como se chega no final dos headers? Com uma linha em branco. Após a linha em branco, se tiver alguma mensagem para ser enviada, ela estará presente.

Então, após a linha em branco, vemos o corpo. E o modo como o corpo será transportado vai ter algumas características próprias. Basicamente, as 3 estratégias são:

tamanho conhecido
chunked
multipart boundary

O envio de tamanho conhecido é basicamente informar que vai enviar N bytes e enviar esses N bytes. O chunked é enviar em pequenos pedaços, em chunks, indicando um chunk especial de tamanho 0, similar ao caracter nulo que termina strings em C. Em transferências multipart, é usado o limitador (boundary) para separar uma parte de outra, e um indicador no boundary é usado para indicar o final da mensagem, mas transferências multipart são usadas dentro do contexto de tamanho conhecido, sendo os boundaries computados para o tamanho total do conteúdo.

E, bem, e quanto à resposta do HTTP? Basicamente tudo que foi dito continua válido para a resposta, mas aqui precisamos distinguir uma coisa: a primeira linha.

Enquanto que na requisição a primeira linha consistia de método, caminho e protocolo, aqui a primeira linha consiste de 3 partes:

protocolo
código de status
uma razão

Na prática, a razão muitas vezes é um mnemônico relativo ao status code. Por exemplo, 200 OK.

Headers especiais

Meu foco é HTTP 1.1. E ele possui alguns headers especiais que fazem parte do protocolo, ou de negociação de conteúdo. Alguns desses headers já foram aludidos:

Content-length
Transfer-encoding

O Content-length vai indicar o tamanho do conteúdo sendo trafegado, exceto se for usado Transfer-encoding: chunked, onde o tamanho não é determinado priori e se precisa usar uma estratégia de streaming específica.

Outro header que pode alterar o como as coisas são transferidas é o Content-type, quando o tipo é multipart/*. Nesse caso, é usada uma estratégia de streaming própria. Mas, as partes relativas ao boundary são partes inerentes da transferência, computado no tamanho total. Portanto, posso ignorar totalmente isso e considerar apenas como um grande transporte.

Outro header especial é a requisição Connection: keep-alive. Basicamente isso quer dizer que o cliente quer manter a conexão aberta, inclusive isso foi utilizado para resolver problemas de performance web, vide O dia em que precisei estudar HTTP, para otimizar a aplicação.

Junto do connection: keep-alive da requisição, temos o connection: closed da resposta. Isto é definido salto a salto, então este header não precisa ser repassado adiante, apenas gerenciado internamente.

Devido a questões de virtual servers e uso da mesma máquina para responder diversas requisições, também tem a questão de enviar o Host como header mandatório.

O header TE tem a particularidade no contexto da requisição. Ao ser usado o valor trailers, indica que o cliente aceita receber headers após o body. Então, como eu não quero lidar com isso, vou tratar de suprimir esse valor.

Tem também o Forwarded, indicado para proxies que querem permitir que o servidor que está recebendo a requisição saiba de onde ela partiu, para a partir disso podeer tomar alguma decisão. Normalmente essa informação é injetada pelo agente de proxy (RFC 7239).

Lista de headers

Content-length
Transfer-encoding
- Valor: chunked
Connection
- Valor: keep-alive, close
Host
TE: trailers
Forwarded
- injetado pelo proxy

Como funciona em Go? Servidor

Vamos começar com a requisição. Não precisamos nos preocupar exatamente com o como as informações são empacotadas, e como é a requisição não preciso nem me preocupar na ordem em que elas são apresentadas.

Em Go, usando o servidor HTTP padrão provido pela linguagem, eu posso simplesmente encaminhar a requisição. Para isso eu preciso ter um cliente HTTP, mas isso será visto mais tarde. Preciso me atentar a algumas coisas na hora de passar a requisição adiante:

devo ignorar totalmente a questão do Connection, isso é algo salto a salto
lidar corretamente com o streaming de dados chunked
header de Host adequado para o encaminhamento

Além disso, a RFC sugere fortemente o Forwarded ao usar proxies, para que o server ainda tenha condição de saber quem fez a requisição original.

Além disso, vem bem a calhar a suprimir TE: trailers. Ou então lidar com isso, mas agora parece uma complicação opcional a mais. Quem sabe um outro momento?

Como servidor, eu tenho acesso ao cmapo request.Body, que implementa a interface io.Reader. E posso usar o método Read dele. Exemplificando uma leitura completa:

body := r.Body

size := 0
buffer := make([]byte, 512*1024)
completo := make([]byte, 0)

for {
    n, err := body.Read(buffer)

    fmt.Printf("leitura parcial <%s>\n", string(buffer[:n]))

    if n > 0 {
        completo = append(completo, buffer[:n]...)
        size += n
    }
    if err == io.EOF {
        break
    }
    if err != nil {
        return
    }
}
fmt.Printf("body completo <%q>\n", string(completo))

Adaptado de Golang Cafe

Basicamente a ideia é ler em um buffer até que nenhum byte mais esteja presente. A leitura vai ocorrer até que err == EOF, situação em que Go indica final da leitura.

No meu caso, eu fiquei concatenando a leitura no slice completo. Para fazer isso corretamente, eu preciso chamar append(slice, elements...). Mas o buffer que estou guardando as coisas é um slice, não um .... Como resolver isso? Usando o spread: completo = append(completo, buffer[:n]...). Adaptei desta resposta no StackOverflow. O Geeks for Geeks oferece também algumas estratégias de fazer a cópia de um slice em outro, e explica alguns detalhes no caminho, How to copy one slice into another slice in Golang. Note que não pego buffer inteiro, apenas a parte que foi lida de buffer, que é o slice buffer[:n].

Fazendo uma leitura enviando 5 bytes por vez, com o corpo tralala, obtive esses logs:

leitura parcial <trala>
leitura parcial <la>
e aí? body <"tralala">

Para pegar o método, eu posso pedir para a requisição r.Method. Ele retorna até métodos fora do convencional. Por exemplo, você pode pedir para o curl fazer uma requisição HTTP usando um método totalmente inovador usando a opção de CLI -X método. No caso, testei com -X PRRRR, gerando o método PRRRR.

Já na hora de escrever a resposta eu preciso me preocupar. Para escrever:

protocolo + status + razão
headers
body

O protocolo vai ser inserido automaticamente pela biblioteca padrão, então preciso de uma alternativa para o código de status HTTP. E o ResponseWriter tem uma alternativa pra isso. Por exemplo, simulando um status de Forbidden:

w.WriteHeader(http.StatusForbidden)

O cuidado a se tomar é que chamar isto deve ser a primeira coisa. Logo depois, vem os headers. Certo isso? Bem... descobri que não. Da documentação de ResponseWriter.Header():

Header returns the header map that will be sent by ResponseWriter.WriteHeader. The Header map also is the mechanism with which Handler implementations can set HTTP trailers.

Changing the header map after a call to ResponseWriter.WriteHeader (or ResponseWriter.Write) has no effect unless the HTTP status code was of the 1xx class or the modified headers are trailers.

Ou seja: os headers vão ser escritos junto do status com WriteHeader.

Usando o exemplo acima, para fazer uma transmissão com Transfer-Encoding: chunked:

w.Header().Add("transfer-encoding", "chunked")
w.WriteHeader(http.StatusForbidden)

w.Write([]byte("lalala\n"))
w.Write([]byte("lelele\n"))
w.Write([]byte("lilili\n"))
fmt.Fprintf(w, "Hello, %q\n", html.EscapeString(r.URL.Path))

Fazendo a leitura em curl:

> curl localhost:8080/oie -v -X PRRRR -d "tralala"
* Host localhost:8080 was resolved.
* IPv6: ::1
* IPv4: 127.0.0.1
*   Trying [::1]:8080...
* Connected to localhost (::1) port 8080
> PRRRR /oie HTTP/1.1
> Host: localhost:8080
> User-Agent: curl/8.7.1
> Accept: */*
> Content-Length: 7
> Content-Type: application/x-www-form-urlencoded
> 
* upload completely sent off: 7 bytes
< HTTP/1.1 403 Forbidden
< Date: Tue, 18 Mar 2025 02:56:14 GMT
< Transfer-Encoding: chunked
< 
lalala
lelele
lilili
Hello, "/oie"
* Connection #0 to host localhost left intact

Hmmm, mas isso não me dá a visão dos chunks. Uma resposta do próprio Bagder indica como obter os chunks, só usar --raw:

> curl localhost:8080/oie -v -X PRRRR -d "tralala" --raw
* Host localhost:8080 was resolved.
* IPv6: ::1
* IPv4: 127.0.0.1
*   Trying [::1]:8080...
* Connected to localhost (::1) port 8080
> PRRRR /oie HTTP/1.1
> Host: localhost:8080
> User-Agent: curl/8.7.1
> Accept: */*
> Content-Length: 7
> Content-Type: application/x-www-form-urlencoded
> 
* upload completely sent off: 7 bytes
< HTTP/1.1 403 Forbidden
< Date: Tue, 18 Mar 2025 02:56:14 GMT
< Transfer-Encoding: chunked
< 
23
lalala
lelele
lilili
Hello, "/oie"

0

* Connection #0 to host localhost left intact

Hmmm, não mandou chunks pequenos... e se eu quiser chunks pequenos? Bem, segundo esta resposta, o ResponseWriter que nos é informado normalmente também implementa http.Flusher. Posso usar o casting para esse fim:

flusher := w.(http.Flusher)

Ou então daria para também se preparar no caso de não ser um http.Flusher:

type fakeflusher struct {
}

func (f fakeflusher) Flush() {
}

flusher, ok := w.(http.Flusher)

if !ok {
    fmt.Println("response not a flusher")
    flusher = fakeflusher{}
}

E aqui estou garantindo que eu possa sempre chamara os métodos de Flush(), pois estou criando um objeto que implementa a interface http.Flusher, afinal ele é da struct fakeFlusher.

Com o flusher em mãos, podemos pedir para que ele dê um flush no que tá retido:

w.Header().Add("transfer-encoding", "chunked")
w.WriteHeader(http.StatusForbidden)

w.Write([]byte("lalala\n"))
flusher.Flush()
w.Write([]byte("lelele\n"))
flusher.Flush()
w.Write([]byte("lilili\n"))
flusher.Flush()

fmt.Fprintf(w, "Hello, %q\n", html.EscapeString(r.URL.Path))

E isso me dá a seguinte chamada curl:

> curl localhost:8080/oie -v -X PRRRR -d "tralala" --raw
* Host localhost:8080 was resolved.
* IPv6: ::1
* IPv4: 127.0.0.1
*   Trying [::1]:8080...
* Connected to localhost (::1) port 8080
> PRRRR /oie HTTP/1.1
> Host: localhost:8080
> User-Agent: curl/8.7.1
> Accept: */*
> Content-Length: 7
> Content-Type: application/x-www-form-urlencoded
> 
* upload completely sent off: 7 bytes
< HTTP/1.1 403 Forbidden
< Date: Tue, 18 Mar 2025 02:56:14 GMT
< Transfer-Encoding: chunked
< 
7
lalala

7
lelele

7
lilili

e
Hello, "/oie"

0

* Connection #0 to host localhost left intact

E agora foi possível perceber perfeitamente a separação em cada um dos chunks transferido, e o chunk terminador de tamanho 0.

Como funciona em Go? Cliente

Para criar uma conexão, a documentação indica usar http.NewRequest e adicionar headers usando req.Header.Add():

req, err := http.NewRequest("GET", "http://example.com", nil)
//                           método                      reader do body
//                                  url alvo da API
req.Header.Add("Header", "value for header")

Para fazer uma requisição completamente arbitrária, é preciso criar um http.Client, e também na documentação ele cita sobre passar o net.Transport para construir o client:

tr := &http.Transport{
    MaxIdleConns:       10,
    IdleConnTimeout:    30 * time.Second,
    DisableCompression: true,
}
client := &http.Client{Transport: tr}

E a requisição é um simples client.Do(req). Por exemplo, para fazer uma chamada para o Computaria em ambiente de desenvolvimento:

tr := &http.Transport{
    MaxIdleConns:       10,
    IdleConnTimeout:    30 * time.Second,
    DisableCompression: true,
}
client := &http.Client{Transport: tr}

func fullRead(r io.Reader) (string, error) {
    size := 0
    buffer := make([]byte, 512*1024)
    completo := make([]byte, 0)

    for {
        fmt.Println("entrando na leitura")
        n, err := r.Read(buffer)

        fmt.Printf("leitura parcial %s\n", string(buffer[:n]))

        if n > 0 {
            completo = append(completo, buffer[:n]...)
            size += n
        }
        if err == io.EOF {
            break
        }
        if err != nil {
            return string(completo), err
        }
    }
    return string(completo), nil
}

req, err := http.NewRequest("GET", "http://localhost:4000/blog/", nil)
if err != nil {
    fmt.Println("deu ruim criando a req")
    return
}
rcvd, err := client.Do(req)
if err != nil {
    fmt.Println("deu ruim lendo a resposta")
    return
}
str, err := fullRead(rcvd.Body)
if err != nil {
    fmt.Println("não leu tudo, portencialmente", str)
    return
}
fmt.Print(str)

E voi là, a página foi escrita no console.

Escrevendo o proxy

Como o Computaria está todo pronto para responder usando como primeiro caminho /blog, vou manter isso no meu proxy. Reescrever essa parte seria bem complicado, pois envolveria ou interceptar a resposta e identificar os links dentro da resposta ou tornar o blog aware de que responderia com outra path base.

O proxy vai implementar http.Handler. Vai bem a calhar que o proxy tenha 3 atributos:

o prefixo que ele vai servir (no caso, /blog/)
o endereço que vai bater (no caso, http://localhost:4000/blog/)
um cliente HTTP já montado

Assim, temos a estrutura proxy definida assim:

type proxy struct {
    client  *http.Client
    target  string
    preffix string
}

tr := &http.Transport{
    MaxIdleConns:       10,
    IdleConnTimeout:    30 * time.Second,
    DisableCompression: true,
}
client := &http.Client{Transport: tr}

proxyHandler := proxy{client, "http://localhost:4000/blog/", "/blog/"}
http.Handle("/blog/", proxyHandler)

log.Fatal(http.ListenAndServe(":8080", nil))

Ok, agora preciso definir como lidar com a requisição. De modo geral, vou pegar as coisas de uma requisição recebida e escrever na requisição a ser feita. Isso inclui método, path (após o prefixo), body, etc. No caso de headers que preciso tomar um pouco de cuidado: quero poder ignorar headers de trailer (portanto vou remover o TE: trailers quando presente), e preciso ignorar Connection e também Host.

É de bom tom adicionar o Forwarded. Na requisição tem o campo r.RemoteAddr, que traz o endereço de quem se conectou e também a porta utilizada. Segundo a especificação, essa porta não é relevante, então preciso limpar ela:

func noPort(remoteAddr string) string {
    for idx, c := range remoteAddr {
        if c == ':' {
            return remoteAddr[:idx]
        }
    }
    return remoteAddr
}

A estratégia que usei para limpar a porta foi iterar até encontrar o :. A iteração do tipo "for-each" em uma string, ou vetor, ou slice, é feita usando o range value, com o primeiro elemento retornado sendo o índice e o segundo elemento o valor em si. No caso acima, idx é o índice e c o caracter da string. Ao localizar o :, pego um "slice" da string até aquele índice. Ou na ausência, retorna o que recebeu.

Para iterar um mapa usamos também o range mapValue, mas a diferença é que, no lugar do primeiro elemento ser um índice, ele é a chave do mapa, e o segundo elemento é o valor associado àquela chave. Isso é bom para iterar nos headers:

for reqHeader, value := range r.Header {
    fmt.Println(reqHeader, value)

    if strings.ToLower(reqHeader) == "connection" || strings.ToLower(reqHeader) == "host" {
        continue
    }
    if strings.ToLower(reqHeader) == "te" {
        valueClean := []string{}
        for _, teValue := range value {
            if strings.ToLower(teValue) == "trailers" {
                continue
            }
            valueClean = append(valueClean, teValue)
        }
        if len(valueClean) == 0 {
            continue
        }
        value = valueClean
    }
    req.Header.Add(reqHeader, strings.Join(value, ", "))
}
req.Header.Add("Forwarded", "for="+noPort(r.RemoteAddr))

A criação da requisição é bem direta, basicamente encaminhando o que veio do cliente:

reqPath := r.URL.Path

relevantPath := reqPath[len(s.preffix):]
req, err := http.NewRequest(r.Method, s.target+relevantPath, r.Body)

A única adaptação feita é a questão de que o relevantPath é computado de acordo com o path da requisição e o prefixo do proxy.

Então, depois de toda essa informação extraída, mandamos a conexão e copiamos os headers da resposta (com exceção do Connection):

rcvd, err := s.client.Do(req)
if err != nil {
    fmt.Println("deu ruim lendo a resposta")
    return
}
for responseHeader, value := range rcvd.Header {
    fmt.Println(responseHeader, value)
    if strings.ToLower(responseHeader) == "connection" {
        continue
    }
    w.Header().Add(responseHeader, string(strings.Join(value, ", ")))
}
w.WriteHeader(rcvd.StatusCode)
io.Copy(w, rcvd.Body)

O código inteiro fica assim:

package main

import (
    "fmt"
    "io"
    "log"
    "net/http"
    "strings"
    "time"
)

type proxy struct {
    client  *http.Client
    target  string
    preffix string
}

func (s proxy) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    reqPath := r.URL.Path
    fmt.Println(reqPath)

    relevantPath := reqPath[len(s.preffix):]
    fmt.Println(relevantPath)
    req, err := http.NewRequest(r.Method, s.target+relevantPath, r.Body)
    if err != nil {
        fmt.Println("deu ruim criando a req")
        return
    }

    for reqHeader, value := range r.Header {
        fmt.Println(reqHeader, value)

        if strings.ToLower(reqHeader) == "connection" || strings.ToLower(reqHeader) == "host" {
            continue
        }
        if strings.ToLower(reqHeader) == "te" {
            valueClean := []string{}
            for _, teValue := range value {
                if strings.ToLower(teValue) == "trailers" {
                    continue
                }
                valueClean = append(valueClean, teValue)
            }
            if len(valueClean) == 0 {
                continue
            }
            value = valueClean
        }
        req.Header.Add(reqHeader, strings.Join(value, ", "))
    }
    req.Header.Add("Forwarded", "for="+noPort(r.RemoteAddr))

    fmt.Println(req.Header)
    fmt.Println()

    rcvd, err := s.client.Do(req)
    if err != nil {
        fmt.Println("deu ruim lendo a resposta")
        return
    }
    for responseHeader, value := range rcvd.Header {
        fmt.Println(responseHeader, value)
        if strings.ToLower(responseHeader) == "connection" {
            continue
        }
        w.Header().Add(responseHeader, string(strings.Join(value, ", ")))
    }
    w.WriteHeader(rcvd.StatusCode)
    io.Copy(w, rcvd.Body)
}

func noPort(remoteAddr string) string {
    for idx, c := range remoteAddr {
        if c == ':' {
            return remoteAddr[:idx]
        }
    }
    return remoteAddr
}

func main() {
    fmt.Println("olá")

    tr := &http.Transport{
        MaxIdleConns:       10,
        IdleConnTimeout:    30 * time.Second,
        DisableCompression: true,
    }
    client := &http.Client{Transport: tr}

    proxyHandler := proxy{client, "http://localhost:4000/blog/", "/blog/"}
    http.Handle("/blog/", proxyHandler)

    log.Fatal(http.ListenAndServe(":8080", nil))
}

[Boost]

Jefferson Quesado — Sun, 16 Feb 2025 20:21:14 +0000

Acho que podemos deixar o mobile first em 2024

Camilo Micheletto ・ Feb 15

#discuss #css #webdev #braziliandevs

Criando projeto Maven com profiles distintos de dependências

Jefferson Quesado — Fri, 31 Jan 2025 16:05:52 +0000

No trabalho tivemos um problema com a GraalVM, e devido a isso essa issue foi criada.

Eu falei com o autor e pensei "será que não seria melhor criar um projeto maven com isso bonitinho? Subir um repo, MCVE, que você controla através de profiles as dependências?"

E cá está o repo! github.com/jeffque/graalvm-regression

Pois bem, aproveitar que vou fazer isso e compartilhar um pouco o processo.

Iniciando um projeto maven

Para começar, eu gosto de iniciar o projeto maven colocar o mvnw (maven wrapper). Eu normalmente começo copiando o mvnw de um outro repositório meu conhecido, mas posso fazer isso de modo mais canônico. Como por exemplo, seguindo esse tutorial do Baeldung:

$ mvn -N wrapper:wrapper

Ficou assim o diretório:

.
├── .mvn
│   └── wrapper
│       └── maven-wrapper.properties
├── mvnw
└── mvnw.cmd

Qual a versão do maven que ele usa? Podemos perguntar diretamente ao mvwn ou então consultar em .mvn/wrapper/maven-wrapper.properties. No caso, o conteúdo do arquivo é:

# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.
distributionType=only-script
distributionUrl=https://repo.maven.apache.org/maven2/org/apache/maven/apache-maven/3.9.9/apache-maven-3.9.9-bin.zip

Muito bem, maven na versão 3.9.9, uma delícia.

Criando o projeto base

Existem diversas maneiras de iniciar um projeto maven. Inclusive a de você
o pom.xml totalmente do zero. Mas... um modo mais canônico seria pedir um
arquétipo, que nem eu fiz em "Hello, World!" em GWT usando arquétipo do TBroyer.

Então, vamos pedir o arquétipo vazio? Normalmente eu peço o maven-archetype-quickstart. Tem uma lista não exaustiva de arquétipos aqui.

./mvnw archetype:generate -DarchetypeGroupId=org.apache.maven.archetypes -DarchetypeArtifactId=maven-archetype-quickstart -DarchetypeVersion=1.5

Após baixar as dependências necessárias para rodar o arquétipo ele me pergunta:

Define value for property 'groupId'
- com.jeffque
Define value for property 'artifactId'
- graalvm-24-1-2-regression
Define value for property 'version' 1.0-SNPASHOT
- <enter> (o que é equivalente a usar o default, que no caso é 1.0-SNAPSHOT)
Define value for property 'package' com.jeffque:
- <enter> (o que é equivalente a usar o default, que no caso é com.jeffque)

Após responder, ele pede para confirmar:

Define value for property 'package' com.jeffque: 
Confirm properties configuration:
javaCompilerVersion: 17
junitVersion: 5.11.0
groupId: com.jeffque
artifactId: graalvm-24-1-2-regression
version: 1.0-SNAPSHOT
package: com.jeffque
 Y:

Confimei e... puff!

.
├── .mvn
│   └── wrapper
│       └── maven-wrapper.properties
├── graalvm-24-1-2-regression
│   ├── .mvn
│   │   ├── jvm.config
│   │   └── maven.config
│   ├── pom.xml
│   └── src
│       ├── main
│       │   └── java
│       │       └── com
│       │           └── jeffque
│       │               └── App.java
│       └── test
│           └── java
│               └── com
│                   └── jeffque
│                       └── AppTest.java
├── mvnw
└── mvnw.cmd

Gerei no canto errado? Ok, só mover uma pasta pra lá

←\leftarrow

cd graalvm-24-1-2-regression
mv pom.xml src ../
mv .mvn/* ../.mvn
rmdir .mvn
cd ..
rmdir graalvm-24-1-2-regression

Ok, ajeitado:

.
├── .mvn
│   ├── jvm.config
│   ├── maven.config
│   └── wrapper
│       └── maven-wrapper.properties
├── mvnw
├── mvnw.cmd
├── pom.xml
└── src
    ├── main
    │   └── java
    │       └── com
    │           └── jeffque
    │               └── App.java
    └── test
        └── java
            └── com
                └── jeffque
                    └── AppTest.java

Adicionando comando de execução

Eu quero facilitar a vida de quem vai testar usando Maven. Para tal, vou configurar o plugin exec. O plugin é esse: exec-maven-plugin.

Na linha de comando:

> ./mvnw exec:java -Dexec.mainClass="com.jeffque.App"
[INFO] Scanning for projects...
[INFO] 
[INFO] ---------------< com.jeffque:graalvm-24-1-2-regression >----------------
[INFO] Building graalvm-24-1-2-regression 1.0-SNAPSHOT
[INFO]   from pom.xml
[INFO] --------------------------------[ jar ]---------------------------------
[INFO] 
[INFO] --- exec:3.5.0:java (default-cli) @ graalvm-24-1-2-regression ---
Hello World!
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  0.383 s
[INFO] Finished at: 2025-01-31T08:02:13-03:00
[INFO] ------------------------------------------------------------------------

Beleza, vamos por no pom? Em pluginManagement a gente indica commo o plugin vai ser executado ao ser chamado, não necessariamente ele será chamado. Então, se eu adicionar o exec-maven-plugin lá, o maven não tentará fazer o fetch desse plugin a priori. Já em build.plugins... aí a gente está indicando que o plugin será de fato executado.

Aí vem a questão: quando usar algo em build.plugins? Quando precisamos que o plugin seja executado e não tem implícito em algum lugar isso. Como por exemplo, chamar o retrolambda para permitir usar a sintaxe de lambdas e conseguir dar um target para java 7.

Ok, vamos adicionar as configurações do plugin em pluginManagement? Primeiramente, vamos colocar o plugin lá:

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>exec-maven-plugin</artifactId>
    <version>3.5.0</version>
</plugin>

Ok, prendemos a versão. Agora, vamos para o como vai ser chamado. No caso, quando for chamado o mojo exec:java: exec identifica esse plugin e java o goal específico:

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>exec-maven-plugin</artifactId>
    <version>3.5.0</version>
    <executions>
        <execution>
            <goals>
                <goal>java</goal>
            </goals>
        </execution>
    </executions>
</plugin>

Ok, agora, vamos por a configuração da classe principal:

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>exec-maven-plugin</artifactId>
    <version>3.5.0</version>
    <executions>...</executions>
    <configuration>
        <mainClass>com.jeffque.App</mainClass>
    </configuration>
</plugin>

Plugin configurado! Será?

> ./mvnw exec:java
[INFO] Scanning for projects...
[INFO] 
[INFO] ---------------< com.jeffque:graalvm-24-1-2-regression >----------------
[INFO] Building graalvm-24-1-2-regression 1.0-SNAPSHOT
[INFO]   from pom.xml
[INFO] --------------------------------[ jar ]---------------------------------
[INFO] 
[INFO] --- exec:3.5.0:java (default-cli) @ graalvm-24-1-2-regression ---
Hello World!
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time:  0.341 s
[INFO] Finished at: 2025-01-31T08:28:48-03:00
[INFO] ------------------------------------------------------------------------

Adaptando ao problema da issue

Vamos colocar as coisas da issue do GitHub. Primeiramente, para a versão problemática do GraalVM. Vamos alterar a main para refletir como está na issue.

Adicionar as dependências e alterar a main foi uma non-issue, bem direto ao ponto. Para testar, coloquei as dependências para a versão do GraalVM com problema e mandei executar:

> ./mvnw compile exec:java
...
org.graalvm.polyglot.PolyglotException: TypeError: k.equals is not a function
    at <js>.:=> (Unnamed:6)
    at com.oracle.truffle.polyglot.PolyglotFunctionProxyHandler.invoke (PolyglotFunctionProxyHandler.java:151)
...

Perfeito! Tal qual aparece na issue!

Profiles

Vou criar perfis distintos. E neles vou colocar as dependências. Você pode ler mais na documentação oficial.

Vou criar dois perfis:

graalvm-24, apresenta o problema
graalvm-20, não apresenta o problema

<profiles>
    <profile>
        <id>graalvm-24</id>
    </profile>
    <profile>
        <id>graalvm-20</id>
    </profile>
</profiles>

Ok. Agora, vou deixar o perfil graalvm-24 ativo por default. Se ninguém falar nada, ele que será invocado:

<profile>
    <id>graalvm-24</id>
    <activation>
        <activeByDefault>true</activeByDefault>
    </activation>
</profile>

Como invocar esse perfil? Passando a opção -P na linha de comando!

Por exemplo:

./mvnw exec:java -Pgraalvm-24

Estou explicitando que quero o perfil graalvm-24. De modo semelhante:

./mvnw exec:java -Pgraalvm-20

Para o perfil graalvm-20. Eu poderia passar múltiplos perfis também:

./mvnw exec:java -Pgraalvm-20,jeff,marmota

Isso ativa os perfis graalvm-20, jeff e marmota. E no caso o activateByDefault, funciona como? Bem, se você não falar nada...

./mvnw exec:java
# note que não tem -P

Aí só ativa o que tá cadastrado pra rodar por padrão.

Muito bem, agora eu coloco as dependências:

<profiles>
    <profile>
        <id>graalvm-24</id>
        <activation>
            <activeByDefault>true</activeByDefault>
        </activation>
        <dependencies>
            <dependency>
                <groupId>org.graalvm.polyglot</groupId>
                <artifactId>polyglot</artifactId>
                <version>24.1.2</version>
            </dependency>
            <dependency>
                <groupId>org.graalvm.polyglot</groupId>
                <artifactId>js-community</artifactId>
                <version>24.1.2</version>
                <type>pom</type>
                <scope>runtime</scope>
            </dependency>
        </dependencies>
    </profile>
    <profile>
        <id>graalvm-20</id>
        <dependencies>
            <dependency>
                <groupId>org.graalvm.sdk</groupId>
                <artifactId>graal-sdk</artifactId>
                <version>20.1.0</version>
            </dependency>
            <dependency>
                <groupId>org.graalvm.js</groupId>
                <artifactId>js</artifactId>
                <version>20.1.0</version>
            </dependency>
        </dependencies>
    </profile>
</profiles>

E pronto, agora tenho dois perfis distintos! Note que o graalvm foi removido do project.dependencies, pois essas dependências sem perfil afetam a todos.

Para testar:

> ./mvnw exec:java
...
org.graalvm.polyglot.PolyglotException: TypeError: k.equals is not a function
    at <js>.:=> (Unnamed:6)
...

> ./mvnw exec:java -P graalvm-20
...
[INFO] --- exec:3.5.0:java (default-cli) @ graalvm-24-1-2-regression ---
Optional[true]
[INFO] ------------------------------------------------------------------------
...

Manipulando query string para melhor permitir compartilhar uma página carregada dinamicamente

Jefferson Quesado — Fri, 24 Jan 2025 00:09:34 +0000

Interagindo no Bluesky acabei conversando com Moreno Colaiacovo. Após uma troca rápida e amigável, resolvi explorar mais o perfil dele e encontrei o Genomics Daily.

Explorando o Genomics Daily, encontrei o archive. Mas uma coisa me incomodou: eu não conseguia compartilhar a data específica que uma notícia surgiu. Então, pensei: "por que não abrir um PR?"

Estrutura do site

O Genomics Daily é uma página estática servida pelo GitHub Pages. Seu repositório é emmecola.github.io. Como um GitHub Pages clássico, é um SSG Jekyll.

Descobri mexendo nesse projeto que o GitHub pages agora tem a possibilidade de hospedar o resultado de uma GitHub Action:

Rodando dois Jekylls em paralelo

Botei para rodar o Genomics Daily em modo padrão. Ou seja: porta 4000. E escrever este post aqui no Computaria sem verificar é... é chato. Então, vamos lá. Corrigir isso.

Para isso, uma pequena olhada no código do Jekyll. E... achei! A opção se chama port!

Ok, em segunda olhada eu vi que também tem disponível facilmente na página web da própria documentação das opções do Jekyll. Ok, consegui a informação que eu precisava, os detalhes não importam tanto.

Então, eu poderia simplesmente chamar o bundle exec jekyll s -w -d -p 4001, mas meu
fluxo atual é com rake, então vou ficar com ele. Portanto, passar a opção da porta para o rake.

Para isso, usei um padrão:

rule(/^run-[0-9]+$/) do |t|
    port = t.name["run-".length() ..]
    run_jekyll port: port
end

Eu pego o nome da task e dela a substring após run-. Então passo para a função run_jekyll com o parâmetro nomeado port:

def run_jekyll(port: nil)
    # debugging
    puts "port? #{port}"
    require "jekyll"
    opts = {
        'show_drafts' => true,
        'watch' => true,
        'serving' => true
    }
    opts['port'] = port unless port.nil?

    # mais debugging
    puts opts
    conf = Jekyll.configuration(opts)
    Jekyll::Commands::Build.process conf
    Jekyll::Commands::Serve.process conf
end

Essa função foi obtida a partir da task orginial run, que ficou assim:

task :run do |t|
    run_jekyll
end

Fazendo isso, temos as APIs:

rake run # vai rodar na porta padrão
rake run-4001 # vai rodar na porta 4001

Bem, isso funciona e funciona bem. Mas o jeito, digamos, mais padrão de passar parâmetros para o rake é usando chaves. Vamos tentar? Estou seguindo a documentação.

No primeiro teste, queria simplesmente saber o que acontece se, por acaso, eu não passar nenhum complemento. Criei uma task chamada run2 só para usar ela nos testes. O jeito geral dela ficou assim:

task :run2,[:port] do |t, args|
    #...
end

Para testar o resultado, mandei imprimir o argumento port e se ele era nulo ou não:

task :run2,[:port] do |t, args|
    puts args.port
    puts args.port.nil?
end

Rodei os seguintes comandos e obtive os seguintes resultados no bash:

> rake run2

true
> rake run2[123]
123
false

Mas... minha shell padrão do sistema é zsh. E rodando no zsh tive um comportamento... ligeiramente diferente...

> rake run2[123]
zsh: no matches found: run2[123]

O que isso quer dizer? Que ele tentou fazer alguma expansão da própria shell em cima de run2[123], enquanto que o bash ficou satisfeito em lidar com isso como se fosse uma simples string. Para rodar com parâmetros precisar usar de escapes da própria shell. Seja o basckslash ou botando entre aspas ou apóstrofos:

> rake run2

true
> rake 'run2[123]'
123
false
> rake "run2[123]"
123
false
> rake run2\[123\]
123
false

Ok, tudo certo. Como a falta do argumento funciona de modo igual ao valor nulo, vou deixar tudo na task run mesmo, com o parâmetro opcional da porta. Inclusive esse parâmetro opcional aparece no rake --tasks. De modo semelhante, alterei também o rake browser para permitir parametrizar a porta da mesma exata maneira:

task :run,[:port] do |t, args|
    require "jekyll"
    opts = {
        'show_drafts' => true,
        'watch' => true,
        'serving' => true
    }
    opts['port'] = args.port unless args.port.nil?
    conf = Jekyll.configuration(opts)
    Jekyll::Commands::Build.process conf
    Jekyll::Commands::Serve.process conf
end

task :browser,[:port] do |t, args|
    require 'dotenv/load'
    port = unless args.port.nil?
        args.port
    else
        4000
    end
    sh "open #{"-a #{ENV["BROWSER_NAME"]}" unless ENV["BROWSER_NAME"].nil?} http://localhost:#{port}/blog/"
end

Mudanças na URL

Meu primeiro experimento foi alterar location. Descobri que tem um campo chamado location.search que é onde moram os query params. Por exemplo, se abrir uma URL tipo https://computaria.gitlab.io/blog/about/?status=true, o valor de location.search será "?status=true". Ok, então posso fazer um simples location.search = "?a=b", correto? Bem, na verdade, não...

Por que não? Porque isso muda o comportamento atual da página Genomics Daily, que é carregar o recurso dinamicamente sem haver recarga de página. Portanto, se eu quiser oferecer alguma alteração para permitir compartilhar a página do dia escolhida no archive, eu não posso escolher fazer assim. Mas, que outras opções eu tenho?

Descobri nesta resposta do StackOverflow que eu posso brincar com a API de history! Vamos brincar aqui no Computaria essa API?

Brinque com o botão no post original.

Ao clicar, você deve perceber que passou a aparecer na URL um query param com o valor marmota=1, e ao clicar novamente muda para marmota=2 e sai incrementando o valor associado à chave marmota para todo e qualquer clique.

A implementação foi assim:

function alteraQueryParam() {
    const url = new URL(window.location.href);
    if (!window.history) {
        alert("Este browser aparenta não ter API de history")
        return
    }

    const paramName = 'marmota'
    let x = url.searchParams.get(paramName)
    if (!!x) {
        x = Number(x) + 1
    } else {
        x = 1
    }
    url.searchParams.set(paramName, x);
    window.history.pushState(null, '', url.toString());
}

Habilitando o Genomics Daily localmente

Clonei o repositório e a primeira coisa que fiz foi copiar o Rakefile do Computaria para o meu clone local (sem commitar, claro). E quando dou um rake run... ele não deu certo! Por quê? Porque ele não encontrava o tal de minima. Mas onde estava esse minima?

minima é um tema do Jekyll, declarado no _config.yaml da página do Genomics Daily:

include: [".well-known"]
theme: minima
header_pages:
  - README.md
  - genomics-daily/index.html

Ok, preciso instalar a gem, e agora? Bem, por via das dúvidas, copia o Gemfile também e adiciona essa gem lá. Feito isso, bundle update e... rake funcionou.

Ajuste em links internos

O link original que saía do dia atual para o archive não funciou no meu fork. Para corrigir isso, sem mudar o comportamento atual, simplesmente transformei o /genomics-daily/archive/ em URL relativa:

 <div>
     <a
-        href="/genomics-daily/archive/"
+        href="{{ "/genomics-daily/archive/" | relative_url }}"
         style="float:right"
         title="View the Genomics Daily archive"
         aria-label="View the Genomics Daily archive">
             Archive
     </a>
 </div>

Carregando a página

Aqui temos dois desafios: carga inicial e atualizar o query param.

Atualizar o query param

Essa parte é tranquila, já resolvemos logo acima. Agora, toda vida que disparar o evento que faz a carga do dia do Genomics Daily precisamos atualizar chamar a função de history para atualizar a URL sem causar recarga da página.

No caso, ele já estava interceptando quando havia uma submissão do formulário, então aproveitei esse trecho:

 form.addEventListener('submit', (e) => {
     e.preventDefault();
     const date = document.getElementById('documentDate').value;
+    if (window.history) {
+        const url = new URL(window.location.href);
+        url.searchParams.set('date', date);
+        window.history.pushState(null, '', url.toString());
+    }
     const [year, month, day] = date.split('-');
     const formattedDate = `${year.slice(2)}-${month}-${day}`;
     fetch(`summary-${formattedDate}.md`)
     .then(response => response.text())
     .then(data => {
         document.getElementById('result').innerHTML = marked.parse(data);
     })
     .catch(error => console.error('Error loading content:', error));
 });

Com isso já temos a possibilidade de ao selecionar uma data poder compartilhar a URL já com a data selecionada. Agora, precisamos botar isso para ser algo útil.

Utilizando ao carregar a página

A primeira coisa que eu queria fazer era ter acesso ao HTML inteiro da página para poder por um onready no <body>, mas eu não tinha acesso. Seria necessário mudar no _layout e, sinceramente? Parece complicação demais.

Outra alternativa seria usar o <script defer> (como fiz em Deixando a pipeline visível para acompanhar deploy do blog), mas isso implicaria remover a localidade do código JS de dentro do HTML. Então, qual evento a mais eu consigo detectar? Bem, uma das alternativas (talvez não a melhor) é interceptar o evento load do objeto window:

<script>
    window.addEventListener('load', () => {
        console.log('oie')
    })
</script>

Apertei F5 e lá estava a mensagem do console. Ok, satisfeito. Enquanto escrevia este post eu me questionei, "será que não poderia ter usado window.onload?"

<script>
    window.onload = () => {
        console.log('oie')
    })
</script>

E funciona também, magnificamente bem. Nessa situação, quando termina de carregar aquilo que é necessário, podemos disparar a chamada para buscar as novas informações. Basicamente é extrair a data do query param date e, estando ele presente, chamar a mesma função que tem no evento de submissão do form. Para isso, primeiro extraí a função de carregamento de conteúdo do evento de submissão:

function loadSummary(date) {
    const [year, month, day] = date.split('-');
    const formattedDate = `${year.slice(2)}-${month}-${day}`;
    fetch(`summary-${formattedDate}.md`)
    .then(response => response.text())
    .then(data => {
        document.getElementById('result').innerHTML = marked.parse(data);
    })
    .catch(error => console.error('Error loading content:', error));
}
form.addEventListener('submit', (e) => {
    e.preventDefault();
    const date = document.getElementById('documentDate').value;
    if (window.history) {
        const url = new URL(window.location.href);
        url.searchParams.set('date', date);
        window.history.pushState(null, '', url.toString());
    }
    loadSummary(date)
});

Ficou no handler do form apenas a parte específica de resgatar o valor date e de empurrar na URL o query param. De resto, fica na função de carregar o conteúdo, loadSummary. E no carregamento:

window.onload = () => {
    const url = new URL(window.location.href);
    if (url.searchParams.get("date")) {
        const queryDate = url.searchParams.get("date")
        document.getElementById('documentDate').value = queryDate
        loadSummary(queryDate)
    }
}

Pronto, aqui eu estou carregando o conteúdo com loadSummary do mesmo jeito, mas também aproveitei e para evitar qualquer confusão coloquei o valor do componente do formulário para o valor correto.

Fiz alguns testes colocando a atribuição de função window.onload dentro de um setTimeout, e o resultado mostrou que o load não é disparado:

setTimeout(() => {
    window.onload = () => {
        const url = new URL(window.location.href);
        if (url.searchParams.get("date")) {
            const queryDate = url.searchParams.get("date")
            document.getElementById('documentDate').value = queryDate
            loadSummary(queryDate)
        }
    }
}, 0)

Mesmo com o intervalor de espera em 0ms. Para contornar isso, resolvi perguntar para o documento se ele já estava no estado completed. Se sim, chamava a função de carregamento, caso contrário botava o listener de evento.

setTimeout(() => {
    function firstLoad() {
        const url = new URL(window.location.href);
        if (url.searchParams.get("date")) {
            const queryDate = url.searchParams.get("date")
            document.getElementById('documentDate').value = queryDate
            loadSummary(queryDate)
        }
    }
    if (document.readyState === 'complete') {
        console.log("completed") // debug
        firstLoad();
    } else {
        console.log("evento")  // debug
        window.onload = firstLoad
    }
}, 0)

E passou pelo debugging de completed, não evento. Ok, feliz. E sem a gambiarra do setTimeout passou pelo outro ramo, perfeito.

Trampolim para funções além do primitivo recursivo? Implementação para a função de Ackermann Peter

Jefferson Quesado — Sat, 18 Jan 2025 10:45:42 +0000

Desde que aprendi sobre trampolim eu apenas fazia questão de usar essa estratégia em casos mais simples, com uma recursão apenas, provavelmente um subconjunto próprio de funções primitivas recursivas.

Mas surgiu uma necessidade no trabalho de fazer uma computação extraordinariamente longa. A primeira função que pensei foi busy beaver, mas além de saber que ela é a mais custosa possível computacionalmente, não tenho muito familiaridade com ela. Então, fui para um caminho que eu tinha mais costume: a função de Ackermann Peter.

Definindo a função de Ackermann Peter

Ela é uma função simples de entender, que recebe dois argumentos como entrada:

int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}

Você pode ler mais sobre ela na sua própria página da Wikipedia, ou no Wolframalpha.

Utilizando a função

Rodei achermannPeter para verificar se era possível usá-lo na demonstração da POC, o primeiro teste (ackermannPeter(3, 3)) demonstrou que se estava calculando corretamente, mas era pouco para o que se desejava fazer. Quando coloquei ackermannPeter(4, 3), em algum tempo aconteceu o famoso stack overflow. Isso porque a chamada da função de Ackermann Peter é extremamente profunda, o simples fato de mudar o primeiro argumento de 3 para 4 fez com que a saída que era 61 passasse a ser $2^{2^{65536}} - 3$ .

Contornando a falta de espaço em pilha

Bem, o problema reside no fato de que a função de Ackermann Peter é muito intensa na recursão, ocupando rapidamente toda a pilha. Então, que tal usarmos de continuação para evitar colocar tudo na pilha? Basicamente, por em prática a ideia do trampolim.

Revisando o trampolim: o passo precisa ter 3 comportamentos:

saber se a computação foi finalizada
resgatar o valor computado
dar um passo e pegar a próxima continuação

Em suma, para o nosso caso em que se retorna um inteiro:

interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    // computation has over
    static Continuation found(int v) {
        return new Continuation() {
            @Override
            public boolean finished() {
                return true;
            }

            @Override
            public int value() {
                return v;
            }

            @Override
            public Continuation step() {
                return this;
            }
        };
    }

    // go on computing
    static Continuation goon(Supplier<Continuation> nextStep) {
        return new Continuation() {
            @Override
            public boolean finished() {
                return false;
            }

            @Override
            public int value() {
                return 0;
            }

            @Override
            public Continuation step() {
                return nextStep.get();
            }
        };
    }
}

E o trampolim propriamente dito é assim:

static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}

Mas, como aplicar no caso da função de Ackermann Peter?

Bem, vamos lá. A função é dividida em 3 casos:

caso base, em que se retorna o valor
recursão simples, que se retorna uma chamada simples a função de Ackermann Peter
segunda recursão, em que se faz uma chamada recursiva usando como valor o resultado de uma chamada recursiva

Hmmm, temos recursão sendo chamada para prover o resultado de uma chamada recursiva?

Bem, nesse caso seria bom que o trampolim controlasse também o resultado da segunda recursão. Mas como ele faria isso?

Bem, bora lá. O primeiro passo é detectar que não temos um valor propriamente dito, mas sim uma Continuation. Isso significa que, no lugar de receber n como um inteiro, passarei a receber ele como uma Continuation. E o que fazer então? Bem, basicamente é verificar se n já finalizou e, se sim, tudo segue mais ou menos normalmente. Mas caso contrário...

Aí daria um único passo nessa continuation e geraria uma nova continuation.

Então, como que ficaria mais ou menos? O esquema geral seria algo assim:

ackermannPeter(m: int, c: Continuation): Continuation {
    if (!c.finished) {
        return goon(() => {
            const next = c.step();
            return goon(() => ackermannPeter(m, next));
        });
    }
    const n: int = c.value();
    // ... trabalha mais ou menos normal
}

Ok, e como seria a parte em que o valor está, de fato, computado? Quando m <= 0, não tem segredo, só dizer que achou o valor n + 1. Agora, e com n <= 0 no caso de m != 0? Aí é um trampolim mais tradicional, usando 1 como valor encontrado de n:

ackermannPeter(m: int, c: Continuation): Continuation {
    if (!c.finished) {
        return goon(() => {
            const next = c.step();
            return goon(() => ackermannPeter(m, next));
        });
    }
    const n: int = c.value();
    if (m == 0) {
        return found(n + 1);
    } else if (n == 0) {
        return goon(() => ackermannPeter(m - 1, found(1)));
    }
    // ... e aqui o pulo do gato!
}

Ok, e o pulo do gato? Bem, o argumento é uma continuação, né? Então criemos a continuação, passemos ela para uma continuação que chama Ackermann Peter e retornemos essa continuação. Algo como:

const next = goon(() => ackermannPeter(m, found(n - 1)));
return goon(() => ackermannPeter(m - 1, next));

Tudo junto?

ackermannPeter(m: int, c: Continuation): Continuation {
    if (!c.finished) {
        return goon(() => {
            const next = c.step();
            return goon(() => ackermannPeter(m, next));
        });
    }
    const n: int = c.value();
    if (m == 0) {
        return found(n + 1);
    } else if (n == 0) {
        return goon(() => ackermannPeter(m - 1, found(1)));
    }
    return goon(() => ackermannPeter(m - 1, goon(() => ackermannPeter(m, found(n - 1)))));
}

E em um esquema Java, menos typescript-esco?

private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m <= 0) {
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}

Esse foi o mais próximo que consegui chegar de um trampolim para a função de Ackermann Peter. Ainda não é perfeito porque chega a serializar a continuação em até n passos aninhados um dentro do outro.

Adicionando memoização

Bem, e se fosse possível memoizar? Vamos ter duas situações de memoização:

aquela que já sabemos o resultado e só precisa retornar o que está na memória
sabemos o passo seguinte e conseguimos inferir o resultado atual

Para o passo 1 funcionar, já precisamos estar com a continução do segundo argumento resolvida. Portanto, só posso usar depois de saber quem é n:

private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    if (jah tem memoizado para(m, n)) {
        return memoization;
    }
    if (m <= 0) {
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1,
            Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
        )))
    );
}

Ok, ainda não consigo fazer muita coisa porque não ensino os resultados. Bem, podemos ensinar a primeira classe de resultados, que é quando m <= 0:

private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    if (jah tem memoizado para(m, n)) {
        return memoization;
    }
    if (m <= 0) {
        memoizar(m, n).o valor(n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1,
            Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
        )))
    );
}

Ok, parece interessante. Mas aqui prende para valor de m constante 0 (já que em tese nunca chega em negativo, exceto em caso de fluke). Vamos expandir para outros valores de m? Se nós soubermos quanto seria para m-1, 1 já conseguimos aprender para m, 0:

private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    if (jah tem memoizado para(m, n)) {
        return memoization;
    }
    if (m <= 0) {
        memoizar(m, n).o valor(n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        if (jah tem memoizado para(m-1, 1)) {
            memoizar(m, n).o valor(memoization);
            return memoization;
        }
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1,
            Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
        )))
    );
}

Ok, muito bom. Conseguimos expandir para diversos valores, mas ainda temos a classe mais abundante de valores: para quando temos argumentos estritamente positivos, que nesse caso teremos duas chamadas à função de Ackermann Peter.

Bem, podemos primeiro checar se temos memoização para m, n-1. Se tiver, apesar de ainda não conseguirmos usar para aprender, ao menos evitamos algumas computações. Se não tiver, aí seguimos com o cálculo clássico:

private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    if (jah tem memoizado para(m, n)) {
        return memoization;
    }
    if (m <= 0) {
        memoizar(m, n).o valor(n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        if (jah tem memoizado para(m-1, 1)) {
            memoizar(m, n).o valor(memoization);
            return memoization;
        }
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    // note que aqui vejo a NÃO memoização agora
    if (!jah tem memoizado para(m-1, 1)) {
        return Continuation.goon(() ->
            ackermannPeterMemo(m - 1,
                Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
            )))
        );
    }
    // ok, aqui já podemos seguir com o valor memoizado da chamada recursiva interna
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1, Continuation.found(memoization))
    );
}

Beleza. Agora, podemos verificar se por acaso já conhecemos algo de m-1, memoization, né?

private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    if (jah tem memoizado para(m, n)) {
        return memoization;
    }
    if (m <= 0) {
        memoizar(m, n).o valor(n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        if (jah tem memoizado para(m-1, 1)) {
            memoizar(m, n).o valor(memoization);
            return memoization;
        }
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    // note que aqui vejo a NÃO memoização agora
    if (!jah tem memoizado para(m, n - 1)) {
        return Continuation.goon(() ->
            ackermannPeterMemo(m - 1,
                Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
            )))
        );
    }
    // ok, aqui já podemos seguir com o valor memoizado da chamada recursiva interna
    if (jah tem memoizado para(m - 1, memoization)) {
        memoizar(m, n).o valor(novaMemoization);
        return novaMemoization;
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1, Continuation.found(memoization))
    );
}

Ok, muito bonito. Mas, como memoizar isso? Bem, a estrutura mais fácil seria um hashmap. Mas pra isso preciso de uma chave, e a chave se for um record implica na criação de muitos objetos para simplesmente verificar se está dentro do mapa.

Mas sabe o que é legal? Que eu preciso de apenas 64 bits para representar todos os meus parâmetros, m e n. Como? Colocando m na parte mais significativa de um long e n na menos:

static long key(int m, int n) {
    return ((long)m) << 32 | (long) n;
}

Voi là. O java trata de fazer o boxing automaticamente de long -> Long, então não preciso me preocupar mais com isso. E o melhor: o Java vai ser ótimo fazendo reuso de objetos.

A propósito, o excesso de casts para long na função acima é para garantir que vai usar a operação de 64 bits corretamente e não perder precisão.

O primeiro teste podemos usar uma memória global:

static HashMap<Long, Integer> paMemory = new HashMap<>();
private static Continuation ackermannPeterMemo(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next));
        });
    }
    int n = c.value();
    {
        long k = key(m, n);
        Integer memoized = paMemory.get(k);
        if (memoized != null) {
            return Continuation.found(memoized);
        }
    }
    if (m <= 0) {
        long k = key(m, n);
        paMemory.put(k, n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        long kRecursivo = key(m - 1, 1);
        Integer memoized = paMemory.get(kRecursivo);
        if (memoized != null) {
            long k = key(m, n);
            paMemory.put(k, memoized);
            return Continuation.found(memoized);
        }
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1)));
    }
    // note que aqui vejo a NÃO memoização agora
    long kRecursivoInterno = key(m, n - 1);
    Integer memoizedInterno = paMemory.get(kRecursivoInterno);
    if (memoizedInterno == null) {
        return Continuation.goon(() ->
            ackermannPeterMemo(m - 1,
                Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1)
            )))
        );
    }
    // ok, aqui já podemos seguir com o valor memoizado da chamada recursiva interna
    long kRecursivoExterno = key(m - 1, memoizedInterno);
    Integer memoizedExterno = paMemory.get(kRecursivoExterno);
    if (memoizedExterno != null) {
        long k = key(m, n);
        paMemory.put(k, memoizedExterno);
        return Continuation.found(memoizedExterno);
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1, Continuation.found(memoizedInterno))
    );
}

Essa função computa fazendo 53.406 chamadas recursivas para ackermannPeterMemo(3, 2), enquanto que a primeira implementação fazia 1.073.692.222 operações.

Agora, vamos nos livrar do global? Basicamente vai ser transformar o que antes era global em argumento.

private static Continuation ackermannPeterMemo(int m, Continuation c, HashMap<Long, Integer> paMemory) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeterMemo(m, next, paMemory));
        });
    }
    int n = c.value();
    {
        long k = key(m, n);
        Integer memoized = paMemory.get(k);
        if (memoized != null) {
            return Continuation.found(memoized);
        }
    }
    if (m <= 0) {
        long k = key(m, n);
        paMemory.put(k, n + 1);
        return Continuation.found(n + 1);
    }
    if (n <= 0) {
        long kRecursivo = key(m - 1, 1);
        Integer memoized = paMemory.get(kRecursivo);
        if (memoized != null) {
            long k = key(m, n);
            paMemory.put(k, memoized);
            return Continuation.found(memoized);
        }
        return Continuation.goon(() -> ackermannPeterMemo(m - 1, Continuation.found(1), paMemory));
    }
    // note que aqui vejo a NÃO memoização agora
    long kRecursivoInterno = key(m, n - 1);
    Integer memoizedInterno = paMemory.get(kRecursivoInterno);
    if (memoizedInterno == null) {
        return Continuation.goon(() ->
            ackermannPeterMemo(m - 1,
                Continuation.goon(() -> ackermannPeterMemo(m, Continuation.found(n - 1), paMemory
            )), paMemory)
        );
    }
    // ok, aqui já podemos seguir com o valor memoizado da chamada recursiva interna
    long kRecursivoExterno = key(m - 1, memoizedInterno);
    Integer memoizedExterno = paMemory.get(kRecursivoExterno);
    if (memoizedExterno != null) {
        long k = key(m, n);
        paMemory.put(k, memoizedExterno);
        return Continuation.found(memoizedExterno);
    }
    return Continuation.goon(() ->
        ackermannPeterMemo(m - 1, Continuation.found(memoizedInterno), paMemory)
    );
}

Trampolim, exemplo em Java

Jefferson Quesado — Fri, 17 Jan 2025 10:54:32 +0000

Vamos fazer um programinha bem simples que soma os números de n até 0? Só que, no lugar de fazer ele iterativo, que tal fazer recursivo?

Bem, vamos chamar esse programa de sum. Sabemos que sum(0) == 0, então temos o caso base. E como chegamos no caso base? Bem, sum(n) == n + sum(n-1), até que eventualmente chegamos em sum(0). Ficaria assim em Java:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Problema de recursão?

Bem, recursão tem um problema inerente quando o caso base está muito distante do valor passado... na maioria das linguagens, a chamada de função acaba fazendo uso da stack do programa para inserir os dados sobre a chamada da função, então eventualmente uma recursão muito grande poderá gerar um estouro de pilha.

Mas, será que tem como evitar isso? Na real, tem sim. E isso é uma estratégia as old as time. Se chama trampoline.

O trampolim

Basicamente a estratégia do trampoline é você fazer um pedaço do programa que retorna um "valor" ou uma "continuation". O que seria a continuation? Uma função que irá continuar o processamento.

É mais ou menos isso daqui:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

O que seria a continuation do `sum`?

Vamos modelar o programa sum para, no lugar de ser simplesmente recursivo, ter uma continuation. Bem, uma maneira é passando o acc como uma espécie de objeto passado pela continuidade. Então, ao chegar em sum_trampoline(0, acc) retornemos acc. E passar para o passo seguinte? Bem...

Bora lá, saímos de sum_trampoline(n, acc) para sum_trampoline(n-1, acc+n). E a primeira entrada é com sum_trampoline(n, 0).

Logo, ficaria assim o código:

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<Object>) () -> sum(n - 1, acc + n);
}

Descrevendo trampolim com tipos

O trampolim precisa ter mais ou menos a seguinte forma:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Só que isso tem uma liberdade de codificação muito grande, não é muito literal para o mundo Java. Podemos detectar que é continuidade perguntando ao objeto. E que tal se perguntarmos "já achou o valor?"? Outra coisa também é que, como em Java não temos sum-types, o return trampolim ali literalmente retornaria o tipo trampolim, no lugar de retornar o valor. Podemos retornar trampolim.value().

Finalmente, temos um ponto crucial que é o bootstrapping do trampolim. Para isso, poderíamos ter uma função que transformasse o input no trampolim de retorno adequado. E input e resultado podem ser generalizados para melhor uso:

public static <IN, R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

E a interface de TrampolineStep<R>?

De instância, ficaram definidos 3 métodos:

gotValue, pergunta se já tem valor
value, retorna o valor encontrado
runNextStep, retorna um valor ou uma continuidade

Bem, basicamente ela vai ter dois estados:

achou o valor
é uma continuidade

Então podemos colocar com métodos estáticos para linicialização dela. Para o caso de já achou o valor, precisa-se passar o valor:

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep<>() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

Para o caso de contnuidade, precisa passar como obter o próximo item da continuidade:

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep<>() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

Para o sum_trampoline, como ele ficaria?

TrampolineStep<Integer> sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

TrampolineStep<Integer> sum_trampoline(int n, int acc) {
    if (n == 0) {
        return TrampolineStep.valueFound(acc);
    }
    return TrampolineStep.goonStep(() -> sum_trampoline(n - 1, acc + n));
}

Tail call Fibonacci

A implementação clássica de Fibonacci segue a definição recursiva:

int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Existe ainda a versão iterativa, que desenrola a definição de Fibonacci não recursivamente, mas para a frente: começando de 0 e 1 e indo até o valor correspondente:

int fib_iterativo(int n) {
    int a = 0, b = 1;
    if (n == 0) {
        return a;
    }
    int i = 1;
    while (i < n) {
        int x = a + b;
        a = b;
        b = x;
        i++;
    }
    return b;
}

Essa implementação tem uma versão rolando para frente, usando o "tail call recursion":

int fib_tc_entrada(int n) {
    return fib_tc(0, 1, 0, n);
}

int fib_tc(int a, int b, int i, int n) {
    if (i == n) {
        return a;
    }
    return fib_tc(b, a+b, i+1, n);
}

Aqui separei na interface de entrada que prepara os dados que serão usados no Fibonacci com tail call recursion. Como ele avança para frente, começamos com os mapeamentos fib[0] => 0, fib[1] => 1 navegando a partir do índice 0 até chegar no índice n.

Fibonacci, de tail call a trampoline

Bem, o exemplo de fib_tc já dá uma ideia bem boa do que seria o trampoline para Fibonacci:

TrampolineStep<Integer> fib_bootstrap(int n) {
    return fib_trampoline(0, 1, 0, n);
}

TrampolineStep<Integer> fib_trampoline(int a, int b, int i, int n) {
    if (i == n) {
        return TrampolineStep.valueFound(a);
    }
    return TrampolineStep.goonStep(() -> fib_trampoline(b, a+b, i+1, n));
}

Recursão a moda clássica em TS: auto referência do tipo de função

Jefferson Quesado — Thu, 16 Jan 2025 12:49:38 +0000

Esse post é um foco em cima da parte final do post Vamos memoizar? Desafio da recursão

Um jeito de fazer recursão é fazer uma função que recebe a si mesma.

Para tal, é preciso declarar o tipo da função, para poder passar a ela mesma como referência:

export type RecFunc = (n: number, f: RecFunc) => number;

export function fix_point(f: RecFunc): (x: number) => number {
        return x => f(x, f)
}

E para implementar uma função como essa (por exemplo, função de Fibonacci):

import { RecFunc, fix_point } from './genericMemoization.js'

const fibPrimitive = (n: number, selfFib: RecFunc): number => n <= 0? 0: n == 1? 1: selfFib(n-1, selfFib) + selfFib(n-2, selfFib);

const fib = fix_point(fibPrimitive);
console.log(fib(12)); // 144

É possível extender para quaisquer argumentos de entrada e saída, apenas foquei aqui em entrada e saída com número simples.

Função de Péter-Ackermann:

export type RecFunc2 = (m:number, n: number, f: RecFunc) => number;

export function fix_point2(f: RecFunc2): (x: number, y: number) => number {
        return (x, y) => f(x, y, f)
}

import { RecFunc2, fix_point2 } from './genericMemoization.js'

const ackPrimitive = (m:number, n: number, selfAck: RecFunc2): number => {
  if (m == 0) return n + 1;
  if (n == 0) return selfAck(m-1, 1, selfAck);
  return selfAck(m-1, selfAck(m, n-1, selfAck), selfAck);
}

const ack = fix_point2(ackPrimitive);

Decorando a função

Posso adicionar tratativas simples às recursões. Como, por exemplo, imprimir no console.log toda vida que a função é chamada com os parâmetros passados, no nível correto. Por exemplo, o nível de entrada é 0, depois a cada passagem aumenta em um o nível.

Vamos chamar de param_logger o objeto que vai lidar com isso. Eu posso interagir com ele de 2 maneiras:

logar o que recebi, imprimindo o nível
criar outro param_logger de um nível mais baixo

O param_logger para satisfazer isso precisa ter duas funções:

type ParamLogger = {
    log: (param: number) => void,
    deeper_logger: () => ParamLogger
}

Uma estratégia que não se importa ainda com a correção do deeper_logger seria simplesmente isso:

const lyingLogger: ParamLogger = {
    log: (param: number) => console.log(`0: ${param}`),
    deeper_logger: () => lyingLogger
}

Certo, agora para manter o nível eu preciso de alguma espécie de parâmetro com o nível. Como eu não tenho explícito, isso significa que vou precisar capturar na clausura. Então isso significa que vou precisar de uma função para criar o logger. E ela vai precisar ser recursiva!

const loggerByLevel = (level: number): ParamLogger => ({
    log: (param: number) => console.log(`${level}: ${param}`),
    deeper_logger: () => loggerByLevel(level + 1)
})

Mas eu não devo expor essa função, né? Posso expor apenas o meu baseLogger. Como faço isso? Através de uma IIFE (immediately invoked function expression):

const baseLogger: ParamLogger = (() => {
    const loggerByLevel = (level: number): ParamLogger => ({
        log: (param: number) => console.log(`${level}: ${param}`),
        deeper_logger: () => loggerByLevel(level + 1)
    })
    return loggerByLevel(0)
})();

Agora, para deixar no espírito desse post, vamos passar a função recursivamente para si mesma?

const baseLogger: ParamLogger = (() => {
    type ParamLoggerCreator = (level: number, func: ParamLoggerCreator) => ParamLogger

    const loggerByLevel: ParamLoggerCreator = (level: number, func: ParamLoggerCreator) => ({
        log: (param: number) => console.log(`${level}: ${param}`),
        deeper_logger: () => func(level + 1, func)
    })
    return loggerByLevel(0, loggerByLevel)
})();

Agora, como iríamos lidar com essa decoração? Uma decoração simples no caso do Fibonacci para simplesmente imprimir o parâmetro:

fibPrimitive(12, (n, self) => {
    console.log(n)
    return fibPrimitive(n, self)
})

Note que a função sendo passada recursivamente adiante é a função self, que inicialmente ela é simplesmente uma chamada de console.log com uma chamada da função principal passando self. Agora eu preciso alterar o self.

Vou me basear na implementação feita para memoização, começando, para eventualmente mudar o self:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        return f(n, logging)
    }
    return n => logging(n, logging)
}

Hmmm, até aí ok, eu diria. Eu posso simular uma espécie de step também:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        return f(n, step)
    }
    return n => logging(n, logging)
}

Ok, step aqui é uma arrow-function. Isso significa que eu posso adicionar propriedades a ela agora:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}

Qual seria o tipo de step nesse momento?

type TipoDeStep = RecFunc & { log: ParamLogger }

// ou então equivalentemente...

type TipoDeStep = ((n: number, s: RecFunc) => number) & { log: ParamLogger }

// outra maneira...

type TipoDeStep = {
    (n: number, s: RecFunc): number,
    log: ParamLogger
}

Essa terceira notação é a anotação de "call signature" (vide geeksforgeeks). Você até não consegue criar diretamente um objeto callable através de uma arrow-function, mas o TS permite que você coloque o valor logo em seguida. Por exemplo, isso é válido:

type BinOp = {
    (a: number, b: number): number,
    nome: string
}

const soma: BinOp = (a, b) => a + b
soma.nome = "+"

Mas isso é inválido:

type BinOp = {
    (a: number, b: number): number,
    nome: string
}

const soma: BinOp = (a, b) => a + b
// erro de TS
// Property 'nome' is missing in type '(a: number, b: number) => number' but required in type 'BinOp'.ts(2741)

Massa! Agora eu preciso detectar quando o self passado é do tipo com a assinatura de chamada e com o atributo log. O jeito mais fácil é fazendo uma função de guarda!

function isRecFuncEtlog(f: RecFunc): f is RecFunc & { log: ParamLogger } {
    return (f as any)["log"] != null
}

Com isso agora eu posso interceptar e usar o log:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        if (isRecFuncEtlog(self)) {
            self.log.log(n)
            return f(n, self)
        }
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}

Pronto! Agora só falta o passo na chamada de quando é uma função com o log. Vou por a mesma lógica do step, só que agora no lugar de usar o baseLogger.deeper_logger() vou usar o .deeper_logger() do self.log:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        if (isRecFuncEtlog(self)) {
            self.log.log(n)
            const step = (n: number, s: RecFunc): number => {
                return self(n, s)
            }
            step.log = self.log.deeper_logger()
            return f(n, step)
        }
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}

DEV Community: Jefferson Quesado

Implementando uma pilha a partir de uma fila

Definindo pilhas e filas

Uma fila com duas pilhas

Uma pilha com duas filas

Uma pilha com uma fila

[Boost]

[PT-BR] Pois é! Um post sobre o hype.

Pequeno template em Node para programação competitiva

Objetivo

A vida, o universo e tudo mais

Gerador de primos

Implementando a mágica

Exemplo do gerador de primos

Exemplo da vida, o universo e tudo mais

Usando o template: macaco prego

Nota sobre leitura de dados vs programação competitiva

Estou estudando isso aqui, recursão e otimização de função de cauda

Entendendo fundamentos de recursão

Sobre operações comutativas e associativas

Comutativa Não-Associativa e Associativa Não-Comutativa

Fazendo um proxy reverso em Go

Objetivos

Hello world

Escutar e servir

Uma revisão em HTTP

Headers especiais

Lista de headers

Como funciona em Go? Servidor

Como funciona em Go? Cliente

Escrevendo o proxy

[Boost]

Acho que podemos deixar o mobile first em 2024

Camilo Micheletto ・ Feb 15

Criando projeto Maven com profiles distintos de dependências

Iniciando um projeto maven

Criando o projeto base

Adicionando comando de execução

Adaptando ao problema da issue

Profiles

Manipulando query string para melhor permitir compartilhar uma página carregada dinamicamente

Estrutura do site

Rodando dois Jekylls em paralelo

Mudanças na URL

Habilitando o Genomics Daily localmente

Ajuste em links internos

Carregando a página

Atualizar o query param

Utilizando ao carregar a página

Trampolim para funções além do primitivo recursivo? Implementação para a função de Ackermann Peter

Definindo a função de Ackermann Peter

Utilizando a função

Contornando a falta de espaço em pilha

Adicionando memoização

Trampolim, exemplo em Java

Problema de recursão?

O trampolim

O que seria a continuation do sum?

Descrevendo trampolim com tipos

Tail call Fibonacci

Fibonacci, de tail call a trampoline

Recursão a moda clássica em TS: auto referência do tipo de função

Decorando a função

O que seria a continuation do `sum`?