Expressão S - S-expression

Estrutura de dados em árvore que representa a expressão S(* 2 (+ 3 4))

Na programação de computador , uma expressão S (ou expressão simbólica , abreviada como sexpr ou sexp ) é uma expressão em uma notação com o mesmo nome para dados de lista aninhada ( estruturada em árvore ). As expressões S foram inventadas e popularizadas pela linguagem de programação Lisp , que as usa tanto para código-fonte quanto para dados.

Na sintaxe usual entre parênteses do Lisp, uma expressão S é classicamente definida como

  1. um átomo, ou
  2. uma expressão da forma em que x e y são expressões S.(x . y)

Esta definição reflete a representação do LISP de uma lista como uma série de "células", cada uma delas um par ordenado . Em listas simples, y aponta para a próxima célula (se houver), formando assim uma lista . A cláusula recursiva da definição significa que tanto esta representação quanto a notação da expressão S podem representar qualquer árvore binária . No entanto, a representação pode, em princípio, permitir referências circulares, em que casos a estrutura não é uma árvore, mas um gráfico cíclico , e não pode ser representada na notação de expressão S, a menos que uma convenção para referência cruzada seja adicionada (análogo ao SQL chaves estrangeiras , XML IDREFs, etc.).

A definição de um átomo varia por contexto; na definição original de John McCarthy , presumia-se que existia "um conjunto infinito de símbolos atômicos distinguíveis " representados como "sequências de letras latinas maiúsculas e dígitos com espaços em branco incorporados" (um subconjunto de sequência de caracteres e literais numéricos ).

A maioria das notações sexpr modernas permitem strings entre aspas mais gerais (por exemplo, incluindo pontuação ou Unicode completo ) e usam uma notação abreviada para representar listas com mais de 2 membros, de modo que

(x y z)

apoia

(x . (y . (z . NIL)))

NILé o objeto especial de fim de lista (escrito alternativamente (), que é a única representação em Scheme ).

Na família Lisp de linguagens de programação, as expressões S são usadas para representar o código-fonte e os dados. Outros usos de S-expressões são em linguagens Lisp-derivados, como DSSSL , e como mark-up em protocolos de comunicação como o IMAP e John McCarthy 's CBCL . Também é usado como representação de texto de WebAssembly . Os detalhes da sintaxe e dos tipos de dados suportados variam nas diferentes linguagens, mas o recurso mais comum entre essas linguagens é o uso de expressões S e notação de prefixo.

Tipos de dados e sintaxe

Existem muitas variantes do formato da expressão S, suportando uma variedade de sintaxes diferentes para tipos de dados diferentes. Os mais amplamente suportados são:

  • Listas e pares :(1 () (2 . 3) (4))
  • Símbolos :with-hyphen ?@!$ a\ symbol\ with\ spaces
  • Strings :"Hello, world!"
  • Inteiros :-9876543210
  • Números de ponto flutuante :-0.0 6.28318 6.022e23

O caractere #é freqüentemente usado para prefixar extensões à sintaxe, por exemplo, #x10para inteiros hexadecimais ou #\Cpara caracteres.

Use em Lisp

Ao representar o código-fonte em Lisp, o primeiro elemento de uma expressão S é comumente um operador ou nome de função e quaisquer elementos restantes são tratados como argumentos. Isso é chamado de "notação de prefixo" ou " notação polonesa ". Como exemplo, a expressão booleana escrita 4 == (2 + 2)em C é representada como (= 4 (+ 2 2))na notação de prefixo baseada em s-expr de Lisp.

Conforme observado acima, a definição precisa de "átomo" varia entre as linguagens do tipo LISP. Uma string entre aspas pode conter normalmente qualquer coisa, exceto aspas, enquanto um átomo de identificador sem aspas pode conter qualquer coisa, exceto aspas, caracteres de espaço em branco, parênteses, colchetes, colchetes, barras invertidas e ponto-e-vírgulas. Em ambos os casos, um caractere proibido pode normalmente ser incluído escapando-se dele com uma barra invertida precedente. O suporte a Unicode varia.

O caso recursivo da definição s-expr é tradicionalmente implementado usando células cons .

Expressões S foram originalmente destinadas apenas para dados a serem manipulados por expressões M , mas a primeira implementação de Lisp foi um interpretador de codificações de expressões S de expressões M, e os programadores Lisp logo se acostumaram a usar expressões S para ambos os códigos e dados. Isso significa que Lisp é homoicônico ; ou seja, a representação primária de programas também é uma estrutura de dados em um tipo primitivo da própria linguagem.

Exemplos de expressões S de dados

Listas aninhadas podem ser escritas como expressões S: ((milk juice) (honey marmalade))é uma expressão S de dois elementos cujos elementos também são expressões S de dois elementos. A notação separada por espaços em branco usada no Lisp (e neste artigo) é típica. As quebras de linha (caracteres de nova linha) geralmente se qualificam como separadores.

