May 19, 2019 / EXERCISE, PROGRAMMING, STYLE

Exercises in Programming Style, stacking things up

Last week, we had our first taste of Exercises in Programming Style. Remember, the goal is to write a simple program, but to comply with some constraints. The previous constraint was that there was only a single variable available, an array. With a statically-typed language such as Kotlin, it required a lot of casting variables to their correct types before using them.

This week, the constraint is as radical, but different. Instead of a single array, we have two data structures available:

A hash map - also known as a dictionary, or an associative array - called the heap
A stack, aptly named… the stack

The goal is to do everything on the stack, and only when necessary store data on the heap. Fortunately, I once attended a keynote on non-mainstream languages, including PostScript, a stack-based language. For that reason, I was a bit familiar about how stack-based languages work. If you have no clue them however, I believe this post is going to be interesting.

This is the 2^nd post in the Exercises in Programming Style focus series.Other posts include:

Stack and stack-based languages quick intro

I assume you’re somewhat familiar with the data structure known as a Stack. It’s a specialized queue, with First In, Last Out semantics. It’s similar to a pile of plates: imagine plate A is put on a stack, then plate B, the plate C. One can only get the plate on the top from the stack: hence, the order will be C, then B, then A.

Likewise, stack-based languages put variables on a stack. To call a function, one need to first push parameters onto the stack, and only then call functions. A function will then pop its parameters from the stack, and push the result onto the stack.

A simple addition would translate as the following in pseudo-code:

PUT 1
PUT 2
ADD

With this, the function ADD will pop the 2, then the 1, sum them and push the result onto the stack.

This might translate as the following in Kotlin:

stack.push(1)
stack.push(2)
stack.push(
    (stack.pop() as Int) + (stack.pop() as Int)
)

One could create an add() function:

fun add() = stack.push(
    (stack.pop() as Int) + (stack.pop() as Int)
)

stack.push(1)
stack.push(2)
add()

The stack in the context of the exercise

The beginning of the program is a good sample to understand how to go beyond the simple example described above:

fun run(filename: String): Map<*, *> {
    stack.push(filename)                 (1)
    readFile()
    filterChars()
    ...
}

fun readFile() {
    val f = read(stack.pop() as String)  (2)
    stack.push(f)                        (3)
}

1	Push the file name passed as a parameter onto the stack
2	Pop the file name and read the file content
3	Push the file lines onto the stack

The read() function takes the file name as the parameter, because it’s a shared utility function shared among all chapters. If one wants to completely adhere to the constraints, it should be changed to accept no parameter and get the file name from the stack. Other functions take no parameters and strictly follow the rule.

fun filterChars() {
    stack.push(                                                       (1)
        (stack.pop() as List<*>)                                      (2)
            .map { "\\W|_".toRegex().replace(it as String, " ") }     (3)
            .map(String::toLowerCase))                                (3)
}

1	Push the result of the processing onto the stack
2	Pop the text lines as a `List` for processing
3	Process the string

This function is now nearly completely in line with the spirit of the exercise.

Preparing for the next step

Actually, the previous code cheats a bit in my opinion: map() is a function from the Kotlin’s stdlib that should be implemented on the stack.

This requires two helper functions that can be implemented with the help of Kotlin’s extension functions:

An extend() method - similar to Python - that takes a collection, and pushes every of its elements onto the stack:
```
fun <T> Stack<T>.extend(iterable: Iterable<T>) {
    iterable.forEach { push(it) }
}
```
A swap() method to swap the position of the first two elements on the stack:
```
fun Stack<Any>.swap() {
    val a = pop()        (1)
    val b = pop()        (1)
    push(a)
    push(b)
}
```
1 Using local variables should normally be disallowed, and the heap used instead. However, I allowed myself this small shortcut, because it looks a lot nicer, and doesn’t change much.

The full nine yards

The easiest part is to update the implementation of the readFile() function, by replacing push() with extend():

fun readFile() {
    val f = read(stack.pop() as String)
    stack.extend(f)                        (1)
}

1	At this point, the stack should consist of one element per line of text in the read file

