Linguagens e Ambientes de Programação (2016/2017)



Teórica 09 (04/abr/2017)

Tudo sobre a execução de programas. Plataformas computacionais.
Implementação de linguagens de programação: Compilação e Interpretação.
Técnicas de implementação mistas. Máquinas virtuais.
Níveis de interpretação.

Detalhes da implementação de interpretadores.
Detalhes da implementação de compiladores.

Ligação.
Carregamento.



Plataformas computacionais

É demasiado simplista dizer que os programas correm sobre hardware. É mais rigoroso dizer que os programas correm sobre uma plataforma computacional.

Uma plataforma é constituída pelos seguintes elementos:

Exemplos de plataformas:


Implementação de linguagens de programação: Compilação e Interpretação

A generalidade das linguagens de programação suporta conceitos e abstrações mais sofisticados do que os mecanismos suportados pelas plataformas computacionais usuais. Assim, para conseguir executar numa plataforma computacional programas escritos numa linguagem de alto nível é preciso recorrer a uma das duas seguintes técnicas, ou a uma mistura das duas:

Compilação

Um compilador é um programa tradutor com as seguintes características:

O seguinte diagrama descreve a situação:

                          --------------
       Programa fonte --> | Compilador | --> Programa objeto
                          --------------  
                          -------------------
                Input --> | Programa objeto | --> Resultados
                          -------------------	   
Alguns exemplos. Na plataforma Intel/Linux usada nas aulas práticas estão disponíveis os seguintes compiladores: Todos estes compiladores geram código nativo.

Interpretação

Um interpretador é um programa "executor" com as seguintes características:

O seguinte diagrama descreve a situação:

                                 -----------------
       Programa fonte, Input --> | Interpretador | --> Resultados
                                 -----------------	   
Alguns exemplos. Na plataforma usada nas aulas práticas está pelo menos disponível um interpretador:

Vantagens/Desvantagens

Vantagens de usar um compilador: Os ganhos de eficiência dos compiladores devem-se à seguinte razão: Vantagens de usar um interpretador:

Técnicas de implementação mistas

São bem claras as diferenças entre os conceitos de compilação e interpretação. Contudo a implementação de muitas linguagens de programação acaba por baseada numa mistura de compilação e de interpretação.

Vejamos três situações diferentes:

Coexistência de código compilado e de código interpretado

Algumas implementações da linguagem Prolog permitem a coexistência de código compilado com código interpretado.

Predicados declarados como estáticos (i.e. que não podem ser alterados em tempo de execução) são normalmente compilados; predicados declarados como dinâmicos (i.e. que podem ser modificados em tempo de execução) são obrigatoriamente interpretados.

A vantagem desta técnica é que permite obter velocidade de execução nas partes estáticas do programa, e a flexibilidade necessária nas partes dinamicamente modificáveis do programa.

Máquinas virtuais

Outra forma de implementação mista de linguagens de programação envolve a invenção duma linguagem intermédia para a qual se escreve um interpretador. O termo máquina virtual é muitas vezes usado, tanto para designar a linguagem intermédia, como o seu interpretador.

Agora basta escrever um compilador para traduzir programas da linguagem de alto nível para código intermédio. O resultado da tradução pode depois ser executado na máquina virtual.

O seguinte diagrama descreve a situação:

                                  --------------
               Programa fonte --> | Compilador | --> Programa intermédio
                                  --------------
                                  -------------------
   Programa intermédio, Input --> | Máquina virtual | --> Resultados
                                  -------------------	   
É muito importante que a máquina virtual seja criada com três objetivos em mente: Vantagens da técnica da máquina virtual: Eis alguns exemplos de implementações baseadas em máquinas virtuais:

Máquinas virtuais just-in-time

Quando é muito importante tornar a implementação duma máquina virtual tão rápida quanto possível, torna-se necessário implementar o respetivo interpretador usando a técnica just-in-time (JIT), também conhecida por tradução dinâmica.

