Clean 2.2 Ref Man

Version 2.2

Language Report

Table of Contents iii

Preface i

Introduction i

More Information on Clean ii

About this Language Report iii

Some Remarks on the Clean Syntax iii

Notational Conventions Used in this Report iv

How to Obtain Clean iv

Current State of the Clean System iv

Syntactic differences between Clean 1.3 and Clean 2.0 v

Differences in Expression Syntax vi

Differences in the Type System vi

Differences in the Module System vii

Final Remarks viii

Chapter 1 Basic Semantics 1

1.1 Graph Rewriting 1

1.1.1 A Small Example 2

1.2 Global Graphs 4

Chapter 2 Modules and Scopes 5

2.1 Identifiers, Scopes and Name Spaces 5

2.1.1 Naming Conventions of Identifiers 5

2.1.2 Scopes and Name Spaces 6

2.1.3 Nesting of Scopes 6

2.2 Modular Structure of Clean Programs 6

2.3 Implementation Modules 7

2.3.1 The Main or Start Module 7

I/O Using the Console 7

I/O on the Unique World 8

2.3.2 Scope of Global Definitions in Implementation Modules 8

2.3.3 Begin and End of a Definition: the Layout Rule 9

2.4 Definition Modules 10

2.5 Importing Definitions 11

2.5.1 Explicit Imports of Definitions 11

2.5.2 Implicit Imports of Definitions 12

2.6 System Definition and Implementation Modules 12

Chapter 3 Defining Functions and Constants 15

3.4.1 Lambda Abstraction 19

3.4.2 Case Expression and Conditional Expression 20

3.5 Local Definitions 20

3.5.1 Let Expression: Local Definitions in Expressions 21

3.5.2 Where Block: Local Definitions in a Function Alternative 21

3.5.3 With Block: Local Definitions in a Guarded Alternative 22

3.5.4 Let-Before Expression: Local Constants defined between Guards 22

3.6 Defining Constants 24

3.6.1 Selectors 25

3.7 Typing Functions 26

3.7.1 Typing Curried Functions 27

3.7.2 Typing Operators 27

3.7.3 Typing Partial Functions 27

3.7.4 Explicit use of the Universal Quantifier in Function Types 27

3.7.5 Functions with Strict Arguments 29

Chapter 4 Predefined Types 31

4.1 Basic Types: Int, Real, Char and Bool 31

4.1.1 Creating Constant Values of Basic Type 31

4.1.2 Patterns of Basic Type 32

4.2 Lists 32

4.2.1 Creating Lists 33

Lazy Lists 33

Strict , Unboxed and Overloaded Lists 33

DotDot Expressions 34

List Comprehensions 35

4.2.1 List Patterns 36

4.3 Tuples 37

4.3.1 Creating Tuples 37

4.3.2 Tuple Patterns 38

4.4 Arrays 38

4.4.1 Creating Arrays and Selection of field Elements 39

Simple Array 39

Array Update and Array Comprehensions 40

Selection of an Array Element 42

4.4.2 Array Patterns 42

4.5 Predefined Type Constructors 42

4.6 Arrow Types 43

4.7 Predefined Abstract Types 43

Chapter 5 Defining New Types 45

5.1 Defining Algebraic Data Types 45

5.1.1 Using Constructors in Patterns 46

5.1.2 Using Higher Order Types 47

5.1.3 Defining Algebraic Data Types with Existentially Quantified Variables 47

5.1.4 Defining Algebraic Data Types with Universally Quantified Variables 48

5.1.5 Strictness Annotations in Type Definitions 49

5.1.6 Semantic Restrictions on Algebraic Data Types 50

5.2 Defining Record Types 50

5.2.1 Creating Records and Selection of Record Fields 52

Simple Records 52

Record Update 52

Selection of a Record Field 53

5.2.2 Record Patterns 53

5.3 Defining Synonym Types 54

5.4 Defining Abstract Data Types 54

