Curry (linguagem de programação) - Curry (programming language)

Este artigo é sobre a linguagem de programação Curry (batizada em homenagem a um matemático e lógico). Para o matemático e o lógico, consulte Haskell Curry . Para a técnica de ciência da computação, consulte Currying .
Curry
Paradigma funcional , lógico , não estrito, modular
Projetado por Michael Hanus, Sergio Antoy, et al.
Disciplina de digitação estático , forte , inferido
SO portátil
Local na rede Internet Curry
Implementações principais
PAKCS (com Prolog como alvo), mcc (com C como alvo), KiCS2 (com Haskell como alvo)
Influenciado por
Haskell e Prolog

Curry é uma linguagem de programação lógica funcional experimental , baseada na linguagem Haskell . Ele mescla elementos de programação funcional e lógica, incluindo integração de programação de restrição .

É quase um superconjunto de Haskell, faltando suporte principalmente para sobrecarregar usando classes de tipo , que algumas implementações fornecem de qualquer maneira como uma extensão de linguagem, como o Münster Curry Compiler.

Fundamentos da programação lógica funcional

Conceitos Básicos

Um programa funcional é um conjunto de funções definidas por equações ou regras. Um cálculo funcional consiste em substituir subexpressões por subexpressões iguais (em relação às definições de função) até que não sejam possíveis mais substituições (ou reduções) e um valor ou forma normal seja obtido. Por exemplo, considere a função duplamente definida por 

double x = x+x

A expressão “ duplo 1 ” é substituída por 1 + 1 . Este último pode ser substituído por 2 se interpretarmos o operador “ + ” como definido por um conjunto infinito de equações, por exemplo, 1 + 1 = 2 , 1 + 2 = 3 , etc. De forma semelhante, pode-se avaliar aninhado expressões (onde as subexpressões a serem substituídas estão entre aspas): 

'double (1+2)' → '(1+2)'+(1+2) → 3+'(1+2)' → '3+3' → 6

Há também outra ordem de avaliação se substituirmos os argumentos dos operadores da direita para a esquerda: 

'double (1+2)' → (1+2)+'(1+2)' → '(1+2)'+3 → '3+3' → 6

Nesse caso, as duas derivações levam ao mesmo resultado, propriedade conhecida como confluência . Isso decorre de uma propriedade fundamental das linguagens funcionais puras, denominada transparência referencial : o valor de um resultado computado não depende da ordem ou do tempo de avaliação, devido à ausência de efeitos colaterais. Isso simplifica o raciocínio e a manutenção de programas funcionais puros.

Como muitas linguagens funcionais como Haskell fazem, Curry apóia a definição de tipos de dados algébricos enumerando seus construtores. Por exemplo, o tipo de valores booleanos consiste nos construtores True e False que são declarados da seguinte forma: 

 data Bool = True | False

Funções em booleanos podem ser definidas por correspondência de padrões, ou seja, fornecendo várias equações para diferentes valores de argumento: 

 not True = False
 not False = True

O princípio de substituir igual por igual ainda é válido, desde que os argumentos reais tenham a forma exigida, por exemplo: 

not '(not False)' → 'not True' → False

Estruturas de dados mais complexas podem ser obtidas por tipos de dados recursivos . Por exemplo, uma lista de elementos, onde o tipo de elementos é arbitrário (denotado pela variável de tipo a ), é a lista vazia “ [] ” ou a lista não vazia “ x: xs ” consistindo de um primeiro elemento x e uma lista xs : 

 data List a = [] | a : List a

O tipo “ Lista a ” é geralmente escrito como [a] e as listas finitas x1 : x2 : ... : xn : [] são escritas como [ x1 , x2 , ... , xn ] . Podemos definir operações em tipos recursivos por definições indutivas onde a correspondência de padrões suporta a separação conveniente dos diferentes casos. Por exemplo, a operação de concatenação " ++ " em listas polimórficas pode ser definida como segue (a declaração de tipo opcional na primeira linha especifica que " ++ " leva duas listas como entrada e produz uma lista de saída, onde todos os elementos da lista são de o mesmo tipo não especificado): 

 (++) :: [a] -> [a] -> [a] 
 [] ++ ys = ys 
 (x:xs) ++ ys = x : xs++ys

Além de sua aplicação para várias tarefas de programação, a operação “ ++ ” também é útil para especificar o comportamento de outras funções nas listas. Por exemplo, o comportamento de uma função last que produz o último elemento de uma lista pode ser especificado da seguinte maneira: para todas as listas xs e elementos e, último xs = e se ∃ys : ys ++ [ e ] = xs.