A ideia da técnica é simples, embora a implementação seja complicada de fazer. Durante a execução do programa intermédio, este vai sendo dinamicamente traduzido em código-máquina que é imediatamente executado. A tradução dinâmica é aplicada a unidades a unidades de código, tais como métodos ou funções, e a implementação gere uma cache de unidades de código já processadas. Ao fim de algum tempo de execução, quando a maior parte do código já foi traduzido, consegue-se atingir uma velocidade de execução que ronda os 70% da velocidade de execução dum programa compilado nativamente. Alguns exemplos de máquinas virtuais para as quais existem versões JIT:


Ponto de vista externo e interno

As técnicas de implementação mistas, fazem esbater a fronteira entre as noções de compilação e de interpretação. Por vezes, para caracterizar a implementação duma linguagem com rigor, temos de considerar dois pontos de vista: Para discutir os dois pontos de vista, vamos considerar uma máquina virtual just-in-time, por exemplo a JVM: Consideremos agora o interpretador de OCaml ocaml, muito usado nas nossas aulas práticas. Consideremos agora a arquitetura de hardware Intel-32. Claramente um processador da Intel implementa uma linguagem que se chama linguagem máquina. Será que deve ser encarado como um compilador ou um interpretador.

Níveis de interpretação

Vejamos os três níveis de interpretação envolvidos na execução dum programa em Java sobre uma JVM implementada em hardware da Intel:
  1. Interpretador de microcódigo implementado dentro do processador físico.
  2. Interpretador de código-máquina - é o processador físico.
  3. Interpretador da JVM - implementado por software.
Podem existir níveis de interpretação ainda menos elevados: E podem existir níveis de interpretação ainda mais elevados:

Detalhes da implementação de interpretadores

Já sabemos que um interpretador é um programa que executa diretamente programas fonte.

Código interpretado é geralmente mais lento (por vezes, 10 vezes mais lento!) do que código compilado. Algumas razões:

Um aspeto importante da interpretação é a forma como o interpretador lida com o texto do programa fonte. Há varias técnicas que têm sido usadas historicamente.

Interpretação direta

Nos interpretadores mais rudimentares, o texto é carregado em memória e é usado diretamente como matéria prima para a execução dos programas.

Os primeiros interpretadores de Basic, em meados dos anos 60, foram feitos desta forma. O manual da linguagem recomendava que não se escrevessem muitos comentários para os programas correrem mais rapidamente. Com efeito, os mesmos comentários eram lidos (e ignorados) sempre que uma dada parte do programa era executada (por exemplo, num ciclo).

Também convinha escolher variáveis com nomes curtos, para acelerar a execução dos programas.

Preprocessamento com identificação de tokens

A maioria dos interpretadores faz algum processamento do ficheiro fonte no momento do carregamento. Tipicamente, os comentários e espaços em branco são removidos, e todas as sequências de caracteres significativas são agrupadas em tokens, ou seja em símbolos que representam palavras reservadas, números, nomes de variáveis, etc.

Durante a interpretação, a matéria prima para a execução dos programas já não são sequências de caracteres, mas sim sequências de tokens. Consegue-se assim obter maior eficiência

O Basic do ZX Spectrum

Uma variante curiosa desta técnica foi usada na implementação do Basic do ZX Spectrum. O ZX Spectrum foi um computador pessoal muito popular na Europa durante os anos 80. Os programas podiam ser carregados a partir duma cassete áudio ou ser metidos à mão. Quando os programas eram metidos à mão, o editor de texto obrigava o utilizador a introduzir as palavras reservadas como tokens, o que era possível devido ao curioso teclado.

Preprocessamento com identificação de árvore sintática

Muitos interpretadores modernos efetuam um processamento bastante sofisticado do ficheiro fonte, no momento do carregamento. Além de identificarem todos os tokens, também identificam a estrutura sintática do programa de entrada e constroem em memória a correspondente árvore sintática (parse tree).