5.4.1 Defining Abstract Data Types with Synonym Type Definition 55

Chapter 6 Overloading 57

6.1 Type Classes 58

6.2 Functions Defined in Terms of Overloaded Functions 59

6.3 Instances of Type Classes Defined in Terms of Overloaded Functions 60

6.4 Type Constructor Classes 60

6.5 Overlapping Instances 61

6.6 Internal Overloading 62

6.7 Defining Derived Members in a Class 63

6.8 A Shorthand for Defining Overloaded Functions 63

6.9 Classes Defined in Terms of Other Classes 64

6.10 Exporting Type Classes 64

6.11 Semantic Restrictions on Type Classes 65

Chapter 7 Generic Programming 67

7.1 Basic Ideas Behind Generic Programming 67

7.2 Defining Generic Functions 70

7.3 Deriving Generic Functions 72

7.4 Applying Generic Functions 72

7.5 Using Constructor Information 73

7.6 Generic Functions and Uniqueness Typing 74

7.7 Exporting Generic Functions 75

Chapter 8 Dynamics 77

8.1 Packing Expressions into a Dynamic 78

8.1.1 Packing Abstract Data Types 79

8.1.2 Packing Overloaded Functions 79

8.1.3 Packing Expressions of Unique Type 79

8.1.4 Packing Arguments of Unknown Type 80

8.1.5 Using Dynamic Typing to Defeat the Static Type System 80

8.2 Unpacking Dynamics Using a Dynamic Pattern Match 81

8.2.1 Unpacking Abstract Data Types 83

8.2.2 Unpacking of Overloaded Functions 83

8.2.3 Unpacking Expressions of Unique Type 83

8.2.4 Checking and Unifying Types Schemes using Type Pattern Variables 83

8.2.5 Checking and Unifying Unknown Types using Overloaded Type Variables 84

8.3 Type Safe Communication using Dynamics 85

8.4 Architecture of the implementation 87

Implementation of Dynamics 88

8.5 Semantic Restrictions on Dynamics 89

Chapter 9 Uniqueness Typing 91

9.1 Basic Ideas behind Uniqueness Typing 91

9.2 Attribute Propagation 93

9.3 Defining New Types with Uniqueness Attributes 94

9.4 Uniqueness and Sharing 96

9.4.1 Higher Order Uniqueness Typing 97

9.4.2 Uniqueness Type Coercions 98

9.5 Combining Uniqueness Typing and Overloading 99

9.5.1 Constructor Classes 99

9.6 Higher-Order Type Definitions 101

9.7 Destructive Updates using Uniqueness Typing 102

Chapter 10 Strictness, Macros and Efficiency 105

10.1 Annotations to Change Lazy Evaluation into Strict Evaluation 105

10.1.1 Advantages and Disadvantages of Lazy versus Strict Evaluation 105

10.1.2 Strict and Lazy Context 106

10.1.3 Space Consumption in Strict and Lazy Context 106

10.1.4 Time Consumption in Strict and Lazy Context 107

10.1.5 Changing Lazy into Strict Evaluation 107

10.2 Defining Graphs on the Global Level 107

10.3 Defining Macros 108

10.4 Efficiency Tips 109

Chapter 11 Foreign Language Interface 111

11.1 Foreign Export 111

11.2 Using ABC instructions 112

Appendix A Context-Free Syntax Description 113

A.1 Clean Program 113

A.2 Import Definition 114

A.3 Function Definition 114

A.3.1 Types of Functions 114

A.3.2 Patterns 115

A.3.3 Graph Expressions 115

A.4 Macro Definition 117

A.5 Type Definition 117

A.5.1 Type Expression 117

A.6 Class and Generic Definitions 118

A.7 Foreign Export Definition 119

A.8 Names 119

A.9 Denotations 119

Appendix B Lexical Structure 121

B.1 Lexical Program Structure 121

B.2 Comments 121

B.3 Reserved Keywords and Symbols 122

Appendix C Bibliography 125

Appendix D Index 129