Principles of functional programming using Elan
Elan is a 'multi-paradigm' programming language. It supports
- Procedural programming
- Object-oriented programming
- Functional programming
and it is a very good way to learn all three of them. Elan lays a very strong foundation
that will make it easier for you to transition later on to more languages that are specialised
towards one of the three programming languages such as Java, C#, or TypeScript for object-oriented programming;
or Haskell, OCaml, or F#, for functional programming. Other popular multi-paradigm languages such as Python,
VB, C#, and Java do not lay as good a foundation.
Functional programming means constructing programs from pure function. A pure function:
- returns a value that is derived solely and deterministically from the values passed to it as parameters
- may call other pure functions but may not depend upon any information other than was passed to it as parameters
- may not generate any 'side effects'. A side effect is anything information, or change to the state of the system,
that could be observed by code outside the function other than the value returned by the function.
The reason for these constraints is that pure functions can be combined to form a program where the results are entirely predictable
and guaranteed. This, surprisingly perhaps, is not the case with impure functions, because external dependencies
and side-effects can result in unexpected interference between the combined functions.
However, as Simon Peyton Jones, one of the leading exponents of functional programming and lead developer of Haskell has said,
'The problem is that the whole point of systems is to produce side-effects', meaning that if a program doesn't at minimum produce
any output - whether displayed on a screen, stored in a file, transmitted over a network,
or driving an actuator in a mechanical device A-level. Then it isn't doing anything useful!
Pure functional programming languages such as Haskell enforce that all functions are pure - even functions that are responsible
for input/output which sounds like a contradiction. But the way that that conundrum is resolved is one of the reasons why learning
to write whole applications in a pure functional language is difficult.
If you want to learn functional programming in a multi-paradigm language such as Python, VB, or C#, say, then you have
to split your program into the pure parts that cover the core data transformations, and the 'impure' parts that handle.
The problem with that approach, is that those languages cannot enforce that separation, and it is all to easy to
find side-effects and dependencies creeping into your supposedly-pure core functionality.
Elan is almost unique amongst multi-paradigm languages in that it enforces that all functions are pure - thus offering
the full benefit of guaranteed safe combination of functions. Input/output must handled in the main routine or procedures,
and there is no danger of these getting mixed up because you can call functions from main or a procedure, but never vice versa.
Additionally, because Elan offers a powerful and easy-to-use mechanism for automated testing of functions, Elan gives
you a strong incentive to implement as much of your application as possible using functions. Indeed it would be good practice when programming in any paradigm to
implement as much of the logic as possible in pure functions, and to keep the main and any procedures as 'thin' as possible.
In other words, as well as keeping input/output out of function, you should aim to as much of the application logic as possible out of the main and procedures.
These design principles apply, whichever programming paradigm you are adopting.
So what is the difference, then, between adopting the functional programming paradigm in Elan, as distinct from adopting the procedural,
or object-oriented paradigms? We suggest the following principles should be adopted when adopting the functional programming paradigm:
- As much of the application logic as possible should be implemented in functions - which, in Elan, are necessarily 'pure' functions.
The main routine (which is needed for any application that may be executed) and any supporting procedures, should be
restricted to the direct implementation of input/output or other behaviour dependent upon the system - and these should
together constitute as small a proportion of the total number of instructions as possible.
- All types passed to functions, or used within functions should be immutable. This means:
- Any of the standard value types: Int, Float, Boolean, String
- These specific library data structures: ListImmutable, DictionaryImmutable, Set, Stack, Queue
- User defined types: Enums, Tuples, Records
All other types, whether defined within the Elan library or as user-defined classes, are mutable and should be avoided.
- The body of every function should consist only of the return instruction, optionally
preceded by one or more let instructions. This combination means that you aren't ever mutating anything
even inside the functions. It also means that all 'iteration' within functions is achieved by using higher-order functions - such
as map, filter, reduce
and/or by defining recursive functions. Similarly, 'selection' is achieved by using 'if expressions' rather than using 'if statements`.
- Random numbers pose a special challenge to functional programming. There are two options:
- Generate random numbers using the standard randomInt, randomInt system methods but only within
the main routine or procedures - passing the generated number(s) into the functions that need them as
Int or Float values. These methods cannot be used
within functions because calling randomInt changes the state of the random number generator
held, invisibly, within the system - in other words the methods have side effects.
- Use the library type Random and its methods. These may be safely passed into a function,
because the next, nextInt methods (which are pure functions)
return the random value together with a new instance of Random - which must then be used to
generate the next random number, and which itself should be returned from the function that uses it.
Example 1: Snake - functional
The code below implements the game of Snake adopting the all of the principles listed above: Notice the following:
- Excluding the test code, which is all at the end, the entire program
code consists of 65 instructions.
- The main routine is just 12 instructions.
- All the rest of the logic is held in standalone (global) functions. It did not prove necessary to use any procedures, though
that would have been allowed, indeed desirable if the alternative would have meant a significantly larger main.
- All functions contain only let and return instructions.
- If expressions are used twice in the moveSnake function.
- The newApple uses recursion to achieve iteration - the requirement being
to place the apple in a new random position until a location is found that does not overlap the body.
- A Hof (filter) is used to achieve iteration in the bodyOverlaps function.
- The code defines two types of record: Game, Square
each with properties. (Function methods may be defined on records, but were not used here.)
- The functional approach to random numbers (using the Random type is used.
- There is a test for each of the functions, and each of those tests
has multiple assert instructions i.e. tests multiple cases. This means that overall
82% of the instructions are covered by automated tests - only the main routine
is not covered, and must be tested manually.
#
+main1
variable blocksname? set to new Array2D<of Int>(40, 30, white)expression?2
let rndname? be new Random()expression?3
call rnd.initialiseFromClockprocedureName?(arguments?)4
variable gamename? set to newGame(rnd)expression?5
set gamevariableName? to newApple(game)expression?6
+while game.isOncondition?7
set blocksvariableName? to updateGraphics(game, blocks)expression?8
call displayBlocksprocedureName?(blocksarguments?)9
call pauseprocedureName?(150arguments?)10
set gamevariableName? to clockTick(game, getKey())expression?11
end while
print "Game Over! Score: {score(game)}"expression?12
end main
+function clockTickname?(g as Game, k as Stringparameter definitions?) returns GameType?13
let g2name? be if k is "" then g
else copy g with
key set to kexpression?14
let g3name? be moveSnake(g2)expression?15
let g4name? be eatAppleIfPoss(g3)expression?16
return if gameOver(g4) then copy g4 with
isOn set to false
else g4expression?17
end function
+function updateGraphicsname?(g as Game, b as Array2D<of Int>parameter definitions?) returns Array2D<of Int>Type?18
let b2name? be b.withPut(g.apple.x, g.apple.y, red)expression?19
let b3name? be b2.withPut(g.head.x, g.head.y, green)expression?20
let tailname? be g.body[0]expression?21
let tailColourname? be if tail is g.priorTail then green
else whiteexpression?22
return b3.withPut(tail.x, tail.y, tailColour)expression?23
end function
+function newApplename?(g as Gameparameter definitions?) returns GameType?24
let x, rnd2name? be g.rnd.nextInt(0, 39)expression?25
let y, rnd3name? be rnd2.nextInt(0, 29)expression?26
let apple2name? be newSquare(x, y)expression?27
let g2name? be copy g with
apple set to apple2,
rnd set to rnd3expression?28
return if bodyOverlaps(g2, apple2) then newApple(g2)
else g2expression?29
end function
+function scorename?(g as Gameparameter definitions?) returns IntType?30
return g.body.length() - 2expression?31
end function
+function moveSnakename?(g as Gameparameter definitions?) returns GameType?32
let kname? be g.keyexpression?33
let x, yname? be g.headexpression?34
let newXname? be if k is "a" then x - 1
else if k is "d" then x + 1
else xexpression?35
let newYname? be if k is "w" then y - 1
else if k is "s" then y + 1
else yexpression?36
return copy g with
body set to g.body.withAppend(g.head),
head set to newSquare(newX, newY)expression?37
end function
+function eatAppleIfPossname?(g as Gameparameter definitions?) returns GameType?38
let tailname? be g.body[0]expression?39
let moveTailname? be g.body[1..g.body.length()]expression?40
return if headOverApple(g) then newApple(g)
else copy g with
priorTail set to tail,
body set to moveTailexpression?41
end function
+function headOverApplename?(g as Gameparameter definitions?) returns BooleanType?42
return g.head is g.appleexpression?43
end function
+function gameOvername?(g as Gameparameter definitions?) returns BooleanType?44
return bodyOverlaps(g, g.head) or hasHitEdge(g)expression?45
end function
+function hasHitEdgename?(g as Gameparameter definitions?) returns BooleanType?46
let x, yname? be g.headexpression?47
return (x is -1) or (y is -1) or (x is 40) or (y is 30)expression?48
end function
+function bodyOverlapsname?(g as Game, target as Squareparameter definitions?) returns BooleanType?49
return g.body.filter(lambda s as Square => s is target).length() > 0expression?50
end function
+function newGamename?(rnd as Randomparameter definitions?) returns GameType?51
return new Game() with
rnd set to rnd,
head set to newSquare(22, 15),
body set to {newSquare(20, 15), newSquare(21, 15)},
priorTail set to empty Square,
key set to "d",
isOn set to trueexpression?52
end function
+record GameName?53
property headname? as SquareType?54
property bodyname? as ListImmutable<of Square>Type?55
property priorTailname? as SquareType?56
property applename? as SquareType?57
property isOnname? as BooleanType?58
property rndname? as RandomType?59
property keyname? as StringType?60
end record
+function newSquarename?(x as Int, y as Intparameter definitions?) returns SquareType?61
return new Square() with
x set to x,
y set to yexpression?62
end function
+record SquareName?63
property xname? as IntType?64
property yname? as IntType?65
end record
+test 66
let g1name? be newGame(new Random())expression?67
let g2name? be newApple(g1)expression?68
let g3name? be clockTick(g2, "s")expression?69
assert g3.headcomputed value? is newSquare(22, 16)expected value? pass70
assert g3.body.length()computed value? is 2expected value? pass71
assert g3.priorTailcomputed value? is g2.body[0]expected value? pass72
assert g3.isOncomputed value? is trueexpected value? pass73
let g4name? be copy g3 with
apple set to newSquare(22, 17)expression?74
let g5name? be clockTick(g4, "s")expression?75
assert g5.body.length()computed value? is 3expected value? pass76
assert g5.priorTailcomputed value? is g4.priorTailexpected value? pass77
assert g5.isOncomputed value? is trueexpected value? pass78
let g6name? be copy g5 with
head set to newSquare(22, 29)expression?79
let g7name? be clockTick(g6, "s")expression?80
assert g7.isOncomputed value? is falseexpected value? pass81
end test
+test 82
variable blocksname? set to new Array2D<of Int>(40, 30, white)expression?83
let g1name? be newGame(new Random())expression?84
let g2name? be newApple(g1)expression?85
set blocksvariableName? to updateGraphics(g2, blocks)expression?86
assert blocks[12, 15]computed value? is redexpected value? pass87
assert blocks[22, 15]computed value? is greenexpected value? pass88
assert blocks[21, 15]computed value? is whiteexpected value? pass89
let g4name? be clockTick(g2, "d")expression?90
set blocksvariableName? to updateGraphics(g4, blocks)expression?91
assert blocks[12, 15]computed value? is redexpected value? pass92
assert blocks[22, 15]computed value? is greenexpected value? pass93
assert blocks[23, 15]computed value? is greenexpected value? pass94
end test
+test 95
let g1name? be newGame(new Random())expression?96
assert g1.applecomputed value? is empty Squareexpected value? pass97
let g2name? be newApple(g1)expression?98
assert g2.applecomputed value? is newSquare(12, 15)expected value? pass99
let g3name? be newApple(g2)expression?100
assert g3.applecomputed value? is newSquare(10, 12)expected value? pass101
#
let g4name? be newGame(new Random())expression?102
let g5name? be copy g4 with
body set to {newSquare(12, 15)}expression?103
let g6name? be newApple(g5)expression?104
assert g6.applecomputed value? is newSquare(10, 12)expected value? pass105
end test
+test 106
let g1name? be newGame(new Random())expression?107
assert score(g1)computed value? is 0expected value? pass108
let g2name? be copy g1 with
body set to {newSquare(4, 4), newSquare(5, 4)}expression?109
assert score(g2)computed value? is 0expected value? pass110
let g3name? be copy g1 with
body set to {newSquare(3, 4), newSquare(4, 4), newSquare(5, 4)}expression?111
assert score(g3)computed value? is 1expected value? pass112
let g4name? be copy g1 with
body set to {newSquare(3, 4), newSquare(4, 4), newSquare(5, 4), newSquare(5, 5)}expression?113
assert score(g4)computed value? is 2expected value? pass114
end test
+test 115
let g1name? be newGame(new Random())expression?116
let g2name? be copy g1 with
key set to "a"expression?117
let g3name? be moveSnake(g2)expression?118
assert g3.headcomputed value? is newSquare(21, 15)expected value? pass119
let g4name? be copy g1 with
key set to "d"expression?120
let g5name? be moveSnake(g4)expression?121
assert g5.headcomputed value? is newSquare(23, 15)expected value? pass122
let g6name? be copy g1 with
key set to "w"expression?123
let g7name? be moveSnake(g6)expression?124
assert g7.headcomputed value? is newSquare(22, 14)expected value? pass125
let g8name? be copy g1 with
key set to "s"expression?126
let g9name? be moveSnake(g8)expression?127
assert g9.headcomputed value? is newSquare(22, 16)expected value? pass128
end test
+test 129
let g1name? be newGame(new Random())expression?130
assert g1.body.length()computed value? is 2expected value? pass131
#
let g2name? be copy g1 with
apple set to newSquare(23, 15)expression?132
let g3name? be eatAppleIfPoss(g2)expression?133
assert g3.body.length()computed value? is 1expected value? pass134
assert g3.applecomputed value? is g2.appleexpected value? pass135
assert g3.priorTailcomputed value? is g2.body[0]expected value? pass136
#
let g4name? be copy g2 with
head set to newSquare(23, 15)expression?137
let g5name? be eatAppleIfPoss(g4)expression?138
assert g5.body.length()computed value? is 2expected value? pass139
assert g5.applecomputed value? is newSquare(12, 15)expected value? pass140
assert g5.priorTailcomputed value? is g1.priorTailexpected value? pass141
end test
+test 142
let g1name? be newGame(new Random())expression?143
let g2name? be copy g1 with
apple set to newSquare(23, 15)expression?144
assert headOverApple(g2)computed value? is falseexpected value? pass145
let g3name? be copy g2 with
head set to newSquare(23, 15)expression?146
assert headOverApple(g3)computed value? is trueexpected value? pass147
end test
+test 148
let g1name? be newGame(new Random())expression?149
assert gameOver(g1)computed value? is falseexpected value? pass150
let g2name? be copy g1 with
head set to newSquare(0, 0)expression?151
assert gameOver(g2)computed value? is falseexpected value? pass152
let g3name? be copy g1 with
head set to newSquare(40, 15)expression?153
assert gameOver(g3)computed value? is trueexpected value? pass154
let g4name? be copy g1 with
head set to newSquare(21, 15)expression?155
assert gameOver(g4)computed value? is trueexpected value? pass156
end test
+test 157
let g1name? be newGame(new Random())expression?158
assert hasHitEdge(g1)computed value? is falseexpected value? pass159
let g2name? be copy g1 with
head set to newSquare(40, 15)expression?160
assert hasHitEdge(g2)computed value? is trueexpected value? pass161
let g3name? be copy g1 with
head set to newSquare(-1, 15)expression?162
assert hasHitEdge(g3)computed value? is trueexpected value? pass163
let g4name? be copy g1 with
head set to newSquare(20, 30)expression?164
assert hasHitEdge(g4)computed value? is trueexpected value? pass165
let g5name? be copy g1 with
head set to newSquare(20, -1)expression?166
assert hasHitEdge(g5)computed value? is trueexpected value? pass167
end test
+test 168
let g1name? be newGame(new Random())expression?169
let g2name? be copy g1 with
body set to {newSquare(3, 4), newSquare(4, 4), newSquare(5, 4)}expression?170
assert bodyOverlaps(g2, newSquare(3, 4))computed value? is trueexpected value? pass171
assert bodyOverlaps(g2, newSquare(4, 4))computed value? is trueexpected value? pass172
assert bodyOverlaps(g2, newSquare(5, 4))computed value? is trueexpected value? pass173
assert bodyOverlaps(g2, newSquare(2, 4))computed value? is falseexpected value? pass174
assert bodyOverlaps(g2, newSquare(6, 2))computed value? is falseexpected value? pass175
end test
+test 176
let sqname? be newSquare(3, 4)expression?177
assert sq.xcomputed value? is 3expected value? pass178
assert sq.ycomputed value? is 4expected value? pass179
end test
+test 180
let rndname? be new Random()expression?181
let gamename? be newGame(rnd)expression?182
assert game.rndcomputed value? is rndexpected value? pass183
assert game.headcomputed value? is newSquare(22, 15)expected value? pass184
let bodyname? be game.bodyexpression?185
assert body.length()computed value? is 2expected value? pass186
assert body[0]computed value? is newSquare(20, 15)expected value? pass187
assert body[1]computed value? is newSquare(21, 15)expected value? pass188
assert game.priorTailcomputed value? is newSquare(0, 0)expected value? pass189
assert game.keycomputed value? is "d"expected value? pass190
assert game.isOncomputed value? is trueexpected value? pass191
end test
Example 2: Wordle solver