Linguagens e Ambientes de Programação (2022/2023)



Teórica 14 (26/abr/2023)

Execução de programas.
Modelos de execução para diversos tipos de linguagens de programação.
Modelo de execução detalhado para linguagens com escopo estático e aninhamento de funções.



Modelo de execução para diversos tipos de linguagens de programação

Na implementação da maioria das linguagens de programação, é necessário considerar diversos aspetos para garantir que os efeitos da execução dos programas são os desejados. Algumas das questões mais importantes a considerar são as seguintes:
  1. Avaliação de expressões
  2. Acesso a variáveis
  3. Chamada e retorno de funções
  4. Passagem de funções como argumento
  5. Funções retornadas por outras funções
Vamos estudar em sucessão estas questões com a ajuda dum modelo de execução. Um modelo de execução descreve um conjunto de mecanismos abstratos que permitem a execução de programas. De notar que o objetivo de qualquer modelo é simplificar o estudo uma realidade, omitindo deliberadamente pormenores não essenciais, evitando complicações desnecessárias. Por exemplo, no nosso modelo, resolvemos assumir a existência duma pilha de execução e usamos essa pilha para exprimir o máximo de funcionalidades, incluindo a avaliação de expressões.

Um modelo de execução pode ser expresso de várias maneiras, por exemplo usando técnicas de semântica operacional ou da programação duma máquina virtual. O estilo que nós usamos é o da descrição informal duma máquina virtual.

1. Avaliação de expressões

No nosso modelo, usamos uma pilha para avaliar expressões. Para cada operação a executar, primeiro os seus argumentos são empilhados (pela ordem em que aparecem escritos) e depois a operação é efetuada. A operação retira os argumentos do topo da pilha, calcula o resultado e deixa esse resultado no topo da pilha.

Por exemplo, para avaliar a expressão 1+2 seguindo as regras atrás descritas, o código gerado pelo compilador seria algo do género:

Não há mais nada a dizer sobre este assunto.

2. Acesso a variáveis

1 - Numa linguagem sem recursividade nem aninhamento de funções, como é o caso do Fortran 77, cada procedimento é dono duma zona de memória própria onde as suas variáveis locais são guardadas. Todas as variáveis são estáticas, ou seja têm localizações de memória fixas. Diversas chamadas do mesmo procedimento reutilizam a mesma zona de memória... não há problema nisto porque, como foi dito, a recursividade não é permitida.

2 - Numa linguagem com recursividade mas sem aninhamento de funções, como é o caso do C, há dois casos a considerar. As variáveis globais, ou seja as variáveis declaradas fora das funções, são consideradas variáveis estáticas e têm localizações de memória fixas. Já as variáveis locais são criadas dinamicamente no topo duma pilha sempre que a sua função-dona é ativada; são removidas do topo da pilha quando a execução da função-dona termina. Simplificando um pouco, a partir do interior duma função em C, as variáveis acessíveis são as seguintes: as variáveis locais dessa função e as variáveis globais que não tenham sido redefinidas dentro da função. Mais nenhumas variáveis são acessíveis de forma direta.

3 - Numa linguagem com recursividade e com aninhamento de funções, como são os casos do Pascal, do OCaml e do GCC (uma variante do C enriquecida), a implementação fica mais complicada porque pretendemos usar a semântica do escopo estático. Agora surgem variáveis declaradas nas funções envolventes, as chamadas variáveis intermédias. Para aceder às variáveis intermédias é preciso guardar na ativação de cada função o respetivo ambiente de definição (que é a função envolvente) representado por um apontador (static link) para a ativação mais recente da função envolvente na pilha. Para aceder a uma variável intermédia é preciso percorrer parte duma lista ligada constituída por static links. Foi Dijkstra quem, em 1960, inventou a técnica dos static links. [Numa linguagem com escopo dinâmico, não é necessário usar static links, pelo que a implementação fica mais simples.]

Para perceber melhor a estrutura dum programa, pode valer a pena desenhar a chamada árvore do programa, que mostra como as várias funções se relacionam. A imagem à direita corresponde ao programa que vai aparecer já a seguir. Uma árvore de programa tem sempre na raiz uma função imaginária chamada start, que contém todo o programa, incluindo as variáveis globais. Por influência desta árvore, muitas vezes usam-se as relações familiares humanas para referenciar as funções. Diz-se, por exemplo, que a função g é irmã de h, filha de f, sobrinha de main e neta de start.

Considere o exemplo abaixo, em GCC, com aninhamento de funções. Neste programa encontram-se muitos exemplos de variáveis intermédias. Por exemplo, do ponto de vista do interior da função h, as variáveis locais da função f que forem acessíveis são consideradas variáveis intermédias. Vamos ser mais completos: do ponto de vista do interior da função h, esta tem acesso a uma variável local chamada i, a uma variável intermédia j na função-mãe e duas variáveis globais k e l na função avó. Em tempo de execução, para a função aceder por exemplo à variável global k da avó, precisa de dar dois saltos na lista de static links para alcançar o registo de ativação que contém a variável pretendida. É um pouco complicado e este exemplo mostra um dos preços a pagar por se usar escopo estático.

