Sistemas Computacionais

Até então temos visto programas que operam sobre dados em uma grande composição de funções, onde a saída de um procedimento alimenta a entrada de outro e assim por diante. O fluxo de dados é sempre unidirecional e depende somente do arranjo dos procedimentos e das entradas iniciais, caracterizando programas puramente funcionais. Além disso, o modelo aplicado para computar o resultado de um programa é muito simples, bastando substituir aplicações de procedimentos por sua definição instanciada com os argumentos fornecidos.

Alguns problemas exigem um fluxo de dados diferente. Gostaríamos de introduzir maneiras de alterar o comportamento do programa de formas diferentes dependendo do instante em que o sistema se encontra.

Perceba que, desde o início da oficina até este ponto, jamais fez-se necessário utilizar conceitos como variáveis, atribuições ou estado mutável; é o que faremos agora.

Na medida em que atribuições e ações de mudança são introduzidas na programação, acabamos de nos sujeitar a todos os problemas terríveis que vêm assolando filósofos por milhares de anos. (Sussman, 1968)

Em Scheme, a ferramenta para tal é set! e seus derivados[2]:

(define count 10)
(define (count-down)
  (set! count (- count 1))
  count)

(define a (cons 1 2))
(define b (cons a a))
(define a (cons 3 2))
b ; = ?

(define a (cons 1 2))
(define b (cons a a))
(set-car! a 3)
b ; = ?

Explique o bug no procedimento set-fact.

(define (fact n)
  (let loop ((i 1) (p 1))
    (if (> i n) p
        (loop (+ i 1) (* p i)))))

(define (set-fact n)
  (let ((i 1) (p 1))
    (let loop ()
      (if (> i n) p
          (begin
            (set! i (+ i 1))
            (set! p (* p i))
            (loop))))))

Memoization com Closures

Se analisarmos a primeira definição do procedimento fib, percebemos que seu principal problema é a computação de resultados que já foram vistos e calculados anteriormente. Uma forma de contornar esse problema seria fazer com que o processo se lembre desses resultados parciais em um tipo de memória, evitando assim uma computação que pode vir a ser custosa. Essa técnica de programação dinâmica se chama memoization.

(define (fib n)
  (display "Computing Fib of ") (display n) (newline)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (memo-fib (- n 1))
                 (memo-fib (- n 2))))))

(define cache (make-table))

(define (memo-fib n)
  (let ((hit? (lookup cache n)))
    ;; hit or miss
    (or hit?
        (let ((result (fib n)))
          (insert! cache n result)
          result))))

;; (clear-table! cache)

Scheme adota a convenção de sinalizar procedimentos que geram efeitos colaterais com o sufixo !.

(define (make-table)
  (cons '*table* '()))