The next step requires to pop every string from the stack, process it, then to push it back. However, because of the nature of the stack, the processed string will be put back on top. And only the top string can be accessed. We could use the heap instead of pushing back the string on the stack, but that would be cheating…

An alternative that is fully stack-compliant is the following:

Push a mutable list on the stack
Repeat the following until there’s but one element on the stack
1. Swap the two first elements - the list and the string
2. Pop the first element - that would be the string to process
3. Process the string
4. Pop the now first element - that would be the list
5. Add the processed string to the list
6. Push back the list onto the stack
Finally, pop the list that contains all processed strings
And push its contents as individual strings on the stack

There’s one additional trick. To add an element to a mutable list, the API is list.add(string). On the stack, this would translate as stack.pop().add(stack.pop()). That means the list should be the first item on the stack. However, the order in our process is reversed: the first item should be the string, the second one the list. Hence, we need a function that reverse the order of the caller - the list - and of the callee - the string. This is easily done with another extension function:

fun <T> T.addTo(collection: MutableCollection<T>) = collection.also { it.add(this) }

The associated implementation is:

fun filterChars() {
    stack.push(mutableListOf<String>())
    while (stack.size > 1) {
        stack.swap()
        stack.push(
            "\\W|_".toRegex()
                .replace((stack.pop() as String), " ")
                .toLowerCase()
                .addTo(stack.pop() as MutableList<Any>)
        )
    }
    stack.extend(stack.pop() as MutableList<Any>)
}

The trick of pushing a collection on the stack, swap, iterate-pop until there’s one single element left on the stack, and push the result as individual items back on the stack can be replicated in other functions. It only requires additional extension functions, depending on the collection’s type e.g. MutableMap.

Additional considerations

There are some additional considerations that deserve to be mentioned.

Evaluation

The first way that comes to mind to evaluate an item on the stack would be to pop it, store it on the heap, then push it back again if necessary. This can be avoided by using the peek() method: peek() allows to get a reference to the first item on the stack, but doesn’t pop it from the stack - it’s still there.

if ((stack.peek() as String).length < 2) {
    // Do something
}

Filter

Evaluation is used to filter out items. To discard an item from the stack, just pop it… and do nothing else with it.

if ((stack.peek() as String).length < 2) stack.pop()        (1)
else (heap["words"] as MutableList<Any>).add(stack.pop())   (2)

1	Filter the item out
2	Store the item on the heap

Custom stack implementation

An additional assignment in this chapter is to create one’s own stack implementation. The default Stack class offered in the JDK suffers from some issues:

It inherits from AbsractList, and thus implements List! That means that while it offers stack-specific methods such as pop() and push(), it also leaks a lot of unrelated methods from the whole inheritance hierarchy, such as add() and remove(). Though our code don’t use those unrelated methods, it still is a bad design decision.
Its parent class is Vector. While not deprecated per-se, this class fell out of favor because of its usage of the synchronized keyword. From a pure performance point of view, it’s better to use a standard ArrayList. If one needs thread-safety, then Collections.synchronizedList() can be used around it.

For both reasons - design and performance - the default Stack implementation is used very rarely.

From a design point of view, the contract for a custom stack is pretty straightforward:

interface Stack<T> {
    val size: Int
    fun push(t: T?)
    fun pop(): T
    fun peek(): T
    fun isNotEmpty()
}

From a performance point of view, it looks like a linked list implementation would be enough. There are no searches, only adding/removing the first element: a search in a linked list is O(n), while adding and removing the 1^st element is only O(1). The JDK API offers a linked lists' implementation, aptly named LinkedList. It’s a no-brainer to use is as a delegate inside our custom stack contract:

class Stack<T> {

    private val list = LinkedList<T>()

    val size: Int
        get() = list.size

    fun push(t: T?) = list.addFirst(t)
    fun pop(): T = list.removeFirst()
    fun peek(): T = list.peekFirst()
    fun isNotEmpty() = list.isNotEmpty()
}

Conclusion

Compared to the single array constraint from the previous week, less casting is required in the codebase.

On the other side, the stack mechanics take some time to get used to, especially if one wants to avoid using the heap: the related mind-calisthenics are interesting, especially swapping.

The complete source code for this post can be found on Github.

To go further:

Follow @nicolas_frankel