Listas

Sintaticamente, quando um cons possui outro cons em seu cdr:

• Removemos o ponto que separa os dois elementos no primeiro cons;
• Removemos os parênteses ao redor do segundo cons.

Majestic Lisp é capaz de seguir essas regras de impressão.

'(a . (b . c))

(a b . c)

A esse encadeamento limitado envolvendo células cons, terminado com um elemento separado por ponto, damos o nome de lista pontuada.

Essa situação pode se repetir recursivamente, toda vez que um novo cons aparecer no cdr de um cons anterior.

'(a . (b . (c . d)))

(a b c . d)

Uma forma de pensarmos em encadeamentos de células cons é através de uma notação conhecida como notação de caixas¹. Nela, cada caixa é simbolizada como uma caixa com duas partes (car e cdr), que acabam tornando-se ponteiros para outros valores.

O exemplo a seguir mostra uma renderização puramente textual de uma notação em caixas para a expressão (a b c . d).

[*|*]--->[*|*]--->[*|*]---> d
 |        |        |
 v        v        v
 a        b        c

Veja que, se tomarmos o cdr da primeira célula, o que resta é outro encadeamento de células; isso deixa bem claro que, no fim das contas, estamos falando de uma célula cons no formato (a . ...), onde ... nada mais é que a próxima célula cons, com seus próprios detalhes.

Podemos usar a notação de caixas para situações ainda mais complexas; veja o exemplo a seguir, que mistura células cons tanto em car quanto em cdr.

'(a . ((b . c) . (d . e)))

(a (b . c) d . e)

Representando com a notação em caixas, temos:

[*|*]--->[*|*]------->[*|*]---> e
 |        |            |
 v        v            v
 a       [*|*]---> c   d
          |
          v
          b

Há um caso particular de listas pontuadas, que é particularmente interessante em dialetos de Lisp. Trata-se de listas cuja estrutura torna-as mais adequadas para processamento.

Quando, no encadeamento de células cons para formação de uma lista pontuada, o cdr da última célula cons for o símbolo nil, então teremos o que chamamos de lista adequada, ou simplesmente lista.

Para esse caso, podemos adicionar mais uma regra de sintaxe:

• Quando o cdr de um cons corresponder ao símbolo nil, pode-se omitir o símbolo nil e o ponto que o precede.

'(a . (b . (c . nil)))

(a b c)

Se observarmos a impressão da lista anterior com a notação em caixas, veremos que trata-se exatamente da mesma coisa que foi escrita usando quoting.

[*|*]--->[*|*]--->[*|*]---> nil
 |        |        |
 v        v        v
 a        b        c

Se listas pontuadas poderiam representar a ideia das listas encadeadas como explicadas por cormen-pt, as listas adequadas são uma representação ainda mais fiel, pois determinam o uso de um único marcador – o símbolo nil – para representar o final de uma lista.

Podemos representar listas (pontuadas ou adequadas) diretamente através do processo de quoting, sem parênteses ou pontos adicionais. O exemplo a seguir mostra uma lista adequada com números de um a quatro.

'(1 2 3 4)

(1 2 3 4)

Sua representação na notação em caixas deixa claro que trata-se de uma lista adequada, como esperado.

[*|*]--->[*|*]--->[*|*]--->[*|*]---> nil
 |        |        |        |
 v        v        v        v
 1        2        3        4

Podemos representar uma lista adequada, sem elementos, através de dois símbolos distintos: '(), que corresponde à sintaxe de uma lista vazia quotada, e nil, que simboliza o fim de uma lista.

Dessa forma, podemos observar que toda lista adequada encerra-se com uma lista vazia.

Do ponto de vista de Majestic Lisp, todo uso de '() em código será transformado no símbolo nil.

'()

nil

Uma forma alternativa de armazenamento de dados em Majestic Lisp pode ser feita usando vetores. Um vetor nada mais é que certos valores armazenados de forma sequencial, para maior facilidade de acesso. Em Majestic, vetores possuem subtipos que indicam a natureza de seus elementos, algo especialmente importante quando os elementos são homogêneos, como veremos em breve.

Um vetor pode ser construído a partir da função vector, e também usando a notação abreviada com colchetes; de fato, para o interpretador de Majestic, o uso dos colchetes é equivalente ao uso da função vector. Os dois exemplos a seguir realizam, de forma equivalente, a construção de dois vetores.

(vector 'a 'b 'c 'd)

[a b c d]

['d 'c 'b 'a]

[d c b a]

Como dito anteriormente, vetores de Majestic possuem subtipos, de forma similar (porém não igual) aos números. Geralmente, um vetor que tenha sido construído a partir de valores com o mesmo tipo terá o tipo dos vetores (isto valerá para números inteiros, pontos flutuantes e caracteres). Para outros tipos de valores e vetores com tipos mesclados, o vetor possuirá um subtipo any.

(vec-type ['a 'b 'c])

any

(vec-type [1 2 3])

integer

(vec-type [#\H #\e #\l #\l #\o])

char

Um vetor com um subtipo só suporta substituição ou adição de novos valores daquele mesmo subtipo, por questões de otimização. Caso seja necessário inserir valores de tipos diferentes, pode-se realizar uma coerção do vetor para um subtipo any, ou para outro tipo de vetor, caso seja aplicável.

(vec-type (vec-coerce 'any [1 2 3]))

any

A diferença principal entre as listas e os vetores está no acesso à informação. Enquanto acessar o n-ésimo valor de uma lista precisa ser feito atravessando-a elemento a elemento, o acesso ao n-ésimo elemento de um vetor pode ser feito em tempo constante.

(vec-at 2 ['a 'b 'c 'd 'e])

c

(nth 2 '(a b c d e))

c

Strings, em Majestic Lisp, são vetores que possuem, estritamente, caracteres; em outras palavras, todo vetor com subtipo char é, necessariamente, uma string.

Podemos construir strings a partir de aspas duplas, como normalmente se faz na maioria das linguagens, e também construí-las através da escrita de um vetor que contenha apenas caracteres.

[#\a #\b #\c #\d]

"abcd"

"abcd"

"abcd"

Strings são úteis para armazenar informações textuais, e são usadas em várias operações como impressão de texto no console, em arquivos, ou mesmo ao levantarmos erros em nossas aplicações.