(define (lookup table key)
  (let ((record (assoc key (cdr table))))
    (cond (record => cdr)
          (else #f))))

(define (insert! table key value)
  (cond ((assoc key (cdr table)) => (lambda (record) (set-cdr! record value)))
        (else (set-cdr! table
                        (cons (cons key value) (cdr table)))))
  'ok)

(define (clear-table! table)
  (set-cdr! table '())
  'ok)

; (define (assoc k a-list)
;   (cond ((null? a-list) #f)
;         ((equal? k (caar a-list)) (car a-list))
;         (else (assoc k (cdr a-list)))))

Tomando a tabela apresentada como exemplo, tente implementar uma pilha (LIFO) com estado mutável. Depois, explique como fazer o mesmo através de programação puramente funcional.

A estrutura de dados implementada é um exemplo de sistema cujos resultados dependem não somente das entradas dadas, mas também do seu estado interno.

Perceba que a única coisa atrelada à sequência de Fibonacci no corpo de memo-fib é a chamada da função fib. Podemos generalizar essa ideia em uma função de alta ordem que retorna um closure contendo sua própria "memória".

(define (memoize proc)
  (let ((cache (make-table)))
    (define (delegate . args)
      (let ((hit (lookup cache args)))
        (or hit
            (let ((result (apply proc args)))
              (insert! cache args result)
              result))))
    delegate))

(define memo-fib (memoize
  (lambda (n)
    (display "Computing Fib of ") (display n) (newline)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (memo-fib (- n 1))
                   (memo-fib (- n 2))))))))

(define memo-sqrt (memoize sqrt))

;; <etc>

Apesar de termos melhorado a performance do procedimento antes exponencial para linear, o fizemos em troca de memória da máquina. Além disso, o sistema de busca de resultados armazenados não é muito eficiente: se na avaliação de (+ (memo-fib (- n 1)) (memo-fib (- n 2))) as entradas na cache estiverem em ordem crescente, seria necessário varrer a lista do início até encontrar a chave (- n 1) e depois recomeçar o processo indo do ínicio da tabela até a entrada (- n 2).

Por causa de situações como estas, implementações sérias de Scheme provêm formas de utilizar estruturas de dados mais eficientes projetadas em outras linguagens. Em Guile, por exemplo, poderíamos utilizar uma hashtable para chegar o mais próximo possível de calcular um dado número de Fibonacci em tempo constante (supondo que já tenha sido pré-computado).

;; GUILE
(define make-table make-hash-table)
(define lookup hash-ref)
(define insert! hash-set!)

Objetos Dinâmicos

No exemplo anterior utilizamos uma lista cujo estado interno era acessado e alterado através de funções auxiliares: os processos são totalmente orientados aos dados manipulados.

A abordagem orientada a objetos em Scheme envolve a utilização de closures que têm acesso ao seu próprio estado e fornecem interfaces para interagir com o ambiente externo.

(define (make-wrapper)
  (let ((x 'void))
    (define (setter! y)
      (set! x y)
      'ok)
    (define (self method)
      (cond ((eq? method 'get) x)
            ((eq? method 'set) setter!)
            (else (error "Undefined operation" method))))
    self))

(define (get-value w)
  (w 'get))

(define (set-value! w x)
  ((w 'set) x))

Nesse exemplo, ao passar a mensagem 'set a um objeto criado por make-wrapper o mesmo retorna um procedimento que alterará seu estado interno quando chamado.

Assim, podemos formar sistemas como conjuntos de objetos intercomunicantes. Note que agora o fluxo de dados não têm sentido único, podendo se propagar de qualquer forma em uma rede de objetos conectados arbitrariamente.

Uma aplicação desse tipo de sistema é encontrada em equações algébricas. Por exemplo, a equação \( F = \frac{9}{5} * C + 32 \) determina a relação entre temperaturas das escalas Celsius e Fahrenheit.

(define (c2f x)
  (+ (* (/ 9 5) x) 32))

Esse procedimento representa apenas um sentido da igualdade, visto que não permite calcular a temperatura em Celsius dado uma em Fahrenheit. O mesmo se aplicaria se fossêmos representar a relação da lei de Ohm.

\[ I = \frac{V}{R} \Leftrightarrow V = R * I \Leftrightarrow R = \frac{V}{I} \]

A mesma deve valer para quaisquer valores de corrente, resistência e tensão, onde uma alteração de um lado da igualdade será propagada pela equação e causará uma mudança no lado oposto. Portanto, visamos modelar equações algébricas através de um sistema de propagação de restrições. Para isso, vamo inserir em Scheme uma linguagem que trata de conectores e operadores.

(define (make-connector)
  (let ((value #f)
        (informant #f)
        (constraints '()))
    (define (set-my-value newval source)
      (cond ((not (has-value? self))
             (set! value newval)
             (set! informant source)
             (for-each-except source
                              inform-about-value
                              constraints))
            ((not (= value newval))
             (error "Contradiction" (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin
            (set! informant #f)
            (for-each-except retractor
                             inform-about-no-value
                             constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint constraints))
          (set! constraints
                (cons new-constraint constraints)))
      (if (has-value? self)
          (inform-about-value new-constraint))
      'done)
    (define (self request)
      (cond ((eq? request 'has-value?) informant)
            ((eq? request 'value) value)
            ((eq? request 'set-value!) set-my-value)
            ((eq? request 'forget) forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown request -- CONNECTOR" request))))
    self))

(define (for-each-except exception procedure list)
  (let loop ((items list))
    (cond ((null? items) 'done)
          ((eq? (car items) exception) (loop (cdr items)))
          (else
           (procedure (car items))
           (loop (cdr items))))))

(define (has-value? connector)
  (if (connector 'has-value?) #t #f))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector new-value informant)
  ((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

(define (constant value connector)
  (define (self request)
    (error "Unknown request -- CONSTANT" request))
  (connect connector self)
  (set-value! connector value self)
  self)

(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) (has-value? a2))
           (set-value! sum
                       (+ (get-value a1) (get-value a2))
                       self))
          ((and (has-value? a1) (has-value? sum))
           (set-value! a2
                       (- (get-value sum) (get-value a1))
                       self))
          ((and (has-value? a2) (has-value? sum))
           (set-value! a1
                       (- (get-value sum) (get-value a2))
                       self))))
  (define (process-forget-value)
    (forget-value! sum self)
    (forget-value! a1 self)
    (forget-value! a2 self)
    (process-new-value))
  (define (self request)
    (cond ((eq? request 'I-have-a-value) (process-new-value))
          ((eq? request 'I-lost-my-value) (process-forget-value))
          (else (error "Unknown request -- ADDER" request))))
  (connect a1 self)
  (connect a2 self)
  (connect sum self)
  self)

(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (and (has-value? m1) (= (get-value m1) 0))
               (and (has-value? m2) (= (get-value m2) 0)))
           (set-value! product 0 self))
          ((and (has-value? m1) (has-value? m2))
           (set-value! product
                       (* (get-value m1) (get-value m2))
                       self))
          ((and (has-value? product) (has-value? m1))
           (set-value! m2
                       (/ (get-value product) (get-value m1))
                       self))
          ((and (has-value? product) (has-value? m2))
           (set-value! m1
                       (/ (get-value product) (get-value m2))
                       self))))
  (define (process-forget-value)
    (forget-value! product self)
    (forget-value! m1 self)
    (forget-value! m2 self)
    (process-new-value))
  (define (self request)
    (cond ((eq? request 'I-have-a-value) (process-new-value))
          ((eq? request 'I-lost-my-value) (process-forget-value))
          (else (error "Unknown request -- MULTIPLIER" request))))
  (connect m1 self)
  (connect m2 self)
  (connect product self)
  self)

(define (probe name connector)
  (define (print-probe value)
    (display name)
    (display " = ")
    (display value)
    (newline))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (self request)
    (cond ((eq? request 'I-have-a-value) (process-new-value))
          ((eq? request 'I-lost-my-value) (process-forget-value))
          (else (error "Unknown request -- PROBE" request))))
  (connect connector self)
  self)

(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

(define (c* x y)
  (let ((z (make-connector)))
    (multiplier x y z)
    z))

(define (cv val)
  (let ((c (make-connector)))
    (constant val c)
    c))

(define (c- x y)
  (let ((z (make-connector)))
    (adder z y x)
    z))

(define (c/ x y)
  (let ((z (make-connector)))
    (multiplier z y x)
    z))

Finalmente, para utilizar o sistema:

(define (celsius-fahrenheit-converter x)
  (c+ (c* (c/ (cv 9) (cv 5)) x) (cv 32)))

(define c (make-connector))
(probe "Celsius" c)

(define f (celsius-fahrenheit-converter c))
(probe "Fahrenheit" f)

(set-value! c 100 'user)


(define (ohms-law v r) (c/ v r))

(define v (make-connector))
(probe "Voltage" v)

(define r (make-connector))
(probe "Resistance" r)

(define i (ohms-law v r))
(probe "Current" i)

Lazy Streams no Infinito

Tendo observado outros tipos de sistemas, voltemos aos unidirecionais com o intuito de explorar esse paradigma de fluxo de dados: se um programa consiste no encadeamento de funções puras, não importa o momento em que um valor intermediário é computado, desde que quando o resultado final seja requisitado ele se faça presente. Sistemas assim podem se dar ao luxo de serem "preguiçosos", adiando ao máximo o instante em que realizarão uma computação.

Computadores, assim como pessoas, tentam adiar ao máximo possível a ocorrência de eventos desagradáveis. (Tanenbaum, 2011)

A seguir implementaremos um tipo de lista que segue essa ideia de lazy evaluation. Os principais procedimentos pelos quais essas "listas preguiçosas" serão manipuladas estão descritos abaixo.

(define (stream-ref seq n)
  (cond ((empty? seq) #f)
        ((<= n 0) (head seq))
        (else (stream-ref (tail seq) (- n 1)))))

(define (stream-for-each proc seq)
  (if (not (empty? seq))
      (begin
        (proc (head seq))
        (stream-for-each proc (tail seq)))))

(define (stream-map proc seq)
  (if (empty? seq) empty-stream
      (stream (proc (head seq))
              (stream-map proc (tail seq)))))

(define (stream-filter pred seq)
  (cond ((empty? seq) empty-stream)
        ((pred (head seq)) (stream (head seq)
                                   (stream-filter pred (tail seq))))
        (else (stream-filter pred (tail seq)))))

(define (stream-foldr op acc seq) ;; aka reduce
  (if (empty? seq) acc
      (op (head seq)
          (stream-foldr op acc (tail seq)))))

(define (stream-zip-with op sa sb)
  (stream (op (head sa) (head sb))
          (stream-zip-with op (tail sa) (tail sb))))

Construa um procedimento (stream-range lo hi) que gera uma stream com todos os inteiros entre lo e hi.

As primitivas que constroem e acessam as streams são responsáveis por diferenciá-las de listas normais.

(define (memo-proc proc)
  (let ((run? #f)
        (cached '()))
    (lambda ()
      (if run? cached
          (let ((result (proc)))
            (begin
              (set! run? #t)
              (set! cached result)
              result))))))

;; delay
(define-syntax lazy
  (syntax-rules ()
    ((lazy expr)
      (memo-proc (lambda () expr)))))

;; force
(define (thunk p) (p))

(define-syntax stream
  (syntax-rules ()
    ((stream x y)
      (cons x (lazy y)))))

(define (head s) (car s))
(define (tail s) (thunk (cdr s)))
(define (empty? s) (null? s))
(define empty-stream '())

As macros stream e lazy definem transformações que ocorrem no código antes da sua interpretação. Assim, uma stream consiste num par onde a computação do segundo elemento foi postergada, deixando apenas uma promessa de que estará lá quando for necessária. Se um elemento de uma stream nunca for acessado, a promessa não precisa ser cumprida e nenhum processamento é efetuado.

Note que esse mecanismo permite representar sequências infinitas: todos os elementos estarão presentes, mas só existirão de fato quando alguém requisitar.

(define (ints-from n)
  (stream n (ints-from (+ n 1))))

(define (sieve seq) ;; crivo de Eratostenes
  (define (divisible? a b)
    (= 0 (remainder a b)))
  (if (empty? seq) seq
      (stream (head seq)
              (sieve (stream-filter (lambda (x) (not (divisible? x (head seq))))
                                    (tail seq))))))

(define primes (sieve (ints-from 2)))

Podemos afirmar, portanto, que primes é a stream de todos os números primos.

O esquema pode ser aplicado também para séries infinitas, por exemplo na série de Taylor-Maclaurin para o arco tangente

\[ \arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + ... \]

(define (arctan-series x n)
  (stream (/ (expt x n) n)
          (stream-map - (arctan-series x (+ n 2)))))

Podemos substituir x=1 para poder encontrar a fórmula de Madhava para aproximar o valor de \( \pi \):

\[ \arctan 1 = \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + ... \]

Tente gerar uma stream contendo as aproximações de pi pela fórmula anterior, onde cada n-ésimo elemento equivale à soma parcial de n termos da série.

(define (partial-sums s)
  (stream-zip-with + s (stream 0 (partial-sums s))))

(define pi-approximations
  (stream-map (lambda (pi/4) (* 4 pi/4))
              (partial-sums (arctan-series 1.0 1))))

Por fim, vamos obter a sequência de Fibonacci completa em uma stream infinita.

(define (fibonacci-sequence prev curr)
  (stream prev
          (fibonacci-sequence curr (+ prev curr))))

(define fibs (fibonacci-sequence 0 1))

Reflita sobre a possibilidade de computar elementos de uma lazy stream paralelamente com técnicas de programação concorrente. Você pode discutir suas ideias na seção de comentários desse site.