paper: "Purely Functional Structured Programming"

I am pleased to announce my new paper "Purely Functional Structured Programming", available at arXiv:1007.3023.

There are also resources accompanying the paper available here.

Feedback is very welcome, of course.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

neophyte/clueless/dumb question

i don't yet understand why shadowing is so exciting. i can understand there being some appeal to the cleanliness of supporting the linear scoping + shadowing, but i don't see that it is something crucial since usability-wise it might lead to code that is harder to read and thus maintain.

edit: i guess it is lead-up to punchlines about how loops and conditionals can be supported? maybe then i am the kind of person who is confused by having the punchlines so far away from the intro?

Shadowing by itself is not

Shadowing by itself is not very exciting (EDIT: but crucial). If you rule out shadowing because you think, well, it is no big deal; then you also rule out purely functional loops and other "nested-block" constructs. Yes, the punchline is a little bit far from the introduction; personally, I like it that way, because when I am told everything in the intro, why should I bother to read the whole paper? :-)

If I'm not interested in

If I'm not interested in reading the whole paper after reading the punchline, why should I? Isn't it more respectful to your readers to let them make that decision themselves? If you put the punchline in the introduction, the reader might decide that they just aren't interested, in which case reading the whole paper is not likely to change that and wastes their time; or, they might get your idea from the punchline and choose not to continue reading as the rest of the paper is useless fluff to them at that point and a waste of their time. If you can fit everything into the introduction, then what is the rest of the paper even for? To demonstrate your how superbly you can make a narrative? At any rate, putting the punchline late just wastes some of your readers' time and loses you readers who, for whatever reason (perhaps because they think there is no punchline) never get to the punchline. The remainder will read the whole paper regardless. A research paper is not a mystery novel.

Actually, I like a research

Actually, I like a research paper to be more like a mystery novel (with a resolution, of course). When I read a paper, I try to guess in what direction the paper will take me, so that I can have my own thoughts about the topic before they are presented to me.

So of course I respect the reader by giving them the best reading experience that I am capable of delivering. Of course, what is "best" might be subjective, so this is up to the author of the paper.

Respect goes both ways. The reader can decide if this is something he or she is interested in after reading the abstract. If the reader does not respect the author enough to read the full paper, why should the author care? I certainly don't.

Research papers are not novels

The author should care because the size of their readership is determined by how many people choose to continue beyond the introduction. For most professional readers (who have a large stack of possible papers to read) it is important to prioritise their time. The distribution of how far they get in particular papers looks somewhat like a pyramid.

For each hundred papers that I find that look interesting enough to skim the abstract I probably read ten introductions. After that I will probably read one full paper. If you want it to be yours then you need to convince me by the time I finish reading the introduction that your paper is the one in a hundred that is interesting and relevant enough for me to read.

Holding details back, hiding surprises and generally treating a paper as if it is some piece of art rather than a technical document will not do the author any favours. It is in their interest to make work as accessible as possible because in their career as an academic they are competing for mindshare. Filtering and excluding the audience will only damage an authors long-term career.

The idea that the reader "owes" the author some respect to read the full work is not compatible with modern science and the volume of results that are published every year. It is also incompatible with accepted standards of writing (e.g Strunk & White) and the simple ideal that the duty of a scientific work is to inform its audience as precisely and succinctly as possible.

Can we get back PL

Can we get back PL discussions now?


Wandered quite far off topic there.

I agree. I will answer PL

I agree. I will answer PL related questions/comments/critics regarding the paper gladly. Otherwise I will keep quiet. EDIT: For readers that prefer precise and succinct over everything else, I recommend to read section 3 (syntax of Mini Babel-17) and section 6 (operational semantics of Mini Babel-17) only.


In section 5, you give an example that mentions the need for a superfluous looking "val a = a". Why do you need that restriction?

What are the advantages over a monadic approach? One advantage is that, when you bind to a symbol, you're binding to its "current value". But you can do the same with monads with a little sugar. And an advantage of monads is that you also can reference the cell by name. So you can write a helper function that does something with the latest value in the cell.

