Programming in Racket #1

Over the last few days I have been learning Racket, a language derived from Scheme.  The main selling point of Racket is its extensive macro system that lets you do everything from the simplest macros through to redefining the entire language (yes you can even get rid of the parens!).  It is a programming language programming language. In fact, Racket is more of a customisable programming language infrastructure / engine with a default language on top of it.

Now, we won’t get to anything too crazy in this post since, well, the mental stuff I have wrote I’d not be happy to show you yet (there will be a little macro though!), but I have been working on the Advent of Code 2015 problems with an eye for attempting to discover the various language features and interesting things it has to offer - rather than the primary objective being to solve the Advent of Code puzzles. Here is some of what I have learnt so far.

Day 1

Day 1 of AOC has us help tracking Santa’s position in a lift.  This is seemingly a job for our good old friend fold.

As you would imagine, Racket has all the usual functional programming higher-order functions, but it also contains a boat-load of “iterators/comprehensions” (such as thisfor/fold) that allow us perform map, fold and friends in a variety of forms, using a shorthand notation.  These can be used to directly create the various in-built data types, such as sets, vectors, lists and dictionaries.

Nothing too crazy going on here, we fold over each character in each string, and create a single accumulatorlevelwhich is increased if the current character is a (, otherwise it is decreased.

Part 2 of this puzzle has us perform the same thing, but the requirement is to find out at what index into the sequence that Santa first hits floor –1

To achieve this, Racket allows us to simply add an additional accumulator to the fold, in this case calledindexwhich is increased on each iteration.  An optional break clause is added (nice!) which causes the fold to terminate early, as soon as the level is equal to minus one, leaving the index at the required value.

In this case we must always return 2 accumulator values.  Unlike most languages,Racket allows you to return more than one value (note this is different from something like F# which uses Tuples, it is still only returning a single value!).  One of the ways to achieve this is using thevalues function, as demonstrated here.

Day 2

For day two, those Elves need some help working out how much wrapping paper they need, and then how much ribbon they need in the second part of the puzzle.  Here we can try out some basic pattern matching, which comes in amillion different forms, all which can be nested in each other. 

Thematch-let* construct here is used to introduce local function bindings that can optionally use the vast variety of pattern matching functionality fromracket/match.  Each expression on the right hand side is matched with the pattern on the left.  You can see the first binding introduced in the functiondimensions matches on the parameterargs using thelistpattern.  My pattern expects three elements in the list to be present and will bind them tol,wand h respectively.

The subsequent bindings are not using any special pattern matching, in the normal format forlet, simply binding to the results of some mathematical functions using the previously bound values.  Note that this is possible because we are using the *’d version ofmatch-let (match-let*), else you do not have access to values that have been bound during the same expression.

Theribbon function is very similar, however since we need only the minimum two elements of the list to determine the length, theargs list is sorted as part of the matching expression input.

So far, without writing any macros, this is the closest I have managed to get to F#s’s pipeline operator.  The higher-order functionday2 uses thelet* function to introduce a series of bindings that shadow each other, using the data introduced from the previous one.  You will notice the second line uses a lambda function, the lambda symbol is optional and can equally be the much longerlambda keyword.

The second call to map has to explicitly callcurry in order to partially apply the innermap function with the functionstring->number.  Unlike F#, vanilla Racket does not have implicit partial application (for good reasons). 

Day 3

Santa needs our help to guide him around delivering presents.  At the end, we need to provide the amount of distinct houses we have delivered presents to.

Racket provides us with a fundamentalstructtype. It supports structural equality out of the box and also pattern matching support, as you would expect, alongside a ton of other stuff I am not going to talk about here.  The intend of this code should be fairly obvious, and also shows the use of the standardmatch construct that is used as a normal expression.  Here I have usedmatch-let first to de-structure the point into itsx andy values which are then used in the subsequence match to create a new point.

The next part is more interesting.  Since we only need to count each distinct location a present is delivered to, this sounds like a job for aset which Racket provides as a fundamental type from withinracket/set.  Like F#, attempting to add something to the set that already exists has no effect, and is perfect for what is required here.

A few new things introduced here, including something I omitted from the code above in part 2 of day 1. let-values is similar toletin that it introduces local bindings, with the difference being that it is especially designed to receivemultiple values that I mentioned earlier.  Since the fold here uses two accumulators, it ultimately returns two values (as opposed to, say, a pair or a list) which are then bound tocandvfor use within the following body of thelet.  This is a common pattern in Racket, with many functions having –values versions of them.

The rest is fairly straight forward, we fold Santa and his visited locations through the instructions, and at the end return the count of the set.

Part 2 is much more interesting, the arrival of RoboSanta means we need to keep track of two locations and alternate each instruction between Santa and RoboSanta.  An initial obvious solution is to simply add an extra location accumulator, and a flag that flips between iterations to determine how moves next.

However, I thought this would be a good opportunity to have a look at how Racket deals withstreams.  I would like to eliminate the flag based logic and instead return successive pairs of the input stream so that Santa and RoboSanta can be updated in lock-step.  It seems thegenerator is the tool for the job fromracket/generator.

A few new things here. Firstly the specialgenerator form will evaluate the body you give it, suspending afteryield is called.  In fact, this is basically a co-routine, something I will have to look more closely at later.  Other new things introduced here aredefine/match, which allows you do define a function that immediately matches on the parameters you give it.  In this case, I use thelist-restpattern to extract the first two elements asaandb with the rest of the list astail.  The pair ofaandbis then yielded viacons and the function is called recursively on the tail.

The last wildcard pattern matches when the list runs out, and returns(void). I am not sure if this is totally necessary, but when consuming this sequence using the functionin-producer it required you to give it an expression that determines when it should stop.  Omitting the data access code for brevity, the reformed version of the fold looks like this

Herematch-let* is used again to simulate a pipeline of data, first extracting and then moving Santa and RoboSanta, updating the visited location set and finally returning the accumulated data. It is about the same amount of code as before, but perhaps the generator will come in handy later!

Day 4

I am going to skip this since it was very easy and I didn’t learn much about the language other than how to create md5 hashes and bit masking.

Day 5

Santa is in a pickle working out which strings have been naughty and nice.  This problem obviously screams “regex!” but, frankly, regex can get in the sea. No one ever had fun writing regex. Instead I am going to do it manually, and as an additional target try to perform only one pass over each string and break processing early if a bad string is detected.

define/match is back on the scene to create some functions that match on multiple values (rather than lists).  Nothing new in the first function, however the second shows a new patternor being used inside the pattern match.  It could equally have been written with one pattern for each letter, but this is a tiny glimpse into the power of Racket’s pattern matching (which of course I know hardly any of yet)

I decided to track if a bad pair has been detected, count the amount of vowels and count the amount of occurrences for letters that appear twice.  Myby-pairs generator is no good for this, needing something more like F#’sSeq.windowed, I decided to simply pass along the previous character as another accumulator.

A couple of interesting things here.  If at any pointis-bad-pair? returns true, the fold stops on the next iteration due tobreak bad? clause. (Breaking Bad!) Lastly the perhaps slightly mysterious lookingmatch* at the bottom uses some new pattern matching forms.  ? allows you to pass a function which will be called on the respective value and only match if it returns true.  In this case I have inlined a lambda that matches if there are at least three vowels.  The last case uses thenotpattern to ensure at least one letter appeared twice.

Part two is much more sinister, and took me quite some time to come up with a nicer solution for it that didn’t have to do multiple or n2 iterations on the data.  Mostly because I had read the problem incorrectly, several times. The first part is easy, and will introduce another matching concept.  The string must have at least one occurrence of the same letter, either side of any letter. 

In Racket, if you use the same identifier to bind the results of patterns to, like I have done here witha,this meansthey must be equal. Otherwise it wouldn’t make any sense, would it?  In this case, it is simple to see if the same letter exists on both sides of some other letter. Very nice!

The second part is trickier.  The requirement is that the string must have at least two instances of the same pair of letters, but not where they overlap.  So “jkjk” is ok, “aaaa” is ok, but “aaa” is not. To fulfil this we can examine the next 3 characters in the string.  If they are all the same, we can add a pair of them to our “seen pairs” set, and then continue processing recursively,skipping the second character, which is critical to the algorithm skipping overlapping pairs.  All other cases of pairs are just added to the set.  In all cases, before adding to the set, we can check if the pair already exists, if it does then the condition is satisfied and the process can prematurely end.  The first version looked like this

This should all be familiar by now.  Again, using the rather nifty matching allows us to specify the case where 3 identifiers are the same, solves this with ease.  The thing I don’t like about this is the repetition of the code that checks if a pair s in a set, then recursively calls the routine again, adding to the set if not.  This code is basically identical in each case, other than the pair construction.  You could try and create a local function to help with this, but there is a better way.

Macros

The solution is to introduce a new piece of syntax that can write the repetitive stuff for us.  Like everything else in Racket,macros come in a million different forms, and are (or can be) lexically scoped.  I am going to use one of the many short-hand ways of writing a small macro,define-syntax-rule and have it scoped inside theauxfunction.

This very simple form defines a macro calledstep.  It expects two expressions as inputs.  Unlike a normal function, these are compile time constructs, and the input expressions here arethe program itself rather than data at run time.  The following body defines a syntax template which the macro expander will use to replace the call site.  Here I have simply wrote the same repetitive code, substituting the two bits of program I have passed in where applicable.  Now the function can be re-written as follows

Beware here that thedefine-syntax-rule form can be a bit misleading with its ease of use. It is also very limiting and to do the really powerful stuff you will want to revert to monsters such assyntax/parse which provides comprehensive pattern matching capabilities for program structure and composition.

Conclusion

I am liking Racket after messing around with it for a few days.  I did some crazy stuff not shown here with macros, and hopefully in following posts I will be able to cover more on building languages using the metaprogramming features Racket provides to do some cool (or completely ridiculous) things.