Exercícios de LP

Processamento de linguagens

1. Defina uma gramática não ambígua que corresponda às expressões lógicas em que os valores lógicos são representados por false e true e que podem conter os operadores de disjunção (||), de conjunção (&&) e de negação (not). Tenha em conta as prioridades relativas usuais destes operadores e que se pretende que as expressões sejam avaliadas da esquerda para a direita, onde aplicável.
2. Implemente em Prolog um predicado que permita calcular o valor das expressões lógicas descritas acima.
3. Acrescente parêntesis à linguagem dos exercícios anteriores.
4. Acrescente o operador de implicação (=>) à linguagem dos exercícios anteriores. Lembre-se de que o operador de implicação associa à direita.
5. Recorrendo às DCG's, implemente um predicado que construa a árvore de sintaxe abstracta das expressões lógicas.
6. Implemente um predicado que calcule o valor de uma expressão lógica a partir da sua árvore de sintaxe abstracta. A avaliação de uma expressão deve terminar assim que o seu valor for conhecido. (Por exemplo, se a expressão for e₁ && e₂ e se o valor de e₁ for false, o valor da expressão também é false, independentemente do valor de e₂, não sendo necessário avaliar este último operando.)
7. Defina em BNF uma gramática não ambígua que gere as expressões matemáticas com números naturais e as operações soma, subtracção, produto e divisão. Tenha em conta as prioridades e a associatividade usuais das operações matemáticas.
8. Implemente em Prolog um predicado que permita calcular o valor de expressões aritméticas com naturais e as operações de adição, subtracção, divisão e multiplicação.
9. Acrescente o operador de potenciação (^) à linguagem do exercício anterior. (Este operador associa à direita.)
10. Acrescente parêntesis à linguagem do exercício anterior.

• (exercício sem número 2)
  Recorrendo ao flex, ao bison e aos ficheiros fornecidos...
  1. Implemente uma calculadora que leia expressões aritméticas, de valor inteiro, inseridas através do teclado, e que escreva o seu valor no terminal. Uma expressão aritmética não pode ocupar mais do que uma linha e cada linha só pode conter uma expressão.
     As expressões aritméticas deverão poder conter números naturais e os operadores de adição e de subtracção.
  2. Acrescente os operadores de multiplicação e de divisão à linguagem reconhecida pela calculadora.
  3. Acrescente a possibilidade de incluir parêntesis nas expressões processadas.
  4. Acrescente o termo $ à linguagem das expressões. Este termo representará o valor da última expressão lida pela calculadora. (Por exemplo, se o valor da última expressão lida tiver sido 5, a expressão $ + $ * $ terá o valor 30, que será o valor representado por $ se ocorrer na expressão que vier a seguir.)
  5. Inclua variáveis na linguagem processada pela calculadora. O nome de uma variável consiste numa letra minúscula e a instrução <variável> = <expressão> servirá para atribuir um valor a uma variável.
     Quando a linha lida pela calculadora consistir numa instruções deste tipo, a calculadora deverá escrever o nome da variável, seguido de = e do valor atribuído à variável (que será, também, o valor de $, se ocorrer na expressão seguinte).

Cálculo-λ

11. Para cada um dos termos-λ abaixo
    1. [Mitchell, 4.3] (λx.λy.x y) (λx.x y)
    2. (λx.λy.y (y x)) y (λx.(λx.x) x)
    3. (λa.a a) (λa.λb.a b)
    1. Identifique as diferentes variáveis que nele ocorrem.
    2. Apresente um termo α-equivalente em que todas as variáveis tenham nomes distintos.
    3. Reduza-o até onde for possível.
12. Considere o programa em C:

        int f(int x) { return x * 2 + 1; }
    
        int main() { return f(f(1)); }
    

    1. Escreva um termo do cálculo-λ que o represente.
    2. Reduza o termo escrito na alínea anterior.
13. Considere o programa em Haskell:

      f x = x * x
      g x = f x + f x
      f 2 + g 2
    

    1. Escreva um termo do cálculo-λ que o represente.
    2. Reduza o termo escrito na alínea anterior.
