Daniel Jomphe

Understanding Dispatch

2009-06-18T00:00:00-07:00

Introduction

I believe multiple dispatch is known to be hard to understand. When I first read about it, for some reason, it took me quite a lot of thinking before I really understood it all. Now that I understand it very well, I find it odd that it felt so challenging at the time. For this reason, I wanted to try putting an end to this nonsense. There’s probably other articles out there that explain it very well today. In any case, here’s my take. As usual with me, it’s pretty wordy: I like to surround that kind of knowledge with lots of useful observations.

Before diving into the matter of the subject, I’d like to mention the areas where I’ve chosen conciseness or simplicity over exhaustivity or depth:

I have decided to always prefer the former over the latter, even when the latter would have made more sense to the knowledgeable reader:
- Compiler over interpreter.
- Class over type.
- Instance over its equivalents.
- Function over method and their equivalents.
I have also decided to omit mentioning in-place:
- Error handling.
- Rules ignored or handled differently by some languages.
- Extreme flexibility needs may warrant usage of reflection to replace static dispatch.

In any case, these omissions should be easy to spot.

Definitions

Function Dispatch happens when some code calls a function, and implies two phases – search and decide:
- First, a search is made for functions of the same name:
  - that are accessible to the caller,
  - whose parameters match the call arguments, and
  - whose return type matches the context of the call.
  - This search is almost always done at compile time. Thus, it’s part of static dispatch.
- Based on the results of the search, a decision is made:
  - If one and only one candidate is found, there’s no need to make any decision other than returning it to the compiler for its execution.
  - If there’s more than one candidate, then we’re in presence of polymorphism:
    - If the decision can be made during compile time, then dispatch makes it and returns the winner to the compiler.
    - Otherwise, if the compiler anticipates that the decision could be made during run time, then it makes provision for the eventual dynamic dispatch of the call.
  - Dynamic Dispatch is all about making a decision related to run time polymorphism. It has access to the results of the search made during the static dispatch. Thus, it decides which candidate should be executed depending on the run time class information available:
    - Single Dispatch pertains to the category of Object Oriented Programming where Classes own their functions. Typical OOP. Thus, the polymorphism in single dispatch is all about making sure the proper function of the instance’s class hierarchy is executed.
    - Multiple Dispatch pertains to what could be called a wider definition of Object Oriented Programming. Or, arguably, it’s the polymorphism of Functional Programming. To define multiple dispatch, let’s use contrasts:
      - Single dispatch is only concerned with the run time class of the instance to which a function belongs.
      - Multiple dispatch is concerned with the run time information of all the instance(s) to which a function is associated.
      - That’s it, and that’s why they’re called single and multiple dispatch.

Observations

Single Dispatch
- Classes define which functions they provide. They own them. Typically, the definition of each one of their functions is written inside their own definition.
- Thus in this model, classes rule.
- Closed. If you own the class, you own its future.
  - The owner will need to evaluate and decide if it’s wise-and how-to open the class properly for future evolution.
- Polymorphism is limited to happen only on the class of the instance of the function called, and nowhere else!
  - Thus, it’s the kind of run time polymorphism most programmers are used to.
- The associations expressed with this model are necessarily of cardinality 1 to N.
- Mixins still fit in this category.
- That’s typical OOP!
Multiple Dispatch
- Functions simply define which parameters they support as usual.
  - Each parameter may be expressed in a way to imply a run time polymorphism check.
- Thus in this model, functions rule.
- Closed. If you own the function, you own its future.
  - The owner will need to evaluate and decide if it’s wise-and how-to open the function properly for future evolution.
- Polymorphism happens everywhere and anyhow you want it!
  - everywhere: each parameter may use run time checks
  - anyhow: polymorphism is not limited in terms of examining the identity of an instance’s class. It may instead decide to inspect values, internal structure or metadata.
- This model may be used to express any kind of association: 1 to N and M to N.
- That’s very powerful functional programming!

Of course, some languages mix together the models behind single dispatch and multiple dispatch. This yields languages that feel more familiar to typical Object Oriented programmers, while keeping all the advantages of multiple dispatch.

Examples

Are they still needed to grok it? Well, I suppose they could help. …But they’re scheduled for later! If someone mentions me that the great set of examples I have in mind might be very useful, it might accelerate a lot my settling on writing them.

10 Reasons To Strictly Separate The V In MVC

2009-03-31T00:00:00-07:00

A few months ago, I spent some time researching better MVC practices. After discussing about it with my colleagues, I researched the following reasons why a business would want to strictly separate the V in MVC from MC.

