Livros sobre semântica da linguagem de programação

31

Eu tenho lido " Semantics with Applications ", de Nielson & Nielson , e gosto muito do assunto. Eu gostaria de ter mais um livro sobre semântica da linguagem de programação - mas eu realmente posso conseguir apenas um.

Dei uma olhada no livro de Turbak / Gifford , mas é muito longo; Eu pensei que Winskel ficaria bem, mas não tenho acesso a ele (não está na nossa biblioteca da Universidade e estou com pouco dinheiro), e nem tenho certeza se não está datado. Slonneger parece bom, mas a parte prática o torna um pouco longo demais, e eu não estou muito confortável com o estilo dele.

Então, minha pergunta é: Winskel é um bom livro? E é datado?

Além disso, existem outros livros concisos sobre o assunto?

reference-request pl.programming-languages semantics denotational-semantics books Jay
fonte
5
adicionou links às páginas do editor para todos os livros. pode ser útil para outras pessoas que procuram navegar.
Suresh Venkat
2
Em que tipo de semântica você está interessado? Denotacional? Operacional? Uma visão geral?
Ohad Kammar
@ Ohad Kammar: Estou interessado em ambos.
Jay

Respostas:

31

Tudo depende da profundidade que você quer ir e do quanto você já sabe. Para um iniciante, o livro de Winksel é muito bom, mas sim, não está apresentando o estado da arte da semântica, como foi escrito há cerca de 20 anos. No entanto, ainda é uma boa primeira introdução ao assunto. Também vale a pena ressaltar que T. Nipkow formalizou uma parte substancial do livro de Winskel em Isabelle / HOL, veja aqui . Portanto, se você quiser aprender a usar assistentes interativos de prova, além de entender a semântica das linguagens de programação, terá muito material coerente para usar.

Outros livros mais avançados são:

  • Gunter, Semântica das Linguagens de Programação , um livro mais avançado, focado na semântica denotacional, uma abordagem da semântica, que não atendeu às expectativas. Concentra-se em linguagens puramente funcionais e ignora a simultaneidade. Este é o livro do qual eu me ensinei semântica na graduação e, em retrospecto, eu gostaria de ter usado o livro de Winksel. Gunter não é uma leitura fácil para iniciantes.

  • Domínios e lambda-calculi de Amadio e Curien. Outro livro escrito mais na tradição teórica do domínio, embora discuta o cálculo do processo.

  • Livros de John Mitchell que já foram mencionados acima. Eles também são principalmente sobre computação seqüencial.

Livros como o TAPL de Pierce são muito bons, mas se concentram estreitamente em um aspecto das linguagens de programação, a saber, tipos, por mais importantes que sejam. Eu não o recomendaria como uma primeira introdução à área geral de linguagens de programação, mas é obrigatório ler para quem quiser aprender sobre tipos.

Verdade seja dita, acho que atualmente não há um livro introdutório atualizado sobre semântica de idiomas que reflita o progresso substancial que a década passada viu, com sua mudança decisiva dos métodos denotacionais e da computação seqüencial para a simultaneidade (cálculo de processos e semântica de jogos) , semântica axiomática e o uso de assistentes de prova interativos na verificação.

Atualização 22. Abril 2014: Tobias Nipkow e Gerwin Klein publicaram um novo livro

que pode ser visto como 'Winskel em Isabelle / HOL'. É uma introdução à semântica das linguagens de programação (principalmente operacional e axiomática), mas, ao contrário das abordagens anteriores baseadas em caneta e papel, este livro expressa toda a sua matemática em Isabelle / HOL. Em outras palavras, é ao mesmo tempo um livro sobre prova de teoremas.

O livro é novo em folha, por isso não usei para ensinar, mas parece realmente adequado como uma introdução que é lançada em um nível mais baixo do que o Software Foundations de Pierce et al.

Martin Berger
fonte
2
Existe uma mudança nos métodos denotacionais? Parece-me mais o tipo de pessoa que usaria provas onduladas à mão, hoje em dia se espera que produzam provas formais. Como os métodos denotacionais ainda não podem modelar com facilidade tudo o que fazemos e exigem muito mais pré-requisitos, esses pesquisadores usam métodos mais acessíveis, como jogos, cálculos de processos, assistentes de prova. Não tenho certeza se há um declínio nos métodos denotacionais.
Ohad Kammar
4
Por favor, não confunda semântica denotacional com teoria de domínio . A semântica de jogos pode ser, e geralmente é, perfeitamente denotacional, ou seja, o significado de um programa é uma função dos significados de suas partes.
Andrej Bauer
2
Abri um novo tópico sobre este comentário. Mas mesmo que eu não tenha certeza de que concordo com sua definição, a semântica de jogos é de natureza denotacional. Acho que devo substituir "jogos" por "semântica operacional" no meu comentário e incluir a semântica de jogos como possivelmente outra forma de pesquisa semântica denotacional. cstheory.stackexchange.com/questions/3577/…
Ohad Kammar
1
Não estou convencido de que haja uma mudança. Veja meu primeiro comentário, à luz do comentário de Andrej.
Ohad Kammar
1
Existe uma mudança? Uma pergunta interessante. Como podemos medir uma mudança? Existem muitos critérios que poderíamos aplicar, desde os relativamente concretos, como a quantidade de doações de novas pesquisas concedidas a diferentes abordagens, a idéias vagas, como o compartilhamento da mente. Dado o envolvimento de nós, pesquisadores, funcionários e candidatos a subsídios, no resultado dessa pergunta, é improvável que concordemos com uma resposta.
Martin Berger
20

