“As causas pelas quais os movimentos verdadeiros e relativos são diferenciados, um do outro, são as forças imprimidas sobre os corpos para gerar movimento.”
Principia, Newton
Linguagens de programação são sistemas formais de símbolos e regras usados para descrever computações de maneira compreensível por humanos e executável por máquinas. Cada linguagem possui uma sintaxe, isto é, regras de formação de programas, e uma semântica, isto é, regras que determinam o significado das construções válidas.
Além de sintaxe e semântica, uma linguagem também envolve bibliotecas, modelo de execução, sistema de tipos, mecanismos de abstração e ferramentas de tradução, como compiladores e interpretadores. No estudo teórico de linguagens, interessa entender não apenas como escrever programas, mas também como descrevê-los formalmente, analisá-los e executá-los.
Um parser é o componente que recebe uma sequência de tokens e constrói uma representação sintática estruturada do programa. Em determinadas operações, a notação pode variar bastante de linguagem para linguagem. Por exemplo, a soma de dois números pode ser escrita de diversas maneiras:
A representação textual que o programador escreve é chamada sintaxe concreta. Internamente, no entanto, ferramentas de compilação e interpretação costumam converter esse texto em formas intermediárias mais convenientes, como árvores sintáticas abstratas. Em linguagens da família Lisp, por exemplo, a própria forma textual já se aproxima bastante dessas estruturas internas por meio de S-expressions.
Suponha um código que simplesmente imprime na tela "Hello" em Python:
print("Hello")Os seguintes são os passos que esse programa vai passar:
Expressões regulares são úteis sobretudo na análise léxica, mas não bastam para descrever toda a estrutura sintática de linguagens de programação reais, que exigem gramáticas mais expressivas.
No conversor utiliza-se a forma Backus-Naur, que é a notação para descrever a gramática de uma linguagem. Por exemplo:
Program
: StatementList
;
Statement
: BlockStatement
| IfStatement
| FunctionDeclaration
...
;
FunctionDeclaration
: def Identifier ( Arguments ) BlockStatement
;
Da árvore abstrata de sintaxe, para a expressão “7+3*4”, a seguinte estrutura em notação JSON:
{
type : "BinaryExpression",
operator: "+",
left : {
type : "NumericLiteral",
value : 7
},
right : {
type: "BinaryExpression",
operator : "*",
left : {
type : "NumericLiteral",
value : 3
},
right : {
type : "NumericLiteral",
value : 4
}
}
}
Esse exemplo mostra como expressões complexas podem conter subexpressões aninhadas, permitindo descrever de forma estruturada qualquer expressão válida da linguagem.
Entre as técnicas comuns de parsing estão parsers descendentes recursivos, LL, LR e suas variantes, cada uma adequada a diferentes classes de gramáticas.
Paradigmas de programação são estilos gerais de organizar programas e resolver problemas. Eles influenciam como modelamos dados, controle, efeitos colaterais, abstrações e composição de operações.
Uma divisão clássica separa linguagens em estilos imperativos e declarativos. No estilo imperativo, o programa descreve explicitamente como a computação evolui por mudanças de estado, atribuições e comandos de controle. No estilo declarativo, o foco recai mais sobre o que deve ser obtido do que sobre a sequência exata de passos para chegar ao resultado.
Na programação procedural, o programa é estruturado em procedimentos e funções. São exemplos tradicionais FORTRAN, ALGOL, COBOL, Pascal e C. Esse estilo enfatiza decomposição em sub-rotinas e fluxo de controle explícito.
Na programação orientada a objetos, os programas são organizados em torno de objetos, classes, encapsulamento, herança e polimorfismo. Linguagens como Java, C++, C# e Python oferecem suporte, em maior ou menor grau, a esse paradigma.
Há ainda paradigmas voltados para concorrência e paralelismo, nos quais múltiplas atividades podem ser executadas simultaneamente ou de forma intercalada. Isso traz ganhos de desempenho, mas também introduz problemas de sincronização, exclusão mútua e coordenação entre processos ou threads.
No caso declarativo, destacam-se os paradigmas lógico, funcional e de consulta a dados. Neles, procura-se expressar propriedades, relações ou transformações desejadas sem detalhar completamente o fluxo operacional.
O paradigma lógico abstrai um modelo computacional e tenta resolver certas tarefas através de uma base de conhecimento e as informações do problema que se tenta concluir. A execução do programa é como uma sequência de proposições matemáticas. Exemplo: Prolog.
A programação funcional tem raízes na lógica e no cálculo lambda. Nela, funções são tratadas como entidades centrais, valores tendem a ser imutáveis e a composição funcional assume papel fundamental. Recursão, funções de alta ordem e ausência ou redução de efeitos colaterais são características comuns desse estilo. São exemplos Haskell, Lisp, ML, Erlang e partes importantes de Scala.
No paradigma de consulta a dados, o foco está em especificar quais dados devem ser obtidos ou transformados, em vez de detalhar passo a passo como percorrê-los. SQL é o exemplo mais conhecido.
Para descrever linguagens de programação com rigor, recorremos a ferramentas matemáticas. Começamos definindo um alfabeto, isto é, um conjunto finito de símbolos. Uma linguagem pode então ser entendida como um subconjunto das cadeias finitas formadas com esses símbolos.
Definição: Seja A={A,B,C} um alfabeto. Se U é um conjunto de todas as strings finitas cujos símbolos estão em A, dizemos que qualquer subconjunto L de U é uma linguagem.
Exemplo: A={0,1,2,3,4,5,6,7,8,9}, é o alfabeto. L = { 12, 142, 1242, 55, 9999 } é um exemplo de linguagem.
Quando precisamos especificar certos subconjuntos de cadeias, utilizamos expressões regulares, que são notações formais adequadas para descrever padrões léxicos.
Exemplos: abcd, (defg)+, vermelho | verde | azul, etc…
Como expressões regulares têm limitações expressivas, linguagens de programação reais precisam de gramáticas formais para descrever sua estrutura sintática. Antes disso, porém, o texto-fonte costuma ser decomposto em tokens, que são unidades léxicas como identificadores, palavras-chave, operadores e literais.
Definição: Dado um conjunto de tokens T e uma linguagem L formada por sequências finitas de tokens de T, a sintaxe de L é o conjunto de regras que define de forma exata qual sequência de tokens estão em L.
Essas regras também são chamadas de regras sintáticas, gramática formal ou simplesmente gramática. Elas podem ser subdivididas em: gramáticas livres de contexto e regulares. O modo de representação é o BNF, já exposto anteriormente. Cada gramática é definida de uma ou mais produções (ou regras de produção) que, por sua vez, são compostas de elementos chamados “não-terminais” ou “terminais”. Cada produção é feita de uma lista não ordenada de escolhas separadas por | (pipe). Um terminal é um token.
Exemplo: Seja T o conjunto de tokens de uma linguagem. T = { true, false, or, and, not, (,), , }
Uma gramática na forma BNF pode ser escrita como:
program ::= true
| false
| and (program, program)
| or (program, program)
| not (program)
Disso temos que L, a linguagem, possui infinitas combinações desses tokens com essas regras:
L = {
or (false, and (true, false)),
and (true, false),
not (false),
…
}
Chamamos de sintaxe concreta a forma textual que obedece às regras da linguagem. A sintaxe abstrata, por sua vez, procura reter apenas a estrutura essencial dessas construções, normalmente por meio de árvores sintáticas abstratas (ASTs).
Para converter uma instância de sintaxe concreta em tokens utilizamos um lexer ou tokenizador (tokenizer). Um parser, ou conversor, é um algoritmo que transforma uma sequência de tokens em uma instância de sintaxe abstrata, uma árvore de conversão. A representação BNF pode ser utilizada para criar um algoritmo de parser, a complexidade desse processo depende das regras de gramática.
Quando uma gramática satisfaz certas restrições, ela pode ser analisada por algoritmos preditivos, como parsers LL(1). Em outros casos, recorremos a técnicas com retrocesso, tabelas LR ou estratégias mais gerais. A escolha do algoritmo depende da estrutura da gramática e dos requisitos da implementação.
Depois da sintaxe, precisamos associar significado aos programas. Isso pode ser feito por diferentes abordagens formais, entre elas a semântica denotacional, que associa construções sintáticas a objetos matemáticos, e a semântica operacional, que descreve como a computação evolui passo a passo.
Um mapa de A para D, onde A é um conjunto de instâncias de sintaxe abstrata e D um conjunto de objetos matemáticos, dito domínio semântico ou apenas domínio. O mapa é frequentemente escrito como [[ .. ]].
A semântica operacional é frequentemente apresentada por regras de inferência. Em versões small-step, descrevemos pequenas transições de computação; em versões big-step, descrevemos diretamente a avaliação de uma expressão ou comando até seu resultado final. Essas regras ajudam a formalizar o comportamento da linguagem.
$[\text{Exemplo}] \frac{\text{dia de sol céu limpo}}{\text{não chove}}$
Onde na parte superior da barra temos as premissas e abaixo as conclusões.
Em muitos formalismos, expressões são vistas como construções cujo objetivo principal é produzir valores. Já comandos ou statements enfatizam alterações de estado e efeitos colaterais, sendo por isso centrais em linguagens imperativas.
Um interpretador é um algoritmo que implementa essas regras de avaliação ou execução, diretamente ou por meio de estruturas equivalentes.
Um tipo pode ser entendido como uma classificação de valores e operações admissíveis sobre eles. Sistemas de tipos ajudam a organizar programas, documentar intenções, detectar erros e orientar otimizações e verificações automáticas.
Usar tipos permite que alguém possa ler, entender e dar manutenção ao programa de forma organizada, ou seja, auxiliam no design escolhido para o código. Adicionalmente, tipos podem ser utilizados para otimizações de código. Em algumas linguagens, o sistema de tipos também pode ser utilizado para localizar certas partes de um objeto complexo.
Uma linguagem é dita type-safe quando suas regras impedem, em condições normais de execução, o uso inconsistente de valores como se pertencessem a tipos incompatíveis.
Type cast é a conversão explícita de um tipo para outro, quando a linguagem permite essa operação.
Algumas linguagens podem verificar em tempo de compilação e/ou execução se houve alguma violação das regras de tipagem do sistema.
Polimorfismo é a capacidade de uma mesma construção operar sobre valores de formas diferentes, dependendo do contexto de tipagem. Em teoria de tipos, costuma-se destacar pelo menos três formas importantes: polimorfismo paramétrico, polimorfismo ad hoc e polimorfismo de subtipo.
Paramétrico: uma função ou estrutura é escrita de forma genérica, podendo operar uniformemente sobre vários tipos sem depender de detalhes específicos de cada um.
T identidade<T>(T valor) {
return valor;
}
int a = identidade<int>(10);
string b = identidade<string>("abc");
Ad hoc: ocorre quando o mesmo nome é usado para implementações diferentes, como em sobrecarga de funções ou operadores.
Subtipo: valores de tipos mais específicos podem ser usados onde um tipo mais geral é esperado, desde que respeitem a interface ou o contrato correspondente.
class Animal {
public void fazerSom() {
System.out.println("O animal faz um som.");
}
}
class Cachorro extends Animal {
public void fazerSom() {
System.out.println("O cachorro late.");
}
}
class Gato extends Animal {
public void fazerSom() {
System.out.println("O gato mia.");
}
}
public class ExemploPolimorfismo {
public static void main(String[] args) {
Animal animal1 = new Cachorro();
Animal animal2 = new Gato();
animal1.fazerSom(); // Resultado: "O cachorro late."
animal2.fazerSom(); // Resultado: "O gato mia."
}
}
Também se fala em tipos opacos e transparentes. Em tipos opacos, a implementação concreta é escondida, expondo-se apenas a interface relevante. Em tipos transparentes, o nome declarado funciona essencialmente como um alias de outro tipo.
A checagem de tipos consiste em verificar se as expressões e operações de um programa respeitam as regras do sistema de tipos da linguagem. Por exemplo, tentar usar um inteiro como se fosse uma função caracteriza um erro de tipo.
Essas verificações podem ocorrer em tempo de compilação, em tempo de execução ou em ambos. Linguagens estaticamente tipadas tendem a detectar vários problemas antes da execução; linguagens dinamicamente tipadas deixam maior parte da verificação para o momento em que o programa roda.
Erros de tipo estão ligados às regras da linguagem e ao modo como expressões são compostas, e não apenas ao comportamento físico da máquina subjacente.
Inferência de tipos é o processo de determinar automaticamente o tipo de expressões com base em regras da linguagem e em informações já conhecidas. Em várias linguagens modernas, isso permite reduzir anotações explícitas sem perder segurança estática.
Do ponto de vista formal, a inferência pode ser descrita por regras aplicadas sobre a árvore sintática do programa, propagando restrições de tipos até encontrar uma atribuição consistente ou detectar incompatibilidades.
Referências: