Recurse.se Yada yada on Software Development

27Jan/120

Reducing Your Troubles

This entry is part 5 of 5 in the series Towards Functional Programming

In this post we’ll continue the refactoring of our now-a-bit-more-elegant Scheme code for doing reports in our hypothetical Gift Card scenario. We will discover another fundamental building block in the functional programming world, a function that takes a list, and reduces it to a single value, using an user provided reducer function.

Together with the list filtering function developed in an earlier post in this series, and the list conversion function in the previous post, we’ll see how our more generic functions can help rewrite a couple of twenty-line problem-specific functions into one-liners, showing off the composability of functions, and hopefully help you increase your understanding of functional programming at the same time.

Aiming for perfectionDarting the Obvious

Continuing our series of rewrites and generalizations, you notice that if you implement a date-minimizer called min-date you could also re-write oldest-used-here into a beautiful one-liner:

(define (oldest-used-here giftcards)
  (min-date (select issue-date (where used-here? giftcards))))

(min-date could internally use an earliest-date function, mentioned in the previous post, that would select the earliest date from its two parameters, but I’m not showing an implementation here)

However there’s something troubling you. Your refactoring-sense is tingling. While you’ve made good progress, you’re not quite there yet. You cannot quite put your finger on it, but there’s something you are missing. You are sure of it!

After a few hmm’s and ooh’s, and thatsnotit’s, you decide it’s the strange similarities yet differences between sum and min-date that’s bothering you. Both functions take a list of something (integers, and dates, respectively) and reduces this down to a single value (the sum, and the minimum date, respectively). Using this observation, could it then be possible to write a generic list-reducer-function somehow!?

After contemplating this insight for a while, you produce the following function in a burst of inspiration:

 1 ; the 'reduce' function turns a list into a single value using 
 2 ; a user-provided reducer function, and an initial seed value
 3 (define (reduce reducer current-value items)
 4   ; if there are no more items, return the current value
 5   (if (empty? items)
 6       current-value
 7       ; otherwise reduce the current value and the current item
 8       ; into a single value using the provided reducer function
 9       (let* ([current-item (first items)]
10              [remaining-items (rest items)]
11              [reduced-value (reducer current-value current-item)])
12         ; and recurse on the remaining items
13         (reduce reducer reduced-value remaining-items))))

(Notice that the reduce function didn’t need to define an iteration helper like we’ve used so many times now, as reduce already has all the parameters needed to simply recurse on itself.) Using the reduce function, you are able to re-write sum, and min-date as the following one-liners;

(define (sum numbers) (reduce + 0 numbers))
(define (min-date dates) (reduce earliest-date (current-date) dates))

I assume we have a current-date function, which is called without parameters to get todays date as a starting value for finding the minimum date. Obviously, if we are trying to find the minimum from a list of some future dates, “today” wouldn’t be a good starting value, would it. But in our given scenario we know we won’t have to deal with gift cards from the future (or will we, Mr. McFly?)

The value of uniformity

Also notice how in this example the sum function is able to use the addition function (+) in a way that for example C# cannot use its addition operator (+), as C# makes a language-level distinction between functions, expressions and operators, whereas these are interchangeable concepts in Lisp and Scheme, as well as in other functional programming languages, as it’s proven useful to be able to pass them around like this!

The Empty List This version of reduce can handle being called with an empty list (or “the” empty list, as it’s normally called, as there’s really only one such list in existence in Scheme) in which case the user-provided value of current-value is returned. You could omit the current-value parameter, and let the reducer instead start off by reducing the first and second elements of the list (instead of the initial value and the first element of the list) but then it wouldn’t know what to return in case we called it with the empty list. But it would be a tad simpler to use.

If we wanted, we could implement this variation as, say, reduce1, calling reduce with the first item of the list as the initial value, but it will need at least one item to reduce:

(define (reduce1 reducer items) (reduce reducer (first items) (rest items)))

Eh, Reduce Me?

Perhaps it’s not clear how reduce does its job. In the case of the sum function, the accumulator (current-value) starts off at 0 and is then updated at each iteration with the sum of itself and the current number from the list, using + as our reducer. (And when I say “update” I don’t mean modified – the accumulator is immutable – but it’s getting a new value when passed into the next iteration!) For a three-element list (1 2 3), and an initial value of 0, the reduction basically becomes:

(+ (+ (+ 0 1) 2) 3)

In the case of the min-date function, we start off at “today”, and at each iteration finds the minumum date of the accumulator (current-value) and the current date from the list (using earliest-date as our reducer). If the current date from the list is later than the currently earliest date found, the accumulator won’t be updated. If an earlier date is found in the list than we’ve previously seen, the accumulator is then updated to this new value, and at the end of the iteration through the list, we have found the minimum date! The reduction then becomes:

(earliest-date (earliest-date (earliest-date init-val first-elem) second-elem) third-elem)

And so on…

Where are we now?

Over the last three posts, you’ve now devised and implemented “where”, “select” and “reduce”, and hopefully learned how to pass around functions as parameters, to specialize the workings of a generic algorithm. Congratulations! These are powerful tools, and fundamental building blocks in the world of functional programming. Use them for good, not for evil! Understanding them is a milestone towards getting a FP mindset! You are likely to use select and where fifty times more often than you’ll use reduce, however.

You should also know that in most, if not all, functional languages these functions, and several more, are already a part of the standard library, but perhaps under different names. where is often called “filter”, select is often called “map” and reduce is often called “fold” (or “foldL”, where L for the fact that it reduces in left-to-right order, which sometimes matters). It’s also likely that these library functions are more advanced than our implementations, for example including error handling, as well as versions that can handle additional input lists.

I’ve chosen other names here than the standard Scheme ones, for several reasons:

  • increased clarity - at least in my opinion; ask someone what they think a function called “map” does, or if then believe a function that “filters” includes, or excludes the filtered items.
  • similarity to SQL clauses - many “non-functional” Microsoft-class programmers already know SELECT and WHERE from writing SQL-syntax.
  • similarity to their C#/.NET names (where they’re called Select, Where and Accumulate)

You should now be able to take over the world! Or at least, you won’t need to manually iterate through lists anymore, as these three functions should be able to cover most of your iteration needs for the next decade or two.

25Jan/120

Select Your Weapon

This entry is part 4 of 5 in the series Towards Functional Programming

In this post we’ll continue the refactoring of our less-than-elegant Scheme code for doing reports in our hypothetical Gift Card scenario. We will discover another fundamental building block in the functional programming world, a function that takes a list, and converts each element into a new form using an user provided conversion function.

Together with the list filtering function developed in the previous post in this series, and a simple list-of-numbers summer, we’ll see how our more generic functions can help rewrite a couple of twenty-line problem-specific functions into one-liners, showing off the composability of functions, and hopefully help you increase your understanding of functional programming at the same time.

Refactoring continued

In our previous post, we saw that in Scheme (or any functional programming language) using a function as a parameter to another function can be very useful, and helps separating generic behavior from the specifics needed for a particular situation. We implemented a generic list filtering method we called where, that let the user provide the filtering rules used by passing in a function that decides which elements to include, and which to exclude.

As you now have the useful where function, you can now redefine the sum-issued-here function (also introduced in the previous post) as a slightly more generic amount-summer-function plus the where-function to find the gift cards to sum. The amount-summer can be defined like this:

 1 ; sum the amounts of all gift card in the list
 2 (define (sum-amount giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (sum-amount-iterator remaining-giftcards accumulated-sum)   
 6     ; if there are no more gift cards, return the accumulated sum
 7     (if (empty? remaining-giftcards)
 8         accumulated-sum
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; get the amount from the gift card, and update the sum
13                [new-sum (+ accumulated-sum (amount current-gc))])
14           ;  and recurse on the remaining items
15           (sum-amount-iterator still-remaining-gcs new-sum))))
16   
17   ; call the helper function with initial values
18   (sum-amount-iterator giftcards 0))

It’s very much like several of the other functions you’ve written (and please see the previous post for a thorough explanation of the recursive iteration helper function). The difference from the original implementation is the fact that this function sums all provided gift cards, as you can now use a separate function to decide which gift cards to sum, which have greatly improved the composability of our functions. By composability I mean that we can compose (combine) them in several different ways to get different results.

We can now rewrite sum-issued-here simply as:

(define (sum-issued-here giftcards)
  (sum-amount (where issued-here? giftcards)))

using the one-line function issued-here? we defined in the previous post, to find us the relevant cards to sum. Now the sum-issued-here cannot become much simpler, but the oldest-used-here function (defined in the previous post, but basically finds the oldest gift card (the one with the earliest issue-date) used in a particular shop) is still in need of a rewrite. While we can use the where function to do part of the job, we cannot re-use much else. We’d rather not write yet-another similar function.

Further ideas for refactoringsThe Wrench Connection

You have a gut feeling that there’s more generic functionality waiting to get extracted, that would let you rewrite many of your previous functions. Thinking hard about this, considering the definition of the sum-amount and the oldest-used-here functions, combined with your new-found insight that it’s possible to parameterize a function with a different function (something we just put to excellent use in our where function), you come up with a few different options for further refactorings:

  • Write a more generic summer, where the property to be summed is controlled by a user-supplied function, for example; (sum-by amount giftcards)
  • Write a generic list converter, where the conversion is controlled by a user-supplied function, so that you could convert a list of gift cards into a list of issue-dates, or amounts.
  • Write a generic summer of a list of numbers, that could then be used to sum those amounts
  • Along the same lines, you’d need a date-minimizer, to find the earliest date among a list of issue-dates

After a short session of guru meditation, you decide a generic list converter function would be a most beautiful and useful companion to your generic list filtering function, as well as being more composable than sum-by, and thus you start with that one. You decide to name it the select function.

Select - A generic list converter function

Your implementation of the select function turns out much like many other functions in this series, based on the same recursive decomposition of the problem, first work in the current item, and then recurse on the rest of the items.

 1 ; the 'select' function converts each item in a list into a new form.
 2 ; the conversion is done by the user-supplied convert function! 
 3 (define (select convert list-of-items)
 4   ; our well-known helper
 5   (define (select-iterator remaining-items results)
 6     (if (empty? remaining-items)
 7         (reverse results) ; restore original ordering
 8         (let* ([current-item (first remaining-items)]
 9                [still-remaining (rest remaining-items)]
10                ; let the passed-in function convert each item into
11                ; a new form and preprend it to the accumulated results
12                [new-results  (cons (convert current-item) results)])
13           ;  and recurse on the remaining items
14           (select-iterator still-remaining new-results))))
15           
16   ; call the helper function with initial values
17   (select-iterator list-of-items empty))

This is an immensely useful function. It may appear just like many other, but you’ll use it time and time again when using functional programming techniques. I’d say it’s one of the most fundamental building blocks of functional code. You’ll use it to convert lists of item-IDs to item objects, using a database lookup function, or to convert from items to XML that you’ll write to a file, and many other things.

Pillow, pillow on the bed, will I ever rest my head?With this masterpiece done, do you pat yourself on the back? Do you take a well deserved nap? No, there’s no stopping you now, and you proceed relentlessly even though your eyes burn from lack of sleep, by re-writing sum-amount (defined at the top of this post) into a generic summer of a list of numbers.

After briefly considering the name ‘reginald’, you rename it sum. It really only needs a trivial change on line 13, to replace the call to the amount function with the current list element itself (and perhaps a few identifiers could use more generic names, as the sum function is no longer gift-card specific). You decide to spare the readers the sight of the actual implementation.

The revised implementation of sum-issued-here is more interesting:

(define (sum-issued-here giftcards)
  (sum (select amount (where issued-here? giftcards))))

This is quite beautiful! Using a few generic and very composable functions and your initial 20-line function has become a one-liner (ok, it’s a two-liner, but the line break is for readability, OK?) with the aid of a few helpers such as amount and issued-here? – also one-liners.

Step by step

The way this version of sum-issued-here works is that if it is called with a list of gift cards, we’ll call them gc1, gc2 and gc3, it will return the sum of the amounts of those issued in a particular shop nearby (as per our definition in the previous post).

  1. The list of gift cards is passed on to the where function that returns a new list, including only those gift cards for which the issued-here? function returns true. Let’s say that was true for gc1 and gc3, but not gc2.
  2. This list with gc1 and gc3 is then passed to the select function, that calls the amount function on each gift card, to extract their amounts into a new list that it returns. This list of amounts (well, plain numbers really) now contains say 250, and 175.
  3. This list of numbers is passed on to the sum function that sums it up into the number 425, which then becomes the return value of this particular call to sum-issued-here.

In the next post, we’ll try to finalize this refactoring session after discovering yet another useful function, so that we can move on to solve a larger and more challenging problem.

21Jan/120

Fun with Functions

This entry is part 3 of 5 in the series Towards Functional Programming

Now we are going to write some Scheme code in order to show off some features of functional programming. (As stated earlier, I’m actually using the Scheme-dialect Racket, but that shouldn’t matter too much for the discussion at hand.) We’re going to write some code, refactor it into more reusable parts, and hopefully become enlightened when we discover the power of passing a function as a parameter to another function.

Let’s write some code, already!

Let’s assume you are given an assignment to create a number of reports for a small retail chain, regarding the use of their Gift Cards. As a programming exercise you decide to do them in Scheme (since on-the-job training is something you have to do every now and then to keep sharp, right?)

Your Lambda Card, Sir!The base data you have is a list of gift cards; gift card ID, issuing store, date of issue, and amount. If the card has been used there’s also the using store, and date of usage. You decide that the first thing to do is to write a Scheme procedure that gives you the sum of all gift cards issued at a particular store, and then move on to more complex queries.

I’m going to skip some parts, such as how you would read your base data from a file or database. (As a side note, I’m using the words ‘procedure’ and ‘function’ to both mean the same thing; a “subroutine” of a larger program).

The resulting code turns out something like this:

 1 ; get the sum of all gift card issued by my store (id "SE1")
 2 (define (sum-issued-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (sum-issued-here-iterator remaining-giftcards accumulated-sum)   
 6     ; if there are no more gift cards, return the accumulated sum
 7     (if (empty? remaining-giftcards)
 8         accumulated-sum
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was my card, update the sum, otherwise keep it the same
13                [new-sum (if (string=? "SE1" (issuing-store current-gc))
14                             (+ accumulated-sum (amount current-gc))
15                             accumulated-sum)])
16           ;  and recurse on the remaining items
17           (sum-issued-here-iterator still-remaining-gcs new-sum))))
18   
19   ; call the helper function with initial values
20   (sum-issued-here-iterator giftcards 0))

I’ll try to explain what this code does. It’ll help if you do understand most of what it does. At line 1 we define a function called sum-issued-here that takes a list of gift cards as input. Then line 5-17 defines a helper function called sum-issued-here-iterator (which is not visible outside the definition of sum-issued-here) that does the actual work, and the helper function is then called at line 20 to give the result of the procedure. In Scheme, there’s no return keyword (or function). Instead the return value of a function is the value of the last expression evaluated. The same is true for most other scheme statements.

The workings of the helper function

The helper function is built on a very common pattern in functional programming; recursive decomposition. Here the problem is divided into two parts, first perform some work on the first element of a list (lines 13-15), and then recurse (line 17) to solve a smaller sub-problem (the work on the remaining items), until you reach the base case when the list is empty (line 7) which ends the recursion. In this case the helper is constructing the answer using an accumulator that is updated in each recursion, and then returned in the base case (line 8).

At line 10-13, we bind three identifiers to their values using a variant of let, called let*:

  • current-gc is bound to the first element of the remaining-giftcards list
  • still-remaining-gcs is bound to a list with the subsequent elements of the remaining-giftcards list (all but the first)
  • new-sum is updated, or not, depending on which store issued the current gift card. For simplicity, you’ve decided to hard code the ID of your nearest store, “SE1”.

The functions amount and issuing-store are property accessor functions for the gift card structure, they obviously return the amount, and the issuing store, respectively, for the provided gift card (their definitions are trivial and not shown). string=? and empty? are simple predicate functions (returning true or false) testing for string equality and the empty list, respectively.  The Spiral of Recursion

Note that we’re not actually updating any “variables”. Everything is immutable, and no values are harmed during the execution of these functions. It may seem like we update the accumulator at least, but in effect, a new accumulator is created at each step, based on the value of the previous accumulator.

You may suspect that this function could cause a stack overflow error if given a really long list, but that won’t happen. We’re not actually using up any stack space for our recursion, regardless of how many times the function calls itself. This is because the above helper function is tail-recursive, which in Scheme is as efficient as a standard iterative loop! So it is really pure iteration, coded as a recursive algorithm.

Your second report, and a Déjà Vu

You then continue implementing a completely different report function, one that should give you the earliest issue-date for all gift cards used in a particular store. When you look at the resulting implementation, you cannot help but notice that it is more or less identical to the previous one:

 1 ; get the earliest issue-date for all gift card used in my store (id "SE1")
 2 (define (oldest-used-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (oldest-used-here-iterator remaining-giftcards minimum-date)   
 6     ; if there are no more gift cards, return the minimum date found
 7     (if (empty? remaining-giftcards)
 8         minimum-date
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was used here, update the minimum-date, otherwise keep it the same
13                [new-minimum-date (if (string=? "SE1" (using-store current-gc))
14                                      (earliest-date minimum-date (issue-date current-gc))
15                                      minimum-date)])
16           ;  and recurse on the remaining items
17           (oldest-used-here-iterator still-remaining-gcs new-minimum-date))))
18   
19   ; call the helper function with initial values
20   (oldest-used-here-iterator giftcards today))

Really, the only differences are that it calls different functions in a few cases. These new functions should be fairly self-explanatory; using-store and issue-date are two additional property accessor functions for the gift card structure, and earliest-date is a “minimum” function for dates, and so returns the smallest/earliest of two dates.

Refactoring functionally

At this point, you are thinking that this probably could be refactored in some way, but it’s not immediately clear what kind of rewrite would let us share parts of the implementation for our gift card report functions. As a first rewrite, you decide that you could probably implement a separate function for the part of the first report that finds gift cards for a particular store, and returns a list of such gift cards.

This already filtered list could then be used as the input for a rewritten, simpler version of the sum-issued-here function you wrote earier, that don’t have to test each gift card for inclusion, and it could be used for several other report functions that do work on lists of cards issued “here”. But it won’t be useful for the “oldest-used-here”-function, as that one needs a list of gift-cards used (not issued) in a particular store (bummer!).

Nevertheless you write something like this:

 1 ; get a list of gift cards issues in my store
 2 (define (issued-here giftcards)
 3   ; define a helper function to recursively iterate over the list,
 4   ; building up the result in an accumulator
 5   (define (issued-here-iterator remaining-giftcards result)
 6     ; if there are no more gift cards, return the minimum date found
 7     (if (empty? remaining-giftcards)
 8         result 
 9         ; otherwise, process the current gift card
10         (let* ([current-gc (first remaining-giftcards)]
11                [still-remaining-gcs (rest remaining-giftcards)]
12                ; if this was my card, include it in the result, otherwise not
13                [new-result  (if (string=? "SE1" (issuing-store current-gc))
14                                 (cons current-gc result)
15                                 result)])
16           ;  and recurse on the remaining items
17           (issued-here-iterator still-remaining-gcs new-result))))
18   
19   ; call the helper function with initial values
20   (issued-here-iterator giftcards empty))

Now, where have I seen this before? Hey wait a minute! This silly silly function keeps repeating itself with only minor variations! This time the accumulator is also a list, and we’re using a function called cons which is the list constructor. It creates a new list by placing the current-gc in front of the (initially empty) result list. The biggest change is perhaps that we no longer try to get at a property of the gift card, and instead work on the gift card itself.

Your very own Lambda-shaped lightning boltAnd then, finally, enlightenment!

What happens next is that you, out of the blue, are struck by a lambda-shaped lightning bolt of pure functional enlightenment! It makes you feel great! Parenthesis suddenly seem like the best thing since curly braces, and prefix arithmetic now seems… less awkward.

You then suddenly realize, why oh why didn’t you see this earlier, that you could parameterize this damned function with another function! It’s just so obvious now! Then you could control what it actually does inside the loop, and have it dance to your tune! It no longer needs to be specifically for finding particular gift-cards, it can do anything, everything, mo ha ha ha!

