“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

12 - Linguagens de Programação

12.1 - Conceitos.

Linguagens de programação são sistemas de símbolos e regras utilizadas para gerar instruções a um computador. Podem ser encaradas como soluções para problemas de armazenamento, protocolos de comunicação ou controles de interface. Cada linguagem tem suas próprias características: sintaxe, comportamento para uma determinada regra, bibliotecas úteis e expressões que o programador pode utilizar. Esses são os principais atributos que são importantes na escolha de uma linguagem. No caso do estudo de linguagens, a sintaxe é o tópico de maior relevância.

O comportamento de uma linguagem de programação é chamado de semântica, ou seja, aquilo que é associado à sintaxe. O problema que surge então é: Como modelar significado? Podemos utilizar a lógica matemática para isso, mas teríamos que lidar com muita complexidade. Criamos então um interpretador de significado, qual recebe uma entrada, executa uma análise e entrega um resultado. Sempre que precisamos avaliar uma linguagem, rodamos o interpretador e avaliamos o resultado. Interpretadores podem ser convertidos em compiladores, que são programas que geram programas.

Um programa que converte sintaxe (sintaxe concreta) em variáveis de um tipo específico (sintaxe abstrata) é chamado de parser. Em determinadas operações, a notação pode ser muito diferente de linguagem para linguagem. Por exemplo, somar dois números pode ser escrito de diversas maneiras:

  1. (3+4): infix
  2. (3 4)+: postfix
  3. +(3 4) : parenthesized prefix

Ao escrever um código em um ambiente de desenvolvimento integrado (IDE) o que vemos tem pouco a ver com as primeiras passagens de um parser. Quando especificamos, por exemplo, uma classe, não precisamos adicionar parênteses para delimitar o começo e o final de um bloco de código, isso é feito pela estruturas intermediárias da linguagem ou da plataforma em uso. A chamada S-expression, é um tipo de organização que adiciona essas marcações no código, par de parenteses no começo e no final, visando facilitar o trabalho de tokenização, leitura e conversão.

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:

  1. Tokenizador : Análise léxica. Deve separar o código tem tokens reconhecíveis, com tipo e valor. Não há validação que a sintaxe está correta.
    {ID: print}
    {STRING: “Hello”}
  2. Conversor (Parser): Faz a análise sintática;
  3. AST (Abstract Syntax Tree): Monta árvore com base na expressão passada. Pode ser passado então para o gerado de código ou compilador.

Uma primeira tentativa de resolver esse problema de conversão é através de expressões regulares, mas há muita complexidade envolvida, sendo que são úteis nos passos 1 e 2.

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
                    }
                }
            }
        

Recursivamente podemos ver que expressões complexas podem ter outras dentro, descrevendo qualquer expressão válida da linguagem.

Os conversores mais poderosos atualmente são os “recursive-descent parsers”.

12.2 - Paradigmas de Linguagens de Programação.

Paradigmas neste contexto são métodos de solução de um problema ou tarefa. Ao escolhermos uma determinada linguagem de programação, com ela vem também a escolha da criadora (ou criadores(as)) a respeito de qual modelo ou conceito é utilizado para chamar uma subrotina ou função. Esses elementos podem ser chamados a qualquer momento, com fins de reutilizar código, facilitar a manutenção e testes.

Podemos dividir os paradigmas em dois grandes grupos: programação imperativa ou declarativa. No primeiro caso, temos uma relação direta com a arquitetura da máquina e o programa vai evoluindo por mudanças nos estados (variáveis em determinado tempo t) através de declarações (statements). É muito simples de implementar, mas problemas complexos podem ser muito difíceis de resolver, acaba sendo menos produtiva e eficiente. É subdividida em: Procedural, Orientada à objetos e de processamento paralelo.

No caso de programação procedural, a função pode ser chamada por qualquer parte do programa, desde que suas dependências tenham sido carregadas corretamente. São exemplos desse paradigma: FORTRAN, ALGOL, COBOL, BASIC, Pascal e C. Não há maneiras simples de esconder a complexidade do código, especificar níveis de visibilidade, herança e abstrações mais sofisticadas, porém, os programas tendem a ser muito mais simples e diretos.

Porém, isso não acontece, por exemplo, com linguagens orientadas à objetos. Seu conceito é de modelar os problemas a partir de objetos reais que tem relações com outros, que contém atributos e funções protegidas por um escopo bem definido chamadas de métodos. São exemplos: Java, C++, Python, PHP, Javascript, C#, etc… A estrutura mínima deixa de ser uma função e vira a classe. É possível definir a visibilidade de certos trechos de código, implementar abstrações, interfaces e herança, reutilizar código de maneira mais complexa, mas o programa pode rapidamente ficar confuso e cada vez mais difícil de ser modificado.