Nota importante: GCC é um nome duma linguagem um pouco mais vasta do que o C de base. Ao contrário do ANSI-C, o GCC suporta aninhamento de funções.

3. Chamada e retorno de funções

Nas linguagem que suportam recursividade, o estado da invocação duma função é capturado numa estrutura chamada registo de ativação (frame). Num registo de ativação guarda-se a seguinte informação: os argumentos e as variáveis locais da função, o endereço de retorno da função, e um apontador para o registo de ativação da função que fez a chamada (dynamic link).

Se a linguagem também permitir aninhamento de funções e se pretendermos usar escopo estático, ainda é preciso guardar no registo de ativação o ambiente de definição da função ou seja um apontador para o registo de ativação mais recente da função envolvente (static link). Repare que a função envolvente pode não ser a mesma função que fez a chamada.

Os registos de ativação organizam-se de forma natural numa pilha, a chamada pilha de execução. A chamada duma função causa o empilhamento dum novo registo de ativação; o retorno duma função causa o desempilhar do registo de ativação mais recente.

Existem dois apontadores muito importantes que apontam para a pilha de execução:

Eis o nosso formato para os registos de ativação:

4. Passagem de funções como argumento - closures

No caso duma linguagem sem aninhamento de funções, como o C, a passagem duma função como argumento é trivial: basta passar o endereço da função.

No caso duma linguagem com aninhamento de funções e com escopo estático, a passagem duma função como argumento é mais complicada. A função passada pode ter necessidade de aceder a variáveis intermédias, e por isso, juntamente com o endereço da função tem também de ser passado o respetivo ambiente de definição (static link).

Portanto a implementação da passagem duma função como argumento envolve tecnicamente a passagem dum par ordenado a que se chama closure (ou fecho em Português):

A razão de ser do nome closure é a seguinte: Em geral, uma função é uma entidade "aberta" (incompleta) pois o seu corpo pode referir entidades desconhecidas localmente. Mas o par função + respetivo ambiente de definição já é uma entidade fechada pois o ambiente de definição "fecha" (completa) o significado da função.

No seguinte exemplo, em GCC, ocorre uma passagem de função como argumento. Medite no código para confirmar a necessidade das closures.

5. Funções retornadas por outras funções

No caso duma linguagem sem aninhamento de funções, como o C, implementar o retorno duma função a partir de outra função é trivial: basta retornar o endereço da função-resultado.

No caso duma linguagem com aninhamento de funções e com escopo estático, como o OCaml, a implementação desse mecanismo é mais complicada. Quando se retorna uma função, o que tecnicamente precisa de ser retornado é uma closure.

Mas aqui pode haver problema. A closure retornada pode depender de entidades locais à função que produz o resultado. Assim quando a função retorna a closure e termina, o seu registo de ativação não pode ser destruído. Uma solução é transferir o registo de ativação para o heap, ou seja para a zona das variáveis dinâmicas. Esta é a solução adotada na linguagem funcional Lua. Outra solução, mais radical, consiste em abandonar completamente o modelo da pilha de execução e passar a criar todos os registos de ativação no heap (deixando que seja o gestor de memória a descobrir o momento em que eles podem ser removidos com segurança).

Esta complicação explica o facto do retorno de funções ser um mecanismo não suportado pela maioria das linguagens de programação. Praticamente só as linguagens funcionais é que suportam este mecanismo.

No seguinte exemplo, em OCaml, a função f retorna uma closure que depende do x local ao f. Quando a closure retornada é depois chamada, o x tem de continuar disponível, apesar da execução de f já ter terminado.



Modelo de execução detalhado para linguagem com escopo estático e aninhamento de funções

Esta secção é de leitura opcional, e poderá ser útil para tirar algumas dúvidas sobre o comportamente exato de algum mecanismo.

As explicações da secção anterior já são suficientes para se perceber como funciona a pilha de execução numa linguagem com recursividade, aninhamento de funções e escopo estático. Inclusivamente, são suficientes para conseguirmos fazer uma execução manual dum programa, desenhando a pilha de execução usando papel e lápis.

Mas se pretendermos automatizar a execução dum programa, precisamos de introduzir mais detalhe e mais um ou dois conceitos novos. Esta nova secção lida com o problema de automatizar a execução dum programa. Apresenta uma implementação parcial em C dos mecanismos de execução estudados. O código C terá grandes semelhanças com o código duma máquina virtual típica.

A grande diferença entre uma execução manual e uma execução automática concretiza-se no tratamento dos acessos a entidades. Numa execução manual não temos problema em perceber qual é a entidade referida referida por um nome - basta procurar no texto do programa (tendo em conta a regra de escopo estático) e também podemos olhar para a árvore do programa.

