Exercícios das práticas de LP

1. Defina em BNF uma gramática não ambígua para analisar expressões matemáticas com números inteiros e as operações soma, subtracção, produto e divisão. Tenha em conta as prioridades e associatividade usuais das operações matemáticas.
2. Implemente em Prolog um predicado que permita calcular o valor de expressões aritméticas com inteiros e as operações de adição, subtracção, divisão e multiplicação.
3. Acrescente o operador de potenciação ^ à linguagem do exercício anterior. (Este operador associa à direita.)
4. Acrescente parêntesis à linguagem do exercício anterior.
5. [Mitchell, 4.3] Reduza o termo (λx.λy.x y) (λx.x y).
6. 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.
7. 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.
      (As anteriores alíneas b) e c) deste exercício foram substituídas pelo exercício seguinte.)

7. (Nova versão do exercício anterior.)
   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),

      o redex (λz.z) (λx.(λy.y) x) é mais exterior que (λy.y) x.)
8. 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.
9. Repita o exercício anterior para o programa:

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

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

11. À 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.
12. 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: 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); mantenha o valor de q na forma 0 + 1 + 3 + ... (ou 1 + 3 + ...).)
13. 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 :: []);
14. Usando o jlex e o cup e partindo dos ficheiros Makefile, expressoes.lex, expressoes.cup, Main.java e Expressao.java
    1. Implemente um avaliador de expressões aritméticas com somas e subtracções entre números naturais. O avaliador deverá construir uma árvore de sintaxe abstracta durante a análise sintáctica e, posteriormente, calcular o valor da expressão lida recorrendo a essa árvore.
    2. Acrescente os operadores de multiplicação ‘*’ e de divisão ‘/’ à linguagem.
    3. Acrescente os parêntesis ‘(’ e ‘)’ à linguagem.
    4. Acrescente o operador de potência ‘^’ à linguagem. Este operador associa à direita e tem maior precedência que os restantes operadores.
15. [Mitchell, 7.1] Considere o seguinte programa, que compila sem erros:

         1:   #include <stdio.h>
         2:
         3:   int main()
         4:   {
         5:     int n, norma;
         6:
         7:     printf("introduza um número: ");
         8:     scanf("%d", &n);
         9:
        10:     if (n > 0)
        11:       {
        12:         int norma = n;
        13:       }
        14:     else
        15:       {
        16:         int norma = -n;
        17:       }
        18:
        19:     printf("norma de %d = %d \n", n, norma);
        20:     return 0;
        21:   }
    

    1. Preveja o resultado do programa apresentado.
    2. Explique o resultado do programa através da evolução da pilha de execução, mostrando o conteúdo dos registos de activação lá contidos ao longo da execução do programa.
    3. Retire a declaração da variável norma da linha 5, substitua a linha 19 pelo código seguinte

           19a:    {
           19b:      int norma;
           19c:
           19d:      printf("norma de %d = %d \n", n, norma);
           19e:    }
       

       e repita as alíneas anteriores.
       (Nota: o resultado obtido com a versão 4 do GCC poderá não ser o esperado.)
    4. Substitua a linha 18 do programa obtido na alínea anterior por um bloco com uma única linha de código que garanta que o resultado escrito na linha 19d nunca estará correcto.
16. [Mitchell, 12.3] Assuma que A <: B e que B <: C.
    1. Quais dos seguintes tipos são subtipo de B -> B?
       1. B -> B
       2. B -> A
       3. B -> C
       4. C -> B
       5. A -> B
       6. C -> A
       7. A -> A
       8. C -> C
       9. A -> C
    2. De quais dos tipos da alínea anterior é B -> B subtipo?
17. Considere o seguinte programa em C+-:

      class A {
      public:
        virtual void g(A* x) { printf("A-g(A)"); }
                void g(B* x) { printf("A-g(B)"); }
      }
    
      class B: public A {
      public:
                void g(A* x) { printf("B-g(A)"); }
                void g(B* x) { printf("B-g(B)"); }
      }
    
      main()
      {
        A *p1 = new A;
        A *p2 = new A;
        B *p3 = new B;
        A *p4 = p3;
        B *p5 = p2;
    
        ...
      }
    

    Para cada uma das instruções seguintes, indique qual o resultado e que acções são efectuadas durante a compilação (em compile-time) e durante a execução (em run-time).

    1. p1 -> g(p2);
    2. p1 -> g(p3);
    3. p1 -> g(p4);
    4. p3 -> g(p1);
    5. p3 -> g(p3);
    6. p4 -> g(p2);
    7. p4 -> g(p3);
    8. p3 -> g(p5);
    9. p5 -> g(p1);
    10. p5 -> g(p3);