Learn some functional programming: funstacker

Reshaping our language

Consis­tent with the prin­ci­ples of func­tional program­ming, our goal is to remove the state and muta­tion from our program. But first, we need to recon­sider more than just the imple­men­ta­tion of our stack.

Recall that stacker was designed around the idea of wrap­ping each argu­ment in the source code within its own (handle ···) datum. So source code that looked like this:

Would end up as a series of S-expres­sions that looked like this:

Sure, this was obvious & conve­nient. But it also resulted in a language imple­men­ta­tion where each call to handle only knew about the current argu­ment. More­over, each call to handle was inde­pen­dent of the ones that come before and after. So we had no choice but to main­tain the program state using an external stack vari­able, and mutate it as the program progressed. This style of program­ming—where func­tion calls use muta­tion to change the program state—is known as imper­a­tive program­ming. It has its place. But it’s not what we’re going for.

If we want to get rid of state & muta­tion, we need to find a different way to main­tain the stack as we handle each argu­ment. And this starts at the top, with the way the expres­sions in our program are nested—what in Racket is called the shape of the code.

One option would be to nest the calls to handle (but let’s call this theo­ret­ical func­tion h2, since it won’t work the same way as handle):

What would happen here? S-expres­sions are eval­u­ated from the inside out. So (h2 4) would be eval­u­ated first, and then its result used as the first argu­ment in (h2 result 8), and so on. So we’d be processing our argu­ments in the correct order, and we could pass the interim stack from one expres­sion to the next. At the end, we’d have the finished stack.

Another option would be to pass all the argu­ments to a single func­tion (let’s call this one handle-args):

In this case, handle-args could access all the argu­ments. There’d be no need to mutate a vari­able outside the bound­aries of the func­tion. All the house­keeping could happen inside, and then the func­tion would deliver the finished stack as its return value.

Though the nesting patterns are different, it turns out that both approaches end up working mostly the same way. But the h2 approach requires a little more knowl­edge about macros than we currently have. So we’ll go with the handle-args approach—pass all the argu­ments to a single func­tion.

Rewriting our reader

Our reader still consists of a single read-syntax func­tion. Let’s replace the existing read-syntax in funstacker.rkt with this code:

This version works basi­cally the same way as before. But this time, rather than wrap each argu­ment in its own (handle ···) datum, we’ll convert the argu­ments into datums without wrap­ping them at all, storing them in a list called src-datums. Then, inside our module-datum, we’ll splice the src-datums into a single (handle-args ···) expres­sion. handle-args will be the name of the new func­tion that will process our argu­ments.

Rewriting our expander

As before, we need to provide a #%module-begin macro that acts as the starting point for the expander. Let’s replace the existing #%module-begin in funstacker.rkt with this code:

In our new read-syntax, we saw that our module-datum will contain exactly one expres­sion, namely a call to (handle-args ···). So the funstacker-module-begin macro only has to be able to handle this one argu­ment as input, which we name HANDLE-ARGS-EXPR. Then, because HANDLE-ARGS-EXPR will return a finished stack, we use it as the input argu­ment in (display (first HANDLE-ARGS-EXPR)). Notice that it replaces stack, the state vari­able that we’re elim­i­nating.

Then we need to imple­ment our stack. In funstacker.rkt, we replace stack, pop-stack!, push-stack! and handle with our new handle-args func­tion:

Some of this looks similar to our old handle func­tion. But we’re moving from an imper­a­tive style to a func­tional style, and intro­ducing some new nota­tion. Let’s go through this func­tion line by line.

The dot in front of args desig­nates it as a rest argu­ment. A rest argu­ment is optional in any func­tion defi­n­i­tion. It can only appear as the last argu­ment. Any number of posi­tional argu­ments can appear before it. The rest argu­ment means “gather the remaining argu­ments in a list and assign it to this vari­able”. A rest argu­ment makes it possible for a func­tion to accept any number of argu­ments. That’s what we need here, since we don’t know in advance how many argu­ments will be in the source code.

Next we have for/fold, which deserves a place in everyone’s list of favorite Racket tools. for/fold iter­ates over a list of values (like the for loops we’ve seen in other languages). But each pass of the loop also returns a special value called an accu­mu­lator.  + The accu­mu­lator is the desti­na­tion of the “folding”, and is also used in the related func­tions foldl and foldr. An accu­mu­lator is similar to a state vari­able, with two differ­ences. First, the accu­mu­lator lives inside our loop, rather than outside. Second, on each pass of for/fold, rather than change the value of the accu­mu­lator with set!, we replace it with a whole new value. The loop ends when the iter­ator runs out of values. The return value of the whole for/fold loop is the final value of its accu­mu­lator.

Let’s consider a simple for/fold loop just so we under­stand the mechanics:

Here, our accu­mu­lator is sum and starts with the value 0. Our iter­ator is int, which will take on each value in (list 1 2 3 4 5 6 7 8 9 10). On each pass of the loop, (+ sum int) means that we add the current value of the sum accu­mu­lator to the current value of int. This result becomes the new accu­mu­lator value for the next pass. So we end up adding the inte­gers together, and the return value of the whole loop is 55.

Going back to our loop:

A for/fold loop has two manda­tory parts.

This loop also uses two optional parts:

This cond expres­sion looks similar to the one we had in our orig­inal handle func­tion. But this time, instead of mutating an external stack vari­able, each branch will create an updated copy of our stack-acc accu­mu­lator. In essence, instead of relying on external push-stack! and pop-stack! func­tions, we’ll do all the stack processing inside our cond.

If arg is a number, we push it onto the stack with cons. If arg is a stack oper­ator, we calcu­late op-result using the first and second elements of stack-acc. Unlike pop-stack!, these oper­a­tions don’t remove argu­ments from the stack, so we have to explic­itly drop two items from stack-acc. Then we put op-result onto the stack (again with cons). The new stack that’s created at the end of each branch will be returned as the value of the whole cond expres­sion, and thereby become the new value of stack-acc used in the next iter­a­tion.

Finally, as we did in stacker, we need to provide our stack oper­a­tors:

Testing Funstacker

Our whole "funstacker.rkt" should now look like this:

If we run our "funstacker-test.rkt" file:

We’ll get:

Our conver­sion to func­tional program­ming is complete. Better still, funstacker is even shorter than stacker.