Com base nesta especificação, pode-se definir uma função que satisfaça esta especificação empregando recursos de programação lógica. Da mesma forma que as linguagens lógicas, as linguagens lógicas funcionais fornecem soluções de busca para variáveis ​​existencialmente quantificadas. Em contraste com as linguagens de lógica pura, elas suportam a resolução de equações sobre expressões funcionais aninhadas de modo que uma equação como ys ++ [ e ] = [1,2,3] seja resolvida instanciando ys na lista [1,2] e e para o valor 3 . Em Curry, pode-se definir a última operação da seguinte forma: 

 last xs | ys++[e] =:= xs = e where ys,e free

Aqui, o símbolo “ =: = ” é usado para restrições equacionais a fim de fornecer uma distinção sintática da definição de equações. Da mesma forma, variáveis ​​extras (ou seja, variáveis ​​que não ocorrem no lado esquerdo da equação de definição) são explicitamente declaradas por “ where ... free ” para fornecer algumas oportunidades para detectar bugs causados ​​por erros de digitação. Uma equação condicional da forma l | c = r é aplicável para redução se sua condição c tiver sido resolvida. Em contraste com as linguagens puramente funcionais, nas quais as condições são avaliadas apenas para um valor booleano, as linguagens lógicas funcionais oferecem suporte à resolução de condições ao adivinhar valores para as incógnitas na condição. O estreitamento, conforme discutido na próxima seção, é usado para resolver esse tipo de condição.

Estreitando

O estreitamento é um mecanismo pelo qual uma variável é vinculada a um valor selecionado entre alternativas impostas por restrições. Cada valor possível é tentado em alguma ordem, com o restante do programa invocado em cada caso para determinar a validade da ligação. O estreitamento é uma extensão da programação lógica, pois realiza uma pesquisa semelhante, mas pode gerar valores como parte da pesquisa, em vez de se limitar a testá-los.

O estreitamento é útil porque permite que uma função seja tratada como uma relação: seu valor pode ser calculado "em ambas as direções". Os exemplos de Curry da seção anterior ilustram isso.

Conforme observado na seção anterior, o estreitamento pode ser pensado como uma redução em um gráfico de termo do programa e, freqüentemente, há muitas maneiras ( estratégias ) diferentes de reduzir um gráfico de determinado termo. Antoy et al. provou na década de 1990 que uma estratégia de estreitamento particular, necessária estreitamento , é ótima no sentido de fazer uma série de reduções para chegar a uma "forma normal" correspondente a uma solução que é mínima entre estratégias sólidas e completas. O estreitamento necessário corresponde a uma estratégia preguiçosa, em contraste com a estratégia de resolução SLD do Prolog .

Padrões funcionais

A última definição de regra mostrada acima expressa o fato de que o argumento real deve corresponder ao resultado do estreitamento da expressão ys ++ [e] . Curry pode expressar essa propriedade também da seguinte maneira mais concisa: 

 last (ys++[e]) = e

Haskell não permite tal declaração, pois o padrão no lado esquerdo contém uma função definida ( ++ ). Esse padrão também é chamado de padrão funcional . Os padrões funcionais são ativados pelos recursos funcionais e lógicos combinados de Curry e oferecem suporte a definições concisas de tarefas que exigem correspondência de padrões profunda em estruturas de dados hierárquicas.

Não determinismo

Como Curry é capaz de resolver equações contendo chamadas de funções com valores desconhecidos, seu mecanismo de execução é baseado em cálculos não determinísticos, de forma semelhante à programação lógica. Esse mecanismo também suporta a definição de operações não determinísticas , ou seja, operações que fornecem mais de um resultado para uma determinada entrada. O arquétipo das operações não determinísticas é a operação infixa predefinida ? , chamado de operador de escolha , que retorna um de seus argumentos. Este operador é definido pelas seguintes regras: 

 x ? y = x
 x ? y = y

Assim, a avaliação da expressão 0? 1 retorna 0 e também 1 . Computação com operações não determinísticas e computação com variáveis ​​livres por estreitamento tem o mesmo poder expressivo.

As regras que definem ? mostram uma característica importante do Curry: todas as regras são testadas para avaliar alguma operação. Portanto, pode-se definir por 

 insert x ys     = x : ys
 insert x (y:ys) = y : insert x ys

uma operação para inserir um elemento em uma lista em uma posição indeterminada de modo que a operação perm definida por 

 perm []     = []
 perm (x:xs) = insert x (perm xs)

retorna qualquer permutação de uma determinada lista de entrada.

Estratégias

Devido à ausência de efeitos colaterais, um programa de lógica funcional pode ser executado com diferentes estratégias. Para avaliar expressões, Curry usa uma variante da estratégia de estreitamento necessária que combina avaliação preguiçosa com estratégias de busca não determinísticas. Ao contrário do Prolog, que usa backtracking para buscar soluções, Curry não fixa uma estratégia de busca específica. Portanto, existem implementações de Curry, como KiCS2 , onde o usuário pode facilmente selecionar uma estratégia de pesquisa, como pesquisa em profundidade (backtracking), pesquisa em largura , aprofundamento iterativo ou pesquisa paralela.

Referências

links externos