Introdução

Programação é uma área muito ampla, subdividida em paradigmas.

Paradigmas nos induzem a raciocinar de maneiras específicas.

Mas paradigmas não são dissociáveis.

Precisamos de uma mente aberta ao racionalizar a computação.

A computação realizada não muda, mas o vocabulário pode tornar o processo rápido.

Linguagens específicas são a ferramenta certa para o propósito certo.

Matemática constitui uma linguagem formal (ainda que não seja universal), onde parte-se de princípios auto-evidentes e, sob meios de racionalização, chega-se a novas conclusões.

"Mathematical notation provides perhaps the best-known and best-developed example of language used consciously as a tool of thought." (Iverson, 1986)

A notação formal usada em TC é uma linguagem matemática que especifica precisamente o funcionamento de máquinas abstratas.

Segundo Iverson (1986), linguagens de programação são notações formais universalizadas.

Mostraremos como linguagens específicas induzem formas diferentes de pensar ao resolvermos problemas específicos.

Mas primeiro…

Autômatos celulares unidimensionais

Notação definida por Stephen Wolfram (2002)

Dados gerais de um AC unidimensional:

• Dois estados por célula: viva (⋄) ou morta (.);
• Dois vizinhos: (esquerdo e direito);
• Vizinhança: Três células (esquerdo, atual, direito).

Rule 90

Considere a seguinte regra baseada na vizinhança:

⋄⋄⋄   ⋄⋄.   ⋄.⋄   ⋄..   .⋄⋄   .⋄.   ..⋄   ...
 .     ⋄     .     ⋄     ⋄     .     ⋄     . 

Transformando em binário

111 110 101 100 011 010 001 000
 0   1   0   1   1   0   1   0

Por que "Rule 90"?

Simplificação da regra

Equivale a realizar uma operação de ou-exclusivo entre os vizinhos e ignorar o estado da célula atual.

1X1 1X0 0X1 0X0
 0   1   1   0 

APL

Começaremos com a linguagem criada por Kenneth E. Iverson, chamada APL.

APL é uma linguagem criada para facilitar a manipulação de vetores e matrizes.

APL não possui, por padrão, nenhum condicional ou laço de repetição explícitos.

Função para a Rule 90 em APL

rule90←{⊃1=+/¯1 1⌽¨⊂⍵}

• Não há nenhuma referência ao tamanho do vetor;
• Não há laços de repetição explícitos;
• Não há estruturas de controle de fluxo explícitas.

Demonstração

      disp 3 1⍴r (rule90 r) (rule90 rule90 r)
┌─────────────┐
│0 0 1 1 1 0 0│
├─────────────┤
│0 1 1 0 1 1 0│
├─────────────┤
│1 1 1 0 1 1 1│
└─────────────┘

      gen←{(rule90⍣⍺)⍵}
      plotgen←{r←⍵⋄(⊃,/⍺ (⍴r))⍴⊃,/{⍵ gen r}¨¯1+⍳⍺}
      5 plotgen r
0 0 1 1 1 0 0
0 1 1 0 1 1 0
1 1 1 0 1 1 1
0 0 1 0 1 0 0
0 1 0 0 0 1 0

Visualização gráfica

      drawfig←{' ⋄'[1+⍵]}
      ]display drawfig 10 plotgen r
┌→──────┐
↓  ⋄⋄⋄  │
│ ⋄⋄ ⋄⋄ │
│⋄⋄⋄ ⋄⋄⋄│
│  ⋄ ⋄  │
│ ⋄   ⋄ │
│⋄ ⋄ ⋄ ⋄│
│⋄     ⋄│
│⋄⋄   ⋄⋄│
│ ⋄⋄ ⋄⋄ │
│⋄⋄⋄ ⋄⋄⋄│
└───────┘

Programa completo

rule90←{⊃1=+/¯1 1⌽¨⊂⍵}
gen←{(rule90⍣⍺)⍵}
plotgen←{r←⍵⋄(⊃,/⍺ (⍴r))⍴⊃,/{⍵ gen r}¨¯1+⍳⍺}
drawfig←{' ⋄'[1+⍵]}

Outras linguagens?

Common Lisp

