16
$\begingroup$

I'm reading Simon Peyton Jones's The Implementation of Functional Programming Languages and there's one statement that surprised me a little bit (on page 39):

To a much greater extent than is the case for imperative languages, functional languages are largely syntactic variations of one another, with relatively few semantic differences.

Now, this was written in 1987 and my thoughts on this subject might be influenced by more modern programming languages that weren't around or popular then. However, I find this a bit hard to believe. For instance, I think that the described Miranda programming language (an early predecessor to Haskell) has much more different semantics compared to a strict language like ML than say C has to Pascal or maybe even C has to smalltalk (although I'll cede that C++ provides some validation of his point :-).

But then again, I'm basing this on my intuitive understanding. Is Simon Peyton Jones largely correct in saying this, or is this a controversial point?

$\endgroup$
18
$\begingroup$

Simon is basically correct, from an extensional point of view. We know pretty well what the semantics of modern functional languages are, and they really are relatively small variations of one another -- they each represent slightly different translations into a monadic metalanguage. Even a language like Scheme (a dynamically typed higher-order imperative language with first-class control) has a semantics which is pretty close to ML and Haskell's.

From a denotational point of view, you can start by giving a pretty simple domain equation for the semantics of Scheme -- call it $V$. People could and did solve equations like this in the late 70s/early 80s, so this isn't too bad. Similarly, there are relatively simple operational semantics for Scheme as well. (Note that when I say "Scheme", I mean untyped lambda calculus plus continuations plus state, as opposed to actual Scheme which has a few warts like all real languages do.)

But to get to a category suitable for interpreting modern typed functional languages, things get quite scary. Basically, you end up constructing an ultrametric-enriched category of partial equivalence relations over this domain. (As an example, see Birkedal, Stovring, and Thamsborg's "Realizability Semantics of Parametric Polymorphism, General References, and Recursive Types".) People who prefer operational semantics know this stuff as step-indexed logical relations. (For example, see Ahmed, Dreyer and Rossberg's "State-Dependent Representation Independence".) Either way, the techniques used are relatively new.

The reason for this mathematical complexity is that we need to be able to interpret parametric polymorphism and higher-order state at the same time. But once you've done this, you're basically home free, since this construction contains all the hard bits. Now, you can interpret ML and Haskell types via the usual monadic translations. ML's strict, effectful function space a -> b translates to $\left<a\right> \to T\left<b\right>$, and Haskell's lazy function space translates to $\left<a\right> \to \left<b\right>$, with $T(A)$ the monadic type of side effects interpreting the IO monad of Haskell, and $\left<a\right>$ is the interpretation of the type ML or Haskell type a, and $\to$ is the exponential in that category of PERs.

So as far as the equational theory goes, since these languages can both be described by translations into slightly different subsets of the same language, it is entirely fair to call them syntactic variations of one another.

The difference in feel between ML and Haskell actually arises from the intensional properties of the two languages -- that is, execution time and memory consumption. ML has a compositional performance model (i.e., the time/space cost of a program can be computed from the time/space costs of its subterms), as would a true call-by-name language. Actual Haskell is implemented with call-by-need, a kind of memoization, and as a result its performance is not compositional -- how long an expression bound to a variable takes to evaluate depends on whether it has been used before or not. This is not modelled in the semantics I alluded to above.

If you want to take the intensional properties more seriously, then ML and Haskell do start to show more serious differences. It is still probably possible to devise a common metalanguage for them, but the interpretation of types will differ in a much more systematic way, related to the proof-theoretic idea of focusing. One good place to learn about this is Noam Zeilberger's PhD thesis.

$\endgroup$
9
$\begingroup$

My sense is that SPJ was referring to purely functional languages -- i.e. languages which are referentially transparent. This includes, e.g., Haskell, Miranda, Clean, but not ML. Once you have a purely functional language, in general, you can give it a fairly clean and well defined denotational semantics. This semantics will, in general, look like one for the lambda calculus, with some tweaks here and there. Generally, you will have a type system which desugars to something resembling a variant of System F -- perhaps more powerful in some regards, more restricted in others. This is why code extraction to/compilation to Haskell, O'Caml, etc. is relatively straightforward from sophisticated dependently-typed proof assistants such as Agda.

Within that framework, there's lots of room for play. Certainly, there is still a difference between a non-strict and a strict language. However, in the absence of side-effects, the only difference is that a non-strict language contains more expressions which do not denote bottom -- insofar as the two evaluation strategies both do not yield bottom, they agree.

Simon's statement also fits in a very important historical context. At the time of the birth of Haskell (1987), there were a panoply of non-strict functional languages -- not only Miranda, but Lazy ML, Orwell, Clean, and many others. Aside from certain syntactic variations, they all were very much the same language. Which was precisely the motivation for the Haskell Committee to form. For more on this, see "A History of Haskell: being lazy with class": http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/.

$\endgroup$
5
$\begingroup$

I think SPJ is correct in saying this for core semantics.

While there are many advanced subtleties one can point to, such as defaulting to strict or lazy evaluation, as you mention, the details of type systems or how larger units of code are organized (modules, structures), the mental model of a program is very similar across functional languages.

Choose some particular specified function and write it in all the languages your are comparing, and you will likely find that the structure and semantics of the different implementations will be very similar for all of them, including level of abstraction, data structures chosen, they'll all assume garbage collection, etc.

On the contrary, say a C implementation vs a Smalltalk implementation of the same function will likely have a different structure (functions and low-level data structures vs objects), focus on different levels of detail (for example, manual memory management vs garbage collection), and operate at different levels of abstraction.

The world-view of the functional language design space is simply more specific and coherent than that of the "imperative programming" space which lumps together assembly, C, Smalltalk, Forth, and dozens of other radically different languages into one catchall category.

$\endgroup$
3
$\begingroup$

I think Simon PJ's quote is a bit of an off-hand remark actually.

Similarity between languages is determined by what consensus has been generated in the researcher and language designer community. There is no question that there is a higher degree of consensus in the functional programming community than in the imperative programming community. But it is also the case that the functional programming languages are mostly designed by researchers rather than practitioners. So, it is natural for such consensus to emerge.

Almost all functional languages use garbage collected memory management and recursive data structures (originated by Lisp), most of them use "algebraic" data types and pattern matching (originated by Hope), a lot of them use higher-order functions and polymorphic functions (originated by ML). Beyond that, the consensus disappears. They differ in module systems used, how state change operations and other computational effects should be handled, and the evaluation order (call-by-name vs call-by-value) etc.

Imperative programming languages generally use nested control structures (originated by Algol 60), and type systems (originated by Algol 60, but consolidated by Algol 68). They generally have cumbersome surface syntax (again going back to Algol 60), make half-hearted attempts to handle higher-order functions and polymorphic types, and differ in their support for block structure and module systems. There is probably more uniformity in the evaluation order because, after the 60's, call-by-name has essentially disappeared from imperative languages.

So, it is not clear to me that the difference between the two classes of languages in their uniformity is all that great.

It would be really worthwhile to bring the cleaner and uniform notations of functional programming into imperative programming languages. I see that Scala has made a beginning in that direction. It remains to be seen whether the trend will continue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.