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.Well that was before Functional Programming hit the headlines.
Richard O'Keefe on Erlang list
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 programmingpedagogy that were widely understood in the 1970s and 80s have mysteriously become ununderstood 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 firstclass  1969
 Settheory moves from the rarefied air of metamathematics into an implemented programming language – In SETL, the abstruse principle called the comprehensionprinciple 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 metalanguage (Hence the name M(eta)L(anguage)). Earlier patternmatching existed in languages like Snobol, and recursion in Lisp. ML, by juxtaposing patternmatching 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 HindleyMilner 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 longestlived 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 FPboat by not being properly buzzword compliant
First release of Visicalc. [More famous later avatars Lotus 123 and Excel]
Relevance to FP? Juxtapose the original Visicalc blurb: Magic sheet of paper that can perform calculations and recalculations with PeytonJones 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. uncorporate. 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
McCarthy gives this interview in 1987:
I think that the historical importance of Lisp is that it was the first language to provide `garbagecollected' 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.
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

Bruno Buchberger spells out: the blackboxwhitebox 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 "whitebox" 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.
 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 functiondot 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 wellknown
 Haskell 1.0

Bruno Buchberger spells out: the blackboxwhitebox principle:
 1991
 Moggi publishes on Monads. Much of programming language research is in taking imperative practice and 'declarativeizing' 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 Realworld
 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 publicpenitence.
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 fullcircle 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 modernFP 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]
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]
Lambda calculus became the theoretical basis for the description and calculation functions. As a mathematical abstraction, not a programming language, it was the basis of almost all functional programming languages today.
ReplyDeleteThanks for that comment, yes λcalculus is an important part of the history....
ReplyDeleteA history is a story after all which must inherently have an arbitrary start: 'Once upon a time…"!!
I decided to start it after modern computers.
We could of course go further back; then yes λcalculus would get included. So would Euler's use of the 'f(x)' notation; the increasing generality of the notion with Dedekind and so on.
Actually this is a rich field and probably demands another blog post...
So for now: Thanks again for the comment!
Which four?
ReplyDelete