Clean Language Report

# Version 3.0
Language Report

# Preface

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 ap-plications 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 alwaysdenotated 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}-list |  | means one or more occurrences of notion separated by commas
terminals |  | are printed in 9 pts courier bold brown
keywords |  | are printed in 9 pts courier bold red
terminals |  | that can be left out in layout mode are printed in 9 pts courier bold blue
{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)

### 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 implementation 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 Dynamiccan 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. Dynamicsmake 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 meant (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 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, theclass C2 with all it's members that are exported by m, the class C3 with it's members mem1 and mem2.

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.