Search This Blog

Wednesday, April 29, 2015

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 worldgood 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... effectivelybased 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]

3 comments:

  1. 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.

    ReplyDelete
  2. Thanks for that comment, yes λ-calculus is an important part of the history....
    A 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!

    ReplyDelete