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.

21 comments:

sigfpe said...

Haskell and OCaml are little different to Scala wrt currying. There is no automatic currying in Haskell, merely a convention that we write functions of type a -> b -> c instead of (a,b) -> c. We can get the same error in Haskell by writing

> f (a,b) = a+b
> f (1)

The way you make this work in Scala is the same way you make it work in Haskell - you showed how in your footnote.

Not that I know any Scala...

Robert Fischer said...

I've addressed these issues in the comment to my post. In particular, the partial function application and the distinction between a singleton object and a module are more problematic than you're selling here.

Maybe if I learned Erlang, I'd have a similar thing to say about it. Or maybe not. I don't know: I've never actually used it.

Haskell and OCaml, though, have the same feel when you code them. Lisp has a different feel which is closer to Haskell/OCaml than Scala/Java, but decidedly different. I get into the nature of that feeling in my most recent comment in my blog post.

I am interested in your "but that's ridiculous" dismissal -- why is it ridiculous to assert Erlang is not a functional language? Your answer there might help me discern more about this "feeling" I'm digging at and tried to call out in my post.

And sigfpe, the distinction between a -> b -> c and (a,b) -> c is more than a convention. Those are two wildly different functions -- in the second case, you've got a tuple.

sigfpe said...

The types a -> b -> c and (a,b) -> c are isomorphic. Because of this you can write functions either way. It's purely a convention in Haskell that most people write functions in the former way. Despite what many people claim, there's no automatic currying in Haskell. The situation is the same in Scala and Haskell. You can write curried functions or uncurried functions in both.

James Iry said...

@Robert,

How can "a->b->c" and "(a,b)->c" be "wildly different" when currying and uncurrying create the well known isomorphism between the two. Here in Haskell because I don't know OCaml:

curry :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x,y)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (x,y) = f x y

These transformations do not change the function being computed. So the curried and uncurried forms can't be "wildly different."

Also, if you view the types as logical propositions then note that (a → (b → c)) = ((a ∧ b) → c).

James Iry said...

heh. I'm not trying to repeat sigfpe. He and I were typing at the same time.

Reginald Braithwaite said...

I can's speak for Clojure or Arc, but Common Lisp and Scheme are not functional languages in that both celebrate programming by side-effect.

Sure, both CL and Scheme have first-class functions, but isn't referential transparency an important characteristic of functional languages?

Jeffrey Massung said...

Pure Lisp is functional, but Common Lisp is not; neither is Scheme.

I understand your post, and I agree with most of it. I don't understand how the definition of "functional language" has changed so much over time to include features. Functional programming isn't about features, but the lack there-of, and what that adds (more is less).

A functional language amounts to a language where f(x) == f(x)... always. And, it's possible to prove that because there is no [mutable] state within f(). That's pretty much it, folks. Everything else is a red herring, a feature added because it's nice. Such features include lazy evaluation, currying, and many others.

A program can written in any language to act functional, and there are many benefits to doing so. But, that doesn't make the language functional.

I don't know Scala, but from what I've read, it's very much functional.

Good post, though.

MononcQc said...

Erlang supports currying via anonymous functions/closures. For the shell:

1> F = fun(A) -> fun(B) -> A + B end end.
2> F1 = F(1).
3> F1(2).
3

The problem with Erlang though is mainly syntactic:
4> F(1)(2).
* 1: syntax error before: '('
4> (F(1))(2).
3

There would be some problems by having automatic currying in Erlang: first is arity, where module functions are identified with their names AND number of arguments (used for pattern matching, defining default values, etc).

The biggest problem would be from the point of view of distributed code on many servers. Sending messages is a side effect in itself and forces the evaluation of a function in ideal circumstances. You can still send closures over the wire, but the problem is that when doing things that way, you make it necessary to send what's shared in the representation. Function closures can contain a LOT of sharing in their representations and this can mess up the memory allocation on the receiver's side. As such, sending evaluated data is desirable in Erlang and it's a somewhat decent argument supporting its eager evaluation: it's not necessary (one could manually force evaluation), but having the usually most efficient thing done for you does help.

In my opinion, Erlang is purely functional (with a sometimes annoying syntax) when done sequentially, but as soon as you enter message passing and concurrency, it becomes a mix of many concepts: actors for the processes; modules become nearly OO, especially when parametrized, etc.

Leon P Smith said...

Good rebuttals, James. By these criteria, you could argue that C is a functional language as well.

So what is a functional versus imperative language? I don't think that languages can really be so classified, rather, only specific programs are functional or imperative.

In my view, functional means an avoidance of side effects, as evidenced by the term "purely functional". I know others include higher-order functions in the definition of "functional", butt imperative constructs can usefully be higher-order as well.