Note that the following points are of course only true of a MVC app which started from day 0 with a V template engine that strictly enforces separation of V from MC.

V template engine easier and faster to learn
- No need to learn a (nearly-/fully-)turing-compliant language
- No need to learn best practices to avoid entangling with MC
V faster to write
- Impossible to write business logic in V
- Programming constructs easier to use
- Final appearance/structure easier to understand/visualize
- No need to review to make sure V avoids entangling with MC
V faster to maintain
- Impossible for V to introduce bugs in business logic
V more generic/general/reusable
- Each part of a template is more applicable to other apps
  - A template can be composed of multiple templates
  - Each purpose-specific template will look pretty much the same in different apps.
V more easily secured
- No control structures used
- No business logic in V
V easier to swap for a sexier V
- No business logic in V
V introduces 0 bugs in an app’s business behavior
- Only possible bugs are presentation-related
V can be written/maintained by designers (or others)
- See previous points.
V and MC can be written concurrently more easily and naturally
- See previous points.
Debugging faster than with traditional MVC apps
- All business-related behavior bugs are in MC
  - No need to look at V for business logic
- Proper MC design more emphasized
  - MC completely reflects the business logic

Consequently, I think it’s safe to say that with strictly-enforced separation of V from MC:

Developing a MVC application is faster
Maintaining a MVC application is faster
Evolving a MVC application is faster

Or, on a business point of view:

Developing, maintaining and evolving applications costs less.

A Practical Solution

Although it’s not yet as popular as some non-strict alternatives like Velocity and FreeMarker, StringTemplate is the most serious and solid strict V // MC template engine I know of. If you can integrate it in your projects, you won’t be disappointed:

Benefits of the strict separation are backed by formal evidence
- White Paper [pdf]
- My annotated version of the same White Paper [pdf]
Mature
- Many years of development, evolution and usage
  - started in 1999
  - public since 2003
Used in critical software
- ANTLR, one of the most widely recognized parser generators!
Used by important industry players
- Adobe (Flex 3)
- Jboss (Rules – Drools)
- Home Depot (a web site with > 500 000 hits per week)
- Oracle
- Squarespace, a publishing platform. Their templates are editable by thousands of bloggers/businesses.
  - “StringTemplate was PERFECT for this. We needed a system that would: (1) Be extremely fast/simple and (2) ENSURE that users can do nothing to harm our system.”
  - “[On the other hand,] Velocity would have been nearly impossible to enforce security with. There were numerous attacks related to invoking classLoaders by referencing getClass on random objects, not to mention that the very paradigm of the templates caused us to write code that did not strictly enforce view vs. controller, further resulting in code we had written that could have been insecure in many cases. It wasn’t just impossible to stop users, but also ourselves in many cases.”
  - This testimony is confirmed through its mention in the formal paper.
Capable of generating any kind of text (xml, html, css, java, etc.)
Powerful enough to express your needs in a V
- This addresses the common fear that a template engine might not be powerful enough for some needs.
- Evidence comes from ANTLR being able to generate parsers using it.
Code released under the generous BSD-3 license.
Implemented in Java
- Integrates with Spring MVC.
- Builds with Maven.
Ported to other languages
- Official ports: C# and Python
- Unofficial ports for your favorite language may exist.
Also available as a command-line tool.

http://www.artima.com/lejava/articles/stringtemplate.html

The Case For Functional Programming

2009-01-29T00:00:00-08:00

Comparing Different Language Levels

In this section, we will derive important conclusions from real life observations.

How To Reach Truthful Conclusions

To this avail, we need to pick someone very special.

Qualifications Of Yours Truly

Well, ehr, we can’t use me. Why? Because I’m a Java and C++ programmer. Because I’m no expert. Because I’m not used to any other kind of programming than what is called Imperative Programming. You know, although I certainly ain’t nobody, I’m still not too far from being your regular Joe.

Now, thinking of this, I know someone who’s not your average Joe at all. Yes, that’s right: we’ll pick him! This guy’s uniquely qualified to derive objective conclusions. Ladies and Gentlemen, allow me to present you the John Smith.

Qualifications Of John Smith

Why John Smith? Because, you see, John Smith is the only guy in the world who’s a complete expert of all the programming language dialects I’m going to use in this article. All of them, no trick!

