Curry is a programming language that integrates functional and logic programming. Last week, Denis Firsov and I had a look at Curry, and Thursday, I gave an introductory talk about Curry in the Theory Lunch. This blog post is mostly a write-up of my talk.
Like Haskell, Curry has support for literate programming. So I wrote this blog post as a literate Curry file, which is available for download. If you want to try out the code, you have to install the Curry system KiCS2. The code uses the functional patterns language extension, which is only supported by KiCS2, as far as I know.
Functional programming
The functional fragment of Curry is very similar to Haskell. The only fundamental difference is that Curry does not support type classes.
Let us do some functional programming in Curry. First, we define a type whose values denote me and some of my relatives.
data Person = Paul
| Joachim
| Rita
| Wolfgang
| Veronika
| Johanna
| Jonathan
| Jaromir
Now we define a function that yields the father of a given person if this father is covered by the Person
type.
father :: Person -> Person
father Joachim = Paul
father Rita = Joachim
father Wolfgang = Joachim
father Veronika = Joachim
father Johanna = Wolfgang
father Jonathan = Wolfgang
father Jaromir = Wolfgang
Based on father
, we define a function for computing grandfathers. To keep things simple, we only consider fathers of fathers to be grandfathers, not fathers of mothers.
grandfather :: Person -> Person
grandfather = father . father
Combining functional and logic programming
Logic programming languages like Prolog are able to search for variable assignments that make a given proposition true. Curry, on the other hand, can search for variable assignments that make a certain expression defined.
For example, we can search for all persons that have a grandfather according to the above data. We just enter
grandfather person where person free
at the KiCS2 prompt. KiCS2 then outputs all assignments to the person
variable for which grandfather person
is defined. For each of these assignments, it additionally prints the result of the expression grandfather person
.
Nondeterminism
Functions in Curry can actually be non-deterministic, that is, they can return multiple results. For example, we can define a function element
that returns any element of a given list. To achieve this, we use overlapping patterns in our function definition. If several equations of a function definition match a particular function application, Curry takes all of them, not only the first one, as Haskell does.
element :: [el] -> el
element (el : _) = el
element (_ : els) = element els
Now we can enter
element "Hello!"
at the KiCS2 prompt, and the system outputs six different results.
Logic programming
We have already seen how to combine functional and logic programming with Curry. Now we want to do pure logic programming. This means that we only want to search for variable assignments, but are not interested in expression results. If you are not interested in results, you typically use a result type with only a single value. Curry provides the type Success
with the single value success
for doing logic programming.
Let us write some example code about routes between countries. We first introduce a type of some European and American countries.
data Country = Canada
| Estonia
| Germany
| Latvia
| Lithuania
| Mexico
| Poland
| Russia
| USA
Now we want to define a relation called borders
that tells us which country borders which other country. We implement this relation as a function of type
Country -> Country -> Success
that has the trivial result success
if the first country borders the second one, and has no result otherwise.
Note that this approach of implementing a relation is different from what we do in functional programming. In functional programming, we use Bool
as the result type and signal falsity by the result False
. In Curry, however, we signal falsity by the absence of a result.
Our borders
relation only relates countries with those neighbouring countries whose names come later in alphabetical order. We will soon compute the symmetric closure of borders
to also get the opposite relationships.
borders :: Country -> Country -> Success
Canada `borders` USA = success
Estonia `borders` Latvia = success
Estonia `borders` Russia = success
Germany `borders` Poland = success
Latvia `borders` Lithuania = success
Latvia `borders` Russia = success
Lithuania `borders` Poland = success
Mexico `borders` USA = success
Now we want to define a relation isConnected
that tells whether two countries can be reached from each other via a land route. Clearly, isConnected
is the equivalence relation that is generated by borders
. In Prolog, we would write clauses that directly express this relationship between borders
and isConnected
. In Curry, on the other hand, we can write a function that generates an equivalence relation from any given relation and therefore does not only work with borders
.
We first define a type alias Relation
for the sake of convenience.
type Relation val = val -> val -> Success
Now we define what reflexive, symmetric, and transitive closures are.
reflClosure :: Relation val -> Relation val
reflClosure rel val1 val2 = rel val1 val2
reflClosure rel val val = success
symClosure :: Relation val -> Relation val
symClosure rel val1 val2 = rel val1 val2
symClosure rel val2 val1 = rel val1 val2
transClosure :: Relation val -> Relation val
transClosure rel val1 val2 = rel val1 val2
transClosure rel val1 val3 = rel val1 val2 &
transClosure rel val2 val3
where val2 free
The operator &
used in the definition of transClosure
has type
Success -> Success -> Success
and denotes conjunction.
We define the function for generating equivalence relations as a composition of the above closure operators. Note that it is crucial that the transitive closure operator is applied after the symmetric closure operator, since the symmetric closure of a transitive relation is not necessarily transitive.
equivalence :: Relation val -> Relation val
equivalence = reflClosure . transClosure . symClosure
The implementation of isConnected
is now trivial.
isConnected :: Country -> Country -> Success
isConnected = equivalence borders
Now we let KiCS2 compute which countries I can reach from Estonia without a ship or plane. We do so by entering
Estonia `isConnected` country where country free
at the prompt.
We can also implement a nondeterministic function that turns a country into the countries connected to it. For this, we use a guard that is of type Success
. Such a guard succeeds if it has a result at all, which can only be success
, of course.
connected :: Country -> Country
connected country1
| country1 `isConnected` country2 = country2
where country2 free
Equational constraints
Curry has a predefined operator
=:= :: val -> val -> Success
that stands for equality.
We can use this operator, for example, to define a nondeterministic function that yields the grandchildren of a given person. Again, we keep things simple by only considering relationships that solely go via fathers.
grandchild :: Person -> Person
grandchild person
| grandfather grandkid =:= person = grandkid
where grandkid free
Note that grandchild
is the inverse of grandfather
.
Functional patterns
Functional patterns are a language extension that allows us to use ordinary functions in patterns, not just data constructors. Functional patterns are implemented by KiCS2.
Let us look at an example again. We want to define a function split
that nondeterministically splits a list into two parts.1 Without functional patterns, we can implement splitting as follows.
split' :: [el] -> ([el],[el])
split' list | front ++ rear =:= list = (front,rear)
where front, rear free
With functional patterns, we can implement splitting in a much simpler way.
split :: [el] -> ([el],[el])
split (front ++ rear) = (front,rear)
As a second example, let us define a function sublist
that yields the sublists of a given list.
sublist :: [el] -> [el]
sublist (_ ++ sub ++ _) = sub
Inverting functions
In the grandchild
example, we showed how we can define the inverse of a particular function. We can go further and implement a generic function inversion operator.
inverse :: (val -> val') -> (val' -> val)
inverse fun val' | fun val =:= val' = val where val free
With this operator, we could also implement grandchild
as inverse grandfather
.
Inverting functions can make our lives a lot easier. Consider the example of parsing. A parser takes a string and returns a syntax tree. Writing a parser directly is a non-trivial task. However, generating a string from a syntax tree is just a simple functional programming exercise. So we can implement a parser in a simple way by writing a converter from syntax trees to strings and inverting it.
We show this for the language of all arithmetic expressions that can be built from addition, multiplication, and integer constants. We first define types for representing abstract syntax trees. These types resemble a grammar that takes precedence into account.
type Expr = Sum
data Sum = Sum Product [Product]
data Product = Product Atom [Atom]
data Atom = Num Int | Para Sum
Now we implement the conversion from abstract syntax trees to strings.
toString :: Expr -> String
toString = sumToString
sumToString :: Sum -> String
sumToString (Sum product products)
= productToString product ++
concatMap ((" + " ++) . productToString) products
productToString :: Product -> String
productToString (Product atom atoms)
= atomToString atom ++
concatMap ((" * " ++) . atomToString) atoms
atomToString :: Atom -> String
atomToString (Num num) = show num
atomToString (Para sum) = "(" ++ sumToString sum ++ ")"
Implementing the parser is now extremely simple.
parse :: String -> Expr
parse = inverse toString
KiCS2 uses a depth-first search strategy by default. However, our parser implementation does not work with depth-first search. So we switch to breadth-first search by entering
:set bfs
at the KiCS2 prompt. Now we can try out the parser by entering
parse "2 * (3 + 4)"
.
-
Note that our
split
function is not the same as thesplit
function in Curry’sList
module.↩
Pingback: A taste of Curry | Theory Lunch
Wait … Isn’t this definition going to trigger some non-deterministic behaviour thus risking testing
rel val1 val2
and failing ifrel
is not reflexive?Or, because failure corresponds to partiality, it will fall back to the next branch?
LikeLike
In fact, this definition introduces non-determinism. If the second and third argument of
reflClosure
are the same, both equations ofreflClosure
are considered. What exactly happens depends on the search strategy.With depth-first search, Curry first evaluates
rel val1 val2
from the first equation, and if this terminates, it takes thesuccess
from the second equation. So ifrel val1 val2
terminates withsuccess
, thenreflClosure
yields the valuesuccess
twice; ifrel val1 val2
terminates with failure (meaning no result), thenreflClosure
yieldssuccess
once. Only ifrel val1 val2
does not terminate,reflClosure
does not terminate and yields no result.With breadth-first search, both equations are processed concurrently. So the
success
from the second equation will always be returned. Whether there will be anothersuccess
and whetherreflClosure
will terminate depends on the behavior ofrel val1 val2
.Note that in the declarative semantics of Curry, there is nothing like falling back to the second equation, as there is in Haskell. If multiple equations of a function definition match, then all these equations are taken, and all are treated equally. It is just a specific search strategy, like depth-first search, that can make program execution not conform to this ideal semantics.
LikeLike
Contrary to what I originally thought, functional patterns are also implemented by the Curry systems PAKCS and MCC.
LikeLike
I just tried the equivalence thing on PAKCS 2.0.0. When executing
Estonia `isConnected` country where country free
, it gets stuck in infinite recursion. It’s kind of disappointing, to be fair. I was fascinated by the power and elegance of those code samples, but it turned out that the language itself is not even properly implemented. And it’s already been like 5 years since you’ve made the post.LikeLike
Just tried it in KiCS2 2.0.0. Same outcome.
LikeLike
This is strange. When I prepared this code, I tested it with the then current version of KiCS2, and it worked just fine.
Unfortunately, I cannot help you with solving this problem, as I am not a Curry user (I just looked a bit at Curry again around the time I wrote the above code). I think it would be good if you would contact the KiCS developers.
LikeLike
Pingback: MIU in Curry « Wolfgang Jeltsch