An advanced, purely functional programming language

This is a WORK IN PROGRESS! ^{1 2}

Preface

“Some half dozen persons have written technically on combinatory logic, and most of these, including ourselves, have published something erroneous. Since some of our fellow sinners are among the most careful and competent logicians on the contemporary scene, we regard this as evidence that the subject is refractory. Thus fullness of exposition is necessary for accuracy; and excessive condensation would be false economy here, even more than it is ordinarily.”

Haskell B. Curry and Robert Feys in the Preface to Combinatory Logic [3], May 31, 1956

History

Read paper “A History of Haskell: Being Lazy with Class” from 2007 or watch the YouTube video.

From its abstract: This paper describes the history of Haskell, including its genesis and principles, technical contributions, implementations and tools, and applications and impact.

Also this video from 2017 where Symon Peyton Jones discusses Haskell’s birth and evolution

Inception

In a meeting held at the conference on Functional Programming Languages and Computer Architecture (FPCA ’87) in Portland, Oregon in September of 1987, it was decided that a committee should be formed to design a much needed common language for a purely functional programming languages

The committee’s primary goal was to design a language that satisfied these constraints:

• It should be completely described via the publication of a formal syntax and semantics.
• It should be suitable for teaching, research, and applications, including building large systems.
• It should be freely available. Anyone should be permitted to implement the language and distribute it to whomever they please.
• It should be based on ideas that enjoy a wide consensus.
• It should reduce unnecessary diversity in functional programming languages.

This documents describes the results of that (and subsequent) committee’s efforts: a purely functional programming language called Haskell, named after the logician Haskell B. Curry whose work provides the logical basis for much of this.

TL;DR;

From this short post full of irony: A Brief, Incomplete, and Mostly Wrong History of Programming Languages.

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?"

Why?

There is an old but still relevant paper about Why Functional Programming Matters by John Hughes. More recently, Sebastian Sylvan wrote an article about Why Haskell Matters.

Purpose

A +10 years old funny video of what Haskell wants to achieve and the path taken to achieve it

Main Features

Haskell is a general purpose, purely functional programming language incorporating many recent innovations in programming language design. Haskell provides higher-order functions, non-strict semantics, static polymorphic typing, user-defined algebraic datatypes, pattern-matching, list comprehensions, a module system, a monadic I/O system, and a rich set of primitive datatypes, including lists, arrays, arbitrary and fixed precision integers, and floating-point numbers. Haskell is both the culmination and solidification of many years of research on non-strict functional languages.

Haskell 2010 Report - Chapter 1 - Introduction

• Purely functional
  • Every function in Haskell is a function in the mathematical sense (i.e., “pure”). Even side-effecting IO operations are but a description of what to do, produced by pure code. There are no statements or instructions, only expressions which cannot mutate variables (local or global) nor access state like time or random numbers.
  • See Lambda calculus and Evaluation Strategies.
• Statically typed
  • Every expression in Haskell has a type which is determined at compile time. All the types composed together by function application have to match up. If they don’t, the program will be rejected by the compiler. Types become not only a form of guarantee, but a language for expressing the construction of programs.
    • See Type checker and type inference in action.
• Type inference
  • You don’t have to explicitly write out every type in a Haskell program. Types will be inferred by unifying every type bidirectionally. However, you can write out types if you choose, or ask the compiler to write them for you for handy documentation.
    • See Type checker and type inference in action.
• Lazy
  • Functions don’t evaluate their arguments. This means that programs can compose together very well, with the ability to write control constructs (such as if/else) just by writing normal functions. The purity of Haskell code makes it easy to fuse chains of functions together, allowing for performance benefits.
    • See Evaluation Strategies.
• Concurrent
  • Haskell lends itself well to concurrent programming due to its explicit handling of effects. Its flagship compiler, GHC, comes with a high-performance parallel garbage collector and light-weight concurrency library containing a number of useful concurrency primitives and abstractions.
• Packages
  • Open source contribution to Haskell is very active with a wide range of packages available on the public package servers.

Lambda calculus

Desugared Haskell is essentially a slightly sugared variant of the lambda calculus with a straightforward denotational semantics.

A little theory about how it all started: The beginnings of Theoretical Computer Science.

Prelude

We will start first showing with examples the standard built-in datatypes and classes in Haskell.

Two thing that you may need to understand first:

1. Values and types

An expression evaluates to a value and has a static type. Values and types are not mixed in Haskell. However, the type system allows user-defined datatypes of various sorts, and permits not only parametric polymorphism (using a traditional Hindley-Milner type structure) but also ad hoc polymorphism, or overloading (using type classes).

2. Namespaces

There are six kinds of names in Haskell:

• Those for values:
  • Variables
  • Constructors
• Those for entities related to the type system:
  • Type variables
  • Type constructors
  • Type classes
• Those for module
  • Module names

There are two constraints on naming: Names for variables and type variables are identifiers beginning with lowercase letters or underscore; the other four kinds of names are identifiers beginning with uppercase letters. An identifier must not be used as the name of a type constructor and a class in the same scope. These are the only constraints; for example, Int may simultaneously be the name of a module, class, and constructor within a single scope.

Built-in

The basic types and classes that are in scope by default in every Haskell file are described in Prelude

• Lists
• Strings
• Fractional Numbers

Set based view:

Eq         = {Float, Double, Int, Word, Integer, Bool}

Ord        = {Float, Double, Int, Word, Integer, Bool}

Enum       = {Float, Double, Int, Word, Integer, Bool}

Bounded    = {Float, Double, Int, Word,          Bool}

Num        = {Float, Double, Int, Word, Integer, Bool}

Integral   = {               Int, Word, Integer      }

Real       = {Float, Double, Int, Word, Integer      }

Fractional = {Float, Double                          }

Floating   = {Float, Double                          }

RealFrac   = {Float, Double                          }

RealFloat  = {Float, Double                          }

Custom Prelude

The Prelude is imported by default or with import Prelude but the default Prelude can be disabled using -XNoImplicitPrelude GHC flag, this allows us to replace the default entirely with a custom prelude. Some projects roll their own Prologue.hs module in replacement.

{-# LANGUAGE NoImplicitPrelude #-}

You get an idea of how customizable source code in Haskell can be.

IO

https://www.haskell.org/onlinereport/haskell2010/haskellch7.html#x14-1420007

Language formal definition

The Haskell reports define “the syntax for Haskell programs and an informal abstract semantics for the meaning of such programs” but not “the ways in which Haskell programs are to be manipulated, interpreted, compiled, etc”.

Haskell’s lexical structure

Expressions

Declarations

Modules

Class hierarchy

Monoids

For an easy start see Monoid, you won’t be using them much but helps undertanding the rest.

Applicative Functors

See subpage

Monads

See subpage

Best publication about monads is this one that focuses on explaining the “bits round the edges” of Haskell programs: Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell

Example

A little example showing how an instance of Monoid, Applicative and Monad is built.

Datatype extensions

Multi-parameter type classes

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

class Collection c a where
        union :: c a -> c a -> c a
        ...

class Coerce a b c | a b -> c where
        add :: a -> b -> c
        ...

IMO this extension was superseded by the type families extension but the reasons for this may provide some hindsight on the type system and the type inference system.

See Multi-parameter type classes

Phantom types (GADTs)

See Phantom

Explain the paper

• True Sums of Products.

Further reading

• What I Wish I Knew When Learning Haskell
  • PDF Version: http://dev.stephendiehl.com/fun/WYAH.pdf
• Write You a Haskell
• Introduction to functional programming
• Haskell 2010 Language Report
• Paper with a static semantics for a large subset of Haskell, including giving a translations into a language without overloading.

TODO

Category theory

Categories for the Working Mathematician

Others

seL4: Formal Verification of an OS Kernel https://www.sigops.org/s/conferences/sosp/2009/papers/klein-sosp09.pdf

Maybe explain some of this: https://stackoverflow.com/questions/36274369/what-are-some-types-that-discriminate-between-categories

1. Based on GHC (The Glasgow Haskell Compiler), a state-of-the-art, open source, compiler and interactive environment for the functional language Haskell ↩

2. Using version 9.2.2 of GHC ↩