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



Teórica 15 (26/abr/2018)

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: Vamos estudar em sucessão estas questões com a ajuda dum modelo de execução. Note que o objetivo de qualquer modelo é simplificar o estudo uma realidade, omitindo deliberadamente pormenores não essenciais e outras complicações. Por exemplo, o nosso modelo não usa registos do CPU para avaliar expressões, apesar das implementações mais eficientes tipicamente os usarem.

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 é ativada. A operação retira os argumentos do topo da pilha, calcula o resultado e deixa-o no topo da pilha.

Acesso a variáveis

1 - Numa linguagem sem recursividade nem aninhamento de funções ou procedimentos, 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 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-mãe é ativada; são removidas do topo da pilha quando a execução da função-mãe termina. A partir do interior duma função em C, as variáveis acessíveis são as seguintes: as variáveis locais da ativação mais recente dessa função e as variáveis globais que não tenham sido redefinidas dentro da função.

3 - Numa linguagem com recursividade e com aninhamento de funções, como são os casos do Pascal, do OCaml e do GCC, a implementação fica mais complicada porque 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 ou seja um apontador para a ativação mais recente da função envolvente (static link). 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.]

Considere o seguinte exemplo, em GCC, que usa variáveis intermédias. Do ponto de vista do interior da função h, as duas variáveis locais da função f são consideradas variáveis intermédias.

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.

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, 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.

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, 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.

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

Para concretizar melhor as ideias anteriores, vamos desenvolver um modelo de execução ainda mais detalhado para o caso das linguagens com escopo estático e aninhamento de funções.

Usaremos a linguagem C como veículo de formalização, para concretizar melhor as ideias. O código C que vai aparecer tem grandes semelhanças com o código duma máquina virtual típica.

Á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 precisam de estar 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 atribuição, primeiro determina-se o valor da expressão da direita, depois determina-se o endereço representado pela expressão da esquerda, e no final guarda-se o valor calculado na posição de memória indicada pelo endereço.

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 calculo 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.

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.

    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.



    #100