In this series, I would like to discuss some reaches of Go programming language. There is no shortage of Go-Language-Of-Cloud style articles in which you can explore the great benefits that Go indeed provides. However, there are lees to every wine, and Go does not go without blemish. In this highly opinionated series, we cover some controversies and, dare I say, pitfalls of the original Go design.
We start tough and begin with the essence of Go — it's inbuild data types. In this article, we put slice to the test. Let's move a step further from the Go Tour and use slice more extensively. For example, there is no separate data type as stack in Go, because slice type is intended to cover all its usage scenarios.
Let's briefly recap the usage of the stack. We can create a stack in two seconds using a couple of paper stickers. You write "buy milk" on the first sticker and put at the desk, and then "make the dishes" on the second and pile it on the first sticker. Now, you have a stack: the dishes sticker came last but will be served first, as it is on the top of the stack. Thus, there is an alternative name for stack — LIFO, Last-In-First-Out. To compare, there is the "opposite" data structure queue or FILO — first in, first out. In programming, stacks are everywhere, either in the explicit form or in the implicit as stack trace of the execution of a recursive function.
Ok, let's put slice into use and implement stack. We need to implement three operations: put at the top of the stack, pop from the top of the stack and return the top item from the stack without removing it (peek). We need to convert "vertical" structure stack to horizontal "slice". So the question is where we should put the top of the stack — at the beginning of slice or at the end of slice? If the top of the stack were at the beginning of slice, then at every push operation we would need to shift all items of the slice to the right. Therefore, the top of the stack will be at the end of the slice. In such a way, we can use append function to push an item at the top of the stack.
stack = append(stack, item)And to get the top item, we access the last item of the slice:
top := stack[len(stack)-1]To pop the item we also need to shrink the slice and exclude the top item (which is located at the end of the slice).
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]So far so good, though, we can notice that the syntax is a bit of a mouthful.
Now, let's play with our stack. Let's say we have a helper function that is responsible to add even items to the stack. For simplicity, let's only deal with a stack of integers.
func process(inp []int, stack []int) {
for _, item := range inp {
if item % 2 == 0 {
stack = append(stack, item)
}
}
}Let's put our stack into use:
func main() {
inp := []int{1, 2, 3, 4}
var stack []int
process(inp, stack)
for len(stack) > 0 {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
}What will be printed when we execute the function?
Actually, nothing will be printed at all. This is because our stack won't grow — at the end of the execution it will remain empty. In Go slice are not true references. A slice, indeed, points to some underlying array. However, it is not a true pointer because it also has two own properties — length and capacity. Internally, slice consists of a pointer to the array, the length of the segment, and its capacity. Inside function process we do update the underlying array. However, when we finish the execution of process finishes, and we are back to main function slice stack still have the length and the capacity equal to zero. To contrast map is a referential structure, and if we passed a map to process, then the changes would have been propagated to main. However, map has its own peculiarities which we cover in the next part.
Ok, slice is not "truly" referential structure, and that's why our code does not work. Let's make it a referential then, and use a pointer to the slice:
func process(inp []int, stack *[]int) {
for _, item := range inp {
if item % 2 == 0 {
*stack = append(*stack, item)
}
}
}Let's update our main as well:
func main() {
inp := []int{1, 2, 3, 4}
var stack *[]int
process(inp, stack)
for len(stack) > 0 {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Println(top)
}
}Now, what would be the result of this program? In this case, it won't compile at all. Now we have to dereference the slice when we measure its length or when we index it.
func main() {
inp := []int{1, 2, 3, 4}
var stack *[]int
process(inp, stack)
for len(*stack) > 0 {
top := (*stack)[len(*stack)-1]
stack = (*stack)[:len(*stack)-1]
fmt.Println(top)
}
}Have we finished already? Our code is already got a bit unwieldy, but we are not here yet. As we converted the stack to a pointer, we need to explicitly initialize it. Otherwise, we will hit all too familiar "nil pointer dereference". This error deserves some more love and will be covered in the next part. Meanwhile, we can just initialize the slice.
inp := []int{1, 2, 3, 4}
stack := &([]int{})
process(inp, stack)
for len(*stack) > 0 {
top := (*stack)[len(*stack)-1]
*stack = (*stack)[:len(*stack)-1]
fmt.Println(top)
}
}Have we finished yes? Yes, at this time we have, and we will get "4 2" as the result of the execution. The code is working, and our stack is ready for use. However, the code isn't that succinct and not that readable as well. All these dereference operations does not come for free and add some noise.
Let's also explore an alternative: instead of using a pointer to the slice, we can just return a new slice that accommodates the added items:
func process(stack []int, inp []int) []int {
// returns the grown slice
}This would also work and it is cheap in regard to performance costs because slice is a lightweight object as we discussed before. However, in this signature, we can see how the details of implementation show through the facade of stack data type. You won't usually see such kind of signature in any algorithmic books, because from a semantic point of view inside helper function process we add new elements to the existing slice and not creating and returning a new one.
To be fair, we don't have to implement stack too often (though, we can't just import it from some third-party lib due to the lack of generics). However, this example can highlight the features of slice data type in Go that can bite you in production — if you pass a slice to some function, this function cannot change the length of the slice.