Teoria da linguagem de programação - Programming language theory
A teoria da linguagem de programação ( PLT ) é um ramo da ciência da computação que lida com o projeto, implementação, análise, caracterização e classificação de linguagens formais conhecidas como linguagens de programação e de seus recursos individuais . Ela se enquadra na disciplina de ciência da computação, dependendo e afetando matemática , engenharia de software , lingüística e até mesmo ciências cognitivas . Tornou-se um ramo bem conhecido da ciência da computação e uma área de pesquisa ativa, com resultados publicados em inúmeras revistas dedicadas à PLT, bem como em publicações de ciência da computação e engenharia em geral.
História
De certa forma, a história da teoria da linguagem de programação antecede até mesmo o desenvolvimento das próprias linguagens de programação. O cálculo lambda , desenvolvido por Alonzo Church e Stephen Cole Kleene na década de 1930, é considerado por alguns como a primeira linguagem de programação do mundo, embora tivesse a intenção de modelar computação em vez de ser um meio para os programadores descreverem algoritmos para um sistema de computador . Muitas linguagens de programação funcional modernas foram descritas como fornecendo um "verniz fino" sobre o cálculo lambda, e muitas são facilmente descritas em termos dele.
A primeira linguagem de programação a ser inventada foi Plankalkül , projetada por Konrad Zuse na década de 1940, mas não conhecida publicamente até 1972 (e não implementada até 1998). A primeira linguagem de programação de alto nível amplamente conhecida e bem - sucedida foi a Fortran , desenvolvida de 1954 a 1957 por uma equipe de pesquisadores da IBM liderada por John Backus . O sucesso do FORTRAN levou à formação de um comitê de cientistas para desenvolver uma linguagem de computador "universal"; o resultado de seu esforço foi ALGOL 58 . Separadamente, John McCarthy, do MIT, desenvolveu o Lisp , a primeira linguagem com origem na academia a ter sucesso. Com o sucesso desses esforços iniciais, as linguagens de programação se tornaram um tópico ativo de pesquisa na década de 1960 e além.
Alguns outros eventos importantes na história da teoria da linguagem de programação desde então:
Década de 1950
- Noam Chomsky desenvolveu a hierarquia de Chomsky no campo da linguística, uma descoberta que impactou diretamente a teoria da linguagem de programação e outros ramos da ciência da computação.
Década de 1960
- A linguagem Simula foi desenvolvida por Ole-Johan Dahl e Kristen Nygaard ; é amplamente considerado o primeiro exemplo de uma linguagem de programação orientada a objetos ; Simula também introduziu o conceito de co-rotinas .
- Em 1964, Peter Landin é o primeiro a perceber que o cálculo lambda de Church pode ser usado para modelar linguagens de programação. Ele apresenta a máquina SECD que "interpreta" expressões lambda.
- Em 1965, Landin introduz o operador J , essencialmente uma forma de continuação .
- Em 1966, Landin apresenta ISWIM , uma linguagem de programação de computador abstrata em seu artigo The Next 700 Programming Languages . É influente no design de linguagens que levam à linguagem de programação Haskell .
- Em 1966, Corrado Böhm introduziu a linguagem de programação CUCH (Curry-Church).
- Em 1967, Christopher Strachey publica seu conjunto influente de palestra notas Conceitos Fundamentais de Linguagens de Programação , introduzindo a terminologia valores de R , L-valores , polimorfismo paramétrico , e polimorfismo ad hoc .
- Em 1969, J. Roger Hindley publica O esquema de tipo principal de um objeto em lógica combinatória , mais tarde generalizado no algoritmo de inferência de tipo de Hindley-Milner .
- Em 1969, Tony Hoare introduz a lógica Hoare , uma forma de semântica axiomática .
- Em 1969, William Alvin Howard observou que um sistema de prova de "alto nível" , conhecido como dedução natural , pode ser interpretado diretamente em sua versão intuicionista como uma variante tipada do modelo de computação conhecido como cálculo lambda . Isso ficou conhecido como correspondência Curry-Howard .
Década de 1970
- Em 1970, Dana Scott publica pela primeira vez seu trabalho sobre semântica denotacional .
- Em 1972, a programação lógica e o Prolog foram desenvolvidos, permitindo assim que os programas de computador fossem expressos como lógica matemática.
- Uma equipe de cientistas do Xerox PARC liderada por Alan Kay desenvolveu Smalltalk , uma linguagem orientada a objetos amplamente conhecida por seu ambiente de desenvolvimento inovador.
- Em 1974, John C. Reynolds descobre Sistema F . Já havia sido descoberto em 1971 pelo lógico matemático Jean-Yves Girard .
- A partir de 1975, Gerald Jay Sussman e Guy Steele desenvolveram a linguagem de programação Scheme , um dialeto Lisp que incorpora escopo léxico , um namespace unificado e elementos do modelo de ator, incluindo continuações de primeira classe .
- Backus, na palestra do Prêmio Turing de 1977 , atacou o estado atual das linguagens industriais e propôs uma nova classe de linguagens de programação agora conhecidas como linguagens de programação em nível de função .
- Em 1977, Gordon Plotkin apresenta Programming Computable Functions , uma linguagem funcional tipificada abstrata.
- Em 1978, Robin Milner apresenta o algoritmo de inferência de tipo Hindley-Milner para ML . A teoria dos tipos foi aplicada como uma disciplina às linguagens de programação. Essa aplicação levou a enormes avanços na teoria dos tipos ao longo dos anos.
Década de 1980
- Em 1981, Gordon Plotkin publica seu artigo sobre semântica operacional estruturada .
- Em 1988, Gilles Kahn publicou seu artigo sobre semântica natural .
- Surgiram cálculos de processo , como o Cálculo de Sistemas de Comunicação de Robin Milner e o modelo de processos sequenciais de Comunicação de CAR Hoare , bem como modelos semelhantes de simultaneidade, como o modelo de ator de Carl Hewitt .
- Em 1985, o lançamento de Miranda despertou um interesse acadêmico em linguagens de programação puramente funcionais avaliadas preguiçosamente. Um comitê foi formado para definir um padrão aberto resultando no lançamento do padrão Haskell 1.0 em 1990.
- Bertrand Meyer criou a metodologia Design by contract e a incorporou à linguagem de programação de Eiffel .
Década de 1990
- Gregor Kiczales , Jim Des Rivieres e Daniel G. Bobrow publicaram o livro The Art of the Metaobject Protocol .
- Eugenio Moggi e Philip Wadler introduziram o uso de mônadas para estruturar programas escritos em linguagens de programação funcionais .
Existem vários campos de estudo que estão dentro da teoria da linguagem de programação, ou que têm uma profunda influência sobre ela; muitos deles têm uma sobreposição considerável. Além disso, o PLT faz uso de muitos outros ramos da matemática , incluindo a teoria da computabilidade , a teoria das categorias e a teoria dos conjuntos .
Semântica formal
A semântica formal é a especificação formal do comportamento de programas de computador e linguagens de programação. Três abordagens comuns para descrever a semântica ou "significado" de um programa de computador são semântica denotacional , semântica operacional e semântica axiomática .
Teoria de tipo
A teoria dos tipos é o estudo dos sistemas de tipos ; que são "um método sintático tratável para provar a ausência de certos comportamentos de programa, classificando frases de acordo com os tipos de valores que elas calculam". Muitas linguagens de programação são diferenciadas pelas características de seus sistemas de tipos.
Análise e transformação do programa
A análise do programa é o problema geral de examinar um programa e determinar as características principais (como a ausência de classes de erros de programa ). A transformação do programa é o processo de transformar um programa de uma forma (linguagem) para outra.
Análise comparativa de linguagem de programação
A análise comparativa de linguagens de programação busca classificar as linguagens de programação em diferentes tipos com base em suas características; categorias amplas de linguagens de programação são freqüentemente conhecidas como paradigmas de programação .
Genérico e metaprogramação
Metaprogramação é a geração de programas de ordem superior que, quando executados, produzem programas (possivelmente em um idioma diferente ou em um subconjunto do idioma original) como resultado.
Linguagens específicas de domínio
Linguagens específicas de domínio são linguagens construídas para resolver com eficiência problemas de uma parte específica do domínio.
Construção do compilador
A teoria do compilador é a teoria de escrever compiladores (ou, mais geralmente, tradutores ); programas que traduzem um programa escrito em um idioma para outro formato. As ações de um compilador são tradicionalmente divididas em análise de sintaxe ( varredura e análise ), análise semântica (determinando o que um programa deve fazer), otimização (melhorando o desempenho de um programa conforme indicado por alguma métrica; normalmente velocidade de execução) e geração de código (geração e saída de um programa equivalente em algum idioma de destino; geralmente o conjunto de instruções de uma CPU).
Sistemas de tempo de execução
Os sistemas de tempo de execução referem-se ao desenvolvimento de ambientes de tempo de execução de linguagem de programação e seus componentes, incluindo máquinas virtuais , coleta de lixo e interfaces de função externa .
Revistas, publicações e conferências
As conferências são o principal local para apresentar pesquisas em linguagens de programação. As conferências mais conhecidos incluem o Simpósio sobre Princípios de Linguagens de Programação (popl), Programação Design Língua e Implementação (PLDI), a Conferência Internacional sobre a programação funcional (ICFP), a Conferência Internacional sobre Programação Orientada a Objetos, Sistemas, Linguagens e Aplicações ( OOPSLA) e a Conferência Internacional sobre Suporte Arquitetônico para Linguagens de Programação e Sistemas Operacionais (ASPLOS) .
Periódicos notáveis que publicam pesquisas PLT incluem o ACM Transactions on Programming Languages and Systems (TOPLAS), Journal of Functional Programming (JFP), Journal of Functional and Logic Programming e Higher-Order and Symbolic Computation .
Veja também
Referências
Leitura adicional
- Abadi, Martín e Cardelli, Luca . A Theory of Objects . Springer-Verlag.
- Michael JC Gordon . Teoria da Linguagem de Programação e sua implementação . Prentice Hall.
- Gunter, Carl e Mitchell, John C. (eds.). Aspectos Teóricos das Linguagens de Programação Orientada a Objetos: Tipos, Semântica e Projeto de Linguagem . MIT Press.
- Harper, Robert . Fundamentos práticos para linguagens de programação . Versão preliminar.
- Knuth, Donald E. (2003). Artigos Selecionados em Linguagens de Computação . Stanford, Califórnia: Centro para o Estudo da Linguagem e da Informação.
- Mitchell, John C .. Fundamentos para linguagens de programação .
- Mitchell, John C .. Introdução à Teoria da Linguagem de Programação .
- O'Hearn, Peter. W. e Tennent, Robert. D. (1997). Linguagens semelhantes a Algol . Progresso em Ciência da Computação Teórica. Birkhauser, Boston.
- Pierce, Benjamin C. (2002). Tipos e linguagens de programação . MIT Press.
- Pierce, Benjamin C. Tópicos Avançados em Tipos e Linguagens de Programação .
- Pierce, Benjamin C. et al. (2010). Fundações de software .
links externos
- Lambda the Ultimate , um weblog da comunidade para discussão profissional e repositório de documentos sobre teoria da linguagem de programação.
- Ótimos trabalhos em linguagens de programação . Coletado por Benjamin C. Pierce ( Universidade da Pensilvânia ).
- Artigos Clássicos em Linguagens de Programação e Lógica . Coletado por Karl Crary ( Carnegie Mellon University ).
- Pesquisa em Linguagem de Programação . Diretório de Mark Leone .
- Textos Online de Teoria da Linguagem de Programação . Na Universidade de Utrecht .
- λ-Calculus: Then & Now de Dana S. Scott para a celebração do centenário de ACM Turing
- Grandes desafios em linguagens de programação . Sessão do painel no POPL 2009.