Linear scope does not extend

Linear scope does not extend into simple-expressions. The reason for this is that once you enter simple-expressions, you don't have a fixed sequential order anymore for the evaluation of the components of the simple-expression. In

val f = a => (b => begin a=2*a; a*b end)

the (b => ...) constitutes a new simple-expression, and the linear scope of a does not reach into this simple-expression. By writing val a = a you start a new linear scope for a.

You can also understand it like this: For example in
val u = f 3
(u 5) * (u 7)
both subexpressions u 5 and u 7 would access the same "reference cell" for a and you suddenly have a race condition that depends on how the evaluation of (u 5) and (u 7) is interleaved.

One advantage over the monadic approach is that you don't have to define a monad :-) It is also simpler and reduces the amount of syntactic clutter to 0 (almost 0, if you count that "superfluous" val a = a). You can nest loops and blocks freely within each other and without any effect on the syntax of the inner nested loops/blocks.

One of the motivations is to draw the "mainstream" programmer to purely functional programming. The typical mainstream programmer has never heard of monads but will be able to make intuitive use of linear scope.

I understand the reason that

I understand the reason that you want to avoid letting linear scope extend into binary operators (you could always declare "left happens first", but I understand why you mightn't want to). What I'm asking is why you lump lambdas in with binary ops. Answering that they are both "simple expressions" just begs the question.

One advantage over the monadic approach is that you don't have to define a monad :-)

I think that's like saying that to do multiplication of integers you have first define a ring. You can implement the state monad without identifying the monad structure. In any event, I support the goal of making functional encodings of imperative programming more palatable.

What I'm asking is why you

What I'm asking is why you lump lambdas in with binary ops. Answering that they are both "simple expressions" just begs the question.

I think I answered that already in my previous answer.

Sorry, I misread your

Sorry, I misread your previous post as two separate examples. So the example is this:

val f = a => (b => begin a=2*a; a*b end)
val u = f 3
(u 5) * (u 7)

That makes sense. You're saying this code will produce an error in the definition of f, at a = 2*a?

The rule that I wanted would need to be: a new linear scope is implicitly created for each captured variable in a closure. I think there's some justification for such a rule if you consider the desugaring to be something like:

val f = a => (b => begin a'=2*a; a'*b end)
val u = f 3
(u 5) * (u 7) -- ok 2*3*5 * 2*3*7

The 'val' declaration wouldn't be so much for declaring linear scopes as for just declaring variable names. Does this approach have problems? It seems to me that if you're writing many curried functions, the current alternative would be moderately annoying.

That makes sense. You're

That makes sense. You're saying this code will produce an error in the definition of f, at a = 2*a?


The rule that I wanted would need to be ...

In principle there is no problem with such a rule, you could introduce it into the language, if you wanted to. There are already creations of linear scope in the language without the "val" keyword, for example in "b => ..." the "b" creates a linear scope, and in "for x in C do ... end" the "x" also creates a new linear scope. But in all of these cases, the linear scope of a variable starts right at the location of its declaration, and I would not want to deviate from such a simple rule.

Actually, comparing your

Actually, comparing your linear scopes to the more monadic-like approach I'm using suggests the rule: only allow mutation of cells defined with 'var x = ...'. I don't allow update of parameters like you do. Also, I have a mechanism for "passing cells by reference" which is really just monadic sugar. Anyway, thanks for clearing up my confusion.

I think there is probably

I think there is probably also a misunderstanding involved that I encountered a couple of times now from various people reading the paper. This stuff is not about how to do imperative programming in a purely functional style (that is what monads are used for), but how to dress purely functional code such that it looks like structured code. I guess that a lot of people would not want to do such a thing and therefore immediately arrive at the misunderstanding.

There are two reasons for wanting to do a thing like this anyway:
1. mainstream programmers have an easier access to the language
2. structured code often is just clearer and easier to read than functional code

I didn't really have that

I didn't really have that misunderstanding. I'm using monads* to give a purely functional semantics, but also choose macros* that present more structured looking code. This presentation is what resembles your linear scopes. Basically, we have similar front ends with different back ends (semantics).

* Not exactly, but close enough


Note that I'm a (mostly imperative) programmer but I still find that in section 4, the fact that the middle block of code is allowed to shadow the 'x value' after the end of the block surprising&confusing, even more that 'traditional' functional programming..

So I don't think that it's such a great progress, even if it's allow reusing imperative construct.

I am not sure what code you

I am not sure what code you refer to, do you mean:

val x = 2 
  val y = x∗x
  x = y

Here x = y is visible outside of the block (so that the whole thing evaluates to 8). That is the behavior for assignments in all languages I know that have imperative assignments, so I am not sure what you find confusing about it.


First thanks for your answer, then you're right that I missed that x isn't redeclared inside the block, but if it's possible to assign several value to x, why does x is declared as a val(ue) instead of a var(iable)?

Would this code below be allowed?
val x = 2
x = 4
If so I don't understand where is the difference between this and normal stateful programming?

The above code is allowed.

The above code is allowed. There are no "var" declarations in the language, only "val" declarations. It is called "val" because it binds names to values, as opposed to names to some reference to values.

val x = 2
x = 4

is equivalent to

val x = 2
val x = 4

(which is also allowed) where the second declaration shadows the first one.

For a lot of imperative-like code, there really is no difference. That is the nice thing about it :-)

