LP 26/09/2011

   # # # # # # # # # # # # # #
  # Linguagens de Programação #
  # Prof. Fernando Pereira    #
  # notasdogarcia.blog.com    #
   # # # # # # # # # # # # # #

		Hoje estamos falando sobre a compilação de linguagens funcionais

Começamos falando sobre onde ficam armazenadas as "variáveis" de SML.

Como o programa é imediatamente executado essas variáveis ficam armazenadas em Registrador ou em cache.

CONCEITO:
Hoje os hardwares usam o sistema Fon Noimann ou seja, armazenam os dados e o código do programa no mesmo sistema de memória.
Outros modelos utilizam dispositivos separados para armazenar os dados e o código.

// Notas:
Esse Fon Noimann foi na verdade um matemático. E quem realmente inventou esse sistema foram outras duas pessoas.
Ele trabalhava no projeto Manhattan.

Ele tem várias conquistas na vida dele, porém acabou ficando famoso por esse artigo que nem era realmente da autoria dele.
Um comentário era que ele era extremamente inteligente e rápido de pensamento, e todos os que o conheceram comentavam isso.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Como chama a area de memória onde ficam armazenadas as informações de uma função recém ativada?
É o registro de ativação da função.

O que se armazena nesse espaço?
  Endereço de retorno.
  Argumentos da função.
  E variáveis locais.
// PS: esse registro que acabo de descrever é o registro de ativação estático, ou seja é alocado em tempo de compilação.

Vantagens:
  Fácil compilação (é fácil implementar um compilador)

Desvantagens:
  Não se pode ter recursão.
  Não se pode ter multi-threading, pois duas threads rodando sobre o mesmo programa não poderiam chamar a mesma função ao mesmo tempo.
  pois as variáveis só seriam alocadas uma vez.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Qual o tempo de vida de uma função e de todo seu registro de ativação?
  É o tempo entre a chamada da função e seu retorno, e o mesmo vale para todas as suas variáveis, endereço de retorno e argumentos.

Existem variáveis locais que sobrevivem ao tempo de vida da função?
  Existem. Elas são as variáveis estáticas e existem em algumas linguagens de programação.
  Essas variáveis ficam alocadas em tempo de compilação juntamente com as variáveis globais.
  Porém só podem ser referenciadas de dentro do escopo da função.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

O conceito de alocação dinâmica surgiu com LISP e OLGOL

Com essa nova característica surge um novo dado nos registros de ativação das funções.

Agora o registro de ativação contém um ponteiro para o último registro de ativação e não apenas para a posição do código de onde ela partiu.
O motivo é que agora voce pode ter vários registros de ativação da mesma função. E assim voce armazenada cada registro em uma posição diferente.
E portanto a posição do código não é mais a única informação importante.

É possível uma mesma função apresentar registros de ativação de tamanhos diferentes?
  Sim.
  Ex:
    int foo (int n)
    {
      int a[n];
      a[0]=1;
      return a[0];
    }
  A variável a é um arranjo de n elementos e n vai ser diferente para cada chamada da função, por isso o tamanho do registro se torna variável.

O professor mandou agente pesquisar sobre o criador do merge sort (de novo eu acho)
  O criador é o Jhon Von Neumann acabei de pesquisar.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Uma ultima informação que fica contida no registro de ativação modernos é o registro de aninhamento.
  Para que serve ele? Para saber quem é a função mãe dele, da qual ele deverá buscar variáveis que ele não encontrar declaradas nele.

  Voces se lembram do exemplo da aula do dia 19/09/2011?

    val one = 1;

    fun inc x = x + one;

    fun foo x =
      let
        val one = 2;
      in
        inc x
      end

    foo 5;

  O que garante que o resultado dessa chamada "foo 5" será igual a 6 e não 7 é o registro de aninhamento.
  Ou seja é um registro de onde a função foi declarada, e pode ser recursivo já que ele apontará para um outro registro de ativação.

  Agora vem a pergunta porque ele aponta para outro registro de ativação de a variável do exemplo tem um valor fixo?
  Porque nada garante que esse valor seja fixo né, eu posso colocar uma expressão para definir o valor de one.

  Assim a função vai buscando na função mãe a variável buscada, se não encontrar ele segue o registro de aninhamento da mãe e assim por diante.

  Note então que a complexidade disso é linear no nível de aninhamento e não no nível de chamadas.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

CONCEITO:
  Variáveis livres são variáveis que são declaradas fora da função.
  Assim uma variável pode ser declarada em uma função mãe, e referenciada por uma função filha.

  Note que é esse o caso da variável one no exemplo acima da função "foo"

  E isso que faz ela livre, o valor dela é livre de qualquer parâmetro da função em sí e dependente apenas da função mãe.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Reflexão sobre funções de Alta Ordem (funções que retornam funções):

  - Agora sobre aquela história de retornar uma função em sml?

  Será que quando voce tem uma função que "cria" outra função do tipo: int -> int -> int, por exemplo.
  ela re-escreve a função toda escrevendo àquela variável como constante em tempo de execução?

  Não na verdade isso seria ineficiente.
  Na prática é utilizado um sistema de closure, que é mais eficiente.
  O closure é um par de ponteiro para função mais um ponteiro para lista de ativação de variáveis livres.
  Assim a função que é "criada" na verdade já existia, e ela precisa apenas de acessar a variável local definda na função mãe por assim dizer.
  Essa lista é criada juntamente com a chamada da função (em tempo de execução).
  E só é desalocada (em SML) quando o coletor de lixo decidir que é o momento.

  Interessante?

// Bem é o fim da aula =].