Lambda the Ultimate

It's clear that being a functional vs an imperative programmer obliges a different way to look at problems, e.g. 'what is the chain of function applications which will transform my problem into an answer' versus 'what is the set of steps and decisions I need?'. With the usual corollary that approaching programming in X with Y's mindset will lead to ugliness and future difficulty.

I'm not sure it is really so different. I tend to think the difference between functional and imperative mindsets is more in the data flow than in the control flow. From my (modest) experiments in imperative, functional and 'logic' (Prolog) programming, the operational intuition is actually rather similar, and maps to the given problem. The handling of data and means of abstraction/genericity are more different.

still less is English; both are direct descendants of their respective ancestors, proto-Anglo-Frisian and Early Modern Dutch. They have undergone morphological tsimplification, but so have all the Germanic languages except standard German, which nobody used as a spoken language until about a century ago and was therefore in the deep freeze.

There are or were Afrikaans-based creoles spoken in South Africa, though, which may have influenced the development of Afrikaans.

Afrikaans is not a creole, still less is English; both are direct descendants of their respective ancestors

Aside from the fact that this would be flamebait even in a linguistics community, this is also way OT.

Unless you can think of a way that a PL can be a creole. ;-)

Given the definition (according to Wikipedia), that a creole language is "a stable, full-fledged language that originated from a pidgin or combination of other languages.", I could argue that Ruby fits the bill, as does one of its ancestors, Perl.

That's not offered as deprecatory; the originators of both languages have been very explicit about being inspired by, or using features borrowed from, a variety of prior languages.

Given that programming languages are intentionally created artifacts, this is probably more common than our use of the word "language" would lead us to assume. In her 1972 paper, Programming Languages: History and Future, Jean Sammet lists as one of the reasons for programming language proliferation, "Facilities of several languages are best combined into a single new language." (item 3 of 7 in section 2.2).

[The hypothesis that English is a creole] as Sarah Grey Thomason and Terrence Kaufman have shown in LANGUAGE CONTACT, CREOLIZATION, AND GENETIC LINGUISTICS (1988), rests on an incomplete understanding of creolization and a shaky grasp on the history of English. There is a wide range of language contact situations, from casual contact to deep structural interference; English is by no means the most striking of these cases. It looks like a creole only if one ignores this range of phenomena and labels any case of moderate interference as creolization.

The sci.lang FAQ (scroll down to qn 20) puts it nicely

Charles, you didn't just quote a newsgroup FAQ as an authoritative source did you?

Well, if you did it, I guess it's OK then. That's great! I'm looking forward to being able to resolve future discussions on LtU by referring to the comp.lang.flamewar FAQ. ;-)

A point about creoles is that they are the native languages of at least some speakers.

I agree that the concept "native language" as it applies to HL does not apply to PLs.
For those interested, there was a previous LtU discussion about the "native language" status of PLs.

Charles, you didn't just quote a newsgroup FAQ as an authoritative source did you?

Well, no, rather as a text that had a high concentration of pithiness. Because my wife is a professor of linguistics, I've had a fair bit of contact with views like it's a fun idea that I sometimes use to annoy students, but it's been debunked. But I wouldn't like to try attributing to them my dim recollections of what they said.

Well, no, rather as a text that had a high concentration of pithiness.

Please take my previous comment as no more than a gentle pulling of the leg.

My stomach always churns whenever an LtU thread gets off of strictly PL topics, especially onto linguistics, because the path to lunacy tends to be much shorter, and unlike PL topics where many of us know enough to assess the merits and weaknesses of various sources, shakier stuff can be taken as gospel. Compound this with the fact that any real discussion to illuminate problems will inevitably go OT, and you can understand why this topic has me reaching for the seltzer.

One substantive point that I will raise, because I think it might have applications to certain PL discussions:

it's a fun idea that I sometimes use to annoy students

