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 2nd post in the Exercises in Programming Style focus series.Other posts include:
- Introducing Exercises in Programming Style
- Exercises in Programming Style, stacking things up (this post)
- Exercises in Programming Style, Kwisatz Haderach-style
- Exercises in Programming Style, recursion
- Exercises in Programming Style with higher-order functions
- Composing Exercises in Programming Style
- Exercises in Programming Style, back to Object-Oriented Programming
- Exercises in Programming Style: maps are objects too
- Exercises in Programming Style: Event-Driven Programming
- Exercises in Programming Style and the Event Bus
- Reflecting over Exercises in Programming Style
- Exercises in Aspect-Oriented Programming Style
- Exercises in Programming Style: FP & I/O
- Exercises in Relational Database Style
- Exercises in Programming Style: spreadsheets
- Exercises in Concurrent Programming Style
- Exercises in Programming Style: sharing data among threads
- Exercises in Programming Style with Hazelcast
- Exercises in MapReduce Style
- Conclusion of Exercises in Programming Style
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
- Swap the two first elements - the list and the string
- Pop the first element - that would be the string to process
- Process the string
- Pop the now first element - that would be the list
- Add the processed string to the list
- 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 implementsList
! That means that while it offers stack-specific methods such aspop()
andpush()
, it also leaks a lot of unrelated methods from the whole inheritance hierarchy, such asadd()
andremove()
. 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 thesynchronized
keyword. From a pure performance point of view, it’s better to use a standardArrayList
. If one needs thread-safety, thenCollections.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 1st 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.