Wednesday, 29 December 2010

Distinctive traits of functional programming languages

The landscape of functional programming languages is remarkably diverse, with most of the major families having quite distinctive traits and dialects that bring their own quirks. Here are some of the major categorizations:

  • Evaluation strategy: non-strict (Miranda, Haskell) vs strict evaluation.

  • Type system: static (Standard ML, OCaml, F#, Haskell, Scala, C# 3) vs dynamic (Scheme, Lisp, Clojure, Erlang) typing and untyped (Mathematica).

  • Kind of static typing: structural (OCaml) vs nominal (F#, Haskell, Scala, C# 3) static typing.

  • Type inference: Damas-Milner (Standard ML, OCaml, F#, Haskell) vs "local" inference (Scala, C# 3).

  • Destructuring: pattern matching (Standard ML, OCaml, F#, Haskell, Erlang, Mathematica) vs manual deconstruction (Scheme, Lisp, C#).

  • Extensibility of algebraic types: always closed (Standard ML, Haskell) vs optionally closed (OCaml).

  • Pattern matching: linear (Standard ML, OCaml, Haskell) vs unbounded (F#, Mathematica).

  • Run-time code generation: meta-circular evaluator (Scheme, Lisp, Clojure) vs heterogeneous code generation (F# → CIL) vs nothing (Standard ML, OCaml, Haskell).

  • Macros: unhygenic macros (Common Lisp, OCaml, Template Haskell, Mathematica) vs hygenic macros (Scheme) vs no macros (Standard ML, F#).

  • Standardization: standardized (Standard ML, Haskell 98, Common Lisp, Scheme) vs proprietary (OCaml, F#, GHC Haskell, Erlang, Mathematica).

5 comments:

Jules said...

What do you mean by unbounded pattern matching

Flying Frog Consultancy Ltd. said...

@Jules: I mean that you can make the asymptotic complexity of pattern matches in F# arbitrarily high using active patterns but that the complexity is still known.

In Mathematica, you cannot even predict the asymptotic complexity of a pattern match.

James Iry said...

> Evaluation strategy: non-strict (Miranda, Haskell) vs strict evaluation.

Scala has optional non-strict evaluation.

> Type system: static (Standard ML, OCaml, F#, Haskell, Scala, C# 3) vs dynamic (Scheme, Lisp, Clojure, Erlang) typing and untyped (Mathematica).

C# has optional dynamic typing. Arguably so do F# and Scala via upcasting.

> Kind of static typing: structural (OCaml) vs nominal (F#, Haskell, Scala, C# 3) static typing.

Scala has both structural and nominal typing.

> Destructuring: pattern matching (Standard ML, OCaml, F#, Haskell, Erlang, Mathematica) vs manual deconstruction (Scheme, Lisp, C#).

Scala should be included under pattern matching. Clojure has some limited built in pattern matching and much richer pattern matching via libraries.

> Extensibility of algebraic types: always closed (Standard ML, Haskell) vs optionally closed (OCaml).

Scala does optionally closed ADTs

> Pattern matching: linear (Standard ML, OCaml, Haskell) vs unbounded (F#, Mathematica).

Scala's is potentially unbounded due to "extractors" (roughly similar to F# active patterns). GHC Haskell now has "view patterns" which are in the same vein.

> Run-time code generation: meta-circular evaluator (Scheme, Lisp, Clojure) vs heterogeneous code generation (F# → CIL) vs nothing (Standard ML, OCaml, Haskell).

I'm not entirely clear on what you're talking about here. There's nothing precluding ML or Haskell from generating ML or Haskell code and evaluating it. Anyway, for some runtime code generation tasks needed by the runtime Clojure uses "heterogenous code generation". Both Scala and Clojure users can use libraries for "heterogenous code generation" at runtime as well.

> Macros: unhygenic macros (Common Lisp, OCaml, Template Haskell, Mathematica) vs hygenic macros (Scheme) vs no macros (Standard ML, F#).

Clojure has unhygenic macros. Scala has none.

> Standardization: standardized (Standard ML, Haskell 98, Common Lisp, Scheme) vs proprietary (OCaml, F#, GHC Haskell, Erlang, Mathematica).

Not clear on this one. Haskell 98, for instance, has a spec but it's not owned by any big standards body. So Scala would be standardized in that sense. But if it's a question of "how many implementations" then Scala is proprietary. Then again, the code is released under a very liberal open source license so even "proprietary" seems a funny term. Clojure doesn't have a real spec (although it does have very nice documentation). Otherwise Clojure is about like Scala - only one implementation but released under very liberal license.

jay paul said...

Nice post! Can’t wait for the next one. Keep stuff like this coming.

HP - ENVY 15.6" Laptop - 8GB Memory - 1TB Hard Drive - Silver

HP - Pavilion 15.6" Laptop - 4GB Memory - 750GB Hard Drive - Black (15-n030us)

YouLoseBellyFat said...

made huge code archive on Csharp Codings