Getting started

To undertake functional programming (FP) in Elan, you should first be reasonably familiar with procedural programming (PP) with Elan, and ideally, with object-oriented programming (OOP) with Elan. Then, switch to the functional profile from the menu at the top of the IDE. This changes two things:

1. The list of demo programs will now show only programs that use FP. A very good place to start is to look at the Snake - functional demo, which is functionally identical to the (procedural) original, but it written using FP design and coding patterns.
2. It will change some of the options available on the new code menus in the editor:
   • Within a function, the only type of instruction that you may add (above the fixed returnreturnreturnreturnreturn instruction) is a new instruction named let (plus, of course, comments).
   • Within a concrete or abstract class, you may add function methods, but not procedure methods.
   • Within a concrete or abstract class, there is a new kind of method named a with method. Actually, this is just a template for a specific form of function method which is particularly useful in FP.
   The rationale for disallowing some of the instructions you are used to in PP or OOP, and how to use the new instructions, will become clear as you read through this document.

In the following sections we will describe 10 principles that define the essence of FP, illustrated with example code - where possible from the demo programs.

Important. Every textbook on FP differs slightly in the definition of core principles, and every language that supports FP differs in the rules that it enforces. The following 10 principles are based on widely recognised best practices in FP. When coding with Elan, in whichever of the supported languages - Python, VB, C#, or Java (or the Elan Reference Language) - these principles are, wherever possible, enforced by the Elan tooling. The resulting code is always valid syntax for the chosen language - but may depend upon common library methods defined in the Elan library. Also, if you go on to write code in any of those languages outside Elan, you will find that the same principles are not necessarily enforced. Though that might appear to offer you more freedom, sticking voluntarily to the principles that you learned in Elan will result in better code and fewer problems.

Principle 1: Functions must be pure

A pure function observes the following rules:

• The value returned by the function (which may be a data structure) must be derived solely and deterministically from the data provided in parameters. This means it may not depend on data obtained from user input, from a file, or from over the network, though such data may be obtained outside the function and passed into it in parameters.
• Similarly, within the function, you cannot make direct use of the system clock or system-generated random numbers. (There is a technique to generate random numbers  within a function, but this is best left until you have a thorough understanding of the basics of FP.)
• The function may not generate any side effects, that is changes to the state of the system that may be observed outside the function.
• When the function has completed its execution the only legitimate observable effect is its returned value.

Dedicated Functional Programming languages — such as Haskell — enforce these rules automatically. Common 'multi-paradigm' languages — including Python, VB, C#, and Java — do not enforce them. However, if any of those languages are used within Elan, then the Elan editor enforces the rules automatically.

This means that every function you see within Elan, and every function you have ever written within Elan (in Python, VB, C#, or Java), is a pure function. That is the reason why, even when you are using the procedural or object-oriented profiles and you are within a function, you cannot print or call a procedure, nor can you make use of system methods such as input, random, or clock. This experience gives you a huge advantage in transitioning to FP.

Principle 2: As much of the code as possible should be in functions

When using FP in Python, VB, C#, or Java, every program still needs a main routine, which is necessarily procedural in nature, because it cannot work without dependencies on the system, and it generates side effects such as output to a display.

To avoid your main routine becoming difficult to read, and to avoid duplicated code, you may still define procedures (which also, inherently, use procedural programming to manage input/output and other system operations). But this second principle of FP implies that the main together with any necessary procedures should be kept as small as possible:

Any code within the main routine or procedures that performs calculation, evaluates logic, or transforms data in any way, should be delegated to functions.

This may seem logical when a program is obviously heavily dependent upon calculation, logic, or data transformation — as, for example, the Best Fit and Wordle solver demo programs. But what about an interactive game, where most of the logic is concerned with managing the user input and the display? Consider the two demo programs: Snake - procedural and Snake - procedural. The two programs behave identically when run. We recommend that you take the time to explore the these two programs in detail,but here's a summary of the key differences:

Principle 3: Every function can and should be unit tested

The idea of writing automated tests isn't restricted to Functional Programming. The tests offered by Elan are known as 'unit tests', and are designed to test functions.

Such tests are extremely easy to write, and run automatically when the program is loaded from a file, and then run again after every edit that results in code that compiles.

Unit tests give you huge confidence that your code does what it is supposed to do, and that subsequent changes, whether as a result of debugging or of implementing new requirements, do not break existing functionality. Without unit tests, bugs might go unnoticed and surface only later and less obviously.

On some platforms it is possible to write automated tests that also cover procedures (including the main routine). These are sometimes referred to as 'end to end tests', or 'UI tests' because they can simulate a user interacting with the program. But such tests are much harder to write than unit tests, and notoriously 'brittle' — meaning that a tiny change to code can break many existing tests and take hours to fix. Changes external to your program, such as a routine upgrade to the browser or operating system, can easily render such tests invalid. Elan does not currently support those kind of tests.

Note, however, that outside Elan, Python, VB, C#, and Java, have unit testing frameworks that can theoretically allow unit tests to run any method. This can be dangerous because running the tests might, without your awareness, be updating a file or database, or sending Internet messages. Unit tests are safe only when applied to safe (i.e. pure) functions.

It follows that the higher the percentage of a program's total instructions that exist within functions, the higher the percentage of your code that can be safely unit tested. The table below shows the percentage of instructions covered by tests for two of the demo programs that offer both procedural and functional implementations. You can verify this information by examining the demo code.

Note on demo program Best Fit

• The Best Fit demo defines a function and a Class for use in other programs. It has no main instruction, so comparison with the the unit testing in other programs would be misleading. The function and the operation of the Class are both 100% tested.

Principle 4: A function consists of a 'return', with optional let instructions

In the FP demos you will see that a significant number of functions simply returnreturnreturnreturnreturn an expression to be evaluated, for example:

Other functions precede the returnreturnreturnreturnreturn by one or more let statements, for example

A let statement works like a variable definition except that the named value created may not be reassigned. But it differs from a constant in that:

• it is defined within a function (or a test), whereas a constant is always defined at global (file) level.
• it may be defined by an expression rather than just by a literal value
• it may refer to a List or other data structure

In the four languages supported by Elan, let instruction are really just disguised variable definitions, executed sequentially. But in a pure FP language such as Haskell, OCAML, or F#, let instructions are executed lazily, meaning that within a function, execution starts with the returned expression, and only evaluates the sub-expressions defined in let instructions when - indeed if they are needed. So getting used to let instructions leaves you better prepared to move onto a pure FP language at a future point.

A let statement defines a 'sub-expression' that will be used in another expression, for one (or more) of these reasons:

• To make a long expression easier to read
• To eliminate duplication — where the same sub-expression otherwise appears in full in more than one place.
• Within a test, because the 'actual' field does not support 'chained' expressions (expressions containing more than one 'dot')

When running in the functional profile, let statement is the only type of instruction that you may add within a function, and the only type in addition to an assert that may be added into a test. (You can still, of course, add comments.)

Principle 5: Selection is implemented using 'if expressions'

When running in the Functional profile, you cannot add an if instruction into a function. So how do you implement 'selection' and 'iteration'? Selection is handled by means of a 'conditional expression', whereas iteration will be addressed under Principle 6 .

All of the languages supported by Elan have their own custom syntax for conditional expressions. For simplicity, and understandability, Elan offers an if function that is used identically in all the languages. (Incidentally, the if function works the same way as it does in an Excel spreadsheet). Here are some examples of conditional expressions from the demo programs:

The if function requires three arguments to be provided, in the following order:

1. The condition, which may compare two values, or it may call another function that returns a Boolean value
2. The value to be returned by the if function when the condition evaluates to true
3. The value to be returned by the if function when the condition evaluates to false

Thus the if function performs a role somewhat similar to an if instruction, but differs from it in these important respects:

• The if function is not an instruction: it forms part, or all, of an expression and may be used within any expression that forms part of an instruction.
• It returns a value, which must be used.
• It may make use of other expressions to define the arguments, but may not contain other instructions.

Although if functions can be nested, nesting to more than one level can become very hard to read. When required, it is often better to delegate to a new function to perform part of the logic.

Principle 6: Iteration may be achieved using recursion

There are two ways to implement iteration within a function:

Either by using 'recursion', i.e. a recursive function (described here), or by the approach described in Principle 8 .

A recursive function is one that at some point evaluates itself, and is best understood by example. In the Recursive Functions demo, the factorial function is a good place to start:

It shows these important aspects of designing a recursive function:

• When the function is called within the function body it is typically with a smaller version of the original problem: in this case factorial(n)factorial(n)factorial(n)factorial(n)factorial(n) calculates factorial(n - 1)factorial(n - 1)factorial(n - 1)factorial(n - 1)factorial(n - 1) and multiplies it by nnnnn.
• The recursion must 'bottom out' eventually, and this must be explicitly checked for. In this case it bottoms out when nnnnn is less than 22222, because 0! and 1! are both 1. The most common error when writing a recursive function is forgetting to define and check for the bottoming-out condition. If you fail to do this, for example by writing return n*factorial(n - 1) Code does not parse as Elan.return n*factorial(n - 1) Code does not parse as Elan.return n*factorial(n - 1) Code does not parse as Elan.return n*factorial(n - 1) Code does not parse as Elan.return n*factorial(n - 1) Code does not parse as Elan. — or you get the condition wrong — the iteration will continue indefinitely until you eventually get a 'Stack overflow error', which crashes the program. Try it so that you learn to recognise and diagnose the potential problem.

Principle 7: Lists and other data structures are never mutated

In procedural programming a List may be mutated either by reassigning an indexed value, for example:

At first sight this may seem awkward, strange and certainly inefficient. But though you might never have thought about it in these terms, this is what you have always done when manipulating a StringstrstringStringString. You can never actually mutate a string, such as converting it to upper case or trimming off the leading spaces. You have to write, for example:

When you want to apply operations to all items in a List you need to use iteration, which means using either recursion  or Higher-order Functions  and within that technique make use of the various with.. methods. The sum function in the Recursive Functions demo calculates the sum of all items in any List of floating point numbers (the tests included in the demo show example results):

Note the use of these two dot function calls on the List lilililili(see Dot syntax  in Language Reference):

• head returns only the first item in the List.
• tail returns all the items of the List except the first.

In FP, algorithms to process lists are often written in terms of the 'head' and 'tail' of the list. You could just write e.g. li[0]li[0]li[0]li[0]li[0] and li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length()) instead, with the same result. But using the head and tail methods makes your code easier to read and may make your intention clearer.

