Since I’ve dissed patterns and OOP recently (and rightly so) I thought I’d be a little positive and recycle an email I sent a friend a while ago. This someone was curious about functional languages after I had mentioned them over dinner as he had no experience with them. I absolutely think that if all you have ever used is an imperative language (exemplified by C++, Java, C# and other similar crap) I highly recommend spending (at least) several days learning a functional language. You’ll be a better programmer for it. (And why not learn some logic programming too, while you’re at it.)
What follows is a somewhat edited version of the 30-minute stream-of-consciousness crash-course email I sent to my friend. (So it’s not the best tutorial in the world, but hopefully it gets someone interested in playing around with a new language.)
Over the years I’ve played around with a lot of different functional languages (including Miranda, Standard ML, Haskell, FP, LISP, and Scheme). Here I’m using Standard ML (SML) because it nicely illustrates some of the cool concepts I wanted to outline (and other than LISP, is the one I know best). Haskell is another good choice for a first functional language and would be worth exploring in addition to SML, notably because Haskell features lazy evaluation (as well as several other important concepts).
To follow along, begin by downloading and installing an SML interpreter.
A smattering of SML
First, some fundamentals. In SML we bind values to variables using “val” and functions to variables using “fun”.
- val m = 42;
val m = 42 : int
- fun inc x = x + 1;
val inc = fn : int -> int
The “- ” is the prompt, so the rest of the line is what was typed. Note that as we type a line and hit return, the system interactively responds with a result on the following line. Note also how SML derives types automatically (known as type inference). “1” is an int and “+” takes two arguments of the same type (both ints or both floats) so “x” must be an int and therefore “inc” must be a function that takes an int as an argument and returns an int (“int -> int”).
The other thing we need to know is that SML natively supports tuples:
- val n = (1,2,3);
val n = (1,2,3) : int * int * int
Note again how it derives the types, using “*” to denote a tuple (or cartesian product if you prefer).
What I want to get to is one of the more powerful concepts of SML: the ability to define recursive data types, by cases. So, diving right in, let us define a binary tree data structure:
- datatype 'a BinTree = Leaf of 'a | Node of 'a BinTree * 'a * 'a BinTree;
datatype 'a BinTree = Leaf of 'a | Node of 'a BinTree * 'a * 'a BinTree
This oneliner(!) says that a data type “BinTree” that contains elements of type “‘a” (a special notation of a polymorph type; think templated type) is either (|):
- a “Leaf” of one element, or
- a “Node” of a 3-tuple, where the first value is a BinTree of the same type, the second value is an element of the type, and the third value is a BinTree of the type.
But more than that, we can now also use “Node” and “Leaf” as constructors to create a tree on the fly:
- val t = Node(Leaf(1), 2, Node(Leaf(3), 4, Leaf(5)));
val t = Node (Leaf 1,2,Node (Leaf #,4,Leaf #)) : int BinTree
Note how the SML interpreter prints the structure for us, but caps it at a certain depth (showing “#” to show it capped it).
We can also construct a tree with floats
- val u = Node(Leaf(1.0), 2.0, Leaf(3.0));
val u = Node (Leaf 1.0,2.0,Leaf 3.0) : real BinTree
which nicely shows how the data type is polymorphic (“type abstracted”). And again it derived the type (“real” as floats are called in SML).
We can now e.g. declare a recursive function “height” that computes the height of a BinTree using declaration by cases:
- fun height (Leaf(x)) = 1
| height (Node(lft, x, rht)) = 1 + Int.max(height lft, height rht);
val height = fn : 'a BinTree -> int
The first case (the first line) is that height is called with an argument that pattern matches “Leaf(x)”, i.e. something constructed using “Leaf” and with a single argument “x”. The second case is that height is called with an argument matching “Node(lft, x, rht)” where lft, x, rht are arbitrary variable names that will bind to the actual values in the supplied Node argument. In the first case, we just return 1 (as a tree with just a leaf has height 1). In the second case, we recursively compute the heights of the subtrees, take the maximum, and add 1. Again the system infers the type, saying height is a function that takes a BinTree of whatever type and returns an int.
We can try height now on “t” and “u”:
- height t;
val it = 3 : int
- height u;
val it = 2 : int
SML also has lists built in:
- val r = [1,2,3];
val r = [1,2,3] : int list
- val s = [4];
val s = [4] : int list
- r @ s;
val it = [1,2,3,4] : int list
The “@” is the built-in append function.
We can now e.g. write a function that takes a BinTree, visits it in depth-first order, and collects all the node values into a list:
- fun values (Leaf(x)) = [x]
| values (Node(lft, x, rht)) = (values lft) @ [x] @ (values rht);
val values = fn : 'a BinTree -> 'a list
(This function usually exists in functional languages, normally known as “flatten.”) And we can use it directly:
- values t;
val it = [1,2,3,4,5] : int list
Note how if we don’t bind the value, the system always binds the last result to “it”. We can use “it” directly if we want.
Now lets create a function “sq” that squares its argument, and we’ll “map” this sq function across every element of the list that is the flattened tree:
- fun sq x = x * x;
val sq = fn : int -> int
- map sq (values t);
val it = [1,4,9,16,25] : int list
“map” is a built in function that takes a function (of type “‘a -> ‘a”) and a list (of type “‘a”) and then applies the function to every element of the list. It is a very useful function that you can now find in a lot of languages, not just functional languages (e.g. in Python and several others.)
BTW, we don’t need to actually bind the function. We can create the sq function on the fly (a so-called lambda function) too, using “fn”:
- map (fn x => x * x) (values t);
val it = [1,4,9,16,25] : int list
And for the last example, SML also handles higher-order functions in the sense we can apply just partial arguments. To show this, first we define a function in two arguments:
- fun add x y = x + y;
val add = fn : int -> int -> int
Note how the type is “int -> int -> int” which is really saying that we have a function that takes an “int” and returns as result a function of type “int -> int”! We can see this is the case by passing only one argument to “add” and bind it to the variable “inc”:
- val inc = add 1;
val inc = fn : int -> int
Lo and behold, inc is a function, of type “int -> int”.
We can now use “inc” in e.g. the map function we used earlier:
- map inc [1,2,3];
val it = [2,3,4] : int list
Yup, it works!
To recap, these 4(!) lines of code implements a (templated) binary tree, declares an instance of a binary tree, and defines a function to compute the height of a binary tree:
datatype 'a BinTree = Leaf of 'a | Node of 'a BinTree * 'a * 'a BinTree;
val t = Node(Leaf(1), 2, Node(Leaf(3), 4, Leaf(5)));
fun height (Leaf(x)) = 1
| height (Node(lft, x, rht)) = 1 + Int.max(height lft, height rht);
How many lines of code do you need in C++ to do the same thing?!
In SML we can encapsulate the data type and the operations on it, just as is done with classes (objects) in object-oriented languages. In SML, such an encapsulation is called an abstract datatype (and created with the keyword abstype). I recommend following the link and reading about abstract data types if you are not familiar with them (and also reading the SML link at the top, to see how they relate to the module concept in SML). OO is not the be-all end-all of encapsulation if you ever thought that.
Edit: Based on a comment that was made (hi Vesa), I should mention that SML in addition has an advanced module system that can be used in preference of abstype. The point of mentioning abstract data types is that they’re an important concept (outside of their use in SML), so they are worthy of a study on their own.
In real life
Sadly, most functional languages are not industrial strength, in part because they never received industry financial backing (like Sun pushing Java, and Microsoft pushing C#). Functional languages in general lack IDEs, debuggers, libraries, and all those other things you need for real development, so the information provided here is mostly for expanding your mind and not for direct practical use. (Yes I know about F#, which is a commendable effort.) A notable exception is Erlang, which has been used and developed by the Swedish phone giant Ericsson (no relation) for many many years and is known to be very robust. This comparison between Erlang and Haskell is quite interesting. Overall, Erlang seems to be an up-and-coming language, which is cool, because we need something to break the dominance of the imperative crowd of languages. Erlang is also very interesting for its support for concurrency, which is highly relevant to this increasingly parallel world.
Further readings
Another few posts worth reading about learning more languages are Jim Tilander’s Are you bilingual and David Pollak’s Functional languages will rule. There’s also several quite good books available for learning more about functional languages (many free for the download):
- Armstrong, Joe. Programming Erlang: Software for a Concurrent World.
- Abelson, Harold. Gerald Sussman. Structure and Interpretation of Computer Programs. (Online version available here.)
- Nilsson, Ulf. Jan Maluszynski. Logic, Programming and Prolog (2ed) (Link is to online version.)
- Okasaki, Chris. Purely Functional Data Structures. (Or download Chris’ thesis for free.)
- O’Sullivan, Bryan. Donald Stewart. John Goerzen. Real World Haskell. (Online version available here.)
- Paulson, Lawrence. ML for the Working Programmer.
- Steele Jr, Guy. Common Lisp the Language, 2nd Edition. (Online version available here.)
Nice write up, IMHO Functional programming should used much more in the industry – or should I say functional concepts.
Since a while ago, I see a trend to write code in a functional style (immutable types, higher-order(-like) functions, ..) with object-oriented languages. The advantage is that, on does not have to worry about unwanted side-effects and thread-safety.
Another nice thing when mixing with OO and fun-style is that you can create public immutable types but allow private (safe) updates. A good example is the single-linked List( head : Element, tail : List). In a functional language with only pure-immutable types, prepending an element is easily done in O(1) but appending is O(n). However with some hidden mutations, you can create a still thread-safe List by appending single elements to the end in O(1) – of course the creation process itself is not thread-safe.
> How many lines of code do you need in C++ to do the same thing?!
5?
template struct BinTree { T t; BinTree *L, *R; }
template BinTree *Node(T leaf, BinTree *L=NULL, BinTree *R=NULL) {
BinTree *bt = new BinTree(); bt->leaf = leaf; bt->L = L; bt->R = R; };
BinTree *t = Node(2, Node(1), Node(4, Node(3), Node(5)));
int height(BinTree *tree) { return !tree->Left ? 1 : max(height(tree->Left), height(tree->Right)); }
“5?”
Nope, not the same code. Your tree — with just one node type — has pointers in the leaves, which the SML tree didn’t have. Recall there are basically as many leaves (N) as there are internal nodes (N – 1) in a binary tree, so your tree would require a lot more extra storage.
Your height function is broken too, btw.
Plus I see a lot of statements squeezed onto one line (which I don’t really mind, but still).
Good walk through. I’ve always wanted to try out a functional language, but have never found the time. A professor of mine was disappointed that no one in my compilers class knew scheme or haskell, so we developed a Java compiler instead. It would be nice if there were a data structures & algorithms course that at least touched on using functional languages.
Good overview. I’ve been mentioning this approach for a little while now too.
Unfortunately, we’re really missing the language “ecosystem” to program in this style in a production basis. I can tell you from first hand experience creating the ecosystem is not an option :).
In addition, functional programming has a dirty little secret: garbage collection. You just cannot enforce immutability without creating new objects constantly, and really you need to collect those old objects automatically.
That said, I think there’s an opportunity for a team to start R&Ding a tool-chain based on a functional language. It’ll be a big risk, but there are certainly benefits.
And secondly I think if you start describing this approach as “declarative” programming you might gain a little traction on the scripting side of things. Let your designers declare *what* happens, rather than *how* it happens. That sort of thing…
Just for the heck of it, here’s a correct c++ version:
template<class A> struct Leaf { A D; Leaf(A d) { D = d; } virtual int height() { return 1; } }; template<class A> struct Node : public Leaf<A> { Leaf<A> * L, * R; Node(Leaf * l, A d, Leaf * r) : Leaf<A>(d) { L = l; R = r; } virtual int height() { return 1 + max((L ? L->height() : 0),(R ? R->height() : 0)); } }; Node<int> t(new Leaf<int>(1),2,new Node<int>(new Leaf<int>(3),4,new Leaf<int>(5)));Not that much more code, but certainly not as readable.
[CE: Edited to make < and > show up correctly.]
I have a lot of admiration for you dear blogger but your immoderate hate for imperative language is getting ridiculous. If only bitching about them would change the face of the world… But other than that, I encourage you to continue advocating for alternatives.
Hi Solomon, I fixed the formatting. Of course, if we run your code through a C++ beautifier then what you squished into 5 lines become 26 lines with a more traditional formatting (and 20 lines if you use superior K&R formatting). Plus the C++ code is — in comparison to the SML code — completely unreadable.
supzi, first, what’s ridiculous is that I’ve never hated on imperative languages and you claiming I have. (But if you mean that I like to point out that C++, as an instance of imperative languages, is from hell, then try some more advanced languages for yourself and you might learn why.) Second, it takes getting a message out to instigate change; that’s what this soapbox is for (and not to gain popularity or admiration). If you don’t like the messages I’m sending and the way I choose to deliver them, feel free to change the channel!
Hi Christer, thanks for the format fix. I wasn’t trying to defend c++ syntax, I just did it for fun. If anything, my code makes your point.
I can understand the wish to make people get out of the box a bit and try something different in order to gain a broader view of things, but while you say that the example you give is much more readable in SML than C++ or other imperatives, I have to share something with you: for me it’s exactly the opposite :)
Regardless, I’m curious to know what the performance and compiled code size of something written in a functional language is. After all, games are quite performance-driven these days and I’d personally choose to live with C++’s madness (I’m used to it by now anyway) if that means my game runs smoothly. I think that, at least for the games industry, the only way to convince people to back up functional languages is to prove they can deliver the performance as well as the cool features.
Alex, how many hours have you spent with the SML syntax? In comparison, how many hours have you spent with the C++ syntax?
Here’s another argument why you should spend time learning more about functional languages. Concepts from functional languages are being copied into imperative languages. Don’t you want to know why?
The problem with buy-in for functional languages isn’t so much speed; you can see that e.g. ATS, an SML-like language, actually spanks C/C++ on average, and others aren’t far behind. (Now imagine what would happen if compilers for functional languages had as much attention as compilers for imperative languages.)
The problem is all those other things: weak IDEs and debuggers, overcoming inertia, etc. That, and people saying that C++ syntax is easier to read when they haven’t actually spent any time with functional languages! ;)
Ok, I see your point, although I still think that at a glance, a nicely formatted C++ block of class definitions is easier to navigate through than a single line with the same concept sqashed into it. I’m not afraid of typing more as long as it’s all good code :)
What’s nagging at me is that there has to be a price to pay for all this and it can’t be just the IDEs and debuggers.
I haven’t looked at functional languages before at all, I admit, and you did arise my interest, but somehow it feels like when I studied declarative programming back at uni (Prolog to be exact): it looked cool, it did some cool stuff, but I’m not using it at all now.
It’s not inertia, it’s a matter of convincing people there’s something better than the wheel. And there might just be, but is it better on every type of surface?
Anyway, job done I think since you convinced me to have a look at functional languages. But I won’t promise anything :P
Double post just to prove I am actually looking into it: I see declarative programming actually covers functional languages too so I should change my statement: I studied logic programming at uni as the course only covered Prolog.
I didn’t study in English so I’m only half used to the English terms ;)
Alex, I’m very glad to hear I’ve “bullied” you into giving functional languages a look!
One thing, do not go into it thinking “if I cannot use it right now or if it isn’t fast enough or doesn’t use a small amount of memory, it’s useless” but rather explore the concepts and ideas for what they are. Then consider “what if this was as fast as and used as much/little memory as C++, what could I do with this?”
Amen.
Functionnal programming takes a bit of learning but it is safer/clearer.
Until now, it was not an option, but the GHC performance (see the shotout) may change things.
Still, the industry is sooo conservative when it comes to languages…
Hey Christer. I hope you’re doing well.
Since you’re using SML for this discussion, for the benefit of those who are skeptical of the performance that functional programming languages can deliver, it may be worth pointing out MLton. It’s a whole-program optimizing compiler for SML that kicks some serious butt, if you can live with the rather dire compile times. People often think of OCaml’s compiler as a good example of an industrial-strength “real world” compiler; actually, it uses very few serious optimization techniques, whereas MLton really brings out the big guns.
I don’t know if it’s just because I haven’t done enough with functional languages or because I picked the wrong language to start with, but for me the best option always seemed to be to pick the right tool for the job – meaning in this case: use imperative languages (or language constructs) for problems that map well to them and functional methods for problems that fit well to them.
This post could also be the product of my current frustration with ocaml. :)
Or maybe it is my frustration with programming languages in general, as I have yet to find one that would just work for my needs.
A case in point:
I’m using (/trying to use) ocaml to analyze some data – the data is basically a multidimensional array of matrices, so it does not map directly to functional programming paradigm, but I think a good programming language should be able to deal with this directly.
So what I would like, is something like a function:
Array.create_tensor (dimensions : int array) (initialvalue : ‘a), that would result an ‘a array array array … array where all the entries contain my initial value and then I could proceed by filling in the array with values and access them with x.(i).(j)…..(k) – and no, I can’t use bigarray and I would like to use the array-access notation provided by the language core. Of course I could do this by creating a new type or class, but this sends me back to OOP or otherwise ugly constructs.
(Note btw. that my function is impossible in caml, as the return type is not fixed – ie. a ‘type array array is a different type from ‘a array, but this is an artificial constraint imposed by the language as the two are just tensors of different rank – the analog would be for the language to consider arrays of different lengths as different types)
Oh well, I guess I’ll just bite the bullet and create my own type for the tensor, but using it will not be as nice.
On the other hand If I were to code this in C I would know immediately how to do this.
Does anyone have suggestions how to solve this? Even the creation of an empty multidimensional array seems difficult in ocaml – at least you can’t do it with just one function and creating one function for each rank seems to beat the purpose of high level programming.
Since I posted a nigh-unreadable C++ version of BinTree, I thought I’d post a Python version that’s much easier on the eyes. This version is more general (I think) than the SML version, and arguable more readable, but it’s not quite as terse. Perhaps a Python expert could improve on it?
class Leaf: def __init__(s,a): s.A = a def height(s): return 1 class Node(Leaf): def __init__(s,a,c): s.A, s.C = a,c def height(s): return 1 + reduce(max,[c.height() for c in s.C]) t = Node(2,[Leaf(1),Node(4,[Leaf(3),Leaf(5)])])We are an indie game company that use OCaml as our programming language of choice. Even though the syntax is slightly awkward it allows you to program in an object oriented manner if you want to; making for a much smoother transition to the functional world.
Many tests show that compiled OCaml has a performance profile comparable to that of C++. The only concern I have so far, is how much we will have to fight the garbage collector in the end (as memory is automatically allocated and deallocated).
Functional programming and all that can perfectly be done in C++, you just have to use the right tools. It’s sad how C++ is so badly known.
The language is powerful enough so that you can do whatever abstraction you want as libraries.
Sum types and pattern matching can be done with a comparable number of lines using Boost.Variant, for example (the matching works with an overloaded functor, which might be more verbose depending on how you generate it). And that’s not really functional programming: it has nothing to do with functions.
Closures, treating functions as objects and manipulating them to create new ones, curryfication, etc. can easily be done in C++.
Parametric polymorphism is the same as C++ templates, which are actually more powerful since you can use SFINAE and overload them.
Writing inline functions can be done by using a DSEL for it (C++, thanks to expression templates, allow any DSEL to be defined). See for example FC++, Boost.Lambda, Boost.Phoenix v2, Boost.Phoenix v3/Boost.Lambda v2, from worst to best. The next C++ standard, due in a few years, has native syntax for it however (and some compilers already implement it).
You cannot infer argument types from a function definition, but SFINAE with expressions (and even raw function templates, since ML can’t overload anyway) provides similar functionality. Type deduction is of course present, however.
loufoque, read more carefully and you’ll see that my post was in two parts. The first one suggested people should step outside their C++-comfort zone and look into functional languages as a means of learning new, powerful concepts (and in a convenient way). The second part was an unfocused crash-course trying to show some nice bits of ML, enough to get someone who has never tried a non-imperative language to become interested in experimenting. The second part was not an attempt to justify the first part.
“The language is powerful enough so that you can do whatever abstraction you want as libraries.”
What is needed is not hodge-podge languages like C++ with do-it-yourself abstractions but languages that (a) have powerful higher-order abstractions built-in as first-class elements (or, at least, sufficient functionality that the libraries you talk about are indistinguishable from built-in ditto) and (b) don’t have side-effects so we can dig ourselves out of this pit of aliasing problems and sequentiality that C and C++ (and other pointer-heavy languages) have dug us into.
I’m afraid the boost stuff that you seem to love dearly I consider to be the foulest-smelling programming shite that’s been created this decade. Just because something can be done doesn’t mean it should be done!
Yes, C++ has sufficient functionality to implement anything as libraries without penalties from not being built-in. I already said so in my previous comment.
You can even implement array programming with the same efficiency as Fortran, or compile regexes at compile-time.
You’re not supposed to use pointers and aliasing in C++, but RAII, which is actually a way better programming idiom than garbage collection that is advocated as being the holy graal in all other languages, since it is deterministic, side-effect free, and can be used for any resource.
The ML family of programming languages is not purely functional, by the way, and their imperative model is based on garbage collection and aliasing.
Also, the functional programming style that you’re advocating is a recommended design to code in modern C++ and is nothing out of the ordinary for a developer who actually knows the right paradigms.
Boost is widely recognized as being the best C++ code out there. A lot of members of the standard committee are members of Boost, and several proposals for the standard come directly from Boost.
Boost also serves as a sandbox to develop new techniques within C++. They have democratized meta-programming and DSEL-programming, uncovering new fields within the language, and even the whole programming community.
It is in my opinion one of the only places where you can find decent libraries, it’s like the rest of the world can’t even code C++ correctly, which is sad.
I suppose game development is the place where you’d find the most horrible C++ code, so I’m not really surprised game developers don’t understand and are afraid of different (right) ways to do things.
Also, you’re saying that not because something can be done it should be done. But people have different needs, and having a minimal language you can code any abstraction in allows you to code the way you want and not be constrained by the limited set of functionality the language designer had in mind.
That’s a well-known good thing in programming language development.
Hopefully with the new C++ standard people will realize there is a lot they don’t know, even if what they will find to be new is nothing new at all. Simple things like concepts, which are mostly syntactic sugar, should make people use more generic programming, parametric polymorphism and structural subtyping.
loufoque, my crystal ball tells me (a) you’re a barely 20-year old student, who (b) have never worked on a real (non-academic) project in your entire life, and consequently (c) have no clue about what the real development issues are. Am I right?
First, there are huge penalties in language-implemented libraries over built-in ditto. These penalties include large increases to compile times, poor error reporting, and an inability to transparently step into data structures. In a real project, as opposed to hacking code in your dorm room, these become serious issues.
Second, “you’re not supposed to use pointers and aliasing in C++”, what crack are you smoking? Pointers, and therefore aliasing, are pervasive in C++; there is no getting away from them. Furthermore, your phrasing suggests you do not know what aliasing is and what problems aliasing cause. Hint: you don’t “use” aliasing — aliasing is endemic to pointer use, which is everywhere in C and C++.
Third, Boost recognized as “the best C++ code out there”, you are joking! It is the worst over-engineered shit that has been created by a bunch of people who are strong in theory but weak in practice and the realities of actual software development. I already mentioned what the problems are above; read my second paragraph of this comment over and over, until you actually understand what I’m saying.
One of the most important things that a good university should teach a computer science student is that programming is not about languages, but about data structures and algorithms. (And experiencing a lot of languages is a way to help people come to this realization on their own, thus my post.) Your attachment to C++ like it was your own mother’s teat suggests you have not yet understood this perhaps most fundamental tenet of computer science.
More importantly, what school does not teach you, but industry does, is that it’s not about programming but about delivering a successful product, on time and on budget. Constructs that obscure code-flow, increase compile time, hamper debugging, cause obscure errors, etc. are counter-productive and are best avoided.
Here’s the most important lesson I can impart on you: programming is a means, not an ends. I wish someone had not just told me that but made me listen, back when I too was a snotty know-it-all 20-year old, like you. You would be wise to take this hard-earned knowledge to heart.
I second that. I’m working in a huge game company that has plenty of C++ experts, we’re really pushing C++ to its limits and we evaluated Boost seriously. And it is seriously unusable. We don’t even use any external STL implementation, we had to roll out our own, because we found that other ones were way too overengineered for game use
“languages that … don’t have side-effects so we can dig ourselves out of this pit of aliasing problems and sequentiality that C and C++ (and other pointer-heavy languages) have dug us into.”
Christer,
Two quibbles:
1. No side-effects
Without side-effects, every object becomes immutable. This is not necessarily desirable for some objects (for instance, large arrays).
Consider having an array of 1000 things (implemented using pointers).
A quite basic operation is to “set” an element of that array to a new thing (if each element of the array is also immutable, this is required whenever an array element is modified in any way).
Without side-effects, this “set” operation has to copy the entire 1000 pointers, in order to modify one of them. This is highly inefficient in cases where you know that the side-effected version is safe. It also requires a 4000-byte memory allocation where none is strictly necessary.
So you can see why side-effect-free languages have never been accepted by working programmers.
I think the solution has to be to use functional style in the low-level, to enable great vectorization and other optimizations, and to use sequential side-effect style at the highest levels (e.g. “first do frame 0, then do frame 1, and maintain a database of actors”). In between,
it’s an open problem :) The entire issue of parallelization onto multiple threads occurs in this middle area. Avoiding contention here is an algorithmic issue and is not something a compiler can just solve for you by enforcing simple rules.
TBH, I think side-effects are an overblown issue with regard to functional programming.
2. No aliasing
I know LISP better than SML so what I say may not apply to SML.
LISP represents objects internally using pointers (although it may shove a small int into the same space too). These pointers are non-typed so there are no strict-aliasing-style guarantees. Therefore, all pointers in LISP must be assumed to alias, which is a larger set than in C++!
AFAICT pointers are endemic in all languages, you just don’t necessarily use pointer syntax. It’s a mistake to lay the problems of pointers onto C++ just because it’s the only language that supports objects which *aren’t* just pointers (i.e. in LISP, you declare a variable, and you’ve
declared a pointer and allocated 4/8 bytes of stack space – only in C++ can you say “actually I want this object allocated *directly* onto the stack). Please don’t turn a great feature of C++ into a putative weakness :)
The aliasing issues are caused by side-effects, not by pointers. Note that aliasing per se doesn’t matter – it’s hazards that matter – and hazards don’t arise when everything is const. So if you assume pure functional style in any language, aliasing is not a problem even in the
presence of pointers. But if you assume side-effects, aliasing becomes a problem, even in LISP. So I feel you’ve been a bit harsh on Mr Loufoque on this point. Pointers are really no more endemic in C++ than in LISP (and presumably SML?) And you can write code in C++ which heavily uses pointers but is none-the-less very friendly to the optimizer (i.e. they are all pointers-to-const).
In summary:
1. Side-effects are not a C++ problem. They are an essential feature which all useful languages offer.
2. Pointers are not a C++ problem. All implementations must use pointers for efficiency.
3. Aliasing is not a C++ problem. If side-effects are allowed, aliasing issues can arise.
In these terms, C++ and LISP are more alike than different.
Hi Eddie! LISP is very different from Haskell and other functional languages that fall into the camp of languages I referred to above. LISP, as you say, is not too dissimilar to C++ in terms of pointer use. Haskell (to name one) is a very different beast. (Probably the key distinction here is one of referential transparency. LISP and C++ does not have referential transparency. Haskell is for all intents and purposes referentially transparent, modulo some nitpicking. SML has pointers, and is not one of the languages that would be considered side-effect free.)
Anyway, as for your quibbles… some counterpoints:
1. Immutable objects in the language does not imply immutable objects in the implementation. I.e. compiled code of a purely functional language can (and do!) destructively modify data. That said, pragmatically we are likely to need side-effects at times, I agree. That is, after all, why e.g. SML has pointers. However, referential transparency still remains a very important and desirable property, even partially so.
2. Note, I did not suggest C++ alone has these problems! Anyway… you’re making some IMO nonsensical statements here. First, “AFAICT pointers are endemic in all languages, you just don’t necessarily use pointer syntax.” Clearly this is not the case! (Consider e.g. Microsoft BASIC.) Are you mixing up the language vs. what happens in the generated code somehow here?
Second, “The aliasing issues are caused by side-effects, not by pointers.” No! Aliasing is caused by pointer use, or, if you prefer, multiple references to the same data location. Side effects have nothing whatsoever to do with aliasing. (To see this, note that it is perfectly possible to have languages with side effects but that do not have aliasing.)
I think there’s enough inaccuracies in your statements (as argued above) that I’ll just conclude and say I do not agree with any of your summary points, other than in the sense that it is true that C++ is not the only language with these problems (but then again, I never suggested it was).
As for performance, I think it is pretty obvious that memory accesses is one of the largest performance bottlenecks we have today, and aliasing and lack of referential transparency are, I believe, by far the top causes of memory-access-heavy generated code. Today we have to manually resolve this problem by carefully crafting code to remove encapsulation abstractions through inlining of code, unrolling of loops, ordering data reads before data writes to remove chance of aliasing, etc. Going forward, I want a language where the compiler can do this all automatically. C++ and other pointer-heavy languages will never allow that to happen. They are the problem, not the solution!
Christer,
On point 1, yes, the compiler can analyze some cases and remove some copies, but this remains the fundamental issue regarding side-effect-free programming. I would prefer to control these cases rather than have the compiler do it’s best, especially when the data structure is very large. So languages IMHO “should” support side-effects.
On point 2, I’m obviously not expressing myself well, because you seem to be missing the point.
If the language allows me to have two references to the same object anywhere, then it is “using pointers”. Most languages allows this, so most languages have pointers. If you have language features which can *only* be implemented using pointers, then the language has pointers, whether it uses asterisk or not. So yes, maybe I am “mixing up” the language features with the implementation, but validly so! I would frankly be astounded if you could literally point me to a language which does not have pointers in this sense.
It doesn’t matter if a language uses pointers, if those pointers are const / the objects are immutable. No bad symptoms can arise. This is why pure functional languages (yes, those with referential transparency) are attractive to optimizers. In this case we can have pointer aliasing without any associated problems. Ergo, aliasing is not in itself a problem. (Another example: texture A must be used in samplers 0 and 1. Do you copy texture A first to avoid pointer aliasing? Of course not!)
When aliasing does matter is if either one of the pointers is non-const. Why? Because it introduces an implicit order dependency. On multi threads this may even require locks to implement. At the very least you lose instruction-level re-ordering. (OTOH, at the *worst*, all you lose is re-ordering optimizations. The code is still correct. Aliasing / side-effecting is purely an optimization issue.)
“Side effects have nothing whatsoever to do with aliasing. (To see this, note that it is perfectly possible to have languages with side effects but that do not have aliasing.)”
Careful with these bald statements Christer :)
An example of a language that has side effects but no aliasing is FORTRAN. *Because* it has no aliasing, side-effects don’t matter. As I have said passim, the problem is neither pointer aliasing alone, nor side effects alone, but the combination of them. I’m surprised to find you arguing about this because to me it’s completely obvious.
Simple table:
0. no side-effects + no pointer aliasing => no problems; but no language works this way AFAIK
1. no side-effects + pointer aliasing => no problems (e.g. some pure functional language)
2. side-effects + no pointer aliasing => no problems (e.g. FORTRAN)
3. side-effects + pointer aliasing => issues arise (e.g. C++, LISP, SML)
(Incidentally, FORTRAN compilers still have to deal with a form of aliasing – e.g. Array[i] and Array[j] with i == j – but not the nasty C++ form e.g. parameter Array == some subarray of parameter Array2.)
I apologize for any inaccuracies in my statements, but I don’t think you’ve identified any so far :) We might be looking at this slightly differently though.
PS: Microsoft VisualBASIC uses pointers endemically. Everything is a reference-counted COM object! The combination of side-effects and aliasing here means that COM objects using the apartment multithreading model must be externally protected when used with multiple threads, for instance.
A short reply as I have to go to work.
The reason you find me arguing is because you’re making statements that I find imprecise at best and wrong at worst. For example, “An example of a language that has side effects but no aliasing is FORTRAN.” Look up what the “EQUIVALENCE” statement does in FORTRAN. (It defines an aliasing relationship, by saying that two objects share the same storage location. That’s aliasing!) Perhaps you meant that FORTRAN, in general, does not have aliasing because the language standard — in the absence of EQUIVALENCE statements — defines there not to be any aliasing. Then sure! But language is important, and my brain-compiler has a very strict syntax check, and exits out at the first error!
The second thing I’m objecting to is that you still seem to be claiming that all languages have pointers in some form or another. Again, that to me is trivially false. But again, “language” (as defined by its BNF) is different from “implementation” (that which runs on a machine, virtual or not) in my book.
I find it very hard to get at the underlying message when the message relies on apparent statements that I deem false (whether or not I may actually agree with the overall message if I were somehow able to overlook the statements to which I object).
That said, I really don’t think there’s much of a disagreement here, other than your terminology not matching mine!
Addendum (since you snuck a comment in before I hit post): Microsoft BASIC is not the same as Microsoft Visual Basic!
I have to agree with three things stated above: (1) you certainly can do functional programming in C++, (2) no, it’s not the best high-level language for that purpose, and (3) Boost is arguably the worst thing to happen to C++ (and that’s only because C++0x is still a draft).
That all said, D is probably the most pragmatic (and useful) approach to layering functional semantics on top of a well-recognized and widely-adopted set of syntax and existing semantics, and that’s largely only because it’s (probably) a very small step to having good IDE and debugger support for it (in theory), compared to the more esoteric functional languages (all of which are probably better suited for the job).
In closing, anyone who expects to have the faintest hope of writing truly concurrent software needs to understand functional processing — they just don’t necessarily need to have to learn a new language to get it. ;) It’s mostly an unfortunate coincidence that C++ will happily let you shoot not only yourself, but your family and closest friends in their collective feet, when it comes to facilitating truly functional processing. But then, C++ was never meant to be functional, and until a very recent few years (months?) concurrent software development hasn’t been an issue. And at the end of the day, we’re all still developing software for Von Neumann machines. ;)
My $0.02
Hi Christer
The point about “all languages having pointers” is not that we have a semantic war but that since all implementations use pointers under the hood, all compilers have to deal with pointers. So there is basically zero benefit in saying “wow look at this cool language without pointers” when you know damned well that right there under the hood are pointers, pointers and more pointers, which the compiler has to analyze in order the optimize the code.
Equally, it’s easy to say “don’t worry, the compiler can figure out that your frightfully inefficient array copies can be removed” but a lot harder to demonstrate implementation code that will do this. For a start it is basically impossible to guarantee that any given array pointer is not being aliased in another thread (unless each thread has its own copy of every piece of data). Even if you are told this, you still need to analyze the loop that updates the array. In the general case, surely this looks *just* like alias analysis? So if the underlying implementation is restricted to the same basic technologies, can it really do better? It would be a shame if, just by changing a few characters in my source, an entire array copy was implicitly inserted. This seems worse than the equivalent situation in C++, where the code just can’t be re-ordered. This doesn’t seem good in a milieu in which bandwidth is king.
For my money, the mathematical elegance of functional languages is just kool-aid. Implementation is all that matters.
Anyway, back to work …
Eddie, you’re missing some fundamental stuff here. There’s a huge difference between the language exposing pointers to the programmer, and the compiler for a pointer-less language introducing pointers during the code generation!
In the former case the compiler has no idea about what aliasing is introduced by the presence of pointers and it has to do extensive alias analysis to find this out, and it only partially succeeds in this. In the latter case, the compiler knows exactly what’s being aliased because the compiler is the one that added the aliasing explicitly. That’s a huge difference and I can’t believe you’re not seeing it.
Also, consider a pointer-less language like Java. Thanks to the lack of pointers, in Java, a compiler is free to completely rearrange the storage order of member variables in a class. It can even do hot-cold splitting automatically. These are massive optimization opportunities! Had Java had pointers, like e.g. C++, there is no way in hell this would be realistically possible.
I think you’re smoking some pretty powerful stuff to claim that the presence or absence of pointers in the language makes no difference for the code generation!
Christer, maybe you should try some of what I’m smoking :)
Aliasing can occur just with arrays and indices. It has very little to do with pointers per se. It has to do with whether or not an algorithm must touch the same piece of data more than once. Whether that algorithm is expressed in a side-effect-free functional language using list comprehensions or an imperative language using pointers makes absolutely no difference whatsoever to whether or not that algorithm contains temporal references to the same logical piece of data. Functional, imperative … it’s all just programming. Your compiler won’t make algorithmic improvements for you.
Sure, we can make some progress by banning address-of being used on, say, local variables (although that’s easy to analyze) or struct members (more useful – the analysis of these is global). But we don’t get rid of the fundamental problem of aliasing. We just get rid of some of the more egregious and embarrassing instances of it. Don’t get me wrong – I’m all in favour of that – but it is simply incorrect to say that the compiler can infer everything about its internal pointer aliasing just because there is no pointer syntax in the BNF.
As for struct re-ordering … this is nonsense! If you have code that would break if someone went in and changed your members around, you’re using undefined C++ behaviour somewhere. This issue has less to do with pointer support than with the lack of typelibs in C++.
I do indeed claim that the presence or absence of pointers in a language makes no crucial difference for code generation, under the proviso that only pointers to heap blocks are allowed to escape a function (other pointers must be used entirely within the scope of the & operation which generated them). i.e. if a language with pointers uses them the same way a language without pointers uses them internally, there’s no essential difference, no.
Swords at dawn? :)
“If you have code that would break if someone went in and changed your members around, you’re using undefined C++ behaviour somewhere.”
Section 5.9.2 of the C++ draft standard (the n1905.pdf one) states:
This means that the following code is well-defined according to the standard
struct Foo { int a; int b; bool IsABeforeB() { return &a < &b; } }and swapping the order of the int declarations will change the value returned by the IsABeforeB() function, and that change in value is a well-defined behavior, contradicting your rubbish claim.
You keep making serious errors in your claims. I think you need to take a step back and refine your position a little. There are some valid points in your posts that I could agree with, but at the same time you're making these clearly-wrong statements which cast aspersions on everything you say, and I just can't let those slide. And you're making me feel bad for ripping into you, so sharpen up your arguments dammit and stop being so sloppy.
> Swords at dawn? :)
I've stabbed you through the heart several times already, but you refuse to die! :)
Sorry for my rubbish claim :) I didn’t realize how broken C++ was :) That’s so stupid and pointless I’m lost for words. OTOH &a without side effects. Show me your DAG node class without pointers.
Let’s have one last go at explaining my point. Consider a node structure in a tree (as in your article). Neither a C++ compiler nor a compiler knows what the “next” pointer points to. But it would be very nice to optimize across the “next” pointer lookup. If we could optimize across this, we could (say) have twice as many instructions before each branch, which is a win. But the only way to know that the “next” pointer doesn’t point to something we have cached in registers is to know that “this is a tree” (versus a general cyclic graph). This is the core of my point. Alias analysis isn’t “solved” by not having explicit pointers. It’s just made 5% easier. It still has the same total-failure cases. And the interesting stuff in alias analysis is not the shitty C++ examples where you can’t do anything, or my cross-language example where you can’t do anything, but cases where indices or pointer arithmetic are used in non-trivial ways that *can* be analyzed, so that inferences can be drawn and new optimizations can be made available. This problem is fascinating and we can expect progress over decades to come. And the key fact is: this problem is equally large in imperative and functional languages.
I think if I could mind-meld with you and put my position across you’d probably agree with it. Writing sentences in English … not so easy :) Don’t feel bad for ripping into me. In fact thank you for doing so because you’ve made me refine my position in my head, even if that’s not making into prose :)
Grrr frustratingly my use of < screwed that post up and the lost text isn’t in “view source”. Two paragraphs missing! Just take it as read that those were the paragraphs which would have convinced you :)
Also in the stuff that did get posted “nor a compiler” should read “nor a < functional language > compiler”.
Since you mentioned Erlang, I can’t resist mentioning Wings3D, which is an open-source 3D modeler written in Erlang by me and other developers in our spare time. It uses OpenGL for displaying the models, but all internal data structures, all commands, and user interface are implemented in Erlang. (It is a highly atypical Erlang application since it doesn’t use Erlang’s greatest strength – concurrency – at all.)
Reading some of the comments above, you might think that since Wings3D is not written in C++ it must be too slow to be useful, but in fact it is fast enough to be useful for doing real modeling, and has a relatively large user base (large, not huge as Blender’s user base).
The advantage of using a functional language is that you can get something working in a short time. If it is too slow you can use some of the time saved by using a functional language to optimize the program, for instance by using smarter algorithms (that might be too painful/time-consuming to implement in C). Also, it is useful much more enjoyable (at least for me) to optimize something that works than to find subtle pointer errors/memory leaks in a C/C++ program.
A functional language can also help with the allocation and deallocation of small objects/structs/records. To get the maximum speed in C/C++ you should use an array, but in a 3D modeler you don’t want arbitrary limits (on the number of polygons it can handle, for instance), so you will need to do dynamic memory allocation. Dynamic memory allocation of small objects in C/C++ done naively can be very slow (so typically, you will have to spend time on fine-tuning memory allocation using special-purpose allocators). Functional languages, on the other hand, usually handle small objects very well.
Christer,
Thanks for your great book which I bought recently. I thought that my calculation of the normal of a quad was a fast as it could get, but it turns out that I could save another 6 multiplications and 6 additions.
/Björn Gustavsson
Hi Christer & Eddie,
Interesting swash-buckling fun. :-)
Eddie, you mentioned that you had a problem with the pure functional use of arrays. Indeed, arrays and reference cells are very useful in a lot of circumstances, which is why languages such as O’Caml and F# supports them. The typical example is Haskell’s two-liner quick-sort:
Now, while really cool and instructive about the core of the routine, it fails to show that whereas the imperative qsort on arrays is not using (much) extra space, this version will use a lot of temporary memory! It is perhaps feasible for the compiler to reduce this to something like “only” twice as much memory as the input data, but I doubt any compiler analysis is that good.
Having said this, in a pragmatic functional language – they simply make it _harder_ to write imperative code (with side-effects), which is good – because in most circumstances, it is clearly not good for concurrency. The biggest stumbling block for making things run fast is breaking mutable data dependencies, so that you can run several tasks concurrently. In this sense, the functional memory model is near-perfect. Since “new” is so cheap (it amounts to bumping a pointer, causing a garbage collection cleanup when memory is full), combined with the fact that new data never mutates old data, you won’t have a problem with concurrency.
Consider making qsort() run on a number of SPUs in paralell. From the above, you can clearly see that you can run the two filters in parallel, so as long as we have cheap temporary memory, we can see that we can start two filtering tasks, each producing four filtering tasks and so on until the size of each array is small enough to be sorted (perhaps in-place in local SPU memory). Well, memory on SPU is cheap, so that’s essentially the best way to sort large things on PS3s (well, the best method is still radix-sort – but you already knew that).
Thanks,
PKE.
That code didn’t come out right.. How do you enter code?
[CE: I edited Pål-Kristian’s post above to include the correct code snippet. I kept this comment and my reply for those who might want to post code in the future, to know how to do so without the blog software eating the code.]
Bracket the code in < pre class=code > … < /pre > (without the extra spaces) and it’ll show up in a nice little code box! Or one can always email me the code and I’ll edit it into a post.