Qual é o objetivo de usar o NIL para representar nós nulos?

No meu curso de Algoritmos e Estruturas de Dados , professores, slides e o livro ( Introdução aos algoritmos, 3ª edição ) têm usado a palavra NILpara denotar, por exemplo, um filho de um nó (em uma árvore) que não existe.

Uma vez, durante uma palestra, em vez de dizer NIL, meu colega disse null, e o professor o corrigiu, e eu não entendo por que os professores enfatizam essa palavra.

Existe uma razão pela qual as pessoas usam a palavra NILem vez de null, ou none, ou qualquer outra palavra? Tem NILalgum significado particular que os outros não têm? Existe alguma razão histórica?

Observe que eu já vi alguns lugares na web em que, por exemplo, a palavra nullfoi usada em vez de NIL, mas geralmente essa última é usada.

Tanto quanto eu estou preocupado, null, nil, nonee nothingsão nomes comuns para o mesmo conceito: um valor que representa a “ausência de um valor”, e que está presente em muitos tipos diferentes (chamado tipos anuláveis ). Este valor é normalmente usado onde um valor está normalmente presente, mas pode ser omitido, por exemplo, um parâmetro opcional. Diferentes linguagens de programação implementam isso de maneira diferente, e algumas linguagens podem não ter esse conceito. Em idiomas com ponteiros, é um ponteiro nulo . Em muitas linguagens orientadas a objetos, null não é um objeto: chamar qualquer método é um erro. Para dar alguns exemplos:

• No Lisp, nilé comumente usado para representar a ausência de um valor. Diferentemente da maioria dos outros idiomas, nilpossui estrutura - é um símbolo cujo nome é "NIL". Também é a lista vazia (porque uma lista deve ser uma célula de contras, mas às vezes não há célula de contras porque a lista está vazia). Seja implementado por um ponteiro nulo sob o capô ou como um símbolo como qualquer outro, depende da implementação.
• Em Pascal, nilé um valor de ponteiro (válido em qualquer tipo de ponteiro) que não pode ser desreferenciado.
• Em C e C ++, qualquer tipo de ponteiro inclui um NULLvalor distinto de qualquer ponteiro para um objeto válido.
• No Smalltalk, nilé um objeto sem método definido.
• Em Java e em C #, nullé um valor de qualquer tipo de objeto. Qualquer tentativa de acessar um campo ou método de nullaciona uma exceção.
• No Perl, undefé diferente de qualquer outro valor escalar e é usado em todo o idioma e biblioteca para indicar a ausência de um valor "real".
• No Python, Noneé diferente de qualquer outro valor e é usado em toda a linguagem e biblioteca para indicar a ausência de um valor "real".
• Em ML (SML, OCaml), Noneé um valor de qualquer tipo no esquema de tipos 'a option, que contém Nonee Some xpara qualquer xtipo 'a.
• Em Haskell, o conceito semelhante usa os nomes Nothinge Just xos valores e Maybe ao tipo.

Nas apresentações de algoritmos, qual nome é usado tende a originar-se do segundo plano do apresentador ou do idioma usado nos exemplos de código.

NULL$\mathsf{nil}$

