Pensando em linguagens de arrays

Pensando na linguagem K

• A programação em K é feita principalmente por meio de um REPL.
• O rlwrap do ngn/k permite navegar pelo histórico com as teclas de seta, o que é útil para desenvolver programas maiores.
• As funções são testadas no REPL antes de serem levadas para o código de fato.
• A saída formatada do ngn/k sempre retorna dados K válidos e pode ser pré-calculada para melhorar a velocidade do programa.
• Scripts K são executados como se tivessem sido digitados no REPL, e o valor de retorno de cada linha é exibido, a menos que termine com ponto e vírgula.
• Scripts permitem definições em múltiplas linhas, o que ajuda na legibilidade.
• Para salvar o trabalho em um script e usá-lo no REPL, é possível executar o arquivo e carregar os dados com \lfile.k.
• É possível carregar o arquivo várias vezes no REPL para sobrescrever dados anteriores.
• A ajuda do REPL, acessada com \, contém vários comandos úteis.

Simplificação da programação com arrays

• Programação com arrays é um processo contínuo de simplificar padrões complexos em padrões menores, mais declarativos e mais fáceis de ler.
• A forma de simplificar padrões complexos é discutida em detalhes em "Patterns and anti-patterns in APL: escaping beginner's plateau - Aaron Hsu - Dyalog '17".

Conversão da multiplicação de matrizes para K

• É possível converter diretamente para K o algoritmo iterativo de multiplicação de matrizes retirado de um artigo da Wikipédia.
• O pior exemplo de código convertido para K exige muitas atribuições de variáveis globais, loops aninhados e muitas mutações.
• É possível simplificar o código resolvendo esses problemas um a um.

Simplificação do loop interno

• No loop interno, sum pode ser simplificado usando fold (/).
• Como ' (each) retorna um array, a variável global C pode ser removida.
• Os loops podem ser simplificados removendo as variáveis i, j e k.

Remoção de loops e minimização de variáveis globais

• É possível remover o loop intermediário combinando diretamente linhas e colunas sem k.
• Para remover j, é possível parear cada coluna de B com A[i].
• Para remover i, é possível usar eachleft para parear cada linha de A com cada coluna de B.
• Variáveis globais deixam de ser necessárias.

Forma final da função de multiplicação de matrizes

• + (transpose) é custoso, então pode ser removido.
• Em vez de multiplicar cada linha de x por cada coluna de y, é possível fazer implicitamente o mesmo ajustando cada linha de B a toda a matriz A.
• No fim, obtém-se uma função de multiplicação de matrizes concisa e explícita.
• O processo de simplificação do código passa por várias etapas no início, mas tende a se tornar mais fácil e intuitivo à medida que a familiaridade com K aumenta.
• A multiplicação de matrizes é um procedimento simples que combina bem com o suporte a arrays em K.
• Em capítulos futuros, serão vistos mais algoritmos que não se encaixam tão bem em K e como lidar com eles.

Opinião do GN⁺

• Este texto mostra como usar a linguagem K para simplificar e otimizar algoritmos como a multiplicação de matrizes.
• O feedback imediato via REPL e a melhoria iterativa do código são características centrais da programação em K e também um método de aprendizado útil para engenheiros de software iniciantes.
• O processo de simplificação do código é importante para desenvolver a habilidade de programação, e este texto o explica de forma concreta e fácil de entender por meio de exemplos específicos.

[GN⁺]

Comentários do Hacker News

• Várias pessoas levantam dúvidas sobre a utilidade e a compreensibilidade das linguagens de array.

  • Linguagens de array não servem para todo problema.
  • São surpreendentemente competentes para muitos tipos de problema.
  • Usuários de linguagens de array em geral são muito inteligentes.
  • Aprender como linguagens de array funcionam é um grande desafio.
  • Escrever código "procedural" em linguagens de array é uma péssima ideia.
  • Entender programação tácita (tacit programming) é uma experiência incrível que expande a mente.
  • A experiência de internalizar verb trains.
  • Entender como linguagens baseadas em arrays lidam com arrays de qualquer dimensão.
  • Entender como under funciona.
  • Entender como funcionam os expoentes de função (function exponents).

• Há muitos aspectos surpreendentes nas linguagens de array, e a lista acima é só uma parte.

  • Ao acompanhar Aaron Hsu desenvolvendo um compilador APL paralelo, isso convenceu a pessoa do real potencial das linguagens de array.
  • Discussão sobre a "densidade semântica" (semantic density) do código APL.

• Se você nunca ouviu falar de programação de arrays e quer uma introdução, a recomendação é "The Array Cast".

• A pessoa descobriu APL/APL2 nos anos 70 e se apaixonou, mas sentiu ainda mais atração pela capacidade de compor funções.

  • Haskell, por ser puro e tipado, é mais divertido e poderoso que APL.
  • A "notação como ferramenta do pensamento" do APL parece uma lógica para justificar concisão excessiva.

• Principal percepção ao usar linguagens de array:

  • Verbos são algoritmos.
  • Uma sequência de verbos (ou advérbios) é a forma de composição mais direta que a pessoa já usou.
  • Um programa é a composição de algoritmos, não um conjunto de instruções e expressões.
  • O conceito de tratar domínio e contradomínio de forma consistente em arrays, mapas e funções.
  • Avaliação da esquerda para a direita, sem precisar que os olhos "fiquem pulando" ao ler o código.
  • É possível, e preferível, enviar código aos dados.
  • Benefícios adicionais da linguagem K: é possível implementar views (isto é, dependências) diretamente, e fazer hot code loading pelo interpretador.

• Pergunta sobre linguagens de array: como realizar uma tarefa como "encontrar todos os números menores que N para os quais a condição P é verdadeira"?

  • Em linguagens de array, em geral cria-se um array de 1 até N, testa-se a condição no array e depois aplica-se uma máscara para obter apenas os elementos em que a condição é verdadeira.
  • Se N for grande e a condição raramente for verdadeira, criar temporários demais parece desperdício de memória e recursos.
  • Implementações de linguagens de array podem otimizar esse problema ou resolvê-lo com técnicas como avaliação preguiçosa (lazy evaluation).

• Experiência com a linguagem J: o paradigma das linguagens de array é enviesado, e não há certeza de que pensar todo problema como aninhamento de arrays realmente ajude.

  • Poder criar livremente estruturas de dados que simplifiquem o problema pode reduzir bastante a complexidade algorítmica.
  • Para usar APL/J/K, é preciso ser mais inteligente por causa desse viés.

• Impressão ao resolver problemas na linguagem K: K é deliberadamente obscura.

  • É uma linguagem boa para quebra-cabeças e soluções engenhosas, mas trabalhar com arrays numpy em Python também ensina linguagens de array e como pensar em arrays.

• Exemplo na linguagem de array J: dot =: +/ . * é usado para calcular o produto escalar (dot product) de P e Q.

• A gramática de K é mais curta, mas é preciso manter na cabeça muito contexto embutido sobre como a linguagem K funciona.