Follow the grammar: bf

Func­tional thinking

In the func­tional version of the bf expander, we have two goals:

What makes this tricky is that bf is, by its nature, an imper­a­tive language. Recall from how bf works that the language relies on two state values: a memory array of 30,000 bytes, and a pointer into that array.

In funstacker, we learned that we could approx­i­mate the behavior of state vari­ables by turning them into accu­mu­la­tors within a for/fold loop. That’s a good start. But unlike funstacker, it won’t be enough. We need to step back and adjust our concep­tual model of our bf imple­men­ta­tion.

Before, we modeled our bf oper­a­tions as trig­gering func­tions that mutated existing state vari­ables. But these func­tions took no argu­ments, and returned no values.

This time, consis­tent with the func­tional-program­ming idiom, we’ll model our bf oper­a­tions as func­tions that take the current array & pointer values as input, operate on them, and then return new array & pointer values as output. This output, in turn, becomes the input to the next func­tion in line. In other words, rather than storing state values outside our func­tions, we’ll let the values travel through the func­tions.

By the way, is this approach guar­an­teed to give us a bf expander that’s shorter than the imper­a­tive expander? No. Faster? No. Morally supe­rior? No. But the func­tional approach is more idiomatic to Racket. It will become a more vital skill as we advance through the tuto­rials, even if it’s not a huge benefit for bf.

(Re)starting the expander

First, let’s strip our "expander.rkt" module back to the bf-module-begin macro, which will be the same:

As before, we’ll need to write macros to handle bf-program, bf-op, and bf-loop nodes in our parse tree. But before we get to those, we’ll make a helper func­tion that will be the engine of our inter­preter.

Applying pres­sure

Our goal is to allow our two bf state values—a memory array of 30,000 bytes, and a pointer into that array—to be passed from one bf oper­a­tion to the next.

To do that, we’ll model these new bf oper­a­tions as func­tions that take two input argu­ments—an array and a pointer—and return a new array and a new pointer. It’s possible for Racket func­tions to return multiple values (see func­tions). But we’ll keep things simple and package the new array and pointer inside a list, which will behave as a single return value. So the new func­tions imple­menting our bf oper­a­tions will follow this pattern:

Next ques­tion: we want the return value of a bf-func to become the input argu­ments of the next-bf-func. But we seem to have an imped­ance mismatch: a bf-func only returns one argu­ment, but next-bf-func needs two argu­ments as input.

We can cure this mismatch with apply. The idea behind apply is simple: it takes a func­tion and a list of values as input, and calls the func­tion while using those values as input argu­ments. So these two expres­sions are always equiv­a­lent:

Our example stip­u­lates that func is a run-time func­tion—not a macro. In general, a macro can’t be passed as an argu­ment to any higher-order func­tion, including apply. For instance, and is a macro, not a func­tion, so it doesn’t work with apply:

To go back to our pseudocode example, since bf-func-result-list is a list of argu­ments, we can use apply to pass them to the next-bf-func:

Now that we have apply, we can add a key helper func­tion to our expander, called fold-funcs, that will be the engine of our bf inter­preter:

Our func­tion relies on for/fold, which we learned about in funstacker as a way of approx­i­mating state values with accu­mu­la­tors. Our fold-funcs func­tion takes two input argu­ments: apl, which is a list of a bf array and pointer—in other words, the return value of a bf-func—and a list of bf-funcs.  + apl = abbre­vi­a­tion for “array–pointer list”. Unre­lat­edly, there’s a fantastic program­ming language from 1964 called APL that required its own special font. Decades of ASCII doldrums would follow. But Racket supports Unicode throughout, so it’s once again possible to use funny symbols in a program­ming language.

When the for/fold loop starts, it creates an accu­mu­lator called current-apl to hold the current state of the bf program, and initial­izes it to the apl argu­ment passed as input. Then it iter­ates over the list of bf-funcs. On each pass through the loop, it uses apply to pass current-apl as argu­ments to the next bf-func.

As we remember from our previous use of for/fold, the return value of bf-func becomes the new current-apl value for the next pass. Once we run out of bf-funcs, the last value of current-apl becomes the return value of the for/fold loop, and there­fore the whole fold-funcs func­tion.

Back to macros

With fold-funcs in hand, we can now rewrite the macros from our imper­a­tive expander in a func­tional style. Nothing has changed in our parse tree. So our macros will be defined using the same syntax patterns we figured out before.

First we have bf-program:

We want to return code for two expres­sions. But a syntax object can only repre­sent one. In this case—or any time we want to return multiple expres­sions—we can consol­i­date them inside a begin.  + Unlike let, begin does not create a new scope for vari­ables—any vari­ables defined inside a begin are visible outside as well.

Then we set up our initial program state in first-apl. As before, our bf array is a Racket vector, and the pointer is an integer, and we’ll combine them in a list. We’ll pass this first-apl to fold-funcs along with our list of OP-OR-LOOP-ARG ... as the list of bf-funcs. As before, this macro should not return a value, so we’ll pass the result of fold-funcs to void.

Next we have bf-loop, which was simple in our imper­a­tive expander, but needs a little more finesse here. We observe two things:

The macro looks like this:

We can make an anony­mous func­tion with lambda, which works like define, except we omit the func­tion name.  + For more about lambda, see func­tions. A lambda expres­sion can be assigned to a vari­able, or used anywhere that Racket expects a func­tion:

In this case, our macro will return a lambda that runs another for/fold loop. As with fold-funcs, the loop will use an accu­mu­lator called current-apl that takes its initial state from the input argu­ments (combining arr and ptr).

