Introdução a Haskell

Processamento da Informação

Informação

do latim, informatio onis, conceber ideia.

Muitas tarefas demandam um processamento de informação que não podem ser feitas utilizando papel, lápis e uma calculadora científica. Mas contamos com o auxílio do computador:

Em Natureza da Informação aprendemos que os computadores utilizam o código binário para codificar a informação armazenada em sua memória. Uma sequência de valores binários pode ser entendida como o código DNA do computador que contém as instruções que devem ser feitas.

Como fazer para nos comunicarmos com o computador de tal forma que ele entenda o que queremos realizar mas que não seja necessário aprender a linguagem binária?

Para resolver esse problema foram criadas as Linguagens de Programação, com o intuito de definir uma linguagem intermediaria que fosse ao mesmo tempo compreendida pelo ser humano e fácil de traduzir para o código binário.

Computação

do latim, computare, calcular.

Cálculo para a solução de um problema através de um procedimento bem definido. Não necessariamente utilizando o computador. Ex.:

Resolva \(x^2 + 10x − 5 = 0\)

Basta fazer:

Algoritmos e Linguagem de Programação

Procedimento bem definido para realizar a computação. Ex.:

• Identifique \(a, b, c\) da equação
• Calcule \(x_1 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}\)
• Calcule \(x_2 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}\)

do grego, algiros arithmos, números dolorosos.

O termo foi criado em homenagem a Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī, matemático persa autor do livro Kitab al-jabr wa’l-muqabala, que estudou soluções de equações lineares e quadráticas.

A partir desse livro foi cunhado o termo álgebra.

Algoritmo de Euclides

Conhecido como o primeiro algoritmo da história contido no livro Os Elementos de Euclides publicado no ano 300 AC.

Dados dois números inteiros, a e b, não primos entre si, encontrar o máximo divisor comum

dado que \(a = b \cdot q + r\) é a divisão inteira e \(r\) é o resto.

Exemplo: \(a = 68\) e \(b = 119\)

Propriedades necessárias de um Algoritmo

1. Finitude: o algoritmo SEMPRE deve terminar em um período finito de tempo.

2. Desambiguidade: cada passo do algoritmo deve ser descrito de forma desambígua.

3. Entrada: um algoritmo pode ter $0$ ou mais entradas (condições iniciais).

4. Saída: um algoritmo deve ter uma ou mais saídas (respostas do problema).

Linguagem de Programação

Para utilizarmos o computador para calcular o resultado de algoritmos precisamos saber nos comunicarmos com ele.

As Linguagens de Programação foram inventadas como um meio termo entre o nosso idioma e o idioma compreendido pelo computador. Elas são definidas como um conjunto de instruções e sintaxes que nos permitem instruir o computador de forma desambígua.

Essas instruções são traduzidas para a linguagem do computador através de um compilador ou interpretador.

Compilador: traduz o código para a linguagem de máquina e armazena essa interpretação em um arquivo executável.

Interpretador: traduz em tempo real o código escrito na linguagem especificada.

mdc 0 b = b
mdc a 0 = a
mdc a b = mdc b (a `rem` b)

main = do
    print (mdc 68 199)

Linguagem de Máquina

O código acima, durante a compilação, é traduzida para uma linguagem intermediária, chamada linguagem de montagem para então ser transformada em uma linguagem de máquina.

A linguagem de máquina são sequências de bits que representam uma instrução.

O código acima em linguagem de montagem pode se tornar (dependendo do compilador):

mov esi, 68 # m = 68
mov ebx, 119 # n = 119
jmp .L2
# vai para o passo 2
.L3:
  mov ebx, edx
# n = r
.L2:
  mov eax, ebx
  idiv esi  # EAX = m / n (EAX), EDX = r
  mov esi, ebx # m = n
  test edx, edx # verifica se o resto é zero
  jne .L3  # se teste anterior não zero, vai para L3

Uma instrução em linguagem de máquina tem o formato:

Uma vez que o código de máquina demanda que o programador tenha em mãos um livro com todos os códigos binários de cada instrução e, mesmo a linguagem de montagem, é bastante distante de uma linguagem natural, foram criadas linguagens de alto nível com o intuito de aproximar de uma linguagem mais descritiva do que queremos computar.

Nesse curso utilizaremos a linguagem Haskell, descrita a seguir.

Linguagem Haskell

Haskell é uma linguagem de programação funcional, ou seja, em que o componente principal são funções matemáticas. O intuito dessa linguagem é que o programador seja capaz de descrever os algoritmos utilizando uma linguagem próxima da linguagem matemática.

Como exemplo, vamos revisitar o algoritmo de mdc, implementado anteriormente e transcrito novamente abaixo:

mdc 0 b = b
mdc a 0 = a
mdc a b = mdc b (a `rem` b)

main = do
    print (mdc 68 199)

As 3 primeiras linhas descrevem a função MDC, na mesma notação (com exceção dos parênteses) que Euclides utilizou! A sintaxe utilizada para definir uma função é:

nome da função parâmetros separados por espaço = expressão / cálculo matemático

A primeira e a segunda linha descrevem os casos especiais da função, em que o valor de uma das variáveis é igual a zero. A terceira linha representa o caso geral, em que \(mdc(a,b) = mdc(b, r)\). A expressão a `rem` b é o resto da divisão de a por b.

As linhas seguintes representa o bloco de execução do seu programa. A palavra-chave main indica que para executar o programa o computador deve seguir as instruções a partir da instrução do. Na última linha requisitamos que o computador calcule e imprima (print) o resultado de MDC(68, 199).

Um exemplo mais simples é o cálculo da média entre dois valores:

media a b = (a + b) / 2

main = do
    print (media 2 3)

A função média pode ser descrita em apenas uma única instrução, como a soma das duas variáveis e a divisão do resultado por dois.

No próximo tópico aprenderemos os operadores aritméticos e lógicos disponíveis como padrão na linguagem Haskell.

A instalação do Haskell vem com duas ferramentas importantes o ghci que é uma ferramenta interativa para explorar o Haskell e o ghc que compila um código-fonte em executável.

No prompt de comando ou terminal digite ghci e aperte enter. Aparecerá a palavra Prelude> que te permite entrar com instruções na linguagem Haskell. Teste com a expressão 3 + 5 apertando enter em seguida, irá aparecer o resultado da expressão. Para sair do modo interativo digite :q e pressione enter.

Para compilar um programa e criar um código executável, primeiro escreva o código em um arquivo com extensão .hs e em seguida execute o comando ghc -o nome-do-programa nome-do-código.hs. Como exemplo salve o cálculo da média no arquivo media.hs e execute o comando ghc -o media media.hs, ao terminar o processo de compilação basta executar o comando media (ou ./media no Linux).