As linguagens que implementam paralelismo, como por exemplo, C#, com base em alguma biblioteca já desenvolvida, tem a capacidade de dividir o processamento de uma tarefa em um ou mais processadores, acelerando a conclusão de um objetivo. Isso traz certos problemas de coordenação no acesso à memória e também na combinação de resultados de diferentes processos (threads). Há diversos algoritmos voltados para a construção, manutenção e execução de algoritmos paralelos, resolvendo problemas bem definidos de acesso a recursos críticos.

O caso declarativo, por outro lado, é dividido em lógica, funcional e de base de dados. Este tipo tem como característica a expressão da lógica de ser computador ao invés de lidar com um fluxo de controle. Pode simplificar a escrita de certos programa paralelos e o foco está o que precisa ser feito e não como será feito.

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 também tem suas raízes na matemática e em uma linguagem independente, onde o papel chave é a execução de uma série de funções matemáticas, onde o modelo central é a função e não a estrutura de dados, não há uma relação forte entre a subrotina e os dados, a função esconde sua implementação e seus valores podem ser sobrescritos sem causar um problema no programa. Não há laços nesse paradigma, iteração é feita via recursão. Uma vez definidas as variáveis, elas não são mais modificadas. São exemplos: Haskell, Scala, Erlang, Lisp, ML.

No modelo de base de dados, o foco está no dados em movimento. As declarações do programa são definidas pelos dados e menos em um passo a passo de como resolver um problema. SQL é a linguagem mais conhecida nesse paradigma.

12.3 - Semântica Formal.

Para poder escrever programas através de linguagens de programação precisamos ser capazes de descrevê-las formalmente, ou seja, utilizando matemática. Começamos definindo que uma linguagem de programação aceita um conjunto finito de símbolos, denominado alfabeto. Uma linguagem seria então qualquer subconjunto de palavras formadas com símbolos desse alfabeto, neste caso, uma palavra é chamada de string, ou uma sequência de carácteres do alfabeto.

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 strings de uma linguagem utilizamos expressões regulares, que é um tipo de notação para definir de forma precisa os elementos que desejamos avaliar. Uma expressão regular $r$ tem os seguintes caracteres especiais que atuam no alfabeto:

  1. “or” ou |, para avaliação lógica;
  2. símbolo de agrupamento ( ), para restringir valores;
  3. * e +, para determinar quantidade.

Exemplos: abcd, (defg)+, vermelho | verde | azul, etc…

Expressões regulares tem limitações, por isso, dado um determinado alfabeto A, quando queremos validar que uma string faz parte de A, podemos primeiro separar seus termos em tokens, que são strings não vazias compostas de símbolos do alfabeto. Qualquer conjunto de tokens é uma linguagem. Devemos definir como os símbolos e os token podem ser organizados para gerar sequências válidas na linguagem. Isso é chamado de sintaxe da linguagem.

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 infintas combinações desses tokens com essas regras:

            L =  {
            or (false, and (true, false)),
            and (true, false),
            not (false),
            …
            }
        

Se um conjunto de strings é válido para a sintaxe definida, o chamamos de sintaxe concreta. Um elemento desse conjunto é chamado de instância de sintaxe concreta. A sintaxe abstrata é o conjunto de todas as instâncias de estruturas de dados correspondentes a uma string em conformidade com as regras daquela linguagem. Sua instância é chamada de árvore de conversão (parse tree). Na primeira seção exibimos um exemplo de uma AST (abstract sintax tree).

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.

Se em um determinado BNF, em cada produção na gramática uma escolha começa com um terminal único, dizemos que a gramática é do tipo LL(1) (monta a árvore decompondo a sequência de tokens da esquerda para direita) e pode ser implementada utilizando um algoritmo chamado “predictive recursive descent” para o parse. Outro algoritmo útil para montar a árvore é chamado de “backtracking recursive descent” e é utilizado quando não forma de determinar unicamente uma escolha de uma determinada produção, dado o BNF.

Podemos definir com rigor como uma estrutura abstrata de sintaxe representa programas e isso é independente da linguagem escolhida e plataforma de execução. Devemos associar significado ao conjunto de objetos simbólicos, ou programas, ou seja, aplicar transformações para saber o que o programa quer dizer e aplicar regras para entender como executá-lo. Isso se faz através da semântica denotacional.

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 de uma sintaxe abstrata é o conjunto de regras que especificam como cada instância a de A pode ser transformada em um tipo de objeto que vai representar o resultado de uma computação descrita por A. É dividida em dois tipos: small-step semantics e big-step semantics. Essas regras especificam as restrições para que um algoritmo seja considerado válido. São implementadas através de regras de inferência, que é um tipo de notação usada para relacionar fatos matemáticos e fórmulas. Exemplo:

$[\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.

Se a semântica operacional não impuser qualquer restrição na ordem das operações de computação, chamamos o subconjunto de sintaxe abstrata de uma linguagem de computação de expressões. O resultado é dito “value”. Isso é possível pois as expressões normalmente não causam efeitos colaterais.

Um algoritmo que converte qualquer árvore de sintaxe abstrata (ASB) que representa uma expressão em uma ASB que representa valor é dito “evaluation algorithm”.

Caso exista ordem, chamamos o subconjunto de sintaxe abstrata de uma linguagem de programação de “statements” ou declarações. Isso normalmente está relacionado com a noção de ponto de controle enquanto o programa é executado. Linguagens que tem declarações e uma noção de controle são chamadas imperativas. Aquelas que utilizam expressões são chamadas de puras ou funcionais.

Um interpretador é um algoritmo que invoca algoritmos de avaliação e execução requiridos pela semântica operacional da linguagem.

12.4 - Teoria dos Tipos: Sistemas de Tipos, Polimorfismo.

Linguagens de programação podem organizar suas estruturas computacionais em tipos como forma de ajudar o programador a estabelecer seus construtos de forma prática. Um tipo é uma coleção de entidades computacionais que compartilham certas propriedades. Os tipos ajudam a organizar conceitos, definem como sequências de bits podem ser executadas de forma consistente e proveem informações ao compilador sobre como manipular um programa.

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.

Type safe: Se uma linguagem de programação tem essa característica então nenhum programa pode violar suas distinções de tipo.

Type cast: Permite converter de um tipo para outro.

Algumas linguagens podem verificar em tempo de compilação e/ou execução se houve alguma violação das regras de tipagem do sistema.

O polimorfismo é um dos princípios fundamentais da programação orientada a objetos (POO) e desempenha um papel crucial na criação de código flexível, reutilizável e extensível. O termo "polimorfismo" deriva do grego, significando "muitas formas". Na POO, o polimorfismo permite que objetos de diferentes classes sejam tratados de maneira uniforme, permitindo que um único código seja usado para manipular objetos de tipos diferentes.

Em termos simples, o polimorfismo permite que uma classe base seja estendida por classes derivadas que compartilham a mesma interface ou herança. Isso significa que as classes derivadas podem substituir ou estender o comportamento dos métodos da classe base, permitindo que diferentes objetos sejam tratados de forma polimórfica.

Existem três formas comuns de implementar o polimorfismo: polimorfismo de subtipo (herança), ad hoc e polimorfismo de parametrização (interfaces ou classes abstratas).

  • Paramétrico: Polimorfismo de parametrização (interfaces ou classes abstratas): Nesse tipo de polimorfismo, o polimorfismo é alcançado por meio de interfaces ou classes abstratas. As interfaces definem um conjunto de métodos que uma classe deve implementar, enquanto as classes abstratas podem fornecer implementações parciais de métodos e ser estendidas por outras classes. Os objetos são tratados de forma polimórfica por meio de referências da interface ou da classe abstrata, permitindo que diferentes classes implementem o mesmo conjunto de métodos.

    
        interface IForma {
            void Desenhar();
         }
         
         class Retangulo : IForma {
            public void Desenhar() {
               Console.WriteLine("Desenhando um retângulo.");
            }
         }
         
         class Circulo : IForma {
            public void Desenhar() {
               Console.WriteLine("Desenhando um círculo.");
            }
         }
         
         public class ExemploPolimorfismo {
            public static void Main(string[] args) {
               IForma forma1 = new Retang
         
    
  • Ad Hoc: É um tipo de sobrecarga, onde duas implementações com tipos diferentes têm o mesmo nome;

  • Subtipo (Subtype): Nesse tipo de polimorfismo, as classes derivadas herdam de uma classe base e podem substituir (sobrescrever) os métodos da classe base de acordo com seu comportamento específico. A chamada a um método pode ter um comportamento diferente dependendo do tipo do objeto em tempo de execução. Isso permite que diferentes objetos sejam tratados de maneira uniforme por meio de sua classe base, mas executem o comportamento específico de suas classes derivadas.

    
        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."
            }
         }
         
    

Há duas formas de declarar tipos: opaca e transparente. No primeiro caso, o tipo não é especificado por uma interface e as informações do tipo são escondidas. No segundo, o nome declarado é sinônimo de outro tipo.

12.5 - Verificação e Inferência de Tipos.

A checagem de tipo é uma forma de validar a consistência da entidade representada por ele, ou seja, um erro é gerado ao tentar utilizar um inteiro como uma função.

No nível do hardware, uma instrução de máquina vai resultar em erro se um tipo que não é função for chamado como função. Se x é um inteiro e tentarmos executar x(), teremos um erro de hardware. Se tentarmos somar um inteiro com um número de ponto flutuante teremos um problema de semântica, apesar de essa operação ser executada em alguns hardware.

Erros de tipo estão ligados à forma como a linguagem é definida e não como o programa é executado.

O processo de determinar o tipo de uma expressão com base em tipos conhecidos é chamada de inferência de tipo. Em alguns casos ela é muito parecida com a checagem de tipo em tempo de compilação. O algoritmo de checagem de tipo avaliar o programa para verificar se os tipos declarados estão de acordo com as definições. Ela suporta um tipo de recurso chamado polimorfismo.

O algoritmo de inferência de tipos pode ser visualizado através de uma árvore de conversão (parse tree) da expressão.