Linguagens e Ambientes de Programação (2016/2017)



Teórica 07 (28/mar/2017)

Computação, Algoritmos, Programas, Linguagens e Paradigmas.
Funções com múltiplos parâmetros. Formas curried e não-curried. Aplicação parcial de funções curried. Formas equivalentes de escrita de funções.
Funções como valores de primeira classe.
Algumas funções de ordem superior sobre listas.

Computação

Computação

Facetas da computação

Automatismos e sua especificação


Algoritmos, Programas e Linguagens de Programação

Muhammad ibn Musa al-Khwarizmi

Algoritmo

A palavra "algoritmo" deriva da palavra Algoritmi que por sua vez corresponde à Latinização do nome do matemático Persa Muhammad ibn Musa al-Khwarizmi, nascido por volta de 780DC. Este cientista, que trabalhou quase toda a sua vida em Bagdad, deu importantes contribuições para a Álgebra, Trigonometria e Aritmética.

Programa

Linguagem de programação

Exemplo de algoritmo

Algoritmo de Euclides - mdc(m,n) Implementação em C do algoritmo anterior

Antiguidade dos Algoritmos

Duas questões importantes sobre computação e linguagens


Paradigmas de Programação

Já sabemos que computação significa processamento automático de informação, mas esta noção é demasiado vaga. Podemos interrogar-nos sobre quais os mecanismos concretos através dos quais esse processamento se efetua.

Na verdade, uma linguagem não pode deixar de se comprometer com algum conjunto de mecanismos primitivos para processar informação. Ao efetuar essa escolha, a linguagem adere a um paradigma de programação particular.

É surpreendente a grande variedade de paradigma de programação que têm sido inventados: PARADIGMAS.

Exemplos de paradigmas de programação e respetivos conceitos de base

Aspetos práticos

Uma linguagem de programação pode combinar mais do que um paradigma


Paradigma imperativo versus paradigma funcional

Paradigma imperativo

Paradigma funcional

Vantagens do paradigma funcional

Desvantagens do paradigma funcional

  • É mais difícil controlar detalhes relacionados com a eficiência dos programas.

  • Há problemas que envolvem estado de forma essencial, como por exemplo programar uma calculadora com registos de memória. Além disso o mundo exterior é imperativo (tem estado). Numa linguagem funcional pura, o estado precisa de ser simulado usando argumentos suplementares nas funções, o que obscurece o código. Contudo, a generalidade das linguagens funcionais não são puras, ou seja oferecem construções imperativas para lidar com certas situações. Deve é tentar-se minimizar e localizar o uso dessas construções.

    Minorar os problemas do estado

    Quando se programa com uma linguagem imperativa, há uma forma de minorar as desvantagens do estado. O uso de estado local privado é seguro de forma geral. Por exemplo, em Java, recomenda-se o uso de variáveis locais nos métodos, de variáveis de instância privadas nos objetos, e convém evitar todas as outras formas.



    Funções com múltiplos argumentos em OCaml

    Em OCaml há duas formas de escrever funções com mais do que um argumento: a forma não-curried e a forma curried. A segunda forma é elaborada mas tem vantagens técnicas.

    Forma não-curried

    Os vários argumento agrupam-se num único tuplo ordenado. Exemplos: Tecnicamente, a função nAdd tem apenas um parâmetro, de tipo int*int. Mas claro, através desse único parâmetro conseguimos passar duas unidades de informação.

    Forma curried

    Os argumentos ficam separados. Exemplos: Escrever funções curried não tem nada que saber: basta separar os parâmetros por espaços em branco, na cabeça de cada função. Contudo o tipo destas funções afigura-se surpreendente para quem o observa pela primeira vez. Isso é resultado da representação interna das funções em OCaml. Segue-se a explicação...

    Representação interna das funções em OCaml

    Por uma questão de simplicidade e regularidade de implementação, o OCaml só usa internamente funções anónimas com um único argumento. Uma função com múltiplos argumentos é convertida para um formato interno especial - chamado forma interna - que envolve apenas funções anónimas com um único argumento.

    Por exemplo, a função

    é internamente convertida em: Repare na engenhosa a ideia que está por detrás do esquema de tradução.

    Vejamos mais alguns exemplos de tradução, lado a lado:

    Avaliação de expressões envolvendo funções com múltiplos argumentos

    Compare a avaliação das duas seguintes expressões:

    Aplicação parcial

    As funções curried têm a vantagem de poderem ser aplicadas parcialmente ou seja, poderem ser invocadas omitindo alguns dos argumentos do final. Eis um exemplo de aplicação parcial:

    Associatividades

    Formas equivalentes de escrever a mesma função

    As seguintes quatro declarações são equivalentes, no sentido em que declaram exatamente a mesma função f:int->int->int. Todas são convertidas para a mesma forma interna.

    Funções como valores de primeira classe

    Nas linguagens funcionais as funções têm o estatuto de valores de primeira classe. Isso significa que as funções têm um estatuto tão importante como o dos inteiros, reais, e outros tipos predefinidos.

    Concretamente, numa linguagem funcional as funções podem ...

    Exemplos

    Exemplo 1. Composição de funções. Também se pode escrever: Exemplo 2. Função para converter do formato não-curried para o formato curried. Também se pode escrever: Exercício: Escrever a função inversa uncurry.

    Exercício: Que funções são as seguintes e quais os seus tipos:

    Exemplo 3. Como representar conjuntos usando apenas funções?

    Um conjunto é uma entidade cuja principal característica é a possibilidade de se poder saber se um valor lhe pertence ou não lhe pertence. Assim vamos representar cada conjunto por uma função booleana que aplicada a um valor produz true se esse valor pertence ao conjunto e false se não pertence. Esta é a chamada função característica do conjunto.

    Exemplo 4. Estrutura de dados com funções: lista de funções.

    Uma limitação das funções

    No caso geral, saber se duas funções dadas são iguais (i.e. saber se produzem sempre os mesmos resultados para os mesmos argumentos) é um problema que não pode ser resolvido por computador. Numa tal situação, costuma dizer-se que o problema é indecidível.

    #120