Appendix A
Context-Free Syntax Description

A.1 | Clean Program
A.2 | Import Definition
A.3 | Function Definition
A.4 | Macro Definition
A.5 | Type Definition
A.6 | Class And Generic Definitions
A.7 | Foreign Export Definition
A.8 | Names
A.9 | Denotations

In this appendix the context-free syntax of C lean is given. Notice that the layout rule (see 2.3.3) permits the omission of the semi-colon (‘;’) which ends a definition and of the braces (‘{’ and ‘}’) which are used to group a list of definitions.

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

## A.1 Clean Program

CleanProgram | = | {Module}+
Module | = | DefinitionModule
| | | ImplementationModule
DefinitionModule | = | definition module ModuleName ;
|  | {DefDefinition}
| | | system module ModuleName ;
|  | {DefDefinition}
ImplementationModule | = | [implementation] module ModuleName ;
|  | {ImplDefinition}

ImplDefinition | = | ImportDef | // see A.2
| | | FunctionDef | // see A.3
| | | GraphDef | // see A.3
| | | MacroDef | // see A.4
| | | TypeDef | // see A.5
| | | ClassDef | // see A.6
| | | GenericsDef | // see A.6
| | | ForeignExportDef | // see A.7

DefDefinition | = | ImportDef | // see A.2
| | | FunctionTypeDef | // see A.3
| | | MacroDef | // see A.4
| | | TypeDef | // see A.5
| | | ClassDef | // see A.6
| | | TypeClassInstanceExportDef | // see A.6
| | | GenericExportDef | // see A.6

## A.2 Import Definition

ImportDef | = | ImplicitImportDef
| | | ExplicitImportDef

ImplicitImportDef | = | import {ModuleName}-list ;

ExplicitImportDef | = | from ModuleName import {Imports}-list ;
Imports | = | FunctionName
| | | ::TypeName [ConstructorsOrFields]
| | | class ClassName [Members]
| | | instance ClassName {TypeName}+
ConstructorsOrFields | = | (..)
| | | ({ConstructorName}-list)
| | | {..}
| | | {{FieldName}-list}
Members | = | (..)
| | | ({MemberName}-list)

## A.3 Function Definition

FunctionDef | = | [FunctionTypeDef]
|  | DefOfFunction

DefOfFunction | = | {FunctionAltDef ;}+
| | | ABCCodeFunctionDef
FunctionAltDef | = | Function {Pattern}
|  | {{LetBeforeExpression}
|  | {| Guard} =[>] FunctionBody}+
|  | [LocalFunctionAltDefs]

Function | = | FunctionName
| | | (FunctionName)

LetBeforeExpression | = | # {GraphDef}+
| | | #!{GraphDef}+

GraphDef | = | Selector =[:] GraphExpr ;
Selector | = | BrackPattern

Guard | = | BooleanExpr
| | | otherwise
BooleanExpr | = | GraphExpr

FunctionBody | = | RootExpression ;
|  | [LocalFunctionDefs]

RootExpression | = | GraphExpr

LocalFunctionAltDefs | = | [where] { {LocalDef}+ }
LocalDef | = | GraphDef
| | | FunctionDef
LocalFunctionDefs | = | [with] { {LocalDef}+ }

ABCCodeFunctionDef | = | Function {Pattern} = code [inline] { ABCInstructions }

### A.3.1 Types of Functions

FunctionTypeDef | = | FunctionName :: FunctionType ;
| | | (FunctionName) [Fix][Prec] [:: FunctionType] ;
FunctionType | = | [Type -> ] Type_Expression [ClassContext] [UnqTypeUnEqualities]
ClassContext | = | | ClassOrGenericName-list TypeVariable {& ClassName-list TypeVariable }
UnqTypeUnEqualities | = | {{UniqueTypeVariable}+ <= UniqueTypeVariable}-list
ClassOrGenericName | = | ClassName
| | | FunctionName TypeKind

### A.3.2 Patterns

Pattern | = | [Variable =:] BrackPattern
BrackPattern | = | PatternVariable
| | | Constructor
| | | (GraphPattern)
| | | SpecialPattern
| | | DynamicPattern

PatternVariable | = | Variable
| | | _

Constructor | = | ConstructorName | // see A.8
| | | (ConstructorName) |

GraphPattern | = | Constructor {Pattern}
| | | GraphPattern ConstructorName GraphPattern
| | | Pattern

