Plaintext
Application Patterns
in Functional Languages
Nikolaas N. Oosterhof
2005
Application Patterns
in Functional Languages
by
Nikolaas N. Oosterhof
a Thesis
written under the supervision of
dr. ir. Jan Kuper
dr. Maarten M. Fokkinga drs. Joeri van Ruth
submitted to the
department of Computer Science
in partial fulfilment of
the requirements for the degree of
Ingenieur
equivalent to a Master’s degree
in
Computer Science
University of Twente
Enschede, The Netherlands
2005
iv
Copyright c 2005 Nikolaas N. Oosterhof.
This document is free; you can copy, distribute, display, perform and/or modify
it under the terms of the Creative Commons Attribution-ShareAlike License
Version 2.0. A copy of the license is included in Appendix B.1.
Supervisor committee:
dr. ir. Jan Kuper Primary supervisor
dr. Maarten M. Fokkinga Secundary supervisor
drs. Joeri van Ruth Secundary supervisor
This thesis can be cited as:
Oosterhof, Nikolaas N. (2005). Application Patterns in Functional Lan-
guages. Master’s thesis, University of Twente, The Netherlands.
The author may be contacted at n.n.oosterhof@student.uva.nl
This thesis is set in Computer Modern Roman by the author using LATEX.
v
Human-readible summary of the
Creative Commons Attribution-ShareAlike 2.0 License
You are free:
• to copy, distribute, display, and perform the work
• to make derivative works
• to make commercial use of the work
Under the following conditions:
Attribution. You must give the original author credit.
Share Alike. If you alter, transform, or build upon this
work, you may distribute the resulting work only under a
license identical to this one.
• For any reuse or distribution, you must make clear to others the license
terms of this work.
• Any of these conditions can be waived if you get permission from the
copyright holder.
Your fair use and other rights are in no way affected by the above.
A copy of the Legal Code (the full license) is included in Appendix B.1.
vi
To my parents
vii
viii
Abstract
Most contemporary pure functional languages provide support for patterns in
function definitions. Examples of common patterns are the identifier, constant,
tuple, list algebraic, n+k and as-pattern.
This thesis introduces a new kind of patterns, called application patterns.
Such patterns consist of a function applied to arguments: they are of the form
(f x1 ... xn ). When such a pattern is matched against an actual argument,
inverse functions are used to find the binding of variables to values. A theoretical
framework is provided that accomodates for defining multiple generalized inverse
functions (for returning different sets of arguments) for one function. These
inverse functions can be available in the system, derived by the system or defined
by the programmer. A notation is introduced so that in a definition’s left hand
side identifiers can be used that are bound in the context. It is established that
application patterns are universal in the sense that they include constant, tuple,
list, algebraic, n+k and as-patterns.
This thesis describes an algoritm that translates functional program code
with application patterns to program code without application patterns that
can be run on an interpreter. It also provides a proof-of-concept implementation
of this algoritm in a functional language.
Keywords: Functional programming, pattern matching, inverse function,
application pattern
ix
x ABSTRACT
Contents
Abstract ix
Acknowledgements xv
1 Introducing patterns 1
1.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Mathematical functions . . . . . . . . . . . . . . . . . . . 1
1.1.2 Functions in functional languages . . . . . . . . . . . . . . 2
1.2 Pattern matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Identifier pattern . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Constant pattern . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 List pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Tuple pattern . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.5 Algebraic pattern . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.6 n+k pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.7 As pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.8 Equivalence pattern . . . . . . . . . . . . . . . . . . . . . 10
1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Application patterns 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Application patterns . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Basic application pattern . . . . . . . . . . . . . . . . . . 11
2.2.2 Refutable application patterns . . . . . . . . . . . . . . . 13
2.3 Currying application patterns . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.2 Cousins of functions . . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Generalized inverse . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Some refinements . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Pattern expressions . . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 Caret notation . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.3 Extraction functions . . . . . . . . . . . . . . . . . . . . . 24
2.4.4 Programmer’s responsibilities . . . . . . . . . . . . . . . . 25
2.5 Application patterns as a generalization . . . . . . . . . . . . . . 26
2.5.1 List pattern, revisited . . . . . . . . . . . . . . . . . . . . 26
2.5.2 Algebraic pattern, revisited . . . . . . . . . . . . . . . . . 26
2.5.3 Tuple pattern, revisited . . . . . . . . . . . . . . . . . . . 27
2.5.4 n+k pattern, revisited . . . . . . . . . . . . . . . . . . . . 27
xi
xii CONTENTS
2.5.5 Constant pattern, revisited . . . . . . . . . . . . . . . . . 28
2.5.6 As pattern, revisited . . . . . . . . . . . . . . . . . . . . . 29
2.5.7 Equivalence pattern, revisited . . . . . . . . . . . . . . . . 29
2.6 Standard inverse functions . . . . . . . . . . . . . . . . . . . . . . 29
2.6.1 Arithmetic operators . . . . . . . . . . . . . . . . . . . . . 30
2.6.2 Goniometric functions . . . . . . . . . . . . . . . . . . . . 31
2.6.3 Numerical functions . . . . . . . . . . . . . . . . . . . . . 32
2.6.4 List manipulation . . . . . . . . . . . . . . . . . . . . . . 33
2.6.5 Conversion functions . . . . . . . . . . . . . . . . . . . . . 35
2.7 The use of application patterns . . . . . . . . . . . . . . . . . . . 36
2.7.1 More readible definitions . . . . . . . . . . . . . . . . . . . 36
2.7.2 Simple string parsing . . . . . . . . . . . . . . . . . . . . . 37
2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 The Application Pattern Compiler 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Intuitively rewriting application patterns . . . . . . . . . . . . . . 39
3.2.1 Basic pattern . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Adding refutability . . . . . . . . . . . . . . . . . . . . . . 40
3.2.3 Adding refutability . . . . . . . . . . . . . . . . . . . . . . 41
3.3 A rewriting algoritm . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Rewriting patterns . . . . . . . . . . . . . . . . . . . . . . 44
3.3.3 Special cases in rewriting . . . . . . . . . . . . . . . . . . 46
3.3.4 Rewriting definitions . . . . . . . . . . . . . . . . . . . . . 48
3.3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 The application pattern compiler . . . . . . . . . . . . . . . . . . 50
3.4.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.2 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.3 Implementation language . . . . . . . . . . . . . . . . . . 51
3.4.4 Implemenation . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.7 List comprehensions . . . . . . . . . . . . . . . . . . . . . 53
3.4.8 Choose carets . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.9 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4 The future for application patterns 57
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3 Further research . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3.1 Lazyness and evaluation order . . . . . . . . . . . . . . . 60
4.3.2 Higher order functions . . . . . . . . . . . . . . . . . . . . 60
4.3.3 More sophisticated pattern failures . . . . . . . . . . . . . 61
4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
A Implementation of the Application Pattern Compiler 63
CONTENTS xiii
B Example input and output 65
B.0.1 Example input . . . . . . . . . . . . . . . . . . . . . . . . 65
B.0.2 Example output . . . . . . . . . . . . . . . . . . . . . . . 67
B.1 Copyright license . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Bibliography 79
xiv CONTENTS
Acknowledgements
I would like to thank my supervisors Jan Kuper, Maarten Fokkinga and Joeri
van Ruth for their continuous support and valuable remarks, suggestions and
feedback.
The important roles of both Jan Kuper and Philip Hölzenspies can hardly
by underestimated. I think the three of us contributed evenly important idea’s
for the development of the idea of application patterns. We had many long
meetings with great discussions about syntax, semantics, esthetics, pragmatics
and many other aspects of the concept. Jan and Philip, it has been a privilege
working with you.
Jan and Philip should also be credited for initiating the Tina development
group. It was this group, with great contributions by Jillis te Hove, Emond
Papegaaij, Arjan Boeijink, Ruben Smelik and Berteun Damman that revived
my enthousiasm for functional programming. This group was very enthusiastic
and open-minded so that the idea for application patterns (in its most basic
form, at that time) could develop. Thank you guys for the nice meetings and
the great atmosphere.
Finally I would like to thank my parents Dick and Janet, my brother Chris and
my sisters Jantine and Dianne for the important role they fulfill in my Life, the
Universe, and Everything. I would like to dedicate my work to all five, but as
there is also another thesis in Philosophy of Science, Technology and Society,
Thinking Machines That Feel: the Role of Emotions in Artificial Intelligence
Research, I considered an even split of dedication for the two generations most
appropriate. Therefore, this thesis is dedicated to my parents.
xv
xvi ACKNOWLEDGEMENTS
Chapter 1
Introducing patterns
This chapter provides the necessary background for the remainder of this thesis.
It provides a short introduction in the world of functions, function definitions in
functional programming and pattern matching. The structure is as follows: in
Section 1.1 the concept of a function is described, both from a mathematical and
a functional programming perspective. In functional programming, patterns are
important in function definitions. Therefore, Section 1.2 provides an overview
is given of typical patterns in functional programming.
1.1 Functions
In this section a brief overview of functions is given. First mathematical func-
tions are described, followed by functions and their definitions in functional
languages.
1.1.1 Mathematical functions
In mathematics, functions are objects that map elements in one set to sets to
elements in another set. If A and B are sets, then the relation f ⊂ A × B is
called a partial function if, for every x ∈ A, there is at most one y ∈ B so that
(x, y) ∈ f . Instead of (x, y) ∈ f , we write f (x) = y or f x = y, and say that
y ∈ B is the image or result of f applied to x ∈ A. Furthermore, A and B are
called the domain and codomain, and we write f : A → B.
A partial function f : A → B is a total function if, for every x ∈ A, there is
one y ∈ B so that f (x) = y. Except when stated otherwise, function indicates
a partial function.
A total function f : A → B is the total inverse of the total function g : B →
A if, for every x and y, (x, y) ∈ f if, and only if, (y, x) ∈ g. We then write
g −1 = f . If f is the total inverse of g, then g is also the total inverse of f , and
we say that f and g are inverse functions.
Sometimes two functions are not inverse, although they would be if their
domain and codomain are restricted. A function f : A → B is the partial inverse
of the function g : C → D if, for every x, x̂ ∈ B ∩C and every y ∈ A∩D, it holds
that if (x, y) ∈ g and (y, x̂) ∈ f then x = x̂. That is, a function and its partial
inverse may not be defined for the same (co)domain, but for their ‘collective’
1
2 CHAPTER 1. INTRODUCING PATTERNS
(co)domain they must agree on the values they map. When no ambiguities can
arise, we say losely that f is the inverse of g and write g −1 = f .
Example. Consider the functions in Table 1.1, whose domain and codomain
are indicated. The functions f , g, h and sin are total functions. For g a total
inverse function exists, whereas for f , h, tan and sin only an partial inverse
exists.
Table 1.1: Some functions and their inverses
function (co)domain restricted inverse function
(co)domain
f : m 7→ m + 1 N→N N → N∗ n 7→ n − 1
g : x 7→ 3x + 5 Q→Q y 7→ y−5
3 √
2
h : x 7→ x − 2x − 3 R → R [1, ∞i → [1, ∞i y 7→ 1 + 4 + y
tan R→R h− π2 , π2 i → R arctan
sin R→R [− π2 , π2 ] → [−1, 1] arcsin
The concept of functions can is important in functional languages. In such
languages functions can be defined, applied to arguments and the result evalu-
ated by a computer program.
1.1.2 Functions in functional languages
Functional progamming is an area of computer science where pure functional
(computer) programs consists largely of, function definitions. Examples of such
functional languages are Haskell, Clean, Gofer and Miranda. Although in math-
ematics it may be sufficient that a function exists with certain properties, in
functional programming functions are defined in an algoritmic fashion. That is,
given a function f and a value x, the image of x under f (if it exists) can be
calculated in finite time using only a limited number of well-defined rules.
This thesis will not describe all features of pure functional programming in
detail. For a good introduction the reader is refered to the books by Thompson
(1995) and Plasmijer and Eekelen (1993).
A Miranda-like syntax is used throughout this thesis. The definition of a
function g with k arguments takes the form
g pat 1 pat 2 . . . pat k
= value 1 , if guard 1
= value 2 , if guard 2
.
.
.
where
where-clauses
g pat 01 pat 02 . . . pat 0k
= ...
.
.
.
1.2. PATTERN MATCHING 3
g pat 001 pat 002 . . . pat 00k
= ...
.
.
.
.
.
.
When g is applied to actual arguments (i.e., values) a1 , . . . , ak , the result is
evaluated as follows. First the left hand side is considered, that is the part up
to and including the last pattern patk . The actual arguments are checked for
having the right form, by matching them against the patterns pat1 , . . . , patk
(more on pattern matching is said in the next section). If the patterns match,
identifiers may be bound by these patterns and evaluation proceeds in the right
hand side. The guards guard1 , guard2 , . . . are evaluated, and the first guardi
that evaluates to True the corresponding valuei is returned as the result of the
evaluation. If there is only one guard, the if, guard1 may be omitted. The
last guard may also be otherwise, which is equivalent to if True
Both the value∗ ’s and guard∗ ’s may contain identifiers that are bound by
patterns or function definitions in the where-clauses. Contrary to patterns
in the left hand side of a definition, patterns in a where-clause may lead to a
runtime exception if they do not match their right hand side.
It is possible, though, that the patterns pat1 , . . . , patk do not match, i.e.
a pattern is refused. However, g’s definition can consist of multiple equations,
each with different patterns: pat∗ ’s, pat0∗ ’s, pat00∗ ’s, and so on. For evaluation,
the first equation whose patterns match is used. That means that if one of the
pat∗ patterns does not match, the pat0∗ ’s are tried, then the pat00∗ ’s, and so on,
until an equation is found in which all patterns match the actual arguments. If
no patterns match, evaluation is halted and a runtime exception is thrown.
The next section shows examples of common patterns in functional lan-
guages.
1.2 Pattern matching
In this section an overview of different types of patterns are given as they are
used in languages such as Haskell (Peyton Jones, 2003) , Clean (Plasmeijer
& Eekelen, 2001) and Miranda (Thompson, 1995). The syntax between these
languages may differ slightly, but Miranda and in one case Amanda are taken
as a starting point.
1.2.1 Identifier pattern
The identifier pattern is the most simple type of pattern. An actual arguments
always matches and is bound to the identifier.
Example. Consider the function max2, that returns the greatest of two num-
bers. Note the first line, the type definition, that states that max2 takes two
numbers as arguments and returns a number as well.
max2 :: num → num → num
4 CHAPTER 1. INTRODUCING PATTERNS
max2 x y = x , if x > y
= y , otherwise
Using this definition, the maximum of the numbers 3 and 5 is computed easily.
max2 3 5
{ patterns match : x := 3 , y := 5 }
⇒ 3 , if 3 > 5
{ 3 > 5 ⇒ False , first guard fails }
⇒ 5 , if True
⇒ 5
Comments are shown between { curly braces }. Here the binding of x to 3
is denoted by x := 3. Binding x to 3 means 1 that each occurence of x can
be replaced by 3 (except when x bound again to some other value in a where
clause).
1.2.2 Constant pattern
Another pattern is the constant pattern that checks whether an actual argument
equals a constant. This pattern refuses the actual argument if it is not equal to
the constant.
Example. The function isSemiVowel takes a character as its arguments and
returns whether this character is a semi-vowel.
isSemiVowel :: char → bool
isSemiVowel ’w ’ = True
isSemiVowel ’y ’ = True
isSemiVowel _ = False
This definition consists of three equations. The last equation contains the _
pattern, which is an identifier pattern and may replaced by any ‘fresh’ identifier
that is not bound elsewhere.
With this definition, it is easily determined that the ’y’ character is a semi-
vowel.
isSemiVowel ’y ’
{ ’y ’ does not equal ’w ’; refuse first equation }
{ ’y equals ’y ’ , second pattern matches }
⇒ True
1 As is the case in any referential transparant language such as Miranda, Clean and Haskell
1.2. PATTERN MATCHING 5
1.2.3 List pattern
Lists are sequences of elements of the same type. Elements in a list are separated
by comma’s and enclosed by brackets. Some examples of lists are
[]
[5 , 12 , 13]
[[ True , False ] , [ False ] , []]
[ ’t ’ , ’i ’ , ’n ’ , ’a ’]
List of characters allow for a special notation using double quotes, so that the
last list can also be written "tina".
Any list can be considered as either the empty list, denoted Nil or [], or
as some head element x followed by a tail list xs. In the latter case we write
x:xs using the cons operator ‘:’. Thus, we can write the list [5, 12, 13] as
5:(12:(13:Nil)). The parenthesis are optional, so that 5:12:13:Nil is also
valid. In the list x:xs it is required that the elements in xs have the same type
as x.
A list patterns is of the form h:t, where h and t are patterns that match
the head and tail, respectively. Note that patterns may be nested : a pattern
may contain another pattern. A list pattern is refused if the actual argument is
the empty list, or if the head or tail pattern does not match.
Example. The join2 function, also written infix ‘++’, joins two lists. It is
defined recursively by
join2 :: [*] → [*] → [*]
join2 [] ys = ys
join2 ( x : xs ) ys = x : ( join2 xs ys )
The lists [1, 2] and [3, 4, 5] are joined as follows.
join2 [1 , 2] [3 , 4 , 5]
{ [1 , 2] does not equal []; refuse first pattern }
{ second pattern matches ; x := 1 , xs := 2 }
⇒ 1 : ( join2 [2] [3 , 4 , 5]
{ [2] does not equal []; refuse first pattern }
{ second pattern matches ; x := 2 , xs := [] }
⇒ 1 : 2 : ( join2 [] [3 , 4 , 5])
{ [] equals [] , first pattern matches }
⇒ 1 : 2 : [3 , 4 , 5]
⇒ [1 , 2 , 3 , 4 , 5]
List patterns allow for powerful computations, as the following example shows.
Example. Consider the prime function that generates the list of primes. Its
definition contains a list pattern (as well as a list comprehension, but that is
not discussed here).
6 CHAPTER 1. INTRODUCING PATTERNS
primes = sieve [2..]
sieve ( p : x ) = p : sieve [ n | n <- x ; n mod p > 0]
The list of primes is infinite and thus can never be evaluated completely. How-
ever, this definition does allow for the evaluation of an initial sublist of the list
of primes. For example,
take 5 primes
⇒∗ [2 , 3 , 5 , 8 , 13]
1.2.4 Tuple pattern
A tuple consists of a finite number of elements, possibly of different types.
Elements are seperated by comma’s en enclosed by brackets, and a tuple with
n elements is called an n-tuple. Some examples are
(1 , 2)
( ’t ’ , 1 , ’n ’ , ’a ’)
((1 , ’a ’) , ( ’z ’ , 2) )
A tuple matches a tuple pattern if they have the same number of elements and
each element matches the respective pattern in the tuple.
Example. A complex number a + bi (a, b ∈ R) can be represented by a 2-
tuple (pair ) of numbers (a, b). The definition for multiplication of two complex
numbers is straightforward.
complex == ( num , num )
multComplex :: complex → complex → complex
multComplex ( a0 , b0 ) ( a1 , b1 )
= ( a0 * a1 - b0 * b1 , a0 * b1 + a1 * b0 )
The complex product of (3 + 4i) · (−1 + 2i) is computed by
multComplex (3 ,4) ( -1 , 2)
{ a0 := 3 , b0 := 4 , a1 := -1 , b1 := 2 }
⇒ (3 * -1 - 4 * 2 , 3 * 2 + -1 * 4 }
⇒ ( -11 , 2)
resulting in −11 + 2i.
1.2. PATTERN MATCHING 7
1.2.5 Algebraic pattern
Algebraic types allow for labelling values of different types with a constructor
and then joining them in a type. A constructor is written with an uppercase
identifier and is defined to be accompanied by a finite number of values called
arguments. Examples of definitions with algebraic types and values are
bool ::= True | False
f u n c t i o n a l P r o g r a m m i n g I s O b s o l e t e :: bool
f u n c t i o n a l P r o g r a m m i n g I s O b s o l e t e = False
binTree ::= Leaf num | Node binTree binTree
myTree = Node ( Leaf 3) ( Node ( Leaf 4) ( Leaf 8) )
maybe * ::= Just * | Nothing
In these definitions True, False, Leaf, Node, Just and Nothing are the con-
structors, and they have zero, zero, one, two, one and zero arguments, respec-
tively.
The binTree is a binary tree that contains numbers. With the maybe type
one can specify that a result is not defined (Nothing), or that the result is
defined and has value v (Just v). In the maybe definition the asterisk ‘*’ is a
type variable, used for polymorphism, so that both Just 3 (of type maybe num)
and Just "ab" (of type maybe [char]) are valid expressions. One example of
its use is given in Chapter 3.
An algebraic pattern matches an algebraic value if it has the same construc-
tor and each argument matches. Note that constants, lists and tuples can be
expressed using algebraic types.
Example. Consider finding the sum of all numbers in a binary tree.
sumBinTree ( Leaf n ) = n
sumBinTree ( Node x y ) = sumBinTree x + sumBinTree y
Now summing up values in myTree proceeds as follows:
sumBinTree myTree
⇒ sumBinTree ( Node ( Leaf 3) ( Node ( Leaf 4) ( Leaf 8) ) )
{ Node ( Leaf 3) ( Node ( Leaf 4) ( Leaf 8) )
does not match Leaf x ; refuse first equation }
{ Node ( Leaf 3) ( Node ( Leaf 4) ( Leaf 8) )
matches Node x y ; x := Leaf 3 ,
y := Node ( Leaf 4) ( Leaf 8) }
⇒ sumBinTree ( Leaf 3)
+ sumBinTree ( Node ( Leaf 4) ( Leaf 8) )
{ Leaf 3 matches Leaf n ; n := 3 }
⇒ 3 + sumBinTree ( Node ( Leaf 4) ( Leaf 8) )
⇒∗ 3 + (4 + 8)
8 CHAPTER 1. INTRODUCING PATTERNS
⇒∗ 15
1.2.6 n+k pattern
The n+k pattern is a pattern that is only applicable to numbers. In its most
common form (e.g., Miranda and Gofer), it only matches nonnegative integers.
In an n+k pattern, the k is a constant number and n is een identifier. When ap-
plied to an actual argument a, n is bound to a-k. Intuitively we can understand
this as ‘solving’ the equation n+k=a for n, which leads to n=a-k.
Example. The power function for natural numbers can be defined by the use
of an n+k pattern. In this example k=1.
power _ 0 = 1
power b ( n +1) = b * power b n
Evaluation of 32 proceeds as follows
power 3 2
{ 0 does not equal 2; refuse first equation }
{ patterns match : b := 3 , n := (2 -1) }
⇒ 3 * power 3 1
{ 0 does not equal 1; refuse first equation }
{ patterns match : b := 3 , n := (1 -1) }
⇒ 3 * 3 * power 3 0
{ 0 equals 0; use first equation }
⇒ 3 * 3 * 1
⇒ 9
An extension to this pattern is available in the Gofer language, as a result of a
discussion on the Haskell mailinglist initiated by Tony Davie (as cited by Jones,
1991). Gofer allows for c * p and p + k patterns, where c > 1 and k > 0 are
constants. It extends the syntax using a grammer so that these patterns can be
nested.
pattern → . . . | pattern + integer | integer ∗ pattern
The semantics of a nested pattern of this form is comparable to that of the
standard n+k pattern.
Example. Tony Davie (as cited by Jones, 1991) gives the following more
efficient definition of the power function
power ’ x 0 = 1
power ’ x (2* n ) = xn * xn
where xn = power ’ x n
power ’ x (2* n +1) = x * power ’ x (2* n )
1.2. PATTERN MATCHING 9
The second and third clause use a c*p and a c*p+k pattern (with c=2 and k=1),
respectively. Evalution of 22 using this definition goes as follows:
power ’ 2 2
⇒ power ’ 2 2
{ 0 does not equal 2 , first equation fails }
{ 2 equals 2* n for n := 1
⇒ xn * xn
where
xn
= power ’ 2 1
{ 1 does not equal 0 , first equation fails }
{ 1 does not equal 2* n for any n , second
equation fails }
{ 1 equals 2* n +1 for n := 0 }
⇒ 2 * power ’ 2 0
⇒ 2
⇒ 2 * 2
⇒ 4
Note that this pattern matches only if the to-be-bound identifier can be given
a non-negative integer value.
1.2.7 As pattern
The as pattern allows for binding identifiers multiple times to (parts of) the
actual argument. That is, if pat is a pattern, (x=pat) is a binding pattern
that binds x to pat if pat matches the actual argument (in Haskell the x@pat
notation is used). It is assumed that x is a free identifier.
Example. The function headListTail gets a non-empty list as argument. It
returns the head of the list, followed by the complete list, followed by the tail
of the list.
headListTail ( list =( x : xs ) ) = x : list ++ tail
Evaluation of this function applied to the list abcde leads to
headListTail " abcde "
{ list pattern matches : x := ’a ’ , xs := " bcde " }
{ binding pattern matches : list := " abcde "
⇒ ’a ’ : " abcde " ++ " bcde "
⇒ " aabcdebcde "
10 CHAPTER 1. INTRODUCING PATTERNS
1.2.8 Equivalence pattern
The equivalence pattern allows for multiple occurences of an identifier in one
equation. Not every language supports this: Haskell and Miranda allows for such
patterns but not Amanda. An equivalence pattern matches if every occurence
of an identifier agrees on a value for that identifier.
Example. Consider the function that determines the greatest common devisor
of two numbers.
gcd x x = x
gcd x y = gcd (x - y ) y , if x > y
= gcd x (y - x ) , otherwise
The first line shows an example of an equivalence pattern, stating that the
greatest common divisors of two equal numbers is that number itself. Using
this definition, the greatest common divisor of 18 and 9 is calculated as
gcd 18 9
{ x := 18 , x := 9 , conflict in first equation , no
match }
{ x := 18 , y := 9 , second equation matches }
{ 18 > 9 ⇒ True }
⇒ gcd (18 -9) 9
⇒ gcd 9 9
{ x := 9 , x := 9 -- no conflict , matches }
⇒ 9
Except when stated otherwise, in the remainder of this thesis it is assumed
that any function definition does not contain an equivalence pattern. However,
as we will see in Section 2.4.2, using a caret notation equivalence patterns can
be mimicked while still each identifier is bound only once.
Several researchers have suggested new forms of pattern matching that are
beyond standard pattern matching described so far. In the next chapter yet an-
other form of pattern matching is introduced. The relation with other proposed
pattern matching extensions is discussed in Section 4.2.
1.3 Conclusion
This chapter gave an overview of function definitions and standard pattern
matching. Function definitions may contain patterns, guards, expressions and
where clauses. Examples of existing patterns are the identifier, constant, list,
algebraic, tuple, n+k, as and equivalence pattern.
In the next chapter a new type of patterns is introduced: application pat-
terns.
Chapter 2
Application patterns
2.1 Introduction
In the previous section the necessary background about functions and pattern
matching was discussed. In this chapter application patterns are described. The
structure of this chapter is as follows: Section 2.2 introduces the concept of ap-
plication patterns, initially in a basic form that is extended with refutability.
Section 2.3 adds application patterns with an arbitrary number of arguments.
In Section 2.4 some refinements are discussed. Section 2.5 describes how ap-
plication patterns can be considered as a general form of most other patterns.
Section 2.6 lists the definition of inverse functions for many standard functions.
Finally the use of application patterns is discussed in Section 2.7.
2.2 Application patterns
Application patterns as presented here were introduced by Oosterhof, Hölzen-
spies, and Kuper (2005). This section describes such patterns, starting with a
basic from to which refutability is added.
2.2.1 Basic application pattern
In its most simple form, an application pattern is a pattern of the form f x.
As any other pattern, application patterns can be used in both the left hand
side of function definitions and in where clauses. The use of an application
pattern requires that an inverse function f−1 is defined. Such an inverse may
be available as a standard function of the programming language (see 2.6), it
can be derived by the systems (a discussion of this subject is beyond the scope
of this thesis) or it must be defined by the programmer. For now it must be
assured that for an actual argument a, f (f−1 a)= a for every value for which
f and f−1 are defined.
When an actual argument b is matched against a pattern f x, x is bound
to the value of the inverse function f−1 applied to b. The intuition behind this
procedure is that
f x=b ⇐⇒ x = f−1 b
11
12 CHAPTER 2. APPLICATION PATTERNS
Note that matching against the pattern f x does not involve checking its syn-
tactic structure. Contrary, an application pattern matches against the semantic
value of the actual argument. Application patterns can be nested and used
together with any other kind of pattern.
Example. The succ function computes the successor of any non-negative in-
teger and has an inverse function succ−1 . Their definitions are trivial.
succ n = n + 1 , if n ≥ 0
succ −1 n = n - 1 , if n ≥ 1
Now consider yet another definition of the power function, one that uses an
application pattern.
power ’ ’ _ 0 = 1
power ’ ’ b ( succ n ) = b * power ’ ’ b n
In the second equation, the second argument succ n is an application pattern
that consists of the function succ applied to an argument n. Note that this
pattern resembles an n+k pattern. Evaluation of power’’ 2 5 now proceeds as
follows.
power ’ ’ 2 5
{ 5 does not equal 0 , refuse first equation }
{ b := 2
{ ’ solve ’
succ n = 5
n = succ −1 5
⇒ 4 }
n := 4 }
⇒ 2 * power ’ ’ 2 4
⇒∗ 32
Example. The zip function zips a pair of lists into a list of pairs and has an
inverse zip−1 .
zip :: ([*] , [**]) → [(* , **) ]
zip (( x : xs ) , ( y : ys ) ) = (x , y ) : zip ( xs , ys )
zip _ = []
zip −1 :: [(* , **) ] → ([*] , [**])
zip −1 (( x , y ) : xys ) = ( x : xs , y : ys )
where
( xs , ys ) = zip −1 xys
−1
zip [] = ([] , [])
2.2. APPLICATION PATTERNS 13
Note that zip−1 always returns lists of equal length, whereas zip is also defined
for pairs of lists with unequal length. This means that zip−1 is a partial inverse
of the function zip.
Suppose a list of (x, y) coordinates is given. The function upperLeft returns
the coordinates of the upperleft corner of the smallest rectangle (with sides
parallel to the x and y axis) that contains all points of the list. It can be
defined with an application pattern.
upperLeft :: [( num , num ) ] → ( num , num )
upperLeft ( zip ( xs , ys ) ) = ( min xs , max ys )
Here the zip (xs, ys) is an application pattern that consists of the function
zip applied to the pair (xs, ys). For an intuitive understanding of this defini-
tion, suppose upperLeft is applied to an actual argument coords. The meaning
of the application pattern zip (xs, ys) is that, for some lists of x-coordinates
xs and y-coordinates ys, coords is the result of zipping these two lists. The
rectangles’ upperleft corner is calculated by taking the minimum and maximum
from the lists of x-coordinates xs and y-coordinates ys, respectively.
The upperleft point for the list of coordinates [(1,4), (-2,3), (5,2)] is
evaluated as follows.
upperLeft [(1 ,4) , ( -2 ,3) , (5 ,2) ]
{ { ’ solve ’
zip ( xs , ys ) = [(1 ,4) , ( -2 ,3) , (5 ,2) ]
( xs , ys ) = zip −1 [(1 ,4) , ( -2 ,3) , (5 ,2) ]
⇒∗ ([1 , -2 ,5] , [4 ,3 ,2]) }
xs := [1 , -2 ,5] , ys := [4 ,3 ,2] }
⇒ ( min [1 , -2 ,5] , max [4 ,3 ,2])
⇒ ( -2 , 4)
2.2.2 Refutable application patterns
Just like some other patterns, application patterns can be refutable. Suppose
that the pattern f x is matched against an actual argument a. If for all possible
values of x, a cannot be the result of f x, the pattern is refused. This is indicated
by a partial definition of f−1 . In Chapter 3 it is shown how this approach allows
for rewriting code that supports refutable application patterns.
Example. Consider the builtin sine function sin. Since the range of this
function is [−1, 1], its inverse sin−1 is only defined for values in this range.
sin −1 x = arcsin x , if -1 ≤ x ∧ x ≤ 1
Now consider the definition of h that contains an application pattern with the
sine function.
14 CHAPTER 2. APPLICATION PATTERNS
h ( sin a ) = a * a
h x = x - 2
When applied to an actual argument b, it depends on the value of this√
argument
which of the two equations is used. When h is applied to 0.866 ≈ 3/2, the
first equation is used which results in 1.0965 ≈ π 2 /9.
h 0.866
{ { ’ solve ’
sin a = 0.866
a = sin −1 0.866
{ -1 ≤ 0.866 ∧ 0.866 ≤ 1 ⇒ True ,
guard succeeds }
⇒ 1.0471 }
a := 1.0471 }
⇒ 1.0471 * 1.0471
⇒ 1.0965
However, when applied to a value with a greater absolute value than one, the
second equation is used and its value is decreased by two.
h 100
{ { ’ solve ’
sin a = 100
a = sin −1 100
{ -1 ≤ 100 ∧ 100 ≤ 1 ⇒ False ,
guard fails }
solving fails }}
{ second pattern matches : x := 100 }
⇒ 100 - 2
⇒ 98
Note that despite the fact that the application pattern sin a does not match
100, no runtime exception is thrown but the next equation is tried. In the
examples shown so far only function applications with one argument were used.
In the next section this is extended to an arbitrary number of arguments.
2.3 Currying application patterns
In this section curried application patterns are discussed. The notions of a
cousin and generalized inverse of a function are introduced, as well as a backtic
notations that allows for defining generalized inverses.
2.3.1 Currying
Many functions take multiple arguments; we have already seen this in the max2
and power functions. However, a function that takes n arguments can be seen
2.3. CURRYING APPLICATION PATTERNS 15
as a higher order function that takes one argument and returns a function that
takes n−1 arguments. This new function can again be applied to one argument,
yielding another function that takes n − 2 arguments, and so on. After n − 1
steps all arguments are handled. Considering functions with multiple functions
as sequences of a number of higher order functions that all take one argument
is called currying.
Example. The power function takes two arguments, a base b and an an ex-
ponent x, and returns a number bx . It can be considered as a curried function,
with type
power :: num → ( num → num )
If power is applied to an actual base argument (say 2), the result is a function
power 2 :: ( num → num )
that takes one argument and returns two-to-the-power-of-that-argument. When
power 2 is applied to another actual argument (say 5) the result is the value
32.
power 2 5 :: num
power 2 5 ⇒ 32
However, applying the idea of application patterns directly to curried func-
tions would yield a typing problem. A function f : A → B takes one argument,
and its inverse is of type f −1 : B → A. But what is the type of, say, the inverse
of the power function? Using the rule for functions with one argument would
yield
!!! power −1 :: ( num → num ) → num
but this would mean that the inverse of the power function would take a higher
function as its argument. This approach has two problems, the first being that
equality of higher order functions is undecidable (this is discussed in more detail
in Section 4.3.2). The second problem is that is unclear what the meaning of
such an inverse would be. However, for the power function meaningful inverse-
like functions can be defined, because if the result bx and one of the arguments
(b or x) is known, the other argument can be found back:
bx = s ⇐⇒ b = s1/x
ln s
⇐⇒ x=
ln b
Thus, we need a generalized form of inverse functions. For this we need the
concept of cousins of a function.
16 CHAPTER 2. APPLICATION PATTERNS
2.3.2 Cousins of functions
Suppose f is a function that takes n arguments
f : A0 → · · · → An−1 → B
with
f x0 · · · xn−1 = expr
For now it is assumed that the A∗ ’s and B types do not contain an ‘→’—but
for a discussion of the possibilities for such functions, see Section 4.3.2.
Note that we can partition the list of indices 0, . . . , n − 1 into two sublists
i1 , . . . , ik and j1 , . . . , jm that both keep their indices in order. We write
[i1 , . . . , ik ] ∪ [j1 , . . . , jm ] = [0, . . . , n − 1]
where the ∪ operator merges two ordered lists into a new ordered list.
The function
fic1 ,...,ik : Aj1 → · · · → Ajm → (Ai1 , . . . , Aik ) → B
so that
fic1 ,...,ik xj1 · · · xjm (xi1 , . . . , xik ) = f x0 · · · xn−1
is called a cousin of f with respect to i1 , . . . , ik . Thus a cousin of f more or less
calculates the same as f itself, it only takes its argument in a different order.
The trivial cousin of f is the cousin of f with respect no none of its arguments
and equals f itself: f = f∅c (so that k = 0, m = n and jp = p − 1).
Example. The repeat function takes a number n and an element c as its
arguments and returns a list with n times the element c.
rep :: num → * → [*]
rep 0 c = []
rep ( n +1) c = c : rep n c
The cousin of rep with respect to the first and second argument is
rep c1,2 :: ( num , *) → [*]
rep c1,2 (0 , c ) = []
rep c1,2 ( n +1 , c ) = c : rep c1,2 (n , c )
Example. The join3 function takes three lists and joins them.
join3 :: [*] → [*] → [*] → [*]
join3 x y z = x ++ y ++ z
It has multiple cousins, two of them being
2.3. CURRYING APPLICATION PATTERNS 17
join3 c2 x z y = x ++ y ++ z
join3 c1,3 y (x , z ) = x ++ y ++ z
2.3.3 Generalized inverse
The concept of cousins, as described in the previous section, allows for defining
inverse functions for curried functions.
Consider the function
f : A0 → · · · → An−1 → B
that has a cousin
fic1 ,...,ik : Aj1 → · · · → Ajm → (Ai1 , . . . , Aik ) → B
with respect to i1 , . . . , ik (hence [i1 , . . . , ik ] ∪ [j1 , . . . , jm ] = [0, . . . , n − 1]).
The generalized inverse of f with respect to i1 , . . . , ik is a function
fi−1
1 ,...,ik
: Aj1 → · · · → Ajm → B → (Ai1 , . . . , Aik )
such that
fi−1 x · · · xjm y = (xi1 . . . , xik )
1 ,...,ik j1
if and only if
fic1 ,...,ik xj1 · · · xjm (xi1 . . . , xik ) = y
that is, if and only if
f x0 · · · xn−1 = y
We call such a function an inverse (function) on its i1 − 1st, . . . , and ik − 1th
argument.
Note that both fic1 ,...,ik and fi−1
1 ,...,ik
can be parametrized by m parameters. In
a parametrized form, these two functions are inverse functions, i.e.
fi−1 x · · · xjm = (fic1 ,...,ik xj1 · · · xjm )−1
1 ,...,ik j1
The trivial inverse of f is the inverse of f on none of its arguments. It has the
type
f∅−1 : A0 → · · · → An−1 → B → ()
and is informally specified by
f∅−1 x0 . . . xn−1 expr = (), iff x0 . . . xn−1 = expr
Note that his inverse is not defined for values in which the guard is false.
For ease of notation, we write the generalized inverse function
fi−1
1 ,...,ik
in Ascii using a backtic notation as
18 CHAPTER 2. APPLICATION PATTERNS
f ‘[ i1 , ... , ik ]
Note that the backtic ‘ is not an operator: f‘[ i1 , ..., ik ] must be consid-
ered as a (systematically named) identifier. With this notation (generalized)
inverse functions can be defined that are used in matching application patterns.
Example. Since a function can have many cousins, it can have many inverses
too. For the power function two meaningul inverse functions can be defined,
namely an inverse on its first argument
power ‘[0] :: num → num → num
power ‘[0] x s = s ^ (1 // x )
and an inverse on its second argument
power ‘[1] :: num → num → num
power ‘[1] b s = ( ln s ) // ( ln b )
Both can be definied simultaniously.
√
The sqroot function · takes the square root from a non-negative number.
Its definition contains an application pattern with the power function.
sqroot ( power x 2) = x
√
For the evaluation of 81, it must be decided which inverse of the power function
must be used. Since in the application pattern power x 2 the first argument is
a variable whereas the second is known (a constant), we choose for the inverse
on the first argument power‘[0]
sqroot 81
{ { ’ solve ’
power x 2 = 81
{ choose power ‘[0] }
x = power ‘[0] 2 81
⇒ 9 }
x := 9 }
⇒ 9
Thus, when multiple inverses are defined the choice which inverse is choosen
depends on which arguments are known. If multiple inverses are possible, it is
the programmer’s responsability to ensure that it does not matter which inverse
function is choosen.
2.3. CURRYING APPLICATION PATTERNS 19
Example. The repeat function has an inverse on its first and second argument.
Given a list, rep‘[0,1] returns a pair with the length of the list and the first
element—but only if all elements in the list are equal. Otherwise the rep‘[0,1]
is not defined. The rep‘[0,1] function is not defined for an empty list, since the
typing system requires that the type of the repeated element is known. Thus,
strictly speaking, rep‘[0,1] is only a partial inverse of rep.
rep ‘[0 ,1] :: [*] → ( num , *)
rep ‘[0 ,1] [ x ] = (1 , x )
rep ‘[0 ,1] ( x : rep n y ) = ( n +1 , x ) , if x = y
Note that the second equation contains a (nested) application pattern with the
repeat function itself. Thus, this definition of rep is recursive.
Consider the function f that is defined with an application pattern with rep.
f ( rep n x ) = x : rep n ’. ’
The evaluation of f applied to a list of two ’a’’s uses the inverse function
rep‘[0,1]
f " aaa "
{ ’ solve ’
rep n x = " aa "
(n , x ) = rep ‘[0 ,1] " aa "
{ " aa " does not match [ x ] }
{ " aa " might match x : rep n ’ y
x ’ := ’a ’ , rep n ’ y := " a "
{ ’ solve ’
rep n ’ y = " a "
(n ’ , y ) = rep ‘[0 ,1] " a "
⇒ (1 , ’a ’) }
n ’ := 1 , y := ’a ’
{ x ’= y ⇒ True } }
⇒ (n ’+1 , x ’)
⇒ (2 , ’a ’)
n := 2 , x := ’a ’ }
⇒ ’a ’ : rep 2 ’. ’
⇒ " a .."
From this definition, two other inverse rep functions can be derived. The first
is used when the repeated element is known but the length of the list must be
computed,
rep ‘[0] :: * → [*] → num
rep ‘[0] y ( rep n x ) = n , if x = y
whereas the other is used if the length of the list is known and the repeated
element must be computed.
20 CHAPTER 2. APPLICATION PATTERNS
rep ‘[1] :: num → [*] → *
rep ‘[1] n ( rep m x ) = x , if m = n
Both definitions, when applied to actual arguments, would make implicit use of
rep‘[0,1]. Note that the definition for rep‘[0] is not defined for an empty list,
although in this case such a definition would make sense. A separate definition
of rep‘[0] would fix this issue.
In this section the basic application pattern was introduced. Refutability
and the concept of generalized inverses that allow for multiple inverses were
added. The next section discusses some refinements to these ideas.
2.4 Some refinements
This section describes how application patterns could be used in where clauses,
lambda abstractions and list comprehensions. Also the caret notation is intro-
duced. This notation allows for more flexible use of bound identifiers in patterns.
Finally extraction functions are discussed.
2.4.1 Pattern expressions
So far we have only dealt with application patterns in the left hand side of func-
tion definitions. Since ordinary patterns can also be used in lambda abstrac-
tions, where clauses and list comprehensions, it is proposed that application
patterns can be used in these expressions. Some examples are:
where clauses such as an application pattern that binds n in
...
where
2^ n = 8
(Note that the above might be read as a definition for the power function
using a constant pattern 2. This issue is addressed in the next section.);
lambda abstractions such as the function that maps every number 2n to the
number n2
(2^ n → n ^2) 256
and
list comprehensions such as the list of numbers
[ n ^2 | 2^ n <- [1..8]]
2.4. SOME REFINEMENTS 21
With application patterns in function definitions the semantics of application
patterns in lambda abstractions and list comprehensions are easily defined. Here
it is left as an exercise for the reader. The implementation of this functionality
is discussed in Section 3.4.6
Some ambiguities may arise in application patterns. To address this issue a
caret notation is introduced in the next section.
2.4.2 Caret notation
Application patterns allow for more flexible syntax in function definitions. How-
ever, their use may lead to ambiguities. A caret notation is introduced for iden-
tifiers that indicates that an identifier (or its inverse function, in the case of an
application pattern) must be retrieved from the context.
Example. Consider Haskell (Peyton Jones, 2003), where an expression of the
form n+k can be used in the left hand side of a where clause, as in
...
where
n + 1 = expr
Now this reads as a (re)definition of the addition function in a where clause.
But with this syntax, how could an n+k pattern be used in a where clause? The
solution that has been chosen in Haskell is to surround the expression n + 1 by
parenthesis, as in
...
where
( n + 1) = expr
A similar problem would arise for the use of an application pattern in a where
clause. Rather than surrounding the pattern by parenthesis (which adds even
more semantics to these tokens), an alternative solution is proposed: the caret
^ identifier-prefix notation. To indicate that a function application should be
used to bind arguments (instead of defining the function itself) the function
name must be prefixed by a caret ^. Obviously the prefixed function identifier
must have an inverse defined in the context.
Example. With the caret notation the definition of sqroot’ could be written
sqroot ’ x
= y
where
^power y 2 = x
where the caret indicates that the inverse of the power function is retrieved from
the context. Note that such ambiguities cannot only arise in where clauses,
22 CHAPTER 2. APPLICATION PATTERNS
not in the left hand side of function definitions, in lambda abstractions or in list
comprehensions. In these cases the caret is optional at the function identifier.
Use of the caret for operators would make expressions less readible. Since
operators will rarely be redefined in a where clause, it is proposed here that the
caret is left out for operators too.
Example. Use of an application function with the addition function + in a
where clause, as in
| f y = x + y
| where
| x ^+ 2 = y
results in a less readible ^+ operator. Note that the same problem applies to
other operators, which would be written as, for instance, ^++, ^:, ^! and even
^^. As the caret is left out for operators, the definition of f can be written
| f y = x + y
| where
| x + 2 = y
Sometimes it may be desired to use identifiers from the context in an application
pattern. To allow for this the caret notation is extended to any identifier, not
just a function name in a function application. The semantics of an identifier
^i is a constant with the value of i derived from the context (assumed that
that ^i not the function identifier in an application ^iargs .
Example. The definition of the factorial function can also be written
fac ^ zero = 1
fac n = n * fac (n -1)
zero = 0
Example. Yet another definition of square root is
| sqroot ’ ’ ( power x ^ two ) = x
| two = 2
The caret notation must be used with care, as it allows for different semantics
of almost identifical expressions, especially in where clauses.
2.4. SOME REFINEMENTS 23
Example. Suppose the function f takes two arguments in the context
x = 2
f ‘[1] x s = ...
f ‘[0 ,1] s = ...
where the inverse functions f‘[0] and f‘[0,1] are both non-refutable.
Table 2.1 shows variants of its use (with and without carets) in a where
clause, and for each variant an equivalent where clause without application
patterns. This is an example of what is presented in Section 3.3 more generally,
namely an approach to rewrite code with function definitions and where clauses
into equivelant code without application patterns.
Table 2.1: Some where clauses and equivalent clauses
Example where clause Equivalent where clause without ap-
plication patterns and carets
... ...
where where
f ^ x y = expr f 2 y = expr
... ...
where where
^ f x y = expr (x , y ) = f ‘[0 ,1] expr
... ...
where where
^ f ^ x y = expr y = f ‘[1] 2 expr
As mentioned before, in a nested application pattern like g (f x y) the
caret may be left out in front of f, since no ambiguity can arise. Thus, such a
pattern is equivalent to g (^f x y).
The caret notation can be extended marginally by assuming that in a left
hand side of a function definition, the context of an identifier also includes other
patterns. Equivalence patterns are not supported by all languages1 . The caret
notation allows for mimicking such a pattern.
1 Amanda is a clear example. Without extra compiler support, Haskell also requires that
in the left hand side ‘The set of patterns must be linear—no variable may appear more than
once in the set.’ (Peyton Jones, 2003)
24 CHAPTER 2. APPLICATION PATTERNS
Example. Consider the following definition of the function that computes the
greatest common divisor for two positive integers.
gcd x ^x = x
gcd ( x + ^ y ) y = gcd x y
gcd x ( x + ^ y ) = gcd x y
The first equation contains an identifier pattern and a constant pattern that
together mimick an equivalence pattern. In the first pattern x is bound the
actual argument, in the second pattern the actual argument is compared to the
value that is bound in the first pattern, i.e. it is compared to the first actual
argument. The second equation contains an n+k pattern. In this pattern the
value of y is used from the context to compute x. This means that y is bound
in the second pattern before the first pattern is evaluated.
In general, since application patterns may be refutable, the caret notation as
proposed here may yield a different order of pattern matching during evaluation.
Consider the definition of f in
f ( power ^ x y ) ( sin x ) = x * y
f _ _ = 0
that contains two application patterns. During evaluation, the first pattern
requires that the value for x is known. This value must be retrieved from the
context, in this case from the second pattern h x. Thus, first the second pattern
must be matched against the second argument, and only then the first pattern
can be matched. If the second pattern in the first equation does not match the
second equation is used.
In brief, with the caret notation it is denoted explicitly which identifiers
are bound and where. It allows for mimicking equivalence patterns and adds a
limited amount of power to existing pattern matching.
2.4.3 Extraction functions
So far we have assumed that defined inverse functions are really the inverse
of some function, and that such inverse functions can be defined more or less
uniquely. However, for application patterns both assumptions are not really
required. In fact, the programmer may go as far as he wants, as far as he
assures that the defined inverse functions are used properly.
Example. The upperLeft function
upperLeft :: [( num , num ) ] → ( num , num )
upperLeft ( zip ( xs , ys ) ) = ( min xs , max ys )
contains an application pattern with the zip function. For its use the definition
of zip‘[0] is required. However, the definition of the zip function is not
really required for this definition of upperLeft to work. If an application
patterns contains a function that is not a partial inverse, this function is called
an extraction function.
2.4. SOME REFINEMENTS 25
2.4.4 Programmer’s responsibilities
Another issue is the use of an application pattern for which different inverse
functions can be defined for the same set of arguments.
Example. The function join2 joins two strings
join2 x y = x ++ y
for which clearly two inverses can be defined, one for each argument.
join2 ‘[0] y s = x , if y = z
where
(x , z ) = split ((# s ) - (# y ) ) s
join2 ‘[1] x s = y , if x = z
where
(y , z ) = split (# x ) s
However, an inverse on both inverses is possible too, but for this multiple defin-
itions are possible. That is, if the list s is the result of x ++ y, the list s can be
split at, e.g., the beginning, middle or end to yield original values for the lists x
and y. These variants can be defined by
join2 ‘[0 ,1] s = ([] , s )
join2 ‘[0 ,1] ’ s = split ( (# s ) / 2) s
join2 ‘[0 ,1] ’ ’ s = (s , [])
All three are partial inverse functions of join2, since for any lists x and y it
holds that
join2‘[0,1] s ⇒∗ (x, y) =⇒ join2 x y ⇒∗ s
join2‘[0,1]’ s ⇒∗ (x, y) =⇒ join2 x y ⇒∗ s
join2‘[0,1]’’ s ⇒∗ (x, y) =⇒ join2 x y ⇒∗ s
However, application patterns that rely on such definitions must be used with
great care. Consider the following definition of mergeSort that sorts a list.
merge :: [*] → [*] → [*]
merge ( x : xs ) ( y : ys ) = x : merge xs ( y : ys ) , if x < y
= y : merge ( x : xs ) ys , otherwise
merge xs ys = xs ++ ys
mergeSort :: [*] → [*]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort ( join2 ’ x y ) = merge ( mergeSort x )
( mergeSort y )
26 CHAPTER 2. APPLICATION PATTERNS
The last equation of the definition of mergeSort contains an application pattern
of the join2’ function. This means that when mergeSort is applied to an actual
list argument with length two or more, the inverse function join2‘[0,1]’ is
used to split the argument in two lists of (almost) equal length. However, the
reader may verify that if the application pattern would contain either the join2
or the join2’’ function, use of the mergeSort function would lead to an infinite
loop for any list with length greater than one. In this case, renaming join2’
to, e.g., join2halves would avoid confusion and ease debugging.
These examples show that the programmer has a great responsibility in
the definitions of inverse functions and in the use (and misuse) of application
patterns.
In this section applications patterns in expressions was discussed, as well as
the caret notation and programmer’s responsabilities. With these considerations
in mind, in the next section it is shown how application patterns relate to other
patterns.
2.5 Application patterns as a generalization
In this section it is shown how application patterns can be seen as a general
form of most of the other patterns discussed in Section 1.2. I consider this as
mostly of theoretical importance: is is not my intention to really rewrite all
patterns by application patterns, not in least because performance may suffer
from such a procedure.
2.5.1 List pattern, revisited
A list pattern x:xs matches any non-empty list, binding x to the head and xs
to the tail of that list. To avoid confusion, I define the cons operator : as a
function with a full name:
cons :: * → [*] → [*]
cons x xs = x : xs
This functions has an inverse on both its arguments that accepts all lists except
the empty list.
cons ‘[0 ,1] xs = ( hd xs , tl xs ) , if xs 6= []
Thus, the list pattern x:xs can also be expressed by the application pattern
cons x xs2 .
2.5.2 Algebraic pattern, revisited
In any algebraic pattern, the constructor can be regarded as an injective function
on all of its arguments.
2 A list pattern can also be expressed by an algebraic pattern. Since it is shown that
algebraic patterns are a special kind of application patterns, this provides another way to
show that list patterns can be expressed by an application pattern.
2.5. APPLICATION PATTERNS AS A GENERALIZATION 27
Example. Miranda and Amanda do not support this, but Haskell provides
direct support for such a construction. In this approach, the division tree type
divTree ::= Lit num | Div divTree divTree
defines two functions that have the types
Lit :: num → divTree
Div :: divTree → divTree → divTree
These functions are injective on all of their arguments, hence the inverses
Lit ‘[0] :: divTree → num
Div ‘[0 ,1] :: divTree → ( divTree , divTree )
exist and their definitions follow directly from the type definition of divTree.
This approach can be used for any algebraic pattern; hence the algebraic pattern
can be seen as a special kind of application pattern. Note that the list pattern
is also a special case.
2.5.3 Tuple pattern, revisited
A tuple pattern can be expressed by an algebraic pattern, as a tuple type can
be expressed by an algebraic type.
Example. The most general 3-tuple type (*, **, ***) is expressed by the
algebraic type
threeTuple * ** *** ::= ThreeTuple * ** ***
With this algebraic type, the tuple pattern (2, x, True) where x is a free
identifier is expressed by
ThreeTuple 2 x True
and it can be matched as any other algebraic pattern.
2.5.4 n+k pattern, revisited
With application patterns, an n+k pattern can be considered as just an appli-
cation with the addition function
plus x y = x + y
28 CHAPTER 2. APPLICATION PATTERNS
For the plus function an inverse function on its first argument can be defined.
plus ‘[0] k n = n - k , if k ≥ 0 ∧ n ≥ k
Note that a variant of this pattern that matches any value (positive or negative)
and allows for any value of k (positive or negative) can be obtained by removing
the guard in this definition.
Likewise, an c*p pattern can be seen as an application with the multiplica-
tion function
times x y = x * y
for which the inverse on its second argument is defined by
times ‘[1] c p = p / c , if c > 0 ∧ divRem p c = 0
The variant that matches any value (6= 0) can be obtained by replacing the
guard by the condition c 6= 0.
2.5.5 Constant pattern, revisited
The constant pattern only checks an actual argument for having a certain con-
stant value. Since a constant can be considered as a constructor without argu-
ments this translates directly to inverse functions. For example, the constants
3 :: num
False :: bool
’w ’ :: char
have inverses that informally may be written
42 ‘[] x = () , if x = 42
False ‘[] x = () , if ~ x
’w ’ ‘[] x = () , if x = ’w ’
Note that these inverses, if they match, only returns the empty tuple (), which
means that a match will not bind any identifiers.
The previous patterns could be expressed directly by application patterns. The
as pattern can be expressed indirectly by use of an helper function.
2.6. STANDARD INVERSE FUNCTIONS 29
2.5.6 As pattern, revisited
The as pattern allows for binding identifiers multiple times to (parts of) the
actual argument. It can be expressed indirectly by using the theSame function
theSame x y = x , if x = y
that has an inverse on both its arguments
theSame ‘[0 ,1] x = (x , x )
With this definition, the as pattern x=pat (in Haskell: x@pat) can be expressed
by the application pattern theSame x pat.
Example. The definition
headListTail ( list =( x : xs ) ) = x : list ++ tail
is rewritten into
headListTail ( theSame list ( x : xs ) ) = x : list ++ tail
2.5.7 Equivalence pattern, revisited
Equivalence patterns cannot be expressed by application patterns. However, the
caret notation does allow for rewriting an equivalence pattern into an identifier
pattern and one or more constant patterns. That is, suppose x occurs multiple
times in a list of patterns. Then every occurance of x except one can be replaced
by the constant pattern ^x that has the value of x. We have seen an example
already in Section 2.4.2.
To conclude, application patterns extended with the caret notation can be
seen as a general form of all patterns except for the identifier pattern.
This overview showed how existing patterns can be seen as special cases of
application patterns. In the next section it is shown that for many standard
functions one or more inverse functions can be defined.
2.6 Standard inverse functions
In this section inverse function definitions are given for standard functions. It
is shown that for many standard functions one or more inverses exist. All their
definitions can be made part of a standard library for inverse functions.
30 CHAPTER 2. APPLICATION PATTERNS
2.6.1 Arithmetic operators
For most arithmetic operators one or two inverses exist. For each function its
type, as well as its inverses are given. For clearity I use alphanumeric identifiers
but indicate the operator characters between brackets.
The inverse definition for the modulo operator % is debatable, as well as that
for the abs function that is more like a guard that checks for a non-negative
argument. As discussed in Section 2.5.4 about the n+k and p*c pattern, for
addition and multiplication the check for a positive argument is language choice.
Here I leave these checks out.
1 || negate [ - ( prefix ) ]
2 || neg :: num → num
3 neg ‘[0] x = neg x
4
5 || addition [+]
6 || plus :: num → num → num
7 plus ‘[0] y s = s - y
8
9 plus ‘[1] x s = s - x
10
11 || subtraction [ - ( infix ) ]
12 || minus :: num → num → num
13 minus ‘[0] y s = s + y
14 minus ‘[1] x s = s - x
15
16 || multiplication [*]
17 || times :: num → num → num
18 times ‘[0] y s = s / y , if y 6= 0
19 = 0 , if s = 0
20
21 6 0
times ‘[1] x s = s / x , if x =
22 = 0 , if s = 0
23
24 || division [/]
25 || div :: num → num → num
26 div ‘[0] y s = s * y
27
28 div ‘[1] x s = x / s , if s 6= 0
29
30 || modulo [%]
31 || mod :: num → num → num
32 mod ‘[1] x s = hd fs , 6 []
if fs =
33 where
34 fs = [ i | i <- [( s +1) ..]
35 ; (x - s ) mod i = 0 ]
36
37 || absolute value
38 || abs :: num → num
39 abs ‘[0] x = x , if x ≥ 0
2.6. STANDARD INVERSE FUNCTIONS 31
40
41 || natural logaritm
42 || ln :: num → num
43 ln ‘[0] x = e ^ x
44
45 || e power
46 || exp :: num → num
47 exp ‘[0] x = ln x , if x > 0
48
49 || power [^]
50 || power :: num → num → num
51 power ‘[0] x s = s ^ (1 // x )
52
53 power ‘[1] b s = ( ln s ) // ( ln b )
2.6.2 Goniometric functions
Inverses for the goniometric functions are easily defined. As the arcsin and
arccos functions may not be available (as is the case in Amanda), they are
expressed using the arctan function.
55 || sine
56 || sin :: num → num
57 sin ‘[0] x = atan ( x // (1 - x ^2) ^0.5 ) , if abs x ≤ 1
58
59 || cosine
60 || cos :: num → num
61 cos ‘[0] x = atan ( (1 - x ^2) ^0.5 // x ) , if abs x ≤ 1
62
63 || tangent
64 || tan :: num → num
65 tan ‘[0] x = atan x
66
67 || inverse sine
68 || arcsin :: num → num
69 arcsin ‘[0] x = sin x , if abs x ≤ pi // 2
70
71 || inverse cosine
72 || arccos :: num → num
73 arccos ‘[0] x = cos x , if abs x ≤ pi // 2
74
75 || inverse tangent
76 || tan :: num → num
77 arctan ‘[0] x = tan x , if remainder x pi 6= pi // 2
32 CHAPTER 2. APPLICATION PATTERNS
2.6.3 Numerical functions
The prime, fibonacci and factorial functions are well-known examples of func-
tions that calculate the n-th number that adheres to some condition. They can
be defined in an easily-readable (but not necesarily efficient) way by
prime :: num → num → num
prime n = ( sieve [2..]) ! n
where
sieve ( p : x ) = p : sieve [ n | n <- x ; n mod p
> 0]
fib :: num → num → num
fib 0 = 1
fib 1 = 1
fib ( n +2) = fibonacci n + fibonacci ( n +1)
fac :: num → num
fac 0 = 1
fac n = n * fac (n -1)
These function have in common that, from a certain value on, they all increase
strictly monotonically. Thus, to define the inverse prime‘[0] applied to some
argument y, we can try for an increasing value x whether prime x evaluates
to y. Now only a suitable starting value for x (0 would be fine), as well as
an halting condition (for when we know that the value for x has grown too
large) have to be defined. The same approach can be used to define the inverse
functions fib‘[0] and fac‘[1].
The helper definition invGenTest provides the desired functionality. It takes
as arguments the original function (for which the inverse is required), a succes-
sor function that increases the starting value, a testing function that indicates
whether the starting value has grown to large, and an initial value x. It returns
a function that takes an image y and returns Just x if there is some value of
x for which y is the image, or Nothing is no such value for x exists. The use
of the maybe type is to allow the inverse function to be a partial definition, so
that its implicit in a pattern allows for refutability.
79 invGenTest :: (* → **) → (* → *) → (* → ** → bool ) → *
→ ** → maybe *
80 invGenTest f next stop x y
81 = Just x , if f x = y
82 = invGenTest f next stop ( next x ) y , if ~( stop x y )
Now inverses for the prime, fibonacci and factorial functions are defined by
84 prime ‘[0] y = fromJust valMb , if valMb 6= Nothing
85 where
86 valMb = invGenTest prime (+1) ( >) 0 y
87
2.6. STANDARD INVERSE FUNCTIONS 33
88 6 Nothing
fib ‘[0] y = fromJust valMb , if valMb =
89 where
90 valMb = invGenTest fib (+1) ( >) 1 y
91
92 fac ‘[0] y = fromJust valMb , if valMb 6= Nothing
93 where
94 valMb = invGenTest fac (+1) facStop 1 y
95 facStop x y = x -1 > log y
Note that, since fib 0 = fib 1 and fac 0 = fac 1, the starting values for
x starts at 1 since the fibonacci and factorial functions only increase strictly
monotonically from 1 on. Note further that the factorial function has a rather
efficient testing functions that increases x faster than the successor function +1.
Finally it must be remarked that other definitions for these inverses may be
more efficient.
Example. The fibonacci numbers have the property that
φn − φ̂n
fib n = √
5
where
√
5+1
φ= ,
√2
5−1
φ̂ =
2
√
as is easily shown by induction. Since fib n approaches φn / 5 asymptotically,
a more efficient definition for the inverse fibonacci function is
fib ‘[0] ’ 1 = 1
fib ‘[0] ’ n = val , if n > 1 ∧ fib val = n
where
val = ceiling ( log n // log phi )
where
phi = (1+5^0.5) // 2
Thus, use of the invGenTest function in inverse function definitions may be
easy, but sometimes more efficient definitions exist.
2.6.4 List manipulation
For many list manipulation functions inverse functions can be defined, most of
them being straightforward.
Note that for the join3‘[1] definition—that joins three lists—the first oc-
curence of the separating string is choosen. That is, if the lists ^y and ^y’ are
known while for certain lists it holds that
join3 x ^y z = s and join3 x’ ^y’ z’ = s
34 CHAPTER 2. APPLICATION PATTERNS
then matching join3 p ^y r against an actual argument will bind p to the
shortest list in x and x’ (and q to the longest list in z and z’). In other words,
join3 is non-greedy. As we will see in Section 2.7.2, this decision allows for
simple string parsing
97 || reverse a list
98 || reverse :: [*] → [*]
99 reverse ‘[0] x = reverse x
100
101 || constitute a list from a head and a tail list
102 || cons :: * → [*] → [*]
103 6 []
cons ‘[0] xs = ( hd x , tl x ) , if x =
104
105 || join two lists [++] ( a . k . a . join2 )
106 || join :: [*] → [*] → [*]
107 join ‘[0] y s = x , if y = z
108 where
109 (x , z ) = split ((# s ) - (# y ) ) s
110
111 join ‘[1] x s = y , if x = z
112 where
113 (y , z ) = split (# x ) s
114
115 || join three lists
116 || join3 :: [*] → [*] → [*] → [*]
117 join3 ‘[1] x z s = y , if x =x ’ ∧ z =z ’
118 where
119 (x ’ , yz ) = split (# x ) s
120 (y , z ’) = split (# ys - # z ) ys
121
122 join3 ‘[0 ,2] y s = hd xzs , if xzs 6= []
123 where
124 xzs = [ (x , z )
125 | i <- [0..(# s - # y - 1) ]
126 ; (x , yz ) = split i s
127 ; (y ’ , z ) = split (# y ) yz
128 ; y = y’
129 ]
130 || zip a pair of lists
131 || zip :: ([*] , [**]) → [(* , **) ]
132 zip ‘[0] :: [(* , **) ] → ([*] , [**])
133 zip ‘[0] (( x , y ) : xys ) = ( x : xs , y : ys )
134 where
135 ( xs , ys ) = zip −1 xys
136 zip ‘[0] [] = ([] , [])
137
138 || zip two lists
139 || zip2 :: [*] → [**] → [(* , **) ]
140 zip2 ‘[0 ,1] xs = zip ‘[0] xs
2.6. STANDARD INVERSE FUNCTIONS 35
141
142 || take the first n elements
143 || take :: num → [*] → [*]
144 take ‘[0] x s = len , if take len s = x
145 where
146 len = # x
147
148 || drop the first n elements
149 || drop :: num → [*] → [*]
150 drop ‘[0] y s = len , if drop len s = y
151 where
152 len = # y
153
154 || splits a list at a certain index
155 || split :: num → [*] → ([*] , [**])
156 split ‘[0 ,1] ( xs , ys ) = (# xs , xs ++ ys )
157
158 || get ( n +1) - th element from list [!]
159 || index :: [*] → num → *
160 index ‘[1] x s = hd is , if is 6= []
161 where
162 is = [ i | i <- [0..(# s -1) ]; s ! i = x ]
163
164 || repeat an element n times
165 || rep :: num → * → [*]
166 rep ‘[0 ,1] :: [*] → ( num , *)
167 rep ‘[0 ,1] [ x ] = (1 , x )
168 rep ‘[0 ,1] ( x : rep n y ) = ( n +1 , x ) , if x = y
2.6.5 Conversion functions
Conversion functions mainly transform values from one type to another. Since
this transformation is already defined in both directions, the inverse definitions
are rather trivial. Note that the definition of lines‘[0] is recursive and rather
symmetrical with that of unlines‘[0].
170 || transform string to integer
171 || atoi :: [ char ] → num
172 atoi ‘[0] s = itoa s
173
174 || transform integer to string
175 || itoa :: num → [ char ]
176 atoi ‘[0] s = atoi s , if filter ( member " -.0123456789")
s = s !\\
177 ∧ count ’. ’ s ≤ 1!\\
178 ∧ count ’-’ ( tl s ) = 0!\\
179 where count x = (#) . filter (= x ) !\\
180
36 CHAPTER 2. APPLICATION PATTERNS
181 || get character ascii code
182 || code :: char → num
183 code ‘[0] s = decode s , if 0 ≤ s ∧ s ≤ 255
184
185 || get character with certain ascii code
186 || decode :: num → char
187 decode ‘[0] s = code s
188
189 || splits a string based on newline characters
190 || lines :: [ char ] → [[ char ]]
191 lines ‘[0] ( join3 x "\ n " ( lines xs ) ) = x : xs
192 lines ‘[0] x = [x]
193
194 || joins a list of lists , adding newline characters
195 || unlines :: [[ char ]] → [ char ]
196 unlines ‘[0] ( x : xs ) = join3 x "\ n " ( join3 xs )
197 unlines ‘[0] [] = []
In brief, for many standard functions an inverse can be defined.
2.7 The use of application patterns
In this section a brief overview of the use of application patterns is given. Be-
sides the theoretical importance that application patterns are a general form
(Section 2.5) they also yield practical implications.
2.7.1 More readible definitions
Using the application pattern, function definitions may become more readible.
That is, if in a function definition first some trivial operation must be performed
on an argument, this operation can be placed in the right hand side of the
definition.
Example. In the following definitions, first a simple operation is applied to
an actual argument.
f ( sin alpha ) = . . . alpha . . .
g (2* n ) = ... n ...
h ( itoa s ) = ... s ...
k ( ln x ) = ... x ...
For example, if f is applied to an actual argument a, the function sin‘[0] is
applied to a and the result bound to alpha. Note that f is only defined for
values between -1 and 1, inclusive. Likewise, the functions g, h and k use,
when applied to an actual argument, the inverse functions *‘[1], itoa‘[0]
and ln‘[0] in order to bind n, s and x, respectively.
2.7. THE USE OF APPLICATION PATTERNS 37
Example. Since nested patterns are possible too, the definition like
f x = ... p ... , if abs x ≤ 1
where
p = 5 - arcsin x
can be written more readible as
f ( sin (5 - p ) ) = ... p ...
Example. Another example of a better readible function definition example
is the upperLeft function
upperLeft :: [( num , num ) ] → ( num , num )
upperLeft ( zip ( xs , ys ) ) = ( min xs , max ys )
2.7.2 Simple string parsing
A nice application for application patterns is simple string parsing. Suppose
that, from a long input string s, some substrings must be bound to the identifiers
x1 ,...,xk which are seperated by known substrings c1 ,...,ck−1 . Then these
identifiers can be bound by matching the pattern
join3 x1 c1 ( join3 x2 c2 (... ( join3 x k−1 c k−1 x k ) ...) )
against the input string s, since during evaluation the inverse join3‘[0,2] is
used to bind the x* ’s. If s starts or ends with a known substring, then the
beginning or end can be matched by the use of the join2 function.
Example. Consider the function vec3length that parses the length of a string
that represents a three-dimensional vector (x,y,z). For any other string it
returns zero. Informally it would be defined by
vec3length ( "(" ++ ( itoa x ) ++ " ," ++ ( itoa y ) ++ " ,"
++ ( itoa z ) ++ "") " )
= ( x ^2 + y ^2 + z ^2) ^ 0.5
vec3length _ = 0
Now clearly the use of ++ will not work, but this definition can automatically
be rewritten into
38 CHAPTER 2. APPLICATION PATTERNS
vec3length ( join2 "("
( join3 ( itoa x )
" ,"
( join3 ( itoa y )
" ,"
( join2 z ") " ))))
= ( x ^2 + y ^2 + z ^2) ^ 0.5
vec3length _ 0
where the join2‘[1], join3‘[0,2] and join2‘[0] inverse functions are used
when vec3length is applied to an actual argument. With this definition, the
length of the vector represented by the string "(2,3,6)" evaluates to 7, whereas
a bad-formed string evaluates to 0.
vec3length "(2 ,3 ,6) "
⇒ 7
veclength " not a vector "
⇒ 0
Thus, such constructions may allow for better readible and easier compre-
hendible definitions.
Besides these considerations, inverse function definitions allow for indicating
that different functions (the function itself and its inverses) are semantically
related. In addition, the caret notation allows for some extra expressive power
in patterns. It must be noted, though, that application pattern syntax and
semantics may take some time to get used to for the programmer.
2.8 Conclusion
This chapter described application patterns. The concept of generalized inverses
was introduced, as well as a new caret notation that adds expressive power to
patterns. Application patterns together with the caret notation
Chapter 3
The Application Pattern
Compiler
3.1 Introduction
In the previous chapter application patterns were discussed. This chapter will
discuss rewriting application patterns into semantically equivalent runnable
code.
In Section 3.2 this rewriting it is made intuitive to the reader by discussing
some examples. In Section 3.3 a general rewriting algoritm for application pat-
tern is sketched. This sketch can be seen as both providing an implementation
of rewriting the rewriting algoritm and providing the semantics of application
patterns. In Section 3.4 the implementation of this rewriting algoritm is dis-
cussed.
3.2 Intuitively rewriting application patterns
In this section I describe intuitively how an application pattern can be rewrit-
ten. In order to describe all features of the rewriting algoritm, I will take the
same approach as in Chapter 1. First rewriting of the basic application pat-
tern is described. Then refutability is added by using the maybe type. Finally
generalized inverse functions are discussed.
3.2.1 Basic pattern
This section describes rewriting a basic pattern f x. Recall the upperLeft
example from Section 2.2.1.
upperLeft :: [( num , num ) ] → ( num , num )
upperLeft ( zip ( xs , ys ) ) = ( min xs , max ys )
How would one rewrite this definition without application patterns? The idea
is that during evaluation of upperLeft a, where a is an actual argument, the
equation
39
40 CHAPTER 3. THE APPLICATION PATTERN COMPILER
zip (xs, ys) = a
is solved for xs and ys by applying the inverse function zip‘[0] to both sides
of this equation:
(xs, ys) = zip‘[0] a
Now the solution proposed here for rewriting the definition of upperLeft is
to introduce a new (free) identifier, say var, that takes the role of the actual
argument. The argument (xs, ys) in the application pattern is then bound in
a where clause:
upperLeft ’ :: [( num , num ) ] → ( num , num )
upperLeft ’ var = ( min xs , max ys )
where
(xs, ys) = zip‘[0] var
3.2.2 Adding refutability
The basic rewriting procedure in the previous section does not take into account
that an application pattern may be refutable. This section describes rewriting
a basic pattern f x where f may be partially defined (yielding refutability).
Consider the definition
h ( sin a ) = a * a
h x = x - 2
This definition uses that the inverse sine function is partially defined, namely
only for values in [−1, 1]:
sin ‘[0] x = arcsin x , if abs x ≤ 1
However, the evaluation of say sin‘[0] 2 produces a runtime exception. In
order to avoid such exceptions, first the definition of sin‘[0] is rewritten (in-
dicated by the _Mb suffix) so that it returns a value of the maybe type:
sin_Mb ‘[0] x = Just arcsin x , if abs x ≤1
= Nothing , otherwise
This rewriting can be performed automatically, as is shown further in this chap-
ter. To apply the sin_Mb‘[0] function to an argument var, first it must be
checked that its value is not Nothing. If its value is not Nothing (that is, the
inverse function is defined for the argument var), it is Just something where
this something is the desired result.
Thus, to rewrite the first equation in the definition of h two variables are
introduced: a var variable that replaces the pattern sin a, and a match variable
that checks whether the inverse function sin_Mb‘[0] is defined for the value of
var. This results in
3.2. INTUITIVELY REWRITING APPLICATION PATTERNS 41
h ’ var = a * a , if match = Nothing
where
match = sin Mb[0] var
Just var = match
h’ x = x - 2
As the first equation now contains an identifier pattern, the second equation has
become unreachable. Thus the two equations must be merged, where care must
be taken that the arguments of h match. Here the occurence x in the second
equation can be renamed to var, resulting in
h ’ var = a * a , if match 6= Nothing
where
match = sin_Mb [0] var
Just var = match
h ’ var = var - 2 , otherwise
3.2.3 Adding refutability
With refutability added in the previous section, now it is time to describe rewrit-
ing application patterns with multiple arguments. This section describes rewrit-
ing a an application pattern f x0 ... xn−1 where f may be partially defined.
Consider the definition
firstAndThird ( join5 x ^ hyph " _ " " -" z)
= "[" ++ x ++ "|" ++ z ++ "]"
hyph = " _ "
where the application pattern join5 x ^hyph "_" "-" z contains five ar-
guments. The second argument ^hyph, the third argument "_" and the fifth
argument are known, i.e. constant or retrieved from the context. The first
argument x and the fifth argument z must be bound.
Now suppose the join5 function joins five lists
join5 a b c d e = concat [a , b , c , d , e ]
and has an inverse function defined with respect to its first, third and fifth
argument
join5 ‘[0 ,2 ,4] :: [*] → [*] → [*] → ([*] ,[*] ,[*])
join5 ‘[0 ,2 ,4] b d s = ...
42 CHAPTER 3. THE APPLICATION PATTERN COMPILER
that can be automatically be rewritten into a definition that returns the maybe
type
join5_Mb ‘[0 ,2 ,4] :: [*] → [*] → [*] → maybe ([*] ,[*] ,[*])
join5_Mb ‘[0 ,2 ,4] b d s = ...
Rewriting as definition ∗ is informally specified by
f‘[a1 ,· · ·,ak ]x1 · · · xm f_Mb‘[a1 ,· · ·,ak ]x1 · · · xm
= v1 , if g1 = Justv1 , ifg1
.. .. ∗ .. ..
. . ⇒ . .
= vn , if gn = Justvn , ifgn
= Nothing, otherwise
and the resulting definition can be added to the existing definitions.
Clearly we must use this inverse function so solve for the arguments x and z
in the application pattern. The first step is the same as in the previous section:
a new identifier var replaces the application pattern:
firstAndThird ’ var
= "[" ++ x ++ "|" ++ z ++ "]"
Note that the arguments in the application pattern join5 x ^hyph "_" "-"
z ")" can be partitioned into three lists,
1. the arguments that are both required by join5_Mb‘[0,2,4] and known:
^hyph and "-";
2. the arguments that are provided by join5_Mb‘[0,2,4] and that must be
bound: x and z; and
3. the arguments that are provided by join5_Mb‘[0,2,4] but are already
known: "_". These arguments must be checked for their value.
Now the inverse join5_Mb‘[0,2,4] is applied to the arguments from the first
set, together with a fresh identifier that replaces the whole application patterns.
The result is again bound to a fresh matching identifier match
firstAndThird ’ var
= "[" ++ x ++ "|" ++ z ++ "]" , if match ~= Nothing
where
match = join5 Mb‘[0,2,4] ^hyph "-" var
The arguments in the other two lists are bound using the result. For members
of the third set, arguments that are provided by join5_Mb‘[0,2,4] but are
already known: "_", new identifiers are introduced that are checked for the
right value by adding a guard to the definition. Here a new identifier var1 is
introduced that is checked for being equal to the third argument "_".
3.3. A REWRITING ALGORITM 43
firstAndThird ’ var
= "[" ++ x ++ "|" ++ z ++ "]" , if match = 6 Nothing
∧ var1 = " "
where
match = join5_Mb ‘[0 ,2 ,4] ^ hyph " -" var
Just (x , var1 , z ) = match
(Note: in the next section an algoritm is presented that treats elements in the
last two lists alike).
Finally one issue must be resolved: what if during rewriting an application
pattern one can choose between multiple inverse functions that all provide the
necessary arguments (and possibly others as well)? Some options are
Choose the first inverse that is defined. This solution is most easily imple-
mented.
Choose the smallest set of arguments that is provided by the inverse.
Choose the largest set of arguments that is provided by the inverse.
Choose a random defined inverse.
Either of the ones above repeatedly by allowing one inverse to fail (be-
cause it is not defined) and then try another one.
The different options may yield different evalution results, for instance when
one inverse is defined for a smaller domain than another one. The pros and
cons of each of these options are subject to further research.
In this section an intuitive overview was given on rewriting single application
patterns. In the next section a general rewriting algoritm is discussed that
rewrites all kinds of patterns that may be nested and overlap.
3.3 A rewriting algoritm
This section sketches rewriting algoritm that can be used for rewriting code
with application patterns into code without application patterns.
3.3.1 Overview
Peyton Jones (1987) describes a compiler that translates function definitions
with pattern matching into case-expressions that can be efficiently evaluated.
This is not the approach of the algoritm described here, as this algoritm trans-
lates function definitions with pattern matching that may include application
patterns into function definitions with pattern matching that does not include
application patterns. In addition, the algoritm described here does not incor-
porate optimizations that are described by Peyton Jones such as a per-column
rewriting.
The compiler described by Peyton Jones provides support for
• Overlapping patterns
44 CHAPTER 3. THE APPLICATION PATTERN COMPILER
• Nested patterns
• Constant patterns
• Multiple arguments
• Non-exhaustive sets of equations
• Conditional equations
• Repeated variables
The rewriting algoritm for application patterns, as described here, provides
support for all these constructions too. For ordinary (i.e., non-application) pat-
terns the algoritm translates pattern correctly, that is in accordance with the
semantics of pattern matching as described by Peyton Jones (1987). There-
fore, one may consider application patterns as an extension to current pattern
matching whose semantics are defined by the rewriting algoritm.
3.3.2 Rewriting patterns
In essence, the algoritm allows for rewriting all kinds of patterns into simpler
patterns. Patterns in the resulting code are either identifier patterns, nested tu-
ple patterns or non-nested algebraic patterns. In this section rewriting all kinds
of patterns is described (except the ones that can be expressed by application
patterns as described in Section 2.5), whereas the next section will cover rewrit-
ing function definitions. One may wonder why rewrite not just the application
patterns and leave the other patterns as they are. However, since application
patterns and all other patterns can occur nested, to avoid runtime exceptions
all patterns must be rewritten.
In the previous section application patterns where rewritten by adding guards
and where clauses to function definitions; the rewriting algoritm is based on the
same principle. The notation
Rewr J e K
= e ’ C guard+ L99g
C wheres+L99ws
means that the algoritm rewrites the pattern e is into e’, with the guard g and
the where clauses ws added to the definition in which the expression occurs.
The predicate isKnown(·) is used to indicate that an expression is known (in
its context), i.e. that it contains no free identifiers.
It is assumed that all identifiers that are bound in patterns are different
(but the caret notation allows for mimicking the equivalence pattern: see Sec-
tion 2.5.7). For application patterns it is assumed that the caret prefix is used
in the function name.
Constant
A constant is replaced by a new identifier whose value is compared to the con-
stant.
3.3. A REWRITING ALGORITM 45
Rewr J c K
= var C guard+ L99var = c
• isKnown( c )
• var is a new identifier
Example. The definition
fac (1 + 2 + 3 + 4 - 10) = 1
is rewritten into
fac var = 1 , if var = 1 + 2 + 3 + 4 - 10
Identifier
Rewriting the identifier pattern is trivial, as it is the identifier itself.
Rewr J i K
= i
• i is an identifier
Function application
For an application pattern the inverse is applied to its required arguments. The
arguments provided by the inverse are (in their rewritten form) bound to the
result.
46 CHAPTER 3. THE APPLICATION PATTERN COMPILER
Rewr J ^ f x 0 ... xn−1 K
= var C guard+ L99match 6= Nothing
C wheres+L99match = f_Mb ‘[ i1 , ... , ik ] x j1 ... x jm
Just ( Rewr J x i1 K ,... , Rewr J x ik K )
= match
• x∗ ’s are patterns
• ∀p ∈ {1, . . . , j} : isKnown( xp )
• The inverse f‘[i1 , ...,ik ] is defined for m argumentsa
• The indices of provided arguments i∗ and indices of required arguments
j∗ partition the list of all argument indicesb :
[i1 , . . . , ik ] ∪ [j1 , . . . , jm ] = [0, . . . , n − 1]
where the ∪ operator merges two ordered lists into a new ordered list.
• var and match are new identifiers
a InSection 3.2.3 it is shown how the inverse f_Mb‘[i1 , ...,ik ] can be derived automati-
cally
b It If multiple combinations of lists fulfill this condition, multiple strategies are possible to
pick one; see Section 3.2.3
This scheme convers algebraic values, in which constructors yield an inverse on
all their arguments so that k = n, m = 0 and ip = i − 1 (see also Section 2.5.2).
This scheme also applies to tuples, lists and constants because they can be
represented by algebraic values.
Example. The definition
gcd x (^ x + y ) = gcd x y
contains an application pattern ^x + y of the addition function (fully written
plus), for which the first argument is known and the second to be bound. It is
rewritten into
gcd x var
= gcd x y , if match 6= Nothing
where
match = plus_Mb ‘[1] ^ x var
Just y = match
where it is assumed that the inverse function plus‘[1] is defined.
3.3.3 Special cases in rewriting
It was shown in Section 2.5 how algebraic, tuple, list and constant patterns are
special cases of an application pattern. This means that they can be rewritten
3.3. A REWRITING ALGORITM 47
using the schemas given in the previous section. However, using these schemas
may not yield the most readible code. In this section alternative rewriting
schemas are given that are more easily readible and implementable. The reader
may verify that the schemas given agree with the more general forms described
previously.
Constructor
For a constructor first the type of the constructor is checked. Then its arguments
(in their rewritten form) are bound to the actual argument using the constructor.
Rewr J C x 0 ... xn−1 K
= var C guard+ L99isConstr var
C wheres+L99isConstr ( C | ...
{z } ) = True
n
isConstr _ = False
C Rewr J x i1 K ... Rewr J x in−1 K = var
• c is a constructor
• x∗ ’s are patterns
• var and isConstr are new identifiers
Example. The definition
sumTree ( Node x y ) = sumTree x + sumTree y
is rewritten into
sumTree var
= sumTree x + sumTree y , if isConstr var
where
isConstr ( Node _ _ ) = True
isConstr _ = False
Constr x y = var
Note that a constant can be seen as a constructor without arguments. This is
also in agreement with the rewriting scheme for rewriting a function application
patterns with k = m = 0.
Tuple
For a tuple the arguments (in their rewritten form) can be rewritten directly,
since a tuple pattern is non-refutable.
48 CHAPTER 3. THE APPLICATION PATTERN COMPILER
Rewr J ( x 0 , ... , xn−1) K
= ( Rewr J x i1 K , ... , Rewr J x in−1 K )
• x∗ ’s are patterns
Identifier bound in the context
An identifier bound in the context is treated like a constant pattern. This is a
special case of rewriting a constant because it must hold that isKnown( ^i ) in
the context of i.
Rewr J ^ i K
= var C guard+ L99var = i
• i is an identifier that is bound in the context.
• var is a new identifier
As described earlier, in a left hand side of a function definition the context also
includes identifiers that are bound in patterns.
Example. The definition
gcd ^ x x = x
is rewritten into
gcd var x = x , if var = x
3.3.4 Rewriting definitions
In the previous section it was described how patterns could be rewritten into
equivalent patterns without application patterns, where some extra guards and
where clauses might me added to the function definition.
For adding these guards and where clauses to a definition, either of two cases
hold:
• The definition’s left hand side consists of an ordinary function with one
or more (rewritten into identifier) patterns as arguments.
The extra guards are added to each of the existing guards. Note that the
order is important: first the extra guards must be tested, in the left-to-
right, outside-in order corresponding to the rewritten pattern, followed by
the existing guards (there is one exception: as shown in Section 2.4.2 the
3.3. A REWRITING ALGORITM 49
caret notation allows for situations in which patterns are matched in a
different order).
The extra where clauses are added to the list of where clauses in the
function definition.
• The definition’s left hand side is itself a pattern in a where clause.
The extra guards are ignored, because is is assumed that they match.
Note that improper use may yield a runtime exception, just like for any
other pattern used in a where clause
The extra where clauses are added to the list of where clauses the pattern
is part of.
All rewriting examples given so far are examples to the first case. An example
of the second case is
p ys = x + # xs
where
( x : xs ) = ys
that is rewritten into
p ys = x + # xs
where
var
= ys
match
= inv_cons_Mb_0_1 var
Just (( x , xs ) )
= match
Note that the pattern x:xs is replaced by the identifier var. x and xs are bound
in the same where clause as where var is bound. There is no guard that checks
whether match equals Nothing. This means that p [] would yield a runtime
exception, just like the original definition.
Intuitively, the algoritm described above agrees with the semantics of pattern
matching as described by Peyton Jones (1987). A proof for this falls outside
the scope of this thesis.
For functions with more than one equation it may be the case that non-
identifier patterns are rewritten into identifier patterns. This can make other
equations unreachable. Therefore the equations must be merged , which requires
that the identifiers in the function’s arguments match. This can be achieved by
renaming identifiers or binding them in a where clause.
3.3.5 Conclusion
In this section an algoritm was sketched for rewriting application patterns. This
algoritm provides support for
50 CHAPTER 3. THE APPLICATION PATTERN COMPILER
Overlapping patterns as multiple guards may evaluate to True
Nested patterns as patterns are rewritten recursively
Constant patterns as a transformation for this case is defined
Multiple arguments even within application patterns, by rewriting the argu-
ments one by one
Non-exhaustive sets of equations which may cause all guards to evaluate
to False
Conditional equations by the use of guards
Repeated variables supported by the use of the caret notation
The next section describes the implementation of this algoritm.
3.4 The application pattern compiler
This section describes the requirements, design and implementation of the appli-
cation pattern compiler. This compiler rewrites definitions with application pat-
terns into code witout application patterns according to the algoritm sketched
in the previous sections.
3.4.1 Requirements
This section discusses the requirements for the pattern match compiler.
The ultimate goal of the pattern match compiler is to provide the ability
to execute code with application patterns. A working implementation would
show conclusivily that application patterns are implementable. Furthermore
it would allow for more programs written with application patterns, so that
it can be tested in real-world applications. In brief, the primary goal of the
pattern match compiler is to provide a proof-of-concept. The requirements are
summarized by
Executable code. The pattern match compiler should allow for running pro-
grams that are specified using application patterns.
Substantial language. It should support a sufficient powerful functional lan-
guage. Not all features have to be working, but all basic functionality
should be available
Performance is not an issue. This is a proof-of-concept, thus performance
is not an important factor. Using the compiler should just not take too
long.
Not fool proof. Likewise, the compiler has not to be foolproof. It should at
least be able to use properly written code.
With these requirements in mind, the design is discussed in the next section.
3.4. THE APPLICATION PATTERN COMPILER 51
3.4.2 Design
To fullfill the requirements specified in the previous section, it is sufficient to
implement the algoritm described in Section 3.3. This algoritm must be pro-
vided with properly parsed input. The result must be written into interpretable
source code. In addition, proper use of the algoritm requires some pre- and
postprocessing.
The output of the compiler, in the form of source code, must be interpreted
by an existing interpreter. A drawback is that debugging may be more cumber-
some, since if the original code contains errors this may result in an error during
rewriting or when the rewritten code is loaded into the interpreter. However,
since the compiler is only a proof-of-concept this is not a great advantage.
3.4.3 Implementation language
The chosen implementation language is Amanda, which supports all common
functional programming features. As input language I defined a Amanda-
corelanguage, which is a substantial subset of the Amanda language providing
support for the following features:
• Constant expressions of type num, char and bool).
• Compound expressions: lists, tuples, algebraic values.
• Constant, list, tuple, algebraic and identifier patterns.
• Identifiers and function applications.
• Prefix and infix operator expressions with priorities.
• Function definitions with multiple equations, clauses and (nested) where
clauses.
However, there is no support for:
• Record, lambda and list comprehension expressions
• As patterns or equivalence patterns (without the caret notation)
• Type denotations or definitions
• Interpreter directives such as import statements
To this language support for caret notation together with application pat-
terns are added, resulting in AmandaAP . In this language it is required that
inverse functions are defined at the top level with all its arguments mentioned
explicitly1 . In addition, inverse functions for operators must use predefined full
names.
The AmandaAP language is definitely powerful enough to meet the require-
ments in the previous section. In 3.4.6 a sketch is given how record, lambda
and list comprehensions could be implemented, but the actual implementation
is beyond the scope of this proof-of-concept prototype.
1 The reason is that the compiler cannot deduce types: it just counts the number of argu-
ments to deduce the total number of arguments of the function it is the inverse of
52 CHAPTER 3. THE APPLICATION PATTERN COMPILER
3.4.4 Implemenation
The complete transformation is divided in a number of steps.
Lexer. The lexer splits the input file into a list of elementary items and attaches
a label to them. In this case, the lexer also keeps tracks of indentation
(the offside rule).
Parser. Based on the lexer output, the parser recognizes structure in sequences
of lexed items and represents this structure using an algebraic datatype.
After this step, infix and prefix operators are written by their full names.
Add carets. As sometimes the use of the caret ^ prefix is optional, these carets
are added to both nested function applications and operator function ap-
plications in left hand sides of definitions.
Syntactic rewrite ++. An extra feature is that patterns with the ++ operator
are automatically rewritten into application patterns with the join2 and
join3 functions (see Section 2.7.2). This rewriting is specific to the ++
operator.
Rename identifiers. In order to avoid problems with identifiers that are re-
defined at multiple levels (such as in nested where clauses), all identifiers
except the function names at the top level are renamed to a new unique
name.
Rewrite application patterns. This is the step that actually performes the
rewriting described by the algoritm presented in Section 3.3. The rewriting
schemes from Section 3.3 are used almost literally.
Merge equations. After rewriting some patterns may be lost, so that equa-
tions in function definitions become unreachable. These equations are
merged.
Add maybe type for inverse functions. Besides the transformation itself, de-
finitions for the inverse functions must be added (Section 3.2.3) so that
they return the maybe type.
Create legal identifiers. Since identifiers with the backtic and caret notation
are illegal identifiers in Amanda-core, these are systematically renamed
into legal identifiers.
Pretty print code. Finally the resulting definitions are printed as more or
less human readible source code.
The lexer and parser are inspired by the grammar reported by Papegaaij (2005).
For the lexer, parser, rename identifiers and rewrite application patterns, I made
extensive use of monad constructions as described by Wadler (1992).
Together, these steps perform the complete transformation from AmandaAP
to Amanda-core. The implementation of each step is described in Appendix A.
3.4. THE APPLICATION PATTERN COMPILER 53
3.4.5 Results
The application pattern compilers works in rewriting code with application pat-
terns. The only problem is that Amanda crashes for larger input files due to
an unexplainable but reproducable memory problem. An example of input and
output is provided in Appendix A.3. The output is accepted by Amanda (if
the proper algebraic type definitions are added manually), the functions can be
run and produce the expected results. This shows that application patterns can
indeed be implemented and used in functional languages.
3.4.6 Extensions
The application pattern compiler provides no support for partial records, lambda
abstractions and list comprehensions. In Amanda all these expressions may con-
tain patterns. In this section I give a sketch how support for such patterns may
be provided.
Partial records
Partial records whose type definition contains n fields can be written by an n-
tuple with elements of the maybetype. Matching against fields in such a record
is matching against the expressions Just ... and Nothing.
Lambda abstractions
In amanda a lambda abstraction takes the form
( pat 1 → x 1 | pat 2 → x 2 | ... | pat k → x k )
where the pat∗ ’s are patterns that are matched against an actual argument.
The pipes | seperate alternatives (thus allowing for case expressions).
Such an expression can be replaced by a free identifier, say f, that is defined
by
f pat 1 = x 1
f pat 2 = x 2
...
f pat k = x k
Clearly this approach can also be used in the case of multiple arguments.
3.4.7 List comprehensions
List comprehensions are easily rewritten using the list monad. This monads
consists of the definitions of the unit and bind operators
monadLst.ama
54 CHAPTER 3. THE APPLICATION PATTERN COMPILER
1 unitLst x = [ x ]
2
3 bindLst ( x : xs ) f = f x : bindLst xs f
4 bindLst [] f = []
Now a list comprehension is easily rewritten by the use of these operators and
lambda abstractions.
Example. As an example, consider the lambda abstraction
[ f x z
| sin p, qs) <- xs
; y <- qs
; check p y
; z + 10 <- zs ]
where the lists xs and zs are bound in the context. The patterns are underlined
in this definition. First the guard check p y can be rewritten into the generator
_ <- if (check p y)[[]] []. Now the lambda abstraction is rewritten using
the monad operators into
concat ( xs $bindLst ( ( sin p , qs ) →
concat ( qs $bindLst ( y →
concat ( if ( check p y ) [[]] []
$bindLst ( _ →
concat ( zs $bindLst ( ( z +10) →
unitLst ( f x z )
| _ → [] ))
| _ → [] ))
| _ → [] ))
| _ → [] ))
Thus, in every generator the pattern is matched against elements in the list. If
matching fails the empty list is returned. The lambda abstractions in this new
expression can be rewritten using the approach described above.
3.4.8 Choose carets
A possible extension would be to allow application patterns without carets, so
that ‘real’ application patterns would be possible. A sketch for an algoritm is
as follows: for a left hande side without carets one may try all possible caret
additions. Since each identifier should occur only once without a caret, the
number of combinations is rather limited. For each combination it can be tried
whether a selection for inverse function exists that binds all required identifiers.
3.5. CONCLUSION 55
3.4.9 Integration
The application pattern is a stand-alone application that works seperately from
the interpreter. For practical use an integration with the compiler or interpreter
would improve usability. This may be achieved by an integration with an pattern
match compiler. Other desirable features are support for a complete functional
language (not a subset), type checking and no memory limitations. In how far
application patterns allow for optimizations like in ordindary pattern matching
(see Peyton Jones, 1987) is a point of further research.
3.5 Conclusion
In this chapter a rewriting algoritm for application patterns as sketched and
described. Also the implementation of this algoritm, the Application Pattern
Compiler, was described. The next chapter discusses further research.
56 CHAPTER 3. THE APPLICATION PATTERN COMPILER
Chapter 4
The future for application
patterns
4.1 Introduction
This chapter describes the relation with other work on extensions to pattern
matching, and gives some suggestions for further research.
4.2 Related work
In this section the relation with other proposed pattern matching extensions is
discussed.
One paper is by Tullsen (2000) who uses inverses of algebraic constructors,
but not more generally for other (non-injective) functions. In addition, his
paper has a different aim, namely introducing patterns as first class language
constructs.
Another paper is by Broberg, Farre, and Svenningsson (2004) who propose
an extension of Haskell with regular expression patterns. Such patterns allow,
amongst other things, for more flexible string parsing. The use of join2 and
join3 as described in Section 2.7.2 are simple cases of what their regular ex-
pression patterns can handle. Whether their more complicated constructions
allow for easy translation in application patterns is a point of further research.
The paper that comes closest to the idea of application patterns is by Erwig
and Peyton Jones (2000) who propose to extend Haskell with pattern guards.
Such constructions allow for pattern matching and adding guards intertwined.
They give the example (translated to Miranda syntax) of a function that looks
up two values in a mapping,
clunky env var1 var2
= val1 + val2 , if ok1 ∧ ok2
= var1 + var2 , otherwise
where
m1 = lookup env var1
57
58 CHAPTER 4. THE FUTURE FOR APPLICATION PATTERNS
m2 = lookup env var2
ok1 = isJust m1
ok2 = isJust m2
Just val1 = m1
Just val2 = m2
Using their proposed pattern guards, this definition can be written
clunky env var1 var2
| Just val1 <- lookup env var1
, Just val2 <- lookup env var2
= val1 + val2
otherwise = var1 + var2
where the <- operator tries to fit a pattern into a value.
Such constructions can, to some degree, be rewritten using application pat-
terns. To accomplish this we use a ‘trick’ that allows for matching patterns and
binding identifiers. The functions
soThat ‘[0 ,1] x = (x , undef )
matchPat ‘[0] x _ = x
are used for ‘creating room’ for binding arguments and for actually matching
patterns, respectively. Note that these two functions are each other’s inverse.
The definition above would translate (using infix notation) into
clunky env var1 ( var2 $soThat (
( Just val1 $matchPat lookup ^ env ^ var1 ) $soThat (
( Just val2 $matchPat lookup ^ env ^ var2 ) )))
= val1 + val2
clunky env var1 var2
= var1 + var2
which strongly resembles the definition with conditional guards above (for the
caret notation see Section 2.4.2). Admittingly it is a bit combersome that the
function arguments env, var1 and var2 must be given twice, and also that var2
is enclosed by parenthesis.
It is easy to add guards as well by using the definition
guardPat ‘[0] x _ = undef , if x
and by binding the result to the wildcard identifier. For example, the definition
f x | [ y ] <- x
, y > 3
, Just z <- h y
= ...
4.2. RELATED WORK 59
can be translated into
f (x $soThat (
[y] $matchPat ^ x $soThat (
_ $guardPat ^ y > 3 $soThat (
Just z $matchPat ^ h ^ y ))))
= ...
Conversely, application patterns can also be expressed using pattern guards
by mimicking the rewriting algoritm described in Section 3.3. Consider the
definition
p ( f ( g x ) y ) ( h z 2)
= x ^ y + z
with the inverses f‘[0,1], g‘[0], and h‘[0] defined. The rewriting algoritm
would yield
p var var1
= x ^ y + z , if match 6= Nothing ∧ match1 6= Nothing ∧
match2 6= Nothing
where
match = f ‘[0 ,1] var
Just ( var2 , y ) = match
match1 = g ‘[0] var2
Just x = match1
match2 = h ‘[0] 2 var1
Just z = match2
With pattern guards one would write
p var var1
| Just ( var2 , y ) <- f ‘[0 ,1] var
| Just x <- g ‘[0] var2
| Just z <- h ‘[0] 2 var1
= x ^ y + z
which can be considered as more readible than what the rewriting algoritm
produces. However, the programmer would have to choose himself which inverse
to choose and in what order patterns are matched.
These examples suggest that with some effort application patterns and pat-
tern guards can be expressed in one another.
60 CHAPTER 4. THE FUTURE FOR APPLICATION PATTERNS
4.3 Further research
4.3.1 Lazyness and evaluation order
Current pattern matching allows for lazy evaluation: when an actual argument
is matched against a pattern, the argument is only evaluated as far as necesssary
do decide whether the pattern matches. For matching algebraic patterns this
means that first the constructor of an actual argument is computed before any
of its arguments are evaluted.
Application patterns are a generalization of existing patterns, but when they
are used to express existing patterns they agree on lazyness behaviour during
evaluation. This can easily be verified by considering the code produced by
the application pattern described in Section 3.4. For application patterns that
are beyond existing patterns, the programmer ultimately decides how ‘lazy’ an
argument can be matched during evaluation.
4.3.2 Higher order functions
So far only application patterns with ordinary values, i.e. non-higher-order
functions are discussed. However, also some higher order functions can be re-
lated to inverse functions. Two examples are the map and function composition
functions, for which it holds that
(map f )−1 xs = map f −1 xs
(f1 ◦ · · · ◦ fn )−1 = fn−1 ◦ · · · ◦ f1−1
Now one might consider writing (funcomp refers to function composition ◦)
!!! map ‘[1] f ys = map f ‘[0] ys
!!! funcomp ‘[0] g h = h . g ‘[0]
!!! funcomp ‘[1] f h = f ‘[0] . h
but this is clearly wrong since the backtic ‘ is not an operator and thus the
identifiers f‘[0] and g‘[0] cannot be used here.
To a very limited extend one might resolve this by introducing a function
inv :: ( $ \ alpha$ → $ \ beta$ ) → ( $ \ beta$ \ to $ \ alpha$ )
that returns the inverse for every function, so that one may write
!!! map ‘[1] f ys = map ( inv f ) ys
!!! funcomp ‘[0] g h = h $funcomp ( inv g )
!!! funcomp ‘[1] f h = ( inv f ) $funcomp h
Now such an inv function would be possible in principe but can be used
only very limited because function equality is not decidable. In Hindley and
4.3. FURTHER RESEARCH 61
Table 4.1: Several notions of function equality for g x = 2 * x in Amanda
g = g ⇒ True
h1 = g h1 = g ⇒ True
h2 x = 2 * x h2 = g ⇒ False
h3 y = 2 * y h3 = g ⇒ False
h4 x = x + x h4 = g ⇒ False
Seldin (1986) the prove is mentioned that, in general, the equivalence of two λ-
expressions cannot be decided. Since functional languages are implementations
of the λ-calculus, this means that also the equality of two function definitions
cannot be decided.
This means that the only proper approach is to use a conservative notion of
function equality. The problem is that how the interpreter or compiler decides
when two functions are equivalent is an implementation issue, not a language
issue. For example, Table 4.1 shows different notation of equality to the function
g x = 2 * x in Amanda.
This approach is even less useful for curried functions. Suppose for a function
f that takes two arguments it holds that
foldl f z [x1 , x2 , . . . , xn ] = f . . . (f (f z x1 )x2 ) . . . xn := y
−1
Suppose further that f has an inverse on its first argument f[0] (in backtic
notation f‘[0]). Then it holds that
−1
foldr f[0] y [x1 , x2 , . . . , xn ] = z
since
−1
foldrf[0] y [x1 , x2 , . . . , xn ]
−1 −1 −1 −1
= f[0] x1 (f[0] x2 (f[0] . . . (f[0] xn y) . . .))
−1 −1 −1 −1
= f[0] x1 (f[0] x2 (f[0] . . . (f[0] xn (f . . . (f (f z x 1 ) x2 ) . . . xn )) . . .))
−1 −1 −1
= f[0] x1 (f[0] x2 (f[0] . . . (f . . . (f (f z x1 ) x2 ) . . .) . . .))
..
.
−1
= f[0] x1 (f z x1)
= z
Now the only way to define an inverse function for the f oldl function would
be introducing an function that gets a function that takes two arguments as
an argument and yields the inverse for that function on its first argument.
For functions that takes more arguments we would need generalized inverse
functions for each kind of cousin, with a whole family of inverse functions as
a result. Since all these functions must adhere a restrictive sense of function
equality, in my opinion it is doubtful how useful this would be. This is however
a point of further research.
4.3.3 More sophisticated pattern failures
A final point for further research is approaches that allow for more sophisticated
pattern matches and misses. Hölzenspies (2005) has written a runtime pattern
62 CHAPTER 4. THE FUTURE FOR APPLICATION PATTERNS
matcher that allows for searching for suitable inverses, together with a notion of
undefined-ness for functions. In what respect such an approach allows for more
powerful evaluation strategies is a point of further research.
4.4 Conclusion
In this chapter related work was described. The pattern guards proposal is
most related in that performing manually the rewriting algoritm described in
the previous chapter is more easily. Application patterns seem able to express
pattern guards.
It is proposed that further research should focus on lazyness and evaluation
order issues in pattern matching. Another point that deserves attention is to
what extent application patterns are useful for higher order functions.
Appendix A
Implementation of the
Application Pattern
Compiler
This Appendix is provided as a seperate document, entitled Application Pat-
terns in Functional Languages: Appendix A: Implementation of the Application
Pattern Compiler
63
64APPENDIX A. IMPLEMENTATION OF THE APPLICATION PATTERN COMPILER
Appendix B
Example input and output
B.0.1 Example input
progIn.amapc
1 f (2+ x ) 3 = x ^2
2
3 g ( Node x y ) = g x + g y
4 g ( Leaf x ) = x
5
6 plus ‘[0] x s = s - x , if x ≥ 0 ∧ s ≥ x
7 plus ‘[1] x s = s - x , if x ≥ 0 ∧ s ≥ x
8
9 k ( Leaf ( n +2) ) ( Node ( Leaf (1+ x ) ) ( Leaf (1+ ^ x ) ) ) = n
^ x
10 k _ _ = 1
11
12 l ( Leaf x ) ( Leaf (^ x + 1) ) = 3
13
14 f 1 2 = 3
15
16 h u = z ^2
17 where
18 z + ^k = x
19 where
20 x + (^ y +2) = y ^ u
21 where
22 y + ^ k = u +1
23 k = 14
24
25 i p = (x , y )
26 where
27 ( Just x , Just y ) = (p , p )
28
29 j ( Just x , (y , z ) ) = x + y + z
65
66 APPENDIX B. EXAMPLE INPUT AND OUTPUT
30
31 m u = y
32 where
33 y + ^z = z + 1 + u
34 where
35 z = 3
36
37 n ( x +1) = fac ( fac x )
38 where
39 fac 0 = 1
40 fac n = n * fac (n -1)
41
42 fac 0 = 1
43 fac n = n * fac (n -1)
44
45 x = 3
46
47 p ys = x + # xs
48 where
49 ( x : xs ) = ys
50
51 cons ‘[0 ,1] xs = ( hd xs , tl xs ) , if xs 6= []
52
53 q ys = f ys + # ys
54 where
55 f ( x : xs ) = 1
56 f _ = 2
57
58 r ( Leaf n ) ( Node ( Leaf (^ n +2) ) ( Leaf ( x +^ n ) ) )
59 = n * x
60 r ( Leaf 2) _
61 = 3
62 r _ ( Leaf n )
63 = n ^2
64 r _ dontcare
65 = 4
66
67 t (2*2) = 3
68 t (2+ x ) = x , if x > 10
69 t _ = 0 - 1
70
71
72 w xs = (x , x )
73 where
74 x = ( fst . cons ‘[0 ,1]) xs
75
76
77 gcd x ^x = x
78 gcd ( x + ^ y ) y = gcd x y
79 gcd x (^ x + y ) = gcd x y
67
B.0.2 Example output
progOut.ama
1 maybe * ::= Just * | Nothing
2
3 tree ::= Node tree tree | Leaf num
4
5 f var var1
6 = x1 ^ 2 , if ( match 6= Nothing ) ∧ ( var1 = 3)
7 = 3 , if ( var14 = 1) ∧ ( var15 = 2)
8 where
9 ( var14 , var15 )
10 = ( var , var1 )
11 match
12 = inv_plus_Mb_1 2 var
13 Just (( x1 ) )
14 = match
15
16 g var2
17 = ( g x2 ) + ( g y ) , if is_Node var2
18 = x3 , if is_Leaf var3
19 where
20 ( var3 )
21 = ( var2 )
22 is_Node ( Node _ _)
23 = True
24 is_Node _
25 = False
26 Node x2 y
27 = var2
28 is_Leaf ( Leaf _)
29 = True
30 is_Leaf _
31 = False
32 Leaf x3
33 = var3
34
35 inv_plus_0 x4 s
36 = s - x4 , if ( x4 ≥ 0) ∧ ( s ≥ x4 )
37
38 inv_plus_Mb_0 x4 s
39 = Just ( s - x4 ) , if ( x4 ≥ 0) ∧ ( s ≥ x4 )
40 = Nothing , otherwise
41
42 inv_plus_1 x5 s1
68 APPENDIX B. EXAMPLE INPUT AND OUTPUT
43 = s1 - x5 , if ( x5 ≥ 0) ∧ ( s1 ≥ x5 )
44
45 inv_plus_Mb_1 x5 s1
46 = Just ( s1 - x5 ) , if ( x5 ≥ 0) ∧ ( s1 ≥ x5 )
47 = Nothing , otherwise
48
49 k var4 var6
50 = n1 ^ x6 , if ( is_Leaf1 var4 ) ∧ (( match1 6= Nothing ) ∧
(( is_Node1 var6 ) ∧ (( is_Leaf2 var7 ) ∧ (( match2 6=
Nothing ) ∧ (( is_Leaf3 var9 ) ∧ ( var10 = (1 + x6 ) ) ) )
)))
51 = 1 , otherwise
52 where
53 (_ , _ )
54 = ( var4 , var6 )
55 match1
56 = inv_plus_Mb_0 2 var5
57 Just (( n1 ) )
58 = match1
59 is_Leaf1 ( Leaf _ )
60 = True
61 is_Leaf1 _
62 = False
63 Leaf var5
64 = var4
65 match2
66 = inv_plus_Mb_1 1 var8
67 Just (( x6 ) )
68 = match2
69 is_Leaf2 ( Leaf _ )
70 = True
71 is_Leaf2 _
72 = False
73 Leaf var8
74 = var7
75 is_Leaf3 ( Leaf _ )
76 = True
77 is_Leaf3 _
78 = False
79 Leaf var10
80 = var9
81 is_Node1 ( Node _ _ )
82 = True
83 is_Node1 _
84 = False
85 Node var7 var9
86 = var6
87
88 l var11 var12
69
89 = 3 , if ( is_Leaf4 var11 ) ∧ (( is_Leaf5 var12 ) ∧ ( var13
= ( x7 + 1) ) )
90 where
91 is_Leaf4 ( Leaf _ )
92 = True
93 is_Leaf4 _
94 = False
95 Leaf x7
96 = var11
97 is_Leaf5 ( Leaf _ )
98 = True
99 is_Leaf5 _
100 = False
101 Leaf var13
102 = var12
103
104 h u
105 = z ^ 2
106 where
107 var16
108 = x8
109 match3
110 = inv_plus_Mb_0 k1 var16
111 Just (( z ) )
112 = match3
113 var17
114 = y1 ^ u
115 match4
116 = inv_plus_Mb_0 ( y1 + 2) var17
117 Just (( x8 ) )
118 = match4
119 var18
120 = u + 1
121 match5
122 = inv_plus_Mb_0 k1 var18
123 Just (( y1 ) )
124 = match5
125 k1
126 = 14
127
128 i p1
129 = ( x9 , y2 )
130 where
131 ( var19 , var20 )
132 = ( p1 , p1 )
133 is_Just ( Just _ )
134 = True
135 is_Just _
136 = False
137 Just x9
70 APPENDIX B. EXAMPLE INPUT AND OUTPUT
138 = var19
139 is_Just1 ( Just _ )
140 = True
141 is_Just1 _
142 = False
143 Just y2
144 = var20
145
146 j (( var21 , ( y3 , z1 ) ) )
147 = x10 + ( y3 + z1 ) , if is_Just2 var21
148 where
149 is_Just2 ( Just _ )
150 = True
151 is_Just2 _
152 = False
153 Just x10
154 = var21
155
156 m u1
157 = y4
158 where
159 var22
160 = z2 + (1 + u1 )
161 match6
162 = inv_plus_Mb_0 z2 var22
163 Just (( y4 ) )
164 = match6
165 z2
166 = 3
167
168 n var23
169 = fac1 ( fac1 x11 ) , if match7 =6 Nothing
170 where
171 fac1 var24
172 = 1 , if var24 = 0
173 = n2 * ( fac1 ( n2 - 1) ) , otherwise
174 where
175 ( n2 )
176 = ( var24 )
177 match7
178 = inv_plus_Mb_0 1 var23
179 Just (( x11 ) )
180 = match7
181
182 fac var25
183 = 1 , if var25 = 0
184 = n3 * ( fac ( n3 - 1) ) , otherwise
185 where
186 ( n3 )
187 = ( var25 )
71
188
189 x
190 = 3
191
192 p ys
193 = x12 + (# xs )
194 where
195 var26
196 = ys
197 match8
198 = inv_cons_Mb_0_1 var26
199 Just (( x12 , xs ) )
200 = match8
201
202 inv_cons_0_1 xs1
203 = ( hd xs1 , tl xs1 ) , if xs1 6= Nil
204
205 inv_cons_Mb_0_1 xs1
206 = Just (( hd xs1 , tl xs1 ) ) , if xs1 6= Nil
207 = Nothing , otherwise
208
209 q ys1
210 = ( f1 ys1 ) + (# ys1 )
211 where
212 f1 var27
213 = 1 , if match9 6= Nothing
214 = 2 , otherwise
215 where
216 (_)
217 = ( var27 )
218 match9
219 = inv_cons_Mb_0_1 var27
220 Just (( x13 , xs2 ) )
221 = match9
222
223 r var28 var29
224 = n4 * x14 , if ( is_Leaf6 var28 ) ∧ (( is_Node2 var29 ) ∧
(( is_Leaf7 var30 ) ∧ (( var31 = ( n4 + 2) ) ∧ ((
is_Leaf8 var32 ) ∧ ( match10 6= Nothing ) ) ) ) )
225 = 3 , if ( is_Leaf9 var34 ) ∧ ( var35 = 2)
226 = n5 ^ 2 , if is_Leaf10 var36
227 = 4 , otherwise
228 where
229 (_ , dontcare )
230 = ( var28 , var29 )
231 (_ , var36 )
232 = ( var28 , var29 )
233 ( var34 , _ )
234 = ( var28 , var29 )
235 is_Leaf6 ( Leaf _ )
72 APPENDIX B. EXAMPLE INPUT AND OUTPUT
236 = True
237 is_Leaf6 _
238 = False
239 Leaf n4
240 = var28
241 is_Leaf7 ( Leaf _ )
242 = True
243 is_Leaf7 _
244 = False
245 Leaf var31
246 = var30
247 match10
248 = inv_plus_Mb_0 n4 var33
249 Just (( x14 ) )
250 = match10
251 is_Leaf8 ( Leaf _ )
252 = True
253 is_Leaf8 _
254 = False
255 Leaf var33
256 = var32
257 is_Node2 ( Node _ _ )
258 = True
259 is_Node2 _
260 = False
261 Node var30 var32
262 = var29
263 is_Leaf9 ( Leaf _ )
264 = True
265 is_Leaf9 _
266 = False
267 Leaf var35
268 = var34
269 is_Leaf10 ( Leaf _ )
270 = True
271 is_Leaf10 _
272 = False
273 Leaf n5
274 = var36
275
276 t var37
277 = 3 , if var37 = (2 * 2)
278 = x15 , if ( match11 6= Nothing ) ∧ ( x15 > 10)
279 = 0 - 1 , otherwise
280 where
281 (_)
282 = ( var37 )
283 ( var38 )
284 = ( var37 )
285 match11
73
286 = inv_plus_Mb_1 2 var38
287 Just (( x15 ) )
288 = match11
289
290 w xs3
291 = ( x16 , x16 )
292 where
293 x16
294 = ( fst . inv_cons_0_1 ) xs3
295
296 gcd x17 var39
297 = x17 , if var39 = x17
298 = gcd x18 y5 , if match12 6= Nothing
299 = gcd x19 y6 , if match13 6= Nothing
300 where
301 ( x19 , var41 )
302 = ( x17 , var39 )
303 ( var40 , y5 )
304 = ( x17 , var39 )
305 match12
306 = inv_plus_Mb_0 y5 var40
307 Just (( x18 ) )
308 = match12
309 match13
310 = inv_plus_Mb_1 x19 var41
311 Just (( y6 ) )
312 = match13
74 APPENDIX B. EXAMPLE INPUT AND OUTPUT
B.1 Creative Commons Attribution-ShareAlike
License Version 2.0
Attribution-ShareAlike 2.0
THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF
THIS CREATIVE COMMONS PUBLIC LICENSE (“CCPL” OR “LICENSE”). THE
WORK IS PROTECTED BY COPYRIGHT AND/OR OTHER APPLICABLE LAW.
ANY USE OF THE WORK OTHER THAN AS AUTHORIZED UNDER THIS LI-
CENSE OR COPYRIGHT LAW IS PROHIBITED.
BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU AC-
CEPT AND AGREE TO BE BOUND BY THE TERMS OF THIS LICENSE. THE
LICENSOR GRANTS YOU THE RIGHTS CONTAINED HERE IN CONSIDERA-
TION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS.
License
1. Definitions
1. “Collective Work” means a work, such as a periodical issue, anthology or
encyclopedia, in which the Work in its entirety in unmodified form, along
with a number of other contributions, constituting separate and indepen-
dent works in themselves, are assembled into a collective whole. A work
that constitutes a Collective Work will not be considered a Derivative Work
(as defined below) for the purposes of this License.
2. “Derivative Work” means a work based upon the Work or upon the Work
and other pre-existing works, such as a translation, musical arrangement,
dramatization, fictionalization, motion picture version, sound recording,
art reproduction, abridgment, condensation, or any other form in which
the Work may be recast, transformed, or adapted, except that a work that
constitutes a Collective Work will not be considered a Derivative Work for
the purpose of this License. For the avoidance of doubt, where the Work is
a musical composition or sound recording, the synchronization of the Work
in timed-relation with a moving image (“synching”) will be considered a
Derivative Work for the purpose of this License.
3. “Licensor” means the individual or entity that offers the Work under the
terms of this License.
4. “Original Author” means the individual or entity who created the Work.
5. “Work” means the copyrightable work of authorship offered under the
terms of this License.
6. “You” means an individual or entity exercising rights under this License
who has not previously violated the terms of this License with respect to
the Work, or who has received express permission from the Licensor to
exercise rights under this License despite a previous violation.
7. “License Elements” means the following high-level license attributes as
selected by Licensor and indicated in the title of this License: Attribution,
ShareAlike.
2. Fair Use Rights. Nothing in this license is intended to reduce, limit, or restrict
any rights arising from fair use, first sale or other limitations on the exclusive
rights of the copyright owner under copyright law or other applicable laws.
B.1. COPYRIGHT LICENSE 75
3. License Grant. Subject to the terms and conditions of this License, Licensor
hereby grants You a worldwide, royalty-free, non-exclusive, perpetual (for the
duration of the applicable copyright) license to exercise the rights in the Work
as stated below:
1. to reproduce the Work, to incorporate the Work into one or more Collective
Works, and to reproduce the Work as incorporated in the Collective Works;
2. to create and reproduce Derivative Works;
3. to distribute copies or phonorecords of, display publicly, perform publicly,
and perform publicly by means of a digital audio transmission the Work
including as incorporated in Collective Works;
4. to distribute copies or phonorecords of, display publicly, perform publicly,
and perform publicly by means of a digital audio transmission Derivative
Works.
5. For the avoidance of doubt, where the work is a musical composition:
1. Performance Royalties Under Blanket Licenses. Licensor waives the
exclusive right to collect, whether individually or via a performance
rights society (e.g. ASCAP, BMI, SESAC), royalties for the public
performance or public digital performance (e.g. webcast) of the Work.
2. Mechanical Rights and Statutory Royalties. Licensor waives the ex-
clusive right to collect, whether individually or via a music rights
society or designated agent (e.g. Harry Fox Agency), royalties for any
phonorecord You create from the Work (“cover version”) and distrib-
ute, subject to the compulsory license created by 17 USC Section 115
of the US Copyright Act (or the equivalent in other jurisdictions).
6. Webcasting Rights and Statutory Royalties. For the avoidance of doubt,
where the Work is a sound recording, Licensor waives the exclusive right
to collect, whether individually or via a performance-rights society (e.g.
SoundExchange), royalties for the public digital performance (e.g. web-
cast) of the Work, subject to the compulsory license created by 17 USC
Section 114 of the US Copyright Act (or the equivalent in other jurisdic-
tions).
The above rights may be exercised in all media and formats whether now known
or hereafter devised. The above rights include the right to make such modifi-
cations as are technically necessary to exercise the rights in other media and
formats. All rights not expressly granted by Licensor are hereby reserved.
4. Restrictions. The license granted in Section 3 above is expressly made subject
to and limited by the following restrictions:
1. You may distribute, publicly display, publicly perform, or publicly digitally
perform the Work only under the terms of this License, and You must in-
clude a copy of, or the Uniform Resource Identifier for, this License with
every copy or phonorecord of the Work You distribute, publicly display,
publicly perform, or publicly digitally perform. You may not offer or im-
pose any terms on the Work that alter or restrict the terms of this License
or the recipients’ exercise of the rights granted hereunder. You may not
sublicense the Work. You must keep intact all notices that refer to this
License and to the disclaimer of warranties. You may not distribute, pub-
licly display, publicly perform, or publicly digitally perform the Work with
any technological measures that control access or use of the Work in a
manner inconsistent with the terms of this License Agreement. The above
applies to the Work as incorporated in a Collective Work, but this does not
76 APPENDIX B. EXAMPLE INPUT AND OUTPUT
require the Collective Work apart from the Work itself to be made subject
to the terms of this License. If You create a Collective Work, upon notice
from any Licensor You must, to the extent practicable, remove from the
Collective Work any reference to such Licensor or the Original Author, as
requested. If You create a Derivative Work, upon notice from any Licensor
You must, to the extent practicable, remove from the Derivative Work any
reference to such Licensor or the Original Author, as requested.
2. You may distribute, publicly display, publicly perform, or publicly digi-
tally perform a Derivative Work only under the terms of this License, a
later version of this License with the same License Elements as this Li-
cense, or a Creative Commons iCommons license that contains the same
License Elements as this License (e.g. Attribution-ShareAlike 2.0 Japan).
You must include a copy of, or the Uniform Resource Identifier for, this
License or other license specified in the previous sentence with every copy
or phonorecord of each Derivative Work You distribute, publicly display,
publicly perform, or publicly digitally perform. You may not offer or im-
pose any terms on the Derivative Works that alter or restrict the terms
of this License or the recipients’ exercise of the rights granted hereunder,
and You must keep intact all notices that refer to this License and to the
disclaimer of warranties. You may not distribute, publicly display, pub-
licly perform, or publicly digitally perform the Derivative Work with any
technological measures that control access or use of the Work in a manner
inconsistent with the terms of this License Agreement. The above applies
to the Derivative Work as incorporated in a Collective Work, but this does
not require the Collective Work apart from the Derivative Work itself to
be made subject to the terms of this License.
3. If you distribute, publicly display, publicly perform, or publicly digitally
perform the Work or any Derivative Works or Collective Works, You must
keep intact all copyright notices for the Work and give the Original Author
credit reasonable to the medium or means You are utilizing by conveying
the name (or pseudonym if applicable) of the Original Author if supplied;
the title of the Work if supplied; to the extent reasonably practicable, the
Uniform Resource Identifier, if any, that Licensor specifies to be associated
with the Work, unless such URI does not refer to the copyright notice or
licensing information for the Work; and in the case of a Derivative Work, a
credit identifying the use of the Work in the Derivative Work (e.g., “French
translation of the Work by Original Author,” or “Screenplay based on
original Work by Original Author”). Such credit may be implemented in
any reasonable manner; provided, however, that in the case of a Derivative
Work or Collective Work, at a minimum such credit will appear where any
other comparable authorship credit appears and in a manner at least as
prominent as such other comparable authorship credit.
5. Representations, Warranties and Disclaimer
UNLESS OTHERWISE AGREED TO BY THE PARTIES IN WRITING, LI-
CENSOR OFFERS THE WORK AS-IS AND MAKES NO REPRESENTA-
TIONS OR WARRANTIES OF ANY KIND CONCERNING THE MATERI-
ALS, EXPRESS, IMPLIED, STATUTORY OR OTHERWISE, INCLUDING,
WITHOUT LIMITATION, WARRANTIES OF TITLE, MERCHANTIBILITY,
FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE
ABSENCE OF LATENT OR OTHER DEFECTS, ACCURACY, OR THE
PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT DISCOV-
ERABLE. SOME JURISDICTIONS DO NOT ALLOW THE EXCLUSION
OF IMPLIED WARRANTIES, SO SUCH EXCLUSION MAY NOT APPLY
B.1. COPYRIGHT LICENSE 77
TO YOU.
6. Limitation on Liability.
EXCEPT TO THE EXTENT REQUIRED BY APPLICABLE LAW, IN NO
EVENT WILL LICENSOR BE LIABLE TO YOU ON ANY LEGAL THE-
ORY FOR ANY SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE
OR EXEMPLARY DAMAGES ARISING OUT OF THIS LICENSE OR THE
USE OF THE WORK, EVEN IF LICENSOR HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
7. Termination
1. This License and the rights granted hereunder will terminate automatically
upon any breach by You of the terms of this License. Individuals or entities
who have received Derivative Works or Collective Works from You under
this License, however, will not have their licenses terminated provided
such individuals or entities remain in full compliance with those licenses.
Sections 1, 2, 5, 6, 7, and 8 will survive any termination of this License.
2. Subject to the above terms and conditions, the license granted here is per-
petual (for the duration of the applicable copyright in the Work). Notwith-
standing the above, Licensor reserves the right to release the Work under
different license terms or to stop distributing the Work at any time; pro-
vided, however that any such election will not serve to withdraw this Li-
cense (or any other license that has been, or is required to be, granted
under the terms of this License), and this License will continue in full force
and effect unless terminated as stated above.
8. Miscellaneous
1. Each time You distribute or publicly digitally perform the Work or a Col-
lective Work, the Licensor offers to the recipient a license to the Work on
the same terms and conditions as the license granted to You under this
License.
2. Each time You distribute or publicly digitally perform a Derivative Work,
Licensor offers to the recipient a license to the original Work on the same
terms and conditions as the license granted to You under this License.
3. If any provision of this License is invalid or unenforceable under applicable
law, it shall not affect the validity or enforceability of the remainder of
the terms of this License, and without further action by the parties to
this agreement, such provision shall be reformed to the minimum extent
necessary to make such provision valid and enforceable.
4. No term or provision of this License shall be deemed waived and no breach
consented to unless such waiver or consent shall be in writing and signed
by the party to be charged with such waiver or consent.
5. This License constitutes the entire agreement between the parties with re-
spect to the Work licensed here. There are no understandings, agreements
or representations with respect to the Work not specified here. Licensor
shall not be bound by any additional provisions that may appear in any
communication from You. This License may not be modified without the
mutual written agreement of the Licensor and You.
78 APPENDIX B. EXAMPLE INPUT AND OUTPUT
Creative Commons is not a party to this License, and makes no warranty whatsoever
in connection with the Work. Creative Commons will not be liable to You or any party
on any legal theory for any damages whatsoever, including without limitation any gen-
eral, special, incidental or consequential damages arising in connection to this license.
Notwithstanding the foregoing two (2) sentences, if Creative Commons has expressly
identified itself as the Licensor hereunder, it shall have all rights and obligations of
Licensor.
Except for the limited purpose of indicating to the public that the Work is licensed
under the CCPL, neither party will use the trademark “Creative Commons” or any
related trademark or logo of Creative Commons without the prior written consent of
Creative Commons. Any permitted use will be in compliance with Creative Com-
mons’ then-current trademark usage guidelines, as may be published on its website or
otherwise made available upon request from time to time.
Creative Commons may be contacted at http://creativecommons.org/.
Bibliography
Broberg, N., Farre, A., & Svenningsson, J. (2004). Regular expression patterns.
67–78. Retrieved on July 14, 2005, from http://www.cs.chalmers.se/
∼d00nibro/harp/harp.pdf.
Erwig, M., & Peyton Jones, S. (2000). Pattern guards and transformational
patterns. Retrieved on September 16, 2005, from http://research.
microsoft.com/∼simonpj/Papers/pat.ps.gz.
Hindley, J. R., & Seldin, J. P. (1986). Introduction to combinators and λ-
calculus. Cambridge University Press.
Hölzenspies, P. K. F. (2005). (personal communication)
Jones, M. P. (1991). Gofer 2.21 release notes. Retrieved on July
7, 2005, from http://www-i2.informatik.rwth-aachen.de/Teaching/
Praktikum/SWPSS96/Gofer/rel221.dvi.
Oosterhof, N. N., Hölzenspies, P. K. F., & Kuper, J. (2005). Application pat-
terns. In Proceedings of trends in functional programming 2005, Tallinn,
Estonia.
Papegaaij, E. (2005). The Tina language: A report on the specification and
implementation. (Personal communication)
Peyton Jones, S. (1987). The implementation of functional programming lan-
guages. Retrieved on June 23, 2005, from http://research.microsoft.
com/Users/simonpj/papers/slpj-book-1987/slpj-book-1987.pdf.
Prentice Hall.
Peyton Jones, S. (Ed.). (2003). Haskell 98 language and libraries: The re-
vised report. Retrieved on May 14, 2005, from http://www.haskell.
org/definition/haskell98-report.pdf. Cambridge University Press.
Plasmeijer, R., & Eekelen, M. van. (2001). Version 2.0 language report
[Draft]. Retrieved on June 2, 2005, from ftp://ftp.cs.kun.nl/pub/
Clean/Clean20/doc/CleanRep2.0.pdf. Department of Software Tech-
nology, University of Nijmegen, The Netherlands.
Plasmijer, R., & Eekelen, M. van. (1993). Functional programming and parallel
graph rewriting. Amsterdam [etc.]: Addison-Wesley.
Thompson, S. (1995). Miranda: The Craft of Functional Programming. Addison
Wesley.
Tullsen, M. (2000). First class patterns. In Practical aspects of declarative
languages, second international workshop,padl 2000 (Vol. 1753, pp. 1–15).
Springer-Verlag.
Wadler, P. (1992). Monads for functional programming. 118. Retrieved on
June 27, 2005, from http://homepages.inf.ed.ac.uk/wadler/papers/
marktoberdorf/marktoberdorf.pdf.
79
Application Patterns in
Functional Languages
Appendix A: Implementation of the
Application Pattern Compiler
by
Nikolaas N. Oosterhof
University of Twente
Enschede, The Netherlands
2005
2
Copyright c 2005 Nikolaas N. Oosterhof.
This document is free; you can copy, distribute, display, perform and/or modify
it under the terms of the Creative Commons Attribution-ShareAlike License
Version 2.0. A copy of the license is included in Section A.5.
The program described in this Appendix is free software; you can redistribute
it and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABIL-
ITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
Public License for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc., 675 Mass
Ave, Cambridge, MA 02139, USA.
The author may be contacted at n.n.oosterhof@student.uva.nl
3
Human-readible summary of the
Creative Commons Attribution-ShareAlike 2.0 License
You are free:
• to copy, distribute, display, and perform the work
• to make derivative works
• to make commercial use of the work
Under the following conditions:
Attribution. You must give the original author credit.
Share Alike. If you alter, transform, or build upon this
work, you may distribute the resulting work only under a
license identical to this one.
• For any reuse or distribution, you must make clear to others the license
terms of this work.
• Any of these conditions can be waived if you get permission from the
copyright holder.
Your fair use and other rights are in no way affected by the above.
A copy of the Legal Code (the full license) is included in Appendix A.5.
Contents
A Implementation 5
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
A.2 The application pattern compiler . . . . . . . . . . . . . . . . . . 5
A.2.1 The main file . . . . . . . . . . . . . . . . . . . . . . . . . 5
A.2.2 The lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
A.2.3 The parser . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.2.4 The preprocessor . . . . . . . . . . . . . . . . . . . . . . . 19
A.2.5 Creating unique identifiers . . . . . . . . . . . . . . . . . . 21
A.2.6 The actual rewriting . . . . . . . . . . . . . . . . . . . . . 25
A.2.7 The postprocessing . . . . . . . . . . . . . . . . . . . . . . 31
A.2.8 Printing the output nicely . . . . . . . . . . . . . . . . . . 34
A.3 Introducing monads . . . . . . . . . . . . . . . . . . . . . . . . . 37
A.4 Some utility functions . . . . . . . . . . . . . . . . . . . . . . . . 42
A.5 Copyright license . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4
Appendix A
Implementation of the
Application Pattern
Compiler
A.1 Introduction
This appendix contains the implementation of the Application Pattern Com-
piler, a compiler for the Amanda functional language that rewrites application
patterns. The actual implementation is given in Section A.2, describing the
lexer, parser, preprocessor, renaming, rewriting, postprocessing and printing.
The implementation makes extensive use of monads which are described in Sec-
tion A.3. Some general utility functions are given in Section A.4.
A.2 The application pattern compiler
A.2.1 The main file
main.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This is the main file .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 *
9 * This program is free software ; you can redistribute it and / or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation ; either version 2 of the License , or
12 * ( at your option ) any later version .
13 *
5
APPENDIX A. IMPLEMENTATION 6
14 * This program is distributed in the hope that it will be useful ,
15 * but WITHOUT ANY WARRANTY ; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE . See the
17 * GNU General Public License for more details .
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program ; if not , write to the Free Software
21 * Foundation , Inc . , 675 Mass Ave , Cambridge , MA 02139 , USA .
22 */
23
24 # import " util . ama "
25
26 # import " monadMb . ama "
27 # import " monadSt . ama "
28 # import " monadSts . ama "
29 # import " monadId . ama "
30
31 # import " lexer . ama "
32 # import " parser . ama "
33 # import " preproc . ama "
34 # import " uniqidfs . ama "
35 # import " rewrite . ama "
36 # import " postproc . ama "
37 # import " prettyPrint . ama "
38
39 || the main function
40 apc :: string → string
41 apc = print
42 . postproc
43 . d e fs I d fProperNaming
44 . defsAddMbInverse
45 . mergeDefs
46 . rewrDefs
47 . uniqidfs
48 . preproc
49 . parser
50 . lexer
51
52
53 || reading input file and writing output file
54 || ( the required preamble is added manually )
55 apcIO fileIn fileOut
56 = fwrite fileOut premable
57 $seq ( fappend fileOut . apc . fread ) fileIn
58 where
59 premable = " maybe * ::= Just * | Nothing \ n \ n "
60 ++ " thenMb Nothing _ = Nothing \ n "
61 ++ " thenMb _ x = x\n\n"
62 ++ " tree ::= Node tree tree | Leaf num \ n \ n "
63
APPENDIX A. IMPLEMENTATION 7
64 || an example
65 apcIOEx
66 = apcIO " progIn . amapc " " progOut . ama "
A.2.2 The lexer
lexer.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the lexer .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10 /*
11 * The lexer state
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13 lexerTp == ( num , string )
14
15 lexerSt * ::= { remaining :: [*] || remaining chars to be lexed
16 , pos :: num || horizontal position
17 , vpos :: num || vertical position
18 , offSides :: [ num ] || stack of indent positions
19 , inDef :: bool || already seen the first ’= ’ - char on this
line ?
20 }
21
22 nilLexer s = { remaining = s , pos =0 , offSides =[] , vpos = 0 , inDef = False }
23
24 getLexerSt s0 = unitSts s0
25 setLexerSt s1 s0 = unitSts s10 s10
26 where s10 = s1 & s0
27
28 /*
29 * Spotting items
30 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
31 || spot single element
32 spot c ( st ={ remaining =[] }) = unitSts False st
33 spot c ( st ={ remaining =( x : xs ) }) = unitSts ( c = x ) st
34
35 || spot multiple elements
36 spots [ c ] = spot c
37 spots ( c : cs ) = spot c $bindSts ( b →
38 ifSts b ( spots cs )
39 ( unitSts False )
APPENDIX A. IMPLEMENTATION 8
40 )
41
42 item ( st ={ remaining =( x : xs ) , pos = pos_ })
43 = [( x , st & { remaining = xs , pos = pos_ +1}) ]
44
45 item _
46 = []
47
48
49 lit c st
50 = item_st , if item_st 6= [] ∧ x = c
51 = [] , otherwise
52 where item_st = item st
53 [( x , _ ) ] = item_st
54
55 anylit cs st = concat [ lit c st | c <- nodup cs ]
56
57 lits [ c ] = lit c $bindSts ( x → unitSts [ x ])
58
59 lits ( c : cs ) = lit c $bindSts ( x →
60 lits cs $bindSts ( xs →
61 unitSts ( x : xs ) ))
62
63
64
65 untilLits str
66 = ( lits str
67 ) $biasedOrSts
68 ( item $bindSts ( c → untilLits str $bindSts ( cs → unitSts ( c : cs ) ) )
69 )
70
71 /*
72 * Processing indentation
73 *
74 * Assumption : every line consists of :
75 *
76 * blank ^* dedent ^* [ non - blank ( any ) ^*] newLine
77 *
78 * A comment is / not / a blankitem
79 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
80
81 /* dedentLit requires sufficient dedents before any non - blank literal
82 0 1 2 3 4 5 6 7 8 9 012 34567 ...
83 ... = ...
84 where
85 ... = ...
86 ... -- → { for this expression : position p =8 , stack =[14 ,6 ,4]}
87
88 */
89
APPENDIX A. IMPLEMENTATION 9
90 dedentLit ( st ={ remaining =[] , offSides =( x : xs ) })
91 = [((" dedent " , "") , st & { offSides = xs }) ]
92
93 dedentLit ( st ={ pos =p , offSides =( x : xs ) })
94 = [((" dedent " , "") , st & { offSides = xs }) ] , if p < x
95 = [] , otherwise
96
97
98 dedentLit _
99 = []
100
101
102 /* Process an indent token ( currently only "=")
103 Assumption : the first occurence of that token is indeed the indent - version
104 this means that " f ( p =( x : xs ) ) = ..." can not be parsed
105 to provide for this : - add a parenthesis counter to the state
106 - write a left / right parenthesis parser that
adjusts that counter
107 - give these parser higher priority dan
indentLit
108 */
109
110
111 indentLit
112 = ( biasedOrsSts . map lits . domain ) indentNames $bindSts ( tk →
113 makeIndent tk )
114
115
116 makeIndent tk ( st ={ pos =p , offSides = offSides_ , inDef = False })
117 = fromJust
118 ( ( (
119 ( hdMb offSides_ $bindMb ( x →
120 ( ( x = p ) $guardMb (
121 unitMb ( unitSts ( lookUp indentNames tk ++ redentSuffix , tk )
122 ( st & { inDef = True }) )
123 )
124 ) $alternativeMb
125 ( ( x < p ) $guardMb (
126 unitMb ( unitSts ( lookUp indentNames tk , tk )
127 ( st & { inDef = True , offSides = p : offSides_ })
)
128 )
129 ) $orJust
130 ( zeroSts st
131 ) )
132 ) $orJust
133 ( unitSts ( lookUp indentNames tk , tk )
134 ( st & { inDef = True , offSides = p : offSides_ })
135 ) )
136 ) $orJust
APPENDIX A. IMPLEMENTATION 10
137 ( zeroSts st
138 )
139 )
140
141 makeIndent _ st = zeroSts st
142
143
144 whereLit = getStateSts $bindSts ( ( st ={ pos = pos , offSides = offSides_ }) →
145 lits " where " $thenSts (
146 updStateSts ( & { inDef = False , offSides = pos : offSides_ } )
147 $thenSts (
148 unitSts (" where " , " where ") )))
149
150
151 newLineLit = lits "\ n " $thenSts (
152 getStateSts $bindSts ( ( st ={ vpos = vpos }) →
153 updStateSts ( & { inDef = False , pos =0 , vpos = vpos +1} ) $thenSts (
154 unitSts (" newline " , "\ n ") )))
155
156
157
158 eofLit ( st ={ remaining =[] , offSides =[]}) = ( unitSts (" eof " , []) ) st
159 eofLit st = zeroSts st
160
161 /*
162 * Defining operators , delimeters and keywords
163 *
164 * - is is assumed that these identifier names (" neg " , " lnot " , " length " ,
165 * " cons " , ...) are / not defined / by the programmer
166 * - however , for inverse definitions these names / must / be used by the
167 * programmer (" neq ‘[0]" , " lnot ‘[0]" , " length ‘[0]" , " cons ‘[0 ,1]" , ...)
168 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
169
170 prefixNames = [ (" -" , " neg ")
171 , ("~" , " lnot ")
172 , ("#" , " length ")
173 ]
174
175
176 infixNames = [ (":" , " cons ")
177 , ("++" , " join ")
178 , (" - -" , " nioj ")
179 , ("\\/" , " lor ")
180 , ("∧\" , " land ")
181 , ("~" , " lnot ")
182 , (" <" , " lt ")
183 , (" <=" , " lte ")
184 , ("=" , " eq ")
185 , ("6=" , " neq ")
186 , ("≥" , " geq ")
APPENDIX A. IMPLEMENTATION 11
187 , (" >" , " gt ")
188 , ("+" , " plus ")
189 , (" -" , " minus ")
190 , ("*" , " times ")
191 , (" // " ," floatdivide ")
192 , ("/" , " divide ")
193 , ("%" , " modulo ")
194 , ( ’d ’:" iv " , " divide ") || } fake amanda parser ; it must
195 , ( ’m ’:" od " , " modulo ") || } have a bad hack here
196 , ("^" , " power ")
197 , ("." , " funcomp ")
198 , ("!" , " index ")
199 ]
200
201 delimNames = [ ("|" , " pipe ")
202 , (";" , " semicolon ")
203 , ("=" , " eq ")
204 , ("{" , " lcurly ")
205 , ("}" , " rcurly ")
206 , ("(" , " lparen ")
207 , (") " , " rparen ")
208 , ("[" , " lbrack ")
209 , ("]" , " rbrack ")
210 , (" ," , " comma ")
211 , (" → " , " larrow ")
212 , (" < -" , " rarrow ")
213 ]
214
215 indentNames = [ ("::=" , " typeDef ")
216 , ("::" , " typeDecl ")
217 , ("==" , " typeEq ")
218 , ("=" , " funDef ")
219 ]
220
221 redentSuffix = " _redent "
222
223 litSuffix = ""
224
225 keywordNames = map dupl [ " if "
226 , " otherwise "
227 ]
228 where dupl x = (x , x )
229
230
231
232 /*
233 * Lexing standard literals
234 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
235
236 lexChar = lexSpecialChar $biasedOrSts
APPENDIX A. IMPLEMENTATION 12
237 ( item $checkSts (~. member "\ ’\"") )
238
239
240 lexSpecialChar = (( lit ’\\ ’) $thenSts (
241 ( item $checkSts ( member ( domain specialChars ) ) )
242 $doSts ( lookUp specialChars )
243 ))
244
245 || characters that are escaped by a backslash ’\ ’
246 specialChars = [ ( ’n ’ , ’\n ’)
247 , ( ’b ’ , ’\b ’)
248 , ( ’t ’ , ’\t ’)
249 , ( ’r ’ , ’\r ’)
250 , ( ’a ’ , ’\a ’)
251 , ( ’\\ ’ , ’\\ ’)
252 , ( ’\ ’ ’ , ’\ ’ ’) || note : we don ’ t allow " ’" or ’" ’;
253 || use "\ ’" and ’\" ’ instead
254 , ( ’\" ’ , ’\" ’)
255 ]
256
257 charLit = seqSts [ lit ’\ ’ ’
258 , lexChar
259 , lit ’\ ’ ’
260 ]
261 $bindSts ( c → unitSts (" char " , c ) )
262
263
264 failLit ( st = { pos = pos_ , vpos = vpos_ , remaining = remaining_ })
265 = error errorMsg
266 where
267 errorMsg = " Lexer : unrecognised character sequence at line "
268 ++ itoa vpos_ ++ ":" ++ itoa pos_
269 ++ "\ nRemaining character sequence : "
270 ++ ( if (# remaining_ > remLength ) ( take remLength remaining_ ++ "
[...]")
271 remaining_
272 )
273 where remLength = 100
274
275
276
277 stringLit = seqSts [ lits "\""
278 , oneOrMoreSts lexChar
279 , lits "\""
280 ]
281 $doSts concat $bindSts ( s → unitSts (" string " , s ) )
282
283
284 lexDigit = item $checkSts isDigit
285 where isDigit c = ( ’0 ’ <= c ∧ c <= ’9 ’)
APPENDIX A. IMPLEMENTATION 13
286
287
288 numLit = ( ( lit ’-’ $thenSts lexPosFloat ) $bindSts ( x →
289 unitSts (" num " , ’ - ’: x ) )
290 ) $biasedOrSts
291 ( lexPosFloat $bindSts ( x →
292 unitSts (" num " , x ) )
293 )
294
295 lexPosFloat = lexNat $bindSts ( x →
296 ( lit ’. ’ $thenSts (
297 lexNat $bindSts ( y →
298 unitSts ( x ++ "." ++ y ) ))
299 ) $biasedOrSts
300 ( unitSts ( x )
301 ) )
302
303
304 lexNat = oneOrMoreSts lexDigit
305
306 chars m n = map decode [ i | cm := code m ; cn := code n ; i < -[ cm .. cn ]]
307
308 lexIdf = startLexIdf
309 $biasedOrSts
310 anylit ( chars ’0 ’ ’9 ’
311 ++ chars ’A ’ ’Z ’
312 )
313
314 startLexIdf = anylit ( " _ " ++ chars ’a ’ ’z ’ )
315
316 idfLit = ( lit ’^ ’ $thenSts (
317 startLexIdf $bindSts ( i →
318 zeroOrMoreSts lexIdf $bindSts ( is →
319 unitSts ( " ctxIdf " , i : is ) )))
320 ) $biasedOrSts
321 ( ( anylit (" _ " ++ chars ’a ’ ’z ’) ) $bindSts ( i →
322 ( zeroOrMoreSts lexIdf ) $bindSts ( is →
323 ( invFunSignature $bindSts ( sign →
324 unitSts (" invIdf " , i : is ++ sign ) )
325 ) $biasedOrSts
326 ( unitSts (" idf " , i : is )
327 ) ))
328 )
329
330 invFunSignature = seqSts [ lits " ‘["
331 , ( lexNat $encloseSts ( lits " ,") ) $doSts concat
332 , lits "]"
333 ]
334 $doSts concat
335
APPENDIX A. IMPLEMENTATION 14
336
337 constrLit = ( anylit ( chars ’A ’ ’Z ’) ) $bindSts ( i →
338 ( oneOrMoreSts lexIdf ) $bindSts ( is →
339 unitSts (" constrIdf " , i : is ) ))
340
341
342 lineCommentLit = lits "||" $thenSts (
343 newLineLit $thenSts (
344 unitSts (" comment " , []) ))
345
346 lexBlank = item $checkSts ( member " ")
347
348 blankLit = ( oneOrMoreSts lexBlank ) $thenSts (
349 unitSts (" blank " , []) )
350
351 preprocLit = biasedOrsSts ( map lits ["# import " , "# synonym " , "# operator "])
352 $bindSts ( xs →
353 zeroOrMoreSts lexBlank $thenSts (
354 stringLit $bindSts ( (_ , ys ) →
355 zeroOrMoreSts lexBlank $thenSts (
356 newLineLit $thenSts (
357 unitSts (" preproc " , xs ++ " " ++ ys ) )))))
358
359 /*
360 * Definition of priority of literals
361 *
362 * For some items this order is / very / important ( a . o . indentation )
363 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
364
365 litMapping
366 = [ (" blank " ++ litSuffix , blankLit )
367 , (" where " ++ litSuffix , whereLit )
368 , (" indent " ++ litSuffix , indentLit )
369 , (" dedent " ++ litSuffix , dedentLit )
370 , (" lineComment "++ litSuffix , lineCommentLit )
371 , (" preproc " ++ litSuffix , preprocLit )
372 ] ++ makeMapping keywordNames ++
373 [ (" idf " ++ litSuffix , idfLit )
374 ] ++ makeMapping ( prefixNames ++ infixNames ++ delimNames ) ++
375 [ (" char " ++ litSuffix , charLit )
376 , (" stringLit " ++ litSuffix , stringLit )
377 , (" num " ++ litSuffix , numLit )
378 , (" constr " ++ litSuffix , constrLit )
379 , (" newline " ++ litSuffix , newLineLit )
380 , (" fail " ++ litSuffix , failLit )
381 ]
382
383 || For this implementation , we want to ignore some literals
384 ignoreNames = [" blank " , " lineComment " , " preproc " , " newline "]
385
APPENDIX A. IMPLEMENTATION 15
386 greaterLength (x , _ ) (y , _ ) = # x > # y
387
388 filterIgnore = filter (~. member ignoreNames . fst )
389
390 makeMapping stuff = [ ( name ++ litSuffix , lits x $thenSts ( unitSts ( name , x ) ) )
391 | (x , name ) <- mergeSortWith greaterLength stuff ]
392 where
393
394
395 otherMapping = [ ( name ++ litSuffix , lits x $thenSts ( unitSts ( name , x ) ) )
396 | (x , name ) <- otherNames ]
397
398 otherNames = mergeSortWith greaterLength ( prefixNames
399 ++ infixNames
400 ++ delimNames
401 ++ keywordNames )
402
403 programLit
404 = altStarSts ( range litMapping ) eofLit
405
406 lexer :: string → [( string , string ) ]
407 lexer = filterIgnore . fst . hd . programLit . nilLexer
A.2.3 The parser
parser.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the parser .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10 /*
11 * Definition of types for definitions and expressions
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13 defTp
14 ::= FunDef exprTp || { left hand side }
15 [( exprTp , exprTp ) ] || = [{ value1 , guard1 } , ... , { valueN , guardN }]
16 [ defTp ] || where { subDef1 , ... , subDefK }
17
18 exprTp
19 ::= FA [ exprTp ] || FA [f , x1 , ... , xN ] is f x1 ... xN
20 || where f must be an * Idf
21 | Constr [ char ] [ exprTp ] || Constr "" [ x1 , ... , xN ] is an N - tuple
APPENDIX A. IMPLEMENTATION 16
22 || Constr c [] is the constant c
23 || Constr C [ x1 , ... , xN ] is C x1 ... xN
24 | Idf [ char ] || Idf i is the identifier i
25 | InvIdf [ num ] [ char ] || InvIdf [ s1 , ... , sK ] f is f ‘[ s0 , ... , sK ]
26 | CtxIdf [ char ] || CtxIdf i is the identifier ^ i
27 || ( bound in context )
28
29 /*
30 * Parsing items
31 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
32 parserSt * ::= { remainingP :: [*] }
33 nilParser s = { remainingP = s }
34
35
36 token t ( st = { remainingP = (( x , y ) : xs ) })
37 = unitSts y ( st & { remainingP = xs }) , if x = t
38 = [] , otherwise
39
40 token _ _ = []
41
42 anyToken ts st = concat [ token t st | t <- nodup ts ]
43
44 /*
45 * Parsing standard literals
46 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
47
48 litExpr = anyToken [" char " , " num " , " string "] $doSts ( x → Constr x [])
49
50
51 listExpr = token " lbrack " $thenSts (
52 ( ( ( expr $separateSts ( token " comma ") )
53 $doSts makeListExpr
54 ) $bindSts ( xs →
55 token " rbrack " $thenSts (
56 unitSts xs ))
57 ) $biasedOrSts
58 ( token " rbrack " $thenSts (
59 unitSts ( makeListExpr [] ) ) )
60 )
61 where
62 makeListExpr [] = Constr " Nil " []
63 makeListExpr ( x : xs ) = FA [ Idf " cons " , x , makeListExpr xs ]
64
65 idfExpr = ( token " ctxIdf " $bindSts ( x →
66 unitSts ( CtxIdf x ) )
67 ) $biasedOrSts
68 ( token " invIdf " $doSts ma k e In v F un S ig n a tu r e
69 ) $biasedOrSts
70 ( token " idf " $bindSts ( x →
71 unitSts ( Idf x ) )
APPENDIX A. IMPLEMENTATION 17
72 )
73
74 faExpr = atomExpr $bindSts ( i →
75 ( oneOrMoreSts atomExpr $bindSts ( xs →
76 unitSts ( FA ( i : xs ) ) )
77 ) )
78
79 constrExpr = ( token " constrIdf " $bindSts ( c →
80 zeroOrMoreSts ( constrExpr $biasedOrSts atomExpr )
81 $bindSts ( xs →
82 unitSts ( Constr c xs ) ))
83 )
84
85 || parse an inverse function signature f ‘[...]
86 || a bit ugly , as it uses the lexerState .
87 make I nv F u nS i gn ature = fst
88 . hd
89 . ( oneOrMoreSts lexIdf $bindSts ( is →
90 lits " ‘[" $thenSts (
91 ( lexNat $separateSts ( lits " ,")
92 $doSts ( map atoi ) ) $bindSts ( sign →
93 lit ’] ’ $thenSts (
94 unitSts ( InvIdf sign is ) ))))
95 )
96 . nilLexer
97
98 /*
99 Priorities of prefix and infix operators
100 */
101 preinfixOps = [ ( [] , [":" , "++" , " - -"] )
102 , ( [] , ["\\/"] )
103 , ( [] , ["∧\"] )
104 , ( ["~"] , [] )
105 , ( [] , [" <" , " <=" , "=" , "6=" , "≥" , " >"] )
106 , ( [] , ["+" , " -"] )
107 , ( [" -"] , [])
108 , ( [] , ["*" , " // " , "/" , ’d ’:" iv " , ’m ’:" od "])
109 , ( [] , ["^"] )
110 , ( [] , ["."] )
111 , ( ["#"] , [] )
112 , ( [] , ["!"] )
113 ]
114
115 || quite elegant solution : -)
116 expr = makePreInfixExpr expr simpleExpr preinfixOps
117
118 makePreInfixExpr _ finalExpr []
119 = finalExpr
120
121 makePreInfixExpr curExpr finalExpr (( prefixes , infixes ) : xs )
APPENDIX A. IMPLEMENTATION 18
122 = prefixExpr $biasedOrSts infixExpr
123 where
124 prefixExpr = biasedOrsSts [ token tname $bindSts ( x →
125 curExpr $bindSts ( c →
126 unitSts ( FA [ Idf tname , c ]) ))
127 | t <- prefixes
128 ; tname := lookUp prefixNames t
129 ]
130 infixExpr = nextExpr $bindSts ( c →
131 biasedOrsSts ( [ ( token tname $bindSts ( x →
132 curExpr $bindSts ( d →
133 unitSts ( FA [ Idf tname , c , d ]) ))
134 )
135 | t <- infixes
136 ; tname := lookUp infixNames t
137 ] ++ [ unitSts c ]
138 ) )
139 nextExpr = makePreInfixExpr nextExpr finalExpr xs
140
141
142 simpleExpr = atomExpr $orSts faExpr $orSts constrExpr
143
144 eofExpr ( st ={ remainingP =[]})
145 = unitSts [] st
146 eofExpr st
147 = zeroSts st
148
149 atomExpr = ( token " lparen " $thenSts (
150 ( token " rparen " $thenSts (
151 unitSts ( Constr "" []) )
152 ) $biasedOrSts
153 ( expr $bindSts ( x →
154 ( token " comma " $thenSts (
155 expr $separateSts ( token " comma ") $bindSts ( xs →
156 token " rparen " $thenSts (
157 unitSts ( Constr [] ( x : xs ) ) )))
158 ) $biasedOrSts
159 ( token " rparen " $thenSts (
160 unitSts x )
161 ) )
162 ) )
163 ) $orSts idfExpr $orSts listExpr $orSts litExpr
164
165
166 funcDefinition = expr $bindSts ( x →
167 token " funDef " $thenSts (
168 funcClause $separateSts ( token " funDef_redent ")
169 $bindSts ( cs →
170 ( token " where " $thenSts (
171 oneOrMoreSts funcDefinition $bindSts ( ws →
APPENDIX A. IMPLEMENTATION 19
172 token " dedent " $thenSts (
173 token " dedent " $thenSts (
174 unitSts ( FunDef x cs ws ) ))))
175 ) $biasedOrSts
176 ( token " dedent " $thenSts (
177 unitSts ( FunDef x cs [] ) )
178 ) )))
179
180
181 funcClause = expr $bindSts ( x →
182 ( token " comma " $thenSts (
183 ( token " if " $thenSts (
184 expr $bindSts ( y →
185 unitSts (x , y ) ))
186 ) $biasedOrSts
187 ( token " otherwise " $thenSts (
188 unitSts (x , Constr " True " []) )
189 ) )
190 ) $orSts
191 ( unitSts (x , Constr " True " []) )
192 )
193
194 program :: stateSts ( parserSt ( string , string ) ) [ defTp ]
195 program = oneOrMoreSts funcDefinition $bindSts ( x →
196 eofExpr $thenSts (
197 unitSts x ))
198
199 || In case of an parsing error the message is not really informative : -|
200 parser :: [( string , string ) ] → [ defTp ]
201 parser s
202 = error " Nothing to parse : empty input " , if s = []
203 = error " Parsing error , somewhere in the program ." , if parses = []
204 = fst ( hd parses ) , otherwise
205 where
206 parses = program ( nilParser s )
A.2.4 The preprocessor
preproc.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the preprocessor .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
APPENDIX A. IMPLEMENTATION 20
9
10 /*
11 * Rewriting left hand side and / or complete definitions
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 rewriteLHside rw ( FunDef f vgs ws )
15 = FunDef ( rw f ) vgs ( map ( rewriteLHside rw ) ws )
16
17 rewriteLRHside rw ( FunDef f vgs ws )
18 = rewriteLHside rw ( FunDef f
19 ( map ( mapPair rw ) vgs )
20 ( map ( rewriteLRHside rw ) ws )
21 )
22
23
24
25
26 rewriteExpr rw ( FA fargs ) = rw ( FA ( map ( rewriteExpr rw ) fargs ) )
27 rewriteExpr rw ( Constr c args ) = rw ( Constr c ( map ( rewriteExpr rw ) args ) )
28 rewriteExpr rw i = rw i
29
30 /*
31 * Rewriting join operators so that e . g . the application pattern
32 * x ++ " ," ++ y ++ " ," ++ z
33 * is rewritten into
34 * join3 x " ," ( join3 y " ," z )
35 * making it suitable for solving for x , y and z by using the inverse join ‘[0 ,2]
36 *
37 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
38 rewriteJoin3 ( f =( FA [ CtxIdf " join " , FA [ CtxIdf " join " , x , y ] , z ]) )
39 = FA ( CtxIdf " join3 " : [x , y , z ]) , if isKnown y
40 = f , otherwise
41
42 rewriteJoin3 ( f =( FA [ CtxIdf " join " , x , FA [ CtxIdf " join " , y , z ]]) )
43 = FA ( CtxIdf " join3 " : [x , y , z ]) , if isKnown y
44 = f , otherwise
45
46 rewriteJoin3 otherExpr
47 = otherExpr
48
49
50 isKnown ( Idf _ ) = False
51 isKnown ( Constr _ args ) = forAll args isKnown
52 isKnown ( FA ( _ : args ) ) = forAll args isKnown
53 isKnown ( CtxIdf _ ) = True
54 isKnown ( InvIdf _ _ ) = True
55
56
57 /*
58 * Add the caret in an application pattern in expressions where it
APPENDIX A. IMPLEMENTATION 21
59 * may be omitted by the programmer , i . e .
60 * - for operators
61 * - in nested function applications
62 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
63 addCtxFA nested ( FA ( i : args ) )
64 = FA ( i1 : args1 )
65 where
66 i1 = makeCtxIdf ( nested \/ isOperator ) i
67 where
68 isOperator = ~( empty [ j | (_ , j ) <- infixNames ++ prefixNames ; Idf j = i ])
69 makeCtxIdf True ( Idf i ) = CtxIdf i
70 makeCtxIdf _ i = i
71 args1 = map ( addCtxFA True ) args
72
73 addCtxFA nested ( Constr c args )
74 = Constr c args1
75 where
76 args1 = map ( addCtxFA nested ) args
77
78 addCtxFA _ i
79 = i
80
81
82 rewrLHsides funcs = map ( rewriteLHside ( limiterates funcs ) )
83 preproc = rewrLHsides [ addCtxFA False , rewriteJoin3 ]
A.2.5 Creating unique identifiers
uniqidfs.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the part that renames identifiers to unique ones .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10 /*
11 * Retrieving primary and secundary identifiers :
12 * - primary : the identifiers that are bound in a definition
13 * - secundary : arguments for the primary identifiers
14 *
15 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
16
17 primSecIdfs atTop ( FA ( CtxIdf f : args ) )
18 = map ( primSecIdfs atTop ) args $bindId ( idfs →
APPENDIX A. IMPLEMENTATION 22
19 unitId ( concatPair ( idfs ) ) )
20
21
22 primSecIdfs atTop ( FA ( f : args ) )
23 = primSecIdfs True f $bindId ( idf →
24 map ( primSecIdfs False ) args $bindId ( idfs →
25 unitId ( concatPair ( idf : idfs ) ) ))
26
27 primSecIdfs _ ( CtxIdf i )
28 = ([] , [])
29
30 primSecIdfs atTop ( InvIdf _ _ )
31 = ([] , [])
32
33 primSecIdfs atTop ( Constr _ args )
34 = map ( primSecIdfs atTop ) args $bindId ( idfs →
35 unitId ( concatPair idfs ) )
36
37 primSecIdfs atTop ( Idf i )
38 = ([ i ] , []) , if atTop
39 = ([] , [ i ]) , otherwise
40
41 || assumption : all identifiers are different
42 exprPrimSecIdfs atTop f s
43 = (( mapPair ( filter ((~) . empty ) ) . primSecIdfs atTop ) f , s )
44
45
46 defsPrimSecIdfs atTop defs s
47 = ( pairAsSet ( concatPair [ fst ( exprPrimSecIdfs atTop fargs nilPair ) | FunDef
fargs _ _ <- defs ]) , s )
48
49
50 /*
51 * Renaming identifiers so they are bound only once in the whole program .
52 * A stack is used for the different scopes .
53 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
54 popSubs (( _ : subs ) , used ) = unitSt subs ( subs , used )
55
56 pushSubs old new ( subs , used )
57 = ( allSubs , ( allSubs , newUsed ) )
58 where
59 allSubs = ( zip2 old new ) : subs
60 newUsed = asSet ( used ++ old ++ new )
61
62
63 subsDefPrimIdfs defs ( s =( subs , _ ) )
64 = ( map ( subsDefIdfs subs ) defs , s )
65
66 subsDefIdfs subs ( FunDef f vgs ws )
APPENDIX A. IMPLEMENTATION 23
67 = FunDef ( subsExprIdf subs f ) (( map . mapPair ) ( subsExprIdf subs ) vgs ) ( map (
subsDefIdfs subs ) ws )
68
69 subsSecIdfs f ( s =( subs , used ) )
70 = ( subsExprIdf subs f , s )
71
72
73
74 subsVgsExprIdfs vgs ( subs , used )
75 = (( map . mapPair ) ( subsExprIdf subs ) vgs , ( subs , used ) )
76
77 subsExprIdf subs ( FA fargs )
78 = FA ( map ( subsExprIdf subs ) fargs )
79
80 subsExprIdf subs ( Constr c args )
81 = Constr c ( map ( subsExprIdf subs ) args )
82
83 subsExprIdf subs ( Idf i )
84 = Idf i1 , if found 6= []
85 = Idf i , otherwise
86 where
87 found = lookUpAll ( concat subs ) i
88 ( i1 : _ ) = found
89
90 subsExprIdf subs ( CtxIdf i )
91 = CtxIdf i1 , if found 6= []
92 = CtxIdf i , otherwise
93 where
94 found = lookUpAll ( concat subs ) i
95 ( i1 : _ ) = found
96
97 subsExprIdf _ i
98 = i
99
100 /*
101 Creating fresh identifiers
102 */
103 numString n = combinations ( bcxyz : rep ( a : bcxyz ) (n -1) )
104 where
105 ( a : bcxyz ) = map decode [ code ’0 ’.. code ’9 ’]
106
107 bdNewIdf i ( st =( x , used ) )
108 = unitSt newIdf (x , used ++ [ newIdf ])
109 where
110 ( newIdf : _ ) = filter ((~) . member used )
111 ( map ( i ++) ("" : concatmap numString [1..]) )
112
113
114 /*
115 The actual renaming .
APPENDIX A. IMPLEMENTATION 24
116 ( bd refers to Barendrecht without any apparant reason )
117 */
118
119 bds :: [ defTp ] → stateT ([[( string , string ) ]] , [ string ]) [ defTp ]
120 || < input > < substitutions > < bound > < output >
121
122 bds defs
123 = defsPrimSecIdfs True defs $bindSt ( ( prim , _ ) →
124 bdNewIdfs prim $bindSt ( prim1 →
125 pushSubs prim prim1 $thenSt (
126 subsDefPrimIdfs defs $bindSt ( defs1 →
127 traverse bd defs1 $bindSt ( defs2 →
128 unitSt defs2 )))))
129
130 bd :: defTp → stateT ([[( string , string ) ]] , [ string ]) defTp
131 bd ( FunDef f vgs ws )
132 = exprPrimSecIdfs True f $bindSt ( (_ , sec ) →
133 bdNewIdfs sec $bindSt ( sec1 →
134 pushSubs sec sec1 $thenSt (
135 bds ws $bindSt ( ws1 →
136 subsVgsExprIdfs vgs $bindSt ( vgs1 →
137 subsSecIdfs f $bindSt ( f1 →
138 popSubs $thenSt (
139 popSubs $thenSt (
140 unitSt ( FunDef f1 vgs1 ws1 ) ))))))))
141
142 /*
143 rename definitions
144
145 renaming wildcard " _ " is necessary : if left out , the definition
146
147 f _ 0 = ...
148 f x y = ... x ... y ...
149
150 is rewritten to something like
151
152 f _ var2 = ...
153 f x y = ... x ... y ..
154
155 which during merging leads to the where clause
156
157 ...
158 where (x , y ) = (_ , var )
159
160 so that x is not bound properly .
161 */
162
163 bddefs defs
164 = traverse bd defs ([[]] , wildCardIdfName : prim )
165 where
APPENDIX A. IMPLEMENTATION 25
166 (( prim , _ ) , _ ) = defsPrimSecIdfs True defs ([] , [])
167
168
169 bdNewIdfs = traverse bdNewIdf
170
171 uniqidfs :: stateT [ defTp ] [ string ]
172 uniqidfs defs
173 = ( used1 , defs1 )
174 where
175 ( defs1 , (_ , used1 ) ) = bddefs defs
A.2.6 The actual rewriting
rewrite.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file does the actual rewriting .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10 idfSep = " _ "
11 varPrefix = " var "
12 matchPrefix = " match "
13
14 maybeSfx = " _Mb "
15
16 invPrefix =" inv "
17
18 newIdfPrefix = " idf_ "
19
20 wildCardIdfName = " _ "
21 wildCardIdf = Idf wildCardIdfName
22
23 /*
24 * The rewriting state
25 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
26
27 patTp
28 ::= { wheres :: [ defTp ] || where clauses to be added
29 , guards :: [ exprTp ] || guards to be added
30 , invFunDefs :: [([ char ] , ([ num ] , [ num ]) ) ] || list of (f , i * ’s , j * ’ s
31 || - i * ’ s : indices provided args
32 || - j * ’ s : " required "
33 , usedIdfs :: [ string ] || bound identifiers
APPENDIX A. IMPLEMENTATION 26
34 , provided :: [( exprTp , exprTp ) ] || provided identifiers and
condition
35 , required :: [( exprTp , exprTp ) ] || required identifiers and
condition
36 }
37
38 nilPat
39 = { wheres = []
40 , guards = []
41 , invFunDefs = []
42 , usedIdfs = []
43 , provided = []
44 , required = []
45 }
46
47 initPatSt ( used , defs )
48 = nilPat
49 & { invFunDefs = [( i , (s , [0..# s +(# as ) -2] - - s ) )
50 | FunDef ( FA (( InvIdf s i ) : as ) ) _ _ <- defs ]
51 , usedIdfs = used }
52
53 define f g
54 = FunDef f [( g , Constr " True " []) ] []
55
56 /*
57 Updating the state
58 */
59 addGuard x ( st ={ guards = guards })
60 = (x , st & { guards = guards ++ [ x ]})
61
62 addWheres xs ( st ={ wheres = wheres })
63 = ( xs , st & { wheres = wheres ++ xs })
64
65
66 addRequired xs g ( st ={ required = required })
67 = ( xs , st & { required = required ++ [ (i , g ) | i <- concatmap ctxIdfs xs ]})
68
69
70 addProvided xs g ( st ={ provided = provided })
71 = ( xs , st & { provided = provided ++ [ (i , g ) | i <- xs ]})
72
73 || find context identifiers ( these are the only that may cause problems )
74 ctxIdfs ( FA ( _ : args ) )
75 = concatmap ctxIdfs args
76
77 ctxIdfs ( Constr _ args )
78 = concatmap ctxIdfs args
79
80 ctxIdfs ( CtxIdf i )
81 = [ Idf i ]
APPENDIX A. IMPLEMENTATION 27
82
83 ctxIdfs _
84 = []
85
86
87
88 /*
89 Adds created guards to existing guards
90 - returns new guards and created where clauses
91 - as a side effect all created guards and where clauses so far
92 are removed from the current state
93 */
94
95 gatherVgsWs vgs st
96 = unitSt ( vgs1 , ws1 ) ( st & emptySt )
97 where
98 { wheres = wheres
99 , guards = guards
100 , provided = provided
101 , required = required
102 } = st
103 vgs1 = [( v , foldr makeAnd g
104 ( fixPatternOrder provided required guards ) )
105 | (v , g ) <- vgs ]
106 ws1 = wheres
107 emptySt = { wheres =[] , guards =[] , provided =[] , required =[]}
108
109 makeAnd x y = FA [ Idf " land " , x , y ]
110
111 /*
112 Fixes order of pattern matching , if necessary . This is only necessary for
113 identifiers used in the context that are bound in a pattern to the right
114 in of the current pattern ( in a lhs )
115
116 For example , in the definition
117
118 f (p x ^y) (q y)
119
120 first y must be resolved ( through q ‘[0] , assumed that it is defined ) ,
121 then x must be resolved ( through p ‘[0] , " " ).
122
123 The order is fixed by moving guards to the left , if necessary .
124
125 Note : there is / no check / for cyclic dependancies .
126 */
127
128 fixPatternOrder provided required guards
129 = map fst patFixed
130 where
131 patDeps = transClose [ ( reqgd , provgd )
APPENDIX A. IMPLEMENTATION 28
132 | ( prov , provgd ) <- provided
133 ; ( req , reqgd ) <- required
134 ; prov = req
135 ]
136 patMDPs = [ (m , (d , p ) )
137 | m , p <- guards , [0..]
138 ; d := lookUpAll patDeps m
139 ]
140 patFixed = mergeSortWith patOrd patMDPs
141
142 /*
143 for the proper order of matching patterns
144 - first consider dependencies
145 - if no dependencies exist , use the ordinary ( left - to - right ) order
146
147 in a tuple (m , (d , p ) ) : m is the matching guard
148 d are other matchings guards m depends on
149 p is the position of the pattern ( p is in [0..])
150 */
151
152 patOrd ( m0 , ( d0 , p0 ) ) ( m1 , ( d1 , p1 ) )
153 = ( d01 ∧ ~ d10 )
154 \/ ~( d10 ∧ ~ d01 )
155 \/ ( p1 > p0 )
156 where
157 d01 = member d1 m0
158 d10 = member d0 m1
159
160
161
162 /*
163 Create new identifier
164 */
165
166 patNewIdf prefix ( s ={ usedIdfs = usedIdfs })
167 = ( Idf newIdf , s & { usedIdfs =( newIdf : usedIdfs ) })
168 where
169 allIdfs = map ( prefix ++) ("" : concatmap numString [1..])
170 ( newIdf : _ ) = filter (~.( member usedIdfs ) ) allIdfs
171
172 patNewIdfs = traverse patNewIdf
173
174 /*
175 Find inverse function definition
176 - if none is found a runtime exception is thrown
177 - if multiple definitions are found the first is taken
178 */
179 patInvFunDef i args ( s ={ invFunDefs = invFunDefs })
180 = error (" No suitable inverse defined for " ++ i ) , if rps = []
181 = ( hd rps , s ) , otherwise
APPENDIX A. IMPLEMENTATION 29
182 where
183 rps = [ ( invIdfAsMb ( InvIdf provi i ) , prov , req )
184 | ( provi , reqi ) <- lookUpAll invFunDefs i
185 ; req := reqi $fromList args
186 ; forAll req isKnown
187 ; prov := provi $fromList args
188 ]
189
190
191 invIdfAsMb ( InvIdf c i )
192 = InvIdf c ( i ++ maybeSfx )
193
194 /*
195 * Rewriting a pattern
196 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
197
198 || Application pattern
199 rewrPat ( pat =( FA ( CtxIdf i : args ) ) )
200 = patNewIdfs [" var "] $bindSt ( [ var ] →
201 addGuard ( FA [ Idf " eq " , var , pat ])
202 $thenSt (
203 unitSt var ) ) , if forAll args isKnown
204
205 = patNewIdfs [" var " , " match "] $bindSt ( [ var , match ] →
206 unitSt ( FA [ Idf " neq " , match , Constr " Nothing " []])
207 $bindSt ( guard →
208 addGuard guard $thenSt (
209 patInvFunDef i args $bindSt ( ( finv , prov , req ) →
210 traverse rewrPat prov $bindSt ( prov1 →
211 addWheres [ define match
212 ( FA ( finv : req ++[ var ]) )
213 , define ( Constr " Just " [ Constr "" prov1 ])
214 match
215 ] $thenSt (
216 addRequired req guard $thenSt (
217 addProvided prov1 guard $thenSt (
218 unitSt var ))))))))
219
220 || Constant application pattern ( that binds no identifiers )
221 rewrPat ( pat =( FA ( f : args ) ) )
222 = patNewIdfs [" var "] $bindSt ( [ var ] →
223 addGuard ( FA [ Idf " eq " , var , pat ])
224 $thenSt (
225 unitSt var ) ) , if forAll args isKnown
226 = error " Oops ! why rewrite function application ?" , otherwise
227
228 || Tuple
229 rewrPat ( Constr "" args )
230 = traverse rewrPat args $bindSt ( args1 →
231 unitSt ( Constr "" args1 ) )
APPENDIX A. IMPLEMENTATION 30
232
233 || Constant
234 rewrPat ( pat =( Constr c []) )
235 = patNewIdfs [" var "] $bindSt ( [ var ] →
236 addGuard ( FA [ Idf " eq " , var , pat ])
237 $thenSt (
238 unitSt var ))
239
240 || Constructor with ≥ 1 argument
241 rewrPat ( Constr c args )
242 = patNewIdfs [" var " , " is_ " ++ c ] $bindSt ( [ var , isConstr ] →
243 unitSt ( FA [ isConstr , var ]) $bindSt ( guard →
244 addGuard guard $thenSt (
245 traverse rewrPat args $bindSt ( args1 →
246 addWheres [ define ( FA [ isConstr , Constr c ( rep wildCardIdf (# args ) ) ])
247 ( Constr " True " [])
248 , define ( FA [ isConstr , wildCardIdf ])
249 ( Constr " False " [])
250 , define ( Constr c args1 )
251 var
252 ] $thenSt (
253 addProvided args1 guard $thenSt (
254 unitSt var ))))))
255
256 || Identifier bound from context : treat like a constant
257 rewrPat (( CtxIdf i ) )
258 = patNewIdfs [" var "] $bindSt ( [ var ] →
259 addGuard ( FA [ Idf " eq " , var , Idf i ])
260 $thenSt (
261 unitSt var ))
262
263 || Any other pattern , i . e . only an identifier
264 rewrPat i
265 = unitSt i
266
267
268
269 /*
270 * Rewriting a definition
271 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
272
273 getMakePats ( pat =( FA (( CtxIdf i ) : args ) ) )
274 = ( [ pat ] , ([ p ] → p ) , False )
275
276 getMakePats ( FA ( i : args ) )
277 = ( args , ( a → FA ( i : a ) ) , True )
278
279 getMakePats pat
280 = ( [ pat ] , ([ p ] → p ) , False )
281
APPENDIX A. IMPLEMENTATION 31
282 getPats expr
283 = pats
284 where
285 ( pats , _ , _ ) = getMakePats expr
286
287 rewrDef ( FunDef fun vgs ws )
288 = unitSt ( getMakePats fun ) $bindSt ( ( pats , makePat , outSide ) →
289 traverse rewrPat pats $bindSt ( pats1 →
290 gatherVgsWs vgs $bindSt ( ( vgs1 , ws1 ) →
291 traverse rewrDef ws $bindSt ( ws2 →
292 unitSt ( if outSide [( FunDef ( makePat pats1 ) vgs1 ( concat ws2 ++ ws1 ) ) ]
293 (( FunDef ( makePat pats1 ) vgs []) : ws1 ++ concat ws2 )
294 || note : use old vgs as we dont check for pattern match
295 ) ))))
296
297 rewrDefs ( ud =( used , defs ) )
298 = ( concat . fst . traverse rewrDef defs . initPatSt ) ud
A.2.7 The postprocessing
postproc.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the postprocessor .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10
11 /*
12 * Comparing patterns to decide whether definitions must be merged .
13 *
14 * This is necessary because replacing non - identier patterns by
15 * identifier patterns can make subsequent equations in function
16 * definitions unreachable
17 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
18
19 equalPat ( FA ( f : xs ) ) ( FA ( g : ys ) )
20 = f = g ∧ and ( map2 equalPat xs ys )
21 where
22
23 equalPat ( Constr c xs ) ( Constr d ys )
24 = and ( ( c = d ) : map2 equalPat xs ys )
25
26 equalPat ( Idf _ ) ( Idf _ ) = True
APPENDIX A. IMPLEMENTATION 32
27 equalPat ( CtxIdf _ ) ( CtxIdf _ ) = True
28 equalPat ( InvIdf _ _ ) ( InvIdf _ _ ) = True
29
30 equalPat _ _ = False
31
32 equalDefPat f g
33 = fp = gp ∧ equalPat x y
34 where
35 (x , y ) = mapPair getFun (f , g )
36 where
37 getFun ( FunDef f _ _ ) = f
38 ( fp , gp ) = mapPair ( fst . primSecIdfs True ) (x , y )
39
40
41 /*
42 * Combining two definitions
43 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
44 joinDefs ( FunDef f0 vgs0 ws0 ) ( FunDef f1 vgs1 ws1 )
45 = FunDef f0
46 ( vgs0 ++ vgs1 )
47 ( alignPats : ws0 ++ ws1 )
48 where
49 ( pats0 , pats1 ) = mapPair getPats ( f0 , f1 )
50 alignPats = define ( Constr "" pats1 ) ( Constr "" pats0 )
51
52 combineDefs ( d : ds ) = foldl joinDefs d ds
53
54 iterateDefs f defs
55 = f [ FunDef fun vgs ( iterateDefs f ws )
56 | FunDef fun vgs ws <- defs
57 ]
58 mergeDefs :: [ defTp ] → [ defTp ]
59 mergeDefs = iterateDefs (( map combineDefs ) . ( partition equalDefPat ) )
60
61 /*
62 * For each inverse function definition , add an extra definition
63 * that returns a value of the maybe type
64 *
65 * That is , for each definition
66 *
67 * f ‘[...] :: ... → tp
68 * f ‘[...] x1 ... xK
69 * = v1 , if g1
70 * ...
71 * = vN , if gN
72 *
73 * we add an extra definition
74 *
75 * f_Mb ‘[...] :: ... → maybe tp
76 * f_Mb ‘[...] x1 ... xK
APPENDIX A. IMPLEMENTATION 33
77 * = Just v1 , if g1
78 * ...
79 * = Just vN , if gN
80 * = Nothing , otherwise
81 *
82 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
83
84 addMbInverse ( def =( FunDef ( FA (( f =( InvIdf _ _ ) ) : args ) ) vgs ws ) )
85 = [ def , defMb ]
86 where
87 defMb = FunDef ( FA (( invIdfAsMb f ) : args ) )
88 ( map addJust vgs ++ [ nothingOtherwise ])
89 ws || assume no inverses are defined in where clauses
90 where
91 addJust (v , g ) = ( Constr " Just " [ v ] , g )
92 nothingOtherwise = ( Constr " Nothing " [] , Constr " True " [])
93
94 addMbInverse def
95 = [ def ]
96
97 defsAddMbInverse :: [ defTp ] → [ defTp ]
98 defsAddMbInverse
99 = concatmap addMbInverse
100
101 /*
102 * Rename identifers of the form InvIdf and CtxIdf
103 * so that they are understood by the Amanda compiler
104 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
105 defs I df P r op e rN aming
106 = map ( rewriteLRHside ( rewriteExpr e x p rI d f Pr o pe r N am i n g ) )
107
108 expr I df P r op e rN aming ( InvIdf s i )
109 = Idf ( invPrefix
110 ++ idfSep
111 ++ i
112 ++ idfSep
113 ++ ( enclose "" idfSep "" ( map itoa s ) )
114 )
115
116 expr I df P r op e rN aming ( CtxIdf i )
117 = Idf i
118
119 expr I df P r op e rN aming i
120 = i
121
122 /*
123 * Very limited postprocessing
124 * Replace expressions " x ∧ True " and " True ∧ x " by " x "
125 "( x ) " by " x "
126 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
APPENDIX A. IMPLEMENTATION 34
127
128 rewrAndTrue ( FA [ Idf " land " , Constr " True " [] , x ]) = x
129
130 rewrAndTrue ( FA [ Idf " land " , x , Constr " True " []]) = x
131
132 rewrAndTrue x = x
133
134
135 rewrSingleConstr ( Constr "" [ x ]) = x
136
137 rewrSingleConstr x = x
138
139 postproc :: [ defTp ] → [ defTp ]
140 postproc = map ( rewriteLRHside ( limiterates ( map rewriteExpr funcs ) ) )
141 where
142 funcs = [ rewrAndTrue , rewrSingleConstr ]
A.2.8 Printing the output nicely
prettyPrint.ama
1 /* the Application Pattern Compiler : a program that translates
2 * a functional language with application patterns into semantic
3 * equivalent runnable code .
4 *
5 * This file contains the prettyPrint functionality .
6 *
7 * Copyright ( c ) 2005 Nikolaas N . Oosterhof
8 */
9
10 /*
11 * Positioning of blocks of text above and next to each other
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 nextTo a [] = a
15 nextTo a [[]] = a
16 nextTo [] b = b
17 nextTo [[]] b = b
18 nextTo a b = [ la ++ lb | la , lb <- filla , fillb ]
19 where
20 ( xa , xb ) = mapPair ( max . map #) (a , b )
21 ( ya , yb ) = mapPair (#) (a , b )
22 filla = fill ( rep ’ ’ xa ) height ( map ( fill ’ ’ xa ) a )
23 fillb = fill ( rep ’ ’ xb ) height ( map ( fill ’ ’ xb ) b )
24 height = max2 ya yb
25
26 nextTos = foldr nextTo []
27
APPENDIX A. IMPLEMENTATION 35
28 above a [] = a
29 above [] b = b
30 above a b = filla ++ fillb
31 where
32 ( xa , xb ) = mapPair ( max . map #) (a , b )
33 filla = map ( fill ’ ’ width ) a
34 fillb = map ( fill ’ ’ width ) b
35 width = max2 xa xb
36
37 aboves = foldr above []
38
39 fill atom length line = line ++ rep atom ( length - (# line ) )
40
41
42 optAbove a [] = []
43 optAbove a [[]] = [[]]
44 optAbove a b = a $above b
45
46 optNextTo a [] = []
47 optNextTo a [[]] = [[]]
48 optNextTo a b = a $nextTo b , otherwise
49
50 /*
51 * Printing definitions and expressions nicely
52 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
53
54 || the boolean denotes whether the result must not be enclosed by parenthesis
55 generic prettyPrint :: bool → * → [ char ]
56
57 prettyPrint _ ( Idf f )
58 = f
59
60 prettyPrint _ ( CtxIdf f )
61 = ’^ ’: f
62
63 prettyPrint _ ( InvIdf sign f )
64 = f ++ " ‘" ++ ( filter (6=’ ’) . toString ) sign
65
66 prettyPrint True ( Constr [] xs )
67 = enclose "(" " , " ") " ( map ( prettyPrint True ) xs )
68
69 prettyPrint _ ( Constr i [])
70 = i
71
72 prettyPrint True ( Constr i xs )
73 = prettyPrint True (( Idf i ) : xs )
74
75 prettyPrint True ( FA [ Idf f , arg ])
76 = prettyPrint True ( Constr fshort [ arg ])
77 where
APPENDIX A. IMPLEMENTATION 36
78 fshort = fromJust ( ( lookUpMb ( invert prefixNames ) f
79 ) $orJust f
80 )
81
82 prettyPrint True ( FA [ Idf f , arg0 , arg1 ])
83 = prettyPrint True farg01
84 where
85 farg01 = fromJust ( ( lookUpMb ( invert infixNames ) f $bindMb ( fshort →
86 unitMb [ arg0 , Idf fshort , arg1 ] )
87 ) $orJust [ Idf f , arg0 , arg1 ]
88 )
89
90 prettyPrint True ( FA ( f : args ) )
91 = prettyPrint True ( f : args )
92
93 prettyPrint b ( FunDef f vgs ws )
94 = unlines ( [ printF ]
95 $above printVgs
96 $above ( [" where "]
97 $optAbove ([" "] $optNextTo printWs )
98 )
99 )
100 where
101 printF = prettyPrint b f
102 printVgs = prettyPrintVgs b vgs
103 printWs = aboves ( map ( lines . prettyPrint b ) ws )
104
105 prettyPrintVgs b vgs
106 = nextTos [ rep defEq (# vgs )
107 , map ( prettyPrint b . fst ) vgs
108 , guards
109 ]
110 where
111 guards = [ guard
112 | (_ , g ) , i <- vgs , [1..]
113 ; guard := if ( g = ifTrue )
114 ( if (# vgs = 1)
115 ""
116 ( if ( i = (# vgs ) )
117 " , otherwise "
118 (" , if " ++ prettyPrint b g )
119 )
120 )
121 (" , if " ++ prettyPrint b g )
122 ]
123 defEq = " = "
124 ifTrue = Constr " True " []
125
126 prettyPrint b (x , y )
127 = prettyPrint True x ++ " " ++ prettyPrint True y
APPENDIX A. IMPLEMENTATION 37
128
129 prettyPrint b (( d = FunDef f cgs ws ) : ds )
130 = ( unlines . aboves . map ((++[" "]) . lines . prettyPrint True ) ) ( d : ds )
131
132 prettyPrint True []
133 = []
134
135 prettyPrint True ( x : xs )
136 = enclose "" " " "" ( map ( prettyPrint False ) ( x : xs ) )
137
138 prettyPrint False y
139 = "(" ++ prettyPrint True y ++ ") "
140
141 prettyPrint _ x
142 = toString x
143
144
145 || Remove spaces at the end of each line
146 crop = unlines . map cropLine . lines
147 where
148 cropLine = reverse . ( dropwhile (= ’ ’) ) . reverse
149
150
151 print :: [ defTp ] → string
152 print = crop . prettyPrint True
A.3 Introducing monads
monadMb.ama
1 /*
2 * Maybe monad
3 *
4 * implementation inspired by Philip Wadler (1992) , MfFP
5 *
6 * 11 -2005 Nikolaas N . Oosterhof
7 */
8
9 maybe * ::= Nothing | Just *
10
11 unitMb :: * → maybe *
12 unitMb a = Just a
13
14 zeroMb = Nothing
15
16 bindMb :: maybe * → (* → maybe **) → maybe **
17 bindMb ( Nothing ) _ = Nothing
APPENDIX A. IMPLEMENTATION 38
18 bindMb ( Just a ) f = f a
19
20 thenMb :: maybe * → maybe ** → maybe **
21 thenMb a b = bindMb a ( _ → b )
22
23 alternativeMb ( Just a ) _ = Just a
24 alternativeMb ( Nothing ) b = b
25
26 alternativesMb = foldl alternativeMb Nothing
27
28 guardMb False _ = Nothing
29 guardMb True a = a
30
31 hdMb [] = Nothing
32 hdMb ( a : as ) = Just a
33
34 tlMb [] = Nothing
35 tlMb ( a : as ) = Just as
36
37 hdtlMb [] = Nothing
38 hdtlMb ( a : as ) = Just (a , as )
39
40
41
42 lastMb [] = Nothing
43 lastMb [ x ] = Just x
44 lastMb ( _ : xs ) = lastMb xs
45
46 frontMb [] = Nothing
47 frontMb [ x ] = Just []
48 frontMb ( x : xs ) = frontMb xs $bindMb ( frontxs → unitMb ( x : frontxs ) )
49
50
51 fromJust ( Just x ) = x
52 fromJust _ = error " fromJust "
53
54 fromJusts = map fromJust . filter (6=Nothing )
55
56 orJust a b = a $alternativeMb ( unitMb b )
57
58 isNothing Nothing = True
59 isNothing _ = False
60
61 areNothing = and . map isNothing
62
63 lookUpMb [] _ = Nothing
64 lookUpMb (( x , y ) : xys ) key = (( x = key ) $guardMb unitMb y )
65 $alternativeMb lookUpMb xys key
66
67 lookMbUpMb xs key = key $bindMb ( x →
APPENDIX A. IMPLEMENTATION 39
68 hdMb ( filter ((= x ) . fst ) xs ) $bindMb ( (_ , y ) →
69 unitMb y ))
monadSt.ama
1 /*
2 * State - transition monad
3 *
4 * implementation inspired by Philip Wadler (1992) , MfFP
5 *
6 * 11 -2005 Nikolaas N . Oosterhof
7 */
8
9 stateT * ** == * → (** , *)
10
11 unitSt :: ** → stateT * **
12 unitSt x st = (x , st )
13
14 bindSt :: stateT * ** → (** → stateT * ***) → stateT * ***
15 bindSt p q s
16 = q x s1
17 where (x , s1 ) = p s
18
19 thenSt p q
20 = p $bindSt ( _ → q )
21
22 getSt :: stateT * **
23 getSt st = ( st , st )
24
25 setSt st _ = ( st , st )
26 updSt f = getSt $bindSt ( s →
27 unitSt ( f s ) $bindSt ( s1 →
28 setSt s1 ))
29
30 traverse :: (** → stateT * ***) → [**] → stateT * [***]
31 traverse f [] st = ([] , st )
32 traverse f ( x : xs ) st = ( x1 : xs2 , st2 )
33 where
34 ( x1 , st1 ) = f x st
35 ( xs2 , st2 ) = traverse f xs st1
monadSts.ama
1 /*
2 * State - transition - with - choice monad
3 *
APPENDIX A. IMPLEMENTATION 40
4 * implementation inspired by Philip Wadler (1992) , MfFP
5 *
6 * 11 -2005 Nikolaas N . Oosterhof
7 */
8
9
10 stateSts * ** == * → [(** , *) ]
11
12 unitSts :: ** → stateSts * **
13 unitSts x st = [( x , st ) ]
14
15 zeroSts x = []
16
17 bindSts :: stateSts * ** → (** → stateSts * ***) → stateSts * ***
18 bindSts p q st0
19 = [ (y , st2 ) | (x , st1 ) <- p st0 ; (y , st2 ) <- q x st1 ]
20
21 thenSts :: stateSts * ** → stateSts * *** → stateSts * ***
22 thenSts p q = bindSts p ( _ → q )
23
24 getStateSts st = unitSts st st
25
26 updStateSts f st0 = setStateSts ( f st0 ) st0
27
28 setStateSts st _ = unitSts st st
29
30
31 orSts :: stateSts * ** → stateSts * ** → stateSts * **
32 orSts p q st0 = p st0 ++ q st0
33
34 biasedOrSts p q st0 = q st0 , if pst0 = []
35 = pst0 , otherwise
36 where pst0 = p st0
37
38 orsSts = foldr orSts zeroSts
39 biasedOrsSts = foldr biasedOrSts zeroSts
40
41 orUnitSts p altval = biasedOrSts p ( unitSts altval )
42
43
44 checkSts p check = p $bindSts ( x → if ( check x ) ( unitSts x ) ( zeroSts ) )
45
46 guardSts check p = checkSts p check
47
48 || parse smallest list " p p ... p q "
49 untilSts p q = ( q )
50 $biasedOrSts
51 ( p $bindSts ( x →
52 untilSts p q $bindSts ( xs →
53 unitSts ( x : xs ) ))
APPENDIX A. IMPLEMENTATION 41
54 )
55
56
57 || parse smalles list " p p ... p q " , return pair (p ’s , q )
58 upToSts p q = ( q $bindSts ( y → unitSts ([] , y ) ) )
59 $biasedOrSts
60 ( p $bindSts ( x →
61 upToSts p q $bindSts (( xs , y ) →
62 unitSts ( x : xs , y ) ))
63 )
64
65 || parse " p q p ... p q p "
66 encloseSts p q = p $bindSts ( x →
67 ( q $bindSts ( y →
68 encloseSts p q $bindSts ( xs →
69 unitSts ( x : y : xs ) ))
70 ) $orUnitSts [ x ] )
71
72 || parse " p q p ... p q p " , but leave out the q ’ s in the result
73
74 separateSts p q = p $bindSts ( x →
75 ( q $thenSts (
76 separateSts p q $bindSts ( xs →
77 unitSts ( x : xs ) ))
78 ) $orUnitSts [ x ] )
79
80
81 || parse p0 p1 ... pN
82
83 seqSts [] = unitSts []
84 seqSts ( p : ps ) = p $bindSts ( x →
85 ( seqSts ps ) $bindSts ( xs →
86 unitSts ( x : xs ) ))
87
88 doSts p f = p $bindSts ( x → ( unitSts ( f x ) ) )
89
90 foldrSts f zero p = ( p $bindSts ( x →
91 foldrSts f zero p $bindSts ( xs →
92 unitSts ( f x xs ) ) ))
93 $biasedOrSts ( unitSts zero )
94
95
96 zeroOrMoreSts p = oneOrMoreSts p
97 $biasedOrSts ( unitSts [])
98
99 || parse longest list p ^+
100
101 oneOrMoreSts p = p $bindSts ( x →
102 ( oneOrMoreSts p $bindSts ( xs →
103 unitSts ( x : xs ) )
APPENDIX A. IMPLEMENTATION 42
104 ) $biasedOrSts
105 ( unitSts [ x ]
106 ) )
107
108
109
110
111 ifSts = if
112
113 || altStarSts parsers stopparser
114 altStarSts ps q
115 = ( q $thenSts ( unitSts [])
116 ) $biasedOrSts
117 ( biasedOrsSts ps $bindSts ( x →
118 altStarSts ps q $bindSts ( xs →
119 unitSts ( x : xs ) ))
120 )
121
122 valsSts = map fst
monadId.ama
1 /*
2 * The trivial identify monad
3 */
4
5 bindId x f = f x
6 unitId x = x
A.4 Some utility functions
util.ama
1 /*
2 * Utility functions
3 *
4 * 11 -2005 Nikolaas N . Oosterhof
5 */
6
7 string == [ char ]
8
9 lookUp [] key = error (" Lookup : not found key " ++ toString key )
10 lookUp (( x , y ) : ys ) key = y , if x = key
11 = lookUp ys key , otherwise
12
APPENDIX A. IMPLEMENTATION 43
13 lookUpAll [] key = []
14 lookUpAll (( x , y ) : ys ) key = y : more , if x = key
15 = more , otherwise
16 where
17 more = lookUpAll ys key
18
19
20 doMapping [] key f = []
21 doMapping (( x , y ) : ys ) key f = (x , f y ) : more , if x = key
22 = (x , y ) : more , otherwise
23 where
24 more = doMapping ys key f
25
26 update [] key z = [( key , z ) ]
27 update (( x , y ) : ys ) key z = (x , y ) : update ys key z , if x 6= key
28 = (x , z ) : ys , otherwise
29
30
31
32 unitMapping x y = [( x , y ) ]
33
34 joinMapping xs ys = [ ( key , ( nodup . concat ) ( lookUpAll ( xs ++ ys ) key ) ) | key <-
( nodup . opPair (++) . mapPair domain ) ( xs , ys ) ]
35
36 joinMappings = foldr joinMapping []
37
38
39 filterDomain f xys = [ (x , y ) | (x , y ) <- xys ; f x ]
40
41 filterRange f xys = [ (x , y ) | (x , y ) <- xys ; f y ]
42
43 mapMapping f xs = [ (x , f y ) | (x , y ) <- xs ]
44
45 appendMapping xs key s = doMapping xs key (++ s )
46
47 domain = map fst
48 range = map snd
49
50 invert = map swapPair
51 where swapPair (x , y ) = (y , x )
52
53 concatmap f = concat . ( map f )
54
55
56
57 front [ a ] = []
58 front ( a : as ) = a : front as
59
60 last [ a ] = a
61 last ( _ : as ) = last as
APPENDIX A. IMPLEMENTATION 44
62
63
64 nand a b = ~( a ∧ b )
65 nor a b = ~( a \/ b )
66
67 id x = x
68
69
70 asSet = sort . nodup
71
72 cup x y = asSet ( x ++ y )
73 cap x y = xy -- ( ( xy -- x ) $cup ( xy -- y ) )
74 where
75 xy = x $cup y
76
77 nilPair = ([] , [])
78 mapPair f (a , b ) = ( f a , f b )
79 opPair f (a , b ) = a $f b
80 joinPair (a , b ) (c , d ) = ( a ++ c , b ++ d )
81 concatPair = foldr joinPair nilPair
82
83 mapFst f (a , b ) = ( f a , b )
84 mapSnd f (a , b ) = (a , f b )
85
86
87 foldrPair (f , g ) (a , b ) xys = ( foldr f a xs , foldr g b ys )
88 where ( xs , ys ) = unzip xys
89
90
91
92 || ’ cross - product ’ of list of lists , using lists instead of tuples
93 || combinations [[1 ,2] , [3 ,4 ,5] , [6]] === [[1 , 3 , 6] , [1 , 4 , 6] , [1 , 5 , 6] , [2 ,
3 , 6] , [2 , 4 , 6] , [2 , 5 , 6]]
94 combinations [ a ] = [ [ x ] | x <- a ]
95 combinations ( a : as ) = [ x : y | x <- a ; y <- combinations as ]
96 combinations [] = []
97
98 unitC [ x ] = [[ c ] | c <- x ]
99 unitC ( x : xs ) = [ i : j | i <- x ; j <- unitC xs ]
100
101 bindC [ x ] f = [ [ f i ] | i <- x ]
102 bindC ( x : xs ) f = [ f i : j | i <- x ; j <- bindC xs f ]
103
104 unzip :: [(* , **) ] → ([*] , [**])
105 unzip [] = ([] , [])
106 unzip (( x , y ) : xys ) = ( x : xs , y : ys )
107 where ( xs , ys ) = unzip xys
108
109
110 sqnc [] x = x
APPENDIX A. IMPLEMENTATION 45
111 sqnc ( f : fs ) x = sqnc fs ( f x )
112
113 generic size :: * → num
114 size ( n = num ) = 1
115 size ( c = char ) = 1
116 size ( b = bool ) = 1
117 size [] = 0
118 size ( x : xs ) = size x + size xs
119 size (x , y ) = size x + size y
120
121 generic enclose :: [ char ] → [ char ] → [ char ] → * → [ char ]
122 enclose left mid right [] = left ++ right
123 enclose left mid right [ x ] = left ++ toString x ++ right
124 enclose left mid right ( x : xs ) = left ++ toString x ++ concatmap (( mid ++) . toString
) xs ++ right
125
126
127 generic toString :: * → [ char ]
128 toString ( n = num ) = itoa n
129 toString ( b = bool ) = if b " True " " False "
130 toString (( c = char ) : cs ) = c : cs
131 toString ( c = char ) = [ ’\ ’ ’ , c , ’\ ’ ’]
132 toString [] = "[]"
133 toString ( x : xs ) = enclose "[" " , " "]" ( x : xs )
134 toString (x , y ) = concat ["(" , toString x ," , " , toString y , ") "]
135 toString (x , y , z ) = concat ["(" , toString x ," , " , toString y , " ," , toString
z , ") "]
136
137 idxs xs = [ i | i , j <- nats 0 , xs ]
138
139 pam [] _ = []
140 pam ( f : fs ) x = f x : pam fs x
141
142 biasedJoin [] y = y
143 biasedJoin x _ = x
144
145
146 generic equals :: * → * → bool
147 equals ( x = bool ) y = x = y
148 equals ( x = num ) y = x = y
149 equals ( x = char ) y = x = y
150 equals [] [] = True
151 equals [] _ = False
152 equals _ [] = False
153 equals ( x : xs ) ( y : ys ) = equals x y ∧ equals xs ys
154
155 pipe [] _ = []
156 pipe ( f : fs ) s = out : pipe fs s2
157 where ( out , s2 ) = f s
158
APPENDIX A. IMPLEMENTATION 46
159 limit ( x : y : ys ) = x , if x = y
160 = limit ( y : ys ) , otherwise
161
162 limit [ x ] = x
163
164
165
166 forAll xs f = and ( map f xs )
167
168 limiterate f = limit . ( iterate f )
169
170 limiterates [] x = x
171 limiterates ( ffs =( f : fs ) ) x
172 = x , if lims = x
173 = limiterates ffs lims , otherwise
174 where
175 lims = limiterates fs ( limiterate f x )
176
177 pairAsSet = mapPair ( sort . nodup . filter ((~) . empty ) )
178
179 fromList is xs = [ xs ! i | i <- is ]
180
181 case x f = f x
182
183 splitOn :: (* → bool ) → [*] → ([*] , [*])
184 splitOn f [] = nilPair
185 splitOn f ( x : xs ) = px $joinPair splitOn f xs
186 where
187 px = ([ x ] , [] ) , if f x
188 = ([] , [ x ]) , otherwise
189
190 || partitions a list of elements
191 || based on an equivalence relation
192 partition :: (* → * → bool ) → [*] → [[*]]
193 partition f []
194 = []
195
196 partition f ( x : xs )
197 = ( x : alike ) : partition f different
198 where
199 ( alike , different ) = splitOn ( f x ) xs
200
201 map2 :: (* → ** → ***) → [*] → [**] → [***]
202 map2 f xs ys = [ f x y | (x , y ) <- zip2 xs ys ]
203
204
205 mergeSortWith f [] = []
206 mergeSortWith f [ x ] = [ x ]
207 mergeSortWith f xs = ( joinListsWith f . mapPair ( mergeSortWith f ) . splitList ) xs
208 where mapPair f (x , y ) = ( f x , f y )
APPENDIX A. IMPLEMENTATION 47
209
210 splitList xs = split (# xs /2) xs
211
212
213 joinListsWith _ ( xs , []) = xs
214 joinListsWith _ ([] , ys ) = ys
215 joinListsWith f (( x : xs ) , ( y : ys ) ) = x : joinListsWith f ( xs , y : ys ) , if f x y
216 = y : joinListsWith f ( x : xs , ys ) , otherwise
217
218 listElemDo f g [] = []
219 listElemDo f g ( x : xs ) = g x ++ listElemDo f g xs , if f x
220 = x : listElemDo f g xs , otherwise
221
222
223 transStep xs = nodup ( xs ++ [( x , z ) | (x , y1 ) <- xs ; ( y2 , z ) <- xs ; y1 = y2 ])
224
225 transClose = limiterate transStep
APPENDIX A. IMPLEMENTATION 48
A.5 Creative Commons Attribution-ShareAlike
License Version 2.0
Attribution-ShareAlike 2.0
THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF
THIS CREATIVE COMMONS PUBLIC LICENSE (“CCPL” OR “LICENSE”). THE
WORK IS PROTECTED BY COPYRIGHT AND/OR OTHER APPLICABLE LAW.
ANY USE OF THE WORK OTHER THAN AS AUTHORIZED UNDER THIS LI-
CENSE OR COPYRIGHT LAW IS PROHIBITED.
BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU AC-
CEPT AND AGREE TO BE BOUND BY THE TERMS OF THIS LICENSE. THE
LICENSOR GRANTS YOU THE RIGHTS CONTAINED HERE IN CONSIDERA-
TION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS.
License
1. Definitions
1. “Collective Work” means a work, such as a periodical issue, anthology or
encyclopedia, in which the Work in its entirety in unmodified form, along
with a number of other contributions, constituting separate and indepen-
dent works in themselves, are assembled into a collective whole. A work
that constitutes a Collective Work will not be considered a Derivative Work
(as defined below) for the purposes of this License.
2. “Derivative Work” means a work based upon the Work or upon the Work
and other pre-existing works, such as a translation, musical arrangement,
dramatization, fictionalization, motion picture version, sound recording,
art reproduction, abridgment, condensation, or any other form in which
the Work may be recast, transformed, or adapted, except that a work that
constitutes a Collective Work will not be considered a Derivative Work for
the purpose of this License. For the avoidance of doubt, where the Work is
a musical composition or sound recording, the synchronization of the Work
in timed-relation with a moving image (“synching”) will be considered a
Derivative Work for the purpose of this License.
3. “Licensor” means the individual or entity that offers the Work under the
terms of this License.
4. “Original Author” means the individual or entity who created the Work.
5. “Work” means the copyrightable work of authorship offered under the
terms of this License.
6. “You” means an individual or entity exercising rights under this License
who has not previously violated the terms of this License with respect to
the Work, or who has received express permission from the Licensor to
exercise rights under this License despite a previous violation.
7. “License Elements” means the following high-level license attributes as
selected by Licensor and indicated in the title of this License: Attribution,
ShareAlike.
2. Fair Use Rights. Nothing in this license is intended to reduce, limit, or restrict
any rights arising from fair use, first sale or other limitations on the exclusive
rights of the copyright owner under copyright law or other applicable laws.
APPENDIX A. IMPLEMENTATION 49
3. License Grant. Subject to the terms and conditions of this License, Licensor
hereby grants You a worldwide, royalty-free, non-exclusive, perpetual (for the
duration of the applicable copyright) license to exercise the rights in the Work
as stated below:
1. to reproduce the Work, to incorporate the Work into one or more Collective
Works, and to reproduce the Work as incorporated in the Collective Works;
2. to create and reproduce Derivative Works;
3. to distribute copies or phonorecords of, display publicly, perform publicly,
and perform publicly by means of a digital audio transmission the Work
including as incorporated in Collective Works;
4. to distribute copies or phonorecords of, display publicly, perform publicly,
and perform publicly by means of a digital audio transmission Derivative
Works.
5. For the avoidance of doubt, where the work is a musical composition:
1. Performance Royalties Under Blanket Licenses. Licensor waives the
exclusive right to collect, whether individually or via a performance
rights society (e.g. ASCAP, BMI, SESAC), royalties for the public
performance or public digital performance (e.g. webcast) of the Work.
2. Mechanical Rights and Statutory Royalties. Licensor waives the ex-
clusive right to collect, whether individually or via a music rights
society or designated agent (e.g. Harry Fox Agency), royalties for any
phonorecord You create from the Work (“cover version”) and distrib-
ute, subject to the compulsory license created by 17 USC Section 115
of the US Copyright Act (or the equivalent in other jurisdictions).
6. Webcasting Rights and Statutory Royalties. For the avoidance of doubt,
where the Work is a sound recording, Licensor waives the exclusive right
to collect, whether individually or via a performance-rights society (e.g.
SoundExchange), royalties for the public digital performance (e.g. web-
cast) of the Work, subject to the compulsory license created by 17 USC
Section 114 of the US Copyright Act (or the equivalent in other jurisdic-
tions).
The above rights may be exercised in all media and formats whether now known
or hereafter devised. The above rights include the right to make such modifi-
cations as are technically necessary to exercise the rights in other media and
formats. All rights not expressly granted by Licensor are hereby reserved.
4. Restrictions. The license granted in Section 3 above is expressly made subject
to and limited by the following restrictions:
1. You may distribute, publicly display, publicly perform, or publicly digitally
perform the Work only under the terms of this License, and You must in-
clude a copy of, or the Uniform Resource Identifier for, this License with
every copy or phonorecord of the Work You distribute, publicly display,
publicly perform, or publicly digitally perform. You may not offer or im-
pose any terms on the Work that alter or restrict the terms of this License
or the recipients’ exercise of the rights granted hereunder. You may not
sublicense the Work. You must keep intact all notices that refer to this
License and to the disclaimer of warranties. You may not distribute, pub-
licly display, publicly perform, or publicly digitally perform the Work with
any technological measures that control access or use of the Work in a
manner inconsistent with the terms of this License Agreement. The above
applies to the Work as incorporated in a Collective Work, but this does not
APPENDIX A. IMPLEMENTATION 50
require the Collective Work apart from the Work itself to be made subject
to the terms of this License. If You create a Collective Work, upon notice
from any Licensor You must, to the extent practicable, remove from the
Collective Work any reference to such Licensor or the Original Author, as
requested. If You create a Derivative Work, upon notice from any Licensor
You must, to the extent practicable, remove from the Derivative Work any
reference to such Licensor or the Original Author, as requested.
2. You may distribute, publicly display, publicly perform, or publicly digi-
tally perform a Derivative Work only under the terms of this License, a
later version of this License with the same License Elements as this Li-
cense, or a Creative Commons iCommons license that contains the same
License Elements as this License (e.g. Attribution-ShareAlike 2.0 Japan).
You must include a copy of, or the Uniform Resource Identifier for, this
License or other license specified in the previous sentence with every copy
or phonorecord of each Derivative Work You distribute, publicly display,
publicly perform, or publicly digitally perform. You may not offer or im-
pose any terms on the Derivative Works that alter or restrict the terms
of this License or the recipients’ exercise of the rights granted hereunder,
and You must keep intact all notices that refer to this License and to the
disclaimer of warranties. You may not distribute, publicly display, pub-
licly perform, or publicly digitally perform the Derivative Work with any
technological measures that control access or use of the Work in a manner
inconsistent with the terms of this License Agreement. The above applies
to the Derivative Work as incorporated in a Collective Work, but this does
not require the Collective Work apart from the Derivative Work itself to
be made subject to the terms of this License.
3. If you distribute, publicly display, publicly perform, or publicly digitally
perform the Work or any Derivative Works or Collective Works, You must
keep intact all copyright notices for the Work and give the Original Author
credit reasonable to the medium or means You are utilizing by conveying
the name (or pseudonym if applicable) of the Original Author if supplied;
the title of the Work if supplied; to the extent reasonably practicable, the
Uniform Resource Identifier, if any, that Licensor specifies to be associated
with the Work, unless such URI does not refer to the copyright notice or
licensing information for the Work; and in the case of a Derivative Work, a
credit identifying the use of the Work in the Derivative Work (e.g., “French
translation of the Work by Original Author,” or “Screenplay based on
original Work by Original Author”). Such credit may be implemented in
any reasonable manner; provided, however, that in the case of a Derivative
Work or Collective Work, at a minimum such credit will appear where any
other comparable authorship credit appears and in a manner at least as
prominent as such other comparable authorship credit.
5. Representations, Warranties and Disclaimer
UNLESS OTHERWISE AGREED TO BY THE PARTIES IN WRITING, LI-
CENSOR OFFERS THE WORK AS-IS AND MAKES NO REPRESENTA-
TIONS OR WARRANTIES OF ANY KIND CONCERNING THE MATERI-
ALS, EXPRESS, IMPLIED, STATUTORY OR OTHERWISE, INCLUDING,
WITHOUT LIMITATION, WARRANTIES OF TITLE, MERCHANTIBILITY,
FITNESS FOR A PARTICULAR PURPOSE, NONINFRINGEMENT, OR THE
ABSENCE OF LATENT OR OTHER DEFECTS, ACCURACY, OR THE
PRESENCE OF ABSENCE OF ERRORS, WHETHER OR NOT DISCOV-
ERABLE. SOME JURISDICTIONS DO NOT ALLOW THE EXCLUSION
OF IMPLIED WARRANTIES, SO SUCH EXCLUSION MAY NOT APPLY
APPENDIX A. IMPLEMENTATION 51
TO YOU.
6. Limitation on Liability.
EXCEPT TO THE EXTENT REQUIRED BY APPLICABLE LAW, IN NO
EVENT WILL LICENSOR BE LIABLE TO YOU ON ANY LEGAL THE-
ORY FOR ANY SPECIAL, INCIDENTAL, CONSEQUENTIAL, PUNITIVE
OR EXEMPLARY DAMAGES ARISING OUT OF THIS LICENSE OR THE
USE OF THE WORK, EVEN IF LICENSOR HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
7. Termination
1. This License and the rights granted hereunder will terminate automatically
upon any breach by You of the terms of this License. Individuals or entities
who have received Derivative Works or Collective Works from You under
this License, however, will not have their licenses terminated provided
such individuals or entities remain in full compliance with those licenses.
Sections 1, 2, 5, 6, 7, and 8 will survive any termination of this License.
2. Subject to the above terms and conditions, the license granted here is per-
petual (for the duration of the applicable copyright in the Work). Notwith-
standing the above, Licensor reserves the right to release the Work under
different license terms or to stop distributing the Work at any time; pro-
vided, however that any such election will not serve to withdraw this Li-
cense (or any other license that has been, or is required to be, granted
under the terms of this License), and this License will continue in full force
and effect unless terminated as stated above.
8. Miscellaneous
1. Each time You distribute or publicly digitally perform the Work or a Col-
lective Work, the Licensor offers to the recipient a license to the Work on
the same terms and conditions as the license granted to You under this
License.
2. Each time You distribute or publicly digitally perform a Derivative Work,
Licensor offers to the recipient a license to the original Work on the same
terms and conditions as the license granted to You under this License.
3. If any provision of this License is invalid or unenforceable under applicable
law, it shall not affect the validity or enforceability of the remainder of
the terms of this License, and without further action by the parties to
this agreement, such provision shall be reformed to the minimum extent
necessary to make such provision valid and enforceable.
4. No term or provision of this License shall be deemed waived and no breach
consented to unless such waiver or consent shall be in writing and signed
by the party to be charged with such waiver or consent.
5. This License constitutes the entire agreement between the parties with re-
spect to the Work licensed here. There are no understandings, agreements
or representations with respect to the Work not specified here. Licensor
shall not be bound by any additional provisions that may appear in any
communication from You. This License may not be modified without the
mutual written agreement of the Licensor and You.
APPENDIX A. IMPLEMENTATION 52
Creative Commons is not a party to this License, and makes no warranty whatsoever
in connection with the Work. Creative Commons will not be liable to You or any party
on any legal theory for any damages whatsoever, including without limitation any gen-
eral, special, incidental or consequential damages arising in connection to this license.
Notwithstanding the foregoing two (2) sentences, if Creative Commons has expressly
identified itself as the Licensor hereunder, it shall have all rights and obligations of
Licensor.
Except for the limited purpose of indicating to the public that the Work is licensed
under the CCPL, neither party will use the trademark “Creative Commons” or any
related trademark or logo of Creative Commons without the prior written consent of
Creative Commons. Any permitted use will be in compliance with Creative Com-
mons’ then-current trademark usage guidelines, as may be published on its website or
otherwise made available upon request from time to time.
Creative Commons may be contacted at http://creativecommons.org/.