Chapter 4. Logic and Recursion
So far, Erlang seems logical but fairly simple. Pattern matching controls the flow through a program, and requests that match a form return certain responses. While this is enough to get many things done, there are times when you’ll want more powerful options, especially as you start working with larger and more complicated data structures.
Logic Inside of Functions
Pattern matching and guards are powerful tools, but there are times when it’s much easier to do some comparisons inside of a function clause instead of creating new functions. Erlang’s designers agreed, and created two constructs for evaluating conditions inside of functions: the case expression and the less frequently used if expression.
The case construct lets you use pattern matching and guards inside of a function clause. It reads most clearly when a single value (or set of values) needs to be compared with multiple possibilities. The if construct evaluates only a series of guards, without pattern matching. The if construct tends to produce more readable code in situations where the multiple possibilities are specified by combinations of different values.
Both constructs return a value your code can capture.
Evaluating Cases
The case construct lets you perform pattern matching inside of your function clause. If you found the multiple function clauses of Example 3-2 hard to read, you might prefer to create a version that looks like Example 4-1, which you can find in ch04/ex1-case.
Example 4-1. Moving pattern matching inside the function
-module(drop).-export([fall_velocity/2]).fall_velocity(Planemo,Distance)whenDistance>=0->casePlanemoofearth->math:sqrt(2*9.8*Distance);moon->math:sqrt(2*1.6*Distance);mars->math:sqrt(2*3.71*Distance)% no closing period!end.
The case construct will compare the atom in Planemo to the values listed, going down the list in order. It won’t process beyond the first match it finds. The case construct will return the result of different calculations based on which atom is used, and because the case construct returns the last value in the function clause, the function will return that value as well.
Note
You can use the underscore (_) for your pattern match if you want a choice that matches “everything else.” However, you should always put that choice last—nothing that comes after that will ever be evaluated.
The results should look familiar:
1>c(drop).{ok,drop}2>drop:fall_velocity(earth,20).19.798989873223333>drop:fall_velocity(moon,20).8.04>drop:fall_velocity(mars,20).12.1819538662728495>drop:fall_velocity(mars,-20).** exception error: no function clause matchingdrop:fall_velocity(mars,-20) (drop.erl, line 5)
The case construct switches among planemos, while the guard clause on the function definition keeps out negative distances, producing (rightly) the error on line 5. This way the guard needs to appear only once.
You can also use the return value from the case construct to reduce duplicate code and make the logic of your program clearer. In this case, the only difference between the calculations for earth, moon, and mars is a gravitational constant. Example 4-2, which you can find in ch04/ex2-case, shows how to make the case construct return the gravitational constant for use in a single calculation at the end.
Example 4-2. Using the return value of the case construct to clean up the function
-module(drop).-export([fall_velocity/2]).fall_velocity(Planemo,Distance)whenDistance>=0->Gravity=casePlanemoofearth->9.8;moon->1.6;mars->3.71end,% note comma - function isn't done yetmath:sqrt(2*Gravity*Distance).
This time, the Gravity variable is set to the return value of the case construct. Note the comma after the end. This function isn’t done yet! Commas let you separate constructs inside of function declarations. The now more readable formula math:sqrt(2 * Gravity * Distance). is the last line of the function, and the value it produces will be the return value.
You can also use guards with a case statement, as shown, perhaps less than elegantly, in Example 4-3, which is in ch04/ex3-case. This example might make more sense if there were different planemos with different rules about distances.
Example 4-3. Moving guards into the case statement
-module(drop).-export([fall_velocity/2]).fall_velocity(Planemo,Distance)->Gravity=casePlanemoofearthwhenDistance>=0->9.8;moonwhenDistance>=0->1.6;marswhenDistance>=0->3.71end,% note comma - function isn't done yetmath:sqrt(2*Gravity*Distance).
This produces results similar to those you saw earlier, except that the error message in response to line 3 changes from no function clause matching drop:fall_velocity(mars,-20) to no case clause matching mars in function drop:fall_velocity/2:
1>c(drop).{ok,drop}2>drop:fall_velocity(mars,20).12.1819538662728493>drop:fall_velocity(mars,-20).** exception error: no case clause matching marsin function drop:fall_velocity/2 (drop.erl, line 6)
The error is correct, in that the case construct is trying to match mars, but misleading because the problem isn’t with mars but rather with the guard that’s checking the Distance variable. If Erlang tells you that your case doesn’t match but a match is obviously right there in front of you, check your guard statements.
If This, Then That
The if construct is broadly similar to the case statement, but without the pattern matching. This allows you to write a catch-all clause, a guard matching true at the end, and often makes it easier to express logic based on broader comparisons than simple matching.
Suppose, for example, that the precision of the fall_velocity function is too much. Instead of an actual speed you’d like to describe the speed produced by dropping from a tower of a given height. You can add an if construct that does that to the earlier code from Example 4-2, as shown in Example 4-4, in ch04/ex4-if.
Example 4-4. Adding an if construct to convert numbers into atoms
-module(drop).-export([fall_velocity/2]).fall_velocity(Planemo,Distance)whenDistance>=0->Gravity=casePlanemoofearth->9.8;moon->1.6;mars->3.71end,Velocity=math:sqrt(2*Gravity*Distance),ifVelocity==0->'stable';Velocity<5->'slow';Velocity>=5,Velocity<10->'moving';Velocity>=10,Velocity<20->'fast';Velocity>=20->'speedy'end.
This time, the if construct returns a value (an atom describing the velocity) based on the many guards it includes. Because that value is the last thing returned within the function, that becomes the return value of the function.
Note
The commas in the if behave like the and operator.
The results are a little different from past trials:
1>c(drop).{ok,drop}2>drop:fall_velocity(earth,20).fast3>drop:fall_velocity(moon,20).moving4>drop:fall_velocity(mars,20).fast5>drop:fall_velocity(earth,30).speedy
If you want to capture the value produced by the if construct and use it for something else, you can. Example 4-5, in ch04/ex5-if, sends a warning to standard output (in this case the Erlang shell) if you drop an object too fast.
Example 4-5. Sending an extra warning if the velocity is too high
-module(drop).-export([fall_velocity/2]).fall_velocity(Planemo,Distance)whenDistance>=0->Gravity=casePlanemoofearth->9.8;moon->1.6;mars->3.71end,Velocity=math:sqrt(2*Gravity*Distance),Description=ifVelocity==0->'stable';Velocity<5->'slow';(Velocity>=5)and(Velocity<10)->'moving';(Velocity>=10)and(Velocity<20)->'fast';Velocity>=20->'speedy'end,if(Velocity>40)->io:format("Look out below!~n");true->trueend,Description.
The new (second) if clause checks the Velocity variable to see if it’s above 40. If it is, it calls io:format, which creates a side effect: a message on the screen. However, every if must find some true statement or it will report an error if nothing matches. Here, you could add an explicit case matching when the Velocity is less than or equal to 40. But in many cases it won’t matter. The true -> true line is a catch-all that returns true no matter what reaches it. After the if concludes, the single line Description. returns the contents of the Description variable from the function.
Note
The catch-all approach works in cases where you only want to test for a subset of cases among a complicated set of possibilities. In cases as simple as this example, however, it’s probably cleaner to create a more explicit test.
The function produces an extra result—the message—when the distance is large enough (and the planemo’s gravity strong enough) to produce a velocity faster than 40 meters per second:
1>c(drop).{ok,drop}2>drop:fall_velocity(earth,10).fast3>drop:fall_velocity(earth,200).Look out below!speedy
Variable Assignment in case and if Constructs
Every possible path created in a case or if statement has the opportunity to bind values to variables. This is usually a wonderful thing, but could result in unstable programs by assigning different variables in different clauses. This might look something like Example 4-6, which you can find in ch04/ex6-broken.
Example 4-6. A badly broken if construct
-module(broken).-export([bad_if/1]).bad_if(Test_val)->ifTest_val<0->X=1;Test_val>=0->Y=2end,X+Y.
In theory, after the case or if is over, the program might crash because of unbound variables. However, Erlang won’t let you get that far:
1>c(broken).broken.erl:11: variable 'X' unsafe in 'if' (line 6)broken.erl:11: variable 'Y' unsafe in 'if' (line 6)error
The compilation errors turn up where your program actually uses the variables. The Erlang compiler double-checks to make sure the variables it’s about to put to use are properly defined. It won’t let you compile something that is broken.
You can bind variables in an if or case construct, but you have to define all of the variables in every single clause. If you’re defining only one variable, it’s also much cleaner to bind the return value of the if or case clause to a variable instead of defining that variable in every clause.
The Gentlest Side Effect: io:format
Up until Example 4-5, all of the Erlang examples you’ve seen focused on a single path through a group of functions. You put an argument or arguments in, and got a return value back. That approach is the cleanest way to do things: you can count on things that worked before to work again because there’s no opportunity to muck up the system with leftovers of past processing.
Example 4-5 stepped outside of that model, creating a side effect that will linger after the function is complete. The side effect is just a message that appears in the shell (or in standard output when you start running Erlang outside of the shell). Applications that share information with multiple users or keep information around for longer than a brief processing cycle will need stronger side effects, like storing information in databases.
Erlang best practice suggests using side effects only when you really need to. An application that presents an interface to a database, for example, really will need to read and write that database. An application that interacts with users will need to put information on the screen (or other interface) so that users can figure out what they’re expected to do.
Side effects are also extremely useful for tracing logic when you are first starting out. The simplest way to see what a program is doing, before you’ve learned how to use Erlang’s built-in tracing and debugging tools for processes, is to have the program report its status at points you consider interesting. This is not a feature you want to leave in shipping code, but when you’re getting started, it can give you an easily understandable window into your code’s behavior.
The io:format function lets you send information to the console, or, when you’re eventually running code outside of the console, to other places. For now, you’ll just use it to send messages from the program to the console. Example 4-5 showed the simplest way to use io:format, just printing a message it takes in double quotes:
io:format("Look out below!~n");
The ~n represents a newline, telling the console to start any new messages it sends at the beginning of the next line. It makes your results look a bit neater.
The more typical way to use io:format includes two arguments: a double-quoted formatting string, and a list of values that can be included in the string. ~w lets you incorporate content without indentation or formatting. In this case (which you can see in ch04/ex7-format), it might look like the following:
io:format("Look out below!~wis too high.~n",[Distance]);
or:
io:format("Look out below!~wis too high on~w.~n",[Distance,Planemo]);
io:format/2 offers many formatting options beyond ~w and ~n. You’ll encounter them in this book as they become necessary, but if you’re impatient, there’s a list in Appendix A. You may also want to explore the section on error logging in Chapter 9, if you find yourself using io:format for tasks that might be helped by more sophisticated logging tools.
Note
Erlang flatly prohibits operations that could cause side effects in guard expressions. If side effects were allowed in guards, then any time a guard expression was evaluated—whether it returned true or false—the side effect would happen. io:format wouldn’t likely do anything terrible, but these rules mean that it too is blocked from use in guard expressions.
Simple Recursion
Because variables can’t change values, the main tool you’ll use to repeat actions is recursion: having a function call itself until it’s (hopefully) reached a conclusion. This can sound complicated, but it doesn’t have to be.
There are two basic kinds of useful recursion. In some situations, you can count on the recursion to reach a natural end. The process runs out of items to work on, or reaches a natural limit. In other situations, there is no natural end, and you need to keep track of the result so the process will end. If you can master these two basic forms, you’ll be able to create many more complex variations.
Warning
There is a third form in which the recursive calls never reach an end. This is called an infinite loop, and is best known as an error you’ll want to avoid. As you’ll see in Chapter 8, though, even infinite loops can be useful.
Counting Down
The simplest model of recursion with a natural limit is a countdown, like the one used for rockets. You start with a large number, and count down to zero. When you reach zero, you’re done (and the rocket takes off, if there is one).
To implement this in Erlang, you’ll pass a starting number to an Erlang function. If the number is greater than zero, it will then announce the number and call itself with the number minus one as the argument. If the number is zero (or less), it will announce blastoff! and end. Example 4-7, found in ch04/ex8-countdown, shows one way to do this.
Example 4-7. Counting down
-module(count).-export([countdown/1]).countdown(From)whenFrom>0->io:format("~w!~n",[From]),countdown(From-1);countdown(From)->io:format("blastoff!~n").
The last clause could have a guard—when From =< 0—but it would be useful only to make clear when the blastoff happens to human readers. Unnecessary guard clauses may lead to weird errors, so brevity is probably the best option here, though you’ll get a warning that From is unused in the final clause. Here’s a test run:
1>c(count).count.erl:9: Warning: variable 'From' is unused{ok,count}2>count:countdown(2).2!1!blastoff!ok
The first time through, Erlang chose the first clause of countdown(From), passing it a value of 2. That clause printed 2, plus an exclamation point and a newline, and then it called the countdown function again, passing it a value of 1. That triggered the first clause again. It printed 1, plus an exclamation point and a newline, and then it called the countdown function again—this time passing it a value of 0.
The value of 0 triggered the second clause, which printed blastoff! and ended. After running three values through the same set of code, the function comes to a neat conclusion.
Note
You could also implement this conclusion with an if statement inside a single countdown(From) function clause, but this construction is unusual in Erlang. I find guards more readable in these cases, but you may see things differently.
Counting Up
Counting up is trickier because there’s no natural endpoint, so you can’t model your code on Example 4-7. Erlang’s single-assignment approach to variables rules out some approaches, but one way to make this work uses an accumulator. An accumulator is an extra argument that keeps track of the current result of past work, passing it back into a recursive function. (You can have more than one accumulator argument if you need, though one is often sufficient.) Example 4-8, which you can find in ch04/ex9-countup, shows how to add a countup function to the count module, which lets Erlang count up to a number.
Example 4-8. Counting up
-module(count).-export([countdown/1,countup/1]).countup(Limit)->countup(1,Limit).countup(Count,Limit)whenCount=<Limit->io:format("~w!~n",[Count]),countup(Count+1,Limit);countup(Count,Limit)->io:format("Finished.~n")....
It produces results such as the following:
1>c(count).{ok,count}2>count:countup(2).1!2!Finished.ok
The export directive makes the countup/1 function visible (as well as the earlier countdown/1, which you’ll find in the sample code).
The countup/2 function, which does most of the work, remains private, not exported. This isn’t mandatory. You might make it public if you wanted to support counting between arbitrary values, but keeping it private is common Erlang practice. Keeping the recursive internal functions private makes it less likely that someone will misuse them for purposes they’re not well-suited to. In this case, it doesn’t matter at all, but it can make a big difference in other more complex situations, especially when data is modified.
When you call countup/1, it calls countup/2 with an argument of 1 (for the current count) and the Limit value you provided for the upper limit.
If the current count is less than or equal to the upper limit, the first clause of the countup/2 function reports the current Count value with io:format. Then it calls itself again, increasing the Count by one but leaving the Limit alone.
If the current count is greater than the upper limit, it fails the guard on the first clause, so the second clause kicks in, reports “Finished,” and is done.
Warning
The guards here are sufficient to avoid infinite loops. You can enter zero, negative numbers, or decimals as arguments to countup/1 and it will terminate neatly. You can get into serious trouble, however, if your termination test relies on == or =:= for a more exact comparison rather than >= or =< for a rough comparison.
Recursing with Return Values
The counting examples are simple—they demonstrate how recursion works, but just discard the return values. There are return values—the io:format calls return the atom ok—but they aren’t of much use. More typically, a recursive function call will make use of the return value.
A classic recursive call calculates factorials. A factorial is the product of all positive integers equal to or less than the argument. The factorial of 1 is 1; 1 by itself yields 1. The factorial of 2 is 2; 2 × 1 yields 2. It starts to get interesting at 3, where 3 × 2 × 1 is 6. At 4, 4 × 3 × 2 × 1 is 24, and the results get larger rapidly with larger arguments.
But there’s a pattern here. You can calculate any factorial by multiplying the integer by the factorial of one less. That makes it a perfect case for using recursion, using the results of smaller integers to calculate the larger ones. This approach is similar to the countdown logic, but instead of just counting, the program collects calculated results. That could look like Example 4-9, which you’ll find in ch04/ex10-factorial-down.
Example 4-9. A factorial written with the counting-down approach
-module(fact).-export([factorial/1]).factorial(N)whenN>1->N*factorial(N-1);factorial(N)whenN=<1->1.
The first clause of factorial uses the pattern previously described. The first clause, used for numbers above one, returns a value that is the number N times the factorial of the next integer down. The second clause returns the value 1 when it reaches 1. Using =< in that comparison, rather than ==, gives the function more resilience against noninteger or negative arguments, though the answers it returns aren’t quite right: factorials really only work for integers of 1 or higher. The results are as previously suggested:
1>c(fact).{ok,fact}2>fact:factorial(1).13>fact:factorial(3).64>fact:factorial(4).245>fact:factorial(40).815915283247897734345611269596115894272000000000
This works, but it may not be clear why it works. Yes, the function counts down and collects the values, but if you want to see the mechanism, you need to add some io:format calls into the code, as shown in Example 4-10. (You can find this at ch04/ex10-factorial-down-instrumented.)
Example 4-10. Looking into the factorial recursion calls
-module(fact).-export([factorial/1]).factorial(N)whenN>1->io:format("Calling from~w.~n",[N]),Result=N*factorial(N-1),io:format("~wyields~w.~n",[N,Result]),Result;factorial(N)whenN=<1->io:format("Calling from 1.~n"),io:format("1 yields 1.~n"),1.
There’s a bit more overhead here. Presenting the result of the recursive call and still returning that value to the next recursive call requires storing it in a variable, here called Result. The io:format call makes visible which value produced the result. Then, because the last value expression in a function clause is the return value, Result appears again. The second clause for 1 is similar, except that it can report simply that 1 yields 1. because it always will.
When you compile this and run it, you’ll see something such as the following:
7>fact:factorial(4).Calling from 4.Calling from 3.Calling from 2.Calling from 1.1 yields 1.2 yields 2.3 yields 6.4 yields 24.24
Although the calls count down the values, as the logic would suggest, the messages about results don’t appear until the countdown is complete, and then they all appear in order, counting up.
The reason this happens is that the function calls don’t return values until the countdown is complete. Until then, the Erlang runtime builds a stack of frames corresponding to the function calls. You can think of the frames as paused versions of the function logic, waiting for an answer to come back. Once the call with an argument of 1 returns a simple value, not calling any further, Erlang can unwind those frames and calculate the Result. That unwinding presents the results—“X yields Y”—in the order that the frames unwind.
That “unwinding” also means that the code in Examples 4-9 and 4-10 is not tail recursive. When Erlang encounters code that ends with a simple recursive call, it can optimize the handling to avoid keeping that stack of calls around. This probably doesn’t matter for a one-time calculation, but it makes a huge difference when you write code that will stay running for a long time.
You can achieve tail recursion for factorials by applying the counting-up approach to factorials. You’ll get the same results (at least for integer values), but the calculations will work a little differently, as shown in Example 4-11, at ch04/ex12-factorial-up.
Example 4-11. A factorial written with the counting-up approach
-module(fact).-export([factorial/1]).factorial(N)->factorial(1,N,1).factorial(Current,N,Result)whenCurrent=<N->NewResult=Result*Current,io:format("~wyields~w!~n",[Current,NewResult]),factorial(Current+1,N,NewResult);factorial(Current,N,Result)->io:format("Finished.~n"),Result.
As in the counting-up example, the main function call, here factorial/1, calls a private function, factorial/3. In this case, there are two accumulators. Current stores the current position in the count, whereas Result is the answer from the previous multiplication. When the value of Current climbs past the limiting value N, the first guard fails, the second clause is invoked, and the function is finished and returns the Result. (You’ll get a compilation warning because the final clause doesn’t use the accumulator variables Current or N. You can ignore it.)
Because factorial/3’s last call in the recursive section is to itself, without any complications to track, it is tail recursive. That allows Erlang to minimize the amount of information it has to keep around while the calls all happen.
The calculation produces the same results, but does the math in a different order:
9>fact:factorial(4).1 yields 1!2 yields 2!3 yields 6!4 yields 24!Finished.24
Although the code is tracking more values, the Erlang runtime has less to do. When it finally hits the final result, there’s no further calculation needed. That result is the result, and it passes back through to the original call. This also makes it easier to structure the io:format calls. If you remove them or comment them out, the rest of the code stays the same.
You can also achieve tail recursion while counting down, without using a counter (Example 4-12).
Example 4-12. A concise factorial that counts down
-module(fact).-export([factorial/1]).factorial(N)->factorial(N,1).factorial(N,Result)whenN>1->factorial(N-1,N*Result);factorial(N,Result)whenN=<1->Result.
Note
You can learn more about working with logical flow and recursion in Chapter 3 of Erlang Programming (O’Reilly); Chapter 4 of Programming Erlang, 2nd Edition (Pragmatic); Sections 2.6 and 2.15 of Erlang and OTP in Action (Manning); and Chapters 3 and 5 of Learn You Some Erlang For Great Good! (No Starch Press).
Get Introducing Erlang, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