More importantly and more impressively, John Smith learned those languages perfectly concurrently, and used them equally ever since. And yet, as if this was not enough qualifications for him, John has been spending 1 hour per working day since the start of his career in 1996, speaking about these different languages with his dozens of siblings who go by the same name as his’, but work in very different contexts. And guess what? They all share this very same background. They all think along the same lines as John’s. Can you believe it? Incredible, isn’t it?

Now, consequently, allow me to truthfully claim that John Smith is, out of any possible doubt, the very best person to help us reach meaningful conclusions about the fundamental differences of these languages.

Doesn’t it feel great to have John Smith with us to help us think this all through? Thanks John, I owe you one!

Natural Language – The Testbed

Now that we have introduced John Smith, let’s talk about the program we will use to compare our different languages.

John said any program could do, so for illustration purposes, this program will be a recipe I chose by asking Google’s first result for recipe, and clicking on two links. The first one led me to a deserts page, and the second one to the yummy-looking Blueberry Buckle. This recipe’s directions are what we will program.

Some English Dialect

For the sake of simplicity, I have inserted the ingredients and their measures right into their preparation directions:

Preheat oven to 375 degrees. Grease one 8×8 inch pan.
Cream together 3/4 cup sugar, 1/4 cup shortening, and one egg.
In a separate bowl mix together 2 cups flour, 2 teaspoons baking powder, and 1/2 teaspoon salt. Stir into sugar mixture, alternating with 1/2 cup milk. Stir in 2 cups fresh blueberries. Pour into greased 8×8 inch pan.
To make topping: Combine 1/2 cup sugar, 1/3 cup flour, 1/2 teaspoon ground cinnamon, and 1/4 cup butter. Sprinkle over cake batter.
Bake at 375 degree for 25-30 minutes.

Now, let’s see how this may be programmed. Please note that in the following versions of these directions, I have, out of pure laziness, left some functions undefined.

Declarative Language

Understanding the concept of declarative programming is useful to see the simplicity of functional programming, since the latter is a special case of the former. Therefore, the following definition should help.

One could think of a declarative language as one which expresses computations as a hierarchy of result descriptions.

Following this line of thinking, functional programming expresses computations as a hierarchy of function applications, where each function produces a result.

When a programmer uses the functional style, he is mostly concerned with defining and combining functions and their applications.

Since the mechanism of function application, or in other words, function call, is universally known, functional programming is far from being inaccessible. And that’s precisely what might come as a surprise to one who has heard that functional programming is a weird way of thinking of the process of writing software.

Before we ponder onto why and how we’ve got to think that functional programming is weird, let’s dive into a few declarative languages to see how they look.

Note that I have taken the liberty to personalize their syntaxes so that they read more easily to the eyes of a java-like language programmer. Therefore, please try not to reason too much about the meaning of how the parenthesises are used. The code examples are not there to help you learn these languages. They’re rather there to help you see more quickly the fundamental semantics of each language. The biggest changes I’ve made was adding a bunch of parenthesises that should not be where they are, and removing some others whose placement would have felt awkward to any java-like language programmer.

Some Functional Lisp Dialect

Remark how this code says only what’s needed:

(defn blueberry-buckle
  (bake
    (oven       (375))
    (ready-cake ([25..30]))))

(defn ready-cake
  (sprinkle
    topping
    (pan-cake))))

(defn pan-cake
  (pour
    (blue-cake)
    (pan ([8,8] crisco))))

(defn blue-cake
  (stir
    blueberries (cup 2)
    (smooth-cake)))

(defn smooth-cake
  (mix-progressively
    milk (cup 3/4)
    cream
    base))

Now, here are a few global variables. They would normally be included as local variables of the functions that need them, but I wanted the code to be easier for you to read, hence these separate definitions:

(def topping
  (mix
    sugar    (cup      1/2)
    flour    (cup      1/3)
    cinnamon (teaspoon 1/2)
    butter   (cup      1/4)))

(def cream
  (mix
    sugar  (cup 3/4)
    crisco (cup 1/4)
    egg    ()))

(def base
  (mix
    flour         (cup        2)
    baking-powder (teaspoon   2)
    salt          (teaspoon 1/2)))

Here are a few interesting properties of this code:

It seems to put an emphasis on the functional forms used.
It’s laid out in a kind of vertical, narrow column.
Types are strongly and dynamically checked.
It uses only one programming technique: function application.
The order in which each expression is written doesn’t matter.

John Smith’s Objective Opinion

According to John Smith, this version of the program is the fastest and easiest to read and write. He says it’s also one of the fastest and easiest to maintain.

(He already took a look at the other versions of this code example that follow. What a dude!)

