Object-oriented programming and algorithmic programming

I haven’t been writing the last two days since I was in Herning for a family birthday but I have been thinking about my Object-oriented programming in R book. Specifically, I have been thinking about algorithmic programming and object-orientation.

Most books I have read on object-oriented programming, and the classes I have taken on object-oriented programming, have centred on object-oriented modelling and software design. There, the focus is on how object-orientation can be used to structure how you think about your software and how the software can reflect physical or conceptual aspects of the world that you try to model in your software. If, for instance, you implement software for dealing with accountance you would model accounts as objects with operations for inserting and withdrawing money. You would try to, as much as possible, mapping concepts from the problem domain to software as directly as possible.

This is a powerful approach to designing your software, but there are always aspects of software that does not readily fit into such modelling. Especially when it comes to algorithmic programming and design of data structures. Search trees and sorting algorithms, for instance, are usually not reflecting anything concrete in a problem domain.

Object-oriented programming, however, is also a very powerful tool to use when designing algorithms and data structures. The way I was taught programming, algorithms and data structures were covered in separate classes from where I was taught object-orientation. Combining object-orientation and algorithmic programming was something I had to teach myself by writing software. I think this was a pity since the two really fit together well.

Polymorphism, a cornerstone of object-oriented programming, lends itself readily to developing flexible algorithms and to combining different concrete implementations of abstract data types to tailor abstract algorithms to concrete problems.

To which degree you would call this object-oriented programming I don’t know. It is more the polymorphism that is important — and polymorphic code is found in many other programming paradigms — but this book seems like as good a place as any to include topics like polymorphic code in designing algorithms and data structures.

When data structures and algorithms a taught in separate classes from, say, functional programming and object-oriented programming, you have to figure out how it all fits together yourself. In actual use, you have to fit it all together.

I don’t know if I am able to write about this in a way that makes the puzzle pieces fit together, but I will at least try to give it a go.

Project setup on GitHub

For my Data Science (programming) class the students have to make an R package for Bayesian linear regression. The plan right now is that they fork a GitHub repository, this one, and then follow the instructions there for making a pull request per student.

From that pull request I can see everything they push to their fork and I can comment and even modify their solutions.

All the weekly exercises are made using GitHub Classrooms, but I think this mix of forks and pull requests might be a better solution overall.

I will try both in the coming class and then pick the best solution for the string algorithms class in the spring…

More bindr

I extended my new bindr package a little today. If you recall it lets you assign to local variables from return values of functions, so, for example, you can use

f < - function(x, y) list(x = x, y = y)
bind(a, b) %<-% f(2, 3)

to assign to local variables a and b the values returned by the function f.

What I implemented today was a syntax for using variables returned by a function — if it returns a list or vector — in expressions for assigning to the local variables.

So now you can write code like this:

f <- function(x, y) list(x = x, y = y)
bind(a = 2 + x, b = a + 3 + y) %<-% f(2, 3)

You can combine positional arguments and expression like these, but probably shouldn’t. If you do, the position alone determines what you get assigned to, so

f <- function(x, y) list(x = x, y = y)
bind(a = y, b) %<-% f(2, 3)

will assign the value of y, 3, to both a and b.

The implementation is contained in the assignment operator and looks like this:

%<-% < - function(bindings, value) {
  if (length(bindings$bindings) > length(value))
    stop("More variables than values to bind.")
  var_names < - names(bindings$bindings)
  val_names < - names(value)
  has_names <- which(nchar(val_names) > 0)
  value_env <- list2env(as.list(value[has_names]),
                        parent = bindings$scope)
  for (i in seq_along(bindings$bindings)) {
    name <- var_names[i]
    if (length(var_names) == 0 || nchar(name) == 0) {
      # we don't have a name so the expression should be a name
      # and we are going for a positional value
      variable <- bindings$bindings[[i]]
      if (!is.name(variable))
        stop(paste0("Positional variables cannot be expressions ",
                    deparse(variable), "\n"))
      val <- .unpack(value[i])
      assign(as.character(variable), val, envir = bindings$scope)
    } else {
      # if we have a name we also have an expression and we evaluate that
      # in theenvironment of the value followed by the enclosing
      # environment and assign the result to the name.
      val <- eval(bindings$bindings[[i]], value_env)
      assign(name, val, envir = bindings$scope)
    }
  }
}

It is not terribly complicated. The only thing you need to keep track of is the environment in which to evaluate expressions, where I make one for the values given on the right-hand side, chain it with the calling frame (saved in the bind function call), and evaluate the expressions in this.

Fun with non-standard evaluation and binding parameters

I am thinking about examples for something useful but simple that can be done with non-standard evaluation in R for when I, in the far future, get to that book. And preferably something I can find a use for myself so it isn’t just wasted on writing but also helps me in my programming.

One thing I miss in R is assigning to more than one variable in pattern matching, or just for tuples or lists for that matter. So that is something I could start playing with. So I did, and you can see the first result on GitHub.

Right now it is just equivalent to tuple/list assignment in Python where you can assign multiple values like this:

x, y, z = 1, 2, 3

and you can use this for vectors and lists. Nothing fancy with pattern matching at all.

The syntax is inspired by the boost implementation of this in C++ and you use a function bind to specify the variables you want to bind and then an infix operator %< -% to assign to the binding.

bind(x, y, z) %<-% 1:3

I briefly considered overwriting the assignment operator, <-, because I just know that I am likely to write

bind(x, y, z) <- 1:3

in such expressions, but sanity prevailed and I left the assignment operator the way it is. It breaks all kinds of things that I cannot fully understand if I mess with it. So therefore a new infix operator %<-%.

The implementation is pretty simple. I just collect the parameters and the enclosing environment in the bind function and then put values in the environment in the %<-% function.

bind <- function(...) {
  bindings <- eval(substitute(alist(...)))
  scope <- parent.frame()
  structure(list(bindings = bindings, scope = scope), class = "bindings")
}

.unpack < - function(x) UseMethod(".unpack")
.unpack.default <-  function(x) x
.unpack.list <- function(x) x[[1]]
<code>%<-%</code> <- function(bindings, value) {
  if (length(bindings$bindings) > length(value))
    stop("More variables than values to bind.")

for (i in seq_along(bindings$bindings)) {
    variable <- bindings$bindings[[i]]
    val <- .unpack(value[i])
    assign(as.character(variable), val, envir = bindings$scope)
  }
}

(Sorry for the formatting of the %<-% name here, I don’t know why the highlighter absolutely has to replace backticks with code-tags, but it does).

The unpack helper functions are just there so I get the value when I have a list and not a length-one list. Otherwise, there is nothing much to it.

For my next trick, I need to figure out how I can bind variables by accessing the names in a value list.

Filter, Map, and Reduce

Just finished the next chapter in Functional Programming in R. This chapter covers the Filter, Map, and Reduce functions and the family of apply functions and a short introduction to the purrr package.

The chapters seem to be getting a little shorter here towards the end of the book, but there isn’t that much to say about these functions. I will think about it a little and see if I can add a little more, but I don’t feel like padding the chapter just to get its length up to the same size as the previous chapters.

I have thought about how to get the previous chapter a little longer. The continuation-passing-style is not that easy to get around mentally if you haven’t seen it before, so I think I will add another example to that section. I just need a good example to use. Will have to think about that.

Anyway, now that this chapter is drafted I will go back to working on Introduction to Data Science and Statistical Programming in R and get that edited so it is ready when teaching starts in two weeks.