14. Repita o exercício anterior para o programa:

      f x = x * x
      g x = f x + f x
      f (3 + g 2)
    

15. Considere o programa em Haskell:

      f x = x * x
      g x = f x + f x
      g (f 2)
    

    1. Escreva um termo do cálculo-λ que o represente.
    2. Reduza o termo escrito na alínea anterior escolhendo sempre o redex mais à esquerda.
    3. Reduza o termo escrito na primeira alínea escolhendo sempre o redex mais exterior mais à direita. (Um redex é mais exterior se está no âmbito de menos abstracções que outro. Por exemplo, no termo

       (λz.z) ((λx.(λy.y) x) w),

       os redexes (λz.z) ((λx.(λy.y) x) w) e (λx.(λy.y) x) w são mais exteriores que (λy.y) x, sendo (λx.(λy.y) x) w o mais à direita.)
16. Repita o exercício anterior para o programa:

      f y = y * y
      g x = f x
      f (g 5)
    

17. Considere o programa em Haskell:

      f x = x + x
      g f x = f x + 1
      h = g f
      h 3
    

    1. Escreva um termo do cálculo-λ que o represente.
    2. Reduza o termo escrito na alínea anterior.
18. Repita o exercício anterior para o programa:

      o f g x = f (g x)
      h x = x + 1
      o h h y
    

Semântica denotacional

19. Recorrendo à semântica denotacional, determine se os seguintes programas são formalmente equivalentes.

    1.   y := 2 * x + 2;
         z := x * 2;
         x := 2 * x + 1
       

    2.   x := 2 * x + 1;
         y := x + 1;
         z := x - 1
       

20. À linguagem dos programas while usada nas aulas teóricas, é acrescentada a instrução de atribuição (ou afectação) simultânea

    x₁, x₂ := e₁, e₂

    cujo efeito é atribuir, em "simultâneo", o valor da expressão e₁ à variável x₁ e o valor da expressão e₂ à variável x₂.

    Defina a semântica denotacional desta instrução e mostre que

    x, y := y, x

    troca os valores de x e de y.
21. Através da semântica denotacional, determine o que calcula o programa seguinte (em particular, qual o valor final de q).

      i := 0; q := 0;
      while i < n do ( q := q + 2 * i + 1; i := i + 1 )
    

    (Sugestões: (1) considere que n₀, o valor inicial de n, é tal que i assume os valores 0, 1, 2, ..., n₀-2, n₀-1, n₀, e expanda o cálculo da semântica denotacional em concordância (i.e., para os valores de i: 0, 1, 2, n₀-2, n₀-1 e n₀, substituindo o que acontece entre 2 e n₀-2 por "..." onde for conveniente); (2) mantenha o valor de q na forma 0 + 1 + 3 + ... (ou 1 + 3 + ...).)

• (exercício sem número 1)
  Considere o fragmento de programa while seguinte.

    if x = 0 then
      ( y := z ^ 2; x := 2 * y )
    else
      ( y := (z + x) ^ 2; z := z + x; x := x + 2 * y )
  

  1. Calcule sua a semântica denotacional.
  2. Proponha código mais simples, semanticamente equivalente ao apresentado, que o possa substituir.

Inferência de tipos

22. Aplique o algoritmo de inferência de tipos às definições e expressões que se seguem, onde os nomes livres se referem a definições de alíneas anteriores.

    Tenha em conta os tipos pré-definidos:

      0, 1, 2, ... : int
      +, -, * : int -> int -> int
      true, false : bool
      = : 'a -> 'a -> bool
      [] : 'a list
      hd : 'a list -> 'a
      tl : 'a list -> 'a list
      :: : 'a -> 'a list -> 'a list
    

    1. fun f1 x y = x + y;
    2. fun f2 x y = f1 x y;
    3. fun f3 x = f1 x;
    4. fun id x = x;
    5. fun apply (f, x) = f x;
    6. fun applyc f x = f x;
    7. id applyc;
    8. applyc id;
    9. apply (f1, 5);
    10. fun curry f x y = f (x, y);
    11. fun flip f a b = f b a;
    12. fun fact 0 = 1
          | fact n = n * fact (n - 1);
    13. fun fib n = fib (n - 1) + fib (n - 2);
    14. fun f4 (m, n) = f4 (m + n, m);
    15. fun f5 (h,x) = h (f5 (h, x - 1), x);
    16. fun f6 h x = h (f6 h (x - 1)) x;
    17. fun f7 g a = g (g a);
    18. fun e1 f = f (e1 0);
    19. fun e2 f = f f + 2;
    20. fun o f g x = f (g x);
    21. fun ou (f, g, x) = f (g x);
    22. fun pr (f, a, x) = f (x, pr (f, a, a x));
    23. fun len l = if l = [] then 0 else 1 + len (tl l);
    24. fun ape l m = if l = [] then m else ape (tl l) m;
    25. fun app l m = if l = [] then m else hd l :: app (tl l) m;
    26. fun rev [] = []
          | rev l = app (rev (tl l)) (hd l :: []);
