|
|
| CARVIEW |
This article is a follow-up to this previous article about bounded loops. Bounded loops are cool because they always terminate and usually it is pretty easy to estimate the computational time. But as every computer scientist, who had to understand the halting problem, knows, there is a big class of algorithms which are harder. These are known as the class of μ-recursive functions. Here, unbounded loops exists which can run forever. I will introduce how IMHO unbounded loops can be implemented in Kotlin in a functional way. And, of course, I could not resist and did some measurements…
First, a Filter
An unbounded loop is typically a WHILE loop. While some expression holds, the loop body is evaluated. Hopefully at some point in time the loop body performs some side effects, the expression does not hold anymore, and the loop terminates. Let us do an example. Consider we have a list of order items, introduced in the previous article, and we would like to filter them for items with a minimal amount. Using an iterator, this would be a classical imperative solution:
fun filterOrderItemsWithMinimumAmountImperativ(
items: List<OrderItem>, amount:Int
):List<OrderItem> {
val result = mutableListOf<OrderItem>()
val iterator = items.listIterator()
while(iterator.hasNext()) {
val orderItem = iterator.next()
if (orderItem.amount >= amount) {
result.add(orderItem)
}
}
return result
}
The loop body has two side effects. First, it changes the iterator while stepping through the list. Second it builds up the filtered result list. The code is simple but still fragile. If I forget to call next() on the iterator, the program will not terminate. From a domain perspective, the loop should not be unbounded because the maximum amount of iterations is the number of elements of the original list. Lists in Kotlin are finite, thus the loop should be finite too.
If you solve this standard problem in Kotlin with a functional approach, you would fold the list and collect all fitting order items on the way:
fun filterOrderItemsWithMinimumAmountFunctional(
items: List<OrderItem>, amount: Int
) : List<OrderItem> =
items.fold(emptyList())
{ list, orderItem ->
if (orderItem.amount >= amount)
list.plus(orderItem)
else list
}
Now, you got rid of all side effects making the code more maintainable and less error-prone. In addition you use a bounded loop, hidden in the fold method, instead of a potentially unbounded WHILE loop. Thus, you will never introduce an infinite loop, even if you add some errors to your own code. Of course, filtering is a standard problem and in real life you would do something like this:
fun filterOrderItemsWithMinimumAmountFunctional2(
items: List<OrderItem>, amount: Int
) : List<OrderItem> =
items.filter { item -> item.amount >= amount }
So, IMHO the lesson to learn here is, if you use an unbounded loop double-check if you really need it. The leading question should be, does the problem at hand require an unbounded loop or would a bounded one suffice.
Let Us Crack a Password
When I thought about a problem which qualifies for an unbounded loop, I remembered a situation some years ago where I lost my password. I have a personal algorithm to generate my password variants. But, somehow no variant worked. After spending two hours testing different passwords with a list on paper next to me, containing all already tried ones, I decided to write my own password attack program. It created passwords using a dictionary in combination with my personal algorithms and tested them on my home computer. This qualifies for an unbounded loop, because it is possible that it never guesses the correct password.
The imperative solution is quickly laid out:
fun dictionaryAttackImperative(
dictionary: Iterator<String>,
checkPassword: (String) -> Boolean
): String? {
var entry: String = null
do {
entry = dictionary.next()
} while (!checkPassword(entry))
return entry
}
It uses an iterator as interface to the creation of new passwords. The actual check of the password is done in the function checkPassword(). As in the example above the iterator-based solution relies on side effects. This is a functional alternative:
fun attackFunctional(checkPassword: (String) -> Boolean)
: String? =
generateSequence(SeedPassword, Password::plusOne)
.first {password ->
checkPassword(password.toString()) }
.toString()
Instead of a WHILE loop a sequence is used. The elements of this sequence correspond to the state of the loop. The next state of the loop is only computed from its previous state. This prevents the usage of side effects. In the code above the state consists only of the current password. The function Password::plusOne is used to compute the next state, in this case the next password which is to be checked. The loop is terminated if the state fulfills a condition, such as the password check is positive.
In this pattern a loop consists of a flow of clearly defined states produced by a clearly defined function. It is the same idea as the iterator pattern but without side effects. From my experience this pattern helps a lot to understand the nature of the computation and to create maintainable code.
With these wise words, this article could end in functional harmony. But, the real world always contains some inconvenient, but interesting truths that disturb the harmony. So, the rest of this article is (again) about the development of efficient code using an imperative or a functional style.
The Password Variant Creation Algorithm
To test the code I choose a simple algorithm for password creation. A password is always an alternating combination of a letter and a digit, ending with a letter. This means “a”, “b”, “1c”, “y5x6c” are valid passwords, “8”, “asd123”, “a0a0” are not valid. To enumerate all possible passwords you can think of them as kind of numbers. The lowest number is “a”. If you increase you get “b”. If you increase “a” 26 times to you get “0a”.
The Imperative Variant
In the imperative variant I use an iterator to compute the next password:
class LettersAndNumbersDictionaryImperative : Iterator<String> {
private var nextEntry: String = "a"
override fun hasNext(): Boolean = true
override fun next(): String {
...
}
..
}
The magic happens in the next() method, which computes the “increased” password:
override fun next(): String {
val result = nextEntry
var nextEntryArray = nextEntry.toCharArray()
var index = 0
do {
val ele = nextEntryArray[index]
val (elePlusOne, overrun) = plusOne(ele)
nextEntryArray[index] = elePlusOne
index++
if (overrun && (index == nextEntry.length)) {
val nextEle = lowestElemOnIdex(index)
val nextEleArray = CharArray(1) { nextEle }
nextEntryArray = nextEleArray + nextEntryArray
}
} while (overrun && (index < nextEntry.length))
nextEntry = String(nextEntryArray)
return result
}
fun plusOne(ele: Char): Pair<Char, Boolean> =
when {
ele.isDigit() -> digitPlusOne(ele)
ele.isLetter() -> letterPlusOne(ele)
else -> throw RuntimeException(
"This should never happen. Ele = $ele")
}
fun lowestElemOnIdex(index: Int) =
if (index % 2 == 1) '0' else 'a'
Without going into details, you can see that there are quite some side effects and unbounded computations lurking in the code. You can also see, that the code is probably pretty efficient, because it uses an array which is updated in-place to compute the next password.
The Functional Variant
In a functional style, side effects and in-place updates are not possible. Thus, every new password is a new immutable object. In my solution, a password consists of a list of elements. The computation of the increased password is performed on this list:
class Password(val elements: List<PasswordElem>) {
fun plusOne(): Password =
computePasswordPlusOne(elements)
...
}
Without going into details here, the computation is done by increasing the first element, checking for an overflow, and, if necessary, compute the overflow in the remaining sublist:
fun computePasswordPlusOne(elements: List<PasswordElem>)
: Password {
val (increasedFirstElem, overflow) =
elements.first().plusOne()
val increasedFirstElemList =
listOf(increasedFirstElem)
val elementsRemainder = elements.drop(1)
return if (overflow) {
val remainderPlusOne =
if (elementsRemainder.isNotEmpty()) {
Password(elementsRemainder)
.plusOne()
.elements
} else {
increasedFirstElem.nextLowestElem()
}
Password(increasedFirstElemList + remainderPlusOne)
} else {
Password(increasedFirstElemList +
elementsRemainder)
}
}
This code is built on top of the elements of the password which may be digits or letters:
sealed class PasswordElem(private val element: Char) {
abstract fun plusOne(): Pair<PasswordElem, Boolean>
abstract fun nextLowestElem(): List<PasswordElem>
...
}
class LetterElem(private val letter: Char) : PasswordElem(letter) {
override fun nextLowestElem(): List<PasswordElem> =
listOf(DigitElem('0'))
override fun plusOne(): Pair<PasswordElem, Boolean> =
if (letter == 'z')
Pair(LetterElem('a'), true)
else
Pair(LetterElem(letter + 1), false)
}
class DigitElem(private val letter: Char) : PasswordElem(letter) {
override fun nextLowestElem(): List<PasswordElem> =
listOf(LetterElem('a'))
override fun plusOne(): Pair<PasswordElem, Boolean> =
if (letter == '9')
Pair(DigitElem('0'), true)
else
Pair(DigitElem(letter + 1), false)
}
This codes looks a lot of cleaner and maintainable than the imperative one. But it is also a lot more code. And there is a lot of object creation involved. Thus, let us do some measurements to see how the two solutions compare!
Functional vs. Imperative
I measured the time in ms to find passwords of different lengths. The axes are logarithmically scaled. Here are the results:
As expected the imperative variant is faster. It is even much faster, up to a factor of 24. Does this mean an algorithm such as the password search can only implemented with an imperative language?
Back to Haskell
To investigate this question I implemented the algorithm in the grandmother of functional languages, in Haskell. The algorithm is pretty similar to the implementation in Kotlin. This is the main “loop”:
import Data.List as L
import Data.Vector as V
attackFunctional1 checkPassword = L.find checkPassword passwords where
passwordsAsVectors = iterate plusOnePassword seedPassword
passwords = Prelude.map passwordToString passwordsAsVectors
The magic happens in the function plusOnePassword:
plusOnePassword password =
if (overflow) then overflowPassword else nonOverflowPassword
where
(increasedFirstElem, overflow) = plusOneElem $ V.head password
elementsRemainder = V.tail password
overflowPassword = cons increasedFirstElem remainderPlusOne
where
remainderPlusOne = if (V.null elementsRemainder)
then
V.singleton $ nextLowestElem increasedFirstElem
else
plusOnePassword elementsRemainder
nonOverflowPassword = cons increasedFirstElem elementsRemainder
If you understood the Kotlin variant, the Haskell version should be readable too. It also relies on basic element types:
data Elem = Digit Char | Letter Char
deriving Show
lowestDigit = Digit '0'
lowestLetter = Letter 'a'
plusOneElem (Digit c) =
if (c == '9') then ( lowestDigit, True)
else ( Digit $plusOneChar c , False)
plusOneElem (Letter c) =
if (c == 'z') then ( lowestLetter, True)
else ( Letter $plusOneChar c, False)
elemToChar (Digit c) = c
elemToChar (Letter c) = c
nextLowestElem (Digit _) = lowestLetter
nextLowestElem (Letter _) = lowestDigit
plusOneChar :: Char -> Char
plusOneChar c = chr ((ord c) + 1)
Without explaining the details, you still can see, that the Haskell variant is more or less the same as the functional Kotlin variant. Now let us see, how it performs:
Similar to the last measurements, the optimized and compiled Haskell code is for small values faster than the interpreted code running in the JVM. But, because it is the same implementation, the Haskell solution scales equally bad. And, it piles up junk. I stopped the Haskell program looking for the 8-length password, when the heap size reached 50 GB.
Haskell, the 2nd try
Ok, the problem seems to be the list which is not garbage collected and, thus, eats up all the memory. In this case you need a real functional loop, a.k.a. recursive function:
attackFunctional2 checkPassword = attackFunctionalIteration seedPassword
where
attackFunctionalIteration password =
if (checkPassword passwordAsString)
then passwordAsString
else attackFunctionalIteration $ plusOnePassword password
where
passwordAsString = passwordToString password
Instead of putting the loop state in a list, it is put into the parameters of a recursive function call. In contrast to Kotlin, the Haskell compiler is really good in transforming recursive calls into “real” loops. Now the measurements look much better:
The Haskell code scales nicely and, even for longer passwords, is similarly fast as the imperative Kotlin variant with its fast in-place updates.
Tail Recursion to the Rescue
If the application of recursive functions as loops helps the Haskell variant, let us do the same with Kotlin. In contrast to Java, the Kotlin compiler actually supports tail recursion with a specific keyword. Here is the code in Kotlin:
fun attackFunctionalTR(checkPassword: (String) -> Boolean): String? {
tailrec fun attackFunctionalIteration(password: Password): String {
val passwordAsString = password.toString()
return if (checkPassword(passwordAsString))
passwordAsString
else attackFunctionalIteration(password.plusOne())
}
return attackFunctionalIteration(SeedPassword)
}
The code is easy to write and pretty similar to the Haskell variant. I did not need to modify the already existing code for reusage. Now let us see, what we actually achieved:
D’oh, the tail recursive function behaves the same as the old functional variant. If you think about it, it makes perfect sense. In Haskell there was the problem, that the old values did not get garbage collected. They piled up and slowed everything down. In Kotlin we solved this issue by using a sequence. Thus, we gained nothing by using the tail recursion.
IMHO, the second Haskell variant is faster because it uses a Vector datatype. Under the hood, it can compile to in-place updates. To my knowledge, in Kotlin there are no similar data types, optimized for immutable writes.
One last word to put these results into perspective. In real life the most time consuming operation is to check the password because this is done by an iterated hash function on an external system. The management overhead to compute the potential passwords is negligible. Still, for me, it is interesting to see, how efficient functional programming can be in a modern programming language, such as Kotlin.
To sum it up
Unbounded loops can easily and nicely be done in Kotlin with sequences. The values in the sequence define the loop state. The computation from one state to the next is done by a pure function. But, in many cases you can avoid unbounded loops and use the much safer bounded loops.
If you need maximum performance in Kotlin, you sometimes still need imperative code. In this case, I would advise to hide it behind a functional interface. Then you can get the best of both world.
You can find the examples and the measurements on GitHub: https://github.com/akquinet/functional-loops-in-kotlin
Feedback is always welcome!
]]>
Loops are a basic paradigm in imperative programming languages. In functional languages you also need to loop, but you do it differently. Here, I present how I prefer to implement loops in a functional style using Kotlin. To check, if this is a good idea at all, I do some benchmarks against imperative variants and good old Haskell.
When I have some spare time left, I like to play with new things. For some months now, I invest this time to learn Kotlin. Because there is not enough time for a pet project, I solve small exercises on CodeWars. To make it even more motivating I decided to implement all solutions in a purely functional way without any side effects. This is actually fun, even though Kotlin itself is far away from being a pure functional programming language. The main approach in Kotlin for computations often consist of typical imperative for-loops. So let us see how to do them in a functional style.
Finite Loops on containers
A long time ago, as a student I learned that there are two types of loops in programming languages. The first type is the typical for-loop with fixed boundaries. These are known as LOOP programs or primitive recursive functions. These have the nice property that they always terminate within an upper bound of time. Here is an example:
data class OrderItem (val orderNumber: String, val amount: Int )
fun sumImperativ(items : List<OrderItem>) : Int {
var result = 0
for( i in 0 until items.size) {
result += items[i].amount
}
return result
}
An OrderItem consist of some order number and an amount of ordered items. The function sumImperativ loops through a list of order items, extract the amounts, and sums them up. The for-loop is fixed. If items is not changed in the loop, then the maximum number of iterations is items.size. And, because the interface List does not contain any write method in Kotlin, items cannot be changed.
There are still some issues with the solution. It is easily possible to get the index wrong. If, for example, the loop would be for(i in 0 ..items.size) you would access i[items.size] which results in an ArrayIndexOutOfBoundsException. The mutable variable result is used to sum up alle the values. In this short example this may work. But in more complex scenarios, errors may sneak into the code.
The functional community often claims that using functional programming (fp), the resulting code is much less error prone. So let us have a look, how this simple loop is done in Haskell, the old champion in the fp programming languages league:
sumOrderItems items = summedAmount where
amounts = map amount items
summedAmount = sum amounts
First you extract all the amounts of the item by mapping the extractor function amount on the list of order items. As result you get amounts as a list of integers and just sums them up. In this short example you would probably inline the variables:
sumOrderItems2 items = sum (map amount items)
Now we get rid of index problems and split the computation in the loop cleanly in its two parts, extraction and summation. There are no side effects and much less things can get wrong. But, looking at the loops we are somehow cheating. This is, because the loops are hidden behind the utility functions map and sum. Their implementation may be hard, especially if the container data types are complex. But because of the functional design the application developer does not need to care. This has proven so valuable that more or less every modern programming language supports this approach. This is the implementation in Kotlin:
fun sumFunctional(items: List<OrderItem>): Int =
items.map(OrderItem::amount)
.sum()
This looks pretty similar to Haskell. IMHO if you use this style of development in Kotlin, the thinking style is pretty similar to the development using Haskell.
Finite Loops without Containers
Very often, looping is done over the contents of container, but not always. A common use case is a mathematical computation. Let us look at a textbook example, the integration of a function. For many function types, an integration can be approximated by transforming the function into a sequence of rectangles, and then sum up the area of the rectangles. Using a finite loop, this is how the algorithm can look like in Kotlin:
fun integrateImperative(
start :Double, end : Double, precision: Long,
f : (Double) -> Double) : Double {
val step = (end-start) / precision
var result = 0.0
var x = start
for ( i in 0 until precision) {
result += f(x) * step
x += step
}
return result
}
Even though this loop is not very complicated, I usually need some time to clearly understand what happens here. Firstly, the rectangles are iterated in the for loop. For each rectangle its area is computed as f(x) * step. All the areas are summed up in result. The variable x is used to adapt the x-coordinate to the loop variable.
Now let us do this the functional way:
fun integrateFunctional(
start :Double, end : Double, precision: Int,
f : (Double) -> Double) : Double {
val step = (end-start) / precision
return (0 until precision)
.map { index -> start + index * step}
.map { x -> f(x) * step }
.sum()
}
The first surprise is that the range expression (0 until precision) which is used in the for loop can also be used as container for the functional style described above. Now, the phases in the computation are clearly separated. First, the index is mapped to x-coordinates, then the areas of the rectangles are computed, and finally summed up.
IMHO this is much better readable than the for loop. But all the interpretations, I gave above, are not in the code. Thus, to enhance the readability of the code, to make it much cleaner, you can do what you typically do: extract variables with meaningful names:
fun integrateFunctionalCleanCode(
start :Double, end : Double, precision: Int,
f : (Double) -> Double) : Double {
val step = (end-start) / precision
val xCoordinates = (0 until precision)
.map { index -> start + index * step }
val allRectangles = xCoordinates
.map { x -> f(x) * step }
return allRectangles
.sum()
}
Now, the domain knowledge is represented in the variables names, and still the code is functional. This seems trivial, but in my experience, when people, such as myself, discover the functional coding style based on streams, they tend to build long und longer stream concatenations. At some tipping point they are not readable anymore and comments are included. This is latest point in time where I would advise to extract variables. The Clean Code principles also applies for functional programming!
What about Performance?
One of the usual counter argument from the imperative guys is that functional programming is slow. The best way to handle this question is to do some measurements. On my (old) MacBook Pro 2015, I measured the execution times for different precisions, each 5 times, and averaged them. These are the results:
Both axes are logarithmically scaled. Because the computation scales linearly the graphs should be linear too. The first surprise is the speedup in the imperative execution times at precision 10^6. Some magic loop optimization seems to kick in, leaving the functional implementation far behind, by a factor of nearly 200. Until the precision 10^5, the speed of the two implementations are pretty similar. I used Kotlin in version 1.3.40.
But, the real issue is the missing data point at precision 10^8. The point is missing because the JVM crashed with an OutOfMemoryError exception. To understand this you have to look at the type of xCoordinates, which is ArrayList. This means all coordinates and all rectangles are stored in an array, consuming memory. For a large loop this is definitely not what you want!
So, the case for functional programming is all lost? No, wait. Kotlin supports sequences . These are in essence lazily evaluated and potentially infinite lists. This is similar to how Haskell works efficiently on large sets of data. The refactoring to sequences is simple. You just hav to add one method call:
fun integrateFunctionalSequence(
start: Double, end: Double, precision: Int,
f: (Double) -> Double): Double {
val step = (end - start) / precision
val xCoordinates = (0 until precision).asSequence()
.map { index -> start + index * step }
val allRectangles = xCoordinates
.map { x -> f(x) * step }
return allRectangles
.sum()
}
Now let us look, if this improves anything:
Firstly, the application does not crash anymore for a precision of 10^8. If you look at the first two data points, you can see that the sequence approach is faster than our first functional implementation. But, when the optimization kicks in, the imperative version is with a factor of 10 still much faster.
To conclude, yes, Kotlin is still much more optimized for imperative programming. If performance is an issue and if there are a lot of computations to perform, you should consider good old looping.
One short look at the old Champion again
To check if this means, functional programming is not fit for numerical computations at all, let us do the same algorithm in Haskell:
integrate start end precision function = sum allRectangles
where
step = (end - start) / (fromIntegral precision)
xCoordinates = map (\i -> start + (fromIntegral i) * step)
[ 0 .. (precision-1)]
allRectangles = map (\x -> (function x) * step) xCoordinates
Not surprising, the Haskell code looks pretty similar to its Kotlin variant. Actually the explicit conversion of datatypes with fromIntegral looks somehow old school. Now let us do some measurements:
Now, this is a nice curve. Firstly, Haskell finally provides the expected linear curve. Up to 10^5 iterations it is much faster than Kotlin. With the optimization at 10^6 iterations, it as as fast as Kotlin.
To sum it up
In my point of view, I have shown that in Kotlin you can use the functional programming style as good as in a pure functional language such as Haskell. For most common small problems, it as fast as imperative solutions. If you have more computional demands you need to take care to use sequences. Still, if you really want to do number crunching, Kotlin in version 1.3.40 needs some more performance tuning to support functional programming.
This was all focused on bounded computations. When I find some more spare time, I will write down an article about unbounded computations. The code of all examples is available on Github: https://github.com/akquinet/functional-loops-in-kotlin
Addendum
Shortly after publishing this article a previous colleague of mine, Martin Möller, sent me a pull request with some alternative and faster functional solutions of the integration problem. This is one of these:
fun integrateSumBy(
start: Double, end: Double, precision: Int,
f: (Double) -> Double): Double {
val step = (end - start) / precision
return (0 until precision).sumByDouble { index ->
val x = start + index * step
f(x) * step
}
}
This version (sumBy) is actually significantly faster:
I played a little bit with the code and got the impression that the concatenation of the sequences is mostly responsible for the bad performance. Thus, if you like functional programming in Kotlin and need performance, then avoid chains of sequences.
Thank you Martin!
]]>