Friday, May 15, 2009

Erlang is Not Functional

Robert Fischer claims Scala is not a functional language. But if you go by his post then Erlang isn't either.

Modules

Fischer says

In OCaml, we define a function like this:
let f x = x + 1;;
In Scala, though, we define the function somewhat differently:
object SomeHolderObject {
  val f(x:int):int = { x + 1 }
}

Now some Erlang

-module(SomeHolderModule).
-export([f/1]).

f(X) -> X + 1.

Erlang requires a function to be defined in a module. Scala calls a module an "object."

Currying and Partial Application

Fischer says [1]

For the shut-out, let's see in Scala makes functional programming easy. Let's start with my favorite functional language stunt: currying. OCaml, you're up to bat first.
let x a b = a + b;;
let y = x 1;;
y 2;; (* 3 *)
Not too shabby. Scala, show your stuff!
def x(a:Int, b:Int) = a + b 
def y = x(1)
/*  ERK!   FAIL!
<console>:5: error: wrong number of arguments for method x: (Int,Int)Int
       def y = x(1)
               ^
*/

And here it is in Erlang

- module(test).
- export([f/2]).

f(X,Y) -> X + Y.

1> c(test).
{ok,test}
2> test:f(1).
** exception error: undefined function test:f/1

Algebraic Data Types

What about Algebraic Data Types, common to functional languages - including my beloved OCaml variant types?

Erlang doesn't have them. You can fake them with tuples and atoms and such, but they just aren't part of Erlang.

Conclusion

Clearly, by Fischer's definition, Erlang is not a functional language.

But that's ridiculous.

David MacIver has an excellent post suggesting that there's a problem of language. Fischer hasn't defined what he means by "functional language" other than "feelings" so we're left with something nebulous.

I think MacIver is right, but Fischer does seem to have an informal definition. His definition of "functional language" is "OCaml". His post compares Scala to OCaml and concludes that because Scala is not OCaml Scala must not be functional.

Yet if I take his specific points I can find other functional languages, like Erlang, that are not OCaml either and therefor not functional either.

In fact, if I look at Common Lisp, Scheme, Clojure and Arc I find that they violate most of his demands too. So the whole Lisp family isn't functional either.

Fischer has fallen prey to a common mistake. He's overgeneralized from one datapoint. It's as if a Scheme programmer concluded that OCaml isn't functional because it doesn't have hygienic macros or a Java programmer concluded that Ruby isn't object oriented because it doesn't have inner classes.

Footnotes

[1] Actually, you can write "def f(a:Int)(b:Int) = a + b" in Scala if you want a curried function or you can write "val y = f(1, _)" if you want to partially apply an uncurried function. So Fischer blows major points here.

Thursday, May 7, 2009

A Brief, Incomplete, and Mostly Wrong History of Programming Languages

1801 - Joseph Marie Jacquard uses punch cards to instruct a loom to weave "hello, world" into a tapestry. Redditers of the time are not impressed due to the lack of tail call recursion, concurrency, or proper capitalization.

1842 - Ada Lovelace writes the first program. She is hampered in her efforts by the minor inconvenience that she doesn't have any actual computers to run her code. Enterprise architects will later relearn her techniques in order to program in UML.

1936 - Alan Turing invents every programming language that will ever be but is shanghaied by British Intelligence to be 007 before he can patent them.

1936 - Alonzo Church also invents every language that will ever be but does it better. His lambda calculus is ignored because it is insufficiently C-like. This criticism occurs in spite of the fact that C has not yet been invented.

1940s - Various "computers" are "programmed" using direct wiring and switches. Engineers do this in order to avoid the tabs vs spaces debate.

1957 - John Backus and IBM create FORTRAN. There's nothing funny about IBM or FORTRAN. It is a syntax error to write FORTRAN while not wearing a blue tie.

1958 - John McCarthy and Paul Graham invent LISP. Due to high costs caused by a post-war depletion of the strategic parentheses reserve LISP never becomes popular[1]. In spite of its lack of popularity, LISP (now "Lisp" or sometimes "Arc") remains an influential language in "key algorithmic techniques such as recursion and condescension"[2].

1959 - After losing a bet with L. Ron Hubbard, Grace Hopper and several other sadists invent the Capitalization Of Boilerplate Oriented Language (COBOL) . Years later, in a misguided and sexist retaliation against Adm. Hopper's COBOL work, Ruby conferences frequently feature misogynistic material.

1964 - John Kemeny and Thomas Kurtz create BASIC, an unstructured programming language for non-computer scientists.

1965 - Kemeny and Kurtz go to 1964.

1970 - Guy Steele and Gerald Sussman create Scheme. Their work leads to a series of "Lambda the Ultimate" papers culminating in "Lambda the Ultimate Kitchen Utensil." This paper becomes the basis for a long running, but ultimately unsuccessful run of late night infomercials. Lambdas are relegated to relative obscurity until Java makes them popular by not having them.