The next example combines the previous two ideas:

• updating a List by using a with.. method to create a copy of the original List with specified differences.
• using recursion to iterate over the items in the List.

A more advanced example is the Merge Sort demo, where:

• the principal function (sort) defines the algorithm in just one line, delegating to other, simpler functions. This is a very good example of 'functional decomposition', that is defining a function in terms of other functions each of which does part of the task.
• as well as testing the principal function, there are unit tests for each of the component functions. This builds confidence and makes debugging simpler. (Recursive functions can be hard to debug otherwise.)
• At first glance, none of the functions appears to be recursive because none of them calls itself directly. However, as you study the code you will see that sort calls sortedFrontHalf and sortedBackHalf both of which call back into sort again — crucially with approximately half of the original List. The same pattern exists between merge and mergeNonEmpty.

Principle 8: A function may be passed into, or returned by, another function

The alternative to writing your own recursive function is to use Higher-order Functions (see HoFs  in Library Reference). A HoF is a function that takes in another function as a parameter (the more common case), or one that returns a function as its result. Under the covers, HoFs are written using recursion, but you don't see this.

There are many possible HoFs, but three of them — filter, map and reduce — are so widely used to process lists in FP, and in many different ways, that they are sometimes referred to as the 'Holy Trinity of Functional Programming'. They can be used individually or in combination. The purpose and operation of each is explained below.

All of the languages supported by Elan have their own versions of filter, map and reduce that are similar in intent but have differing syntax, and sometimes different names (e.g. 'fold' in place of 'reduce').The Elan library has its own version of these functions which work the same way in each language.

Start by loading and running the demo program Map, Filter, Reduce, and look at the test:

Each of the three HoFs is applied to a List by a 'dot method call'. In this example each is applied to the same List (of floating point numbers), though the subject List may be of any Type. Because they are all dot methods, they can easily be chained in dot sequences, as shown.

Each HoF is passed the name of a function that is defined elsewhere in the program. The function name is given as an argument, without brackets or arguments, e.g. lessThan5. For filter and map, this is the only argument; for reduce there is another argument. Taking each HoF in turn:

filter

