aula-02.org

Aula 02

Formas Especiais

Formas Especiais são formas com um método de avaliação específico. Vimos define, cond, if, and e or.

A tentativa de definir new-if mostra que if é uma forma especial. No código abaixo, a última forma, quando avaliada, provoca um erro. Ou seja, if não pode ser definida como uma função regular, é uma forma especial com uma semântica de avaliação particular.

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(if (< 0 10) 1 (/ 10 0))

(new-if (< 0 10) 1 (/ 10 0))

Abstrações

Quando definimos uma função, estamos criando uma abstração. Os usuários da função square não precisam saber como ela calcula o quadrado de um número. Os parâmetros são os argumentos da função, no corpo da função as referências aos parâmetros estão ligadas. Mas na função sum-of-squares, notamos que embora as referências à x e y estejam ligadas aos parâmetros da função, os símbolos square e + estão livres, a função espera que eles estejam definidos no ambiente onde a função está sendo declarada.

(define (square x) (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

A forma normal de avaliação das formas de Racket/Scheme é avaliar os argumentos e então aplicar a função. Alternativamente, poderia-se pensar em expandir primeiro as expressões e depois reduzir para valores.

No código seguinte, a função p é uma função recursiva que não para. O exemplo serve para mostrar que os diferentes métodos de avaliação descritos no parágrafo anterior podem produzir resultados diferentes.

(define (p) (p))

(define (test x y)
  (if (= x 0) 0 y))

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))

Raiz Quadrada e o Método de Newton

A função abaixo implementa o método de Newton para calcular a raiz quadrada de um número. Detaca-se a criação de abstrações diferentes (funções) para cada parte fundamental do algorítmo. Temos a função good-enough? (que por retornar sempre true ou false chamaremos de predicado), a função improve responsável por a cada iteração melhorar o chute da raiz, e a função sqrt-iter que efetivamente implementa o loop que tenta a cada etapa melhorar o chute até ter um valor próximo o suficiente da raiz desejada.

(define (square x) (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

A função good-enough? não é boa para valores muito pequenos nem para valores muito grandes. Por que? Para valores grandes, o preço que pagamos para calcular (square guess) é bem alto, dado que o resultado desta avaliação pode ser um valor tão grande quanto o valor entrada, exigindo o dobro da memória na computação da raiz. Para valores pequenos, o que ocorre? Experimentem as chamadas:

(sqrt 0.00005)
(sqrt 0.99999)

Exercícios

• Melhorar a função good=enough? como proposto no livro (exercício 1.7).
• Adaptar as funções acima para que além de retornar a raiz de um número, sqrt também retorne o número de interações necessárias para calcular a raiz.

Soluções

Observem o uso de list para retornar uma lista de valores. Notem ainda o argumento inters que armazena o número de interações executadas. Código enviado pelo Henrique e ajustado por mim.

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? new-guess old-guess)
  (< (abs (- new-guess old-guess)) 0.001))

(define (sqrt-iter x guess old-guess inters)
  (if (good-enough? guess old-guess)
      (list guess inters)
      (sqrt-iter x (improve guess x) guess (+ 1 inters))))

(define (sqrt x)
  (sqrt-iter x (improve 1.0 x) 1.0 0))

Discutimos a diferença na performance da expressão (- new-guess old-guess), linear no número de algarismos de new-guess e old-guess, com a expressão (* x x), quadrática no número de algarismos de x.