To me, this raises the most interesting question about this topic: why does the idea annoy people. Just as with some of the perennial PL back-and-forths, this may tell us more about the issue then any of the associated technical details.

I love that quote :-) thanks for sharing.

For a PL or any industry standard the army would be capital, and the navy one or more corporations supporting it.

Unfortunately, there's no need to treat "army" and "navy" as stand-ins. Which programming language researcher has not gotten a grant from the DARPA and the ONR, in the US at least? Probably those fringe elements working on dialects and not languages :P

a dialect with proponents in custom T-shirts.

(from the ELCON10 conference, T-shirts are important ;P )

(MLton link)

()

Memory management.

Memory management.

I thought of that one too, but couldn't think of a language that required you to express all of your memory management.

The obvious candidates, C and C++, require it in practice but not by the design of the language per se, since they both allow many cases of memory management to happen automagically, and in theory (in a better world than ours) you could avoid it completely.

e.g. for C, you can use the stack as "poor man's garbage collection" or in C++, where destructors will be called automatically when the object goes out of scope.

Can you think of a language that does uniformly require explicit memory management?

Cyclone in some cases, which is enforced by region typing. It's not "uniform" in the sense that it's required everywhere however.

Well, I didn't say all memory management... Even having to be explicit about heap allocation is a significant bifurcation in the design space, imho. But if you want more, I'd say Forth might fit the bill. It's not so different from C, but since the stacks are manually managed, I would say all memory management is pretty much manual.

if anyone can think of other features of PLs that have a similar effect of requiring that you are explicit about some property or behaviour, thereby making programmers in a language with that feature especially aware of that property or behaviour.

Racket (and I think most implementations of records for Scheme) require you to say what type of object you're operating on every time you extract a field - e.g. (point-x p). Typed languages like Java don't require that, and neither do languages with hash-based objects like Python.

I just thought of more. Turns out it's not hard once you get going.

C++ requires you to be explicit about constness.

C requires you to be explicit about errors at every function application that can generate one.

Java requires you to be explicit about whether a method can raise or pass along an exception.

ASM requires you to be explicit about how you encode objects in memory.

Python requires you to be explicit about which object you're operating on (i.e. no implicit "self" or "this").

Scheme and Racket require you to be explicit about mutation; in contrast, in most imperative languages, whether an assignment mutates or merely constructs is implicit.

Haskell requires you to be explicit about any kind of computational effect.

Languages without lambdas require you to explicitly construct closures; i.e. you have to say "I'm closing over this value" whenever you do it.

Does C# require you to declare that you're overriding a method? I seem to recall something like that.

In C++, you can leave everything non-const if you want, so that const-ness is implicit. You will have issues at the boundaries of standard and external libraries, but nothing that const_cast won't fix.

In C, sadly, there is no requirement to be explicit about errors at function application, or at least none that the language can enforce. That's one reason why bugs occur.

I disagree on ASM. You'd better have your layout documented somewhere, but just accessing what you need directly when you need it is IMO an example of implicit encoding - ASM doesn't require you to put a label on every significant chunk of a structure, and typically provides no way to label a specific bit-range.

In Haskell, pretty much all code could be written in monadic form, irrespective of whether it has side-effects or not. Exceptions include basic arithmetic operators, but even in C, the '+', '-' etc operators have no side-effects.

The point about "Languages without Lambdas" is more "Languages without Closures" really. Nested procedures are a common case which is not a lamda, but which requires (implicit) closures.

Any language that allows you to override a method requires you to declare it. The override declares its own existence, after all. But I think you're thinking of C++, where a method must be declared 'virtual' if any derived class needs to override with run-time dispatch. In C# and Java, IIRC, methods are "virtual" by default, but overriding can be banned by declaring the method "final".

"virtual" vs. "final" shows a kind of dichotomy. Often, making one thing explicit means the opposite thing is implicit, which makes a hole through which everything can be implicit if the developer is sufficiently insane to exploit it.