Reactions

Hey, doesn’t this mean that the Java version isn’t the fastest and easiest one?

Doesn’t this feel weird to you? John may say this, but what’s the heck anyway with these weird functional, academic-level languages, right? Such languages aren’t fit for critical production usage. They would crumble under hardship. They’re not battle-tested. They’re not widely used. They’re too hard to learn. Right?

Wait, John says these assumptions of ours are all false. How could it be? Let’s skip to the next section, may we?

Some Functional Haskell Dialect

In this language, each function name is written on the left side of =, which means “… is described as …”. Obviously, the right side of = describes what computations each function depends on to produce its result.

blueberryBuckle = bake(Oven(375), readyCake([25..30]))

readyCake       = sprinkle(topping, panCake)
  where topping = mix([Sugar(Cup(1/2)),         Flour(Cup(1/3)),
                       Cinnamon(Teaspoon(1/2)), Butter(Cup(1/4))])

panCake         = pour(blueCake, Pan([8,8], Crisco))

blueCake        = stir(BlueBerries(Cup(2)), smoothCake) 

smoothCake      = mixProgressively([Milk(Cup(1/2)), cream, base])
  where cream   = mix([Sugar(Cup(3/4)), Crisco(Cup(1/4)), Egg()])
        base    = mix([Flour(Cup(2)),   BakingPowder(Teaspoon(2)),
                       Salt(Teaspoon(1/2))])

Now, let’s implement three of the unimplemented functions, just to see how algorithms are expressed in Haskell:

mix(ings)              = stir(ings, Mixture())

mixProgressively(ings)                 = mixParts(map(/10, ings), Mixture(), ings)
  where mixParts(    _, mixed, [[]:_]) = mixed
        mixParts(parts, mixed, rests)  = mixParts(parts,
                                                  stir(parts, mixed),
                                                  map(-(parts), rests))

stir(ings, mixture)    = foldr(incorporate, mixture, ings)

Here are a few interesting properties of this code:

It seems to put an emphasis on the equational nature of the program.
It’s laid out much more horizontally than vertically.
Types are strongly and statically inferred.
It uses only one programming technique: function application.
The order in which each expression is written doesn’t matter.

John Smith’s Objective Opinion

According to John Smith, this version of the program is the second fastest and easiest to read and write. He adds, though, that out of the box, Haskell goes great lengths to guarantee a lot of things that are impossible to guarantee in most other languages’ proposed usage. Therefore, he says, Haskell is the fastest and easiest to maintain. And for big programs, he says it’s also the fastest to write.

Reactions

What, again? Where’s Java?

Imperative Language

Aside from the fact that imperative languages are the tool to which we’re used, how could one define this concept?

One could think of an imperative language as one which expresses computations as a sequence of manipulations, which must imperatively be followed in the order in which they are expressed, affecting the state of named memory blocks that are shared, so as to progressively build a result out of them.

When a programmer uses the imperative style, he is mostly concerned with the interactions of his code lines with the named variables that progressively help building the result.

Some Object-Oriented Java Dialect

Ah, home, sweet home. How reassuring is the smell of home, sweet home, isn’t it?

public class Chef {
  public static BlueberryBuckle main(String args[]) {
    Chef   chef       = new Chef();

    Oven   oven       = new Oven();
    Pan    pan        = new Pan(8, 8);
    Grease shortening = new Crisco();

    chef.prepare(oven, 375);
    chef.prepare(pan,  shortening);

    Mixture cream = chef.mix(
      chef.prepare(new Sugar(),        Units.cup(3/4)),
      chef.prepare(shortening,         Units.cup(1/4)),
      chef.prepare(new Egg()));

    Mixture cake = chef.mix(
      chef.prepare(new Flour(),        Units.cup(2)),
      chef.prepare(new BakingPowder(), Units.teaspoon(2)),
      chef.prepare(new Salt(),         Units.teaspoon(1/2)));

    cake = chef.mixProgressively(
      cake,
      cream,
      chef.prepare(new Milk(),         Units.cup(1/2)));

    cake = chef.stir(
      cake,
      chef.prepare(new Blueberries(),  Units.cup(2)));

    chef.pour(cake, pan);

    Mixture topping = chef.mix(
      chef.prepare(new Sugar(),        Units.cup(1/2)),
      chef.prepare(new Flour(),        Units.cup(1/3)),
      chef.prepare(new Cinnamon(),     Units.teaspoon(1/2)),
      chef.prepare(new Butter(),       Units.cup(1/4)));

    chef.sprinkle(topping, pan);

    chef.waitFor(oven);

    return chef.bake(pan, oven, 25, 30);
  }
}

