5.1.2 Abstração no Projeto de Máquinas

Frequentemente definiremos uma máquina para incluir operações "primitivas" que são na verdade muito complexas. Por exemplo, nas seções 5.4 e 5.5 trataremos as manipulações de ambientes do JavaScript como primitivas. Tal abstração é valiosa porque nos permite ignorar os detalhes de partes de uma máquina para que possamos nos concentrar em outros aspectos do projeto. O fato de termos varrido muita complexidade para debaixo do tapete, no entanto, não significa que um projeto de máquina seja irrealista. Podemos sempre substituir as "primitivas" complexas por operações primitivas mais simples.

Considere a máquina MDC. A máquina tem uma instrução que calcula o resto dos conteúdos dos registradores a e b e atribui o resultado ao registrador t. Se quisermos construir a máquina MDC sem usar uma operação de resto primitiva, devemos especificar como calcular restos em termos de operações mais simples, como subtração. De fato, podemos escrever uma função JavaScript que encontra restos desta forma:

Exemplo de Código

1function remainder(n, d) {
2  return n < d
3         ? n
4         : remainder(n - d, d);
5}

function remainder(n, d) {
  return n < d
         ? n
         : remainder(n - d, d);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Assim, podemos substituir a operação de resto nos caminhos de dados da máquina MDC por uma operação de subtração e um teste de comparação. A Figura 5.5 mostra os caminhos de dados e o controlador para a máquina elaborada. A instrução

assign("t", list(op("rem"), reg("a"), reg("b")))

na definição do controlador MDC é substituída por uma sequência de instruções que contém um laço, como mostrado na Figura 5.6.

controller(
  list(
    "test_b",
      test(list(op("="), reg("b"), constant(0))),
      branch(label("gcd_done")),
      assign("t", reg("a")),
    "rem_loop",
      test(list(op("<"), reg("t"), reg("b"))),
      branch(label("rem_done")),
      assign("t", list(op("-"), reg("t"), reg("b"))),
      go_to(label("rem_loop")),
    "rem_done",
      assign("a", reg("b")),
      assign("b", reg("t")),
      go_to(label("test_b")),
    "gcd_done"))

Figura 5.6: Sequência de instruções do controlador para a máquina MDC na Figura 5.5.

Exercício 5.3

Projete uma máquina para calcular raízes quadradas usando o método de Newton, conforme descrito na seção 1.1.7 e implementado com o seguinte código na seção 1.1.8:

Exemplo de Código

1function sqrt(x) {
2  function is_good_enough(guess) {
3      return math_abs(square(guess) - x) < 0.001;
4  }
5  function improve(guess) {
6      return average(guess, x / guess);
7  }
8  function sqrt_iter(guess) {
9      return is_good_enough(guess)
10             ? guess
11             : sqrt_iter(improve(guess));
12  }
13  return  sqrt_iter(1);
14}

function sqrt(x) {
  function is_good_enough(guess) {
      return math_abs(square(guess) - x) < 0.001;
  }
  function improve(guess) {
      return average(guess, x / guess);
  }
  function sqrt_iter(guess) {
      return is_good_enough(guess)
             ? guess
             : sqrt_iter(improve(guess));
  }
  return  sqrt_iter(1);
}

⛓ sessãoCódigo editável · Ctrl+Enter executa · Esc solta o foco

Comece assumindo que as operações is_good_enough e improve estão disponíveis como primitivas. Em seguida, mostre como expandir essas operações em termos de operações aritméticas. Descreva cada versão do projeto da máquina sqrt desenhando um diagrama de caminho de dados e escrevendo uma definição do controlador na linguagem de máquina de registradores.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Primeira versão — tratando is_good_enough e improve como operações primitivas: registradores x e guess; o controlador é um laço puro:

   guess ← 1
test
   se good_enough(guess, x), vá para done
   guess ← improve(guess, x)
   vá para test
done

Versão expandida — abrindo as duas "primitivas" em aritmética de verdade (quadrado, subtração, valor absoluto, comparação com 0.001; divisão e média), o teste vira uma sequência com um registrador temporário:

test
   t ← guess · guess
   t ← t − x
   t ← abs(t)
   se t < 0.001, vá para done
   t ← x / guess
   guess ← (guess + t) / 2
   vá para test

Os caminhos de dados ganham os operadores aritméticos e o registrador t. A comparação das duas versões é o ponto do exercício: o nível de abstração das operações primitivas é uma escolha de projeto — descer de nível troca simplicidade do controlador por realismo do hardware.

Resolvi o exercício 5.3

Exercício 5.3​

Exercício 5.3