The mental model for imperative programming is one of simulation. To understand such a program, one has to imagine discrete pieces of state and step through the code mentally and see how they change over time^[1].

This paradigm is formalized by the Turing machine, which in the artist's imagination looks like this^[2]:

But while programs are executed in Turing Machines, they are evaluated in the Lambda Calculus, which is the formalization for functional programming^[3]. Lambda Calculus is all about functions -- defining them with explicit arguments, composing them, and evaluating them through substitution, expansion, and reduction^[4].

Expressing computations as pure, side-effect free functions allows us to reason about our programs as equations, much like solving one on paper^[5].

Its elegance comes through to us in daily programming when using map and fold instead of loops and mutation, and when we prefer to chain together a series of pure functions to transform data rather than mutating them in-place imperatively.

So why can't we use more FP in our Ruby code? Any programming language that supports first-class functions (the ability to pass around functions as values) notionally supports functional programming. But affordance matters, and Ruby has poor affordance for practical day-to-day FP. Let me show you an example of one such missing affordance.

Linked Lists vs Arrays #

Enumeration in Ruby is functional (map, reduce, times etc.) and that style of programming percolates nicely to our own code as well. However the language doesn't have linked-lists and all collections are implemented using arrays. This limits us to using only the FP-esque functions provided by the standard library and prevents us from creating our own purely functional constructs.

For instance, in the FP model of computation, accumulation is done in this manner: the function recursively calls itself, and each time it returns a new list that includes the latest element. Remember that we're trying to write purely functional code which doesn't have the notion of state, and so can't rely on mutation for efficiency.

But it wouldn't work well in Ruby or Javascript, because they don't have native linked-lists, and instead rely on Array for accumulation. Here's a Ruby function implemented in this manner:

def map(array, &fn)
  if array.empty?
    []
  else
    me = yield(array[0])
    rest = map(array[1..-1], &fn)
    [me] + rest
  end
end

map([1, 2, 3]) {|num| num*10}

To be able to add an element to an array without mutating it, the runtime has to first allocate a new one^[6] and then copy over the elements from the original array. Thus an O(1) operation in a linked-list becomes an O(n) operation with arrays^[7], and it makes purely functional programming in Ruby unaffordable.

This approach however is eminently practical in functional languages because they have linked lists, which unlike arrays, are variable length structures. Pre-pending elements to a linked list is an O(1) operation because the language runtime can freely allocate memory from the heap for just the new element, and point its tail to the head of the existing list. This gives you a new list which contains the newly added element, while not mutating the existing list.

Languages exist in a spectrum -- one can program C in an object-oriented way^[8], but as a matter of degree, Ruby is more object-oriented than C. Clearly, some language features give more affordance to certain styles of programming, and some others take them away. In this sense, the absence of linked-lists in Ruby makes it more difficult to do FP, and the presence of pervasive mutation further decreases that affordance.

Syntax as affordance #

It is also possible for a language to encourage one style of programming over another by the choice of its syntax. For example, functional languages try to keep the syntax for defining functions, applying it, and passing it around as terse as possible. Here's a definition of map for Ruby, Reason, and Haskell:

## Ruby

def map(a, &f)
  if a.empty?
    []
  else
    x = yield(a[0]) 
    xs = map(a[1..-1], &f)
    [x] + xs
  end
end

map([1, 2, 3]) {|num| num*10}

/* Reason/OCaml */

let rec map = f =>
  fun
  | [] => []
  | [x, ...xs] => [f(x), ...map(f, xs)];

[1, 2, 3] |> map(x => x * 10);

-- Haskell

map _ []     = []
map f (x:xs) = f x : map f xs

map (\x -> x * 10) [1, 2, 3]

As you can see, the syntax becomes more light-weight as we go from Ruby, an imperative object-oriented language; to Reason/OCaml which is an eager typed functional language with mutation; and reach Haskell which is a lazy typed functional language where all functions are pure.

On the flip side, writing mutation-heavy code in Haskell will require more syntax and new mental models than it will be to write them in Ruby^[9]. OCaml takes a middle stand with "pragmatic purity", which is to say purity where it matters and dropping it (but with guarantees) to get some work done more efficiently.^[10]

---

1. Nygard and Dahl started work on Simula, the first object-oriented programming language, to simulate queuing systems and they demonstrated it in the original paper with airport check-in counters. Link: The Development of the SIMULA languages. ↩︎

2. This image is widely used on the web to depict the Turing machine, but the original source is unknown. ↩︎

3. Conal Elliot riffing on "Can functional programming be liberated from the von Neumann paradigm?" ↩︎

4. Lambda Calculus defines only composition and nothing else; but how can we do complex computations with composition alone? Prof. Graham Hutton shows how lambda calculus starts from this single primitive and builds a universe in this fabulous Computerphile video. ↩︎

5. "This post will walk through an intermediate example of equational reasoning to show how you can interpret Haskell code by hand by applying substitutions as if your code were a mathematical expression. This process of interpreting code by substituting equals-for-equals is known as equational reasoning." -- Gabriel Gonzalez, Haskell for all. Link to the full post ↩︎

6. Arrays are allocated as contiguous memory blocks and everytime one grows beyond its allocated size, the language runtime applies heuristics to decide how much more memory to allocate so that it can reduce the frequency of allocations, while not hoarding too much memory that might not be used. ↩︎

7. BuckleScript, the blazing fast OCaml-to-Javascript compiler used in ReasonML, compiles OCaml lists down into Javascript arrays by treating them like a linked list. Each list element becomes a 2-element array, where the first element contains the value, and the next element is a reference to the next element in the list. This makes equivalent functional code faster in Reason/OCaml than naive Javascript code which uses Array.concat. Javier Chávarri demonstrates this nicely here. ↩︎

8. Object-oriented Programming with ANSI-C ↩︎

9. Monads for functional programming by Philip Wadler, and Tackling the Awkward Squad by Simon Peyton Jones ↩︎

10. Thanks to Javier Chávarri for the sentence ↩︎