We remember from how bf works that a bf-loop needs to continue indef­i­nitely until the current byte is zero. So our for/fold loop will iterate using in-naturals, which produces an unending sequence of inte­gers. Then we add a #:break condi­tion, which ends the loop when the condi­tion becomes true, to test whether the current byte is zero. (We haven’t made the current-byte func­tion yet, but we will shortly.)

Finally, we have our new call to fold-funcs, which feeds in our current-apl and list of argu­ments. fold-funcs will return a list with a modi­fied array and pointer, which becomes the value of current-apl for the next pass of our loop.

When the current byte becomes zero, this for/fold loop will end, and its return value will be the last value of current-apl. This, in turn, becomes the return value of the lambda func­tion.

Duuuude. That was the most super-duper-Rackety macro we’ve written yet. Don’t panic if it takes another read for every­thing to sink in. The big point is that we’re seeing how we can pass an array / pointer list not just “hori­zon­tally” from func­tion to func­tion (= what we did within fold-funcs) but also “verti­cally” by calling fold-funcs again within a loop. This tech­nique is called recur­sion. It’s a classic design pattern of func­tional program­ming, and ubiq­ui­tous in Racket.

In this case, the benefit of recur­sion is that we can totally avoid relying on external state vari­ables and muta­tion. The other benefit is that we can now relax—it’s all down­hill from here.

Our third macro is bf-op:

It looks similar to our previous bf-op macro, but rather than returning a self-contained func­tion appli­ca­tion like #'(gt), this version will return only the name of the corre­sponding func­tion (so that fold-funcs can apply a list of argu­ments to it).

Now we’re ready to add the func­tions that imple­ment the core bf array oper­a­tions.

(Re)imple­menting the BF array

Our array-imple­men­ta­tion func­tions will cover the same ground as before.

The current byte is the byte in the array at the loca­tion indi­cated by the pointer. So our current-byte func­tion just gets the value from arr at the posi­tion ptr using vector-ref:

Keeping with the func­tional idiom, our new set-current-byte will dupli­cate the input array with vector-copy, update the byte of interest with vector-set!, and then return this new array. In this case, vector-set! doesn’t count as muta­tion, because it’s just for internal house­keeping. What’s impor­tant is that we’re not using it to affect data outside the func­tion. (Consis­tent with Racket conven­tion, we remove the ! from the end of our func­tion name, to signal that it returns a value rather than relying on muta­tion):

Then we have the func­tions that imple­ment specific bf oper­a­tions. This time, rather than taking no argu­ments and returning no values, each func­tion will take two argu­ments—an array and a pointer—and return a list with a possibly modi­fied array and pointer.  + Require­ments for input and output values can be enforced less casu­ally with contracts, a topic we’ll cover later.

The gt and lt func­tions—corre­sponding to the bf oper­a­tions > and <—increase or decrease the pointer by one.

The plus and minus func­tions—corre­sponding to the bf oper­a­tions + and -—increase or decrease the value of the current byte. We can express these oper­a­tions in terms of current-byte and set-current-byte:

The period func­tion, corre­sponding to a . in bf code, writes the current byte to stan­dard output. As before, we use the Racket library func­tion write-byte to help out. Then we just return the unmod­i­fied input values:

Finally, the comma func­tion, corre­sponding to a , in bf code, sets the current byte to one read from stan­dard input. As before, we can do this with the Racket func­tion read-byte:

Our finished expander should look like this, with the new array imple­men­ta­tion high­lighted:

Testing our BF expander

Let’s confirm that our test file "atsign.rkt" still works:

Very good. How about our “Hello World” bf program?

Excel­lent. And the facto­rial gener­ator—

Every­thing checks out. We’ve success­fully converted our imper­a­tive-style expander into a func­tional-style expander. Again, in the case of bf it’s not neces­sarily the fastest approach. In fact, we prob­ably noticed that "factorial.rkt" now runs much slower.

The main point was to show that even a language like bf that relies on state and muta­tion can be imple­mented without them, by relying on func­tional-program­ming tech­niques. As we move toward languages with more complex inter­ac­tions, the clean­li­ness of the func­tional approach will pay divi­dends.

This will also be the last time we do an imper­a­tive-to-func­tional conver­sion. After this, we’ll just do every­thing in a func­tional style at the outset, avoiding state and muta­tion as much as possible (though keeping with our non-dogmatic policy, we won’t avoid it if it becomes neces­sary).

Can we make it faster?

Alan Perlis once quipped that “A Lisp programmer knows the value of every­thing, but the cost of nothing.” Meaning, the pursuit of func­tional purity can nega­tively affect real-world perfor­mance. In this case, we elim­i­nated state and muta­tion from our bf expander. But it got much slower.

Why? We could point out some small inef­fi­cien­cies, but the major bugaboo is our imple­men­ta­tion of set-current-byte:

The problem here is that memory allo­ca­tion isn’t free. Our input array arr is a large data struc­ture—30,000 bytes—so vector-copy has to allo­cate nearly 30K every time it’s called. That takes time. Also, because the old arr is never used again, it gets marked for dele­tion by Racket’s garbage collector. Garbage collec­tion happens auto­mat­i­cally as the program runs. As discarded memory piles up, the garbage collector has to run more often. That takes time too.

What to do? The simplest fix would be to avoid unnec­es­sary memory allo­ca­tion. We can do that by adjusting set-current-byte to reuse our input data struc­ture arr for the output:

If we make this update and try "factorial.rkt" again, it runs much faster.

Can we live with this change? Sure. We’re not here to be rigid about func­tional program­ming. The fact that bf relies on a 30,000-byte array is unusual. And throwing out 29,999 bytes every time we change one is, in prac­tical terms, wasteful and slow.

More­over, because each arr passed to set-current-byte is never reused, this change has no effect on the rest of the program. In all, it’s a tiny compro­mise with a clear benefit. Ship it.