cdiggins.com

There seems to be a fair amount of confusion about how I could claim that a map function could have O(1) complexity. Maybe it might help if I show the psuedo-code:

class List {
  List(Object hd, Object tl) {
    head = hd; tail = tl;
  }

  List Map(Function f) {
    return new MappedList(f, this);
  }

  Object Head() {
    return head;
  }

  List Tail() {
    return tail;
  }

  Object head;
  List tail;
};

class MappedList : List {
  MappedList(Function f, List l) {
    list = l;
    fxn = f;
  }

  List Map(Function f) {
    return new MappedList(Compose(f, fxn), this);
  }

  Object Head() {
    return f(head);
  }

  List Tail() {
    return new MappedList(fxn, list.Tail());
  }

  List list;
  Function fxn;
};

Note that while the map functions for both lists have O(1) complexity, they create new lists for which head and tail access is slightly more expensive. This effect is cumulative. So the complexity of the complexity analysis of the whole program is going to be changed as a result.

A debate is currenly raging on at reddit.com on whether a lazy map is an O(1) algorithm or not, because of my previous blog post. I was surprised that it would be controversial, and to be honest I am a little shocked at how people seem to be throwing logic overboard. Consider the Haskell program:

let prog n = head (map (* 2) [1..n])

So is the complexity of this program O(n) because it has a map in it? It is in fact an O(1) program, because Haskell doesn’t bother evaluating the map over the entire list.

There is little disagreement about that, but the confusion arises about whether the complexity analysis of the call to “map” should be considered context sensitive. The answer is that the call itself is always constant, but it affects the complexity of other algorithms that use the output later on. 

This unfortunately means complexity analysis of a lazy program is non-trivial; we have to know the precise moments of evaluation and the details. List traversal, for example, will become non-linear if we call map N times.

Here is a fun puzzle to think about, what is the complexity of the following algorithm: “construct a list by calling a lazy map function N times, where N is the length of a list. Traverse the list N times.”. What are the assumptions of your analysis? What techniques can you use to further reduce the complexity?

An interesting feature of Cat is that it is partially lazy: evaluation may not occur if there is no reason for it. This allows for some fun optimizations that have been traditionally the domain of fully lazy languages like Haskell. One example is the map function. The map function takes a list and a unary function, it then returns a new list that would result by transforming each value using the function. For example:

>> [1 2 3] list [2 *] map 

stack: (2, 4, 6)

In Cat this function usually takes O(1) time because instead of iterating over all items, a new list object is generated. This list is a sub-type of list, and only performs the transformation as items in the list are requested. 

If you are interested in this and other similar kinds of lazy optimizations for C# there is a functional lists library in the Cat source code in the file CatFunctionalList.cs.

There was some discussion about a formal definition of first class values and first class functions at Lambda-the-Ultimate.org recently. Here is my definition of first class values: 

A first class value is a value which can be passed as a parameter to a procedure, returned as a result from an evaluated expression (e.g. function call), and constructed dynamically. A first class function is a function which is a first-class value. 

Informally a first class value shares the other common characteristics of values of the most fundamental types in the language (e.g. int, float, double, char, etc. in C) 

To use C as an an example, a function is missing two crucial properties to be considered first class. First it can’t be an l-value like any of the fundamental types: you can’t assign a function to another function, you can only assign references. Second you can’t create functions dynamically, you can only reference functions which have been declared in the source code. There is some confusion though unfortunately because pointers to functions are themselves first-class.

See also: Andreas Rossberg’s definition.

A recent assignment for a programming language semantics course as University of Montreal, was to implement an interpreter and type inference engine in Prolog for a small dialect of Cat. Woo-hoo!

A compositional programming language is a programming language where the sequencing operator (i.e. the operation denoted by whitespace) is the function composition operation.

This is my proposed definition for a class of languages, which have been referred to, with increasing frequency, as concatenative languages.

Some examples of compositional programming languages (according to the definition I’ve proposed) are: PostScript, Forth, Joy, Factor, and Cat. While most stack-oriented languages are also compositional languages, compositional languages are not neccessarily stack-oriented. Some non-stack-oriented compositional programming languages include: Enchilada and XY. These two languages are both self-identified as being concatenative. The term “concatenative” is frequently used as a synonym for compositional languages, but the definition of “concatenative” is not widely agreed upon.

The term “concatenative programming language” clearly conveys the fact that concatenation (or sequencing or juxtaposition) of terms is fundamental in a given language, but not to what purpose. In languages like Haskell and ML the concatenation of terms is fundamental, and denotes function application. The question then remains, are Haskell and ML concatenative languages? We can concatenate expressions in these languages, to generate new valid expressions.

Proponents of the term “concatenative programming language” generally would exclude Haskell and ML, and restrict the term to include compositional programming languages. I feel that this dilutes the usefulness of the term “concatenative”, because it is assigned an arbitrary implicit meaning.

I conclude by suggesting that the term “concatenative” is a bit too easily misinterpreted to be an effictive description of a class of programming languages.