Functional Programming and Type Systems

Question

I have been learning about various functional languages for some time now including Haskell, Scala and Clojure. Haskell has a very strict and well-defined static type system. Scala is also statically typed. Clojure on the other hand, is dynamically typed.

So my questions are

1. What role does the type system play in a functional language?
2. Is it necessary for a language to have a type system for it to be functional?
3. How is the "functional" level of a language related to the kind of the type system of the language?

Answer 1

1. Same as in any programming language: it helps you to avoid/find errors in your code. In case of static typing a good type system prevents programs with certain types of errors from compiling.
2. No. The untyped lambda calculus is what you could call the prototype of functional programming languages and it is, as the name suggests, entirely untyped.

3. In a functional language (as well as any other language where a function can be used as a value) the type system needs to know what the type of a function is. Other than that there is nothing special about type systems for functional languages.

   In a purely functional language you need to abstract side-effects, so you'd want the type system to somehow be able to support that. For example if you want to have a world type like in Clean, you'd want the type system to support uniqueness types to ensure proper usage.

   If you want to have an IO monad like in haskell, you'd need an IO type (though a monad typeclass like in haskell is not required to have an IO monad, so you don't need a type system, which supports that).

Answer 2

A language does not need to be typed to be functional - at the heart of functional programming is the lambda calculus, which comes in untyped and typed variants.

The type system plays two roles:

• it provides a guarantee at compile time that a class of errors cannot occur at run-time. The class of errors usually includes things like trying to add two strings together, or trying to apply an integer as a function.
• it has some efficiency benefits, in that objects at runtime do not need to carry their types around, because the types have already been established at compile-time. This is known as type erasure.

In advanced type systems like Haskell's, the type system can provide more benefits:

• overloading: using one identifier to refer to operations on different types
• it allows a library to automatically choose an optimised implementation based on what type it is used at (using Type Families)
• it allows powerful invariants to be proven at compile time, such as the invariant in a red-black tree (using Generalised Algebraic Datatypes)

Answer 3

What role does the type system place in a functional language?

To Simon Marlow's excellent answer, I would add that a type system, especially one that includes algebraic data types, makes it easier to write programs:

• Software designs, which in object-oriented languages are sometimes expressed using UML diagrams, are very clearly expressed using types. This clarity manifests especially when not only values have types, but also modules have types, as in Objective Caml or Standard ML.

• When a person is writing code, a couple of simple heuristics make it very, very easy to write pure functions based on the types:

  • A value of function type can always be created with a lambda.
  • A value of function type can always be consumed by applying it.
  • A value of an algebraic data type can be created by applying any of the type's constructors.
  • A value of an algebraic data type can be consumed by scrutinizing it with a case expression.

  Based on these observations, and on the simple rule that unless there's a good reason, a function should consume each of its arguments, it's pretty easy to cut down the space of possible code you could write to a very small number of candidates. For example, there just aren't that many sensible functions of type (using Haskell notation)

  forall a . (a -> Bool) -> [a] -> Bool
  

  The art of using types to create code is called type-directed programming. When it works well, you hear functional programmers say things like "once we got the types right, the code practically wrote itself." Since the types are usually much smaller than the code, this is a big win.

Answer 4

1: Same as any other, it stops you from doing operations that are either ill-defined, or whose result would be 'nonsensical' to humans. Like float addition on integers.
2: Nope, the oldest programming language in the world, the (untyped) lambda calculus, is both functional and untyped.
3: Hardly, functional just means no side effects, no mutations, referential transparency et cetera.

Just remember that the oldest functional language, the untyped lambda calculus has no type system.