One can certainly write imperative Haskell or Scheme or Erlang code, and one can almost write C in a purely-functional style. (Alhough purely functional C is rarely practical, I daresay a more functional C is often both attractive and practical.)

You can discuss the level of support for functional styles, e.g. OCAML (very good), Scala (pretty good), Python (ok, but half-hearted), C (rather poor), or most assemblers (non-existent, except in some organizational sense). But by declaring a language as "functional", I think it's really saying "most people who use this language use it to write functional programs", and similarly for imperative languages. It's more an issue of prevailing idioms.

Unknown said...

Whether Erlang is functional or not never mattered. It's pragmatic first and foremost.

http://12monkeys.co.uk/2009/05/16/erlang-is-pragmatic.html

Monoidus said...

Fischer confusion obviously comes from the fact that those languages aren't purely functional, they aren't even functional. They merely offer some degree(some more, some less) of support for FP paradigm.

Several languages like Scala, Erlang, Groovy, Ruby and even Java have some support for Functional Programming. That does not make those languages functional like Haskell or Miranda.

It's like Java. Java has and excellent support for OO paradigm and actively converges its users towards it, but Java itself isn't purely OO like Ruby and you're still allowed to program in Java procedurally exactly like c code.

Anonymous said...

Just because "a->b->c" and "(a,b)->c" are an isomorphism doesn't make them equivalent in Haskell's type system:

Prelude> let fadd a b = a + b
Prelude> :t fadd
fadd :: (Num a) => a -> a -> a
Prelude> let tadd (a,b) = a + b
Prelude> :t tadd
tadd :: (Num t) => (t, t) -> t

It seems a little disengenuous to claim that Haskell doesn't support automatic currying by defining a function that expects a tuple value type (obviously function definition in Haskell does not include parentheses around parameters) and then calling it with an integer.

Loup Vaillant said...

"Automatic currying" is a bad name to begin with. When they say "X has automatic currying", most people actually mean "X encourages the curried form".

In Scala, Erlang, Lisp etc, there is a syntactic burden to write and use function in curried form. In Ocaml, Haskell, Miranda etc, there is a syntactic burden to write functions in uncurried form.

That's it. Now I would like to see a definition of true automatic currying, and an example if possible.

Anonymous said...

@Loup Vaillant

I can't speak for true automatic currying, but some Haskell compilers (e.g. GHC) will do automatic 'uncurrying'. That is, at the level of the compiled code and the runtime, there is a distinction between functions which get one argument at a time vs all (or many) at once, and the compiler will do analysis to try to pick the best representation based on usage.

It's not really uncurrying, because un/currying is a type-system matter and so it's not safe to alter types. Rather it's "un-partial application" as it were. GHC also does other tricks like automatically unpacking tuple arguments when it can, so at the representation layer there's no difference between unpacked uncurried arguments and un-PAed groups of arguments.

Writing a true automatic un/currying language wouldn't be difficult, just add in implicit coercions like C made so popular. Writing one that had other nice properties like being sane or efficient would be harder :)

Jason Dusek said...

@ Hasan Veldstra : That really has nothing to do with what we are talking about. No one is arguing that Erlang isn't any good.

Anonymous said...

There's too much confusion arising
when using the phrase
"language Blah is a functional language". For languages like
Scala and for that matter Perl,
one should say that they have
"functional characteristics" or that
they "support functional modes of
programming". From what I have seen I would not think that Scala is
primarily a "functional language".

Anonymous said...

Brainfuck (http://en.wikipedia.org/wiki/Brainfuck) is missing!!!

James Iry said...

Even at the time I wrote this Scala supported curried function definition. It's in my footnote.

Asdasd said...

This is one of the most important reasons why carrera

sunglasses
are worn and you should never compromise on this aspect of wholesale Cocoons Sunglasses .Update your looks and transform your style with extraordinary collection of Wholesale Ray Ban Sunglasses .Black shades are no longer in demand by

fashion enthusiasts as earlier days. Lenses cebe sunglasses these days

acquire the full-colour behavior, from a gradient lens which is actually a blend of more than one color with different effects adidas sunglasses . Mirror-coated lenses also knows as a flash lens, termed

as ghosngeti Sunglasses is of silver is again in demand. These ghose lenses are among best-sellers, one vvsdfswesdfsdfgs can find them in blue,

green, purple and pink as well.

John Walling said...

The history of programming languages without mentioning Forth or Mumps, is like the history of breakfast cereals without mentioning Fruit Loops or Chocolate Frosted Sugar Bombs.

Ed Schneeflock said...

I will suggest that Erlang can do exactly what OCaml does though the syntax is not as clean. Here in the Erlang shell

X = fun(A, B) -> A + B end.
Y = fun(A) -> apply(X, [1, A]) end.
Y(2).