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!
You must log in to post a comment.