(defun rot (n list)
  (cond ((zerop n) list)
        ((< n 0)
         (rot (+ (length list) n) list))
        (t (append (nthcdr n list)
                   (butlast list
                            (- (length list)
                               n))))))

(defun rule90 (list)
  (let ((left-rot  (rot 1 (copy-list list)))
        (right-rot (rot -1 (copy-list list))))
    (loop for val1 in left-rot
       for val2 in right-rot
       for num = (+ val1 val2)
       collect (if (= num 1) 1 0))))


(defparameter *r*
  (loop for i from 1 to 7
     collect (if (member i '(3 4 5)) 1 0)))

(format t "~a~%~a~%" *r* (rule90 *r*))

(0 0 1 1 1 0 0)
(0 1 1 0 1 1 0)

C++ moderno

#include <iostream>
#include <vector>
#include <algorithm>

void
rule90(std::vector<int>& r)
{
    std::vector<int> lrot(r);
    std::vector<int> rrot(r);

    std::rotate(lrot.begin(),  lrot.begin()  + 1, lrot.end());
    std::rotate(rrot.rbegin(), rrot.rbegin() + 1, rrot.rend());

    for(int i = 0; i < lrot.size(); i++) {
        int neighbors = lrot[i] + rrot[i];
        r[i] = (neighbors == 1) ? 1 : 0;
    }
}

void
print_vec(const std::vector<int>& r)
{
    for(int n : r)
        std::cout << n << ' ';
    std::cout << std::endl;
}

int
main(void)
{
    std::vector<int> r;
    for(int i = 1; i <= 7; i++) {
        if(i == 3 || i == 4 || i == 5)
            r.push_back(1);
        else r.push_back(0);
    }

    print_vec(r);
    rule90(r);
    print_vec(r);
    return 0;
}

0 0 1 1 1 0 0 
0 1 1 0 1 1 0

Nem tudo que reluz é ouro…

APL é boa para vetores e matrizes, mas não para propósito geral*.

APL requer um esquema de teclado próprio.

APL tem implementações muito fragmentadas.

As melhores partes de APL estão em Dyalog APL, uma implementação paga (se usada comercialmente).

Convenhamos, ninguém usa APL.

…mas nem tudo que é obscuro é carvão!

Aprender uma linguagem completamente diferente aguça sua forma de pensar.

Usar um paradigma diferente obriga você a pensar de forma diferente.

Muitas soluções para problemas envolvem pensamento lateral.

Problema: Dígrafos

Encontre todos os caminhos do nó a ao nó e.

Solução não-trivial: Use Prolog!

:- initialization main.

edge(a, b).
edge(b, d).
edge(d, h).
edge(a, f).
edge(c, d).
edge(h, e).
edge(a, g).
edge(c, e).
edge(h, f).
edge(b, c).
edge(g, h).

path(A, B, [A, B]) :- edge(A, B).

path(A, B, [A | CB]) :- edge(A, C),
                        path(C, B, CB).

main :-
    bagof(P, path(a, e, P), L),
    write(L),
    halt.

[[a,b,d,h,e],[a,b,c,e],[a,b,c,d,h,e],[a,g,h,e]]

Prolog pode ser de grande ajuda quando utilizado com outros paradigmas de programação.

De fato, variações de Prolog podem ser utilizadas como linguagens para bancos de dados relacionais.

Prolog também pode ser fácil e rapidamente implementado em linguagens como Scheme (Abelson et al., 1996; Pellegrini, 2018).

Conclusão

Matemática é uma linguagem para racionalização, e portanto, um recurso para modelagem de raciocínio.

Não prenda sua forma de raciocínio a uma única linguagem.

Aprenda uma nova linguagem de programação (especialmente se for diferente do que você usa).

Notações são suas amigas. Busque entender o que elas querem lhe dizer!

Bibliografia

ABELSON, H.; SUSSMAN, G. J.; SUSSMAN, J. Structure and interpretation of computer programs. MIT Press: Cambridge, 1996. ISBN: 978-0-262-51087-5.

IVERSON, K. Notation as a tool of thought. IBM Thomas J. Watson Research Center, 1986.

HOLM, N. S. Prolog control in six slides. Julho de 2019.

PELLEGRINI, J. C. Programação funcional e concorrente com Scheme. Universidade Federal do ABC: Santo André, 2018.