Now, try to imagine how you would program the unimplemented methods, like chef.mixProgressively(…). Try a little more. Form yourself a mental picture. Continue, it’s not clear enough. Ok, now it looks like something.

John Smith’s Objective Opinion

According to John Smith, this version of the program is the third fastest and easiest to read, write, and maintain.

John also mentions the unimplemented methods are much more involving to write than with our Haskell dialect.

Moreover, John mentions he uses quite a few faster- and easier-to-use languages than this one, that still fit in the category of object-oriented, imperative languages.

Reactions

Isn’t this surprising, again? Let’s not hear him anymore on Java.

Some Procedural C Dialect

So, where’s the program?

Wait, we know it would look almost the same as that of Java, just much more awkward in large systems. No need to bother writing this, right?

I know you can easily imagine how you would program the unimplemented functions, like mixProgressively(…). We can easily see how awkward it would be to write them without them fitting in the greater scheme of the object-oriented paradigm.

John Smith’s Objective Opinion

According to John Smith, this version of the program is the second longest and hardest to read, write, and maintain.

Reactions

Rock on, John! We now understand each other. No need to spend more time with C. Let’s see what’s next.

Some Procedural Assembly Language Dialect

So, where’s the program?

Wait, did you really expect me to write this whole stuff in assembly language!? I mean, isn’t it, by all means, completely evident how hard and long it would take me to write and debug this stuff?

Try to imagine how you would program everything, including the unimplemented procedures, like mixProgressively. Wouldn’t it be longer to do than with Java’s for comprehensions or C’s for statement, and all those neat features we’re used to?

John Smith’s Objective Opinion

Now, according to John Smith, this version of the program is the longest and hardest to read, write, and maintain.

Reactions

Ah! Rock on, John! We truly understand each other. Wait, that’s right, we weren’t used to think like you just some time ago…

Stop taking the Chef for a fool!

If we consider that:

starting when we stopped looking at declarative language examples, each one of the program versions we looked at was successively closer to machine-level details, and
John’s opinions were really true,

then we can safely derive some conclusions.

Conclusion

Each time we step closer to the machine-level details…

…we need to invest more mental effort and more time to write something.

Each time we step farther away from the machine-level details…

…we need to invest less mental effort and less time to write something.

Rants

Now, my question is, who on earth decided that Java was far enough from machine-level details?

In other words, who, after having known the enlightenment coming from stepping away from the machine-level details, decided it would be wrong to pursue further enlightenment by continuing to step away from the machine-level details?

Well, let’s get back to constructive stuff.

Some Chef Dialect

Isn’t it worth to pursue such clarity and succinctness?

Buckle (Blueberry)

Of course, no general-purpose programming language allows that level of expressivity (that is, without writing anything to back the expression given in the example). This example is clearly an exaggeration of what the perfect programming language could be. It’s meant to illustrate how Domain-Specific Languages (DSLs) can be interesting.

Now, this is where we raise an interesting question. Which kind of programming language would be the most effective at writing DSLs?

John says the answer is to be found somewhere in the category of declarative languages. Functional languages are the most widely used class of declarative languages.

Who’s The Chef?

Or, in another words, who’s the one taken for a fool?

It’s The Compiler!

Obviously, the Chef is our programming language’s compiler. Right? After all, whatever was the level of programming language we used, we always wrote the instructions that it needed to produce what we wanted to eat.

Of course, the more succinctly the compiler allows us to express what we want, the better Chef it is.

The Dynamics Of Compilers

But it’s us, isn’t it, who programmed the behavior of the Chef, in our object-oriented version? Yes, that’s right. Each one of Chef’s unimplemented methods would have to be written by us. And each one of Chef’s method calls, too, have been written by us. And in the non-object-oriented languages, although we didn’t explicitly mention Chef, we were still writing equivalent code. So we understand that whatever the paradigm and language we use to program a computer, we always end up writing everything the compiler doesn’t write for us.

In other words, we write the reciprocal of what the compiler writes:

ourCode + compilerCode = program

From this, we can derive:

ourCode      = program - compilerCode
compilerCode = program - ourCode

Now, if this doesn’t make perfect sense to you, there’s a good reason for it. Any successful high-schooler could beat my long-forgotten (poor) maths skills. Therefore, please correct me if I’m wrong in any way.

Then Who’s The Compiler?

