Elementos da Programação de Computadores

Lucas Vieira

Recapitulando

  • Expressões Primitivas
  • Meios de Combinação
  • Meios de Abstração

Composição de procedimentos

Exemplo: Elevar ao quadrado

#lang sicp

;; Para    Elevar Algo ao quadrado,
(define             (square x)
  (*               x               x))
;; multiplique   Algo    por    Si Mesmo.

Definição formalizada

(define (<nome>  <parâmetros formais>)  <corpo>)

Modelo substitutivo para procedimentos

#lang sicp

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

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

Calculando a soma dos quadrados de \((2 + 3)\) e \((4 * 5)\):

(sum-of-squares (+ 2 3) (* 4 5))
(sum-of-squares 5 20)
(+ (square 5) (square 20))
(+  (* 5 5)    (* 20 20))
(+     25         400)
425

Controle de fluxo

Problema 1: Função Módulo

Função Módulo: O módulo de \(x \in \mathbb{R}\) pode ser descrito como

\begin{equation*} f(x) = \begin{cases} x &\text{se $x > 0$}\\ 0 &\text{se $x = 0$}\\ -x &\text{se $x < 0$} \end{cases} \end{equation*}

Exemplo 1

#lang sicp

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

Estrutura geral da condicional

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))
  • Condicional não é função!

Exemplo 2

#lang sicp

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))
  • Simplificação do Exemplo 2
    #lang sicp
    
    (define (abs x)
      (if (< x 0)
          (- x)
          x))
    

Estrutura geral do special-form "if"

(if <predicado> <consequente> <alternativa>)
  • Condicional não é função!

Operadores lógicos

  • (and <e1> <e2> ... <en>)
  • (or <e1> <e2> ... <en>)
  • (not <e>)

Processos gerados por procedimentos

Fatorial

Dado \(\mathbb{U} = \mathbb{N^{*}}\), \(n! \Rightarrow f(n)\) tal que

\begin{equation*} f(n) = \begin{cases} 1 &\text{se $n = 1$}\\ n \cdot f(n - 1) &\text{caso contrário} \end{cases} \end{equation*}

Amostra

\begin{align*} 5! = 5 \cdot 4! &\Leftrightarrow f(5) = 5 \cdot f(4)\\ 1! = 1 &\Leftrightarrow f(1) = 1 \end{align*}

Exemplo 1: Fatorial por recursão linear

#lang sicp

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (1- n)))))

Expansão para fatorial de 6:

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

Exemplo 2: Fatorial por recursão iterativa

#lang sicp

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (1+ counter)
                 max-count)))

(define (factorial n)
  (fact-iter 1 1 n))

Expansão para fatorial de 6:

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

Sequência de Fibonacci

A sequência de Fibonacci inicia-se com os números \(0, 1, 1, 2, 3, 5, 8, 13 \dots\)

O enésimo número da sequência de Fibonacci (\(\mathbb{U} = \mathbb{N}\)) pode ser calculado como

\begin{equation*} f(n) = \begin{cases} 0 &\text{se $n = 0$}\\ 1 &\text{se $n = 1$}\\ f(n - 1) + f(n - 2) &\text{para outros casos} \end{cases} \end{equation*}

Exemplo 1: Fibonacci por recursão em árvore

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (1- n))
                 (fib (- n 2))))))

Expansão para 5º número da sequência de Fibonacci

fib_quad.png

Exemplo 2: Fibonacci por recursão iterativa

#lang sicp

(define (fib-iter current previous count)
  (if (= count 0)
      previous
      (fib-iter (+ current previous)
                current
                (1- count))))

(define (fib n)
  (fib-iter 1 0 n))

Expansão para 5º número da sequência de Fibonacci

(fib 5)
(fib-iter 1 0 5)
(fib-iter 1 1 4)
(fib-iter 2 1 3)
(fib-iter 3 2 2)
(fib-iter 5 3 1)
(fib-iter 8 5 0)
5

Exercícios

Exercício 1

(sicp, Exercise 1.10) O procedimento a seguir computa uma função matemática conhecida como função de Ackermann.

#lang sicp

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (1- x)
                 (A x (1- y))))))

Quais são os valores das expressões a seguir?

(A 1 10)
(A 2 4)
(A 3 3)

Exercício 2

Uma forma engenhosa de calcular o máximo divisor comum entre dois números é o algoritmo de Euclides, definido segundo a equação a seguir (\(\mathbb{U} = \mathbb{N}\)):

\begin{equation*} mdc(a, b) = \begin{cases} a &\text{quando $b = 0$}\\ mdc(b, a\, mod\, b) &\text{caso contrário} \end{cases} \end{equation*}

Dado que \(x\, mod\, y\) é o resto da divisão inteira entre \(x\) e \(y\):

  1. Escreva um procedimento que compute o máximo divisor comum entre quaisquer dois números.
  2. Realize uma expansão, segundo o Método Substitutivo, para o procedimento que escreveu. Não é necessário mostrar condicionais.

Dica: remainder é o procedimento geral em Scheme que computa o resto da divisão inteira entre dois números.

Exercício-desafio

(sicp, Exercise 1.6, adaptado) Alyssa P. Hacker não vê por que if precisa ser um special-form. "Por que eu não posso definir um procedimento simples em termos de cond?", ela pergunta.

A amiga de Alyssa, Eva Lu Ator, diz que isso pode, sim, ser feito, através da seguinte nova definição de if:

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

Maravilhada, Alyssa usa new-if na seguinte expressão:

(define (foo a b)
  (new-if (> a 0)
          (/ b a)
          (foo (1+ a) b)))

O que acontece quando Alyssa tenta usar este procedimento para computar (foo -2 5)? Explique.

Bibliography

  • [sicp] "Harold Abelson, Gerald Jay Sussman & Julie Sussman", Structure and Interpretation of Computer Programs, MIT Press (1996).

Bibliography

  • [sicp] "Harold Abelson, Gerald Jay Sussman & Julie Sussman", Structure and Interpretation of Computer Programs, MIT Press (1996).