Por que a lista vazia é usada como o terminador de lista no Lisp?

4

Parece-me que o terminador de lista no Lisp poderia ser qualquer valor arbitrário. Por exemplo, o terminador de cadeia em C é o ponteiro nulo. Existe uma razão filosófica pela qual a lista vazia foi escolhida para terminar as listas?

    
por Skilldrick 16.04.2012 / 05:33
fonte

5 respostas

15

Uma lista Lisp não é realmente terminada com uma lista vazia - ela é terminada com um valor especial, tradicionalmente chamado de nil . Acontece que, tradicionalmente, isso é avaliado como false - o que o torna tão próximo do ponteiro nulo de C quanto possível (em C, uma constante de ponteiro nulo é uma constante inteira igual a zero, que também é avaliada como false ).

UmalistavaziaébasicamenteapenasumaformaabreviadadeexpressaroNIL-jáquevocênãotemsequerumaúnicacéluladecons,tudooquerestaéoNILqueterminaalista.Emoutraspalavras,nãoéqueumalistasejaterminadacomumalistavazia-équeumalistavaziaconsisteemapenasumterminador.

Usandoanotaçãodeponto,épossívelvincularascélulasdeconsdeoutrasmaneiras,masoresultadonãoéuma"lista" como o termo é normalmente usado.

    
por 16.04.2012 / 05:40
fonte
8

As listas de Lisp não têm realmente um valor de 'terminação'. Na verdade, o Lisp nem sequer possui uma estrutura de dados de lista primitiva. As listas são criadas a partir da lista vazia e de uma cadeia de células de cons com links apontando para o conteúdo da lista.

As listas são definidas recursivamente:

  • a lista vazia é ()
  • uma lista newlist é o resultado de (CONS element list) , em que (FIRST newlist) é element e (REST newlist) é list .

Uma lista está vazia quando é a lista vazia ou (NULL list) é verdadeira.

Porque newlist é o resultado de (CONS element list) , na verdade, é um objeto cons cell e '(lista nova CONSP) é verdadeira.

Nos tempos antigos, FIRST era chamado de CAR e REST era CDR . Hoje é um bom estilo para usar em operações de lista FIRST e REST . CAR e CDR é melhor usado quando alguém explora o recurso que algo (árvore, fila, lista, ...) é construído a partir de células de cons.

Historicamente (e ainda no Common Lisp que pretende ser compatível com versões anteriores), a lista vazia é também o símbolo exclusivo NIL . A lista vazia é avaliada por si mesma e é também o valor false . No Esquema Lisp-dialect, a lista vazia NÃO é o valor falso.

CL-USER 12 > (setq l1 ())
NIL

CL-USER 13 > (setq l2 (cons 1 (cons 2 l1)))
(1 2)

CL-USER 14 > (consp l1)
NIL

CL-USER 15 > (consp l2)
T

CL-USER 16 > (null l1)
T

CL-USER 17 > (null l2)
NIL

CL-USER 18 > (first l2)
1

CL-USER 19 > (rest l2)
(2)

CL-USER 20 > (rest (rest l2))
NIL

CL-USER 21 > (consp (rest l2))
T

CL-USER 22 > (consp (rest (rest l2)))
NIL
    
por 16.04.2012 / 10:10
fonte
6

Eu lhe darei a resposta filosófica para sua pergunta filosófica:

Parece-me que o terminador de lista no Lisp poderia ser qualquer valor arbitrário. [...] Existe uma razão filosófica pela qual a lista vazia foi escolhida para terminar listas?

A resposta à sua pergunta é esta: o terminador de lista é um valor arbitrário . É tão arbitrário que diferentes dialetos de Lisp usem um valor diferente para ele e ainda assim permaneçam compatíveis com o conceito.

O Common Lisp usa um objeto de símbolo: o símbolo nil . Um símbolo! O que um símbolo tem a ver com listas? Nada.

(exceto que quando trabalhamos com objetos matemáticos com lápis e papel, usamos símbolos. Um círculo com um traço ou {} representa um conjunto vazio, etc. Então, por que não usar símbolos de máquina da mesma forma?)

O esquema usa uma lista vazia, o objeto () que não é um símbolo.

O Esquema () e o Common Lisp nil são bem diferentes, mas eles terminam adequadamente uma lista, exatamente de acordo com sua observação de que poderia ser qualquer valor arbitrário!

Portanto, existe uma razão filosófica pela qual a lista vazia encerra as listas? Sim! A razão é que qualquer objeto que entenda terminar uma lista é , por definição, a lista vazia. Se você usar o número 42 como terminador de lista, então () significa 42.

Matematicamente, cada lista tem a lista vazia como sufixo (assim como cada conjunto tem o conjunto vazio como um subconjunto). Como a representação da lista Lisp é baseada em sufixos (uma lista não vazia é uma referência a um objeto que contém o primeiro elemento e o sufixo dessa lista), deve haver algo para manipular o caso quando uma lista tiver apenas um elemento e seu próprio sufixo é (matematicamente) a lista vazia. Qualquer objeto instalado como o sufixo é entendido como sendo a lista vazia, e por uma questão de consistência e unidade, esse objeto deve ser melhor usado como a representação da lista vazia autônoma também, não apenas como a representação do vazio. sufixo da lista de um elemento.

    
por 17.04.2012 / 00:26
fonte
0

Isso pode não ser uma explicação específica do idioma e um pouco anti-científica, mas pode lhe dar alguns pensamentos.

Você poderia pensar sobre a linguagem como um conjunto de todos os fatos relativos ao "mundo" ou "universo" criado por essa linguagem. Como este é um conjunto, você precisaria ter um conjunto de complementos para todos os fatos excluídos do idioma, ou seja, algo para significar "não neste conjunto". Em certa luz nil (ou falsas ou outras variantes do "nada" pode ser entendido como "não neste conjunto"). Como os contras são um dos blocos de construção básicos da linguagem, o átomo usado para significar nada é usado para qualquer valor ainda não criado. Então, você não termina a lista com uma lista vazia (como então você encerra listas vazias?), É apenas em algum momento que não há nada que os contras estejam apontando e nil é a maneira de dizer isso.

    
por 16.04.2012 / 16:27
fonte
0

Como Rainer e Jerry explicaram, as listas Lisp são construídas a partir de células de cons, então não é realmente e lista vazia. Conceitualmente, é útil pensar dessa maneira ao definir funções recursivas. É um pouco mais óbvio se olharmos para a definição do tipo de dados List em (por exemplo) Haskell.

data List a = Cons a (List a)
            | Empty <<== nil in Lisp

O que isso diz é que ou temos uma célula Cons com um elemento seguido por uma cauda ou uma lista vazia. Portanto, uma lista de 1 elemento é (Cons 1 Vazio). Isso é útil para definir funções recursivas, como map.

map f (Cons e tail) = Cons (f e) (map f tail)
map f Empty = Empty

Que no Lisp poderia ser

(defmethod fmap (f (lst cons))
  (cons (funcall f (car lst))
        (fmap f (cdr lst))))

(defmethod fmap (f (lst null))
  nil)

Portanto, pensar conceitualmente em uma lista como sendo encerrada pela lista vazia pode ser muito útil,

    
por 16.04.2012 / 16:43
fonte

Tags