So in reality, the Chef is made up of two entities. First, human-generated code. Second, compiler-generated code. In other words, the compiler is made up of a human compiler and a machine compiler. Hey! don’t call me a compiler, that’s gross!

Our Choice

Now, trust John, we don’t want to be the Chef. That’s why we don’t use assembly language unless we really don’t have any other choice. It’s better to have a Chef at our service. And it’s even much, much better if our Chef is intelligent enough that we don’t have to go at lengths for him to understand what we truly want to eat.

Therefore, if we could find a Chef that allows us to express our desires five times more succinctly and clearly than the one that comes with Java, wouldn’t we be up for total enlightenment? We could either write five times faster the same programs as what we write today with Java, or take the same time that we’re used to, but to get programs five times more interesting.

Wow! I want to work with a better Chef. Don’t you?

Stronger Comparisons Of Language Levels

Now, let’s put aside our own conclusions to hear other kinds of wisdom.

After all, who knows if I can prove Johm Smith’s existence?

1977 – John Backus

We are now reaching one of the most interesting parts of this article.

Here are a few reasons why you might already know of John Backus:

He created the first compiler and high-level programming language: FORTRAN (1958).
He’s also known for his work on other early languages, including ALGOL.
In 1959, he contributed the definition of the Backus Normal Form (BNF), which was later improved by Peter Naur, becoming the Backus-Naur Form.
We were reminded of his life’s works when he died in 2007.

Now, why do you think I’m mentioning the creator of the first high-level programming language?

Frustrations And Solutions

Let’s hear Alex Aiken, from Stanford University:

He grew frustrated with the limitations of imperative-style programming and felt that there must be a better, higher-level way to develop software.

I certainly can relate to this, even 30 years later.

He eventually came to the realization that a core difficulty with FORTRAN-style languages was that programmers were reduced to reasoning about a long sequence of small state changes to understand their programs, and that a much simpler and more compositional method of reasoning would be to think in terms of the net effect of a computation, where the only thing that mattered was the mapping from function inputs to function outputs.

Functional programming! Or, should I say, function-level programming. Why? Because Backus’ ideas go even further than what we use now.

There were others, including Robin Milner [SML] and David Turner [SASL, Miranda ~> Haskell], who were thinking along similar lines at about the same time, but as yet there was no functional programming community.

One might want to include Lisp in this list, but should not overlook that Lisp, being a multi-paradigm programming language, embraced very openly many imperative programming techniques.

That all changed with Backus’ Turing Award lecture, published in 1978. His paper, “Can Programming Be Liberated from the von Neumann’s Style?”, did something very unusual, perhaps unique: it attacked his own previous work, his own legacy, and furthermore proposed an alternative that was far out of the mainstream. His paper had an electric effect; I think it is fair to say that it jump-started the field of functional programming. Certainly the number of researchers in the area, and the amount of funding for that research, increased dramatically in the years just after John received the Turing Award. His Turing Award remains his most cited paper, and indeed remains the most cited of all the Turing Award lectures in the 40 year history of that prize.

History now tells us that it’s in the 10 years following Backus’ lecture that researchers found most major ways of optimizing compilers to narrow the performance gap between functional languages and their imperative counterparts.

So, although John Backus is most remembered for his first works on FORTRAN, BNF and ALGOL, we should not forget why he devoted the last 15 years of his career to the field of functional programming.

On Imperative Programming Languages

Now, let’s see exactly how Backus described, in his famous lecture, imperative programming languages:

Conventional programming languages are growing ever more enormous, but not stronger. Inherent defects at the most basic level cause them to be both fat and weak:
their primitive […] style of programming inherited from their common ancestor—the von Neumann computer,
their close coupling of semantics to state transitions,
their division of programming into a world of expressions and a world of statements,
their inability to effectively use powerful combining forms for building new programs from existing ones, and
their lack of useful mathematical properties for reasoning about programs.

Ouch! One could hardly find a harder critique of his own work!

If you would like to understand precisely what he means by these five arguments, you should definitely read at least the first 7 pages of his paper.

Each new language claims new and fashionable features, […] but the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them. […] Since large increases in size bring only small increases in power, smaller, more elegant languages […] continue to be popular. But there is a desperate need for a powerful methodology to help us think about programs, and no conventional language even begins to meet that need. In fact, conventional languages create unnecessary confusion in the way we think about programs. […] Although I refer to conventional languages as “von Neumann languages” to take note of their origin and style, I do not, of course, blame the great mathematician for their complexity. In fact, some might say that I bear some responsibility for that problem.