• returns a List that is made up of selected items from the original List. The function passed into filter is applied to each of the List's items in turn, and determines whether or not each should 'pass' through the filter into the resulting List. In the first example the function passes only those values from the original List that are less than 5.
• the definition of the function lessThan5 (lower down in the code) includes a parameter of Type FloatfloatdoubleDoubledouble (the same Type as of the item in the List) but returns a BooleanboolboolBooleanbool specifying whether or not a specific item should pass the filter. Making sure that Types match up as expected can be the trickiest part of learning to use HoFs.

map

• returns a List that will have the same number of items as in the original List. They might be of the same Type as the in the original List (though typically different values) or, depending on the return Type of the function passed in, the items in the resulting List might be of a Type different from those in the original List. But each item in the resulting List corresponds ('maps') to an item of the original List at the same position
• as with filter, the function passed into map must have a single parameter of the same Type as the items in the List, though its return value may be of any Type.

reduce

• returns a single value, that is derived by combining all of the item values in the original List according to the function passed in. That derived value can be of the same Type as the items of the List (for example when used to combine a List of numbers by addition or multiplication), but can be of a different Type including a data structure.
• Unlike filter and map, reduce requires two arguments:
  1. the initial value (sometimes called the 'seed') that will be progressively refined and eventually returned. This initial value must therefore have the Type of the desired final value.
  2. the function passed into reduce must define two parameters:
     1. the accumulating value, therefore of the same Type as the initial 'seed' value.
     2. the item to which the function is applied, therefore of the same Type as the items in the List.
• The return Type of the function must have the same Type as the 'seed' value.
• Each item of the List is passed in turn into the function (as second argument), the first argument being the latest value that has developed from the seed.

filter and map methods may be chained, and in any order, provided that the item Type of each resulting List is of the Type expected by the next one.

Because reduce transforms a List into a single value, it is typically used in isolation or as the last of a chain. It can, of course, be followed in the chain by a simpler function (such as round).

Lambdas

In the examples above the function being passed into the HoF (using its name) is defined as a 'standalone' (global) function elsewhere in the program. This pattern has two advantages:>/p>

• The function may be used elsewhere in the program, either to pass into a another HoF, or in the same way as any other function.
• The function can be tested in isolation.

However, there are many circumstances where the function you need to pass into a HoF, is unlikely to be used in any different context, and where the function is so simple that it hardly warrants its own test — especially if the whole expression that uses the HoF is being tested.

A lambda is a function that is defined 'inline' as an argument in a function call. For example, the expression from the example above:

thereby eliminating the need to define the lessThan5 function for one use only.

There is a whole branch of mathematics devoted to 'lambda calculus', which in turn provided the theoretical underpinning for the concept of function programming (FP). And lambdas have capabilities that are both more subtle and more sophisticated than can be described here, including the idea of 'closure' (which you can look up if you are ready to go much deeper — and which is supported in Elan). However, you should note that, because of the need for compatibility across all the supported languages, Elan has a restricted implementation of HoFs and of 'function passing' in general, but it is sufficient to grasp the key principles of Functional Programming. To go further you would need to switch to a pure FP language such as Haskell. Currently Elan does not permit (in any of the supported languages):

• The definition of a lambda except inline as the argument to a HoF. You cannot, for example, assign a lambda (or a function) to a variable.
• The definition of your own HoFs — you are restricted to using the HoFs defined in the Elan library.

Using HoFs to iterate over a 2D List

If you are using Elan's Block Graphics, or have another need to process a 2D List (such as working with matrices or tabular data), and you want to do this in pure functions, you have the challenge of how to iterate over two dimensions — something that is straightforward in procedural programming by means of 'nested loops'. It is certainly possible to iterate over two dimensions of a List using HoFs within a single expression, but until you are fluent in such programming, the recommended approach is to break up the task into an 'inner' function that processes just a single column (or row, if preferred) of the 2D structure and an 'outer' function that processes each of the columns (or rows).

This is exemplified in the following functions, taken from the Life - functional demo, which together perform a role equivalent to the nextGeneration procedure in the Life - procedural demo:

Note the use of range in both functions to create colscolscolscolscols and rowsrowsrowsrowsrows respectively, which are just Lists of numbers e.g. [0, 1, 2, .. , 39]. The map HoFs iterate over these column and row numbers using them to access the appropriate portions of the gridgridgridgridgrid, which is a 2D List<of List<of Int>>list[list[int]]List<List<int>>List(Of List(Of Integer))List<List<int>>.