SpecialPattern | = | BasicValuePattern
| | | ListPattern
| | | TuplePattern
| | | ArrayPattern
| | | RecordPattern

BasicValuePattern | = | BasicValue |
BasicValue | = | IntDenotation | // see A.9
| | | RealDenotation | // see A.9
| | | BoolDenotation | // see A.9
| | | CharDenotation | // see A.9

ListPattern | = | [[ListKind][{LGraphPattern}-list [: GraphPattern]] [SpineStrictness]]
LGraphPattern | = | GraphPattern |
| | | CharsDenotation | // see A.9

TuplePattern | = | (GraphPattern,{GraphPattern}-list)

RecordPattern | = | {[TypeName |] {FieldName [= GraphPattern]}-list}

ArrayPattern | = | {{GraphPattern}-list} |
| | | {{ArrayIndex = Variable}-list} |
| | | StringDenotation | // see A.9

DynamicPattern | = | (GraphPattern :: DynamicType)
DynamicType | | | { DynPatternType}+
DynPatternType | = | Type
| | | TypePatternVariable
| | | OverloadedTypePatternVariable
TypePatternVariable | = | Variable
OverloadedTypeVariable | = | Variable^

### A.3.3 Graph Expressions

GraphExpr | = | Application

Application | = | {BrackGraph}+ |
| | | GraphExpr Operator GraphExpr |
| | | GenericAppExpr |
Operator | = | FunctionName | // see A.8
| | | ConstructorName | // see A.8

BrackGraph | = | GraphVariable
| | | Constructor
| | | Function
| | | (GraphExpr)
| | | LambdaAbstr
| | | CaseExpr
| | | LetExpr
| | | SpecialExpression
| | | DynamicExpression

GraphVariable | = | Variable | // see A.8
| | | SelectorVariable | // see A.8

LambdaAbstr | = | \ {Pattern} = GraphExpr
| | | \ {Pattern} -> GraphExpr

CaseExpr | = | case GraphExpr of
|  | { {CaseAltDef}+ }
| | | if BrackGraph BrackGraph BrackGraph
CaseAltDef | = | {Pattern}
|  | {{LetBeforeExpression}
|  | {| Guard} = [>] FunctionBody}+
|  | [LocalFunctionAltDefs]
| | | {Pattern}
|  | {{LetBeforeExpression}
|  | {| Guard} -> FunctionBody}+
|  | [LocalFunctionAltDefs]

LetExpresssion | = | let { {LocalDef}+ } in GraphExpr

SpecialExpression | = | BasicValue
| | | List
| | | Tuple
| | | Array
| | | ArraySelection
| | | Record
| | | RecordSelection

List | = | ListDenotation |
| | | DotDotexpression |
| | | ZF-expression |
ListDenotation | = | [[ListKind] [{LGraphExpr}-list [: GraphExpr]] [SpineStrictness] ]
LGraphExpr | = | GraphExpr |
| | | CharsDenotation | // see A.9
DotDotexpression | = | [[ListKind] GraphExpr [,GraphExpr]..[GraphExpr] [SpineStrictness] ]
ZF-expression | = | [[ListKind] GraphExpr \\ {Qualifier}-list [SpineStrictness]]
Qualifier | = | Generators { , let { {LocalDef}+ } } {|Guard}
Generators | = | {Generator}-list |
| | | Generator {& Generator} |
Generator | = | Selector <- ListExpr | // select from a lazy list
| | | Selector <|- ListExpr | // select from an overloaded list
| | | Selector <-: ArrayExpr | // select from an array
Selector | = | BrackPattern | // for brack patterns see 3.2
ListExpr | = | GraphExpr |
ArrayExpr | = | GraphExpr |

Tuple | = | (GraphExpr,{GraphExpr}-list)

Array | = | ArrayDenotation |
| | | ArrayUpdate |
| | | ArraySelection |
ArrayDenotation | = | {{GraphExpr}-list} |
| | | StringDenotation | // see A.9
ArrayUpdate | = | { ArrayExpr & [{ArrayIndex {Selection} = GraphExpr}-list] [\\ {Qualifier}-list]}
| | | {[ArrayExpr &] GraphExpr \\ {Qualifier}-list}
ArraySelection | = | ArrayExpr.ArrayIndex {Selection} |
| | | ArrayExpr!ArrayIndex {Selection} |
Selection | = | . FieldName |
| | | . ArrayIndex |
ArrayExpr | = | GraphExpr |
ArrayIndex | = | [{IntegerExpr}-list] |
IntegerExpr | = | GraphExpr |