Durante a interpretação, a matéria prima para a execução dos programas é a árvore sintática. Consegue-se assim obter ainda maior eficiência.

Interpretador ou compilador?

Note que a identificação dos tokens e a construção da árvore sintática correspondem às duas primeiras fases de processamento dos compiladores tradicionais. Realmente, para aumentar a eficiência dum interpretador é preciso integrar nele alguma funcionalidade típica dos compiladores. Prosseguindo nesta linha de integrar mais e mais funcionalidade dos compiladores num interpretador, em breve se chega à técnica mista das máquinas virtuais, estudada da aula anterior. Do ponto de vista interno, já deixámos de ter um interpretador, e passámos a ter um sistema misto constituído por um compilador que gera código intermédio e um interpretador duma máquina virtual.


Detalhes da implementação de compiladores

Num compilador típico, a compilação evolui ao longo duma série de fases. Cada fase descobre informação que é necessária nas fases seguintes, ou então transforma o programa numa forma que é requerida pela fase seguinte.
  1. Leitura de caracteres do ficheiro fonte

  2. Análise lexical (scanner)

  3. Análise sintática (parser)

  4. Análise semântica

  5. Melhoramento e completação da árvore Abstract

  6. Geração de código intermédio

  7. Otimização de código intermédio

  8. Geração de código máquina


Ligação

Para simplificar as discussões anteriores relativas a compiladores, temos vindo a omitir qualquer referência à questão da ligação de ficheiros objeto. Vamos tratar agora dessa questão que não pode ser ignorada quando se discute o tema da implementação de linguagens de programação.

Código fonte e código objeto

Um programa é muitas vezes constituído por diversos ficheiros fonte, sendo o conjunto habitualmente designado por código fonte do programa. Exemplos:

Quando o compilador processa o código fonte dum programa, o compilador gera um ficheiro objeto distinto por cada ficheiro fonte. Exemplos: O conjunto dos ficheiros objeto chama-se código objeto.

Ligador

Depois de compilado o código fonte, para se obter o programa executável é preciso usar um programa ligador que junta os diversos ficheiros objeto num único programa executável. Na altura de ligar um programa é preciso também indicar quais são as bibliotecas (arquivos de ficheiros objetos predefinidos) que interessa juntar ao programa.

Em Linux, o ligador chama-se ld e pode ser invocado diretamente pelo utilizador, se tal for desejado. Mas geralmente é mais prático invocar indiretamente o ligador através do comando de compilação. Em todo o caso, veja o que diz o início do manual do comando ld:

No Linux usa-se a opção "-o" na linha de comando dos compiladores serve para invocar indiretamente o ligador como último passo da compilação. Exemplos:

Outra missão do ligador é resolver as referências cruzadas de nomes globais que podem ocorrem nos diversos ficheiros object. Para perceber o que está em causa vamos observar a tabela de símbolos e informação de relocação que é guardada dentro do ficheiro object correspondente ao seguinte ficheiro fonte "a.c": O comando nm do Linux mostra os símbolos e informação de relocação de ficheiros-objeto individuais. Aplicando nm ao ficheiro object "a.o", obtém-se o seguinte:

Carregamento

O carregador é a componente do núcleo do sistema operativo que trata de carregar em memória os programas para depois os executar.

No Linux, execve é o nome da chamada ao sistema que permite usar o carregador. Leia o que diz o início do manual do comando execve:

Em algumas plataformas, e.g. System/360 da IBM, o carregador tem a tarefa de efetuar relocação de endereços, porque o hardware só suporta endereçamento absoluto.

Nas plataformas modernas está geralmente disponível um segundo carregador - um carregador dinâmico - que permite carregar bibliotecas dinâmicas a meio da execução dum programa. Em Windows as bibliotecas dinâmicas são guardadas em ficheiros com extensão "dll". No Linux a extensão das bibliotecas dinâmicas é "so".



#120