See? And that’s not all.

Before discussing alternatives to von Neumann languages, let me remark that I regret the need for the above negative and not very precise discussion of these languages. But the complacent acceptance most of us give to these enormous, weak languages has puzzled and disturbed me for a long time. I am disturbed because that acceptance has consumed a vast effort toward making von Neumann languages fatter that might have been better spent in looking for new structures. For this reason I have tried to analyze some of the basic defects of conventional languages and show that those defects cannot be resolved unless we discover a new kind of language framework.

Reading Backus’ paper has been a profoundly enlightening experience for me.

I definitely suggest you schedule some time to read at least the first 12 pages of his lecture. The first 7 pages will shed out more light on what’s wrong with imperative languages; then, the next pages will explain how a language can be implemented on top of a very small number of sound and simple concepts that can be used and powerfully combined in all sorts of natural ways to describe computations.

References

Bibliography

1982 – David Turner

John Backus has often been caught saying of himself that he’s lazy. It was one of his ways of explaining why he created high level languages. Nonetheless, the computer scientist the most remembered when it comes to laziness isn’t Backus, but David Turner, who brought us the concept of lazy evaluation. Incidentally, we also owe him a great deal for the concept of purity in functional programming.

Both the purity and laziness concepts are central to what Turner wrote in 1981-1982 in his paper called Recursion Equations As A Programming Language.

Problems And Solutions

The importance of [functional] languages lies in the fact that they hold out the promise of being able to solve both of these problems at the same time [1: software costs, 2: taking advantage of a very large degree of concurrency in the machine]. In both cases the key step is the abolition of the assignment statement, and with it the notion of sequencing.

Ouch! Abolition of the assignment statement might sound incredibly alien to your ears, but please bear with him. It makes much more sense than it might appear to the functional programming neophyte. And by sequencing, David means how imperative languages oblige us to control explicitly, instead of implicitly, the order in which things are supposed to happen.

The Desirable Properties Of Mathematical Language

When we compare our programming languages with all previous mathematical notation, however, the differences are very striking. Mathematical notation has evolved over many centuries and obeys certain basic rules, which are common to every area of mathematics, and which give mathematical notation its deductive power.

First of all mathematics is static. There is no equivalent, in mathematics, of the programming language notion of a procedure which gives a different answer each time you call it. The mathematical idea of a function is a fixed table of input-output pairs. […] This is so even when mathematics is used to describe processes of change as in physics. […] Physics as a science became possible only because Newton showed us how to reduce dynamics to statics in this way.

Secondly, and relatedly, there is in mathematics a certain kind of consistency in the use of names […] Paradoxical though it may sound, in mathematics variables do not vary; they stand for a constant value throughout their scope.

These basic properties of mathematical notation have been termed by logicians, “referential transparency” […] An immediate consequence of referential transparency is that equality is substitutive – equal expressions are always and everywhere interchangeable. It is this which gives mathematical notation its deductive power.

Thus, we shouldn’t spit on the semantics of such a notation.

On Imperative Programming Languages

[…] In introducing the assignment statement, which can change the value of a variable in the middle of its scope, they have broken the basic ground-rules of mathematical notation. Instead of being referentially transparent, programming languages are referentially opaque. In fact, the things that we call “variables” […] are not really variables […] – in the last analysis they are names for registers in the store of a Von-Neumann computer.

It is because of this that it is so difficult to reason about programs. Since expressions can change their value through time, equality is not substitutive. Indeed, […] it does not even have to be true that an expression is equal to itself (because the presence of side effects may mean that evaluating the same expression twice in succession can produce two different answers)! In general it is not possible to reason about such programs on the basis of a static analysis of the program text – instead we have to think of the program dynamically and follow the detailed flow of control […].

Thus, to one equally used to imperative and declarative languages, it takes more time to read and understand properly imperative code. And that’s not all.

A number of studies carried out in the industry have shown that a given programmer tends to produce, per year, a relatively fixed number of lines of code […] and while the number of lines varies quite a lot from programmer to programmer, it is for a given individual largely independent of the language in which he is working (for example, it doesn’t seem to matter whether it is assembly code or PL/1).

The significance of this result is that it means that the most important single variable in determining software production costs, apart from the quality of the programmers, is the level of language at which they are working. […] programs written in FORTRAN are from five to ten times shorter than the equivalent assembly code. Other things being equal, then, the FORTRAN programmer is from five to ten times more productive than the assembly code programmer.

The same kind of rule applies to today’s mainstream languages.

Our problem today is that in the 25 years that have elapsed since the invention of FORTRAN we have failed to produce any further substantial improvement in this basic ratio of expressive power. If you compare a program written in a “modern” imperative language, such as PASCAL or ADA with its FORTRAN equivalent, you will not find it very much shorter (in fact it might even be longer, because of the extra declaratory information necessitated by the current fad for very restrictive forms of strong typing).

Since then, some things changed:

First, object orientation completely replaced our simple procedural practices, with many good results. Overall, it’s recognized that object orientation made our programs slightly less verbose, but more complicated.
Second, some arduous things, like memory management, have been removed from our hands, thanks to garbage collection. This change is recognized as being the one that contributed the most to improving our productivity in the last 20 years.
Third, our languages started to adopt more functional techniques, like those of higher-order programming.

Taken together, these changes enabled us to create programs in some of our modern languages which are probably five to ten times shorter than they would have been in the C++ of 10 years ago. All of this being said, let’s mention that our imperative languages have continued to use this very restrictive form of strong typing that David wrote about. It’s only recently that some of our languages started to improve on this basic type checking by inferring some types; but even this is a far cry from the kind of type checking that exists in the functional breed of languages.

All of this being said, what needs to be emphasized is that even though our languages have evolved, they are still fundamentally oriented towards an imperative usage.

[…] We can give a general reason why the change from an imperative language to a descriptive one should lead to programs becoming so much shorter. Expressed at an appropriate level of abstraction […], an algorithm is a partially ordered set of computations – the partial ordering being imposed by the data dependencies.

In order to execute an algorithm on a Von-Neumann computer, however, we have to convert this to a total ordering (in any one of the many possible ways) and organise storage for the intermediate results. In an imperative language both of these tasks must be carried out explicitly by the programmer with the result that he has to specify a great deal of extra information.

In summary, a good case can be made out for saying that the fundamental cause of the software crisis is the imperative and machine oriented nature of our programming languages, and that to overcome it we have to abandon the use of side effects and programmer control of sequencing in favour of purely functional notation.

Radical, but true. There’s been a time when programmers felt garbage collection was an unacceptable way of managing memory. Nowadays, we wouldn’t want to part with such a facility unless it was of the utmost importance to do so. The same can be said of what I will call manual computation order management. It’s time for us let it loose in most of our code. Smart compilers can give us another big increase in productivity, if we will let them decide how to order our computations, within the limits of our very clear functional semantics.

The theoretical possibility of programming in a purely functional style has been known about for two decades – the obstacle to its use in practice has always been the difficulty of achieving acceptable efficiency in the use of existing hardware while using such techniques.

A few years after he wrote his paper, the technology used to create optimizing compilers for functional languages started to become competitive. Since then, the gap has been closed. That is, of course, if you compare those functional and imperative languages whose compiler is designed for performance.

Daniel Jomphe

Understanding Dispatch

Introduction

Definitions

Observations

Examples

10 Reasons To Strictly Separate The V In MVC

A Practical Solution

The Case For Functional Programming

What Is Discussed Here?

Comparing Different Language Levels

How To Reach Truthful Conclusions

Qualifications Of Yours Truly

Qualifications Of John Smith

Natural Language – The Testbed

Some English Dialect

Declarative Language

Some Functional Lisp Dialect

John Smith’s Objective Opinion

Reactions

Some Functional Haskell Dialect

John Smith’s Objective Opinion

Reactions

Imperative Language

Some Object-Oriented Java Dialect

John Smith’s Objective Opinion

Reactions

Some Procedural C Dialect

John Smith’s Objective Opinion

Reactions

Some Procedural Assembly Language Dialect

John Smith’s Objective Opinion

Reactions

Stop taking the Chef for a fool!

Conclusion

Rants

Some Chef Dialect

Who’s The Chef?

It’s The Compiler!

The Dynamics Of Compilers

Then Who’s The Compiler?

Our Choice

Stronger Comparisons Of Language Levels

1977 – John Backus

Frustrations And Solutions

On Imperative Programming Languages

References

Bibliography

Further Reading

1982 – David Turner

Problems And Solutions

The Desirable Properties Of Mathematical Language

On Imperative Programming Languages

References

Bibliography

1984 – John Hughes

References

More to come in the future…

Fundamental Problems Of The Imperative Way

The Assignment Statement

Manual Computation Order Management

The Imperative Coalition’s Last Hopes

Object Orientation

Higher-Order Functions

Limits