Record | = | RecordDenotation
| | | RecordUpdate
RecordDenotation | = | {[TypeName|] {FieldName = GraphExpr}-list]}
RecordUpdate | = | {[TypeName|][RecordExpr &][{FieldName {Selection} = GraphExpr}-list]}
RecordExpr | = | GraphExpr
RecordSelection | = | RecordExpr [.TypeName].FieldName {Selection}
| | | RecordExpr [.TypeName]!FieldName {Selection}

DynamicExpression | = | dynamic GraphExpr [:: Type]

## A.4 Macro Definition

MacroDef | = | [MacroFixityDef]
|  | DefOfMacro
MacroFixityDef | = | (FunctionName) [Fix][Prec] ;
DefOfMacro | = | Function {Variable} :== FunctionBody ;
|  | [LocalFunctionAltDefs]

## A.5 Type Definition

TypeDef | = | AlgebraicTypeDef
| | | RecordTypeDef
| | | SynonymTypeDef
| | | AbstractTypeDef
| | | AbstractSynonymTypeDef

AlgebraicTypeDef | = | ::TypeLhs | = ConstructorDef
|  |  | {| ConstructorDef} ;
ConstructorDef | = | [ExistentalQuantVariables] ConstructorName {BrackType}
| | | [ExistentalQuantVariables] (ConstructorName) [Fix][Prec] {BrackType}

TypeLhs | = | [*] TypeConstructorName {TypeVariable} | // see A.8

ExistentalQuantVariables | = | E.{TypeVariable }+:

Fix | = | infixl
| | | infixr
| | | infix

Prec | = | Digit | // see A.8

BrackType | = | [UniversalQuantVariables] [Strict] [UnqTypeAttrib] TypeExpression

UniversalQuantVariables | = | A.{TypeVariable }+:

Strict | = | !

UnqTypeAttrib | = | * |
| | | UniqueTypeVariable: | // see A.8
| | | . |

RecordTypeDef | = | ::TypeLhs = [ExistentalQuantVariables] [Strict] {{FieldName :: [Strict] Type}-list} ;

Type | = | {BrackType}+

SynonymTypeDef | = | ::TypeLhs :== [UniversalQuantVariables] Type ;

AbstractTypeDef | = | ::TypeLhs ;

AbstractSynonymTypeDef | = | ::TypeLhs ( :== [UniversalQuantVariables] Type ) ;

### A.5.1 Type Expression

TypeExpression | = | TypeVariable | // see A.8
| | | TypeConstructorName |
| | | (Type) |
| | | PredefinedType |
| | | PredefinedTypeConstructor |

PredefinedType | = | BasicType
| | | ListType
| | | TupleType
| | | ArrayType
| | | ArrowType
| | | PredefType

BasicType | = | Int
| | | Real
| | | Char
| | | Bool

ListType | = | [[ListKind] Type [SpineStrictness]] |
ListKind | = | ! | // head strict list
| | | # | // head strict, unboxed list
SpineStrictness | = | ! | // tail (spine) strict list

TupleType | = | ([Strict] Type,{[Strict] Type}-list)

ArrayType | = | {[ArrayKind] Type} |
ArrayKind | = | ! | // strict array
| | | # | // unboxed array

