Distinctive traits of the functional languages

Question

It is known that all functional languages share some basic properties like using functions as basic building block for programs with all the consequences like using recursion instead of iteration. However, some fundamental differences also exist. Lisp uses a single representation for both Lisp code and data, while ML has no standard representation of ML code. Erlang has a built-in actor-based concurrency. Haskell has monads. Haskell makes a distinction in the static type system between pure and impure functions; ML does not.

What are the distinctive fundamental differences between other functional languages (Clojure, F#, Arc, any other)? By fundamental I mean something which influences the way you develop in this language, and not for example, whether it is integrated with some wide-spread runtime.

Answer 1

There are many differences but only two differences I'd categorize as fundamental in that they make a big difference to your development:

1. Dynamically typed vs static, polymorphic type system with algebraic data types and type inference. A static type system restricts code somewhat, but has many advantages:
   • Types are documentation that is checked by the compiler.
   • The type system helps you choose what code to write next, and when you're not sure just what to write, the type system helps you easily and quickly rule out many alternatives.
   • A powerful, modern, polymorphic type system is unreasonably good at detecting small, silly, time-wasting bugs.
2. Lazy evaluation as the default everywhere vs lazy evaluation restricted to carefully controlled constructs.
   • Lazy vs eager has tremendous implications for your ability to predict and understand the time and space costs of your programs.
   • In a fully lazy language, you can completely decouple production of data from decisions about what to do with data once produced. This is especially important for search problems as it becomes much easier to modularize and reuse code.

Answer 2

Functional Programming is a style, not a language construct

Most functional languages have some common principles:

• Immutable objects
• Closures and anonymous functions
• Generic algorithms
• Continuations

But the most important principle is that they usually force you to write in a functional style. You can program in a functional style in most any language. C# could be considered "functional" if you write code like that, as could any other language.

Answer 3

1. Non-strict vs strict evaluation.

2. Static vs dynamic typing.

3. Structural vs nominal static typing. OCaml is the only language I can think of with structural typing (in both objects and polymorphic variants), which closes the gap with dynamic typing by removing the need to define many types (e.g. variant types).

4. Hindley-Milner derivatives vs other static type inference algorithms. SML, OCaml, Haskell and F# use type inference algorithms based upon Hindley-Milner whereas Scala has only local type inference (like C# 3) and requires many more annotations to compile. (Haskell code is often full of type annotations at the function level but most are unnecessary and are added for documentation and to help the compiler in the presence of errors).

5. Pattern matching vs manual deconstruction. SML, OCaml, F#, Haskell, Mathematica and Scheme automate the deconstruction of values.

6. Closed sum types vs only open sum types. SML, OCaml, F# and Haskell allow closed/sealed algebraic types to be defined to strengthen static typing by conveying more specific constraints implicitly. OCaml and F# also allow open sum types whereas SML does not and Haskell requires an elaborate workaround (described by Oleg Kiselyov).

7. Bounded-time patterns. Pattern matching is very fast in SML and (vanilla) OCaml but has unknown performance in F# due to active patterns and even unknown asymptotic complexity in Mathematica.

8. On-the-fly compilation to native code. F#, Lisp and Scheme allow code to be generated, compiled and executed efficiently at run-time.

9. Macros. OCaml, Mathematica, Lisp and Scheme are extensible languages.

10. Standardized vs proprietary. SML, Haskell 2010, Common Lisp and Scheme are standardized languages whereas OCaml, Erlang, F# and Mathematica are proprietary.

Answer 4

Fundamental properties?

• Functional Purity (lack of side-effects)
• As a tie-in from the above, lack of state.
• Pattern-matching in functions

The first is beautiful, the second is an ugly side-effect of the former (pun intended).

The real-world compensation for lack-of-state is what I find to be the biggest differentiator between functional languages.

Those few things give lots of freebies. Most of the time, languages handle memoization.

Answer 5

Off the top of my head:

• lazy vs. eager (aka non-strict vs. strict or call-by-need vs. call-by-value): are function arguments evaluated before the function application, or after, or never?
• pure vs. impure: does the language allow functions to have side effects? Does it have mutable references?
• static vs. dynamic: does the language check types at compile time or runtime?
• algebraic datatypes: does the language support pattern matching over variant types?
• metaprogramming: does the language provide a powerful code generation system?
• concurrency and parallelism: are threads/processes a first-class abstraction? Does the language make it easy to run multiple computations at the same time?
• "exotic" types: how expressive is the static type system? GADTs? Dependent types? Linear types? System F?

Only the first two items are really unique to functional languages (i.e., almost all imperative languages are eager and impure).

Answer 6

I like Chris Conway's answer that states some important axes that help classify different functional languages.

In terms of features of specific languages, I'll pick F# to call out some features not found in many other FPLs:

• Active Patterns: a number of FPLs have algebraic data types and pattern-matching, but the F# feature called 'active patterns' lets you define new patterns that allow you to use pattern-matching syntax on arbitrary data.
• Computation expressions: F# has some beautiful syntactic sugar for authoring monadic code; though the type system cannot express higher-kinded polymorphism (no abstraction over type constructors) so you can't write code for an arbitrary monad M, the code you can write for a fixed monad is very cool, and people write some great comprehensions in the seq{} or async{} monads.
• Quotations: the usual 'code as data for metaprogramming' bit, though F# has an expressive static type system and rich syntax, and I'm not sure how many non-lisps can do this.

In terms of general classification, F# is

• eager (strict, call-by-value; but 'lazy' is a keyword & library and using seq/IEnumerable for some laziness is a common strategy)
• impure (though syntax biases you towards a purer-by-default style)
• static (with type inference, so F# often 'feels like scripting', only with type safety)

Your question is phrased in a way with clear bias against some extra-language pragmatics (e.g. what runtime does it integrate with), but you also ask what "influences the way you develop", and these things do influence that:

• Visual Studio integration means a great editing experience (e.g. Intellisense)
• Visual Studio integration means a great debugging experience (e.g. breakpoints/tracepoints, locals, immediate window, ...)
• REPL for scripting or UI-on-the-fly is hotness (fsi.exe command-line, or "F# Interactive" integrated in VS)
• .NET integration means for most 'X' there's already a library to do that
• side tools like FsLex/FsYacc, and integration with MSBuild which makes 'build system' easy

(I think that trying to separate a language from its runtime and tooling is a mostly academic exercise.)

So there's a description of lot of distinctive features of one particular language of which I am a fan. I hope others might post similar answers that call out distinctive features of other individual languages.