Pensando em linguagens de arrays

• A programação em K se concentra em levar para scripts o código experimentado no REPL e em reduzir continuamente grandes padrões imperativos a padrões de arrays menores e declarativos
• Scripts ngn/k são executados linha a linha como entradas no REPL, e dados e funções salvos podem ser carregados no REPL com \l file.k
• Transpor diretamente a multiplicação de matrizes com três laços no estilo da Wikipedia resulta em muitas variáveis globais, laços aninhados e mutações, o que vai contra os pontos fortes de K
• O processo de melhoria passa por +/ fold, ' each, /: eachright, \: eachleft, remoção de transposição e conversão tacit, condensando de matmul: {x{+/x*y}\:y} até matmul: (+/*)\:
• O exemplo de multiplicação de matrizes mostra que a habilidade em K está em repetir o processo de condensação de código, transformando procedimentos complexos em expressões de arrays mais legíveis

---

Fluxo de desenvolvimento em K centrado no REPL

• O código-fonte completo pode ser visto no matmul.k no GitHub
• A programação em K acontece em grande parte no REPL, o que facilita experimentar e melhorar rapidamente em cima do código anterior
• A combinação de ngn/k com rlfe oferece histórico com as setas para cima/baixo, suficiente para desenvolver programas K maiores
• O fluxo natural é testar funções primeiro no REPL e depois movê-las para o código real
• O prettyprinting de ngn/k sempre retorna dados K válidos, então é possível pré-computar alguns valores para acelerar o programa

Modelo de execução de scripts K

• Scripts K são executados como se tivessem sido digitados no REPL
  • Cada linha é executada em ordem
  • Se uma linha não terminar com ponto e vírgula, o valor retornado é impresso
• Scripts permitem definições em várias linhas, melhorando a legibilidade
• Para usar dados e funções salvos no REPL, execute \l file.k
  • O arquivo é executado
  • Os dados do arquivo são carregados
  • Carregar o mesmo arquivo várias vezes sobrescreve os dados anteriores
• Mais comandos podem ser consultados na ajuda do REPL acessada com \

Como reduzir padrões em uma linguagem de arrays

• K e programação de arrays são um processo de simplificação contínua de padrões
• Mesmo padrões grandes e difíceis de manejar têm pelo menos uma forma de serem reduzidos a algo menor, mais declarativo e mais legível
• A discussão relacionada pode ser vista em detalhes em Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
• Um ponto de partida comum é tentar traduzir para K algoritmos conhecidos do GeeksforGeeks ou da Wikipedia
• O exemplo usa multiplicação de matrizes

Ao transpor diretamente a multiplicação de matrizes imperativa

• O Matrix multiplication algorithm da Wikipedia preenche a matriz C com três laços i, j, k e acumulação em sum
• Traduzir isso diretamente para K leva a muitas atribuições de valores globais como A, B, n, m, p, C, i, j, k e sum
• Esse código usa K como se fosse uma linguagem imperativa, então não se encaixa bem no design de K
• O problema se resume a três pontos
  • Muitas atribuições globais
  • Vários níveis de laços aninhados permanecem
  • Há mutações frequentes

Dobrar e reduzir a partir do laço mais interno

• O laço mais interno inicializa sum como 0 e percorre k, acumulando A[i;k]*B[k;j]
• A primeira melhoria é usar /, o fold, para trocar a soma por +/
  • A global sum desaparece
  • O código fica organizado na forma C[i;j]::+/...
• Em seguida, usando o fato de que ' each retorna um array, é possível usar diretamente o valor retornado pelos laços aninhados sem modificar C
• Depois desse estágio, restam apenas três laços sem mutação, e as variáveis centrais passam a ser i, j e k

O processo de eliminar k, j e i

• O papel das três variáveis é o seguinte
  • i indexa cada linha de A
  • j indexa cada coluna de B
  • k indexa cada coluna de A e cada linha de B
• k faz com que cada linha de A e cada coluna de B sejam pareadas e multiplicadas, então é possível remover o índice intermediário e fazer o pareamento diretamente
  • Nesse estágio, um laço e m deixam de ser necessários
• Para remover j, é preciso pegar cada coluna de B e pareá-la com A[i]
  • Transpõe-se B e usa-se eachright /: para parear cada elemento
• i também pode ser eliminado da mesma forma
  • Usa-se eachleft \: para parear cada linha de A com cada coluna de B
• Após esse processo, chegamos à forma abaixo, sem globais

matmul: {x{+/x*y}/:\:+y}

Remoção da transposição e forma tacit final

• A transposição + é custosa, então pode ser removida
• A abordagem existente é a forma ingênua de multiplicar cada linha de x por cada coluna de y
• Em vez disso, ao alinhar cada linha de B ao A inteiro, o mesmo trabalho pode ser realizado implicitamente

