O que é uma espécie na semântica da linguagem de programação?

9

No capítulo 1 de Fundamentos práticos para linguagens de programação , o autor menciona que as árvores de sintaxe abstratas estão associadas a tipos .

Intuitivamente, as classificações são como tipos, mas eu gostaria de saber se elas têm uma definição precisa. Ficaria feliz se algumas referências também forem fornecidas.

rslima
fonte

Respostas:

4

Depende da semântica que usaríamos para tipos e tipos. + No entanto, uma breve - pouca informal - definição pode ser + Os tipos são classes de ASTs e os tipos são classes de valores .

Número47
fonte
4

Na verdade, há muita semelhança entre as classificações para a sintaxe e os tipos abstact, como normalmente entendido. Porém, as sortes são um conceito sintático formal , e as árvores AS também são sintaxe, enquanto os tipos são um conceito semântico .

A terminologia vem do termo álgebra (também chamado de álgebra livre ) e álgebra universal . São teorias essencialmente sintáticas de estruturas algébricas, analisadas independentemente de quaisquer interpretações. Eles foram desenvolvidos na primeira metade do século XX.

Um termo pode ser visto como uma árvore, onde os nós são rotulados a partir de um conjunto finito de operadores, cada operador tendo uma aridade fixa que especifica o número de filhas na árvore. Arity 0 é para folhas. Nas álgebras com várias classificações, isso é refinado com classificações, de modo que cada operador pertence a uma classificação e as regiões são substituídas por uma lista ordenada de classificações, que corrige para cada filha o tipo de operador principal. O tipo de operador, juntamente com a lista dos tipos de sua filha, é chamado de assinatura do operador.

Nas álgebras universais, isso é refinado pela introdução de relações de equivalência definidas equacionalmente entre termos.

Embora pareça ter diminuído um pouco, esses conceitos eram bastante populares e muito estudados em ciência da computação no final do século XX, como álgebras abstratas, que eram vistas como uma base para tipos de dados abstratos, que é, em parte, precursor do que é nas classes em programação orientada a objetos.

As álgebras universais estão relacionadas ao desenvolvimento da teoria das categorias, que também é fundamental na visão atual de tipos e linguagens de programação.

As álgebras são objetos sintáticos e devem ser usadas com uma interpretação em alguns domínios semânticos correspondentes aos tipos. Uma interpretação é um homomorfismo que mapeia as classificações em domínios de valores (tipos) e os operadores em funções entre esses domínios, para que as assinaturas sejam respeitadas e as equações também no caso de uma álgebra equacional. É assim que você pode aplicar os resultados da teoria de grupos a qualquer domínio com uma operação que respeite a definição de um grupo.

Essa organização foi considerada muito conveniente pelos primeiros pesquisadores em linguagens de programação, especialmente aqueles preocupados com a formalização de linguagens de programação. Teve a vantagem de isolar sintaxe e semântica e de ser matematicamente bem compreendido.

Outro motivo para adotá-lo foi a preocupação com o desenvolvimento de uma ferramenta para manipular programas, seja em ambientes de desenvolvimento ou em sistemas formais para provar propriedades de programas (que se mostraram cada vez mais problemas gêmeos).

Isso levou ao surgimento do conceito de árvore de sintaxe abstrata (AST) para linguagens de programação, que são essencialmente termos de uma álgebra com classificação múltipla (algumas vezes refinada com o uso da união de classificação em alguns sistemas). O AST é a sintaxe de referência para uma linguagem, a partir da qual a semântica pode ser definida pelo homomorfismo, como na semântica denotacional.

Isso não é apenas conveniente para estudar semântica de linguagens, mas as árvores são mais bem estruturadas que as strings e, portanto, uma base melhor para o desenvolvimento de ferramentas de programação e ambientes de programação.

Ele permite isolar a análise, que era tradicionalmente uma parte confusa, pois as limitações da tecnologia de análise forçavam o uso de gramáticas distorcidas. Isso também leva em consideração os problemas de apresentação.

Ele permite várias representações concretas (de seqüência de caracteres ou gráficas) de programas, o que às vezes pode ser conveniente (não há motivo para usar a pontuação em vez de guias, ou o inverso, na sintaxe do programa deve ser imposta às pessoas).

Facilita a definição de muitas interpretações de programas e de vários tipos , a fim de analisar as propriedades do programa com interpretações abstratas.

É conveniente para escrever ferramentas de manipulação de programas (semi-) automatizadas, por exemplo, para transformações automáticas de programas ou traduções entre idiomas.

Às vezes, as coisas podem ser um pouco mais complicadas na prática, porque algumas formas da Sintaxe Abstrata permitem que alguns operadores construam árvores (expressões) que pertencem a vários tipos (uma maneira informal de ver isso). Por exemplo, pode haver uma classificação para construções sintáticas que representam variáveis ​​(entidades atribuíveis) e outra para expressões. Mas qualquer variável pode ser usada como expressão, sendo o inverso falso.