I think I once saw a coding standard mandating against the use of "const" because it was too much hassle. Not anywhere I worked - may have been a daily WTF or similar.

In Haskell, pretty much all code could be written in monadic form, irrespective of whether it has side-effects or not. Exceptions include basic arithmetic operators, but even in C, the '+', '-' etc operators have no side-effects.

I'm not convinced. When giving a type signature for your code, you still have to describe what monads are used. If you use specific monads, you have to be explicit about it, and if your code is polymorphic in the monad used, then it's pure.

Note that "being explicit about" is not an absolute, formal definition. "Languages differ essentially in what they must convey" does *not*, in practice, refers to something absolutely mandatory.
An example in the original article is that, in language without neutral gender, or when using words with no neutral form, you have to be explicit about the sex of the people you refer to. The example is the translation of "a neighbor" in french or german (voisin/voisinne, Nachbar/Nachbarin). But you could, by using a delicate periphrase, be explictely implicit about it (la personne qui est ma voisine; die Person, die ...).

Similarly, the fact that you *can* express effects implictely in Haskell, for example by using the "do" notation, does not contradict the fact that Haskellers reason explictely about effects when speaking, and that it impacts the way they think about programming and programs, even when telling a story to an other computer or human that does not speak their native language.

That is, you can declare as many monads as you want, and each monad can only go where you've explicitly sent it. But the IO monad isn't just another monad. It's perfectly plausible to pass the IO monad pretty much everywhere, in which case you may as well be writing Pascal. You'd be insane to do it, true, but it's possible.

I committed the all-too-common error of replying after reading the first paragraph.

In any case, my post wasn't about real-world practice - it was about what's possible, irrespective of sanity. In Haskell, passing the IO monad explicity *allows* you to have side-effects - it doesn't force you to have side-effects even in the rarest special case.

Pedanting though this is, there is a point to it. Tell people that pure functional languages at best imply (rather than directly representing) algorithms, and they will tell you that you can translate imperative languages line-for-line directly into Haskell. And so, indeed, you can - providing you pass that IO monad to every translated function to enforce time ordering irrespective of whether there are any side-effects or not.

Any language that allows you to override a method requires you to declare it. The override declares its own existence, after all.

I don't know about C#, but in Scala at least, you have to declare that the method is overriding something (not just declare the overriding method). "def foo()" won't work if the class inherits a foo()-method from somewhere, and "override def foo()" won't work if it does not inherit a foo()-method.

One way Tim Budd put Jakobson's maxim:

... for both computers and natural languages it is the case that the language will direct thoughts, but cannot proscribe thoughts.
~ Tim Budd, Multiparadigm Programming in Leda, Ch 1, Pg 7

Budd did not cite Jakobson directly, though. He did cite a number of cool books, however:

• The Great Eskimo Vocabulary Hoax and Other Irreverent Essays on the Study of Language by Geoffrey K. Pullum, which debunks the Snapple fact that Eskimos have many words for "snow".
• The Language Instinct: How the Mind Creates language, which argues against Sapir-Whorf Hypothesis.
• The Alphabet Effect by Robert Logan, which argues the benefits of a linear, sequential alphabet over heiroglyphics and ideographics, including the advancments it has allowed in logic and science.
• The Fifth Generation Fallacy: Why The Japanese is Betting Its Future on Artificial Intelligence by J. Marshall Unger, where Unger argues the Japanese language itself had a huge impact on the Japanese 5GL Project.

Speaking of goto's, does anyone know of an online copy of Knuth's "Notes on avoiding go to statements", 1971, Information Processing Letters? I think that is the paper I am compelled to bring up whenever someone mentions goto, but I am not sure and cannot find my copy of the paper I am looking for.

(I'm fairly sure it was Knuth, and it's not "Structured programming with go to statements".)

Notes on avoiding go to statements is not available online (that I am aware of), but it is reprinted in Knuth's Selected Papers on Computer Languages.