Esta é uma gramática livre de contexto simples para um pequeno subconjunto do inglês escrito como uma expressão S (Gazdar / Melish, Processamento de linguagem natural em Lisp), onde S = frase, NP = frase nominal, VP = frase verbal, V = verbo : 

(((S) (NP VP))
 ((VP) (V))
 ((VP) (V NP))
 ((V) died)
 ((V) employed)
 ((NP) nurses)
 ((NP) patients)
 ((NP) Medicenter)
 ((NP) "Dr Chan"))

Exemplo de expressões S de código-fonte

O código do programa pode ser escrito em expressões S, geralmente usando notação de prefixo.

Exemplo em Common Lisp : 

(defun factorial (x)
   (if (zerop x)
       1
       (* x (factorial (- x 1)))))

Expressões S podem ser lidas em Lisp usando a função READ. READ lê a representação textual de uma expressão S e retorna dados Lisp. A função PRINT pode ser usada para produzir uma expressão S. A saída então pode ser lida com a função READ, quando todos os objetos de dados impressos têm uma representação legível. Lisp tem representações legíveis para números, strings, símbolos, listas e muitos outros tipos de dados. O código do programa pode ser formatado como expressões S bem impressas usando a função PPRINT (nota: com dois Ps, abreviação de pretty -print).

Os programas Lisp são expressões S válidas, mas nem todas as expressões S são programas Lisp válidos. (1.0 + 3.1)é uma expressão S válida, mas não um programa Lisp válido, uma vez que Lisp usa notação de prefixo e um número de ponto flutuante (aqui 1.0) não é válido como uma operação (o primeiro elemento da expressão).

Uma expressão S precedida por uma aspa simples, como em 'x, é um açúcar sintático para uma expressão S citada , neste caso (quote x).

Análise

As expressões S são frequentemente comparadas ao XML : a principal diferença é que as expressões S têm apenas uma forma de contenção, o par pontilhado, enquanto as tags XML podem conter atributos simples, outras tags ou CDATA , cada uma usando uma sintaxe diferente. Para casos de uso simples, as expressões S são mais simples do que XML, mas para casos de uso mais avançados, XML tem uma linguagem de consulta chamada XPath, muitas ferramentas e bibliotecas de terceiros para simplificar o manuseio de dados XML.

estandardização

Padrões para algumas linguagens de programação derivadas de Lisp incluem uma especificação para sua sintaxe de expressão S. Isso inclui Common Lisp (documento padrão ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS e R6RS ) e ISLISP .

Variante de Rivest

Consulte também: Expressões S canônicas

Em maio de 1997, Ron Rivest submeteu um Internet-Draft para ser considerado para publicação como um RFC . O rascunho definiu uma sintaxe baseada em expressões S do Lisp, mas destinada ao armazenamento e troca de dados de uso geral (semelhante ao XML ), em vez de especificamente para programação. Nunca foi aprovado como um RFC, mas desde então foi citado e usado por outros RFCs (por exemplo, RFC 2693) e várias outras publicações. Ele foi originalmente planejado para uso em SPKI .

O formato de Rivest define uma expressão S como sendo uma string de octetos (uma série de bytes ) ou uma lista finita de outras expressões S. Ele descreve três formatos de intercâmbio para expressar essa estrutura. Um é o "transporte avançado", que é muito flexível em termos de formatação e é sintaticamente semelhante às expressões do estilo Lisp, mas não são idênticas. O transporte avançado, por exemplo, permite que strings de octeto sejam representadas literalmente (o comprimento da string seguido por dois pontos e toda a string bruta), uma forma entre aspas permitindo caracteres de escape, hexadecimal , Base64 , ou colocada diretamente como um "token" se ele atende a certas condições. (Os tokens de Rivest diferem dos tokens Lisp porque os primeiros são apenas por conveniência e estética, e são tratados exatamente como outras strings, enquanto os últimos têm um significado sintático específico.)

O rascunho de Rivest define uma representação canônica "para fins de assinatura digital". Ele foi projetado para ser compacto, fácil de analisar e exclusivo para qualquer expressão S abstrata. Ele permite apenas strings textuais e proíbe espaços em branco como forma de strings externas. Finalmente, há a "representação de transporte básica", que é a forma canônica ou a mesma codificada como Base64 e cercada por colchetes , esta última destinada a transportar com segurança uma expressão S codificada canonicamente em um sistema que pode mudar o espaçamento (por exemplo, um e-mail sistema que tem linhas de 80 caracteres de largura e envolve qualquer coisa mais longa do que isso).

Este formato não foi amplamente adaptado para uso fora do SPKI (alguns dos usuários são GnuPG , libgcrypt, Nettle e GNU lsh). A página da web de expressões S de Rivest fornece código-fonte C para um analisador e gerador (disponível sob a licença do MIT ), que pode ser adaptado e embutido em outros programas. Além disso, não há restrições à implementação independente do formato.

Veja também

Referências

links externos