Version
2.1
Language
Report
Preface
|
|
Introduction
Clean is a practical applicable general-purpose lazy pure functional programming language suited for the development of real world applications.
Clean has many features among which some very special ones.
Functional languages are usually implemented using graph-rewriting techniques. Clean has explicit graph rewriting semantics; one can explicitly define the sharing of structures (cyclic structures as well) in the language (Barendregt et al., 1987; Sleep et al., 1993, Eekelen et al., 1997). This provides a better framework for controlling the time space behavior of functional programs.
Of particular importance for practical use is Clean’s Uniqueness Type System (Barendsen and Smetsers, 1993a) enabling the incorporation of destructive updates of arbitrary objects within a pure functional framework and the creation of direct interfaces with the outside world.
Clean’s “unique” features have made it possible to predefine (in Clean) a sophisticated and efficient I/O library (Achten and Plasmeijer, 1992 & 1995). The Clean Object I/O library enables a Clean programmer to specify interactive window based I/O applications on a very high level of abstraction. One can define callback functions and I/O components with arbitrary local states thus providing an object-oriented style of programming (Achten, 1996; Achten and Plasmeijer, 1997). The library forms a platform independent interface to window-based systems: one can port window based I/O applications written in Clean to different platforms (we support Mac and PC) without modification of source code.
Although Clean is by default a lazy language one can smoothly turn it into a strict language to obtain optimal time/space behavior: functions can be defined lazy as well as (partially) strict in their arguments; any (recursive) data structure can be defined lazy as well as (partially) strict in any of its arguments.
The rich type system of Clean 1.3 (offering high-order types, polymorph types, type classes, uniqueness types, existentially quantified types, algebraic types, abstract types, synonym types, record types, arrays, lists) is extended with multi parameter type constructor classes and universally quantified types (currently limited to rank 2, rank n is in preparation). Furthermore, arrays and lists are better integrated in the language. Strict, spine-strict, unboxed and overloaded lists are predefined in the language.
Clean now offers a hybrid type system with both static and dynamic typing. An object (expression) of static type can be changed into an object of dynamic type (a “Dynamic”) and backwards. One can read a Dynamic written by another Clean program with one function call. A Dynamic can contain data as well as (unevaluated) functions. This means that one can very easy transfer data as well as code (!) from one Clean application to another in a type safe manner enabling mobile code and persistent storage of an expression. This technique involves just-in-time code generation, dynamic linking and dynamic type unification.
Clean offers support for generic programming using an extension of the class overloading mechanism. One can define functions like equality, map, foldr and the like in a generic way such that these functions are available for any (user defined) data structure. The generic functions are very flexible since they not only work on types of kind star but also on higher order kinds.
Clean (Brus et al., 1987; Nöcker et al., 1991; Plasmeijer and Van Eekelen, 1993) is not only well known for its many features but also for its fast compiler producing very efficient code (Smetsers et al., 1991). The new Clean 2.0 compiler is written in Clean. The Clean compiler is one of the fastest in the world and it produces very good code. For example, the compiler can compile itself from scratch within a minute.
The Clean 2.0 system includes lots of tools and libraries, all written in Clean of course. Included is an IDE (Integrated Development Environment), a dedicated text editor, a project manager, a code generator generating native code (the only piece of software written in C), a static linker, a dynamic linker, a proof system (Sparkle), a test system (GAST), a heap profiler, a time profiler, and lots of libraries.
People already familiar with other functional programming languages (such as Haskell; (Hudak et al., 1992), Gofer/Hugs (Jones, 1993), Miranda (Turner, 1985) and SML (Harper et al., 1986)) will have no difficulty to program in Clean. We hope that you will enjoy Clean’s rich collection of features, Clean’s compilation speed and the quality of the produced code (we generate native code for all platforms we support). Clean runs on a PC (Windows 2000, ‘98, ’95, WindowsNT). There are also versions running on the Mac and Linux.
Research on Clean started in 1984 (the Dutch Parallel Machine Project) in which we had to good idea to focuss on compilation techniques for classical computer architectures. Many new concepts came out of the research of the Clean team (see below). These ideas are not only incorporated in our own system, many of them have also been adopted by other languages like Haskell and Mercury.
More Information on Clean
A tutorial
teaching how to program in Clean can be found on our web
pages.
See http://wiki.clean.cs.ru.nl/Functional_Programming_in_Clean.
Information about the libraries (including the I/O library) that are available for Clean can also be found on the web, surf to http://wiki.clean.cs.ru.nl/Libraries.
There is a manual teaching the use of the Object I/O library. It includes many examples showing you how to write interactive window based programs.
See http://clean.cs.ru.nl/download/supported/ObjectIO.1.2/doc/tutorial.pdf.
The basic concepts behind Clean (albeit of one of the very first versions, namely Clean 0.8) as well as an explanation of the basic implementation techniques used can be found in Plasmeijer and Van Eekelen (Adisson-Wesley, 1993).
The book is out of print, but copies can found on http://wiki.clean.cs.ru.nl/Functional_Programming_and_Parallel_Graph_Rewriting
There are many papers on the concepts introduced by the Clean group (such as term graph rewriting (Barendregt et al., 1987), lazy copying (van Eekelen et al., 1991), abstract reduction (Nöcker, 1993), uniqueness typing (Barendsen and Smetsers, 1993, 1996), Clean’s I/O concept (Achten, 1996 & 1997), Lazy Copying for Concurrent Clean (Kesseler, 1991 & 1996), Type dependent Functions for Dynamics (Pil, 1999), I/O of Dynamics (Vervoort, 2001), a Typed Operating System (van Weelden, 2001). For the most recent information on papers (http://wiki.clean.cs.ru.nl/Publications) and general information about Clean (http://clean.cs.ru.nl) please check our web pages.
About this Language Report
In this report the syntax and semantics of Clean version 2.0 are explained. We always give a motivation why we have included a certain feature. Although the report is not intended as introduction into the language, we did our best to make it as readable as possible. Nevertheless, one sometimes has to work through several sections spread all over the report. We have included links where possible to support browsing through the manual.
At several places in this report context free syntax fragments of Clean are given. We sometimes repeat fragments that are also given elsewhere just to make the description clearer (e.g. in the uniqueness typing chapter we repeat parts of the syntax for the classical types). We hope that this is not confusing. The complete collection of context free grammar rules is summarized in Appendix A.
Some Remarks on the Clean Syntax
The syntax of Clean is similar to the one used in most other modern functional languages. However, there are a couple of small syntactic differences we want to point out here for people who don’t like to read language reports.
In Clean the arity of a function is reflected in its type. When a function is defined its uncurried type is specified! To avoid any confusion we want to explicitly state here that in Clean there is no restriction whatsoever on the curried use of functions. However, we don’t feel a need to express this in every type. Actually, the way we express types of functions more clearly reflects the way curried functions are internally treated.
E.g., the standard map function (arity 2) is specified in Clean as follows:
map::(a -> b) [a] -> [b]
map f [] = []
map f [x:xs] = [f x:map f xs]
Each predefined structure such as a list, a tuple, a record or array has its own kind of brackets: lazy lists are always denotated with square brackets […], strict lists are denotated by [! …], spine strict lists by [… !], overloaded lists by [|… ] , unboxed lists by [#…]. For tuples the usual parentheses are used (…,…), curly braces are used for records (indexed by field name) as well as for arrays (indexed by number).
In types funny symbols can appear like., u:, *, ! which can be ignored and left out if one is not interested in uniqueness typing or strictness.
There are only a few keywords in Clean leading to a heavily overloaded use of : and = symbols:
function::argstype -> restype // type specification of a function
function pattern
| guard = rhs // definition of a function
selector = graph // definition of a constant/CAF/graph
function args :== rhs // definition of a macro
::Type args = typedef // an algebraic data type definition
::Type args :== typedef // a type synonym definition
::Type args // an abstract type definition
As is common in modern functional languages, there is a layout rule in Clean (see 2.3). For reasons of portability it is assumed that a tab space is set to 4 white spaces and that a non-proportional font is used.
Function definition in Clean making use of the layout rule.
primes:: [Int]
primes = sieve [2..]
where
sieve:: [Int] -> [Int]
sieve [pr:r] = [pr:sieve (filter pr r)]
filter:: Int [Int] -> [Int]
filter pr [n:r]
| n mod pr == 0 = filter pr r
| otherwise = [n:filter pr r]
Notational Conventions Used in this Report
The following notational conventions are used in this report. Text is printed in Microsoft Sans Serif 9pts,
the context free syntax descriptions are given in Microsoft Sans Serif 9pts,
examples of Clean programs are given in Courier New 9pts,
Semantic restrictions are always given in a bulleted list-of-points.
When these restrictions are not obeyed they will almost always result in a
compile-time error. In very few cases the restrictions can only be detected
at run-time (array index out-of-range, partial function called outside the domain).
The following notational conventions are used in the context-free syntax descriptions:
|
[notion] |
means that the presence of notion is optional |
|
{notion} |
means that notion can occur zero or more times |
|
{notion}+ |
means that notion occurs at least once |
|
{notion}-lis |
means one or more occurrences of notion separated by comma’s |
|
terminals |
are printed in 9 pts courier |
|
keywords |
are printed in 9 pts courier |
|
terminals |
that can be left out in layout mode are printed in 9 pts courier |
|
~ |
is used for concatenation of notions |
|
{notion}/~str |
means the longest expression not containing the string str |
All Clean examples given in this report assume that the layout dependent mode has been chosen which means that redundant semi-colons and curly braces are left out (see 2.3.3).
How to Obtain Clean
Clean and the Integrated Development Environment (IDE) can be used free of charge. They can be obtained
• via World Wide Web (http://clean.cs.ru.nl) or
• via ftp (ftp://ftp.cs.ru.nl in directory pub/Clean).
Clean is available on several platforms. Please check our WWW-pages regularly to see the latest news. New versions of Clean in general appear first on Windows and later on Mac systems. Versions for Linux platforms appear less frequently.
Current State of the Clean System
Release 2.1 (November 2002).
Compared with the previous version the following changes have been made.
Experimental features of the previous version, such as dynamics (see Chapter 8), generics (see
Chapter 7) and strict-lists (see 4.2) have
been improved and further incorporated in the language.
Many bugs, most of which appeared in the new features, have been
removed.
The quality of the generated code has been improved.
Release 2.0 (November 2001).
There are many changes compared to the previous release (Clean 1.3.x). We have added many new features in Clean 2.0 we hope you will like.
Clean 2.0 has multi-parameter type constructor classes. See Section 6.4.
Clean 2.0 has universally quantified data types and functions (rank 2).
See Section 3.7.4 and 5.1.4.
The explicit import mechanism has been refined. One can now more
precisely address what to import and what not. See 2.5.1.
Cyclic depedencies between definition modules are allowed. This
makes it easier to define implementations modules that share definitions. See 2.5.1.
Definitions in a definition module need not to be repeated in the
corresponding implementation module anymore. See
2.4.
Due to multi-parameter type constructor classes a better
incorporation of the type Array could be made. See 4.4.
Clean 2.0 offers an hybrid type system: one can have statically and
dynamically typed objects (Dynamics). A statically typed expression can
be changed into a dynamically typed one and backwards. The type of a Dynamic can be
inspected via a pattern match, one can ensure that Dynamics fit together by using
run-time type unification, one can store a Dynamic into a file with one function
call or read a Dynamic stored by another Clean application. Dynamics can be
used to store and retrieve information without the need for writing parsers, it
can be used to exchange data and code (!) between applications in a type safe
manner. Dynamics make it easy to create mobile code, create plug-ins or create a
persistent store. The Clean run-time system has been
extended to support dynamic type checking, dynamic type unification, lazy
dynamic linking and just-in-time code generation (See
Chapter 8).
There is special syntax and support for strict and unboxed lists.
One can easily change from lazy to strict and backwards. Overloaded functions
can be defined which work for any list (lazy, strict or unboxed). See 4.2.One can write functions like ==, map, foldr in a generic
way. The generic functions one can define can work on higher order
kinds. With kind indexed functions one can indicated which kind is actually
mend (see Chapter 7). A generic definition
can be specialized for a certain concrete type.
The Clean system has been changed and extended: a
new version of the Clean IDE, a new version of the
run-time-system, and a dynamic linker is included. See
8.3.
Clean 2.0 comes with an integrated proof system (Sparkle), all written in
Clean of course. See http://www.cs.kun.nl/Sparkle.
Clean 2.0 is open source. All source code will be made available on the
net.
We have also removed things:
We do not longer support annotations for concurrent evaluations ({P}
and {I} annotations. However, we are working on a library that will support
distributed evaluation of Clean expressions using
Dynamics (see Van Weelden and Plasmeijer, 2002).
There is no strict let-before expression (let!) anymore in Clean 2.x. You still can enforce strict evaluation using the strict hash
let (#!).
One cannot specify default instances anymore that could be used to
disambiguate possible ambiguous internal overloading. Disambiguating can be
done by explicitely specifying the required type.
There is also some bad news:
Due to all these changes Clean 2.0 is not
upwards compatible with Clean 1.3.x. Many things are
the same but there are small differences as well. So, one has to put some
effort in porting a Clean 1.3.x application to Clean 2.0. The most important syntactical differences are described
below. Note that we do no longer support Clean 1.3.
The Clean 1.3 compiler is written in C. The Clean 2.0 compiler has been rewritten from scratch in Clean. The internal structure of the new compiler is a better than the old
one, but the new compiler has become a bit slower than the previous C version as
well. Large programs will take about 1.7 times as much time to compile (which
is still pretty impressive for a lazy functional language).
Syntactic differences between Clean 1.3 and Clean 2.0
Clean 2.x is not downward compatible with Clean 1.3.x. Probably you have to change your 1.3.x sources to get them through the Clean 2.x compiler.
Differences in Expression Syntax
There is no strict let-before expression (let!) anymore in Clean 2.x. You still can enforce strict evaluation using the strict hash let (#!).
Differences in the Type System
For multiparameter type classes a small change in the syntax
for instance definitions was necessary. In Clean 1.3.x
it was assumed that every instance definition only has one type argument. So in
the following 1.3.x instance definition
instance c T1 T2
the type (T1 T2) was meant (the type T1 with the argument T2). This should be written in Clean 2.x as
instance c (T1 T2)
otherwise T1 and T2 will be interpreted as two types.
The type Array has changed. In Clean 2.x the Array class has
become a multiparameter class, whose first argument type is the array and whose
second argument type is the array element (see ??). Therefore a 1.3 definition
like
MkArray:: !Int (Int -> e) ->.(a e) | Array a & ArrayElem e
MkArray i f = {f j \\ j <- [0..i-1]}
becomes in Clean 2.x:
MkArray:: !Int (Int -> e) ->.(a e) | Array a e
MkArray i f = {f j \\ j <- [0..i-1]}
There is a difference in resolving overloading. Consider the
following code:
class c a :: a -> a
instance c [Int]
where
c [1] = [2]
f [x:xs]
= c xs
Although this is accepted by Clean 1.3.x, Clean 2.x will complain: "Overloading error [...,..,f]: c no instance available of type [a]." The Clean 2.x compiler applies no type unification after resolving overloading. So c is in function f applied to a list with a polymorph element type ([a]). And this is considered to be different from the instance type [Int]. If you give f the type [Int] -> [Int] the upper code will be accepted.
Clean 2.x handles uniqueness attributes in type synonyms different
than Clean 1.3.x. Consider the following definitions:
:: ListList a :== [[a]]
f :: *(ListList *{Int}) -> *{Int}
f [[a]] = { a & [0]=0 }
In Clean 1.3.x the ListList type synonym was expanded to
f :: *[*[*{Int}]] -> *{Int}
which is correct in Clean 1.3.x. However, Clean 2.x expands it to
f :: *[[*{Int}]] -> *{Int}
This yields a uniqueness error in Clean 2.x because the inner list is shared but contains a unique object. This problem happens only with type synonyms that have attributes "inbetween". An "inbetween" attribute is neither the "root" attribute nor the attribute of an actual argument. E.g. with the upper type synonym, the formal argument "a" is substituted with *{Int}. Note that also the "*" is substituted for "a". Because we wrote *(ListList ...) the root attribute is "*". The result of expanding *(ListList *{Int}) is *[u:[*{Int]]. "u" is an attribute "inbetween" because it is neither the root attribute nor the attribute of a formal argument. Such attributes are made _non_unique_ in Clean 2.x and this is why the upper code is not accepted. The code will be accepted if you redefine ListList to
:: ListList a :== [*[a]]
Anonymous uniqueness attributes in type contexts are not allowed in Clean 2.x. So in the following
function type simply remove the point.
f :: a | myClass .a
The String type has become a predefined type. As a consequence you
cannot import this type explicitly anymore. So:
from StdString import :: String
is not valid.
There was a bug in the uniqueness typing system of Clean 1.3: Records or data constructors could have existentially quantified
variables, whose uniqueness attribute did _not_ propagate. This bug has been
solved in Clean 2.x. As a consequence, the 2.x compiler might complain about your
program where the 1.3.x compiler was happy. The problem might occur when you
use the object I/O library and you use objects with a uniquely attributed local
state. Now the object becomes unique as well and may not be shared anymore.
Differences in the Module System
The syntax and semantics of explicit import statements has
been completely revised. With Clean 2.x it is possible to
discriminate the different namespaces in import statements. In Clean 1.3.x the following statement
from m import F
could have caused the import of a function F together with a type F and a class F with all its instances from m. In Clean 2.x one can precisely describe from which name space one wants to import (see 2.5.2). For example, the following import statement
from m import F,
:: T1, :: T2(..), :: T3(C1, C2), :: T4{..}, :: T5{field1, field2},
class C1, class C2(..), class C3(mem1, mem2)
causes the following declarations to be imported: the function or macro F, the type T1, the algebraic type T2 with all it's constructors that are exported by m, the algebraic type T3 with it's constructors C1 and C2, the record type T4 with all it's fields that are exported by m, the record type T5 with it's fields field1 and field2, the class C1, the class C2 with all it's members that are exported by m, the class C3 with it's members mem1 and mem2.
There is a tool called "coclPort" that is able to automatically convert Clean sources with 1.3.x import syntax to sources with 2.x syntax.
Previous Releases. The first release of Clean was publicly available in 1987 and had version number 0.5 (we thought half of the work was done, ;-)). At that time, Clean was only thought as an intermediate language. Many releases followed. One of them was version 0.8 which is used in the Plasmeijer & Van Eekelen Bible (Adisson-Wesley, 1993). Version 1.0 was the first mature version of Clean.
Copyright, Authors and Credits
Clean, Clean Development System, copyright 1987 - 2001, Hilt B.V., the Netherlands.
Hilt is a Dutch company owned by the Clean team founded to ensure excellent technical support for commercial environments. Hilt furthermore educates in functional programming and develops commercial applications using Clean.
Clean is a spin-off of the research performed by the Software Technology research group, Nijmegen Institute for Information and Computing Sciences (NIII), at the University of Nijmegen under the supervision of prof. dr. ir. Rinus Plasmeijer.
The Clean System 2.0 is developed by:
|
Peter Achten: |
Object I/O library |
|
Artem Alimarine |
Support for Generic Programming |
|
Diederik van Arkel |
Clean Integrated Development Environment for Windows and Mac |
|
|
Port of Object I/O library to the Mac |
|
John van Groningen: |
Code generators (Mac (Motorola, PowerPC), PC (Intel), Sun (Sparc)), |
|
|
Clean compiler, Low level interfaces, all machine wizarding. |
|
Marco Pil |
Dynamics |
|
Maarten de Mol |
Sparkle, the integrated proof system |
|
Sjaak Smetsers: |
Clean compiler design, |
|
|
All type systems (including uniqueness typing and type classes), |
|
Ron Wichers Schreur: |
Clean Compiler, Testing, |
|
|
Clean distribution on the net. |
|
Martijn Vervoort |
Dynamics, dynamic linker |
|
Martin Wierich |
Clean compiler |
|
Marko van Eekelen: |
Clean semantics |
|
Rinus Plasmeijer: |
Overall language design and implementation supervision |
.
Special thanks to the following people:
Christ Aarts, Steffen van Bakel, Erik Barendsen, Henk Barendregt, Pieter Hartel, Marco Kesseler, Hans Koetsier, Pieter Koopman, Eric Nöcker, Leon Pillich, Ronan Sleep and all the Clean users who helped us to get a better system.
Many thanks to the following sponsors:
• the Dutch Technology Foundation (STW);
• the Dutch Foundation for Scientific Research (NWO);
• the International Academic Center for Informatics (IACI);
• Kropman B.V., Installation Techniques, Nijmegen, The Netherlands;
• Hitachi Advanced Research Laboratories, Japan;
• the Dutch Ministry of Science and Education (the Parallel Reduction Machine project (1984-1987)) who initiated the Concurrent Clean research;
• Esprit Basic Research Action (project 3074, SemaGraph: the Semantics and Pragmatics of Graph Rewriting (1989-1991));
• Esprit Basic Research Action (SemaGraph II working group 3646 (1992-1995));
• Esprit Parallel Computing Action (project 4106, (1990-1991));
• Esprit II (TIP-M project area II.3.2, Tropics: TRansparent Object-oriented Parallel Information Computing System (1989-1990)).
A system like Clean cannot be produced without an enormous investment in time, effort and money. We would therefore like to thank all commercial Clean users who are decent enough to pay the license royalties.
Final Remarks
We hope that Clean indeed enables you to program your applications in a convenient and efficient way. We will continue to improve the language and the system. We greatly appreciate your comments and suggestions for further improvements.
November 2002
Rinus Plasmeijer and Marko van Eekelen
|
Affiliation: |
Department of Software Technology |
|
|
|
|
Mail address: |
University of Nijmegen, |
|
|
Toernooiveld 1, |
|
|
6525 ED Nijmegen, |
|
|
The Netherlands. |
|
|
|
|
e-mail: |
|
|
|
|
|
|
|
|
Phone: |
+31 24 3652644 |
|
Fax: |
+31 24 3652525 |
|
|
|
|
Clean on internet: |
|
|
Clean on ftp: |
ftp://ftp.cs.ru.nl in pub/Clean |
|
Questions about Clean: |
|
|
Subscription mailing list:: |
clean@cs.ru.nl, subject:: subscribe |