Functional Programming: A Timeline

Rob Hagan at Monash had shown that you could teach students more Cobol with one semester of Scheme and one semester of Cobol than you could with three semesters of Cobol.
Richard O'Keefe on Erlang list

Well that was before Functional Programming hit the headlines.
These days FP is quite a buzzword. Is this for good or bad?
If real world ≡ good well then Scala and Clojure and Erlang and Haskell becoming more and more 'real world' is a wonderful thing.
If what is good is understanding, then I am not so sure. Many things about programming, pedagogy and programming-pedagogy that were widely understood in the 1970s and 80s have mysteriously become un-understood today.
However in this darkening of the age there are some glimmers… eg ACM's 2013 curriculum.
In this post I would like to delineate a timeline of the semantics and significance of Functional in the last 50 years. In subsequent posts I'll try to deconstruct how the semantics has shifted around in this time.

Timeline

1957

The first programming language – Fortran

1957

The first functional programming language – For(mula)Tran(slator)

Why? Whoa! How?

Read on…

1957

Chomsky publishes Syntactic Structures
The impact of this on FP is profound (and still in the future) as indicated by Bob Harper

1960

Lisp; and APL

1960

Algol – A boat missed The report comments:

Samelson and others had unsuccessfully tried to have procedures as parameters included in ALGOL 60 in a straightforward manner

What would CS have been for the last 50 years if this decision had been different??

1966

ISWIM – famous for offside rule. Real contrib? Design first implement 20 years later

1967

Scott and Strachey start using functions for denoting the meaning of imperative languages
First use of the term first-class

1969

Set-theory moves from the rarefied air of meta-mathematics into an implemented programming language – In SETL, the abstruse principle called the comprehension-principle becomes a connerstone of programming.

1972

Unix and C – one negative and one positive contribution to FP

• The inception of the widespread abuse of function syntax for denoting procedural semantics.
• In a world where all languages were spelt like COBOL, FORTRAN, LISP, APL, JOVIAL etc, ie programming languages were STRICTLY AND INVARIABLY UPPERCASE, for the first time programmers can use lowercase. If you consider this a non seqitur wrt a history of FP, ask yourself the connections between math and notation

1973

Milner makes ML. Started as a logic meta-language (Hence the name M(eta)-L(anguage)). Earlier pattern-matching existed in languages like Snobol, and recursion in Lisp. ML, by juxtaposing pattern-matching with recursion, made concrete and executable one of the more abstruse concepts of CS theory – structural induction.
Biggest contrib: An ML program is as free from variable declarations as Lisp and more strongly typed than Pascal. So Hindley-Milner type inference makes the famous dilemma between statically and dynamically typed languages into a mostly bogus argument.

1976

Dijkstra's Discipline of Programming – FP from 'the other side'.
Floyd and Hoare gave the semantics of imperative programs relationally (or predicatively or 'axiomatically'). Dijkstra expressed the same thing with wp — a function.

And the first version of emacs — probably one of the longest-lived widely used systems written in Lisp

1977

Burstall and Darlington FP as 'recursion equations'. Narrowing the gap between math and programming

1977

Backus Turing award and lecture in which the name 'FP' is introduced. And Backus does public penitence for the 'sin' of inventing Fortran, 20 years after the invention.
Ironic if we see 2011 below…
Also… how much did the next two Turing award winners happen because of Backus? [conjecture of course]

1978

Floyd's Turing lecture on Paradigms of Programming

1979

Iverson Turing Award and lecture — one of the important compendia of FP that mostly misses the FP-boat by not being properly buzzword compliant
First release of Visicalc. [More famous later avatars Lotus 1-2-3 and Excel]
Relevance to FP? Juxtapose the original Visicalc blurb: Magic sheet of paper that can perform calculations and recalculations with Peyton-Jones description of spreadsheets as The world's most widely used functional language

1980

Hope adds algebraic data types to recursion + equational reasoning. [Bit unclear: what came from Hope and what from ML]

1981

E.F. Codd wins Turing award for the relational model. Thanks to imperative programming domination, it would take another quarter century before SQL's links with programming enter the mainstream of programming [2007 below].

1980s

Lazy FPLs like SASL, KRC, Miranda, Orwell, LML start appearing.
MIT uses scheme to teach its first programming course, based on…
SICP, a landmark not just in Lisp circles but for CS at large.

1986

Meertens publishes Programming as a mathematical activity
How many pythonistas today know that Meertens is a grandfather of python? SETL → ABC → Python

Ericsson needs a language for its telephone switches.
Strangely instead of choosing to make a fancy language for phone switches it makes a simple language for supporting concurrency... effectively… based on functional programming. v.v. un-corporate. And Erlang is born.

1987

Earliest reference (I can find) to Bird and Meertens combined creation – squiggol

Late 80s