Principle 9: User-defined Classes should be immutable

It is possible, indeed highly desirable, to have user-defined Types (i.e. Classes) in FP. However, in true FP, an instance of a Class would never be mutated. So, when running under the functional profile, you may define Classes and add properties and function methods, but you may not define any procedure method. (In Object-oriented Programming you would use procedure methods to mutate an instance or do anything that cannot be done by a function.)

But this raises a question: how are we to make changes to an instance of a Class?. The answer is similar to that for updating a List, String, or other standard data structure within a function (described in Principle 7 ): you need define with.. methods that return a copy of the instance with specified changes. For example, in the Snake - functional demo, the Class GameGameGameGameGame has several with.. methods, one of which is shown here:

• returns a GameGameGameGameGame (i.e. a Class instance)
• creates a copy (i.e. a new instance) of thisthisthisthisthis (instance) named copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis
• reassigns the property headheadheadheadhead of copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis to the new value
• returns the updated copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis (instance)

Although a with.. method is a pure function, the standard form of a with.. method, like the one above, must be created using the with method instruction template, which is offered only within a Class, and only when using the functional profile.

The reason is that only within the with.. method are you allowed to reassign a property, and this may only be on the a value named copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis. You cannot, for example, edit it to say e.g. reassign this.xvariableName? to valuevalue or expression?0self.xvariableName? = valuevalue or expression? # reassign variable0this.xvariableName? = valuevalue or expression?; // reassign variable0Me.xvariableName? = valuevalue or expression? ' reassign variable0this.xvariableName? = valuevalue or expression?; // reassign variable0, since that would make changes observable from outside the function.

Note, in the same demo, that the Class SquareSquareSquareSquareSquare does not define any with.. methods because there is no need within the program to update any instance of Square — instead, a new instance is created, specifying the xxxxx and yyyyy coordinates as needed. For this reason the method named withNewApple does not need to be able to reassign a property on a copy, but does need to do other work. It has been written using the standard function method instruction template.

Principle 10: Generating Random numbers within a function requires a special pattern

Warning: This is an advanced technique and we recommend not attempting to use it until you are fairly comfortable with all the previous Principles.

In procedural programming you use the 'system methods' random (for a floating point number in the range 0 to 1) or randInt for an integer in a specified range. You may use these system methods within the main routine or a procedure, and you may pass these random values into a function, but you may not generate one or more random values within a function. When writing games and simulations that rely heavily on generating random numbers this can make it very difficult to achieve the primary objective of doing all data transformations within functions. Fortunately, there is a mechanism to generate random numbers within functions. Before looking at how to use it, it is important to understand the following:

• A small number of computers have dedicated hardware that generates true random numbers using advanced physics such as quantum effects or radioactive decay. Most computers, however, rely on 'pseudo random number' generation. This is where the next random number is derived from the previous one, but in such a way that for most practical purposes the results may be considered random.
• When you use the standard random or randInt system methods, the 'system' is keeping track of the previously generated numbers and using them to generate the next ones. This means that your code that uses them is dependent upon state of the system as a whole.
• A function has to be 'deterministic' in that its returned value must depend solely on the values provided as arguments; for a given set of argument values, a function must always return the same result. Its result cannot be dependent upon the current date, time or what the system has done previously. A function that was given all such information in its parameters would make it extremely complicated and unwieldy!

The 'functional Random' pattern, works within these constraints. If you want to generate one or more random numbers within a function, you must pass in the 'state' needed to derive that next random value, and you must pass the updated state to the next place where a new random is required, either inside or outside the function. This is done using an instance of the Type RandomRandomRandomRandomRandom (note the capital R, which distinguishes this from the procedural methods) which may be thought of as an instance of a 'Random Number Generator'.

To see how RandomRandomRandomRandomRandom works, we will first explore it within a tiny program intended to show the result of rolling a dice 10 times:

Now when you run the same program it produces random looking values, but always in the same sequence. This effect can be very useful for testing code, but it makes for very predictable games!

To overcome this predictability, initialise the random generator from the system clock (given that it changes 1,000 times per second) which will make it almost impossible to predict the sequence: