Introduction
We started looking at arrays in the last step. We’re going to take a closer look today, exploring different ways of looking at Parrot arrays to build an averaging calculator. We’ll start with no array at all, to build the basic flow of our program and to demonstrate that an array is not always needed. Then we’ll move on to more interesting stuff, with array indexing, stack opcodes, and iterators.
Building the Basic Flow
Our averaging program is going to get its input from the user, and will take an arbitrary quantity of Numbers. Basically, it will keep accepting Numbers until the user indicates that she’s done. It will then display the average of all Numbers and exit.
Sounds simple enough. How will the user tell the program that she’s done? I like the idea of using the string “done”. It’s easy to remember and to the point. Wait. Let me think about that for a moment. The phrase “done” may be easy to remember, but “quit” is more common for leaving an interactive shell. I guess we should use “quit”.
Okay, let’s make the basic shell.
There’s a little debugging output that won’t be necessary once the program is filled out a little more, but we’ve got the basics.
Notice that the string is converted to a number using normal Perl rules: if it doesn’t have any numbers, it’s treated as zero. We could put in some error checking to chastise the user for bad input, but I don’t feel like it right now.
Averaging With No Arrays
I would like to point something out before we start digging into array features. We don’t need to use arrays when calculating something like an average. Here’s a perfectly useful example that never uses a single array:
Here’s what it looks like in action.
Why did I show this? Well, basically because “write an averaging program without using an Array in the language of your choice” is an interview question I’ve been asked a couple of times. It’s been a while, but I thought I’d be ready in case somebody asked me again. They’ll probably expect me to use Java or Ruby or something. This will show them. This will show them all! This will show them - uhh -
I’m not sure what it’ll show them.
Anyways - I wrote this version because I felt like it. Let’s start writing code that uses arrays, okay?
Stacks - Pushing and Popping
The stack is one of the fundamental data structures. The mental image is straightforward: you have a stack of things. You can push a new thing onto the stack, or you can pop the top thing from the stack into your hand. Stacks provide a simple way to handle every item in a collection. One thing you need to keep in mind is consistent with that stack image: once you’ve popped an item from the stack, it’s not in the collection anymore. So popping all the way through a stack results in what? Yes, that’s right. It results in an empty stack.
Still, the stack structure is good enough for a lot of collection handling, and will definitely work for our averaging application.
I’ll show you the code first, then we can talk about it.
We use the ResizableFloatArray PMC to hold our user’s numeric input. That is a built-in PMC, so we don’t need to do any special includes to access it. Just create a new one with the new
opcode.
After creating numbers
, we can push new values onto the array with the push
opcode. We use this to collect user input.
Later on, when we’re calculating the average, we use pop
to grab the most
recently pushed value from the stack. We keep doing that until we’re out of
numbers, as judged by a simple if
test.
If numbers
is empty and that test looks false to Parrot, the program falls
through to the next statement. That next statement is where we actually
calculate the average.
Yes, I was being more clever than I needed to with this example session, but I wanted to remind you that Parrot accepts E notation for numbers. Here’s the same session with the numbers looking more like you might have expected.
shift
and unshift
- The Bottom of the Stack
While push
and pop
work on the end of an array, Parrot also provides unshift
and shift
which handle corresponding functionality on the front of an array.
Let’s go back to the stack image for a moment. We already have the basic idea
of pushing onto and popping off of the top of a stack. We can also shift an
item from the bottom of that stack. What used to be the first item is now in our
hands, and the rested of the stack has shifted down so that the old second
item is the new first item. We can unshift an item into the bottom of the
stack. Now that unshifted item is the new first in the collection, and the old
first item is now the second.
I really need to get some illustrations in here. The idea is very easy to show, but my language skills aren’t adequate for the task.
Which is better? I’ll be honest with you. I don’t really know. I stick to pushing and popping because it’s easier to visualize.
However, when you combine push
and shift
you get a whole new structure called a queue.
Queues
A queue is yet another way of looking at your array when you are concerned about order. Stacks are LIFO: when you pop an item from the stack, you’re getting the last item that was pushed. Queues are FIFO: when you shift an item from the queue, you get the first item that was pushed. Okay - the technical term for placing an item in the queue is enqueue and for grabbing an item is dequeue. Pushing and shifting refer to the opcodes we’re using. Use whatever term you’re happier with.
The actual code for using a queue instead of a stack still doesn’t look all that different, because they’re still producing the same final result. Let’s write an example that clearly demonstrates the difference between a queue and a stack:
Now we can see exactly what numbers are being grabbed as our program calculates the sums.
That output could fill up the screen if I had a lot of values. I might want to fine-tune the debug output. Then again, I might want to just move on to the next subject.
Accessing by Index
Stacks and queues are a practical solution to a wide range of collection-handling
problems. They do have one shortcoming, though. Both of them are destructive.
When you pop
or shift
a value from an array, you are actually removing that value.
There is nothing left after you haved popped or shifted the last value. Sometimes that is okay, but sometimes you want to use the array for some other calculation. Those are the situations where you want a way to access the contents of the array without changing them. One way to do that is by accessing contents via an index.
The Parrot Array documentation shows a few things about setting up fixed-size arrays and setting individual values within arrays, but what I care about is the fact that array elements are accessed pretty much the same as in other languages I’m familiar with. We use square brackets []
to access a specific element, and the count is zero-based. Yes, zero-based indexing can be a little confusing sometimes. Think of it as “how many items from the front is the element I want?” and you should be fine.
We’ll build up our array in the same way that we have been, because I want the user to have some flexibility in deciding how many numbers to average. After that we’ll step through the array by incrementing an index.
A little more information is displayed in this version.
Notice that we check to see if we’ve stepped outside of bounds right away. We could test at the end of that section, but the truth is that I don’t trust my own code. The sooner I can see if I need to move on, the happier I’ll be. I could even test if we’ve somehow gone below zero if I was feeling especially paranoid. I won’t do that today, though. You’re welcome.
Using an Iterator
We’re nearly done. There is only one more way of traversing arrays that I want to look at. Parrot Iterators allow you to step through the contents of an array without doing anything to the array itself, while ignoring the details of array indexing.
All right. This example is easier for me to read than the others for some reason. That could be due to the simple fact that I’ve been looking at Parrot arrays for a couple of hours now. Maybe it’s because my blocks are more clearly labelled. Maybe it’s because using an iterator allowed me to build up a sum and still get the length the length of numbers
later, rather than building up two values at the same time. I’m not really sure. I do know that I feel like the iterator has given me a nice little convenience layer for handling my array. The output is still the same.
Conclusion
We had already taken a glance at arrays when we worked with the command line. Today we dove a little deeper, looking into different ways we can access the contents of an array. Now you understand how to treat a ‘ResizableFloatArray’ like a stack, a queue, a plain old array, or an iterable collection. These principles should work for other array types as well. Parrot has many array PMCs, and you can find them on the list of core PMCs here.
Backlinks
Added to vault 2024-01-15. Updated on 2024-07-10