Wadler writes why calculating is better than scheming — the beginnings of the end of the era of Lisp as the premier functional language.
Turner writes more strongly against Lisp:

It needs to be said very firmly that LISP, at least as represented by the dialects in common use, is not a functional language at all. Lisp does have a functional subset, but that is a rather inconvenient programming language and there exists no significant body of programs written in it. Almost all serious programming in LISP makes heavy use of side effects and other referentially opaque features
I think that the historical importance of Lisp is that it was the first language to provide `garbage-collected' heap storage. This was a very important step forward. For the development of functional programming, however, I feel that the contribution of Lisp has been a negative one. My suspicion is that the success of Lisp set back the development of a properly functional style of programming by at least ten years.

McCarthy gives this interview in 1987:

I was writing a "silicon compiler" as a DSL in a strict subset of ML, and was keen to understand these (for me, new/strange) functional languages a little better. So I asked McCarthy was the use of the LAMBDA notation in Lisp because the language was functional, or was it just a convenient notation for anonymous functions? His answer was short and very definitive: he said it was a convenient notation — he didn't consider Lisp to be a functional language.

1989

Wadler publishes Theorems for free.  Evidently FP is a welfare state where free theorems are abundant. Why is imperative programming so impoverished of free theorems?

1990

1. Bruno Buchberger spells out: the blackbox-whitebox principle:

   A didactic principle that can govern the use of software systems in math courses. The principle states that, in the treatment of each subarea of mathematics, one must distinguish between a "white-box" and a "black box" phase. In the "white box" phase, algorithms must be studied thoroughly, i.e. the underlying theory must be treated completely and algorithmic examples must be studied in all details. In the black box phase, problem instances from the area can be solved by using symbolic computation software systems. This principle can be applied recursively.

2. Dijkstra and Scholten publish Predicate Calculus and Program Semantics
   Not much to do with functional programming; but with function notions and notation:
   Euler notated function as f(x)
   Functional languages notate with f x
   D&S notate with f.x ie the application has an explicit operator.
   In a laconic comment they say that the function-dot has the same notational significance that the '=' of Recorde had 500 years earlier!
   This significance is elaborated at Thought dialogue with EWD and DotingOnTheDot and Purgatory
   and most well-known
   
3. Haskell 1.0

1991

Moggi publishes on Monads. Much of programming language research is in taking imperative practice and 'declarative-izing' it. In showing monads as a generalized form of computation, Moggi demonstrates the opposite direction: How to add imperation to the rarefied realms of category theory.

1991

The Unicode consortium is incorporated.
What the hell does that have to do with functional programming?
What does notation have to do with math?
And math with programming?
Read APL/Squiggol above

1992

Essence of FP: The essence of impure (ie imperative) features can be captured in a pure functional language – using Monads

2001

The great god of imperative programming, Dijkstra, at the end of his life publicly acknowledges the benefit of using Haskell to introduce programming

2007

.Net 3.5 releases LINQ – Two subjects, databases and programming, that were hitherto regarded as immiscible, finally meet thanks to FP

2008

Haskell becomes Real-world

2009

MIT switches its introductory programming course from Scheme to Python

SICP reflected an aspiration to place computer science closer to the pure sciences, i.e. math … However, nowadays an engineer must learn to perform basic science experiments to find out how (buggy) software and hardware actually works (for which python is better)

2010

Functional languages – scala – start making the Tiobe index.
Resurgence of Lisp under the functional moniker – Clojure

2011

Death of McCarthy. A little before he dies, he gives an interview in which
McCarthy spills the beans!
In the 1st question he says he learnt functional programming from Backus' Fortran.
Now! Now!! John if you had made that statement a little earlier than the end of your sojourn on this planet, the other John would have been saved the public-penitence.
And so one needs to understand that while in 1957 Fortran was a functional language – the very name carries that intention – by 1977 that stand needed a very public withdrawal.
Anyhow… Lets be clear about it:
Fortran was (is?) the first functional programming language
More significantly FP has come round full-circle in 50 years till we reach… 

2013

ACM curriculum 2013 functional programming enters the realm of absolute basics of CS.

2030??

In the same way that in 1957 Fortran was a functional language whereas today even Lisp is not regarded as properly functional, I am ready to bet that 20 years from now Haskell wont be either.
Beginning rumbles: Bob Harper's Haskell is exceptionally unsafe

---

Above timeline explored in more detail in subsequent posts. Here's the next.

Also Richard O' Keefe in arguing with some of the above makes many interesting historical remarks himself. [Should have gone in comments below but blogger protests the length!!]

---

Paul Hudak

one of the few who straddled the Lisp to modern-FP worlds, died on April 29th 2015, as I was putting this post together. This post is dedicated to his memory.
I would like to add about Paul Hudak's Scheme and the early flounderings of lisp but cant find the reference. [in case someone can find it]