Curry (programming language): Difference between revisions

Revision as of 17:22, 29 June 2023

Latest revision as of 08:50, 25 August 2025

(26 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Programming language}}

{{About|the programming language Curry (named in honour of a mathematician and logician)|the mathematician and logician|Haskell Curry|the computer science technique|Currying}}

{{Primary sources|date=July 2019}}

{{Infobox programming language

|name = Curry

|logo =

|paradigm = [[functionalFunctional programming|functional]], [[logicLogic programming|logic]], non-strict, modular

|year =

|designer = Michael Hanus, Sergio Antoy, et al.

|developer = [[Kiel University]]<br/>[[Ludwig Maximilian University of Munich]]<br/>[[University of Münster]]<br/>[[Portland State University]]<br/>[[Complutense University of Madrid]]<br/>[[Technical University of Madrid]]

|developer =

|released = {{Start date and age|1995}}

|latest_release_version = {{wikidata|property|reference|edit|P348|P548=Q2804309}}

|latest_release_datelatest release version = <small>({{wikidata|qualifierproperty|reference|edit|P348|P577P548=Q2804309}})</small>

|latest release date = ({{wikidata|qualifier|P348|P577}})

|latest_test_version =

|latest preview version =

|latest_test_date =

|latest preview date =

|typing = [[static typing|static]], [[strong typing|strong]], [[type inference|inferred]]

|typing = [[static typing|static]], [[Strong and weak typing|strong]], [[type inference|inferred]]

|implementations = [https://www.informatik.uni-kiel.de/~pakcs PAKCS] (with [[Prolog (programming language)|Prolog]] as the target), [http://danae.uni-muenster.de/curry/ mcc] (with [[C (programming language)|C]] as the target), [http://www-ps.informatik.uni-kiel.de/kics2/ KiCS2] (with [[Haskell (programming language)|Haskell]] as the target)

|platform = [[x86-64]]

|operating system = [[Cross-platform software|Cross-platform]]: [[Linux]]

|license = [[BSD licenses|BSD]] 3-clause

|website = {{URL|www.curry-lang.org}}

|implementations = [https://www.curry-lang.org/pakcs PAKCS] ([[Prolog]] target), [http://danae.uni-muenster.de/curry/ mcc] ([[C (programming language)|C]] target), [https://www.curry-lang.org/kics2/ KiCS2] ([[Haskell]] target)

|dialects =

|influenced by = [[Haskell]], [[Prolog]]

|influenced =

|influenced by = [[Haskell (programming language)|Haskell]] and [[Prolog (programming language)|Prolog]]

|operating_system = portable

|license =

|website = [https://curry.pages.ps.informatik.uni-kiel.de/curry-lang.org/ Curry]

}}

'''Curry''' is a [[declarative programming]] language, an implementation of the [[functional logic programming]] paradigm,<ref>{{cite web |editor-last=Hanus |editor-first=Michael |title=Curry: A Truly Integrated Functional Logic Language |url=https://www.curry-lang.org/documentation/report/}}</ref><ref>{{cite journal |last1=Sergio |first1=Antoy |last2=Hanus |first2=Michael |year=2010 |title=Functional Logic Programming |journal=Communications of the ACM |volume=53 |issue=4 |pages=74–85 |publisher=ACM |doi=10.1145/1721654.1721675 |s2cid=14578759}}</ref><ref>{{cite book |last=Hanus |first=Michael |title=Programming Logics - Essays in Memory of Harald Ganzinger |chapter=Functional Logic Programming: From Theory to Curry |series=Lecture Notes in Computer Science |year=2013 |doi=10.1007/978-3-642-37651-1_6 |volume=7797 |pages=123-168 |isbn=978-3-642-37650-4}}</ref> and based on the [[Haskell]] language. It merges elements of functional and logic programming,<ref name="Curry and Curl programming languages">

'''Curry'''<ref>{{cite web

{{cite web |title=Curry experimental programming language |url=https://www.mvps.net/docs/curry-and-curl-programming-languages |website=MVPS.net |access-date=2 September 2021}}</ref> including [[constraint programming]] integration.

| editor = Michael Hanus

| title = Curry: A Truly Integrated Functional Logic Language

| url = http://www.curry-lang.org/

}}</ref> is an experimental [[functional logic programming]] language,<ref>{{cite journal

| author = Sergio Antoy and Michael Hanus

| title = Functional Logic Programming

| journal = Communications of the ACM

| volume = 53

| issue = 4

| pages = 74–85

| publisher = ACM

| year = 2010

| doi = 10.1145/1721654.1721675

| s2cid = 14578759

}}</ref> based on the [[Haskell (programming language)|Haskell]] language. It merges elements of functional and logic programming,<ref name="Curry and Curl programming languages">{{cite web |title=Curry experimental programming language |url=https://www.mvps.net/docs/curry-and-curl-programming-languages |website=MVPS.net |access-date=2 September 2021}}</ref> including [[constraint programming]] integration.

It is nearly a superset of Haskell but does not support all language extensions of Haskell. In contrast to Haskell, Curry has built-in support for non-deterministic computations involving search.

It is nearly a superset of Haskell, lacking support mostly for overloading using [[Polymorphism (computer science)#Subtyping|type classes]], which some implementations provide anyway as a language extension, such as the Münster Curry Compiler.<ref>[http://danae.uni-muenster.de/curry/ The Münster Curry Compiler]</ref>

==Foundations of functional logic programming==

Line 57 ⟶ 43:

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

In this case, both derivations lead to the same result, a property known as [[Confluence (term rewriting)|confluence]]. This follows from a fundamental property of pure functional languages, termed [[referential transparency]]: the value of a computed result does not depend on the order or time of evaluation, due to the absence of [[Side effect (computer science)|side effects]]. This simplifies the reasoning about, and maintenance ofmaintaining, pure functional programs.

As many functional languages like [[haskell (programming language)|Haskell]] do, Curry supports the definition of [[algebraic data type]]s by enumerating their constructors. For instance, the type of Boolean values consists of the constructors {{Mono|True}} and {{Mono|False}} that are declared as follows:

<syntaxhighlight lang="haskell">

data Bool = True | False

Line 72 ⟶ 58:

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

More complex [[data structuresstructure]]s can be obtained by [[recursive data type]]s. For instance, a list of elements, where the type of elements is arbitrary (denoted by

the type variable {{Mono|a}}), is either the empty list “{{Mono|[]}}” or the non-empty list “{{Mono|x:xs}}” consisting of a first element {{Mono|x}} and a list {{Mono|xs}}:

<syntaxhighlight lang="haskell">

Line 92 ⟶ 78:

===Narrowing===

Narrowing is a mechanism whereby a variable is [[name binding|bound]] to a value selected from among alternatives imposed by constraints. Each possible value is tried in some order, with the remainder of the program invoked in each case to determine the validity of the binding. Narrowing is an extension of logic programming, in that it performs a similar search, but can actually generate values as part of the search rather than just being limited to testing them.

Narrowing is useful because it allows a function to be treated as a relation: its value can be computed "in both directions". The Curry examples of the previous section illustrate this.

Narrowing is a mechanism whereby a variable is [[name binding|bound]] to a value selected from among alternatives imposed by constraints. Each possible value is tried in some order, with the remainder of the program invoked in each case to determine the validity of the binding. Narrowing is an extension of logic programming, in that it performs a similar search, but can actually generate values as part of the search rather than just being limited to testing them.

As noted in the prior section, narrowing can be thought of as reduction on a program term graph, and there are often many different ways (''strategies'') to reduce a given term graph. Antoy et al.<ref>{{cite journal

Narrowing is useful because it allows a function to be treated as a relation: its value can be computed "in both directions". The Curry examples of the previous section illustrate this.

|last1=Sergio |first1=Antoy |last2=Echahed |first2=Rachid |last3=Hanus |first3=Michael

|title=A Needed Narrowing Strategy

As noted in the previous section, narrowing can be thought of as reduction on a program term graph, and there are often many different ways (''strategies'') to reduce a given term graph. Antoy et al.<ref>{{cite journal

|journal=Journal of the ACM

| author = Sergio Antoy, Rachid Echahed and Michael Hanus

|volume=47

| title = A Needed Narrowing Strategy

|issue=4

| journal = Journal of the ACM

|pages=776–822

| volume = 47

|publisher=ACM

| issue = 4

|year=2000

| pages = 776–822

|issn=0004-5411

| publisher = ACM

|doi=10.1145/347476.347484

| year = 2007

| s2cid=47275506

| issn = 0004-5411

|hdl=11858/00-001M-0000-0014-B494-9

| doi = 10.1145/347476.347484

|hdl-access=free

| s2cid = 47275506

}}</ref> proved in the 1990s that a particular narrowing strategy, ''needed narrowing'', is optimal in the sense of doing a number of reductions to get to a "normal form" corresponding to a solution that is minimal among sound and complete strategies. Needed narrowing corresponds to a lazy strategy, in contrast to the [[SLD resolution|SLD-resolution]] strategy of [[Prolog]].

===Functional patterns===

The rule defining {{Mono|last}} shown above expresses the fact that the actual argument must match the result of narrowing the expression {{Mono|ys++[e]}}. Curry can express this property also in the following more concise way:

<syntaxhighlight lang="haskell">

last (ys++[e]) = e

</syntaxhighlight>

Haskell does not allow such a declaration since the pattern in the left-hand side contains a defined function ({{Mono|++}}). Such a pattern is also called ''functional pattern''.<ref>{{cite journalbook |doilast1=10.1007/11680093_2Antoy |first1=Sergio |last2=Hanus |first2=Michael |title=Logic Based Program Synthesis and Transformation |chapter=Declarative Programming with Function Patterns | year=2006 | journalseries=Lecture Notes in Computer Science |year=2006 |doi=10.1007/11680093_2 |volume=3901 | pages=6–22 | author=Antoy Sergio, Hanus Michael| isbn=978-3-540-32654-0 }}</ref> Functional patterns are enabled by the combined functional and logic features of Curry and support concise definitions of tasks requiring deep pattern matching in hierarchical data structures.

===Non-determinism===

Since Curry is able to solve equations containing function calls with unknown values, its execution mechanism is based on non-deterministic computations, similarly to logic programming. This mechanism supports also the definition of ''non-deterministic operations'', i.e., operations that delivers more than one result for a given input. The archetype of non-deterministic operations is the predefined infix operation {{Mono|?}}, called ''choice'' operator, that returns one of its arguments. This operator is defined by the following rules:

Line 126 ⟶ 111:

x ? y = y

Thus, the evaluation of the expression {{Mono|0 ? 1}} returns {{Mono|0}} as well as {{Mono|1}}. Computing with non-deterministic operations and computing with free variables by narrowing has the same expressive power.<ref>{{cite journalbook |doilast1=10.1007/11799573_9Antoy |first1=Sergio |last2=Hanus |first2=Michael |title=Logic Programming |chapter=Overlapping Rules and Logic Variables in Functional Logic Programs | year=2006 | journalseries=Lecture Notes in Computer Science |year=2006 |doi=10.1007/11799573_9 |volume=4079 | pages=87–101 | author=Antoy Sergio, Hanus Michael| isbn=978-3-540-36635-5 }}</ref>

The rules defining {{Mono|?}} show an important feature of Curry: all rules are tried in order to evaluate some operation. Hence, one can define by

Line 141 ⟶ 126:

===Strategies===

Due to the absence of side effects, a functional logic program can be executed with different strategies. To evaluate expressions, Curry uses a variant of the ''needed narrowing'' strategy which combines [[lazy evaluation]] with non-deterministic search strategies. In contrast to Prolog, which uses backtracking to search for solutions, Curry does not fix a particular search strategy. Hence, there are implementations of Curry, like [https://www.curry-lang.org/kics2/ KiCS2], where the user can easily select a search strategy, like [[depth-first search]] (backtracking), [[breadth-first search]], iterative deepening, or parallel search.

==Implementations and programming tools==

There are various implementations of Curry available. The most prominent representatives are the Portland Aachen Kiel Curry System [https://www.curry-lang.org/pakcs/ PAKCS] which compiles Curry programs into [[Prolog]], the Kiel Curry System [https://www.curry-lang.org/kics2/ KiCS2] which compiles Curry programs into [[Haskell]], the Münster Curry Compiler [http://danae.uni-muenster.de/curry/ MCC], and [https://www.curry-lang.org/curry2go/ Curry2Go] which compiles Curry programs into [[Go (programming language)|Go]] programs and supports fair parallel search by mapping non-deterministic evaluations into [[light-weight process]]es (goroutines).

To support programming in Curry, there is a collection of [https://cpm.curry-lang.org/ Curry software packages], a [https://cpm.curry-lang.org/currygle/ Curry API search engine], a [https://github.com/fwcd/curry-language-server Curry language server] providing [[integrated development environment|IDE]] support, e.g., in [[Visual Studio Code]], as well as various program documentation and analysis tools.

==Discussion and further reading==

[[John Alan Robinson]] discussed in his invited CL2000 paper<ref>{{cite book |last=Robinson |first=John Alan |title=First International Conference on Computational Logic (CL 2000) |chapter=Computational Logic: Memories of the Past and Challenges for the Future |series=Lecture Notes in Computer Science |year=2000 |doi=10.1007/3-540-44957-4_1 |volume=1861 |pages=1-24 |isbn=978-3-540-67797-0}}</ref> the integration of functional programming with logic programming where he wrote: "It is inexplicable that the two idioms have been kept apart for so long within the computational logic repertory. We need a single programming language in which both kinds of programming are possible and can be used in combination with each other." He surveyed different attempts and concluded that Curry is the "most promising one".

The textbook <ref>{{cite book |last1=Louden |first1=Kenneth C. |last2=Lambert | first2=Kenneth A. |title=Programming Languages - Principles and Practice |publisher=Cengage Learning |year=2012 |isbn=978-1-111-57763-6}}</ref> about principles and practice of programming languages contains a chapter on programming in Curry.

Due to the absence of side effects, a functional logic program can be executed with different strategies. To evaluate expressions, Curry uses a variant of the ''needed narrowing'' strategy which combines [[lazy evaluation]] with non-deterministic search strategies. In contrast to Prolog, which uses backtracking to search for solutions, Curry does not fix a particular search strategy. Hence, there are implementations of Curry, like [http://www-ps.informatik.uni-kiel.de/kics2/ KiCS2], where the user can easily select a search strategy, like [[depth-first search]] (backtracking), [[breadth-first search]], iterative deepening, or parallel search.

==References==

{{reflistReflist}}

==External links==

*[http{{Official website|https://www.curry-lang.org/ Curry] - The home page of Curry}}

*[httphttps://smap.informatik.unicurry-kiellang.deorg/ Smap] - A web-based execution environment for Curry and Haskell with various example programs

*[https://cpm.curry-lang.org/ Curry packages] - A collection of software packages for Curry

*[http://danae.uni-muenster.de/curry/ MCC] - The Münster Curry Compiler, which uses [[C (programming language)|C]] as the target

*[http://www.informatikdanae.uni-kielmuenster.de/~pakcscurry/ PAKCSMCC] A- majorThe Münster Curry implementation with a WWW interfaceCompiler, which usestargets [[PrologC (programming language)|PrologC]] as the target

*[httphttps://www-ps.informatik.unicurry-kiellang.deorg/kics2pakcs/ KiCS2PAKCS] A major Curry implementation, which usestargets [[Haskell (programming language)|HaskellProlog]] as the target

*[https://www-ps.informatik.unicurry-kiellang.deorg/currywikikics2/documentation/mailing KiCS2] A Curry Mailingimplementation, targets List[[Haskell]]

*[https://www.curry-lang.org/curry2go/ Curry2Go] A Curry implementation, targets [[Go (programming language)|Go]], and supports fair parallel search

*[http://www.informatik.uni-kiel.de/~mh Michael Hanus's home page]

*[https://github.com/curry-language/ GitHub repositories] with Curry implementations and tools

* ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.148.524 Purely Functional Lazy Non-deterministic Programming]'' (Fischer, Kiselyov, Shan, 2009), ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.4578 Transforming Functional Logic Programs into Monadic Functional Programs]'' (Braßel, Fischer, Hanus, Reck, 2010) on modeling lazy non-deterministic (logic) programming (like in Curry) in a purely functional language ([[Haskell (programming language)|Haskell]]); such approach might give the programmer more flexibility in the control over the strategies that—in the case of Curry—are built-in.

*[https://curry-lang.org/various/mailinglist/ Curry Mailing List]

*[http://www.michaelhanus.de/ Michael Hanus's home page]

* ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.148.524 Purely Functional Lazy Non-deterministic Programming]'' (Fischer, Kiselyov, Shan, 2009), ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.157.4578 Transforming Functional Logic Programs into Monadic Functional Programs]'' (Braßel, Fischer, Hanus, Reck, 2010) on modeling lazy non-deterministic (logic) programming (like in Curry) in a purely functional language ([[Haskell]]); such approach might give the programmer more flexibility in the control over the strategies that—in the case of Curry—are built-in.

{{Haskell programming}}

{{Haskell Curry}}

{{Authority control}}

[[Category:High-level programming languages]]

[[Category:Concurrent programming languages]]

[[Category:Experimental programming languages]]

[[Category:Functional logic programming languages]]

[[Category:Haskell programming language family]]

[[Category:Programming languages created in the 1990s1995]]

[[Category:Nondeterministic programming languages]]

[[Category:Literate programming]]

[[Category:Academic programming languages]]

[[Category:Software using the BSD license]]

<!-- Hidden categories below -->

[[Category:Articles with example Haskell code]]

[[Category:Statically typed programming languages]]