Os primeiros artigos sobre isso, para linguagens de programação, datam de meados dos anos setenta. A conceituação da época destinava-se à produção de ambientes de programação conscientes em sintaxe (a palavra "direcionado" era então usada). Procure Mentor e Centaur na Europa e Cornell Program Synthesizer nos EUA. Eles foram os dois primeiros sistemas a realmente usar esses conceitos de maneira prática. Muitos outros foram desenvolvidos depois.

Mas a sintaxe abstrata é anterior a esses sistemas. A linguagem Lisp (1958) tinha sintaxe abstrata, o que não é surpresa, pois foi desenvolvida por um lógico e com o objetivo de criar programas que manipulam programas (veja também ML e LCF ... que vieram mais tarde). Mas Lisp não foi classificado: tudo era sintaticamente uma lista e uma estrutura mais refinada dependia essencialmente da semântica. Isso levou algumas pessoas a considerar, de maneira um tanto incorreta, que o Lisp não tinha sintaxe.

babou
fonte
Você diria que existem 2 hierarquias diferentes, uma na região da sintaxe e outra na região da semântica. Na sintaxe, temos como você ASTs e tipos e classes de tipos. Na semântica, temos valores, tipos, tipos ... etc. Não existem linguagens que unifiquem ambos em um ambiente de desenvolvimento como Twelf ou Coq?
CMCDragonkai
@CMCDragonkai Eu diria (exceto possíveis erros) exatamente o que eu disse. Eu não chamaria essas hierarquias, mas domínios de (meta) discurso. A separação sintaxe-semântica distingue o que falamos e como o fazemos, o que requer representação. Você não deve querer misturar sintaxe e semântica do mesmo idioma, mas a sintaxe de um idioma pode ser um objeto de discurso, portanto, pertence à semântica de outro idioma. Nesse sentido, você pode ver alguma unificação, para ser tratado com cuidado. A sintaxe é sempre gerada finitamente, enquanto a semântica não tem essa restrição.
babou 02/02
2

Parece no capítulo quatro que os tipos são para sintaxe e os tipos são para semântica.

O exemplo de gráfico de sintaxe na página 40 lida com os tipos no idioma L {num str}. Aparentemente, tipos são categorias na sintaxe do idioma.

Em particular, "mais" tem uma classificação, que é a categoria sintática do seu resultado. O tipo de operador "mais" é nomeado "Exp". Isso representa o fato de que, sintaticamente, uma invocação do operador "mais" é uma expressão. Uma invocação do operador "mais" pode preencher uma posição em uma árvore de sintaxe abstrata onde uma expressão é permitida. Esse é o tipo de construção que é um "mais". É assim que ele se encaixa na estrutura de um texto que representa um programa.

O sistema de tipos na página 41 lida com os tipos no idioma L {num str}. O tipo de operador "mais", considerando que seus operandos têm o tipo "num", é "num". Este julgamento é uma descrição parcial da semântica do operador "plus". Ou seja, parte do significado do operador "mais" é a combinação de dois números para produzir um número. Este significado distingue "mais" de outras expressões.

Além disso, existe uma classificação chamada "Typ" que contém os dois tipos, "num" e "str".

minopret
fonte
11
Bem, ele usa esse conceito, mas ele não o define claramente. Encontrei o termo "lógica de classificação múltipla", que me parece que tipos e tipos são conceitos relacionados realmente fechados. Eu só queria saber uma definição clara para ambos.
Rslima
É algo a ver com "sistemas de tipo puro". Eu suspeito que poderíamos considerar a apresentação em " Lambda Calculi with Types " como convencional. Mas não é conciso. Ainda não encontrei uma referência que forneça definições claras e concisas de termo, tipo, tipo e classificação.
Minopret
E quanto aos chefes de produção em um analisador? Muitas vezes, você acaba classificando gramáticas com nomes semelhantes, como Expressão ou Tipo.
CMCDragonkai
1

No início do capítulo 1, Harper dá uma dica do que ele quer dizer com a palavra tipo :

A sintaxe de um idioma especifica os meios pelos quais vários tipos de frases (expressões, comandos, declarações etc.) podem ser combinados para formar programas.

Ele define a palavra frase como uma árvore de sintaxe abstrata, que ele discute.

jcora
fonte
Parece-me que "sortes" foram usadas com seu significado habitual em inglês aqui, sinônimo de "sortes".
Raphael
@ Rafael Sim, mas parece que esse significado é consistente com o último uso formal, você não concorda?
jcora
Não é bem assim. A frase "esse tipo de X" pode aparecer frequentemente no livro; esta frase não indica de forma alguma que algo está sendo definido. (Além disso, esta passagem não corresponde à maneira como entendo o termo "classificação").
Raphael
@ Rafael OK, por favor, explique como esse uso específico é inconsistente, certamente me informaria, porque é assim que eu o entendo atualmente.
jcora
A noção de "classificação" que eu conheço está associada a nós individuais do AST, não a uma árvore inteira (que é o que você diz "frase" significa na sua fonte).
Raphael