My very first foray into software was copying a BASIC program from a blackboard and entering it into a mainframe via a DECwriter terminal way back in January 1981, a time when most people didn’t know what a computer was and even fewer knew how to write programs.
I was in high school at the time and I still remember that program today. It set me on the path to imperative programming.
As I progressed I learned more languages: Pascal, Fortran, Assembly and C. Then came the age of Object Oriented (OO) Languages such as C++, Java and, of course, Magik. But the key similarity in all these languages is you built programs as a series of steps that told the computer how to solve the problem.
Functional Programming
After high school I went on to major in Computer Science and concentrated on Artificial Intelligence. It was in one of these AI classes I was first introduced to Functional Programming (FP) via a language called LISP.
I did not like LISP.
It required a completely different way of thinking. Rather than instructing a computer how to behave, and specifically what to execute, this language had me building programs by composing functions and dealing with lists. It was a declarative language where you told the computer what to do and left the, how-to, details to the language and its libraries.
I liked imperative programming better.
Far better.
So much better, in fact, I gritted my teeth and did the minimum possible in LISP (and Prolog, but that’s another story) until I didn’t have to use it anymore. Then I happily went back to the imperative languages and forgot about FP.
Until one day I was reading about a FP language called Scheme — a LISP dialect. Of course my first instinct was to stop reading, but I continued because it mentioned an interesting procedure called, map(). That was intriguing.
Many years later, in 2011, JavaScript added map, along with reduce and filter, to the language and I started to see the benefits of functional programming.
OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.”
Michael Feathers
Conceptually FP allows you to write robust programs that are modular (with highly reusable functions) and simple to test. You generally don’t have to worry about side-effects, and functional programs are oh-so-easy-to-understand – they’re practically self-documenting.
Michael Feathers wrote, “OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts.”
FP does this by abstracting control structures and operations to minimize visible state mutation and thus minimize side-effects. Of course there is far too much about FP to cover in one article, but I want to give you a small taste of how FP concepts can help you write better Magik code.
Say what? Write better Magik code with FP?
Isn’t Magik Object Oriented? Doesn’t Magik lack functions? How in the world are we going to use FP concepts with Magik?
Ummm… to answer these questions… yes, yes and I’ll show you in the following paragraphs.
First, let’s take a look at what’s desired in a language to truly support FP.
- Obviously it needs functions.
- Functions need to be first-class citizens.
- Lexical Scoping has to be supported.
- Closures are good to have.
- Recursion is a must.
Okay, I’ll stop right there. Except for recursion, on the surface Magik doesn’t appear to have any of these features, so you would be justified in thinking Magik is not going to make a very good FP language… but you’d be incorrect.
While it’s true Magik is NOT a functional programming language (it’s strictly OO and imperative unlike, say, JavaScript, which is equal parts OO and FP, or LISP which is 100% FP), it supports everything I listed above — most people just don’t realize it. So there’s no reason you can’t benefit by using a mix of OO and FP techniques… because Magik has a not-so-secret weapon…
Magik’s Not-So-Secret Weapon
What Magik has going for it is the procedure.
As it turns out, the highly underutilized _proc() provides everything we need to mimic the important FP concepts in Magik (in reality procedures aren’t underutilized at all, just underutilized by Magik programmers. Procedures are actually used to implement methods under the covers).
Procedures can be passed to and from methods and other procedures (providing for higher-order procedures) and assigned to variables — thus making them first-class citizens in Magik (perhaps I should have titled this article, “Procedural Programming,” but that has different connotations — so I’ll stick with functions, but when you see me mention function or component, for Magik, think procedure).
Procedures can mimic lexical scope using _import and they support closures by being able to _import variables and parameters as well as return nested procedures.
And that’s really all we need to achieve significant benefits, because Magik procedures behave very much like functions in FP languages.
Sure, it’s not syntactically as nice to write FP code in Magik, but we can get around that by encapsulating the ugly parts in methods.
At a high-level we can describe FP as taking an input, passing it through a series of functions and returning an output. Any program, even a large and complex one, can be decomposed into a set of functions where each one takes an input, does some processing and returns an output.
Each function is relatively small, highly cohesive, does one thing well and has a stable signature. By combining these reusable functions in different ways, we create new programs. Plus, functions shouldn’t mutate state, so side-effects are minimized. And functions should completely encapsulate their exposed operations without showing how they are implemented or how they use data internally.
Wait a minute, you might be thinking, isn’t that what OO does?
Not exactly.
With OO programs you create new functionality by extending (or inheriting) from parent classes and writing methods that share state with other methods. So you’re exposing the internal workings of the parent class to its children and coupling methods within a class.
OO classes also mutate state as a matter of course (yes, I’m looking at you slotted_exemplar). Classes are also relatively large and when you throw in sub/super-classes, they quickly becomes unwieldy.
FP-OO
But don’t get me wrong. I’m still a fan of OO and it is very much essential when working with Smallworld. What I’m trying to convey is you can still use OO techniques, but combine them with FP, to make better, easier to maintain and more robust applications.
In fact, a melding of FP and OO creates a far better way of writing Smallworld applications because it inherits the strengths of both paradigms. FP-OO gains polymorphism from OO and referential transparency, immutability and statelessness from FP.
Both paradigms support data and behavioural abstraction and encapsulation (although FP do these better) and inheritance (although OO does this better).
Polymorphism allows us to define multiple implementations of a method and use the one that is relevant to the object we’re currently evaluating. Therefore we’re free to change that implementation without affecting any of the other implementations. In effect, it promotes loose coupling between similar methods (something not easily available to FP functions).
Referential transparency refers to the fact when we call a function with the same inputs, the same output is returned. You can view it as mapping an input to an output, because the function doesn’t depend on (or change) state outside its scope and therefore eliminates side-effects (so if you replace a function call with its result, you’re guaranteed the program’s meaning will not change) . This also contributes to its stateless nature.
And because functions should return new values, rather than mutate the values passed to them, immutability is preserved and that further reduces the chance of inadvertent side-effects.
So if we use objects to encapsulate state (as well as implement inheritance and polymorphism when needed) along with FP techniques to manipulate these objects at a higher level of abstraction, we gain the robust, declarative, easier-to-test, non-side-effects nature of FP united with the dynamic lower-level, decoupled polymorphic benefits and ease of inheritance from OO.
These benefits make our applications easier to test, simpler to change and faster to enhance. They also make applications predictable and easier to understand.
Okay, enough preamble… let’s dive into an example.
beeble_map()
Remember that map() function I found so intriguing. Let’s write it in Magik.
# BEEBLE_MAP:
_method ro_indexed_collection_mixin.beeble_map(p_callback)
_if _self.empty?
_then
_return _self
_endif
_local l_return << _self.new(_self.size)
_local l_indx << 1
_for e _over _self.fast_elements()
_loop
l_return[l_indx] << p_callback(e, l_indx, _self)
l_indx +<< 1
_endloop
_return l_return
_endmethod
beeble_map takes a callback procedure and iterates over _self applying the callback to each element. It then returns a new object (the same type as _self) with the results of calling the callback on each element in the original object. It’s very useful for processing entire collections of elements without having to deal with the underlying loops, indexes and scoping issues.
It’s written on ro_indexed_collection_mixin so it’s available on classes such as simple_vector and rope.
I’m going to use footpath objects to demonstrate FP concepts, so if you don’t have the Cambridge DB handy, here’s what one looks like.
footpath122:
:name unset
:class footpath_class(Cycle Path)
:length unit_value(length_value: 431.201 m)
:centre_line chain:(gis_id(55565186,1025390625,1112659))
:annotation unset
:seats select_collection(seat)
:walks a sw:db_set
And here’s an example using beeble_map.
Magik> v << gis_program_manager.cached_dataset(:gis)
gis_ds_view(Gis)
Magik> footpaths << v.collections[:footpath]
a ds_collection(footpath)
Magik> footpath_lengths << rope.new_from(footpaths).beeble_map(print_out_length)
249.393 m
687.355 m
27.435 m
19.993 m
113.337 m
39.316 m
43.485 m
305.081 m
139.631 m
485.424 m
87.864 m
457.339 m
262.545 m
298.709 m
580.847 m
68.033 m
234.037 m
414.225 m
423.421 m
355.774 m
269.381 m
144.252 m
431.201 m
1825.459 m
486.847 m
73.229 m
114.869 m
421.095 m
442.431 m
sw:rope:[1-29]
Magik>
Note how easy it is to read the FP declarative style of invocation (line 7). You can just about read it in English (“create a new rope containing all elements in the footpaths collection and print out each of their lengths”).
Here’s the callback procedure print_out_length.
_global print_out_length <<
_proc (p_current_elem)
_local l_length << p_current_elem.length
write(l_length)
_return l_length.write_string.as_number()
_endproc
It receives an element, passes the length message to the element, writes out the length and returns the length as a number.
Pretty simple, eh?
Yes… but that simplicity belies a great deal of power.
By separating the functionality from the loop, we created a loosely coupled relationship. And by encapsulating the functionality inside a function, we created a reusable component. In addition, by ensuring our function doesn’t change visible state, we’ve introduced statelessness and by returning a new object (rather than changing the one on which we invoked the beeble_map method), we’ve ensured immutability.
And we did this all in that very simple example.
You see, loops are hard to reuse because, in the imperative realm, they’re tightly coupled to the functionality they control.
Reusable components can be re-purposed multiple times to build larger components and, even, complete applications. Plus if you need to change an implementation or fix a bug, you only have to do it in one place. They also provide for a high level of abstraction, so you’re not bogged down in the underlying details.
Aiming for stateless components ensures you don’t affect global state and inadvertently break other parts of the code. In a nutshell, if you can avoid side-effects and state changes outside a function’s scope, your code will have fewer bugs and be easier to test, maintain and enhance. By viewing functions as black boxes that do one succinct piece of work and don’t mutate external data, you have the basic building blocks necessary to construct robust software.
These concepts are so important, FP gives these types of functions a special name: pure functions. Such functions depend only on their inputs. Given the same inputs, pure functions return the same results each time they’re invoked, and they don’t modify anything beyond their scope.
And when functions don’t have side-effects, you can invoke them whenever, wherever and as many times as you want without having to worry about breaking something else. It makes multi-threaded programming, testing, debugging, higher-order operations and understanding much easier (as I mentioned above, this particular attribute is called referential transparency).
Of course it would be impractical to write all Magik code as pure functions. Magik relies heavily on objects and the active record pattern, both of which rely on state changes that have far-reaching effects.
What I’m suggesting is to find the right balance between pure and impure components in order to minimize the side-effects in your code. Separate them, and if you have the option of implementing a pure function, do that rather than take the impure alternative.
Always look for ways to decompose your application’s requirements into purpose-driven functional components (where lower-level functions work on objects and are combined in higher-order functions to increase abstraction) and then recompose these components into an application that meets the requirements.
If you’ve done this correctly, the application will be easily understood from the meaning of its components — much like a sentence is understood from the meaning of its words (and a paragraph from the meaning of its sentences).
The other interesting feature you’ll notice from the beeble_map example is the use of chaining. If you look at line 7, in the example, you’ll notice the results of the new_from(footpaths) method are passed directly into the beeble_map() method — there are no intermediate variables. Chaining in this example was small, so if you blinked, you might have missed it. However let’s expand the example and see where we end up.
beeble_filter()
Like beeble_map, beeble_filter takes a callback procedure and iterates over _self applying the callback to each element (the callback must return true or false). It then returns a new object (the same type as _self) containing only the elements that returned true when the callback was invoked on them. Here’s the method written in Magik.
# BEEBLE_FILTER:
_method ro_indexed_collection_mixin.beeble_filter(p_callback)
_if _self.empty?
_then
_return _self
_endif
_local l_indx << 1
_local l_filtered_results << rope.new()
_for e _over _self.fast_elements()
_loop
_if p_callback(e, l_indx, _self) _is _true
_then
l_filtered_results.add_last(e)
_endif
l_indx +<< 1
_endloop
_return _self.new_from(l_filtered_results)
_endmethod
And here’s an example of it in use.
Magik> cycle_paths << rope.new_from(footpaths).beeble_filter(is_cycle_path)
sw:rope:[1-2]
Magik> print(cycle_paths)
rope(1,2):
1 footpath122:(940672)
2 footpath122:(1129380)
Magik>
In this example we’ve replaced the beeble_map() method with beeble_filter() and provided a new callback named is_cycle_path. Note how the declarative form makes everything easy to understand (“create a rope of all footpaths and only keep those that are cycle paths — i.e. filter out everything that isn’t a cycle path”).
Here’s what the new callback looks like.
_global is_cycle_path <<
_proc(p_arg)
_return p_arg.class = "Cycle Path"
_endproc
As you can see, it’s succinct and easy to understand. Now let’s generalize the callback so we can reuse it with other footpath classes (or any object that understands the class message).
_global beeble_is <<
_proc(p_class)
_return _proc (p_obj)
_import p_class
_return p_obj.class = p_class
_endproc
_endproc
This callback takes a footpath class argument and returns a procedure (which in turn takes an object argument and returns a boolean). It is also succinct and can replace is_cycle_path in beeble_filter() to achieve different results.
Magik> pedestrian_paths << rope.new_from(footpaths).beeble_filter(beeble_is("Pedestrian Surfaced"))
sw:rope:[1-24]
Magik> print(pedestrian_paths)
rope(1,24):
1 footpath122:(541250)
2 footpath122:(541256)
3 footpath122:(541266)
4 footpath122:(541274)
5 footpath122:(541282)
6 footpath122:(541290)
7 footpath122:(541298)
8 footpath122:(884831)
9 footpath122:(884839)
10 footpath122:(884852)
11 footpath122:(884858)
12 footpath122:(884869)
13 footpath122:(884891)
14 footpath122:(884897)
15 footpath122:(884910)
16 footpath122:(884918)
17 footpath122:(884926)
18 footpath122:(884932)
19 footpath122:(884940)
20 footpath122:(884951)
21 footpath122:(884959)
22 footpath122:(884970)
23 footpath122:(940866)
24 footpath122:(1129390)
Magik>
Again, the declarative nature of the chain is easy to comprehend. So let’s add a bit of additional complexity and see if anything changes. What if we wanted to find the length of all cycle paths? How would we do that?
Magik> cycle_path_lengths << rope.new_from(footpaths).beeble_filter(beeble_is("Cycle Path")).beeble_map(print_out_length)
431.201 m
421.095 m
sw:rope:[1-2]
Magik> print(cycle_path_lengths)
rope(1,2):
1 431.2
2 421.1
Magik>
See what I did there? I simply reused the callbacks and methods, we’d discussed in previous examples, and chained them together in a specific way.
And the declarative nature of the invocation still makes it easy to understand what’s going on despite adding to the complexity (“create a rope of footpaths from the footpath collection, find only the cycle paths and print out only those lengths”).
Pretty cool huh? Yep. But before we finish up, I’d like to introduce one last method.
beeble_reduce()
Like beeble_map and beeble_filter, beeble_reduce traverses _self and invokes a callback function on each element. However it keeps track of the cumulative value returned from each callback and returns the final cumulative value after all elements have been processed.
Here’s the Magik code.
# BEEBLE_REDUCE:
_method ro_indexed_collection_mixin.beeble_reduce(p_callback, _optional p_initial_value)
_if _self.empty?
_then
_return _self
_endif
_local l_indx << 1
_local l_accumulated_value << p_initial_value.default(0)
_for e _over _self.fast_elements()
_loop
_if e _isnt _unset
_then
l_accumulated_value << p_callback(l_accumulated_value, e, l_indx, _self)
_endif
l_indx +<< 1
_endloop
_local l_return << _self.new(1)
l_return[1] << l_accumulated_value
_return l_return
_endmethod
And here’s an example of beeble_reduce in action.
Magik> total_footpath_length << rope.new_from(footpaths).beeble_map(print_out_length).beeble_reduce(total_length)
249.393 m
687.355 m
27.435 m
19.993 m
113.337 m
39.316 m
43.485 m
305.081 m
139.631 m
485.424 m
87.864 m
457.339 m
262.545 m
298.709 m
580.847 m
68.033 m
234.037 m
414.225 m
423.421 m
355.774 m
269.381 m
144.252 m
431.201 m
1825.459 m
486.847 m
73.229 m
114.869 m
421.095 m
442.431 m
sw:rope:[1-1]
Magik> print(total_footpath_length)
rope(1,1):
1 9.502e+3
Magik>
And here’s the total_length callback code.
_global total_length <<
_proc (p_total, p_current_val)
_return p_total + p_current_val
_endproc
Notice this callback has 2 parameters. The first, p_total, accumulates the running total while the second, p_current_val, is passed the element that is currently being iterated over. The callback simply returns the sum of the two.
Once all elements have been visited, beeble_reduce returns the final value of p_total.
At this point, I’m pretty sure you know what’s coming next…
Magik> total_cycle_path_length << rope.new_from(footpaths).beeble_filter(beeble_is("Cycle Path")).beeble_map(print_out_length).beeble_reduce(total_length)
431.201 m
421.095 m
sw:rope:[1-1]
Magik> print(total_cycle_path_length)
rope(1,1):
1 852.3
Magik>
Does it get any easier to reuse code than this? I’ll leave that one up to you.
Alright, this has been a fairly long article, so let’s finish up with one last thing.
The callbacks used by beeble_map, beeble_filter and beeble_reduce all take optional arguments. The first is the index of the element currently being processed and the second optional argument is the object (i.e. _self) holding the elements being processed. Normally we don’t use them, however we can if we need to.
Suppose we wanted the average length of all pedestrian surfaced footpaths. How would we do that?
If you said, “write another callback,” then a great big no-prize is heading your way. That’s exactly what we’d do. Here’s that callback.
_global avg_length <<
_proc (p_total, p_current_val, p_indx, p_self)
_local l_total << p_total + p_current_val
_if p_indx _is p_self.size
_then
_return l_total / p_indx
_else
_return l_total
_endif
_endproc
What we’re doing here is including the optional p_index and p_self parameters along with beeble_reduce‘s required p_total and p_current parameters. We then keep a running total of the length, as usual, but check to see when we’ve processed all elements by testing to see when p_indx is equal to the size of _self. When that’s the case, we simply divide the running total by the number of elements (l_total / p_indx) and return that as the final value.
Here’s what it looks like in practice.
Magik> avg_pedestrian_path_length << rope.new_from(footpaths).beeble_filter(beeble_is("Pedestrian Surfaced")).beeble_map(print_out_length).beeble_reduce(avg_length)
249.393 m
687.355 m
27.435 m
19.993 m
113.337 m
39.316 m
43.485 m
305.081 m
139.631 m
485.424 m
87.864 m
457.339 m
262.545 m
298.709 m
580.847 m
68.033 m
234.037 m
414.225 m
423.421 m
355.774 m
269.381 m
144.252 m
114.869 m
442.431 m
sw:rope:[1-1]
Magik> print(avg_pedestrian_path_length)
rope(1,1):
1 261.0
Magik>
As you can see, we’ve simply replaced the total_length callback with the avg_length one to get the desired result. And the declarative nature makes it easy to understand what the chain of invocations does.
Earlier I mentioned the use of chaining, where the output of one method in the chain is fed into the next method. In functional programming this is known as point-free composition — because we’re eliminating points (in this context, a point refers to a low-level parameter) and joining methods each doing one small thing. The result is a style that makes code easier to read.
Go back and look at the code for beeble_map, beeble_filter and beeble_reduce. There are two important ideas to notice.
First, each procedure takes another procedure in order to specify behaviour (that’s why they’re called higher-order procedures).
Second, they are written in an imperative manner. FP creates black box functions to abstract away imperative-style programming. Under the covers, FP functions may mutate state and make use of impurity, but from the developer’s point-of-view they try to wall off impurity and expose pure functions whenever feasible.
But now that you’ve seen how Functional Programming procedures work under the covers, I’ll let you in on a secret not generally known to Magik developers: Smallworld already has these functions available out of the box (map is written on writable_indexed_collection_mixin, filter is written on ro_indexed_collection_mixin and reduce is written on basic_collection_mixin) so you can use them without having to load any additional code.
I know these are relatively simple examples, but rest assured you can use these same techniques to build very large and complex applications using map, filter and reduce with the appropriate callback procedures.
Of course we’ve only scratched the surface when it comes to FP and I’ll post additional articles in the future (because I just know someone is going to ask about performance issues related to using beeble_map and beeble_filter on large datasets. Yes Virginia, there is a way to write performant FP code).
At the end of the day, FP has many advantages over imperative programming and can be used nicely with Magik to make your applications more robust, easier to maintain and simpler to enhance.