Aqui está uma amostra aleatória de materiais disponíveis gratuitamente on-line:

  • Winskel, A Semântica Formal das Linguagens de Programação , pré-visualização do Google Livros . Não sei nada sobre este livro. Está na lista porque a pergunta é específica sobre o conteúdo, que é online, principalmente.
  • Morgan, Programming from Specification , lista de arquivos ps . O assunto é refinamento, que é o processo de iniciar com descrições não executáveis ​​de alto nível e transformar sistematicamente em algo executável. Obviamente, toda etapa de refinamento deve preservar a semântica, por isso também discute um certo tipo de semântica (principalmente com base nos formadores de predicado treansform).
  • Harper, Fundamentos Práticos de Linguagens de Programação , pdf of draft . Veja o comentário de Dave Clarke abaixo.
  • Remy, Usando, Compreendendo e Desvendando a Linguagem OCaml , pdf . Este é o livro do qual aprendi programação funcional (OCaml, mais precisamente) e gostei muito . Apresenta a semântica dos recursos básicos da linguagem de uma maneira muito agradável e, no processo, apresenta o cálculo lambda e a teoria dos tipos com base no "precisa saber".
  • Peyton Jones, A Implementação de Linguagens de Programação Funcional , djvu . Os primeiros capítulos descrevem o cálculo lambda (e sua `semântica operacional ') e como os recursos de linguagem de nível mais alto são sugeridos no cálculo lambda. Nesse sentido, o artigo fornece uma semântica operacional para linguagens funcionais.
  • Pierce (ed), Tópicos avançados em tipos e idiomas de programação , visualização do Google Livros .
  • Slonneger, Sintaxe e Semântica das Linguagens de Programação , lista de arquivos pdf . Eu olhei para isso brevemente há muito tempo e não gostei muito. Está na lista porque é mencionado na pergunta.
  • Brookes, Uma Semântica para Lógica de Separação Simultânea , pdf . Este é um grande artigo (80 páginas), não um livro. Eu o incluí porque é um desenvolvimento relativamente recente que acho interessante.
Radu GRIGore
fonte
1
isso é um monte de links :)
Suresh Venkat
3
Isso seria mais útil se tivesse sido apresentado como uma lista. De qualquer forma, recomendo o livro Harper: clique em "pode".
Dave Clarke
Concordo. Radu, você poderia listar os livros, para sabermos em que estamos clicando? isso seria um excelente recurso.
Suresh Venkat
É uma lista agora. (A primeira versão foi publicada por volta das 2h da manhã, depois de dormir cerca de 5h da noite anterior.: P)
Radu GRIGore
16

Eu dividiria os livros sobre semântica da linguagem de programação em duas classes: aquelas focadas na modelagem de conceitos da linguagem de programação e aquelas focadas nos aspectos fundamentais da semântica. Não há razão para que um livro não possa fazer as duas coisas. Mas, geralmente, há muito que você pode colocar em um livro, e os autores também têm suas próprias predisposições sobre o que é importante.

O livro de Winskel, já mencionado, aborda um pouco dos dois aspectos. E, é um bom livro para iniciantes. Um livro igualmente bom, talvez até melhor, é o que eu comecei: Descrição denotacional das linguagens de programação de Gordon . Este foi o meu primeiro livro sobre semântica, que li logo depois de terminar meu trabalho de graduação. Devo dizer que isso me deu uma base sólida na semântica e nunca tive que me perguntar como a semântica denotacional difere da semântica operacional ou semântica axiomática etc. Este livro continuará sendo meu favorito de todos os tempos na semântica denotacional.

Outros livros que se concentram nos aspectos de modelagem , e não nos aspectos fundamentais, são os seguintes:

  • Semântica das linguagens de programação da Tennent , que é um livro mais ou menos atualizado sobre a semântica das linguagens de programação imperativas. É fácil de ler. No entanto, tende a ser abstrato nas partes posteriores do livro e você pode ter que se esforçar para ver por que as coisas estão sendo feitas de uma maneira específica.

  • Teorias de Reynolds sobre linguagens de programação . Qualquer pessoa especializada em semântica deve definitivamente ler este livro. Afinal, é de Reynolds. (David Schmidt comentou uma vez para mim: "mesmo que Reynolds esteja lendo o jornal da manhã para você, você quer ouvir com atenção, porque pode aprender algo importante"!) Ele tem uma boa cobertura dos aspectos de modelagem e de fundamentos.

Os melhores livros sobre aspectos fundamentais são os de Gunter (que considero um livro de pós-graduação) e os de Mitchell (que é um bom livro de referência para se ter em sua estante, porque é bastante abrangente).

Uday Reddy
fonte
É muito bom ter você aqui, Uday!
Radu GRIGore
Estou feliz por estar aqui também. Este é um recurso muito bom!
Uday Reddy
Que tal: Transições e árvores: uma introdução à semântica operacional estrutural de Hans Hüttel 2010. Parece ter boas críticas, mas ninguém menciona aqui.
Arturo Hernandez
1
@ Dia: Obrigado pela resposta. O que significam "modelar conceitos de linguagem de programação" e "os aspectos fundamentais da semântica"? Quais são as suas diferenças e relações?
Tim
1
@ Tim: Para fornecer a semântica de uma linguagem de programação, você precisa formar estruturas matemáticas, por exemplo, conjuntos no caso mais simples, mas estruturas sofisticadas como domínios, categorias, barras de carvão etc. para problemas que os conjuntos não conseguem lidar. Por "aspectos fundamentais", refiro-me à teoria dessas estruturas mais sofisticadas. No primeiro caso, o foco está nas linguagens de programação e, no último caso, nos fundamentos matemáticos.
precisa saber é o seguinte
8

Eu realmente gostei de ler Winskel quando estava no curso de graduação em semântica. Não sei dizer se é datado, já que não faço pesquisa nesse campo. Uma vantagem do Winskel é que você pode encontrá-lo traduzido em outros idiomas que não o inglês.

Para uma leitura mais aprofundada, mais em nível de pós-graduação, sugiro os livros de John Mitchell, Fundamentos para linguagens de programação e conceitos em linguagens de programação . Se você ler apenas os primeiros capítulos, acho que eles também atendem às suas exigências de concisão.

Você não encontrará rascunhos gratuitos desses livros; portanto, se você tiver um orçamento restrito, procure o "poder" na resposta de Radu.

Alessandro Cosentino
fonte
6

Bem, não sou especialista no assunto, mas há alguns conselhos gerais que posso dar.

Primeiro, há algumas pessoas que já leram o livro e forneceram críticas sobre ele. Por exemplo, para o livro de Winskel, The Semantics Formal of Programming Languages (veja [1] e [2] ), encontrei resenhas na Amazon.

Parte de uma revisão diz:

Este livro confunde sintaxe e semântica desde o início, como separar os literais de seus valores. Nenhuma notação especial foi usada para diferenciá-las. Esta é uma questão crucial que o autor deve abordar em um tópico como este. Além disso, algumas outras anotações que ele usou são bastante confusas, como mostrar as premissas e conclusões.

O autor parecia presumir que você possui TODOS os pré-requisitos necessários ao explicar os materiais de base nos primeiros capítulos (isto é, teoria dos conjuntos, semântica operacional, induções, definições indutivas) muito brevemente. O estilo usado pelo autor na introdução é colocar dois ou três parágrafos de texto e colocar algumas fórmulas e depois dar exercícios. O que é, para mim, bastante frustrante ...

18/20 pessoas acham o comentário útil. Você pode procurar na Amazon (ou em outras fontes) para ver mais avaliações.

Segundo, a Amazon oferece tipos e linguagens de programação e teoria básica de categorias para cientistas da computação, juntamente com este livro. Em outro tópico, Dave Clarke oferece esses livros como excelentes em "Sistemas de tipos e semântica da linguagem de programação". Mais uma vez, não sou especialista, mas esses podem ser úteis para você.

MS Dousti
fonte
O TaPL fica um pouco lento demais para o meu gosto. É um bom livro, mas mencionei isso porque a pessoa que pergunta parece preocupada com os livros "longos".
Radu GRIGore
@ Radu: Certamente o TAPL é lento, mas é uma introdução bastante boa. O livro do Harper que você mencionou nos seus links é muito mais rápido e cobre muito mais terreno, embora ainda não tenha sido concluído.
Dave Clarke
4
Tome essa resenha da Amazon do livro de Winskel com uma pitada de sal. É frequentemente usado como um texto recomendado nos cursos de semântica da graduação e possivelmente atrai estudantes insatisfeitos. Eu li o livro e achei os capítulos introdutórios mais do que suficientes. Sua notação por toda parte parecia ser completamente padrão também.
Dominic Mulligan