Version 2.1

Language Report

# Preface

• | Introduction
• | More Information on Clean
• | About this Language Report
• | Some Remarks on the Clean Syntax
• | Notational Conventions Used in this Report
• | How to Obtain Clean
• | Current State of the Clean System
• | Copyright, Authors and Credits
• | Final Remarks

## Introduction

C lean is a practical applicable general-purpose lazy pure functional programming language suited for the development of real world applications.

C lean has many features among which some very special ones.

Functional languages are usually implemented using graph-rewriting techniques. C lean 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 C lean’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.

C lean’s “unique” features have made it possible to predefine (in C lean) a sophisticated and efficient I/O library (Achten and Plasmeijer, 1992 & 1995). The C lean Object I/O library enables a C lean 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 C lean to different platforms (we support Mac and PC) without modification of source code.

Although C lean 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 C lean 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.

C lean 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 C lean 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 C lean 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.

C lean 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.

C lean (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 C lean 2.0 compiler is written in C lean. The C lean 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 C lean 2.0 system includes lots of tools and libraries, all written in C lean 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 C lean. We hope that you will enjoy C lean’s rich collection of features, C lean’s compilation speed and the quality of the produced code (we generate native code for all platforms we support). C lean runs on a PC (Windows 2000, ‘98, ’95, WindowsNT). There are also versions running on the Mac and Linux.

Research on C lean 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 C lean 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 C lean 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 C lean 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 C lean (albeit of one of the very first versions, namely C lean 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 C lean 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), C lean’s I/O concept (Achten, 1996 & 1997), Lazy Copying for Concurrent C lean (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 C lean (http://clean.cs.ru.nl) please check our web pages.

## About this Language Report

In this report the syntax and semantics of C lean 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 C lean 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 C lean 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 C lean 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 C lean 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 C lean 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 C lean 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 C lean (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 C lean 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 C lean 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 C lean 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

C lean and the I ntegrated D evelopment E nvironment (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).

C lean is available on several platforms. Please check our WWW-pages regularly to see the latest news. New versions of C lean in general appear first on W indows and later on M ac 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 (C lean 1.3.x). We have added many new features in C lean 2.0 we hope you will like.

C lean 2.0 has multi-parameter type constructor classes. See Section 6.4.

C lean 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.

C lean 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 C lean 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 C lean 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 C lean system has been changed and extended: a new version of the C lean IDE, a new version of the run-time-system, and a dynamic linker is included. See 8.3.

C lean 2.0 comes with an integrated proof system (Sparkle), all written in C lean of course. See http://www.cs.kun.nl/Sparkle.

C lean 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 C lean expressions using Dynamics (see Van Weelden and Plasmeijer, 2002).

There is no strict let-before expression (let!) anymore in C lean 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 C lean 2.0 is not upwards compatible with C lean 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 C lean 1.3.x application to C lean 2.0. The most important syntactical differences are described below. Note that we do no longer support C lean 1.3.

The C lean 1.3 compiler is written in C. The C lean 2.0 compiler has been rewritten from scratch in C lean. 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

C lean 2.x is not downward compatible with C lean 1.3.x. Probably you have to change your 1.3.x sources to get them through the C lean 2.x compiler.

#### Differences in Expression Syntax

There is no strict let-before expression (let!) anymore in C lean 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 C lean 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 C lean 2.x as

instance c (T1 T2)

otherwise T1 and T2 will be interpreted as two types.

The type Array has changed. In C lean 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 C lean 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 C lean 1.3.x, C lean 2.x will complain: "Overloading error [...,..,f]: c no instance available of type [a]." The C lean 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.

C lean 2.x handles uniqueness attributes in type synonyms different than C lean 1.3.x. Consider the following definitions:

:: ListList a :== [[a]]

f :: *(ListList *{Int}) -> *{Int}

f [[a]] = { a & [0]=0 }

In C lean 1.3.x the ListList type synonym was expanded to

f :: *[*[*{Int}]] -> *{Int}

which is correct in C lean 1.3.x. However, C lean 2.x expands it to

f :: *[[*{Int}]] -> *{Int}

This yields a uniqueness error in C lean 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 C lean 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 C lean 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 C lean 1.3: Records or data constructors could have existentially quantified variables, whose uniqueness attribute did _not_ propagate. This bug has been solved in C lean 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 C lean 2.x it is possible to discriminate the different namespaces in import statements. In C lean 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 C lean 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 C lean sources with 1.3.x import syntax to sources with 2.x syntax.

Previous Releases. The first release of C lean was publicly available in 1987 and had version number 0.5 (we thought half of the work was done, ;-)). At that time, C lean 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 C lean.

## Copyright, Authors and Credits

C lean, C lean Development System, copyright 1987 - 2001, Hilt B.V., the Netherlands.

Hilt is a Dutch company owned by the C lean team founded to ensure excellent technical support for commercial environments. Hilt furthermore educates in functional programming and develops commercial applications using C lean.

C lean 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 C lean System 2.0 is developed by:

Peter Achten: | Object I/O library
Artem Alimarine | Support for Generic Programming
Diederik van Arkel | C lean 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)),
| C lean compiler, Low level interfaces, all machine wizarding.
Marco Pil | Dynamics
Maarten de Mol | Sparkle, the integrated proof system
Sjaak Smetsers: | C lean compiler design,
| All type systems (including uniqueness typing and type classes),
Ron Wichers Schreur: | C lean Compiler, Testing,
| C lean distribution on the net.
Martijn Vervoort | Dynamics, dynamic linker
Martin Wierich | C lean compiler
Marko van Eekelen: | C lean 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 C lean 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 C oncurrent C lean 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 C lean cannot be produced without an enormous investment in time, effort and money. We would therefore like to thank all commercial C lean users who are decent enough to pay the license royalties.

## Final Remarks

We hope that C lean 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: | rinus@cs.ru.nl
| marko@cs.ru.nl
Phone: | +31 24 3652644
Fax: | +31 24 3652525
C lean on internet: | http://clean.cs.ru.nl
C lean on ftp: | ftp://ftp.cs.ru.nl in pub/Clean
Questions about C lean: | clean@cs.ru.nl
Subscription mailing list:: | clean@cs.ru.nl, subject:: subscribe