Elmord's Magic Valley

Software, lingüística, mitologia nórdica e rock'n'roll

Blueprints for a shell, parte 4: Ramblings on syntax

2015-03-17 01:10 -0300. Tags: comp, prog, pldesign, shell, lash

Este post é parte de uma série sobre o lash, um shell que eu estou ideando.

Hoje discutiremos algumas questões sintáticas do shell. Depois disso eu provavelmente vou dar uma pausa na série e tentar implementar um protótipo do lash, mesmo com algumas questões ainda em aberto. Em particular, falta falar sobre estruturas de controle (mas o básico (if, while, each) não tem muito o que discutir) e módulos (que vão ficar para o futuro).

O meu objetivo ao escolher a sintaxe do shell é achar um ponto de equilíbrio entre minimalismo sintático total (e.g., S-expressions1) e ter sintaxe especial para tudo (e.g., bash). No geral, o guiding principle é expor a maior parte das funcionalidades do shell por meio de funções, e usar sintaxe especial apenas quando seria inconveniente escrever uma chamada de função, especialmente para features freqüentemente usadas em modo interativo (e.g., redirects e pipelines). Este post é uma survey dos elementos sintáticos do (ba)sh e como eles serão representados em lash.

Comandos simples

A sintaxe básica de um comando em (ba)sh é, em BNF fuleiro:

command ::= {var=value}* {word | redirect}*

A semântica é: se há words no comando, a primeira word é o nome do comando a ser executado, e as demais são os argumentos. O comando é executado em um ambiente acrescido das variáveis de ambiente especificadas, e com os redirects em efeito. Se não há words, as variáveis especificadas (do shell, não de ambiente) recebem os valores atribuídos, e os redirects... bom, aparentemente não fazem nada, mas isso depende da variante de sh, porque o comportamento aparentemente é indefinido no padrão POSIX. A ordem de avaliação das coisas também é um pouco peculiar:

bash# a=$(date >&2) uname $(pwd >&2) 2>/dev/null
/tmp
Mon Mar 16 21:27:09 BRT 2015
Linux

dash# a=$(date >&2) uname $(pwd >&2) 2>/dev/null
/tmp
Linux

Vale notar que os redirects e as words podem aparecer intercalados na linha de comando (inclusive minha BNF está errada, porque redirects podem aparecer intercalados com as atribuições também); a ordem em que eles aparecem relativos aos outros elementos sintáticos parece ser irrelevante.

Em lash, depois de muita hesitação, eu decidi atirar pela janela as atribuições prefixadas; o comando env do Unix já serve para rodar comandos em um ambiente modificado (env FOO=bar comando). Eu pensei em obrigar os redirects a aparecerem no final, mas me dei conta de que pode ser útil escrever um redirect intercalado em comandos que recebem blocos. e.g.:

each_line </etc/passwd {|line|
    echo "bla bla $line"
}

Ainda não sei até que ponto isso pode ser útil, mas por enquanto fica aí. Fica a questão da ordem de avaliação. A remoção das variáveis prefixadas são uma coisa a menos na equação. Quanto ao momento em que os redirects tomam efeito, há algumas possibilidades:

  1. Antes de tudo, afetando inclusive chamadas a comandos com $(...), $[...] e companhia. Tem o detalhe de que o redirect em si também pode envolver avaliação (ls >$[generate-a-file-name]). Nesse caso o redirect evidentemente só pode ter efeito depois do comando.
  2. Depois da avaliação de tudo e imediatamente antes de executar o comando propriamente dito. Aparentemente é isso que o bash faz.
  3. O redirect afeta a avaliação de tudo o que aparece depois dele na linha de comando, i.e., 2>/dev/null foo $(bar) afeta a execução de bar, mas foo $(bar) 2>/dev/null não.

Por ora o plano é fazer como o bash, primariamente porque sim.

Fica ainda a questão da atribuição, já mencionada anteriormente: usar um comando para atribuição (set x = 42), ou tratar o = especialmente no parser? Eu não gosto muito de casos especiais, mas talvez a atribuição mereça tratamento especial. Eu nem sei se atribuição (por oposição a definição de uma nova variável) é particularmente freqüente em um script para justificar um caso especial.

Quoting

O bash possui uma porção de coisas quote-like:

O plano para o lash é:

Outra utilidade de strings com delimitador (semi-)arbitrário é que elas supririam a funcionalidade dos "here-documents" do bash, os quais veremos adiante.

Here-documents

Here-documents permitem embutir um trecho de texto, delimitado por uma string à escolha, a ser enviado para a entrada padrão (ou outro file descriptor) do comando a ser executado:

cat <<FIM >foo.txt
The quick brown fox
jumps over the lazy dog.
FIM

Por padrão, o shell realiza substituições no conteúdo do here-document. Se o delimitador for citado/escapado, o conteúdo é interpretado literalmente. Além disso, se o delimitador é precedido de -, espaços e tabs no começo de cada linha são descartados.

Em alguma versão o bash introduziu também "here-strings", que permitem usar uma string simples ao invés de um documento multi-linha como entrada:

sed 's/foo/bar/' <<<"$content"

Se o lash adotasse um mecanismo para strings com delimitadores (semi-)arbitrários, como a contra-aspa descrita anteriormente, seria possível unificar esses dois casos. Strings com delimitador arbitrário podem ser usadas também para inicializar variáveis, por exemplo, coisa que não é possível com here-documents em bash.

Parameter substitution

O bash possui uma dúzia de coisas da forma ${varsomething}, que permitem fazer alguma transformação sobre o valor de uma variável. Além de a sintaxe ser abstrusa, a string a ser manipulada tem que estar armazanada em uma variável (não pode ser o resultado de outra substituição, por exemplo; para aplicar múltiplas substituições é necessário armazenar os resultados parciais em uma variável). O plano em lash é substituir todas as substituições (heh) por funções.