Yet, a few years later Rich De Milo and others published a paper showing that if you completely disposed of goto and wrote programs in the style suggested by researchers, that some of these programs would have exponential inflation in the number of statements. The 1970s and 1980s Goto vs. Goto-free design was one of the last big language design wars, but very few people seem to actually think through the tradeoffs that are made in goto-free design.

In modern languages with properly implemented tail calls and continuations (or possibly exceptions), what tradeoffs are those? I doubt the De Milo paper's conclusions would hold up in that context.

That "design war" was pretty much won in 1977 by Lambda: The Ultimate GOTO, it's just that as usual, the future is unevenly distributed. Old-style uncontrolled gotos are only needed when your programming language is rigidly stack-based and functions always have to return to where they were called from.

Let's see what Dijkstra said?: Goto Statement Considered Harmful.

In [2] Guiseppe Jacopini seems to have proved the (logical) superfluousness of the go to statement. The exercise to translate an arbitrary flow diagram more or less mechanically into a jump-less one, however, is not to be recommended. Then the resulting flow diagram cannot be expected to be more transparent than the original one.

Somehow Dijkstra has been connected with Jacopini and Bohm's proof, even though he only mentions it in passing at the end of his essay. I suppose people wanted a mathematical proof of goto elimination, as if it meant anything in terms of program clarity. Dijkstra was clear such a mathematical proof did not exist at the time of him writing that letter (that he was aware of). David Harel has an excellent essay where he traces the history of The Structured Program Theorem and other "folk theorems", titled On Folk Theorems:

Indeed, it seems that H.D. Mills who, in his unpublished lecture notes, termed the result of [15] "The Structure Theorem" was one of the driving forces behind the glorification of Bohm and Jacopini's result, which he reproved and discussed in highly attended lectures and seminars in the following years.

[...]

It is interesting to note that both the local transformation of Bohm and Jacopini [15] and Mirokowska [70], and the aforementioned global one fail, by their very nature, to preserve the structure of the original flowchart. Ironically, though, they are proofs of a so-called "structuring result".

As a brief aside, my interest in Bohm and Jacopini's paper was spurred by my hobby project of reading the papers on Benjamin C. Pierce's Great Works in Programming Languages, which also mentions Knuth's 1974 Structured programming with 'go to' statements paper and Steele's Rabbit thesis.

Anton van Straaten wrote:

That "design war" was pretty much won in 1977 by Lambda: The Ultimate GOTO, it's just that as usual, the future is unevenly distributed. Old-style uncontrolled gotos are only needed when your programming language is rigidly stack-based and functions always have to return to where they were called from.