23. Considere o código ML seguinte:

      fun f x y =
        let fun g x = 3 * x + y in
          g (x - 1)
        end;
    
      f 4 5;
    

    1. Traduza-o para cálculo-λ.
    2. Reduza o termo obtido na alínea anterior.
    3. Aplique o algoritmo de inferência de tipos à definição de f.

Registos de activação

24. Considere o fragmento de código C seguinte:

      {
        int a = 5, b = 2, c = 0;
    
        while (b > 0)
        {
          int a = 3;
    
          a = (a - b) * (a + b);
          c += a;
          --b;
        }
    
        {
          int d;
    
          {
            int a = 15, b;
    
            b = c + d + a;
          }
    
          d = b;
        }
    
        return c;
      }
    

    1. Identifique os vários blocos do código (nomeie-os A, B, ...).
    2. Em cada bloco, diga quais as variáveis locais e globais que nele ocorrem.
    3. Para cada variável global de cada bloco, calcule a distância (em número de blocos) entre o bloco onde ela está a ser usada e o bloco onde ela é declarada.
    4. Desenhe o registo de activação de cada bloco. (Assuma que a unidade de memória é a palavra e que cada inteiro e cada apontador ocupa uma palavra.)
    5. Estude a evolução da pilha de execução ao longo da execução do código apresentado.
25. [Mitchell, 7.8] Para o programa ML:

      1   let val x = 2 in
      2     let fun y = x + y in
      3	  let val x = 7 in
      4	    x +
      5             f x
      6       end
      7     end
      8   end;
    

    estude a evolução do conteúdo da pilha de execução durante a sua avaliação, e determine o valor das ocorrências de x (nas linhas 2, 4 e 5) e o valor final, quando
    1. a ligação dos nomes é estática (lexical/static scope).
    2. a ligação dos nomes é dinâmica (dynamic scope).

Passagem de argumentos

26. [Mitchell, 7.6] Considere o código seguinte, escrito numa notação à la Algol/Pascal:

      var x: integer;
    
      procedure p(y: integer)
      begin
        y := 1;
        x := 10
      end;
    
      x := 0;
      p(x);
    

    Traduza o código apresentado para ML, de modo a reflectir os modos de passagem de argumentos indicados, e calcule o valor final de x em cada um dos casos.
    1. Passagem de argumentos por valor.
    2. Passagem de argumentos por referência.
    3. Passagem de argumentos por valor-resultado.
       (O modo de passagem de argumentos por valor-resultado (ou copy-in/copy-out) funciona como a passagem de argumentos por valor até ao fim da execução do corpo da função ou procedimento. Nesta altura, e antes da função ou procedimento retornar, o valor dos argumentos formais (formal arguments) é copiado para os argumentos efectivos (actual arguments).)
27. [Mitchell, 7.7] Calcule o resultado do programa seguinte, escrito numa notação à la Algol/Pascal, para os modos de passagem de argumentos indicados.

      begin
        integer i;
    
        procedure pass(x, y: integer)
        begin
          x := x + 1;
          y := x + 1;
          x := y;
          i := i + 1
        end;
    
        i := 1;
        pass(i, i);
        print i
      end
    

    1. Passagem de argumentos por valor.
    2. Passagem de argumentos por referência.
    3. Passagem de argumentos por valor-resultado.