PredefType | = | World | // see StdWorld.dcl
| | | File | // see StdFileIO.dcl
| | | String | // synonym for {#Char}
PredefinedTypeConstructor | = | [] | // list type constructor
| | | [! ] | // head strict list type constructor
| | | [ !] | // tail strict list type constructor
| | | [!!] | // strict list type constructor
| | | [#] | // unboxed head strict list type
| | | [#!] | // unboxed strict list type
| | | ({,}+) | // tuple constructor (arity >= 2)
| | | {} | // lazy array type constructor
| | | {!} | // strict array type constructor
| | | {#} | // unboxed array constructor
| | | (->) | // arrow type constructor

## A.6 Class and Generic Definitions

ClassDef | = | TypeClassDef
| | | TypeClassInstanceDef
| | | TypeClassInstanceExportDef

TypeClassDef | = | class ClassName TypeVariable [ClassContext]
|  | [[where] { {ClassMemberDef}+ }]
| | | class FunctionName TypeVariable :: FunctionType;
| | | class (FunctionName) [Fix][Prec] TypeVariable :: FunctionType;

ClassMemberDef | = | FunctionTypeDef
|  | [MacroDef]

TypeClassInstanceDef | = | instance ClassName Type+ [ClassContext] |
|  | [[where] {{DefOfFunction}+ }] | // in implementation modules
|  | [special {TypeVariable = Type}+] | // in definition modules

TypeClassInstanceExportDef | = | export ClassName BasicType-list;

GenericsDef | = | GenericDef ;
| | | GenericCase;
| | | DeriveDef ;

GenericDef | = | generic FunctionName TypeVariable+ :: FunctionType
GenericCase | = | FunctionName {|GenericTypeArg|} {Pattern}+ = FunctionBody
GenericTypeArg | = | CONS [of {Pattern}]
| | | FIELD [of {Pattern}]
| | | TypeConstructorName
| | | TypeVariable

DeriveDef | = | derive FunctionName TypeConstructorName+

GenericAppExpr | = | FunctionName TypeKind GraphExpr
TypeKind | = | {|* {-> *} |}

GenericExportDef | = | GenericDef ;
| | | DeriveDef ;

## A.7 Foreign Export Definition

ForeignExportDef | = | foreign export [ ccall | stdcall ] FunctionName ;

## A.8 Names

ModuleName | = | LowerCaseId | | | UpperCaseId | | | FunnyId
FunctionName | = | LowerCaseId | | | UpperCaseId | | | FunnyId
ConstructorName | = |  |  | UpperCaseId | | | FunnyId
SelectorVariable | = | LowerCaseId |  |  |  |
Variable | = | LowerCaseId |  |  |  |
MacroName | = | LowerCaseId | | | UpperCaseId | | | FunnyId
FieldName | = | LowerCaseId |  |  |  |
TypeConstructorName | = |  |  | UpperCaseId | | | FunnyId
TypeVariable | = | LowerCaseId |  |  |  |
UniqueTypeVariable | = | LowerCaseId |  |  |  |
ClassName | = | LowerCaseId | | | UpperCaseId | | | FunnyId
MemberName | = | LowerCaseId | | | UpperCaseId | | | FunnyId

LowerCaseId; | = | LowerCaseChar~{IdChar}
UpperCaseId | = | UpperCaseChar~{IdChar}
FunnyId | = | {SpecialChar}+

LowerCaseChar | = | a | b | c | d | e | f | g | h | i | j
| | | k | l | m | n | o | p | q | r | s | t
| | | u | v | w | x | y | z |
UpperCaseChar | = | a | b | c | d | e | f | g | h | i | j
| | | k | l | m | n | o | p | q | r | s | t
| | | u | v | w | x | y | z |
SpecialChar | = | ~ | @ | # | $ | % | ^ | ? | !
| | | + | - | * | < | > | \ | / | | | & | =
| | | : |
IdChar | = | LowerCaseChar |
| | | UpperCaseChar |
| | | Digit | // see A.9
| | | _ | ‘ |

## A.9 Denotations

IntDenotation; | = | [Sign]~{Digit}+ | // decimal number
| | | [Sign]~ 0~{OctDigit}+ | // octal number
| | | [Sign]~ 0x~{HexDigit}+ | // hexadecimal number
Sign | = | + | - | ~ |
RealDenotation | = | [Sign~]{Digit~}+.{~Digit}+[~E[~Sign]{~Digit}+]
BoolDenotation | = | True | False |
CharDenotation | = | CharDel AnyChar/~CharDel CharDel |
CharsDenotation | = | CharDel {AnyChar/~CharDel}+ CharDel |
StringDenotation | = | StringDel {AnyChar/~StringDel}+ StringDel |

AnyChar | = | IdChar | ReservedChar | Special |
ReservedChar | = | ( | ) | { | } | [ | ] | ; | , | .
Special | = | \n | \r | \f | \b | // newline,return,formf,backspace
| | | \t | \\ | \CharDel | // tab,backslash,character delete
| | | \StringDel | // string delete
| | | \o{OctDigit}+ | // octal number
| | | \x{HexDigit}+// hexadecimal number |
| | | \{Digit}+ | // literal digit sequence
| | | \IdChar | // escape any other character

Digit | = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
OctDigit | = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
HexDigit | = | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
| | | A | B | C | D | E | F
| | | a | b | c | d | e | f

CharDel | = | '
StringDel | = | "