1970 - Niklaus Wirth creates Pascal, a procedural language. Critics immediately denounce Pascal because it uses "x := x + y" syntax instead of the more familiar C-like "x = x + y". This criticism happens in spite of the fact that C has not yet been invented.

1972 - Dennis Ritchie invents a powerful gun that shoots both forward and backward simultaneously. Not satisfied with the number of deaths and permanent maimings from that invention he invents C and Unix.

1972 - Alain Colmerauer designs the logic language Prolog. His goal is to create a language with the intelligence of a two year old. He proves he has reached his goal by showing a Prolog session that says "No." to every query.

1973 - Robin Milner creates ML, a language based on the M&M type theory. ML begets SML which has a formally specified semantics. When asked for a formal semantics of the formal semantics Milner's head explodes. Other well known languages in the ML family include OCaml, F#, and Visual Basic.

1980 - Alan Kay creates Smalltalk and invents the term "object oriented." When asked what that means he replies, "Smalltalk programs are just objects." When asked what objects are made of he replies, "objects." When asked again he says "look, it's all objects all the way down. Until you reach turtles."

1983 - In honor of Ada Lovelace's ability to create programs that never ran, Jean Ichbiah and the US Department of Defense create the Ada programming language. In spite of the lack of evidence that any significant Ada program is ever completed historians believe Ada to be a successful public works project that keeps several thousand roving defense contractors out of gangs.

1983 - Bjarne Stroustrup bolts everything he's ever heard of onto C to create C++. The resulting language is so complex that programs must be sent to the future to be compiled by the Skynet artificial intelligence. Build times suffer. Skynet's motives for performing the service remain unclear but spokespeople from the future say "there is nothing to be concerned about, baby," in an Austrian accented monotones. There is some speculation that Skynet is nothing more than a pretentious buffer overrun.

1986 - Brad Cox and Tom Love create Objective-C, announcing "this language has all the memory safety of C combined with all the blazing speed of Smalltalk." Modern historians suspect the two were dyslexic.

1987 - Larry Wall falls asleep and hits Larry Wall's forehead on the keyboard. Upon waking Larry Wall decides that the string of characters on Larry Wall's monitor isn't random but an example program in a programming language that God wants His prophet, Larry Wall, to design. Perl is born.

1990 - A committee formed by Simon Peyton-Jones, Paul Hudak, Philip Wadler, Ashton Kutcher, and People for the Ethical Treatment of Animals creates Haskell, a pure, non-strict, functional language. Haskell gets some resistance due to the complexity of using monads to control side effects. Wadler tries to appease critics by explaining that "a monad is a monoid in the category of endofunctors, what's the problem?"

1991 - Dutch programmer Guido van Rossum travels to Argentina for a mysterious operation. He returns with a large cranial scar, invents Python, is declared Dictator for Life by legions of followers, and announces to the world that "There Is Only One Way to Do It." Poland becomes nervous.

1995 - At a neighborhood Italian restaurant Rasmus Lerdorf realizes that his plate of spaghetti is an excellent model for understanding the World Wide Web and that web applications should mimic their medium. On the back of his napkin he designs Programmable Hyperlinked Pasta (PHP). PHP documentation remains on that napkin to this day.

1995 - Yukihiro "Mad Matz" Matsumoto creates Ruby to avert some vaguely unspecified apocalypse that will leave Australia a desert run by mohawked warriors and Tina Turner. The language is later renamed Ruby on Rails by its real inventor, David Heinemeier Hansson. [The bit about Matsumoto inventing a language called Ruby never happened and better be removed in the next revision of this article - DHH].

1995 - Brendan Eich reads up on every mistake ever made in designing a programming language, invents a few more, and creates LiveScript. Later, in an effort to cash in on the popularity of Java the language is renamed JavaScript. Later still, in an effort to cash in on the popularity of skin diseases the language is renamed ECMAScript.

1996 - James Gosling invents Java. Java is a relatively verbose, garbage collected, class based, statically typed, single dispatch, object oriented language with single implementation inheritance and multiple interface inheritance. Sun loudly heralds Java's novelty.

2001 - Anders Hejlsberg invents C#. C# is a relatively verbose, garbage collected, class based, statically typed, single dispatch, object oriented language with single implementation inheritance and multiple interface inheritance. Microsoft loudly heralds C#'s novelty.

2003 - A drunken Martin Odersky sees a Reese's Peanut Butter Cup ad featuring somebody's peanut butter getting on somebody else's chocolate and has an idea. He creates Scala, a language that unifies constructs from both object oriented and functional languages. This pisses off both groups and each promptly declares jihad.

Footnotes

  1. Fortunately for computer science the supply of curly braces and angle brackets remains high.
  2. Catch as catch can - Verity Stob

Edits

  • 5/8/09 added BASIC, 1964
  • 5/8/09 Moved curly brace and angle bracket comment to footnotes
  • 5/8/09 corrected several punctuation and typographical errors
  • 5/8/09 removed bit about Odersky in hiding
  • 5/8/09 added Objective-C, 1986
  • 5/8/09 added Church and Turing
  • 4/9/10 added Ada (1983) and PHP(1995)