Existe um pequeno problema envolvido: o bash distingue entre ${var//$match/$replacement} e ${var//"$match"/$replacement}. No primeiro caso, *, ? e similares dentro de $match têm seus significados de globbing, enquanto no segundo eles são interpretados literalmente. Esse problema afeta outras coisas que trabalham com patterns. No comentário linkado (que trata da função glob, que retorna uma lista dos arquivos que casam com um padrão), a solução que eu encontrei foi usar uma format string para separar as partes que devem ser interpretadas como pattern das partes que devem ser interpretadas literalmente (assim como printf em C separa a string de controle de strings incluídas com %s e que são usadas literalmente), mas no caso de substituições não sei se seria muito conveniente – talvez agrupando o pattern e seus argumentos em um array:

# Equivalente a ${string//"$match"*/"$replacement"} em bash.

subst $string ("%s*" $match) $replacement

Kinda weird, mas eu consigo sobreviver. Na verdade, acho que o melhor seria tratar o pattern como literal por padrão, senão certo que alguém vai escrever $[subst $var $match $replacement] sem nem pensar se $match contém asteriscos ou não, e aí vai ser outra daquelas situações em que um script funciona 99% do tempo, até que um dia alguém resolve usar uma string com * e o script tem um comportamento inesperado. A sintaxe de subst poderia ser:

Qual a sua opinião?

Outra situação que usa patterns e sofre do mesmo problema é o case, que a princípio há de ser um comando comum sem sintaxe especial (case STRING (PATTERN-1 BLOCO-1 ... PATTERN-N BLOCO-N)2). Idealmente a sintaxe adotada para as substituições deverá ser utilizada para o case também.

And, or, not

Em (ba)sh, comando1 && comando2 executa comando1 e, se este retornar 0 (i.e., verdadeiro), executa comando2. O exit status do comando como um todo é o exit status do último comando que for executado. Analogamente, comando1 || comando2 executa comando1 e, se este retornar não-zero (i.e., falso), executa comando2. Em ambos os casos, comando é um "comando completo", que pode envolver pipelines. Há dois casos de uso principais desses operadores:

Portanto, eles permanecem.

! nega o exit status do comando (troca de não-zero para 0 e de 0 para 1). Ele também se aplica a um "comando completo", negando uma pipeline inteira (o exit status de uma pipeline é o exit status do último comando), e essa seria a única razão que eu vejo para tratá-lo como sintaxe especial e não apenas um comando chamado !. Não sei se justifica; além de ser uma situação bem rara, nada impede de simplesmente escrever o ! antes do último comando da pipeline. Além disso, talvez fosse o caso de escrever ! {comando1 | comando2} anyway, por clareza. While we are at it, podíamos renomear o comando para not, para deixar mais claro que se trata de um comando comum e não sintaxe especial, mas aí já não sei.

Process substitution

Em bash, <(comando) cria um pipe (um par de file descriptors em que tudo que entra numa ponta sai na outra), executa comando com a saída padrão redirecionada para o lado entrante do pipe, e a expressão é substituída por um nome de arquivo que corresponde ao lado de saída do pipe. Por exemplo, é possível escrever:

diff <(sort file1) <(sort file2)

que executa sort file1 e sort file2 e chama algo como diff /dev/fd/63 /dev/fd/62. Analogamente, >(comando) executa comando com a entrada padrão vinda da ponta de saída do pipe, e a expressão é substituída por um nome de arquivo correspondente à ponta de entrada.

Embora essa sintaxe seja bastante conveniente para usar na linha de comando (e na verdade acho que o exemplo com o diff é o único que eu já usei na linha de comando na vida), não sei se eu quero mantê-la em lash. Não só pelo princípio de evitar sintaxe extra gratuita, mas também porque ela parece um redirecionamento, mas é uma word. Se eu quisesse redirecionar um file descriptor para o resultado do process substitution (o que é útil primariamente para fazer um pipeline com um file descriptor que não seja a stdout, e.g., redirecionar a stderr para um comando), eu teria que escrever algo como (o espaço é necessário):

ls 2> >(comando)

o que não é exatamente óbvio. Talvez uma função desse conta do recado, algo como:

diff $[popen -r {sort file1}] $[popen -r {sort file2}]

Ok, a cara disso é terrível3. Talvez se a popen ganhar outro nome, e o comando aceitar um nome de comando e argumentos diretamente ao invés de obrigatoriamente um bloco:

diff $[readfrom {sort file1}] $[readfrom {sort file2}]
diff $[pipefrom {sort file1}] $[pipefrom {sort file2}]
diff $[pipefrom sort file1] $[pipefrom sort file2]

Não sei.

Outro problema com a sintaxe do bash é que o comando parece um array, e talvez um array fizesse sentido como alvo do redirect (redirecionaria para todos os nomes de arquivo no array). Por outro lado, o caso do array poderia ser representado pelo array "spliced", qualquer que seja a sintaxe escolhida para ele (e.g., >$@(file1 file2)), ou simplesmente permitindo múltiplos redirects do mesmo file descriptor (>file1 >file2; o zsh permite isso, acho). Não sei.

Humanitas precisa dormir

Por hoje ficamos por aqui. Como sempre, tudo o que eu digo que "é" de tal jeito é só o plano atual, tudo está sujeito a discussão, comentários e sugestões são sempre bem-vindos, live free or die, do what you want 'cause a pirate is free, etc. Como esse é, a princípio, o último post da série for a while, sinta-se a vontade para comentar aqui sobre tópicos não abordados até agora na série.

_____

1 Em tempos de outrora eu pensei em usar S-expressions para toda a sintaxe (inclusive redirecionamentos e pipelines), mas permitir omitir os parênteses em torno de comandos que aparecem sozinhos em uma linha. O resultado não me foi exatamente satisfatório. Além disso, turns out que um shell totalmente baseado em S-expressions já foi feito (o qual por sinal provavelmente é uma boa fonte de inspiração).

2 Os patterns e blocos vão em um array primariamente para permitir que eles ocupem múltiplas linhas sem ter que pôr um \ no final de cada linha:

case $file (
    "*.mp3" { ... }
    "*.ogg" { ... }
    "*" { ... }
)

3 Revisando o post, eu olhei para isso e pareceu a sintaxe mais natural do mundo, mas a essa altura minha percepção já está meio alterada pelo sono.

7 comentários

Blueprints for a shell, parte 3: Tipos de dados

2015-03-13 22:47 -0300. Tags: comp, prog, pldesign, shell, lash

Este post é parte de uma série sobre o lash, um shell que eu estou ideando.

A world made of strings

Em (ba)sh só existe um tipo de dado: a string. Em bash, uma variável pode ser declarada como um array (e em versões mais recentes, como um dicionário), mas embora a variável seja um array, o array em si não é um valor de primeira classe: não é possível passar um array como argumento para uma função, ou armazenar um array dentro de outro, por exemplo. Isso limita um bocado o que se pode fazer em bash sem apelar para gambiarras do inferno. (Claro que "dá" para viver sem essas coisas. Também "dá" para programar com máquinas de Turing...)

lash quebra com a tradição, se revolta contra o sistema e introduz arrays, dicionários e blocos de primeira classe (bem como possivelmente outros objetos, como canais de comunicação, mas isso ainda está em aberto). Assim, é possível fazer coisas futurísticas como manter uma coleção de dados estruturados e escrever funções para manipular arrays e produzir outros arrays. Fantástico, não? Welcome to 2015.

Independentemente do shell, variáveis de ambiente e argumentos de processos no Unix também são strings (e strings que não podem conter \0, ainda por cima), o que significa que não temos como passar diretamente nossos valores estruturados para outros processos. Uma abordagem alternativa seria fazer como Tcl: representar tudo como strings, definir certos formatos de string para armazenamento de dados estruturados (e.g., keyed lists, ou XML if you're feeling crazy), e prover funções para interpretar e manipular tais strings. Isso permitiria passar dados "estruturados" para subprocessos, pois eles seriam apenas strings. Mas, seriously, guardar tudo como string e parsear/procurar dentro da string para obter um elemento de uma lista/dicionário? Gerar uma string nova toda vez que se altera um elemento? Tá certo que seria possível mitigar um pouco esses problemas usando alguma representação interna mágica para strings, mas sei lá. Por ora eu prefiro ter dados estruturados normais.5 Além disso, blocos têm que ser dados especiais de qualquer forma, para carregar informação de escopo.

So, tipos de dados.

Strings e números

Uma string em lash é uma seqüência de bytes; internamente, o shell não está preocupado com a interpretação desses bytes (como caracteres codificados em UTF-8, por exemplo). No geral, o ambiente Unix como um todo não está preocupado com o conceito de codificação; nada exige que nomes de arquivo sejam strings UTF-8 válidas, por exemplo, e o resultado de um globbing deveria ser representável por strings do shell sem nenhum mistério. Arquivos/streams também não tem nenhuma codificação inerente, e coisas como echo $str não deveriam ter que fazer nada de mágico para decidir como mandar o conteúdo da string para o arquivo. Interpretar os bytes de uma string como UTF-8 (ou outro encoding) é responsabilidade das funções que o shell provê para manipular strings.

Acho que em um shell não faz muito sentido ter um tipo numérico distinto. Em um shell, quando se escreve algo como my x = 01, espera-se que o 0 permaneça lá; quando se chama xargs -0, espera-se que o - não se perca, etc. Além disso, os argumentos que o script recebe da linha de comando são todos strings, e não me parece interessante ter que convertê-los manualmente para números antes de fazer operações aritméticas com eles. Ao invés disso, a interpretação de uma string como um número cabe aos operadores aritméticos. Por questão de eficiência, o resultado de uma operação aritmética pode ser armazenado internamente como um número (a idéia é evitar ter que converter o resultado para string e reconverter para número caso ele seja usado novamente em uma operação aritmética), mas isso não é observável pelo script.

Diferentemente do (ba)sh, o lash deverá suportar aritmética de ponto flutuante. Isso levanta a questão de como distinguir divisão inteira de divisão em ponto flutuante. Eu sou favorável a adotar / para divisão em ponto flutuante e // para divisão inteira, a la Python 3. Os demais operadores aritméticos produzem resultado em ponto flutuante se um dos argumentos for float, e inteiro caso contrário. A representação em string de um número em ponto flutuante sempre inclui um ponto1 (a idéia é que se alguma coisa estiver produzindo resultados float indevidamente, isso não vai passar silenciosamente durante a execução (ou assim se espera)). Operações aritméticas sobre strings que não são números válidos produzem um erro de execução, i.e., nada de NaN propagation a la JavaScript ou interpretação implícita como 0 a la PHP. Na verdade nem o bash deixa esse tipo de coisa passar em silêncio... com algumas exceções: uma string vazia é tratada como um 0, e espaços em torno de um número são ignorados. Aqui fico na dúvida entre "strictness" e conveniência; talvez em um script seja uma boa aceitar esses dois casos.

Strings não são arrays, e (assim como em bash) não são indexáveis com a sintaxe normal de arrays. Haverá funções para obter substrings, mas ainda não pensei bem nos nomes e na sintaxe, e em como especificar o range de bytes/caracteres desejado (início e tamanho? início e fim? inclusivo ou exclusivo? Todas as opções, dependendo dos parâmetros?). Uma possibilidade seria:

Pode ser meio verboso, mas captura de substring parece ser uma coisa relativamente rara em bash, baseado em um grep na minha amostra extremamente significativa de meia dúzia de scripts que estavam à mão, então acho que a clareza e a flexibilidade compensam a verbosidade.

O tamanho da string pode ser obtido com as funções bytelen e charlen, dependendo do tipo de tamanho desejado. (Há ainda a situação em que se quer a largura impressa da string (combining characters não contam no comprimento, e caracteres chineses-et-al ocupam duas posições), bem como substrings baseadas na posição impressa dos caracteres, mas isso vai ficar para o futuro distante, possivelmente numa biblioteca.)

Funções que trabalham com delimitadores (e.g., split STRING DELIM) têm que aceitar delimitadores de tamanho arbitrário, pelo simples fato de que elas têm que funcionar com delimitadores em UTF-8 e ao mesmo tempo se manterem agnósticas quanto à codificação. (Por outro lado, isso assume que a codificação tem a mesma propriedade do UTF-8, de que é possível identificar o começo de um caractere inambiguamente a partir de um ponto arbitrário na stream, o que basicamente só é verdade no UTF-8 e em encodings em que 1 byte = 1 caractere. Meh.)

Arrays

Arrays são seqüências de valores quaisquer. A sintaxe literal para arrays é (valor1 ... valorN). (Os parênteses são herdados da sintaxe de inicialização de variáveis-array do bash. Além disso, colchetes e chaves já têm outros usos. Isso a princípio conflita com a sintaxe do (ba)sh para rodar um comando em um subprocesso4 (( comandos )), mas eu já não pretendia ter essa sintaxe em lash to begin with. Uma função poderia prover essa funcionalidade (e.g., subproc { comandos }).)

Arrays são indexados com a sintaxe $var[expr]. Assim como em bash, expr é avaliado como uma expressão aritmética, sem necessidade de escrever $var[$((expr))]. Diferentemente de bash, chaves não são exigidas, i.e., não é necessário escrever ${var[expr]}. Por um lado isso é mais limpo, mas por outro pode conflitar com o uso de [] como wildcard, e.g., my prefix = /dev/tty; echo $prefix[1-8]. Acho que isso não chega a ser um grande problema, pois isso gera um erro de execução ($prefix não é um array), e portanto é fácil de detectar e corrigir (para ${prefix}[1-8]; dá até para incluir essa informação na mensagem de erro).

Assim como em bash, o array tem que estar em uma variável para ser indexado ($[função][expr] não seria interpretado como uma indexação do resultado de função, a princípio (ou seria?)), mas nada impede que haja uma função index ARRAY N, com a qual se poderia escrever $[index $[função] N].

A sintaxe de atribuição funciona com arrays também (var[i] = 42). Isso implica que atribuição tem que ter tratamento sintático especial, para que coisas como var[i*i] = 42 não causem globbing.

Como fica o caso de arrays multidimensionais (i.e., arrays que contêm outros arrays)? $var[i][j] é uma sintaxe válida? Se sim, não tem por que não aceitar $[função][expr] também, acho.

É possível atribuir a uma posição que ainda não existe (a la Perl), ou isso é um erro (a la Python)? Se a "label" do índice é importante (e não apenas a ordem), não seria o caso de usar um dicionário anyway? Eu consigo pensar em duas situações em que se poderia querer especificar um índice não-existente explicitamente:

  1. Adicionar um elemento no fim do array. Mas para esse caso poderia haver uma função push (ou append, porque aí também podemos ter uma prepend para adicionar no começo; ou poderia haver uma função mais geral insert, para inserir um elemento entre dois quaisquer, ou no início/fim), ou uma sintaxe a la PHP (var[] = 42).
  2. Inicializar um vetor/matriz com alguma fórmula matemática, e.g.:
    my array = ()
    range 0 -toin 10 {|i|
        array[i] = $(( i * i ))
    }
    

    Parece um caso de uso razoável, mas de qualquer forma ele falha com arrays multidimensionais ($array[i][j] = 42 é um erro porque $array[i] não é um array, a menos que seja inicializado primeiro). Pode-se suprir esse caso com uma função make_matrix que recebe o tamanho das dimensões e retorna um vetor inicializado.

Ou podemos permitir atribuição out-of-bounds (e preencher qualquer elemento entre a última posição preenchida e a posição atribuída com a string vazia) e era isso. Não sei (o plano inicial é não permitir).

Outra função básica de manipulação de arrays é each, que recebe um array e um bloco e chama o bloco com cada elemento do array. Também pode haver uma map, que produz um novo array com cada resultado retornado pelo bloco, e uma versão destrutiva de map (chamada map!, talvez2).

A função len retorna o número de elementos do array. Não sei se há necessidade de uma sintaxe especial para isso (e.g., $#var).

$@var "splices" o array, produzindo um argumento ("word" na terminologia do (ba)sh) para cada elemento do array, i.e.:

my array = (1 2 3)
foo $array         # chama foo com um argumento (o array)
foo $@array        # chama foo com três argumentos (1, 2 e 3)

Dicionários

Um dicionário é um mapeamento de strings para valores. (Por que só strings? Talvez faça sentido permitir valores quaisquer como chave.) A sintaxe literal para dicionários é %(chave1=valor1 chave2=valor2 ...) (o % é para sugerir uma vaga relação com hash-tables em Perl), com espaços opcionais em torno do =, o que fica meio estranho sem delimitadores entre os pares chave = valor, mas pode-se usar quebras de linha se desejado:

my person = %(
    name = Hildur
    age = 18
    country = Iceland
)

[Note to self: Em coisas como %(foo=(1 2 3)), assim como em my foo=(1 2 3), foo=(1 2 3) não é uma "palavra" normal do shell, porque é parte string, parte array, i.e., tanto dicionários literais quanto declaração de variável exigem tratamento especial pelo parser (a menos que haja um tipo de dados "associação" ao qual coisas da forma A=B possam ser mapeadas).]

Elementos de um dicionário são acessados com a sintaxe $var{chave}. Não se usa colchetes como em arrays porque a expressão entre colchetes sofre avaliação aritmética, que não é o que queremos em um dicionário. (Será que foi uma boa idéia fazer avaliação aritmética automática after all?) Isso é outro elemento de sintaxe (além dos blocos) que conflita com a sintaxe de brace expansion do bash (foo{1,2,3}). Não sei se isso é um ponto a favor da mudança da sintaxe de acesso a dicionário ou do brace expansion. Outra possibilidade seria usar colchetes, assim como arrays (e aí eles perdem a propriedade de avaliação aritmética, o que pode tornar o acesso a array meio inconveniente), ou talvez $var<chave>, mas isso conflita com a sintaxe de redirecionamento. (Lembrando que isso poderia ser um redirecionamento se $var contivesse um file descriptor. Nesse caso o > posterior seria um erro de sintaxe, então só a interpretação como acesso a dicionário seria válida, mas eu só descubro isso quando chego no >; além disso a chave não poderia ter um espaço não-escapado. Fora que é uma sintaxe totalmente não-usual para acesso a dicionário (as chaves pelo menos têm precedente em Perl).)

Se my dict = %(a=1 b=2 c=3), qual o resultado de $@dict?

Haveria uma porção de funções para iterar sobre dicionários: each-key; each-value; each-entry, que reberia um dicionário e um bloco de dois argumentos e o chamaria com a chave e o valor de cada entrada no dicionário; ou, havendo o tipo associação, chamaria o bloco com cada associação. Alternativamente, havendo o pipeline de objetos, poderia haver uma função keys que produz todas as chaves, e aí escreveríamos keys $dict |> each {|key| ... } (ou qualquer que seja a sintaxe do pipe de objetos), e da mesma forma para os valores (e associações, em as havendo).

Será que é uma boa ter um tipo dicionário distinto de array, ou o melhor é unificar os dois a la PHP, JavaScript, etc.? Acho que eu prefiro ter dois tipos separados, mas há de se pensar melhor.

Interações entre valores estruturados e strings

Em (ba)sh, diferentemente das linguagens de programação em geral, uma variável pode aparecer como parte de uma "palavra" maior, e.g., foo$bar; o conteúdo da string é concatenado na palavra e era isso. Mas e se $bar não for uma string? Pode-se produzir uma versão serializada do valor (o que provavelmente é mais útil), ou gerar um erro.

Coisas como foo$@bar (onde my bar = (1 2 3)) poderiam expandir para foo1 foo2 foo3, como o brace expansion do bash. O problema é que $@ assume que o array está em uma variável. Daria para expandir arrays literais também3, e,g., foo(1 2 3) geraria foo1 foo2 foo3, e aí seria possível eliminar o uso de chaves para brace expansion. O problema é que by far o meu uso mais freqüente de brace expansion na linha de comando é com a string vazia, e.g., mv file{,~} ao invés de mv file file~, e na nova sintaxe isso seria mv file("" ~) (na verdade o ~ teria que ser escapado para não sofrer tilde expansion...). Talvez dê para sobreviver.

^D

Por hoje ficamos por aqui. Como sempre, tudo o que foi apresentado são só os planos e idéias atuais, tudo pode ser mudado, e comentários e sugestões são muito bem-vindos (mas provavelmente só vou ver/responder comentários depois do fim-de-semana).

_____

1 Ou talvez um e+42 da vida (talvez só como formato de entrada válido, mesmo que as operações do shell sempre produzam resultados em notação decimal).

2 (update) Ou adicionar uma opção -overwrite à função map (que parece uma coisa mais shell-like); ou ainda, adicionar opções -collect e -overwrite à each e nem ter uma map separada.

3 (update) Note' to self: Isso também é uma string misturada com um array, então o my x=(1 2 3) não é mais um caso especial para o parser (ou pelo menos para o "reader", porque ainda teria uma interpretação diferente do caso foo(1 2 3)).

4 (update) Na verdade não conflita, porque um array não faz sentido como primeira coisa na linha de comando (ou faz?).

5 (update) Parafraseando um grande sábio, "If you want Tcl, you know where to find it." (Dito isso, eu vejo mérito na abordagem "everything is a string".)

4 comentários

Blueprints for a shell, parte 2: Variáveis, definições e escopo

2015-03-13 00:11 -0300. Tags: comp, prog, pldesign, shell, lash

Este post é parte de uma série sobre o lash, um shell que eu estou ideando.

Um pouco de contexto

Em (ba)sh todas as variáveis são globais (inclusive as "locais", que são globais com escopo dinâmico). Independentemente das variáveis do shell, todo processo no Unix possui um conjunto de variáveis de ambiente (environment variables). Os shells tendem a unificar variável do shell e de ambiente de alguma forma. A maneira como isso é feito em (ba)sh é tratar todas as variáveis uniformemente como "do shell" e marcar certas variáveis como "exported": essas variáveis são passadas como variáveis de ambiente para os processos chamados pelo shell. Além disso, o bash possui um comando local, que faz com que os valores atribuídos às variáveis passadas ao local a partir desse ponto só durem até a função onde o local foi chamado retornar, i.e., o local permite "shadowar" uma variável durante a execução de uma função. Funções chamadas pela função que declarou a variável "local" também vêem o novo valor, e nada impede "localizar" uma variável de ambiente (que continua sendo uma variável de ambiente).

Nessa situação, determinar a que variável o código está se referindo ao dizer $x é uma questão bastante simples: só existe uma variável x no programa inteiro. Evitar conflitos de nomes é basicamente problema do programador.

Se isso já é um problema em bash, em um shell com lambdas isso seria um disastre, pois um bloco de código pode ser chamado dentro de uma função diferente da que o definiu, e quem escreve o bloco não necessariamente tem como saber (nem deveria ter que saber) os nomes das variáveis usadas nesse outro ponto do programa. Assim, lash adota escopo léxico, como qualquer linguagem sã, o que significa que pode haver múltiplas variáveis com o mesmo nome em um programa. Isso também implica que nós vamos ter que conciliar escopo léxico com variáveis de ambiente.

So, variáveis em lash

O comando my introduz variáveis léxicas, cujo escopo é o bloco onde o my se encontra. A sintaxe básica é:

my nome = valor

Eu estou meio na dúvida quanto ao uso de espaços em torno do =. Em bash, atribuição de variável não permite espaços. Não havendo espaços, seria possível definir múltiplas variáveis no mesmo comando:

my x=1 y=2 z=3

Com espaços, para a coisa continuar legível, acho que seria necessário introduzir um delimitador entre as atribuições, mas isso não é tão simples em um shell, porque em:

 my x=1, y=2, z=3

a vírgula poderia ser parte da string que se está atribuindo. Uma alternativa é permitir declarar uma única variável com espaços, ou múltiplas variáveis sem espaços. A sintaxe não é ambígua, de qualquer forma.

Pergunta: uma definição com my x=1 afeta referências a x no mesmo bloco que apareçam antes do my? Por exemplo, em:

my x = 1
while {true} {
    echo $x
    my x = 2
    echo $x
}

que x é visto pelo primeiro echo quando o while executar pela segunda vez? Ou, de maneira mais convoluta:

my x = 1
my block = {
    my f = { echo $x; }
    my x = 2
    $f
}

imprime o valor de qual x? Se o desejado for o 1, então a implementação de variable lookup tem que tomar o cuidado de não simplesmente pegar o primeiro x subindo na hierarquia de ambientes (a princípio o bloco interno procuraria a variável x primeiro no ambiente do próprio bloco, depois no bloco em que o bloco se encontra, depois fora dos blocos). Por outro lado, essa semântica em que a referência a uma variável nunca muda, independente de declarações posteriores, permitiria resolver tudo estaticamente, o que pode deixar o lookup com uma performance melhor. Outra questão é: esse tipo de coisa acontece na prática? Eu fico seriamente tentado a dizer que é indefinido nesses casos qual das duas variáveis é acessada. Provavelmente alguém vai querer comer meu fígado por introduzir comportamento indefinido em um shell, mas eu não estou propondo nada da natureza de comportamento indefinido em C, em que o programa pode fazer qualquer coisa, incluindo roubar seu dinheiro e fugir do país; certamente uma das duas variáveis é acessada, sem nenhum efeito inesperado. A idéia é apenas manter em aberto a possibilidade de diferentes implementações de lookup de variáveis. Se você acha que isso é uma má idéia, por favor se manifeste.

Atribuição

Estou na dúvida se atribuição vai usar uma keyword do tipo set, ou se só o sinal de igual vai ser suficiente. Parece concebível que alguém invente um comando que recebe = como argumento, então:

foo = 42

poderia ser uma chamada a foo. Esse problema poderia ser evitado exigindo set foo = 42, ou proibindo os espaços em volta do = (que é o que o (ba)sh faz), mas o espaço me parece bem desejável quando o valor atribuido é uma expressão maior com chamadas a funções e what-not, ou quando o lado esquerdo é um array[índice]. Por outro lado, não lembro de nenhum comando que recebe = como primeiro argumento, então talvez tratar um = não escapado/quoted na segunda posição como algo especial e dispensar o set não seja problema. Será?

Também há de se considerar a possibilidade de introduzir outros operadores de atribuição, como +=, e nesse caso, se haverá operadores separados para strings, números e arrays ou se um só basta. (Em bash, += appenda strings e arrays; olhando o lado direito da atribuição dá para saber qual é o caso. Para incrementar variáveis numéricas, é necessário estar em "modo de expressão aritmética", i.e., dentro de ((...)), $((...)), índice de array, etc.)

O que acontece ao se atribuir um valor a uma variável não declarada? Acho que isso seria no mínimo um warning, talvez um erro. Acessar uma variável não-definida também, mas seria bom ter alguma coisa equivalente ao ${var:-default}, i.e., "usa o valor de $var, ou a string default caso var não esteja definida (ou seja vazia, se o : estiver presente)". Eu tinha pensado em ter uma função or valor1 valor2, que devolve valor1 se ele for um valor diferente da string vazia (ou um valor nulo especial? nós teremos um?), ou valor2 caso contrário. O problema é que $[or $var default] vai emitir um warning se $var não estiver definida. Talvez pudesse haver uma sintaxe especial $?var que devolve o valor da variável ou vazio caso ela não exista, sem emitir um warning, e então o equivalente do ${var:-default} seria $[or $?var default]. Meio verboso, mas não parece ruim (eu acho).

Variáveis globais

Nós teremos um sistema de módulos (cujos detalhes eu ainda não pensei direito e que será assunto de um post futuro), e concebivelmente um módulo poderá querer tornar algumas variáveis visíveis a outros módulos. Possibilidades:

Separar variáveis públicas das demais parece uma boa, mas não sei se não é "só uma coisa a mais".

Funções

Funções e variáveis vivem em namespaces separados em (ba)sh, e a princípio isso deve ser mantido em lash. Em (ba)sh, todas as definições de função possuem escopo global (na verdade tudo tem escopo global em (ba)sh). Como já comentado anteriormente, embora possa parecer "óbvio" mudar isso em lash e tornar as definições de função léxicas, assim como as variáveis, código como:

if {some-condition} {
    def foo {
        ...
    }
}

em que se espera que a definição de foo resultante seja global, é comum em arquivos de configuração e afins. Possibilidades:

  1. def define funções globais, i.e., no escopo do módulo em que a definição foi feita. (No escopo léxico, ou no escopo dinâmico? Se um bloco que contém um def é passado como argumento e chamado em uma função definida em outro módulo, em que módulo o def tem efeito? Bom, a julgar pelo if, no módulo em que o def se encontra, i.e., no escopo léxico.) Não há definições locais de função e era isso.
  2. def define funções globais, mas é possível escrever algo como my def foo { ... } para definir uma função local. Pode ser uma boa, só não sei se vale a pena o esforço. Também teria algum efeito no lookup de funções/comandos que precisa ser melhor considerado.
  3. def define funções no escopo léxico local. Bagunça com o caso do def dentro de um if, mas isso poderia ser contornado permitindo algo como public def foo { ... } dentro do if. (Mas quem disse que eu queria exportar do módulo? Também poderia ser usada uma keyword diferente (e.g., global), que torna global mas não exporta do módulo.)

No momento eu estou inclinado à alternativa (1), mas aceito contra-argumentos.

Funções definidas em um módulo são visíveis a partir de outros módulos por default, ou é necessário dizer public def foo { ... } para exportar uma função? (Lembrando que a gente nem decidiu ainda se vai ter uma keyword public ou não na linguagem...)

Variáveis de ambiente

O escopo de uma variável de ambiente a princípio é o processo inteiro. (É possível conceber que cada módulo pudesse ter sua própria idéia de ambiente, mas acho que nunca antes na história desse país uma linguagem tratou variáveis de ambiente assim.) Em um shell, espera-se acessar variáveis de ambiente com a mesma sintaxe das variáveis comuns (acho inventar uma sintaxe nova para dizer $HOME não vai ser uma proposta popular). Outra peculiaridade das variáveis de ambiente é que seus valores só podem ser strings. Seria possível serializar outros valores para permitir passá-los como variáveis de ambiente para subprocessos, mas só o lash reconheceria essas variáveis como valores especiais, e seria necessário indicar de alguma maneira reliable que a variável contém um valor especial, e não uma string que parece muito com um valor especial. Depois do causo do ano passado com o Shellshock, eu estou meio receoso de permitir coisas que não sejam strings em variáveis de ambiente.

Em bash uma conseqüência não muito agradável de o shell misturar as variáveis de ambiente com as comuns é que é possível um script começar a usar uma variável feliz da vida sem saber que havia uma variável de ambiente com o mesmo nome. Isso é agravado pelo fato de que em bash uma variável inexistente pode ser usada sem warning nem erro (a menos que set -u esteja ativo), então um script pode ser escrito assumindo que uma dada variável está vazia e inadvertidamente herdar do ambiente uma variável com conteúdo. Mesmo que esse não seja o caso e o script inicialize suas variáveis antes de usar, ele ainda pode estar inadvertidamente alterando uma variável de ambiente, que será herdada por subprocessos.

Em lash a situação a princípio é menos problemática porque toda variável tem que ser declarada antes de usar, e um my sobrepõe uma variável de ambiente de mesmo nome. Em geral, se eu esquecer de declarar a variável, o shell emitirá um erro, então um script que roda sem erros para mim pelo menos está imune a variáveis de ambiente inesperadas presentes nos sistemas dos outros, mas eu ainda posso acabar esquecendo o my sem gerar erro se der o acaso de eu usar um nome de variável que é uma variável de ambiente presente no meu sistema. Soluções:

  1. Exigir que toda variável de ambiente usada seja explicitamente importada antes do uso. Acho que isso não seria uma opção muito popular. Talvez não fosse tão ruim se algumas variáveis mais tradicionais fossem importadas por default (e.g., HOME, USER), mas isso me parece super-arbitrário.
  2. Permitir o acesso a variáveis de ambiente como qualquer outra variável, mas permitir atribuição apenas com um comando especial (e.g., setenv HOME = /). Acho que isso pega como erro a grande maioria das capturas indevidas de variáveis de ambiente. Fica o caso de se o programador erra o nome da variável de ambiente (uma nova variável seria criada, ao invés de emitir um erro). Evitar esse problema acho que traria mais inconveniente do que vantagem.
  3. Não fazer nada. Na real isso mal é uma opção, já que o setenv tem que existir de qualquer forma para criar variáveis de ambiente novas, e uma vez que ele exista não tem por que não aplicar a solução (2).

So (2) it is, aparentemente.

Escopo dinâmico

E quando eu quero escopo dinâmico, after all? Pode-se argumentar que ninguém em sã consciência quer escopo dinâmico, mas, por exemplo, se formos implementar o tal pipeline de objetos, precisamos de um meio de redirecionar o canal de saída de um comando para o canal de entrada de outro, e uma maneira de fazer isso é ter os canais de entrada e saída como variáveis dinâmicas e shadowá-las para fazer o redirecionamento; é como normalmente se redireciona *standard-output* e companhia em Common Lisp, e (current-output-port) et al. nos Schemes que suportam "fluid variables" (que são variáveis dinâmicas com outro nome).

Se formos ter variáveis dinâmicas, para evitar o caos manifesto, parece uma boa exigir que elas sejam previamente declaradas como tal (i.e., não é possível "localizar" a la bash uma variável previamente declarada com my). Também há o problema de como implementar o escopo dinâmico. Na situação em que só há uma thread, a operação de shadowar uma variável pode ser implementada simplesmente salvando o valor antigo, atribuindo o valor novo, e depois restaurando o valor antigo. Quando há múltiplas threads, entretanto, deseja-se que um shadow dentro de uma thread não afete as outras. E guess what? O nosso pipeline de objetos exige que cada parte do pipeline rode simultaneamente (ou pelo menos cooperativamente), dentro do mesmo processo, e o que cada uma vê como canal de entrada e de saída é diferente, então essa implementação "ingênua" de shadowing não nos serve.

Eu tenho um certo receio de que, a menos que as variáveis dinâmicas sejam identificáveis estaticamente, a presença delas bagunce / afete a performance do lookup de todas as variáveis. Quando a definição da variável dinâmica está lexicamente visível é fácil distingui-las, mas quando elas vêm de outro módulo, isso pode ser complicado. Uma solução é simplesmente usar uma sintaxe diferente para acessar variáveis dinâmicas, e.g., earmuffs: $*output_channel*. Essa sintaxe tem a vantagem de ser imediatamente familiar ao grande contingente de programadores de Common Lisp (right?), e a desvantagem da potencial confusão com o * que faz globbing (e.g.:

dynamic *prefix* = foo
touch foo1 foo2 foo3
echo $*prefix**

), mas outra sintaxe que distinguisse variáveis dinâmicas de variáveis comuns poderia ser escolhida.

Acho que por hoje deu

Reiterando, sempre que eu digo que alguma coisa em lash "é" de tal e tal jeito, eu só quero dizer que esse é o plano atual, mas estou aberto a sugestões. Feedback é sempre bem-vindo.

8 comentários

Blueprints for a shell, parte 1: Funções, blocos e retorno

2015-03-11 23:15 -0300. Tags: comp, prog, pldesign, shell, lash

Este post é parte de uma série sobre o lash, um shell que eu estou ideando.

Hoje vamos discutir a feature que dá nome ao shell, lambdas, ou blocos. (Na verdade eu pensei no nome primeiro e fiquei com ele porque consegui pensar num significado que o justificasse, mas não vamos nos ater a esses detalhes.)

(Em diversos pontos ao longo do texto eu vou dizer que certa feature em lash "é" de tal e tal jeito. Isso só significa que essa é a minha idéia atual sobre a feature, não que eu tenha decidido definitivamente que isso vai ser assim. Comentários e sugestões são sempre bem-vindos.)

Como mencionado anteriormente, a idéia em lash é usar blocos extensivamente ao invés de sintaxe especial para estruturas de controle (if, for, while, etc.). Blocos em lash são valores de primeira classe, i.e., podem ser passados como argumento para funções, por exemplo. Um bloco instanciado é uma closure, i.e., ele lembra do ambiente de variáveis em que foi criado. No geral, variáveis em lash têm escopo léxico, e não escopo dinâmico como em (ba)sh. (A coisa não é tão simples por conta de variáveis de ambiente e outros detalhes, mas discutiremos isso no futuro.)

Blocos são escritos entre chaves ({ comandos }). Blocos podem receber parâmetros, que podem ser declarados com uma sintaxe Ruby-like: {|param1 param2 ... paramN| comandos }. O último parâmetro pode ser precedido de @; nesse caso, ele coleta em um array os argumentos restantes da chamada ao bloco.

Não sei se permitir $1, $2, etc., para acessar os argumentos de um bloco é uma boa idéia; como tudo é bloco em lash, acho que isso ia dar muita confusão ao tentar acessar um argumento de função de dentro de um if e situações similares. Melhor é requerer que os parâmetros sejam declarados. ($1 e companhia talvez possam adquirir outros usos, e.g., em matching de expressões regulares, mas esse é um tópico que eu não vou abordar any time soon.)

Now the thorny questions.

Arity mismatch

O que acontece se o número de parâmetros e de argumentos não casar? No geral o ideal é gerar um erro de execução ou um warning, mas eu me pergunto se não há situações em que pode ser interessante permitir passar um bloco sem parâmetros para uma função que chama o bloco com alguns argumentos, nos quais o bloco não tem interesse. (Por exemplo, o if poderia chamar o bloco do "then" com o resultado retornado pelo teste do if, no qual não temos interesse a maior parte do tempo.) Uma possibilidade seria não permitir mismatch, exceto no caso em que o bloco não tem declaração de parâmetros at all, i.e., {|| true; } 42 é um erro, mas { true; } 42 não é. Mas eu imagino que isso possa fazer funções declaradas sem parâmetros engolirem silenciosamente argumentos passados por engano. Por ora, acho que mismatch vai ser sempre um erro/warning mesmo, enquanto não aparecer um caso de uso que definitivamente sugira que o contrário é desejável.

Retorno

Quando eu digo return 42, quem retorna? O comportamento esperado é retornar da função em que o return se encontra, mas agora o corpo de um if ou foreach tecnicamente também é uma função, que provavelmente não é a função que o usuário tem em mente ao escrever um return.

Se o return retorna da função "esperada", também há o caso em que um bloco que contém um return é passado para uma função definida pelo usuário e chamada de dentro dessa função; nesse caso o return é um non-local exit, i.e., a função que retorna é a função onde o bloco foi definido, não a função que chamou o bloco. (Na verdade o caso do return dentro do if também é um non-local exit, mas é um caso com o qual nós já estamos acostumados.) Outros casos de controle de fluxo não-local são os comandos break e continue dentro de um while. Talvez fosse interessante introduzir uma construção mais geral a partir da qual esses casos mais específicos podem ser implementados, e que também poderia ser usada para implementar exceções. Ao mesmo tempo, eu gostaria que um return fosse uma operação "barata", então é necessário tomar algum cuidado antes de sair over-engineerando controle de fluxo. A construção que naturalmente "suggests itself" para a tarefa é continuations e call/cc, mas esse caminho me dá um certa preocupação, especialmente se continuações que retornam múltiplas vezes forem permitidas. (Incidentalmente, eu pretendo implementar as versões iniciais do shell em Chicken Scheme, o que tornaria tudo isso muito simples, mas eu quero manter aberta a possibilidade de reimplementar em alguma outra linguagem no futuro (e.g., Rust, depois que ele sair de alpha).) Além disso, seria necessário lidar com unwind-protect / dynamic-wind / interação de tratadores de exceção com continuations. Eu não estou gostando muito de toda essa complexidade que surgiu do nada enquanto eu estava tranqüilo aqui inventando meu shell.

Outra dificuldade é como fazer o return, que a princípio seria um comando como qualquer outro, retornar do bloco lexicamente apropriado, já que ele não recebe como argumento nada que lhe sirva para saber de que escopo léxico ele foi chamado. Ele não pode só retornar do contexto mais no topo da pilha de chamadas porque o return pode ser não-local. Por exemplo, em um código como:

def foo {
    bar {|x| return $x}
}

def bar {|block|
    $block 42
}

o return que será executado quando $block for invocado deve retornar de foo, não de bar. Uma solução é fazer todo comando receber implicitamente um argumento escondido que representa o escopo em que o comando foi chamado. That's kinda weird (e me lembra o &environment das macros do Common Lisp e o "dynamic environment argument" em Kernel), mas pode funcionar. Outra solução é fazer def (o comando de definição de função) introduzir uma função local return no escopo do corpo da função, i.e., cada função vê um return diferente, mas a princípio eu não pretendia nem introduzir funções nomeadas locais (more on that later).

Também dá para simplesmente tratar def, return e companhia como special operators e era isso. Eu não queria introduzir nenhum special operator na linguagem, mas talvez isso não seja muito prático. Preciso pensar melhor sobre isso. (No fim das contas, return, break e continue trabalham com escopo léxico, enquanto exceções e unwind-protect trabalham com escopo dinâmico, então a "óbvia" unificação dos conceitos não é tão direta assim.)

Funções locais

A princípio o filosoficamente correto seria que definições de função tivessem escopo léxico, assim como as variáveis. Porém, me parece que coisas do tipo:

if {whatever} {
    def foo {
        ...
    }
}

que define uma função global ou não dependendo de uma condição, são comuns em scripts e bashrcs da vida. Daria para introduzir comandos separados para definir funções locais e globais, mas realmente não vejo muita utilidade para funções locais (além de blocos anônimos) em um shell. Se você discorda, por favor se manifeste.

(Por um lado dá para argumentar que se você realmente precisar de uma função local, pode declarar uma variável local e atribuir um bloco a ela. Por outro lado, há a diferença de que o return dentro de um bloco retorna da função externa, não do bloco. Essa questão do return não vai deixar de me assombrar tão cedo.)

Sintaxe

O uso de chaves para delimitar funções conflita com o uso de chaves em bash, que expande coisas como touch {1,2,3}.txt para touch 1.txt 2.txt 3.txt, bem como coisas como {01..99} para 01 02 ... 99. Uma solução para evitar a ambiguidade é, ao encontrar um {, continuar lendo até o primeiro espaço ou }, e se houver uma , ou .. não-escapado na string lida, considerar como um brace expansion, caso contrário como um bloco. Eu detesto esses look-aheads em parsing, mas talvez seja o caminho a seguir. (O próprio bash já faz alguma distinção contextual com relação às chaves, tratando chaves em comandos como cmd arg1 {arg2 arg3 como caracteres literais, mas em bash o parsing se dá em múltiplos passos, em que primeiro ocorre word splitting e depois brace expansion, o que torna esse tipo de coisa relativamente simples. No caso de blocos, não dá para realizar word splitting primeiro porque o bloco é mais do que só uma seqüência de "words" comuns.) Outra solução é mudar a sintaxe do brace expansion, que sequer é parte do sh to begin with (é uma extensão do bash). Discutiremos alternativas quando falarmos de arrays, em um post futuro.

Returning and replying

Comandos no Unix possuem duas formas primárias de retornar informação para o chamador:

Queremos um mecanismo que permita retornar quaisquer valores, inclusive dados estruturados como listas e blocos. Eu vejo algumas possibilidades:

  1. Estender o conceito de exit status para permitir quaisquer valores, não apenas inteiros entre 0 e 255. O problema com essa abordagem é conciliá-la com o conceito de verdadeiro e falso convencional do (ba)sh: quando meu valor de retorno é um dado arbitrário, eu provavelmente quero que a maioria dos valores sejam tratados como verdadeiro, e coisas como 0, a string vazia, a lista vazia, etc., sejam tratados como falso.
  2. Estender o conceito de stdout para permitir enviar valores arbitrários, não apenas bytes. Isso é uma idéia muito legal, e abre caminho para a implementação de um "pipeline de objetos", mas envolveria uma certa mandinga para tratar a stdout comum do Unix e a stdout de objetos transparentemente. Também tem a vantagem de que se a saída não é capturada, ela é impressa para o terminal, o que faz sentido em modo interativo. Por outro lado, provavelmente muitas vezes queremos rodar um comando apenas pelos side-effects e descartar a saída, e ficar redirecionando para /dev/null every now and then pode ser inconveniente (embora seja possível inventar uma sintaxe abreviada para isso). Além disso, isso impede que uma função cujo valor de retorno esteja sendo capturado possa imprimir normalmente para a stdout.
  3. Criar um novo mecanismo de retorno independente dos dois anteriores. Essa é a solução mais straightforward, e por enquanto é a minha working hypothesis, mas tem a desvantagem de criar um conceito extra. Para diferenciar o retorno de um valor do retorno de um exit status convencional, eu adotei a palavra reply ao invés de return (que continua existindo com seu significado convencional).

A sintaxe para chamar uma função e capturar o valor de retorno por enquanto é $[comando], pelo simples fato de que ela não está sendo usada para mais nada (em bash ela é uma sintaxe deprecated para avaliação aritmética, que hoje em dia se escreve $((expressão))), e, pode-se argumentar, porque lembra a função dos colchetes em Tcl. Eu me pergunto se ${comando} não seria uma escolha melhor, pois tem mais cara de "executa este bloco e pega o valor", mas essa sintaxe é usada em (ba)sh para delimitar nomes de variável (e.g., echo "Eu sabia essa com ${fruta}s), e não sei se é uma boa mudar isso.

Uma questão é se o reply de fato retorna da função, ou só "emite" o valor de retorno. Se o mecanismo de retorno escolhido for o (1) ou o (3), faz mais sentido retornar e sair da função, mas se a escolha for o (2), faz mais sentido emitir o valor, como se fosse um print, e seguir a execução, até porque seria possível imprimir múltiplos valores, no caso do pipeline de objetos (e aí fica a questão de como $[...] se comporta se o comando emite múltiplos valores).

Awey?

Por hoje ficamos por aqui. Como sempre, feedback é muito bem-vindo.

11 comentários

Blueprints for a shell, parte 0: Visão geral

2015-03-10 22:32 -0300. Tags: comp, prog, shell, pldesign, lash

Sim, meus caros, o mui lendário e prometido shell que eu estou há anos dizendo que quero escrever está mais perto do que nunca de talvez ser escrito. Isso se deve a uma decisão de vida curiosa que me deixou com mais tempo para projetos pessoais, pelo menos por enquanto.

A questão é: tem um trilhão de decisões de design que eu preciso tomar e que eu gostaria de pensar bem sobre e discutir antes de começar a implementar. Assim, me pareceu uma boa escrever sobre elas aqui para me ajudar a organizar as idéias e coletar comentários, sugestões e opiniões. A idéia original era escrever um único post com tudo, mas eu comecei a fazer isso ontem e me dei conta de que ele ia acabar ficando gigante. Então, o plano agora é escrever uma série de posts. Neste aqui, apresentarei as idéias básicas do novo shell, e nos próximos pretendo entrar nos detalhes de features mais específicas, tais como tipos de dados, quoting, closures, estruturas de controle, módulos, escopo de variáveis e afins.

Por que um novo shell?

Eu já escrevi um post (gigante) sobre o assunto antes, mas basicamente: o shell é uma péssima linguagem de programação. Embora o bash tenha adquirido inúmeras features ao longo dos anos, coisas que se esperam de qualquer linguagem de programação que se leve a sério, tais como dados estruturados de primeira classe e a possibilidade de retornar valores de funções sem criar um subprocesso, não existem até hoje. Acho que existe um círculo vicioso na evolução dos shells: shells não são vistos como linguagens de programação "de verdade" por seus usuários por terem programabilidade pobre, e os desenvolvedores de shells não melhoram a programabilidade do shell porque não há demanda dos usuários. A premissa do novo projeto é romper com essa idéia e tornar o shell uma linguagem "decente" como Perl, Python ou Ruby, sem entretanto perder as características que tornam um shell conveniente, i.e., a facilidade de chamar e combinar programas de linha de comando e de utilizá-lo como uma interface interativa para o sistema operacional.

Objetivos gerais

Eis uma lista das idéias básicas que hão de guiar o desenvolvimento desse novo shell.

A sintaxe de uso interativo freqüente deverá permanecer largamente igual à do (ba)sh. Coisas como redirecionamentos simples (>, >>, <), pipes, globbing (*.txt, /dev/tty[1-8]), tilde expansion (cd ~/Desktop), etc., manterão a mesma sintaxe. A sintaxe dessas coisas é tradicional demais (e familiar até a usuários de ambientes não-Unix), então me parece melhor mantê-la igual, mesmo que isso limite as escolhas sintáticas para outras funcionalidades do shell.

Dito isto, compatibilidade com (ba)sh não é um objetivo do shell. A manutenção da sintaxe das funções mais comuns é mais uma questão de compatibilidade com os usuários de shell do que com os shells propriamente.

Uma das features mais importantes do shell novo é o suporte a dados estruturados de primeira classe. Isto é, arrays e dicionários podem ser armazenados em variáveis, dentro de outros arrays e dicionários, passados como argumento para funções, retornados por funções, etc. Isso implica a adição de um mecanismo para retorno de valores complexos por funções, bem como uma sintaxe para chamar uma função e capturar seu valor de retorno, sem criar um subshell para isso (diferente do $(...) do (ba)sh).

Outra feature importante é o suporte a closures, ou blocos de código de primeira classe. Isso permite a substituição de diversas estruturas de controle que têm sintaxe especial no (ba)sh (if, for, while, etc.) por comandos simples que recebem blocos de código como argumento, e também permite que novas estruturas de controle sejam definidas pelo usuário.

O suporte a closures e a funções com valores de retorno complexos nos possibilita fazer uma grande limpeza na sintaxe do shell, substituindo certos elementos de sintaxe questionável (e.g., ${var,,*}) por equivalentes mais legíveis (e.g., $[lowercase $var]). A idéia é inicialmente ter o mínimo de sintaxe especial. Porém, sintaxe minimalista não é necessariamente um princípio sagrado, e se for observado que algumas operações são freqüentes o suficiente para justificar uma sintaxe especial, tal sintaxe pode vir a ser acrescentada ao shell.

O shell deve facilitar a escrita de scripts robustos. Em (ba)sh é muito fácil escrever um script que aparentemente funciona corretamente, mas falha diante de nomes de arquivo com espaços ou quebras de linha, ou comandos que usam * ou ? com seu sentido literal e funcionam 99% do tempo, mas falham misteriosamente ocasionalmente, porque coisas como *~ são mantidas intactas pelo (ba)sh quando não há nenhum arquivo que case com o padrão, o que faz com que o comando funcione ou não dependendo do conteúdo do diretório atual, ou porque o (ba)sh expande caracteres epeciais em situações inesperadas. O shell deve ter um comportamento consistente, fácil de "reason about", sem dependências mágicas de contexto e do ambiente do usuário.

Uma preocupação secundária mas importante é que o shell deve ser razoavelmente rápido. Não necessariamente rápido como uma chita, mas idealmente com uma performance equiparável à de Python ou Ruby. (Isso não precisa ser uma preocupação inicialmente, mas é bom mantê-la em mente durante o design da linguagem.) O bash é absurdamente lento, e shell scripts em geral tendem a ser lentos por terem que usar comandos externos para diversas coisas que em outras linguagens seriam builtins ou bibliotecas. O que nos leva ao próximo item...

O shell deve ter suporte a bibliotecas, módulos ou algo do tipo para reuso de código. Idealmente, também deve ser possível escrever bibliotecas/módulos compilados que possam ser utilizados por scripts. Isso permite a adição de features sem engordar o shell. Deve ser fácil distribuir e instalar bibliotecas para o shell. Idealmente, também deve ser fácil determinar e instalar (semi-)automaticamente as bibliotecas das quais um script depende. Deve ser possível isolar namespaces para evitar conflitos de nomes.

Finalmente, features interativas, como edição de comandos e histórico, não devem ser parte do core do shell. Com suporte a bibliotecas/módulos, não há por que colocar essas funcionalidades no binário principal e carregá-las ao rodar scripts, que não precisam delas.

Remarks on syntax

O fato de que o shell deve ser conveninete de usar interativamente, e de que desejamos manter um mínimo de "compatibilidade de usuário" com a sintaxe tradicional do sh, impõe certas restrições nas escolhas sintáticas do shell. Por exemplo, em uso interativo, strings literais são mais freqüentes do que variáveis, então faz sentido que strings não exijam aspas e variáveis sejam introduzidas por um símbolo especial ($). < e > possuem significados convencionais, então embora às vezes seja muito tentador utilizá-los como delimitadores para alguma outra coisa, o melhor é deixá-los em paz.

Essas restrições fazem com que seja difícil escolher uma sintaxe para certas features que seja "ergonômica" para programar e ao mesmo tempo não interfira e se encaixe direito com o resto do shell. Até hoje eu não encontrei uma sintaxe para capturar o resultado de uma função que me agrade totalmente, por exemplo.

Dito isso, embora eu seja da opinião de que "syntax matters", eu cheguei à conclusão de que, pelo menos inicialmente, considerações sintáticas não são tão importantes assim, já que em geral a sintaxe pode ser alterada mais adiante sem muito impacto no resto do projeto (pelo menos enquanto ele não for oficialmente released e não tivermos que lidar com esse negócio de "usuários"). Assim, vou aceitar por ora uma certa dose de bizarrice sintática quando não houver uma escolha obviamente melhor, deixando aberta a possibilidade de mudanças futuras.

Um outro fator ao qual eu pretendo dar um peso importante ao definir a sintaxe é o que podemos chamar de dificuldade de interpretação incorreta. Por exemplo, eu costumava não ir muito com a cara do uso de my em Perl para declarar variáveis locais, mas ele tem o mérito de deixar claro (para mim, pelo menos) que trata-se de uma declaração de variável (e não uma atribuição a variável já existente), e que o escopo dela é o bloco em que se encontra (e não a função ou o módulo ou whatever). let também é relativamente claro, mas let é um comando que faz algo diferente em bash (avaliação de expressões aritméticas e atribuição (não declaração)), então talvez seja melhor evitar essa palavra (mas ainda estou meio em dúvida).

Um contra-exemplo é a sintaxe para declaração de variáveis de ambiente temporárias: em um comando como

LC_ALL=C find /home | grep '[^A-Za-z0-9]'

o LC_ALL=C vale só para o find, ou para o grep também? (Resposta: só para o find.) Em um comando como

foo=42 echo $foo

$foo está no escopo da definição ou não? (Resposta: não.) No geral, acho preferível escolher uma sintaxe que não deixe dúvida de qual é a interpretação correta. Similarmente, se alguma distinção é importante, pode ser melhor obrigar o usuário a especificá-la ao invés de usar um default que freqüentemente pode não ser o que o usuário quer, ou que pode induzir ao erro alguém lendo o código escrito por outra pessoa. Por exemplo, eu não pretendo ter uma função len para strings no shell, mas sim funções como bytelen (número de bytes), charlen (número de codepoints Unicode) e charwidth (largura do texto na tela), exigindo que o programador seja específico quanto a o que quer dizer com "comprimento" da string. (Esses nomes ainda são meio questionáveis, pois o encoding das strings (que supostamente é UTF-8) fica implícito, mas ainda não pensei com calma sobre o assunto.)

A teaser

Embora por enquanto nada esteja muito bem definido, para tornar as coisas um pouco mais concretas, eis um exemplo da cara que eu imagino que a tal linguagem vai ter:

# Função que retorna um dicionário contendo a quantidade de usuários
# que usam cada shell.

def count_shell_users {
    my counts = %()
    each_line </etc/passwd {|line|
        my (user pass uid gid name home shell) = $[split $line ":"]
        counts{$shell} = $(( $[or $counts{$shell} 0] + 1 ))
        # (A sintaxe da linha acima provavelmente não é definitiva.)
    }
    reply $counts
}

# Função que retorna todos os elementos de uma lista que satisfaçam um predicado.

def filter {|list predicate|
    my result = ()
    each $list {|item|
        if {$predicate $item} {
            push $result $item
        }
    }
    reply $result
}

# Exemplo de uso.
my dirs = $[filter (/etc/*) {|x| isdir $x}]

Por hoje é só

Por hoje ficamos por aqui. Nos próximos episódios trataremos de tópicos mais específicos. Perguntas, sugestões, opiniões, comentários, tanto sobre os tópicos abordados quanto sobre outras coisas que você gostaria de ver (ou não) num shell, são muito bem-vindos.

(By the way, não havendo conflito com nenhum projeto ativo, o shell a princípio deverá se chamar lash (lambda shell).)

8 comentários

O que são capabilities e o que elas têm de tão mágico

2014-04-19 08:39 -0300. Tags: comp, prog, unix, security

Eu já falei de capabilities por aqui algumas vezes antes. Neste post tentarei explicar o que elas são e por que eu acho que elas são a panacéia universal (ok, não, mas por que eu acho que elas são um avanço em comparação com as permissões convencionais do Unix).

(Antes de mais nada, gostaria de ressaltar que as capabilities a que eu me refiro aqui não têm nada que ver com o que o Linux chama de capabilities, que são basicamente uma maneira de separar o tradicional balaio de poderes do root em unidades que podem ser atribuídas individualmente a processos (e.g., com isso é possível dar a um processo o poder de alterar o relógio do sistema sem conceder todos os outros poderes de root junto).)

Ok, que diabos são capabilities?

Uma capability é um objeto ou "token" que representa a habilidade de um processo de acessar um certo recurso, tal como um arquivo ou uma conexão de rede. Capabilities possuem três propriedades importantes:

Turns out que file descriptors no Unix possuem essas três propriedades. Ao abrir um arquivo no Unix, o processo recebe um número inteiro que é um índice na tabela de file descriptors do processo, que é acessível apenas pelo kernel. File descriptors abertos podem ser passados adiante para os filhos de um processo ou transferidos via sockets. Uma vez aberto o arquivo, as credenciais do processo são irrelevantes para o seu acesso: um processo pode, por exemplo, começar executando como root, abrir um recurso privilegiado (e.g., ouvir em uma porta menor que 1024), e depois trocar de credenciais para um usuário menos poderoso sem perder o acesso ao recurso privilegiado, pois a posse do file descriptor da conexão é suficiente para garantir-lhe acesso ao recurso. (Um file descriptor não é uma capability pura porque conserva outros dados além dos necessários ao acesso do recurso, tais como a posição do cursor no arquivo, o que dificulta seu uso compartilhado por outros processos depois de transmitido, mas em essência trata-se de uma capability.)

A mágica de um modelo de segurança baseado em capabilities, entretanto, é que todo acesso a recursos é feito por meio de capabilities, e um processo tem acesso apenas aos recursos representados pelas capabilities que lhe são entregues. No Unix, por outro lado, um processo recebe acesso implícito e mais ou menos inevitável a diversos recursos, tais como o filesystem e a habilidade de criar conexões de rede. É possível cercar o acesso a esses recursos, e.g., usando chroot para entregar um filesystem alternativo ao processo (mas não é possível não entregar filesystem nenhum ao processo) ou regras de firewall para bloquear o acesso do processo à rede (geralmente indiretamente, e.g., rodando o processo com outro usuário e bloqueando o usuário no iptables), mas há uma série de dificuldades e inconvenientes envolvidos:

A raiz do problema é que o modelo de segurança do Unix foi criado no contexto dos sistemas multi-usuário dos anos 1970, em que a preocupação primária era proteger os usuários uns dos outros e o sistema dos usuários. Hoje em dia as preocupações são outras: no caso de computadores pessoais, a maioria das máquinas roda com um único usuário, e queremos proteger o usuário de programas potencialmente mal-comportados (seja por conterem vulnerabilidades, seja por descuido do programador, seja porque o programa é intencionalmente malicioso) que o próprio usuário executa. No caso de servidores, queremos minimizar o potencial de desastre caso um serviço seja comprometido. Capabilities se encaixam melhor (acredito) com essas preocupações do que o modelo de segurança tradicional do Unix, pois permitem um controle maior de o que um processo é capaz de acessar. Ao invés de passarmos aos programas o acesso ao filesystem inteiro e os nomes de arquivos que queremos que o programa manipule, passamos capabilities aos arquivos de interesse, sem entregar o acesso a todo o resto do filesystem junto. Ao invés de chamar todos os programas com o poder de abrir conexões de rede, podemos passar esse poder apenas aos processos que realmente tenham que ter esse acesso.

E o browser?

A essas alturas você talvez esteja se perguntando: "Ok, meu filho, e como isso resolve o problema do browser? Eu não vou ter que entregar uma capability para acessar todos os meus arquivos para o caso de eu querer fazer upload de um deles? Hã? Hã?"

A solução é uma das coisas mais legais que se consegue fazer com capabilities. Lembre-se de que capabilities podem ser transmitidas entre processos. Isso significa que nós podemos ter um daemon (chamemo-lo fileopend) capaz de fornecer capabilities. Ao iniciarmos o browser, passamos a ele uma capability que é um canal de comunicação com o fileopend. Quando o usuário vai fazer upload de alguma coisa, ao invés de o browser abrir a janelinha de "Abrir arquivo", ele manda uma requisição de abertura de arquivo ao fileopend. O fileopend, então, mostra a janelinha de "Abrir arquivo" ao usuário. O usuário escolhe o arquivo, e então o fileopend o abre e envia a capability correspondente àquele arquivo específico para o browser. O browser, assim, só tem acesso a arquivos que o usuário tenha selecionado explicitamente na janela de "Abrir arquivo".

Genial, hã?

And we can do it right now!

Atualmente existe um projeto chamado Capsicum: practical capabilities for UNIX, que teve bastante progresso recentemente. Trata-se de uma implementação de capabilities no FreeBSD, que está sendo adaptada para o Linux. O projeto inclusive produziu uma versão do Chromium baseada em capabilities, usando uma idéia análoga à do fileopend (que eles chamam de "user angels") para abrir arquivos do usuário.

Mas teoricamente, seria possível implementar capabilities em user-space no Unix com uma pequena dose de faconice. No cenário mais simples, seria possível rodar cada processo com um usuário/grupo diferente (gerar um UID/GID para cada processo novo), em um chroot, com acesso à rede bloqueado no firewall, etc., apenas com um canal de comunicação com um daemon que intermediaria o acesso dos processos a todos os recursos, tais como arquivos, conexões de rede, etc. Esse daemon faria o papel do kernel em um sistema com suporte nativo a capabilities. O problema com essa abordagem é performance: todo acesso a recursos teria que passar pelo canal de comunicação entre os processos comuns e o daemon. Porém, uma vez que file descriptors podem ser transmitidos por sockets no Unix, seria possível usar o daemon apenas para criar e transmitir file descriptors (capabilities) para os processos. Uma vez de posse do file descriptor, o processo pode utilizar o recurso "nativamente". A perda de performance seria apenas na abertura de recursos, e talvez não fosse tão significativa. Anyway, graças ao Capsicum, estamos em vias de ter capabilities nativas no Linux (hopefully no kernel mainline) sem ter que apelar a gambiarras.

Unix is dead. Long live Unix.

Comentários

NSA operation ORCHESTRA, e alguns pensamentos sobre o estado atual da computação

2014-04-17 01:29 -0300. Tags: comp, prog, security, politics, ramble

No FOSDEM (Free and Open Source Developers' European Meeting) deste ano, Poul-Henning Kamp deu uma palestra muito interessante intitulada "NSA operation ORCHESTRA - Annual Status Report" (video, slides). A palestra, apresentada na forma de um report de um programa fictício da NSA, explora a idéia de o que a NSA poderia estar fazendo para coletar o máximo de informação com o menor custo possível. Possibilidades incluem:

Como diz nos slides da palestra, "A intenção foi fazer as pessoas rirem e pensarem, mas eu desafio qualquer um a provar que não é verdade."

A única coisa que não me agrada nessa palestra é a conclusão de que "this is a political problem" e de que é inútil fazer qualquer coisa do ponto de vista técnico. As ações da NSA são um problema político, mas: (1) isso não quer dizer que não possamos ou devamos buscar eliminar fontes de vulnerabilidades no software existente; (2) esse tipo de sabotagem poderia vir igualmente de uma organização privada com recursos suficientes, então o problema não é puramente político, no sentido de que mesmo nos livrando de governos maliciosos, o problema não desapareceu.

Ação política é importante, mas como desenvolvedores de software podemos tomar atitudes para mitigar o efeito de ações maliciosas sobre software. Para começar, podemos parar de usar ferramentas da idade da pedra, que facilitam a introdução (acidental ou deliberada) de falhas de segurança, como C/C++. O potencial de insegurança no C/C++ não é o mero descuido na hora de calcular os índices e o tamanho de um vetor (que por si só já é uma eterna fonte de vulnerabilidades). Em C/C++ existe o conceito de comportamento indefinido (undefined behavior), e cada versão nova do GCC/Clang/[insira seu compilador C/C++ favorito aqui] sai "melhor" em explorar comportamento indefinido para fins de otimização do que a anterior. A idéia básica é que se um programa realiza certas ações "proibidas" pelo standard da linguagem (e.g., acessar um elemento além do final de um vetor), o comportamento resultante do programa não é especificado pelo standard, então o compilador é livre para gerar um programa que faz qualquer coisa nesses casos. Por exemplo, suponha que você escreve algo como:

void foo(struct pessoa_t *pessoa) {
    int idade = pessoa->idade;

    if (pessoa == NULL)
        printf("Oops, pessoa inválida!\n");
    else
        printf("A idade da pessoa é %d.\n", idade);
}

pessoa é um ponteiro (potencialmente nulo) para uma estrutura de dados. Acessar o conteúdo apontado por um ponteiro nulo é um comportamento indefinido: um programa que faz isso é um programa incorreto. Logo, o compilador é livre para gerar código que não funciona no caso de o ponteiro ser nulo. Logo, o compilador pode assumir que pessoa não é um ponteiro nulo: se a hipótese do compilador for verdade, o programa estará correto, e se não for, tanto faz se o programa está correto. Mas se o ponteiro não é nulo (por hipótese), então o if na função é redundante (pois a condição é sempre falsa): o compilador pode descartar as linhas cor-de-burro-quando-foge do código resultante, como uma otimização. Foi exatamente uma otimização desse tipo que transformou um erro de programação no kernel do Linux em uma falha de segurança alguns anos atrás. Outras situações em que o compilador pode conspirar contra o programador incluem: remover verificações de overflow em operações aritméticas, pois signed overflow é indefinido em C/C++; reordenar acessos à memória, ignorando que outras threads podem depender do acesso em uma certa seqüência, se o programador não tomar o cuidado de forçar a ordem das operações; e inúmeras outras situações. Dado o grau de exploitação de comportamento indefinido nos compiladores C/C++ modernos, seja por avanços tecnológicos em análise estática, seja por influência da NSA/agentes soviéticos/illuminati/maçonaria, eu me sinto fortemente propenso a encarar o compilador C/C++ como um agente malicioso, e a idéia de minimizar o uso dessas linguagens parece cada vez mais appealing.

Outra medida técnica para reduzir a propensão dos sistemas computacionais a falhas de segurança é adotar modelos de segurança baseados em capabilities, em que o default é os processos não terem acesso a nada que não lhes seja explicitamente concedido, ao contrário dos modelos baseados em usuários, como o do Unix, em que é difícil ter certeza absoluta de quais são os poderes que um processo tem, e a grande maioria dos processos roda com mais permissões do que precisa (e.g., seu browser tem o poder de ler todos os seus arquivos pessoais, o tempo inteiro).

Falar é mais fácil do que fazer. Hoje em dia há uma falta de soluções práticas que nos permitam livrarmo-nos do C/C++ sem perder performance ou outras conveniências, ou sistemas baseados em capabilities que não sejam sistemas acadêmicos cuja adoção no mundo real é inviável. Estes são problemas nos quais eu pretendo trabalhar durante a minha existência neste mundo [aquela história de crowdfunding era só parcialmente brincadeira :)]; mais sobre isso em um post futuro, talvez. O ponto é que definitivamente há (muito) o que fazer do ponto de vista técnico para mitigar os efeitos de ações da NSA e outros agentes maliciosos.

5 comentários

Bounds checking elimination

2014-04-12 23:45 -0300. Tags: comp, prog, pldesign

Essa história de Heartbleed me lembrou de algumas coisas que eu tinha pensado meses atrás e não lembrava mais.

Para quem não sabe, o Heartbleed (concisamente explicado por este quadrinho do xkcd) é uma falha de segurança na OpenSSL (uma biblioteca que implementa os protocolos de comunicação segura SSL e TLS usada por basicamente todo o mundo) que permite a um atacante obter porções da memória do servidor potencialmente contendo dados como nomes de usuários, senhas, a chave privada do certificado servidor, etc.

Como 237% das falhas de segurança de software encontradas nos últimos 30 ou 40 anos, o Heartbleed é causado por um buffer overflow (tecnicamente "overread", pois trata-se de leitura e não escrita), e teria sido evitado se a OpenSSL tivesse sido escrita em uma linguagem que fizesse verificação de limites (bounds checking) antes de acessar uma posição de um vetor.

No fórum do xkcd, alguém escreveu:

Heartbleed is yet another example of why coding in C is a bad idea. A memcpy with an incorrect size caused all this because C compilers do no bounds checking. Heartbleed wouldn't have happened if OpenSSL had been written in, for example, Ada. Instead of an information leak that leaves no trace it would have been a denial of service at the worst.

Mais adiante na thread, alguém respondeu:

It's yet another example of why poorly written code is a bad idea. No amount of programming languages and frameworks is going to protect you from incompetent programmers.

A essa altura eu fechei a tab e fui ler outras coisas, porque se eu continuasse ali eu ia acabar respondendo com o equivalente virtual do soco na cabeça pra desentupir o cérebro. Isso é mais ou menos como ter um viaduto do qual diariamente caem carros há trinta anos, e se recusar a colocar um muro de proteção nas bordas, porque se alguém cai "a culpa é do motorista que foi incompetente".

But, but, but, bounds checking? Is it web-scale?

Se bounds checking é uma coisa tão mágica, por que não está todo o mundo usando linguagens que fazem bounds checking? A resposta, obviamente, é performance, a propriedade mais importante de qualquer software. Does it work? No, but it's fast! Ok, chega de comentários sarcásticos por ora. Eu já falei sobre a performance de bounds checking em um post anterior, onde fiz alguns benchmarks com código em C com e sem bounds checking (implementado manualmente com ifs no código testando se o índice está dentro dos limites do vetor e abortando a execução caso contrário). As conclusões no final foram que:

Do segundo item depreende-se que um acesso bounds-checked a um vetor é cerca de 25% mais lento do que um acesso direto. Assumindo que a maioria dos programas não consiste primariamente de acessos a vetores, esses 25% talvez não fizessem tanta diferença, e o benefício seria maior que o custo. (Disclaimer: talvez no caso geral o slowdown seja maior que 25%. Talvez eu faça mais uns benchmarks, só para não perder o costume, quando estiver mais disposto. Read on.)

O primeiro item é mais interessante: em algumas circunstâncias é possível provar que todos os acessos a um vetor estarão dentro dos limites, e nesses casos não é necessário fazer qualquer verificação em tempo de execução. Por exemplo (assumindo uma função hipotética length_of, que retorna o comprimento de um vetor), em um loop como:

for (i=0; i < length_of(vector); i++)
    printf("%d", vector[i]);

não é necessário verificar em tempo de execução se vector[i] está dentro dos limites do vetor, pois é possível ao compilador provar em tempo de compilação que i só adquire valores que são índices válidos do vetor. Para casos simples como esse, o gcc e outros compiladores já são capazes de fazer esse tipo de análise estática, como visto no post linkado; não se trata de uma tecnologia mítica e utópica. Os problemas começam a surgir quando temos coisas como:

int get(int vector[], int i) {
    return vector[i];
}

void foo() {
    ...
    for (i=0; i < length_of(vector); i++)
        printf("%d", get(vector, i));
}

pois a função get não sabe que será chamada com um índice válido. Se o compilador fizer inlining de get no corpo de foo, ele será capaz de eliminar o bounds checking, mas, no caso geral, não queremos sempre fazer inlining (get poderia ser uma função grande chamada em diversos pontos do código, por exemplo), e a função get (que poderia ter sido compilada separadamente) não pode assumir que quem a chamar lhe passará um índice válido.

Mas ela pode exigir. Imagine que pudéssemos escrever algo do tipo:

int get(int vector[n], int i)
    i>=0 && i<n;
{
    return vector[i];
}

i>=0 && i<n é parte da assinatura da função: além de ela exigir que o primeiro argumento seja um vetor de int e o segundo um int, ela também exige que a condição especificada seja satisfeita. Com isso: (1) a função pode assumir que a condição é verdadeira dentro do corpo, eliminando assim o bounds checking; e (2) o encargo de testar se a condição é verdadeira é passado para o chamador da função (foo, no nosso exemplo), onde há contexto suficiente para determinar se a condição é sempre verdadeira em tempo de compilação (por conta de ocorrer dentro do for, no nosso exemplo). Se esse for o caso, o bounds check pode ser eliminado do programa; caso contrário, o check é realizado em tempo de execução, garantindo que o acesso será seguro.

Mesmo em loops em que o range não está evidentemente nos limites do vetor é possível utilizar uma pequena dose de falcatrua para "amortizar" os checks. Por exemplo, em uma função como:

int sum(int vector[], int start, int end) {
    int i, total=0;
    for (i=start; i<=end; i++)
        total += vector[i];
    return sum;
}

não é possível eliminar completamente o checking, pois não sabemos de antemão se start e end é uma faixa válida de índices do vetor. Mas nem por isso precisamos fazer o checking dentro do loop. Ao invés disso, podemos transformar o código em:

int sum(int vector[], int start, int end) {
    int i, total=0;

    int length = length_of(vector);
    if (start < 0) out_of_bounds_exception();
    if (end >= length) out_of_bounds_exception();

    for (i=start; i<=end; i++)
        total += vector[i];
    return sum;
}

Se a execução passar dos ifs, então start e end são índices válidos no vetor, e não precisamos executar testes para cada acesso.

Só tem um pequeno problema na transformação acima: ela encerra o programa se end estiver além dos limites do vetor mesmo antes de vetor[end] ter sido acessado; basicamente uma exceção que ainda não aconteceu encerra o programa. Neste programa em particular isso não chega a ser um problema pois o comportamento observável do programa seria o mesmo, mas isso não é válido no caso geral. Por exemplo, poderia ser que eu soubesse de antemão que o vetor é encerrado por um valor 0, e escrevesse o código como:

int sum(int vector[], int start, int end) {
    int i, total=0;

    for (i=start; i<=end; i++) {
        if (vector[i] == 0) break;
        total += vector[i];
    }

    return sum;
}

Nesse caso, mesmo que eu passe um end inválido, pode ser que o meu programa termine com um resultado correto, desde que o vetor seja devidamente terminado com um 0. O compilador não tem dados suficientes para provar que o vetor terá o 0, entretanto, e portanto checks precisam ser inseridos. Ainda assim, é possível transformar o código em algo como:

int sum(int vector[], int start, int end) {
    int i, total=0;

    int length = length_of(vector);
    if (start < 0) out_of_bounds_exception();
    int bounded_end = min(end, length-1);

    for (i=start; i<=bounded_end; i++) {
        if (vector[i] == 0) break;
        total += vector[i];
    }

    if (end>bounded_end && i>bounded_end) out_of_bounds_exception();

    return sum;
}

que é menos trivial (e provavelmente pode ser escrito de maneira mais eficiente, mas menos clara para fins de exposição), mas preserva a semântica do programa (a prova é sugerida como exercício para o leitor).

Nem sempre os índices de vetores provêm de ranges seqüenciais. Um exemplo em que isso não ocorre é em uma busca binária, em que, para eliminar os checks, o compilador precisaria conseguir provar que (min+max)/2 está entre min e max*.

Outra situação é quando criamos um vetor de lookup reverso r que mapeia os valores de um vetor v aos índices correspondentes, i.e., se v[1] = 42, então r[42] = 1. Nesse caso, para eliminar os checks, o compilador precisa ter informação suficiente para saber que os valores de v são sempre índices válidos em r. O que pode ser viável se o tipo de v indicar qual é a faixa de valores válidos que o vetor pode conter. De qualquer forma, é interessante que esse tipo de assumption usualmente escondida sobre o comportamento do programa seja explicitamente expressível na linguagem, especialmente se tais declarações (1) não forem obrigatórias, e (2) forem usadas para melhorar performance. (Side-effect: as pessoas seriam incentivadas a documentarem melhor seus programas visando ganhar performance. Todos comemora.)

Caveats

Bounds checking é só um componente de memory-safety. Outro aspecto importante é garantir que os ponteiros/referências apontam de fato para objetos válidos em memória, e não para áreas que já foram desalocadas (ou pior, realocadas para outros objetos). A solução clássica para o problema é gerência automática de memória com garbage collection, mas há outras soluções possíveis.

O fato de que, com a introdução de pré-condições, os tipos das funções falam mais sobre o que a função faz, provavelmente implica que os tipos das funções mudam com mais freqüência quando uma função é alterada, efetivamente alterando sua interface, uma vez que cabe ao chamador da função garantir que as pré-condições são satisfeitas. Isso torna mais provável que uma alteração em uma biblioteca exija a recompilação de todo o mundo que depende dela. A solução que eu proponho é distribuir tudo como bytecode e (re)compilar para código nativo transparentemente as needed (o que tem inúmeras outras vantagens, tais como não fixar a ABI, permitir compilar o código com ou sem certs instruções (e.g., SSE) dependendo de sua disponibilidade no processador, permitir se aproveitar de mandingas brabas dependentes de uma versão da arquitetura (e.g., assumir que ponteiros têm efetivamente 48 bits e não 64 no amd64) sem se preocupar se daqui a 5 anos elas não vão mais funcionar, pois o ambiente pode simplesmente testar se uma assumption é válida e recompilar caso contrário, etc.). Uma solução alternativa é the C++ way: não fazer nada a respeito.

Conclusões

1. Bounds checking, galera. De uma vez por todas. Entre acidentes e talvez-nem-tão-acidentes, depois de 30 anos tá na hora de a gente aprender, não?

2. Bounds checking não necessariamente implica perda de performance, pois o compilador pode determinar que certos checks não são necessários em tempo de execução. Em uma linguagem sem bounds checking, o programador tem que ou inserir os checks manualmente anyway para garantir que não ocorrerá nenhum buffer overflow, ou concluir que o check não é necessário pois o índice está garantidamente dentro do vetor. No primeiro caso o check está lá anyway com ou sem bounds checking automático; com o check automático não há o risco de o programador esquecer de fazer o teste. No segundo caso o programador pode (idealmente) escrever explicitamente o raciocínio que permite concluir que o check é desnecessário, o que, além de menos error-prone (já que, se o compilador não for capaz de concluir que o raciocínio é válido, seja porque o raciocínio está errado ou porque o compilador não é suficientemente esperto, ele vai inserir o check dinâmico), é benéfico do ponto de vista de engenharia de software.

P.S.: Idéias similares às apresentadas neste post já foram inventadas e reinventadas mais de oito mil vezes sob os nomes de dependent types, design by contract, e sabe-se lá mais que outros (sinta-se à vontade para citar referências nos comentários). É por este motivo que, embora o tópico seja perfeitamente o tipo de coisa na qual eu gostaria de trabalhar, eu provavelmente não vou nem tentar empurrar o tema da minha dissertação de mestrado para esse caminho. Mais sobre isso em um post futuro, talvez.

_____

* Ou ser informado disso pelo programador, como um "axioma" sem prova. Nesse caso introduz-se uma fonte bastante perigosa de potenciais bugs, pois um axioma incorreto poderia levar a transformações de código incorretas em pontos arbitrários do programa. Uma solução semi-aceitável neste caso particular é ter uma função na biblioteca padrão da linguagem que calcula a média de dois números, acompanhada de um axioma sobre o resultado. O problema é que se a habilidade de declarar axiomas sem prova for introduzida na linguagem, é praticamente certo que alguém vá usá-la incorretamente e criar outro Heartbleed. Outra alternativa é introduzir um meio de o programador escrever a prova do axioma, que o compilador seria então capaz de verificar. Isto é nada mais, nada menos do que uma aplicação de proof-carrying code.

4 comentários

Tudo o que você nunca quis saber sobre union types

2013-10-23 02:45 -0200. Tags: comp, prog, pldesign

Este post relata o que eu aprendi tentando misturar (ou combinar) uniões de tipos e polimorfismo paramétrico na mesma linguagem. Faz tempo que eu não escrevo um post de 20k que ninguém vai ler, então aproveito a oportunidade para documentar essas coisas todas antes que eu as esqueça. Este post está sujeito a alterações futuras (dada a impossibilidade técnica de produzir alterações passadas) caso eu lembre de mais algum detalhe.

Contexto

Para quem não sabe, meu tema de TCC é criar uma linguagem de programação funcional didática. A motivação por trás disso é reduzir os problemas encontrados pelos alunos da disciplina de Fundamentos de Algoritmos (da qual eu fui monitor por três anos) com a linguagem Scheme/Racket (especificamente, com as linguagens didáticas do How to Design Programs, doravante HtDP).

Um dos problemas com essas linguagens é a falta de um sistema de tipos estático. Como conseqüência, as funções e estruturas no código escrito na disciplina normalmente são acompanhadas de um pequeno comentário em um formato semi-padrão indicando os tipos dos parâmetros e retorno das funções, campos de estruturas, etc. O problema é que essa informação não é usada pela linguagem, o que significa que (1) ela não é lá muito útil; (2) conseqüentemente os alunos tendem a não escrevê-la; (3) não há qualquer validação sobre o formato dos comentários, o que impede os alunos de "testar" se eles estão corretos. Para resolver isso, a nova linguagem (que, por motivos de piada interna maior, chama-se Faz), é estaticamente tipada e permite (na verdade exige) declarar os tipos das funções e estruturas.

O problema é que diversos exercícios do HtDP utilizam tipos mistos. Tipos mistos são uma maneira semi-formal de descrever os tipos de funções e de dados freqüentemente utilizados em linguagens dinamicamente tipadas. Por exemplo, se uma função área aceita como argumentos quadrados e círculos, pode-se definir um tipo misto "forma" constituído por quadrados e círculos e dizer que a função recebe uma forma e produz um número. No HtDP, tipos mistos são "definidos" por meio de comentários no código.

A maioria das linguagens estaticamente tipadas não permite definir tipos mistos dessa maneira. Ao invés disso, a maioria das linguagens funcionais estaticamente tipadas permitem a declaração de uniões etiquetadas (tagged unions), ou sum types. Por exemplo, em Haskell, um tipo para formas poderia ser escrito como:

data Forma = Retangulo Float Float
           | Circulo Float

A declaração define o tipo (Forma) e os possíveis construtores de valores desse tipo (Retangulo, Circulo) e os tipos dos campos de cada construtor. Para criar um valor, escreve-se uma chamada ao construtor, tal como Retangulo 2 3 ou Circulo 4.

Uma união etiquetada é diferente de um tipo misto porque o tipo misto não exige uma etiqueta; é possível definir um tipo misto "número-ou-string" consistindo de números ou strings, por exemplo, sem definir novos construtores para o tipo novo. Embora a diferença possa parecer trivial, em muitos casos a ausência de tags é bastante conveniente. Por exemplo, alguns exercícios do HtDP definem uma "página Web" como uma lista contendo símbolos (palavras) e outras páginas Web (subpáginas). (I know, I know.) Um exemplo de "página Web" seria algo como:

(list 'Eis 'um 'exemplo 'de 'página 'web
      (list 'the 'quick 'brown 'fox 'had 'better 'things 'to 'do)
      (list 'whatever 'whatever 'bla))

Em Haskell, uma definição para esse tipo de dados ficaria algo como:

data Webpage = List [WebpageContent]
data WebpageContent = Word String | Sub Webpage

E o exemplo ficaria:

List [Word "Eis", Word "um", Word "exemplo", Word "de", Word "página", Word "web",
      Sub (List [Word "the", Word "quick", Word "brown", Word "fox", Word "had",
                Word "better", Word "things", Word "to", Word "do"]),
      Sub (List [Word "whatever", Word "whatever", Word "bla"])]

Que é "um pouco" menos conveniente. Poder-se-ia argumentar que a escolha de representação é tosca, mas de qualquer forma, uma vez que o meu objetivo era permitir transcrever os exercícios do HtDP para Faz com o mínimo de turbulência, eu queria encontrar alguma maneira de integrar os tipos mistos do HtDP na linguagem da maneira mais direta possível.

Então pensei eu: e que tal se adicionarmos uniões de tipos na linguagem? Uniões representam diretamente a idéia de tipos mistos. O usuário simplesmente diz:

tipo Coisas = Números U Strings

e agora 42 e "foo" pertencem ao tipo Coisas, sem necessidade de declarar tags. (Por baixo dos panos, a implementação guarda "tags" para saber os tipos dos valores, como em qualquer linguagem dinamicamente tipada, mas isso é um detalhe de implementação que não interessa ao usuário.) Simples, hã? Agora temos tipos mistos e tipagem estática. (By the way, a declaração acima é válida em Faz.)

Estranhamente, entretanto, aparentemente nenhuma linguagem estaticamente tipada usada por mais do que duas pessoas suporta uniões de tipos. Por que será?

Polimorfismo paramétrico

Haskell e companhia suportam uma coisa chamada de polimorfismo paramétrico (também conhecida por tipos genéricos no mundo C++/Java). Nessas linguagens é possível declarar coisas como "listas de α, para todo α", ao invés de declarar um tipo novo para cada tipo de lista que se deseja utilizar. Também é possível escrever funções de tipos genéricos. Por exemplo, uma função para incluir um elemento em uma lista nessas linguagens possuiria um tipo como (α, lista de α) → lista de α, i.e., uma função que recebe um argumento de um tipo α qualquer, uma lista de elementos do mesmo tipo α, e produz uma lista do mesmo tipo. Uma função que implementa o operador de composição de funções (f∘g), i.e, que recebe duas funções e produz uma terceira função que é equivalente a aplicar a segunda sobre o resultado da primeira, teria um tipo como (α→β, β→γ) → (α→γ), indicando que as funções podem ser de quaisquer tipos, mas o resultado da primeira tem que ser do mesmo tipo do argumento da segunda (β), e a função resultante recebe um argumento do mesmo tipo do da primeira (α) e produz um resultado do mesmo tipo do da segunda (γ).

A verificação/inferência de tipos nessas linguagens é feita usando o famoso Hindley-Milner type system e extensões do mesmo. Os detalhes podem ser um pouco sórdidos, mas, a menos que eu esteja viajando completamente, a idéia do Hindley-Milner é extremamente simples: ao checar uma expressão, gera-se uma lista de constraints (restrições) que devem ser satisfeitas para que a expressão esteja bem tipada. Por exemplo, se temos as seguintes funções (e respectivos tipos):

compose       : (α→β, β→γ) → (α→γ)
bool_to_int   : bool→int
int_to_string : int→string

então uma chamada como compose(bool_to_int, int_to_string) só é bem-tipada se:

α→β = bool→int
β→γ = int→string

Esta é a lista de constraints que devem ser satisfeitos. Do primeiro constraint, tem-se que:

α = bool
β = int

e do segundo,

β = int
γ = string

Como não há conflito entre os constraints, tem-se que a expressão é bem-tipada, e o tipo da chamada é α→γ = bool→string. Por outro lado, uma chamada como compose(bool_to_int, bool_to_int) produziria os constraints:

α→β = bool→int   =>  α = bool
                     β = int
β→γ = bool→int   =>  β = bool
                     γ = int

que não podem ser satisfeitos, e portanto a expressão é mal-tipada.

Enter subtyping

O Hindley-Milner foi feito para resolver constraints de igualdade. Em uma linguagem com relações de subtipagem (e.g., em que se pode declarar um tipo funcionário como subtipo de pessoa), aplicações de função não exigem mais que os tipos dos argumentos sejam iguais aos declarados para os parâmetros, mas sim que eles estejam contidos nos tipos dos parâmetros. Por exemplo, se pessoa tem os campos nome e idade, e funcionário tem os campos nome, idade e salário, então uma função como obtém_idade, do tipo pessoa → int, pode receber tanto pessoas quanto funcionários como argumentos.

E a presença de uniões de tipos basicamente introduz relações de subtipagem da maneira mais desenfreada possível: quaisquer dois tipos A e B possuem um supertipo comum, A U B. Isso significa que se temos uma função f do tipo (α, α) -> α, uma chamada como f(1, "foo") produz os constraints:

int ⊆ α
strings ⊆ α

que é satisfatível com α = int U string. Note que, na verdade, int U string é apenas um limite inferior para α: qualquer outro supertipo, como int U string U char, ou (top, o supertipo de todos os tipos), também serviria. Porém, intuitivamente int U string é o tipo mais "útil" inferível para a expressão, no sentido de que é o que mantém a informação mais precisa de que tipo de coisas se pode fazer com o resultado.

Nem sempre, entretanto, existe um único tipo "mais útil". A relação de subtipagem entre tipos funcionais possui uma propriedade curiosa: um tipo Sparam → Sreturn é subtipo de Tparam → Treturn, ou

Sparam → Sreturn ⊆ Tparam → Treturn

se

Tparam  ⊆ Sparam e
Sreturn ⊆ Treturn .

[Para entender essa inversão, você pode pensar assim: um tipo (S) é subtipo de outro (T) se S puder ser usado em qualquer lugar que T possa ser usado (e.g., funcionário é um tipo de pessoa porque um funcionário pode ser usado em qualquer lugar em que uma pessoa pode ser usada). Para que uma função (f) possa ser usada no lugar de outra (g), ela não pode exigir mais do argumento do que a outra, mas pode exigir menos (e.g., se g espera funcionários, então uma função que espere pessoas pode ser usada em seu lugar, pois funções que esperam pessoas também aceitam funcionários). Por outro lado, f tem que produzir um resultado tão bom ou melhor do que o da função que ela está substituindo (e.g., se g produzia pessoas, então f tem que produzir uma pessoa ou um funcionário, pois quem vai usar o resultado da função espera trabalhar com o resultado como se ele fosse uma pessoa).]

Agora imagine que temos uma função f do tipo (α→α) → (α→α), e uma função g do tipo int U string → int. A chamada f(g) produz o constraint:

int U string → int ⊆ α → α

de onde tem-se:

α ⊆ int U string
int ⊆ α

Tanto α = int quanto α = int U string são soluções válidas para os constraints, e nenhuma é evidentemente melhor que a outra.

Coisas como a chamada compose(bool_to_int, int_to_string) da seção anterior agora produzem constraints do tipo:

α ⊆ bool
int ⊆ β
β ⊆ int
string ⊆ γ

Destas, a única variável cujo tipo é fixado pelos constraints é β; as outras duas só possuem upper e lower bounds. Novamente, a solução "óbvia" ou "mais útil" seria α = bool, γ = string. Formalizar o "mais útil" no caso geral, entretanto, é um problema não-trivial e, como visto, nem sempre existe solução (o que fazer nesses casos é uma boa pergunta).

Variable identification

No Hindley-Milner, sempre que o constraint solver encontra um constraint da forma variável = whatever, ele substitui todas as ocorrências da variável por whatever no tipo e nos demais constraints, mesmo que whatever seja outra variável. Isso é válido porque os constraints são igualdades. No mundo da subtipagem, entretanto, igualar as variáveis nem sempre é a melhor solução. Por exemplo, considere as seguinte funções, escritas em um pseudocódigo funcional esquisito:

foo(f: α→β, g: α→γ, h: α→γ, k: β→γ) : Tripla(α→γ, α→γ, α→γ)
 = Tripla(compose(f, k), g, h)

jogo_do_pim(x: Int) : Int U String
 = if x mod 4 ≠ 0 then x
                  else "pim"

jogo_do_pi(x: Int) : Int U String U Char
 = if x == 4 then 'π'
   else if x mod 4 ≠ 0 then x
   else "pim"

id(x: ι) : ι
 = x

(Procurando por "jogo do pim" na Web encontrei um negócio interessante.) Agora, queremos tipar a chamada:

foo(jogo_do_pim, jogo_do_pi, id, id)

que produz os seguintes constraints, um para cada parâmetro/argumento (note que cada ocorrência de id usa variáveis de tipo separadas; caso contrário, todas as chamadas de id do programa teriam que ter o mesmo tipo):

Int → Int U String         ⊆  α → β
Int → Int U String U Char  ⊆  α → γ
ι  → ι                     ⊆  α → γ
ι′ → ι′                    ⊆  β → γ

Digerindo esses constraints, temos:

α            ⊆ Int
Int U String ⊆ β

α                    ⊆  Int
Int U String U Char  ⊆  γ

α ⊆ ι
ι ⊆ γ

β  ⊆  ι′
ι′ ⊆  γ

Se fôssemos igualar variáveis a la Hindley-Milner, teríamos, pelos dois últimos constraints, que α = γ e β = γ, e portanto α = β, mas não é possível resolver os constraints assim, pois α ⊆ Int e Int U String ⊆ β. Uma solução válida é:

α = Int
β = Int U String
γ = Int U String U Char

o que exemplifica que identificar/unificar as variáveis em constraints da forma α ⊆ β não é uma boa idéia na presença de union types (ou subtipagem em geral). Isso significa que podemos dar tchau para o Hindley-Milner. Só que agora temos um bocado de problemas. Por exemplo, suponha que temos os seguintes constraints:

α ⊆ Listas de β
β ⊆ Listas de α

Isto é um ciclo, que produziria um tipo infinito, o que em princípio é um erro. O Hindley-Milner facilmente detecta esta situação: ao encontrar o primeiro constraint, ele substitui todas as ocorrências de α por Listas de β, e o segundo constraint fica β ⊆ Listas de Listas de β. De forma geral, um ciclo sempre leva em algum ponto a um constraint em que a mesma variável aparece dos dois lados, o que é fácil de detectar. Sem igualamento de variáveis, essa abordagem não funciona.

Side note: para evitar a unificação, uma coisa que eu tinha pensado era, ao encontrar constraints do tipo α ⊆ Listas de β, substituir todas as ocorrências de α por Listas de α′, refletindo o fato de que se sabe que α é uma lista, mas não se sabe ainda de quê. O problema é que nesse caso o algoritmo entra em loop, pois:

α ⊆ Listas de β  => Listas de α′ ⊆ Listas de β            (expansão de α)
β ⊆ Listas de α     β ⊆ Listas de Listas de α′

                 => α′ ⊆ β                  (cortando o construtor comum)
                    β ⊆ Listas de Listas de α′

                 => α′ ⊆ Listas de β′
                    Listas de β′ ⊆ Listas de Listas de α′ (expansão de β)

                 => α′ ⊆ Listas de β′
                    β′ ⊆ Listas de α′       (cortando o construtor comum)

                    (... and so on ...)

Problema dos ciclos à parte, como devemos tipar uma expressão como compose(id, id)? A expressão produz os seguintes constraints:

α  ⊆  ι
ι  ⊆  β
β  ⊆  ι′
ι′ ⊆  γ

Qual é a solução? Unificar as variáveis? Mas em quais casos é correto unificar e em quais não é?

Instanciação ambígua de variáveis

A existência de uniões de tipos torna possível declarar coisas como:

f(x: Par(Int, α) U Par(α, String)) : α
 = if x.first ∈ Int then x.second
                    else x.first

Agora se chamarmos f(Par(5, "foo")), qual é a instanciação correta para tipo de x? α = Int ou α = String? Uma solução é detectar esse tipo de coisa e proibir que o mesmo tipo paramétrico apareça múltiplas vezes em uma união com um argumento que alterna entre concreto e abstrato. Da mesma forma, parâmetros de tipos como Int U α devem ser proibidos, pois a instanciação de α é ambígua quando o argumento é Int. E α U β também é ambíguo, pois para qualquer instanciação, a instanciação "flipada" (trocando os valores de α e β) também é válida. Supostamente essas restrições resolvem o problema, mas eu não estou quite sure quanto a isso.

O que eu fiz em Faz (sic)

Com o tempo limite para concluir o TCC se aproximando e a minha paciência/interesse no problema acabando, o que eu acabei fazendo foi um sério corte orçamentário na utilização de tipos paramétricos e uniões na linguagem. Para evitar o problema da unificação de variáveis, os casos em que ela é necessária são simplesmente proibidos: constraints da forma X ⊆ Y em que tanto X quanto Y contêm variáveis abstratas de tipos são rejeitados pelo typechecker. Isso significa que coisas como compose(id, id), em que tanto o parâmetro (α→β) quanto o argumento (ι→ι) são polimórficos, são rejeitadas. É tosco, mas pelo menos some com o problema. Além disso, uniões de tipos paramétricos também possuem algumas restrições (que eu ainda não defini direito, para ser sincero; quando eu terminar o TCC pode ser que eu edite esta seção).

Conclusão

Certa vez um sábio disse o seguinte:

Follow! But follow only if ye be man of valour! For the entrance to this cave is guarded by a creature, so foul, so cruel, that no man yet has fought with it and lived! Bones of full fifty men are strewn about its lair! So, brave knights, if you do doubt your courage or your strength come no further, for death awaits you all, with nasty, big, pointy teeth...

Acredito que ele estava falando de union types.

Comentários

Convertendo archives do LISTSERV para mbox

2013-09-04 01:45 -0300. Tags: comp, unix, prog, perl

Escrevi um pequeno script em Perl para converter um archive de mailing list do LISTSERV para o formato mbox, que pode ser importado em diversos clientes de e-mail. Possa ele ser-vos útil.

3 comentários

Main menu

Posts recentes

Tags

comp (80) life (31) prog (31) unix (29) random (23) mundane (21) lang (20) about (18) mind (15) web (13) img (11) rant (11) pldesign (10) ramble (9) privacy (8) esperanto (7) bash (7) shell (6) home (6) lash (5) conlang (5) academia (5) freedom (4) book (4) lisp (4) copyright (4) worldly (4) mestrado (4) misc (4) film (3) music (3) kbd (3) politics (3) security (3) network (2) poem (2) editor (2) physics (2) php (2) android (2) cook (2) latex (2) wrong (2) treta (2) c (2) pointless (1) kindle (1) audio (1) perl (1)

Elsewhere

Quod vide


Copyright © 2012-2015 Vítor Bujés Ubatuba De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.

Powered by Blognir.