matmul: {x{+/x*y}\:y}

• Esta função pode ser convertida para a forma tacit aplicando as regras do Chapter 3
• O resultado final é o seguinte

matmul: (+/*)\:

Intuição de linguagem de arrays construída com prática

• matmul: (+/*)\: fica organizado como uma função de multiplicação de matrizes ao estilo K
• O processo de condensação pode parecer ter muitas etapas no início
• Quanto mais se pratica K, mais a condensação de código se torna uma tarefa fácil e intuitiva
• Multiplicação de matrizes é um procedimento simples que combina bem com o suporte a arrays de K
• Nos próximos capítulos, serão abordados algoritmos que não combinam bem com K e como lidar com eles

[GN⁺]

Comentários do Hacker News

• Na prática, o que mostrou de forma mais convincente o potencial das linguagens de arrays foi um vídeo em que Aaron Hsu explica o desenvolvimento do compilador APL paralelo Co-dfns: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
  Ele também escreveu várias vezes no HN, sob o nome arcfide, sobre densidade semântica, explicando que o código APL é projetado para permitir ver, quase sem se deslocar, o modo de funcionamento, o contexto ao redor e as dependências dentro de uma única tela: https://news.ycombinator.com/item?id=13571159
  A visão é que, quando o nome de um algoritmo fica tão conciso a ponto de ter tamanho parecido com o de uma descrição por extenso do próprio algoritmo, passamos a ler o código em unidades idiomáticas, como quem lê frases em inglês, e pode ser mais rápido alterar diretamente todos os usos visíveis na tela do que criar abstrações reutilizáveis

  • Fico curioso se LLMs com uma janela de contexto finita talvez lidem melhor com APL do que com outras linguagens
  • Acho que precisar escrever uma explicação tão longa é sinal de que o código é feio. Se tivessem escolhido símbolos que parecessem menos feios quando colados uns aos outros, talvez não fosse necessário gastar 18 horas tentando convencer as pessoas de que a linguagem não é ruim

• Para quem não conhece bem programação com arrays, recomendo The Array Cast como material introdutório: https://www.arraycast.com/episodes/
  O endereço RSS é https://www.arraycast.com/episodes?format=rss

  • Ouvi mais ou menos os 5 primeiros episódios de The Array Cast tentando ser convencido, mas no fim não comprei a ideia. Os apresentadores diziam que a notação curta das linguagens de arrays e os símbolos não ASCII ficam aceitáveis com a familiaridade e valem a pena por causa das vantagens, mas a maior parte dessas vantagens já era familiar hoje em linguagens mainstream por meio de funções de ordem superior
    map/filter/reduce já existem em praticamente todo lugar, e fiquei com a impressão de que eles ignoravam o fato de que dá para usá-los sem aprender um novo sistema de notação parecido com ideogramas
  • Foi por isso que conheci BQN, mas ainda não sei se usaria em um ambiente de produção real. Mesmo gostando, fora R, NumPy e Julia, a maioria das linguagens de arrays parece estranha, e me parece que, se eu me aprofundar em APL, J e BQN, vou acabar afastando justamente as pessoas que poderiam me ajudar depois

• Conheci APL/APL2 nos anos 70, em terminais de papel que realmente usavam sobreimpressão, e me apaixonei de imediato, mas depois, ao conhecer programação funcional com ML e Haskell, percebi que o que eu realmente gostava em APL era mais a capacidade de composição de funções do que os arrays
  Haskell é totalmente puro e tem tipos aplicados de forma abrangente, então é muito melhor nesse aspecto, além de ser mais divertido e poderoso do que APL. Fiz muitos projetos pequenos e médios, também criei um protótipo mostrando que o parser do LLVM Flang poderia ser implementado com parser combinators, e todos os anos resolvo o Advent of Code em algumas centenas de linhas no total. Se você gosta de APL, vale a pena experimentar Haskell
  Hoje, o aspecto de APL como “notação como ferramenta do pensamento” me parece mais uma forma de racionalizar concisão excessiva. É bom para mostrar o poder da composição, mas também pode prejudicar a clareza

  • Neste assunto, acabo repetindo sempre a mesma coisa, mas depois que fiquei razoavelmente bom em Haskell point-free, quase parei de mexer em J e K. Quando se misturam functors, fica ainda mais poderoso do que trens de verbos; <=< já existe, e usando algo equivalente a fmap a coisa realmente funciona muito bem
    |||, +++, &&&, *** também são bons, e dá para criar seus próprios operadores UTF-8 para deixá-los mais curtos e bonitos. Ainda assim, é uma pena que código Haskell sério, em trabalho real ou publicado, raramente seja tão amigável ao espaço vertical da tela desse jeito
  • Seria bom poder ver o link do código-fonte do Advent of Code

• Fiquei curioso sobre como linguagens de array geralmente lidam com problemas como “encontrar todos os números menores que N para os quais o predicado P é verdadeiro”. Por exemplo, encontrar primos menores que 1000 ou triplas pitagóricas com z menor que 1.000.000
  Em uma linguagem imperativa, você verificaria o predicado em um loop; em uma linguagem funcional, usaria recursão ou map/filter sobre uma lista preguiçosa. Mas, em linguagens de array, entendo que normalmente se cria um array 1..N, aplica-se o predicado para criar um array de máscara e então se filtra o array original com essa máscara
  Se N for enorme, como 1 bilhão, e o predicado quase nunca for verdadeiro, criar dois arrays temporários gigantes, o 1..N e a máscara, parece um enorme desperdício de memória e recursos. Fiquei curioso se linguagens de array ficam lentas por continuarem criando esses arrays temporários, ou se as implementações otimizam isso com algo como avaliação preguiçosa

  • Sim, desperdiça muita memória. Mas memória é barata e, se necessário, é possível dividir o cálculo em blocos. Na prática, é raro a memória acabar, mas o bloqueio é útil para permanecer em níveis mais baixos da hierarquia de cache
    Linguagens escalares, por outro lado, por padrão processam um valor por vez, desperdiçando o paralelismo potencial que linguagens de array aproveitam com algoritmos SIMD. Isso também só não parece um grande problema porque estamos acostumados com o estado atual, e a solução também é bloqueio
    Se uma linguagem de array é de fato boa depende do problema. Na maioria dos usos práticos, desempenho não importa nem um pouco, e a reputação de k parece vir mais do fato de o kdb ser rápido como banco de dados do que de k, como implementação de linguagem, ser rápido. Ainda assim, só de focar em algoritmos de array elegantes em vez de otimizações detalhadas por máquina, dá para ficar surpreendentemente rápido: https://mlochbaum.github.io/BQN/implementation/versusc.html
  • Há algumas formas de contornar isso. Avaliação preguiçosa é uma delas, e Kap a usa: https://aplwiki.com/wiki/KAP
    Outra maneira óbvia é fazer fusão de loops em todo o corpo para evitar a criação de arrays temporários. Uma opção mais simples é dividir os arrays de entrada e saída em chunks de algumas dezenas de KB, limitando o uso de memória temporária desnecessária. Até onde sei, nenhuma linguagem de array faz isso automaticamente, e eu gostaria de tentar fazer isso algum dia no CBQN. O usuário também pode fazê-lo manualmente e, para maximizar desempenho, isso de fato precisa ser feito com frequência
  • A intuição está em grande parte correta, mas, na prática, é um problema raro. Na família k, por exemplo em ngn/k, há uma estrutura preguiçosa que trata algo como !10000000, uma iota de 0 até dez milhões, como um simples intervalo, sem realmente criar um array de dez milhões de inteiros
    Claro, dependendo dos operadores usados, esse array pode acabar sendo criado. Também há otimizações como transformar um padrão do tipo +|x, que inverte x e pega o primeiro elemento, em simplesmente pegar o último elemento
  • Parece que você está assumindo que a criação do array acontece literalmente. Não há motivo para uma linguagem de array não poder processar internamente em chunks. Mesmo que você peça um array de 10 bilhões de inteiros, ela pode não criá-lo ingenuamente exatamente assim
  • Muitas linguagens de array de fato têm esse problema. Mais precisamente, o problema é que a abordagem simples e intuitiva tende a computar muito mais do que o necessário
    Claro, dá para escrever de outro jeito e evitar isso, mas essas soluções podem ficar mais longas e menos bonitas. O dialeto de APL em que estou trabalhando, Kap, adia a computação até que o resultado seja necessário, tratando vários casos para permitir escrever o código da forma intuitiva sem calcular resultados que serão descartados

• Os maiores aprendizados que tive usando linguagens de array, especialmente k, foram os seguintes. Verbos são algoritmos, e em linguagens imperativas e orientadas a objetos muitas vezes é preciso implementar diretamente algoritmos comuns como find, sort e group
  Sequências de verbos ou advérbios foram a forma de composição mais direta que já usei, e a composição é fácil e natural. Um programa passa a parecer uma composição de algoritmos, não uma coleção de instruções e expressões
  Tratar de forma consistente os conceitos de domínio e contradomínio em arrays, mapas e funções simplifica as escolhas de design, e a avaliação da direita para a esquerda evita que os olhos precisem ficar pulando de um lado para outro ao ler o código
  É possível, e preferível, enviar o código para os dados em vez de trazer os dados para o código. A maioria dos grandes projetos em k, excluindo comentários, cabe dentro de uma MTU de rede, isto é, 1540 bytes. Como bônus de k, views podem implementar relações funcionais diretamente, e o carregamento de código a quente via interpretador permite aplicações que rodam “para sempre”

• Minha impressão pessoal, enviesada e limitada, ao resolver problemas da linguagem K para me preparar para entrevistas de emprego, é que a linguagem é intencionalmente obscura. É uma boa linguagem para puzzles e soluções engenhosas
  Mas acho que o que ensina linguagens de array e a pensar em arrays é a experiência de trabalhar com arrays NumPy em Python

  • Fiquei curioso para saber de qual entrevista era

• Pela minha experiência usando J por cerca de 50 horas, senti, honestamente, que esse paradigma é enviesado demais para um lado só
  Não sei se pensar em todos os problemas como aninhamento de arrays ajuda como ferramenta de pensamento. Se você puder criar livremente estruturas de dados que capturem bem o problema, a parte algorítmica pode ficar muito mais simples
  Acho que é preciso ser mais inteligente para usar APL/J/K. Em linguagens mais flexíveis, abordagens que funcionam de imediato muitas vezes são impossíveis ali, então é preciso transformar o problema, e esse processo pode exigir muito mais reflexão

• Este exemplo é baseado em K, mas outra linguagem de array é J: http://jsoftware.com
  Em J, se você escrever dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q, isso retorna 10, o produto interno de P e Q

  • A linguagem de array original é APL, e o produto interno pode ser escrito como dot←+.×. Mas, se a notação por extenso é tão curta quanto um nome razoavelmente curto, não há muita necessidade de dar um nome a ela, e talvez ainda seja preciso colocar espaços ao redor do nome
  • Ainda não entendo bem qual é a vantagem disso em relação a Haskell. Dá para escrever dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], p `dot` q
    Aos meus olhos, a única diferença parece ser usar nomes em sum e zipWith, e o fato de que lifting ou transformação estrutural não acontecem “magicamente”
  • Em KlongPy, o produto interno é escrito como dot::{+/x*y}. O formato é P::[2 3 4], Q::[1 0 2], dot(P;Q)

• Olhando os exemplos, não entendo qual é o sentido disso. O desempenho é melhor de alguma forma?
  A sintaxe de multiplicação de matrizes é mais curta, mas isso parece ser porque é preciso manter na cabeça muito contexto embutido sobre como a linguagem K funciona

  • O fato de ser mais conciso já tem valor por si só. Especialmente se pensarmos que a matemática é um processo de comprimir cada vez mais conceitos em definições de nível mais alto. Quando conceitos de nível mais alto se tornam elementos primitivos, dá para pensar mais rápido e construir objetos mais complexos
  • O desempenho pode ser melhor. Computadores são muito rápidos em varrer arrays, especialmente quando dá para aproveitar SIMD, mas isso não é tudo
    Vale a pena experimentar uma linguagem de arrays e brincar com ela até entender o paradigma. Muitas vezes código imperativo é expresso melhor em estilo de arrays, e funções longas e cheias de detalhes às vezes ficam muito mais simples usando apenas operações de arrays ou combinadas com outros estilos
  • Verbosidade também tem custo, e se você acredita que só funções realmente complexas têm o privilégio de ser verbosas, o sentido fica fácil de ver
    Comparando, em Haskell, (+) <$> Just 1 <*> Just 2 com do x <- Just 1; y <- Just 2; Just (x + y), nesse nível de complexidade eu sempre prefiro a primeira. A segunda ocupa mais espaço e dá a sensação de que algo mais complexo está acontecendo
    Para uma tarefa mais complexa, em vez de usar a segunda forma, eu preferiria decompô-la em funções pequenas para que uma variação da primeira fizesse sentido. Isso é uma troca: transformar “alguns iniciantes conseguem ler rapidamente” em “quem está acima de iniciante consegue ler”
    Se “alguns iniciantes conseguem ler” for o alvo de otimização, vejo retornos decrescentes muito grandes; em vez disso, miro em algo que “acima de iniciante” — ou, em alguns casos, “nível intermediário ou acima” — consiga ler

• Há muitos motivos para usar qualquer linguagem, e muitos motivos para não usar. Mas o ponto central não é a notação curta, a clareza relativa nem a capacidade de compilar para código rápido; é se o programador que vier depois conseguirá modificar e manter esse código para uso real
  Com frequência demais, programadores querem mostrar suas habilidades leet e não levam em conta os pobres coitados que terão de assumir aquele código depois. Na prática, muito código leet precisa ser descartado ou completamente reescrito para se obter algo sustentável no longo prazo
  Levei muito tempo para entender isso e, depois, passei a tentar escrever código limpo, simples e compreensível para que outras pessoas pudessem mantê-lo. Código descartável muitas vezes acaba virando a infraestrutura básica da organização e se cristaliza em algo incompreensível para a próxima geração