After coming to your senses, you promptly rewrite it so:

 1 ; the 'where' function could probably prove useful, as its filtering
 2 ; behavior is controlled by the user-supplied predicate? function!
 3 (define (where predicate? list-of-items)
 4   ; our well-known helper
 5   (define (where-iterator remaining-items results)
 6     (if (empty? remaining-items)
 7         (reverse results) ; restore original ordering
 8         (let* ([current-item (first remaining-items)]
 9                [still-remaining (rest remaining-items)]
10                ; We're now letting the predicate? function decide
11                ; if the current-item should be included or not!
12                [new-results (if (predicate? current-item)
13                                 (cons current-item results)
14                                 results)])
15           (where-iterator still-remaining new-results))))
16 
17   ; call the helper function with initial values
18   (where-iterator list-of-items empty))

Now, this function is quite general and useful! It takes a list, and builds a new list containing all items for which the function passed in returns true. The ability to use functions like this, the same way you can use say a number (passing it as a parameter to another function, storing it in a variable, and returning it as a result from a function) is perhaps the defining characteristic of functional programming.

Note that as the list constructor function cons puts new items at the front of the list we need to reverse the result list as the last step, in order to keep the result in the same order as the original list, which seems like a good thing to do. It didn’t really matter in our earlier implementations.

Putting ‘where’ to work

You then write two simple one-liners; a predicate function issued-here? that checks if the provided gift card was issued at the “SE1” store or not, and another called used-here? that checks if the provided gift card was used at the “SE1” store or not.

(define (issued-here? gc) (string=? "SE1" (issuing-store gc)))
(define (used-here? gc) (string=? "SE1" (using-store gc)))

You can then use them together with your new where-function like this:

(sum-amount (where issued-here? giftcards))
(sum-amount (where used-here? giftcards))

to sum the giftcards issued, or used, at the “SE1” shop! Wonders upon functional wonders! This is the kind of code we’d like to write! Will you ever need to see a recursive helper function again, you wonder! In the next post, we’ll try to continue our refactoring of our Gift Card report functions, and show the definition of the sum-amount function used above.

12Jan/120

A Functional Language

This entry is part 2 of 5 in the series Towards Functional Programming

In this post I show the basics of the language Scheme, in order to be able to use Scheme in later posts to prove a few points on functional programming as a useful and powerful paradigm. Scheme is chosen for it’s simple syntax and minimalistic design.

Choice of language

I decided to start my journey towards understanding functional using F#, a new functional programming language from Microsoft. This was because it seemed like the perfect choice for someone like me who knew C# and the .NET Framework, as you can use .NET Framework classes from within F#, as well as easily call your F# code from C#, and vice versa. But I quickly began worrying that I wasn't doing it right, as F# is really a multi-paradigm language in which you can code in an imperative style, and I felt I was doing Frankenstein-style code (Frankencoding, if you will).

I therefore looked at other functional languages, that would not let me drift back into the imperative world so easily, with the intention of coming back to F# later. The weird looking syntax and terminology of Haskell really threw me off, and Erlang was also quite confusing. Lisp looked more promising, except for a bit of initial parenthesis angst, but it was when I learned more about Scheme, a beautifully minimalistic Lisp dialect, that I knew I’d found what I had been looking for!

Scheme schematics

I started toying with Scheme using PLT Scheme. (Since then that particular dialect of Scheme I’m using has been renamed Racket but it’s still “Scheme” for all our intents and purposes).

Key points about the Scheme language are:

  • Truly minimalistic design, meaning very few keywords and syntactic forms
  • Strongly but dynamically typed
  • Everything is either a value, or a list of values. The list is the primary data structure.
  • Functions are values too, and can be stored and passed around
  • As with all Lisp dialects, the code itself is list structured, as all statements are list-formed expressions
  • All statements are also expressions returning a value
  • All values are immutable (unchangeable), even lists
  • A powerful macro system for rewriting code at compile time

First let’s look at the syntax, and then we can elaborate on some of the other key points. The explanations of some things will have to wait until later posts, in order to keep this post to the point, but feel free to ask in the comments.

The Syntax of Scheme

This table summarizes most of what you need to know about Scheme syntax:

Concept Syntactic form Examples
Identifier ‹id› convert
bigger?
append-name
pos
Definitions ( define ‹id› ‹expr› )

Binds the identifier ‹id› to the value of the provided expression.