The differences begin to emerge when you start doing things you would normally not do in languages like C etc. For example, an example from the paper is the function

x => begin 
       val y = x∗x
       val h = dummy => y 
       y = y∗y 
       (h 0) ∗ y

which maps x to x^6. In Scala you can write something similar with "var":

(x : Int) => { var y = x∗x 
               val h = () => y
               y = y∗y 
               h() ∗ y }

But there y really stands for a reference, not for a value. Therefore h will notice when called that y now refers to a new value, and therefore the above function maps x to x^8.

Another example that you would normally not write in C is

val x = 0
begin val x = 1; x end ∗ begin val x = x + 2; x end

In Mini Babel-17, Blocks have values too, so the above evaluates to 2. The code

val x = 0
begin x = 1; x end ∗ begin val x = x + 2; x end

is illegal, though, because x is no longer in linear scope in the assignment x = 1.

I hope this helps, but feel free to ask further if something is unclear, I am always happy to talk about this stuff :-)

EDIT: Of course another very important difference between Mini Babel-17 and the usual imperative languages is that because Mini Babel-17 is purely functional, you can only use persistent data structures like the ones described in Chris Okasakis "Purely Functional Data Structures".

Maybe related to naming

Thanks, I'll try to reread your paper again, maybe you could use ref(erence) as a keyword instead of val(ue)?

Having a proper keyword helps readability..

That would not be a good

That would not be a good renaming, because "val" really denotes a binding from names to values, not from names to references.

The confusion I have is that

The confusion I have is that your two competing constructs are "val x = ..." and "x = ...", both of which bind values to names. So "value" doesn't make much sense as the distinguishing qualifier. I'd suggest "def" or "declare", or you could have a pair of named constructs, "let" and "set". You could do alot of things, but I agree with renox that right now it's misleading to me.

"def" is already taken for

"def" is already taken for (possibly) mutually recursive definitions in Babel-17.
The name "val" is not supposed to be distinguishing. The only difference between "val x = 2" and "x = 2" is the scope within which the binding takes place. After actually programming a day or so in the language, you would probably think "how can it be any different?" :-)

EDIT: What is misleading and what not depends a lot on your personal context. For Standard ML programmers, "val" is a very natural keyword with respect to what its meaning in Babel-17 is.

Couldn't you move 'def' to

Couldn't you move 'def' to 'rec'? Anyway, this is surely off-topic. I agree with you that after you've used the language a bit, it will be second nature and you won't think about the name. That would also probably be true if the keyword was 'foo'.