É possível que seu professor deseje usar a palavra nullpara um ponteiro nulo constante na linguagem de programação usada no curso (Java ou C #?) E NILdenotar a ausência de um nó em algumas estruturas de dados, que podem ou não ser implementadas como uma constante de ponteiro nulo (por exemplo, como visto acima, no Lisp, NILmuitas vezes não é implementado como um ponteiro nulo). Essa distinção seria relevante ao discutir técnicas de implementação para estruturas de dados. Ao discutir as estruturas de dados em si, o conceito de nulo-ponteiro-constante é irrelevante, apenas o conceito não-igual a qualquer outro valor é importante.

Não existe um esquema de nomenclatura padrão. Outro professor ou livro didático poderia usar nomes diferentes.

Acredito que a razão para o uso de nulo e nulo é que o primeiro é principalmente um substantivo e o segundo, principalmente um adjetivo (verifiquei na web e em meu artigo de dicção: American Heritage 1992).

Em relação ao significado e à história, o NIL é uma contração do latim "nihil", que significa "nada".

Que eu saiba, o uso do nome nilpara indicar um ponteiro nulo foi introduzido com a linguagem de programação Lisp (1958).

Um ponteiro nulo é um valor de ponteiro que não deve apontar para nada e, portanto, não deve ser desreferenciado. Na maioria dos casos, os ponteiros são simplesmente endereços de memória. Qualquer variável (ou seja, qualquer local) que se destina a conter esse ponteiro sempre conterá alguma configuração de bits, e essa configuração pode ser lida como um endereço de memória. Portanto, geralmente o valor nilserá o endereço de uma área de memória proibida para o programa, causando alguma forma de falha (possivelmente interrupção) se o programa tentar desreferenciar nil, o que pode ser apenas um erro.

Ter um valor padrão predefinido exclusivo para desempenhar essa função é essencial nas linguagens usando ponteiros explicitamente, pois é importante poder testar se um ponteiro está atualmente apontando para algum local da memória ou não. Normalmente, no Lisp, uma lista era construída como uma sucessão de pares "contras", contendo um ponteiro "car" para um elemento da lista e um ponteiro "cdr" para o próximo par. No último par da lista, o segundo ponteiro foi nil.

Isso corresponde à definição recursiva de uma lista como uma lista vazia ou um elemento da lista concatenado a uma lista. Portanto, uma lista sem elemento foi representada por nil. Essa lista vazia é a identidade da lista monóide.

Como as listas podem ser usadas para representar conjuntos, nesse caso, o conjunto vazio também pode ser representado por nil.

Assim, nilhistoricamente, era um valor especial de ponteiro, mas passou a ser entendido como um valor de identidade especial para outros domínios mais abstratos, como listas ou conjuntos.

Um ponteiro igual a nilera um ponteiro nulo, sendo nulo um adjetivo e não um substantivo (isto é, um substantivo).

O uso coordenado de ambas as palavras, como adjetivo e substantivo, é bastante consistente com outras práticas. O qualificador null é frequentemente usado para o zero de uma estrutura algébrica, como a identidade de um monóide: o elemento nulo . As listas formam um monóide , onde o valor nulo é a identidade. O mesmo vale para os conjuntos (embora eles formem uma álgebra com muito mais propriedades). Diz-se da mesma forma que um número inteiro é nulo quando é zero.

Existem muitas variações no uso dessas palavras e de outras, como nenhuma, dependendo dos autores e idiossincrasias das linguagens de programação.

As duas principais conotações são , como explicado acima

• como um "valor indefinido" padrão, representando de fato a ausência de qualquer valor utilizável.

• como valor de identidade de algum domínio

Isso mostra que não é exato afirmar que o NIL é " um valor que representa a" ausência de um valor ", como feito por Gilles na resposta aceita . Depende do idioma e de seus usos. A linguagem de programação LISP provavelmente introduziu NIL na terminologia de programação 55 anos atrás. No LISP, NILestá a lista vazia e pode-se notar, equivalentemente, ()qual é a representação natural da lista vazia.Não representa a ausência de um valor. Às vezes, é usado como marcador de posição para valores ausentes, embora isso geralmente deva ser evitado precisamente porque a lista vazia é um valor. O que significa um valor ausente em uma estrutura em qualquer objeto arbitrário, escolhido pelo programador, que não pode ser confundido com valores aceitáveis.

Os dois conceitos são bastante diferentes, embora tenhamos mostrado acima que eles podem ser relacionados. Pode ser interessante ter uma taxonomia detalhada do modo de uso da terminologia enumerada pela resposta de Gilles, para ver se os usos de cada uma dessas palavras estão mais orientados para uma conotação ou outra.

Os nomes não são mais do que aquilo que lhes é atribuído em um determinado contexto, por quem quer que esteja definindo o discurso. Alguns usos são mais comuns, mais naturais ou mais consistentes, mas deve-se sempre verificar as definições e garantir que significado foi pretendido em cada contexto. E nem sempre se deve esperar que a terminologia tenha sido escolhida com bom gosto ou consistência.

NIL é um objeto com um valor que informa ao programador que o objeto não é válido. É particularmente útil em C ++, onde NULL é definido como 0. Se você der uma referência a NULL em C ++, terá um comportamento indefinido. Se você desassociar o NIL (um ponteiro para um objeto vazio que você definiu), obterá um objeto que poderá dizer que está além do fim da sua estrutura de dados. É ótimo para evitar falhas catastróficas do programa e detectar erros.

Você pode usar o NIL em casos como listas duplamente vinculadas, sendo o início e o fim da lista para acompanhar a cabeça e a cauda, ​​e certifique-se de que os ponteiros -> next e -> prev nunca façam referência a NULL.