(define num 42)
(define powers (list 1 2 4 8 16))
Conditionals ( if ‹expr1› ‹expr2› ‹expr3› )

if expr1 is true, evaluates expr2 otherwise evaluates expr3

(if (empty? lst)
    (min num lower-bound)
    (max num upper-bound))
Local bindings ( let ([‹id› ‹expr›]) ‹body-expr› )

Binds one or more identifiers to the value of the provided expressions. The identifiers are visible only inside the body-expr.

(let ([a (random 10)]
        [b (random 10)])
   (if (> a b)
       "A was bigger than B"
       "B was bigger than A"))
 
Function calls ( ‹id› ‹expr›* )

When ‹id› is bound to a function, invokes that function with the value of the remaining expressions as parameters

(write-log "num is ~a now" num)
(sum 2 8 5 6) 
(multiply 2 (sum num 1))
(exit)
Function definition syntax ( define ( ‹id› ‹id›* ) ‹body-expr› )
binds the first id to a function which takes parameters named by the remaining ids, and the body-expr as the implementation
(define (max a b)
          (if (> a b) a b))
Anonymous functions ( lambda ( ‹id›* ) ‹body-expr› )

creates an unnamed function which takes parameters named by the ids, and the body-expr as the implementation

(lambda (a b) (if (> a b) a b))

And, yes, I’m skimming over some parts, but this will get you a long way. All these are also expressions in their own right - with the exception of the define form which returns no useful value - which means you can do something like in this silly example:

(define min/max (let ([num 3])
                  (if (negative? num) 
                      (lambda (a b) (if (> a b) a b)) 
                      (lambda (a b) (if (> a b) b a)))))

where min/max is defined as either a function returning the minimum of two values, or another function returning the maximum of two values, depending on the sign of num (and num is not visible outside the let). Note that whitespace and indentation is not significant in Scheme.

No operators, but there are always functions

You are probably used to writing expressions such as 1 + 2 * 3 * 4 + 5 / 6. where “operators” like + and * are “infix” (placed in the middle), between two sub-expressions.

In Scheme there’s no infix operators, as these operators are instead ordinary functions, and thus written in prefix form (placed in the beginning) just like any other function call in Scheme. The above expression then becomes;

(add 1 (multiply 2 3 4) (divide 5 6))

Or, rather, since the add, multiply and divide functions is actually named +, * and / (which are all perfectly valid Scheme identifier names), it actually becomes:

(+ 1 (* 2 3 4) (/ 5 6))

Yes, this feels awkward when you are used to the traditional way of writing expressions, but there are compelling reasons. This rule makes the syntax far more regular, if nothing else. And you may freely store and pass around these functions, just like any other value or function. In C#, even though you can pass around functions nowadays, you still cannot pass around the operators as if they were functions.

Note that prefix arithmetic like the above is a property of Lisp-like languages like Scheme, and has absolutely nothing to do with functional programming per se. So don’t write off FP just because prefix arithmetic at first glance seems like the dumbest thing since 7-bit ASCII!

Comparison operators are also functions

Using the same logic, comparison operators like ‘and’, ‘or’, <, >, and = are also functions, so you would write:

(or (and (> a 0) (< b 0)) (= a b 10))

instead of say (a > 0 && b < 0) || (a == 10 && b == 10) in C# or Java. (Note that and/or are really “special forms”, as they short circuit, and returns the last value that needed to be evaluated in order to determine the result)

Now I think you know enough Scheme to get your feet wet! Let’s fool around with it in the next post.

Tagged as: No Comments
9Jan/120

A Paradigm Shift

This entry is part 1 of 5 in the series Towards Functional Programming

I started out, like most programmers do, writing imperative code. In recent years, however, I have begun to understand the power of functional programming. By understanding the thinking from a different programming paradigm you can become a better developer, even if you don’t switch to a different language or framework. You can use functional programming techniques in C# or Java, and properly applied, they are sure to improve the quality of your code! This series of posts tries to explain why anyone would want to take a closer look at functional programming.

In the Beginning was the Code

The Emperor of the Imperative EmpireI first learned programming in BASIC on the Apple IIc in the mid eighties. Incidentally it was Microsoft that supplied BASIC for a majority of the popular home computers of the seventies and eighties, including both the Apple II and the C64, and it was selling licenses for Microsoft BASIC that made Bill Gates his first gazillons.