Mas numa execução automática, já não é prático trabalhar com o texto do programa. Contém usar valores numéricos que capturem os aspetos desses entidades que são relevantes para a execução - por exemplo no caso duma variável, precisamos de dois valores numéricos: (1) o offset da variável dentro do seu registo de ativação; (2) a diferença de nível na árvore do programa entre o ponto do uso e o ponto da definição.

Áreas de memória e registos

O nosso modelo tem três áreas de memória: Pouco será dito sobre a zona de código e sobre o heap. O stack vai receber quase toda a nossa atenção.

Os registos do modelo são os seguintes:

Eis uma concretização em C destas ideias:

Avaliação de expressões

Como já foi dito, usamos a pilha de execução como auxiliar da avaliação de expressões. Os argumentos das operações são empilhados e depois a operação encontra os seus argumentos no topo da pilha.

Eis uma concretização em C destas ideias:

Acesso a variáveis

Em tempo de execução os nomes das funções não estão disponíveis. Para referenciar uma variável em tempo de execução basta usar as chamadas coordenadas da variável, constituídas por dois valores:

A diferença de nível representa o número de static links que é preciso seguir para se atingir o registo de ativação onde se encontra a variável pretendida. No caso do acesso a uma variável local, a diferença de nível é zero.

O compilador da linguagem consegue determinar com muita facilidade as coordenadas que permitem referenciar cada variável. Um ser humano também o faz facilmente. Por exemplo, no primeiro exemplo desta aula, qual é a diferença de nível das utilizações das variáveis i, j, k e l dentro da função f?

Numa execução, numa atribuição, primeiro determina-se o valor da expressão da direita (o valor é empilhado), depois determina-se o endereço representado pela expressão da esquerda (o endereço também é empilhado), e no final guarda-se o valor calculado na posição de memória indicada pelo endereço (os dois elementos empilhados são desempilhados).

Concretização em C:

Chamada e retorno de funções

No nosso modelo, o formato dum registo de ativação é o que se apresenta abaixo. Convenciona-se que a posição do DL é o ponto de referência oficial de qualquer registo de ativação. Quem aponta para um registo de ativação aponta sempre para o respetivo DL.

O registo FP aponta para a célula onde é guardado o dynamic link do registo de ativação mais recente. Nos acessos aos argumentos e variáveis da função, usa-se o registo FP como ponto de referência. Assim, os argumentos da função têm offset negativo, a começar em -1, e as variáveis locais têm offset positivo, a começar em 3. No diagrama assume-se que a pilha cresce para cima.

A principal complicação envolvida na ativação duma função e na criação do seu registo de ativação é o cálculo do static link (que representa o ambiente de definição dessa função). O static link tem de ser guardado no registo de ativação da função para permitir o subsequente acesso a variáveis não-locais. Para determinar o static link é preciso conhecer a diferença de nível (nesting) entre o ponto da declaração da função e o ponto da sua chamada. A diferença de nível representa o número de static links para é necessário percorrer para se atingir o registo de ativação onde se encontra o static link a copiar. Numa chamada recursiva, a diferença de nível é zero. Na chamada duma função filha, a diferença de nível é -1.

No nosso modelo a chamada e retorno de funções estão organizados da seguinte forma:

Concretização em C:

Passagem de funções como argumento - closures

Já sabemos que a passagem duma função como argumento requer efetivamente a passagem duma closure como argumento. A principal complicação envolvida na criação da closure é o calculo do static link. Mas agora não há qualquer novidade: ele calcula-se exatamente da mesma forma que na chamada duma função normal.

A ativação duma função através duma closure é mais simples do que a ativação direta duma função pois o static link já se encontra calculado na closure.

Concretização em C:

Funções retornadas por outras funções

O estudo mais detalhado desta questão é um tópico avançado que está fora do âmbito da cadeira de LAP. Nesta parte de LAP, trabalhamos apenas com programas em que não ocorre retorno de funções.



Exercícios

  • Relativamente ao primeiro exemplo desta aula, mostre o estado da pilha de execução à entrada da função h.
  • Relativamente ao segundo exemplo desta aula, mostre o estado da pilha de execução à entrada da função h. (Será feito numa aula prática.)

    Para efeitos da criação do registo de ativação inicial, convém imaginar que cada programa em C está embebido numa função chamada start, sem argumentos. É importante tratar todas as entidades globais do programa como sendo locais à função imaginária start.

    Assuma também que a primeira célula da pilha de execução é identificada como posição 0, a segunda célula da pilha de execução é identificada como posição 1, etc.



    Vídeos antigos

    Estes vídeos poderão estar um pouco desatualizados, pois foram feitos no contexto duma edição anterior do LAP. Contudo, partes dos vídeos poderão continuar a ter alguma utilidade. ERRATA:

    1. Mesmo quase no final do vídeo, o valor de l devia ser 6 (3+2+1) e não 8, claro.


    #--- 40 50