> The development of the theory of types that eventually led to the Standard ML type system goes back more than a hundred years.

> David MacQueen, Robert Harper, and John Reppy. "The history of Standard ML." [^MacQ20]

It's not that there's a lack of literature on the history of functional programming. There are already general overviews of functional programming [^Huda89] [^Turn12], as well as histories of specific languages or language families [^Huda07] [^MacQ20] [^McCa78] [^Stee96], and biographies of researchers [^Camp85] [^MacQ14]. So why do we need yet another one?

### Cryptolambdian

When, yet again, gigabytes of memory are insufficient for compiling Haskell code, the question naturally arises: in what _sense_ did functional programming exist in, say, 1973? Unfortunately, materials on the history of functional programming usually don't pay much attention to this. For histories of functional programming, they often contain too little history of _programming_.

We don't aim to define "programming," but in this work, we assume it's the process of writing programs. And our great predecessors, in their works on the history of functional programming, don't particularly like to write about what programs resulted from this process.

Worse, programming historians often venture so far back that it's questionable whether "programming" existed at all in those periods.

For example, MacQueen, Harper, and Reppy start the prehistory of Standard ML in 1874 [^MacQ20]. Obviously, functional programming didn't exist in 1874. It's not so obvious whether it existed in 1974. What programs had been written in functional languages by that year? What implementations were available, and for whom? Until what year could functional programming languages be said to exist only in the same sense as in 1874, as notations in books, notebooks, on chalkboards, and so on?

For example, it's often claimed that ML appeared in 1973, but what exactly happened that year? That year, Robin Milner had the desire to write an interactive theorem prover not in Lisp. Did Milner succeed, and in what year? What part of the interactive theorem prover was written in ML? How many lines of code did it have? Who wrote an interactive theorem prover entirely in ML, and how many years later? And who wrote an interactive theorem prover entirely using ML implementation, in turn, itself written in ML, and when? And how many lines of code were in that implementation? Our work will answer these and other questions.

There's a vast difference - and a significant time gap - between dreaming of functional programming and actually writing a program in a functional language. We believe this perspective is useful for those who don't think history begins and ends with an idea, and that implementing it is trivial and uninteresting.

It's not that the question of functional language implementation usability is never raised, but our great predecessors weren't particularly interested in it. Some surveys list implementations considered "non-toy," "efficient" [^Huda89], or "fast" [^SPJ87], but their criteria are vague, and you might get a different impression if you knew more about those implementations. We certainly did. In such lists, compilers that compiled themselves and other large projects are mentioned alongside ones that didn't.

Therefore, we will try to establish what size programs were written using functional languages and what the performance of these programs was.

All this is mostly a consequence of our great predecessors writing primarily histories of ideas. And they didn't do that because it's easy - tracing the history of ideas is very hard. That's one reason we're not writing a history of ideas. We're writing a history of implementations first, and only then a history of ideas.

For every idea, one can trace a predecessor, and each one pulls further into the depths of centuries. It's ideas all the way down. That's how a historian of functional programming ends up in 1874. A history of implementations solves that problem neatly - perhaps _too_ neatly.

Ideas leave fewer traces, and the ones they leave are less convenient for a historian. An implementation (even a failed one) leaves behind different versions of code, notes in it, bug reports, release announcements - evidence of what worked and when.

Ideas leave behind papers, which might be published years later and "cleaned up" in ways that erase history. The related work section documents the relationships between ideas, but not their history. Influences are often declared, but the "influencing" idea might only be discovered after the "influenced" one has already been reinvented independently.

Sometimes, an author explicitly states this. For example, Xavier Leroy writes that he reinvented some ideas from Krivine's machine without knowing about it and only added citations after other people pointed out the similarity. The creator of Chez Scheme independently rediscovered some ideas found in VAX ML, while others were directly borrowed. But not everyone feels the need to disclose this.

Attempts to trace the history of ideas are also complicated by the fact that the opinions of language authors about which languages they influenced may not coincide with the opinions of the authors of those languages about which languages influenced them.

This shouldn't be surprising. Ideas for how to design programming languages often arise independently. Even the Hindley-Milner algorithm - a nontrivial and precisely defined concept - was independently reinvented. But no one has ever independently written two identical compilers.

It's easier to cite a paper than to reuse compiler code. So, when we write histories of ideas, the graph ends up with too many edges.

To group implementations into families, we'll use rarer but more reliable connections: shared code, common authors, and bootstrapping one implementation with another.

Historians of functional programming often face the same challenge we've outlined - how to define the scope of their study. If you're writing a language's history, where do you draw the line? One approach is to define a language by its syntax and semantics - trees or sequences of symbols that can be compared. This enables building trees and graphs that show how programming languages evolved and diverged. Of course, that level of analysis is very demanding. We'll analyze not the syntax/semantics descriptions (the most suitable targets for such analysis), but the next best thing - actual implementations in functional languages.

Unfortunately, our great predecessors often chose simpler criteria. Names. If anything can prevent a historian from endlessly digging into the past, it's names. But using names to decide where one language ends and another begins may not be a great solution.

Some authors love a name so much that they keep using it for ever-new and increasingly unrelated things. Syntaxes of many FP languages in the '80s resembled each other more than they resembled their own earlier versions from the '70s, despite sharing names. Fortunately, something was first called "ML" a very long time ago, and there are no obstacles to starting the history of ML from its beginning, or even long before its beginning.