After many years of doing BASIC I then learned a couple of other languages, including C and some Pascal. I also tried to learn C++ on my own, but didn't get it until at university when I was taught object oriented design and development. I also learned a bit of Java. When I was employed I learnt Visual Basic and later C#.

… and the Code was Imperative

Superficially these languages are rather different from each other, but the common denominator for all these languages is that they are all imperative languages! “Imperative” comes from the Latin word for “to command” and this means that programs are constructed by setting up an initial state (a collection of variables with known values) and then executing a sequence of statements that manipulate the program state.   

A simple example would be calculating the sum of an integer array, which looks basically the same in any of these languages.

int sum = 0;
for(int i = 0; i < values.Length; i++)
{
    sum = sum + values[i];
}

Here, the program state is contained in the two variables sum (keeping track of the running sum) and i (keeping track of the current iteration index). Both of these are initialized to zero, and then updated in each iteration of the loop. The three different statements are clearly imperative (since they order the computer “Do that”, “Change this”), and modifying state:

  • declaration, allocating (and initializing) a variable
  • iteration, the for statement explicitly manages the iteration, allocating, initializing and updating the iteration index as well as checking the termination condition before each iteration
  • assignment, which change the assigned variable

Computer Hardware is Imperative

Most programming languages are imperative, because this is an abstraction that closely models the way the computer hardware works, where executing (imperative) machine code instructions changes the state of the machine (such as the CPU registers or memory contents).

Object oriented languages like C++, C# and Java improve this model by encouraging encapsulating and protecting most state inside objects instead of using a global scope, but are nevertheless imperative in nature, as they all emphasize changes in state. Indeed the point of most instance methods are modifying (or exposing) the object's internal state.

Introducing Functional Programming

The all-powerful Lambda

However, a few years ago I decided it was time to look at an entirely different class of languages, namely functional languages. Now, I’m not talking about functional as in if something works or not. The term “functional” is used because  of the emphasis on application of “mathematical functions”, instead of changes in state. I’ll explain some of the important differences between imperative and functional programming in a later post. The rest of this post is aimed at helping you understand why it could be interesting to know more about functional programming.

Higher productivity and quality

I had read articles like Why Functional Programming Matters, Beating the Averages and Lisp as an Alternative to Java, which all claim you can get higher productivity and quality using functional programming. Statements such as [functional programming] is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days from How To Become A Hacker was also intriguing.

All this made me interested in functional programming (or “FP” for short), but did not really help learning how or where I could apply FP techniques without learning a whole new language. It was still also unclear to me as what FP was all about, exactly. I just didn’t get it.

My curiosity was further prompted by discussions on FP with Adam Petersen, who I had the pleasure of working with for a few months when I was doing a consulting job using C++. I was looking at the usage of the C++ STL and boost libraries in the existing code base, and even though I knew C++ well (or so I thought) I still could not fully understand some of the impossibly terse and elegant code that Adam put out, much less write code like it, as it seemed to require a different way of thinking. It was not that it did something I couldn’t have written, but I would have written the same thing much differently, using at least three times the number of lines of code, in a manner that felt clumsy in comparison. Adam, of course, used functional programming techniques in C++.

No Assembly Required

I was at this point certainly interested in “getting” functional programming, as it now seemed clear it was worthwhile to learn, and useful even when not actually programming in a FP language. However, learning FP would not prove very easy! Learning the syntax of a new language is easy, learning a different way of thinking is much harder. I basically had to rewire the programming patterns etched into my brain by 25 years of imperative thinking, and learn new problem solving techniques using a fundamentally different way of thinking. My first attempts in using functional languages had a heavy imperative accent.

However, don’t start thinking that this FP stuff is much too hard, or that you will have to spend years and years until you finally get it. Yes, doing a cold turkey switch to a FP language without a mentor would probably be abysmal for your productivity, but the good news is that it is entirely possible to benefit from FP in smaller chunks than what I tried to bite off, and that you can get clear benefits from using FP within the comfort of your primary programming language (especially C#).

In the next post I'll try to elaborate on what it is, exactly, that makes functional programming so powerful, compared to imperative programming.