# 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:

1. 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.
2. 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.
3. 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`.
4. 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.

# Use the W,A,S,D keys to change Snake direction comment?
+main 1 variable blocks name? set to new Array2D<of Int>(40, 30, white)expression?2 let rnd name? be new Random()expression?3 call rnd.initialiseFromClock procedureName?(arguments?)4 variable game name? set to newGame(rnd)expression?5 set game variableName? to newApple(game)expression?6 +while game.isOn condition?7 set blocks variableName? to updateGraphics(game, blocks)expression?8 call displayBlocks procedureName?(blocks arguments?)9 call pause procedureName?(150 arguments?)10 set game variableName? to clockTick(game, getKey())expression?11 end while print "Game Over! Score: {score(game)}"expression?12 end main
+function clockTick name?(g as Game, k as String parameter definitions?) returns Game Type?13 let g2 name? be if k is "" then g
else copy g with
key set to k expression?14 let g3 name? be moveSnake(g2)expression?15 let g4 name? be eatAppleIfPoss(g3)expression?16 return if gameOver(g4) then copy g4 with
isOn set to false
else g4 expression?17 end function +function updateGraphics name?(g as Game, b as Array2D<of Int>parameter definitions?) returns Array2D<of Int>Type?18 let b2 name? be b.withPut(g.apple.x, g.apple.y, red)expression?19 let b3 name? be b2.withPut(g.head.x, g.head.y, green)expression?20 let tail name? be g.body[0]expression?21 let tailColour name? be if tail is g.priorTail then green
else white expression?22 return b3.withPut(tail.x, tail.y, tailColour)expression?23 end function +function newApple name?(g as Game parameter definitions?) returns Game Type?24 let x, rnd2 name? be g.rnd.nextInt(0, 39)expression?25 let y, rnd3 name? be rnd2.nextInt(0, 29)expression?26 let apple2 name? be newSquare(x, y)expression?27 let g2 name? be copy g with
apple set to apple2,
rnd set to rnd3 expression?28 return if bodyOverlaps(g2, apple2) then newApple(g2)
else g2 expression?29 end function +function score name?(g as Game parameter definitions?) returns Int Type?30 return g.body.length() - 2 expression?31 end function +function moveSnake name?(g as Game parameter definitions?) returns Game Type?32 let k name? be g.key expression?33 let x, y name? be g.head expression?34 let newX name? be if k is "a" then x - 1
else if k is "d" then x + 1
else x expression?35 let newY name? be if k is "w" then y - 1
else if k is "s" then y + 1
else y expression?36 return copy g with
body set to g.body.withAppend(g.head),
head set to newSquare(newX, newY)expression?37 end function +function eatAppleIfPoss name?(g as Game parameter definitions?) returns Game Type?38 let tail name? be g.body[0]expression?39 let moveTail name? 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 moveTail expression?41 end function +function headOverApple name?(g as Game parameter definitions?) returns Boolean Type?42 return g.head is g.apple expression?43 end function +function gameOver name?(g as Game parameter definitions?) returns Boolean Type?44 return bodyOverlaps(g, g.head) or hasHitEdge(g)expression?45 end function +function hasHitEdge name?(g as Game parameter definitions?) returns Boolean Type?46 let x, y name? be g.head expression?47 return (x is -1) or (y is -1) or (x is 40) or (y is 30)expression?48 end function +function bodyOverlaps name?(g as Game, target as Square parameter definitions?) returns Boolean Type?49 return g.body.filter(lambda s as Square => s is target).length() > 0 expression?50 end function +function newGame name?(rnd as Random parameter definitions?) returns Game Type?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 true expression?52 end function +record Game Name?53 property head name? as Square Type?54 property body name? as ListImmutable<of Square>Type?55 property priorTail name? as Square Type?56 property apple name? as Square Type?57 property isOn name? as Boolean Type?58 property rnd name? as Random Type?59 property key name? as String Type?60 end record +function newSquare name?(x as Int, y as Int parameter definitions?) returns Square Type?61 return new Square() with
x set to x,
y set to y expression?62 end function +record Square Name?63 property x name? as Int Type?64 property y name? as Int Type?65 end record +test clockTick optional description?66 let g1 name? be newGame(new Random())expression?67 let g2 name? be newApple(g1)expression?68 let g3 name? be clockTick(g2, "s")expression?69 assert g3.head computed value? is newSquare(22, 16)expected value? pass 70 assert g3.body.length()computed value? is 2 expected value? pass 71 assert g3.priorTail computed value? is g2.body[0]expected value? pass 72 assert g3.isOn computed value? is true expected value? pass 73 let g4 name? be copy g3 with
apple set to newSquare(22, 17)expression?74 let g5 name? be clockTick(g4, "s")expression?75 assert g5.body.length()computed value? is 3 expected value? pass 76 assert g5.priorTail computed value? is g4.priorTail expected value? pass 77 assert g5.isOn computed value? is true expected value? pass 78 let g6 name? be copy g5 with
head set to newSquare(22, 29)expression?79 let g7 name? be clockTick(g6, "s")expression?80 assert g7.isOn computed value? is false expected value? pass 81 end test +test updateGraphics optional description?82 variable blocks name? set to new Array2D<of Int>(40, 30, white)expression?83 let g1 name? be newGame(new Random())expression?84 let g2 name? be newApple(g1)expression?85 set blocks variableName? to updateGraphics(g2, blocks)expression?86 assert blocks[12, 15]computed value? is red expected value? pass 87 assert blocks[22, 15]computed value? is green expected value? pass 88 assert blocks[21, 15]computed value? is white expected value? pass 89 let g4 name? be clockTick(g2, "d")expression?90 set blocks variableName? to updateGraphics(g4, blocks)expression?91 assert blocks[12, 15]computed value? is red expected value? pass 92 assert blocks[22, 15]computed value? is green expected value? pass 93 assert blocks[23, 15]computed value? is green expected value? pass 94 end test +test newApple optional description?95 let g1 name? be newGame(new Random())expression?96 assert g1.apple computed value? is empty Square expected value? pass 97 let g2 name? be newApple(g1)expression?98 assert g2.apple computed value? is newSquare(12, 15)expected value? pass 99 let g3 name? be newApple(g2)expression?100 assert g3.apple computed value? is newSquare(10, 12)expected value? pass 101 # test that apple is never over snake comment? let g4 name? be newGame(new Random())expression?102 let g5 name? be copy g4 with
body set to {newSquare(12, 15)}expression?103 let g6 name? be newApple(g5)expression?104 assert g6.apple computed value? is newSquare(10, 12)expected value? pass 105 end test +test score optional description?106 let g1 name? be newGame(new Random())expression?107 assert score(g1)computed value? is 0 expected value? pass 108 let g2 name? be copy g1 with
body set to {newSquare(4, 4), newSquare(5, 4)}expression?109 assert score(g2)computed value? is 0 expected value? pass 110 let g3 name? be copy g1 with
body set to {newSquare(3, 4), newSquare(4, 4), newSquare(5, 4)}expression?111 assert score(g3)computed value? is 1 expected value? pass 112 let g4 name? 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 2 expected value? pass 114 end test +test moveSnake optional description?115 let g1 name? be newGame(new Random())expression?116 let g2 name? be copy g1 with
key set to "a"expression?117 let g3 name? be moveSnake(g2)expression?118 assert g3.head computed value? is newSquare(21, 15)expected value? pass 119 let g4 name? be copy g1 with
key set to "d"expression?120 let g5 name? be moveSnake(g4)expression?121 assert g5.head computed value? is newSquare(23, 15)expected value? pass 122 let g6 name? be copy g1 with
key set to "w"expression?123 let g7 name? be moveSnake(g6)expression?124 assert g7.head computed value? is newSquare(22, 14)expected value? pass 125 let g8 name? be copy g1 with
key set to "s"expression?126 let g9 name? be moveSnake(g8)expression?127 assert g9.head computed value? is newSquare(22, 16)expected value? pass 128 end test +test eatAppleIfPoss optional description?129 let g1 name? be newGame(new Random())expression?130 assert g1.body.length()computed value? is 2 expected value? pass 131 # negative case comment? let g2 name? be copy g1 with
apple set to newSquare(23, 15)expression?132 let g3 name? be eatAppleIfPoss(g2)expression?133 assert g3.body.length()computed value? is 1 expected value? pass 134 assert g3.apple computed value? is g2.apple expected value? pass 135 assert g3.priorTail computed value? is g2.body[0]expected value? pass 136 # positive case comment? let g4 name? be copy g2 with
head set to newSquare(23, 15)expression?137 let g5 name? be eatAppleIfPoss(g4)expression?138 assert g5.body.length()computed value? is 2 expected value? pass 139 assert g5.apple computed value? is newSquare(12, 15)expected value? pass 140 assert g5.priorTail computed value? is g1.priorTail expected value? pass 141 end test +test overApple optional description?142 let g1 name? be newGame(new Random())expression?143 let g2 name? be copy g1 with
apple set to newSquare(23, 15)expression?144 assert headOverApple(g2)computed value? is false expected value? pass 145 let g3 name? be copy g2 with
head set to newSquare(23, 15)expression?146 assert headOverApple(g3)computed value? is true expected value? pass 147 end test +test gameOver optional description?148 let g1 name? be newGame(new Random())expression?149 assert gameOver(g1)computed value? is false expected value? pass 150 let g2 name? be copy g1 with
head set to newSquare(0, 0)expression?151 assert gameOver(g2)computed value? is false expected value? pass 152 let g3 name? be copy g1 with
head set to newSquare(40, 15)expression?153 assert gameOver(g3)computed value? is true expected value? pass 154 let g4 name? be copy g1 with
head set to newSquare(21, 15)expression?155 assert gameOver(g4)computed value? is true expected value? pass 156 end test +test headIsAtEdge optional description?157 let g1 name? be newGame(new Random())expression?158 assert hasHitEdge(g1)computed value? is false expected value? pass 159 let g2 name? be copy g1 with
head set to newSquare(40, 15)expression?160 assert hasHitEdge(g2)computed value? is true expected value? pass 161 let g3 name? be copy g1 with
head set to newSquare(-1, 15)expression?162 assert hasHitEdge(g3)computed value? is true expected value? pass 163 let g4 name? be copy g1 with
head set to newSquare(20, 30)expression?164 assert hasHitEdge(g4)computed value? is true expected value? pass 165 let g5 name? be copy g1 with
head set to newSquare(20, -1)expression?166 assert hasHitEdge(g5)computed value? is true expected value? pass 167 end test +test bodyOverlaps optional description?168 let g1 name? be newGame(new Random())expression?169 let g2 name? 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 true expected value? pass 171 assert bodyOverlaps(g2, newSquare(4, 4))computed value? is true expected value? pass 172 assert bodyOverlaps(g2, newSquare(5, 4))computed value? is true expected value? pass 173 assert bodyOverlaps(g2, newSquare(2, 4))computed value? is false expected value? pass 174 assert bodyOverlaps(g2, newSquare(6, 2))computed value? is false expected value? pass 175 end test +test newSquare optional description?176 let sq name? be newSquare(3, 4)expression?177 assert sq.x computed value? is 3 expected value? pass 178 assert sq.y computed value? is 4 expected value? pass 179 end test +test newGame optional description?180 let rnd name? be new Random()expression?181 let game name? be newGame(rnd)expression?182 assert game.rnd computed value? is rnd expected value? pass 183 assert game.head computed value? is newSquare(22, 15)expected value? pass 184 let body name? be game.body expression?185 assert body.length()computed value? is 2 expected value? pass 186 assert body[0]computed value? is newSquare(20, 15)expected value? pass 187 assert body[1]computed value? is newSquare(21, 15)expected value? pass 188 assert game.priorTail computed value? is newSquare(0, 0)expected value? pass 189 assert game.key computed value? is "d"expected value? pass 190 assert game.isOn computed value? is true expected value? pass 191 end test

# Example 2: Wordle solver