It is a great paper, but Steele actually shifts the problem by giving an engineering perspective, comparing Lisp to Fortran and using the engineering results derived from his optimizer to show that Lisp could be more efficient than Fortran. At the time, it was widely believed that procedure calls were too expensive, and many computer scientists were dissuaded from persuing interesting control structures because other scientists believed they could not be efficiently implemented. (In Steele's Evolution of Lisp paper, he channels Hewitt in mentioning possibility lists as one such idea Daniel Friedman had but was dissuaded from persuing.) Steele also argues for a conceptual change in how we think about flow control, going so far as to argue we rename tail-call to tail-transfer, since that better approximates the concept. Steele also argues that languages should have more than one construct with equivalent conceptual meaning. In other words, the representation should be user-definable, a very progressive, object-oriented view of programming language design for the time.

Harel doesn't mention Steele's paper, unfortunately, but he does mention how the flowcharts Structured Program Theorem can be progressively generalizez and ultimately traces it back to Kleene.

In a nutshell, there may be better people to listen to on this subject than Dikstra, and more intellectual content than a paper everyone cites but doesn't bother to even read, just because they have an urge to blog and need something to blog about and, oh, goto seems topical for whatever reason.

Of the most interesting remarks on Goto I've found, Knuth's examples as well as his mentioning of Horning's XPL compiler and Schorre's work on Meta-II are probably the most delightful (for their practicality), and Alan Kay cites Meta-II as one of the biggest inspirations of his career, in serving to understand the "monsterous bug" in Lisp 1.5.

You read too much into my subject line. I apologize for any confusion I may have caused, but you might have noticed that the Drupal-required subject lines on LtU are occasionally used in ways that aren't necessarily intended as an actual argument in whatever discussion is taking place.

Still, Dijkstra's ultimate point was valid, i.e. gotos are harmful and unnecessary, at least in high-level languages. He was ahead of his time in making that case, and his argument and specific conclusions suffered somewhat from that. Our critical perspective on this today has the benefit of a great deal of hindsight, decades of research and experience, and a rather different landscape when it comes to programming languages, programs, and computers.

(On the latter point, try to place yourself in 1968 technologically, and imagine what you might know about computer programs, and how you would know it. 1968 was the year that DRAM was patented, and the following year saw a small new company named Intel building the whopping 1Kbit RAM chip - 128 bytes - a breakthrough in semiconductor memory which led to the downfall of magnetic core memory where you could actually see individual bits easily with the naked eye.)

In a nutshell, there may be better people to listen to on this subject than Dikstra, and more intellectual content than a paper everyone cites but doesn't bother to even read

I hope that on LtU, amongst regulars at least, we can take for granted that we've actually read such papers, and understand their historical context and limitations.

Steele also argues for a conceptual change in how we think about flow control, going so far as to argue we rename tail-call to tail-transfer, since that better approximates the concept.

This is the point I was getting at in my actual comment. (I don't recall Steele's advocating the term "tail-transfer", though - where in the paper is that?)

With tail calls, you have a much more principled version of goto, which eliminates the need for most kinds of goto. It also encourages goto targets to be abstracted as functions, which tends to improve the structure of programs, often quite dramatically when compared to a goto-based version.

Steele actually shifts the problem by giving an engineering perspective

As you observe, he was responding to the prevailing engineering perspective at the time, but his observations and conclusions go well beyond that, so he does much more than just "shift the problem": he solves it, definitively, and even predicts many aspects of the future of functional programming. He observes that the issue goes beyond engineering:

The use of this style does not depend on procedure calls being cheap or being compiled as tail-recursive branches, though if they are so compiled running time is reduced and less stack is consumed, which are desirable characteristics apart from the issue of style.

He also covers the Boehm and Jacopini theorem you mentioned:

This points up to some extent the ultimate futility of the Boehm-Jacopini theorem. We can certainly express all programs in a structured form by introducing flag variables, but the preceding series of reasonable transformations merely renders it unstructured again, demonstrating that we had not really made the program structured in nature, but only in form.

Tangentially, he complains about the 1977 equivalent of overzealous blog posts:

The practitioners of programming discipline point with pride to such theorems as that of Boehm and Jacopini, showing that any program can be written using their favored constructs. Such theorems have recently been ballyhooed about to the point of absurdity: "Structure programming is based on the mathematically proved Structure Theorem."

He doesn't ignore language psychology and philosophy, which has always been one of his strengths, e.g.:

We believe that the psychological effect of this new method will be the most important, for it does away with the automatic reflexive thought that "procedure calls always return". (Imagine, for example, that we had always thought of GOTO as branching forward and never backward, under the influence of old paper-tape machines. Until we had dispelled this notion, could we ever have seen the abstract pattern of while-do?) Once we realize that procedure calls are semantically a superset of GOTO, we are free to exploit a far more expressive style.

This brings me back to the point of my original comment, which was a response to the claim that "very few people seem to actually think through the tradeoffs that are made in goto-free design." I was wondering what tradeoffs those might be, in a language which implements functions properly. I don't believe there are any tradeoffs significant enough to warrant considering a traditional goto in a high-level language. In other words, Dijkstra was right.

(Caveat: some control flow patterns require something more like continuations, but in those cases "goto" tends to be a terrible solution anyway. A language with properly-implemented functions should almost certainly provide some sort of support for continuations instead of gotos. Haskell provides a nice exmple of allowing first-class continuations to be implemented on top of nothing but function calls and syntactic sugar for function-call-based monads.)

I am going to quote a rather large section since Dr. Dobb's does an awful job archiving stories for later retrieval:

Dijkstra went on to defend this position and to acknowledge that he was not the first to make such observations. But it was this letter that sparked the big controversy in computer science at that time. An entire session was devoted to the topic at the ACM National Conference in 1972. This was organized as a debate; Martin Hopkins of IBM presented the case for the goto, and Bill Wulf of Carnegie-Mellon University presented the case against. (See Hopkins, "A Case for the GOTO," and Wulf, "A Case against the GOTO," both in ACM SIGPLAN Notices, Vol. 7, No. 11, November 1972.)

This was the same year that Dahl, Dijkstra, and Hoare published an elegant little book called Structured Programming (Academic Press, ISBN 0122005503). It was also just before I became a student at Harvard College. I was 17, and I had just gotten a summer job working on MacLisp at MIT. (So, you see, my previous year's experience implementing Lisp for the 1130 really paid off!) The conference was in Boston, so I was able to attend. (I was already a student member of the ACM, thanks to the encouragement of a kindly judge at a science fair.) At the end of the Goto Debate, there was time for audience comments and questions. I can't resist quoting some of my remarks from the transcript of the discussion because they represent my earliest published thoughts on language design:

I'd like to point out that some consideration should be given to how the style of the language can affect not only the readability of the program after it is written but the conceptualization of the program itself as it's being written. The facilities which a language provides can grossly affect the style in which a program is written. For example, I once had to implement Conway's "Life" game on a computer, which involves a large number of parallel matrix operations. Doing it in Fortran and doing it in APL will impose two very different styles on the implementation because APL allows you to think in terms of parallel operations, whereas Fortran doesn't.
(We should remember that this was well before Fortran 90. Modern versions of Fortran do support parallel array operations.)
I also wanted to point out that earlier, the statement was made that if you leave goto in a given language, you will at least have the choice, whereas if you leave it out, you can get in trouble. I'd like to point out that whether or not this choice is made, we should also give consideration to the choice of putting in features, which allow you the choice of the goto. In other words, put in while-do, the case, and so forth, so you will have a choice in both directions.
—ACM SIGPLAN Notices, Vol. 7, No. 11, November 1972, pp. 80-81.

Hard to believe he said that as a 17 year old!

Though Guy Steele may be remarkable, I too implemented the game of life from a copy of the Scientific American at age sixteen or something. It just shows that young people are extremely fast at comprehending stuff.

Thing is, I don't think there's anything inherently difficult about programming, or even language design discussions at the 'goto' level. By now, most discussions from then are interesting only from an historic perspective. I think CS should just be taught (well) in high-school, where I even would prefer an FP course instead of an imperative course to match the algebraic skills developed during math and physics.

Then again, another important take away from the article is that each language is about the same in solving the problems at hand, even if the languages nuances are different. So while the dynamicists and staticists are arguing about nuances, their languages both solve the same set of problems. Correspondingly, I have always been bothered by the toolbox approach to language harmony (this language is good at that, this other language is good at this), it sounds to me like saying French is good for romance and German is good for talking to your dog.

Personally, I've found that languages do shape my thinking, but they also come with conveniences and nuances that I get used to, making language switching a bit more difficult. For example, the transition from Java to Scala as my main PL was fairly quick but there was a few weeks where my mind was still thinking in Java so I had to explicitly retrain myself. Then I made the transition from Scala to C# as my main PL, and given all the conveniences in Scala, this transition was much much harder to get my mind out of Scala thinking.

The whole book is basically about notation.