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 Clean 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	=	"