Unfortunately, many authors use different names for the same thing. The first Haskell compiler was created in just a few months from a non-Haskell compiler. This clearly indicates that a great deal of work had already been done, which can justifiably be considered work towards creating Haskell. Three of the first five Haskell compilers were developed for many years before the idea to design this language even emerged. Alas, non-Haskell wasn't called "Haskell," so nothing could be done - in the history of Haskell [^Huda07], no more than a few lines could be devoted to this.

The authors of Haskell chose a different non-Haskell as the basis for the first Haskell Report. And this non-Haskell resembles Haskell 1.0 more than ML in '82 resembled ML in '83. But sorry - it wasn't called "Haskell," so our great predecessors can't write its history.

We can.

### Phanerolambdian

What is our history of implementations? Primarily, it's a history of compilers for general-purpose machines, and to a lesser extent of interpreters and specialized hardware implementations. We chose compilers for conventional machines because they're the most successful implementation path for functional languages: they've survived to this day (unlike special hardware), they've been used for substantial programs (unlike many interpreters and hardware), more is simply known about them; there is something to write about. Compilers are complex enough that there aren't _too_ many of them - unlike interpreters. So we end up with a manageable set of fairly detailed histories, rather than endless lists with terse descriptions.

Of course, we'll touch on interpreter and hardware history where it's needed to understand compiler history, but we don't aim for completeness there.

Still, the history of implementations has its problems. The history of programming is not very eventful during times when functional programmers weren't writing many non-trivial programs. What are non-trivial programs? We'll consider such programs to be the code of a compiler for a functional language or the code of a theorem prover.

This may not seem like a high bar, but for functional programming it definitely is. Frankly, it's not like we had much choice in setting this bar. Outside of micro-benchmark speeds and how fast a compiler written in a functional language compiles, there isn't much information.

About some implementations, one can read that Fibonacci numbers are computed not much slower than in C, and that a compiler written in the language compiles something in an acceptable time. About others, one can read that no compiler is written in them, and performance is not that important anyway.

Since the history of programming and working implementations is heavily skewed towards the end of the history of ideas, it doesn't fit well with the typical "progress" and "formation" structure of idea histories, where everything starts with Lisp, continues with strict functional languages, and concludes with lazy ones. Instead, we have a period where nothing worked, followed by a period where everything did - all at once.

Our history is structured by the lifecycle of implementations, or more precisely, their families. We will begin with implementations whose developers planned or even attempted to create a functional language compiler from a non-functional language compiler, or to turn a non-compiler functional system into a compiler. For a long time, such plans were either not implemented at all, or attempts were made but were unsuccessful. We will discuss this period in Part Zero of our history.

When several such attempts finally succeeded, the first part of the history began. In it, we will discuss the first compilers for functional languages that do not yet resemble those we defined above as the functional languages whose history we are writing.

In the second part, we will describe how these implementations were transformed into implementations of precisely such languages - the languages of the Edinburgh research programme, whose history we are writing. And about new implementations that were implementations of such languages from the very beginning.

In the third part, we will discuss the next period, in which these implementations were used to write the first serious programs: provers and a new generation of functional language compilers. This is when functional programming finally _arrives_.

The history of implementations poses a question for us, the answer to which requires considering the history of conventional machines and operating systems as well. Which, of course, we will also describe without any claim to completeness. If the idea of functional programming, as our great predecessors discovered, existed for as long as programming itself, or even longer, then why wasn't there functional programming? When could it have already appeared? And what existed when functional programming did not?

REFERENCES

----------

[^Camp85]: Campbell-Kelly, Martin. “Christopher Strachey, 1916-1975: A Biographical Note.” Annals of the History of Computing 7 (1985): 19-42.

[^Huda89]: Paul Hudak. 1989. Conception, evolution, and application of functional programming languages. ACM Comput. Surv. 21, 3 (Sep. 1989), 359–411. DOI:10.1145/72551.72554

[^Huda07]: Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler. 2007. A history of Haskell: being lazy with class. In Proceedings of the third ACM SIGPLAN conference on History of programming languages (HOPL III). Association for Computing Machinery, New York, NY, USA, 12–1–12–55. DOI:10.1145/1238844.1238856

[^MacQ14]: Luca Cardelli and the Early Evolution of ML, by David MacQueen. A paper presented at the Luca Cardelli Fest at Microsoft Research Cambridge on Sept. 8, 2014.

[^MacQ20]: MacQueen, David B., Robert Harper and John H. Reppy. “The history of Standard ML.” Proceedings of the ACM on Programming Languages 4 (2020): 1 - 100.DOI:10.1145/3386336

[^McCa78]: McCarthy J. History of LISP. In History of programming languages 1978 Jun 1 (pp. 173-185).

[^SPJ87]: Peyton Jones, Simon L. The implementation of functional programming languages (prentice-hall international series in computer science). Prentice-Hall, Inc., 1987.

[^Stee96]: Guy L. Steele and Richard P. Gabriel. 1996. The evolution of Lisp. History of programming languages---II. Association for Computing Machinery, New York, NY, USA, 233–330. doi:10.1145/234286.1057818

[^Turn12]: Turner DA. Some history of functional programming languages. In International Symposium on Trends in Functional Programming 2012 Jun 12 (pp. 1-20). Springer, Berlin, Heidelberg.