Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence

Table of Contents

• Statically-typed functional programming, Elm, Conway's Game of Life, and Emergence
  • Table of Contents
  • Introduction
  • Definitions
  • Elm syntax
    • Basic types
    • Type aliases
    • Type variables
    • Custom types
    • Functions
    • Conditionals
    • Tuples
    • Records
    • Lists
  • Statically-typed functional programming fundamentals
    • Mathematical functions
    • Types
    • Pure functions
    • Determinism
    • Referential transparency
    • Side effects
    • Immutability
    • Monads
      • Maybe
      • Result
    • Higher-order functions
    • Anonymous functions
    • Partially-applied functions
  • The Elm Architecture
  • Conway's Game of Life
    • Rules
    • Implementation
  • Determinism in the Game of Life
  • Emergence
  • Conclusion
  • References
  • Acknowledgements
  • About the author

Introduction

This is an exploration of implementing Conway's Game of Life in Elm, a statically-typed functional programming language. It is also a demonstration of how statically-typed functional programming can facilitate emergence by allowing for the creation of complex systems through simple rules. For readers unfamiliar with Elm or functional programming, a brief introduction is provided. However, experienced Elm programmers may wish to skip ahead to the section on the Game of Life. The table of contents may be used as a convenient reference for any necessary refreshers.

Definitions

Statically-typed functional programming is a programming paradigm that combines the use of pure functions and immutable data with the use of type systems to ensure the correctness and safety of program execution.

Elm is a statically typed, functional programming language that compiles to JavaScript.

The Conway's Game of Life is a cellular automaton that simulates the evolution of a population of cells in a grid.

Emergence is a phenomenon in which complex patterns and seemingly intelligent behaviors emerge from the interaction of simple entities. This can occur in both natural systems, such as the emergence of complex brain functions from the interaction of neurons in the nervous system, and artificial systems, such as the emergence of traffic patterns in a city from the interaction of individual drivers.

Elm syntax

Elm is statically typed, meaning that the type of each value in the program must be known at compile time, and strongly typed, meaning that the type of each value cannot be changed once it has been declared.

Basic types

In Elm, all values have a type, which can be either a basic type or a composite type. The basic types, known as primitive types, are Int, Float, Bool, Char, and String. For example:

name : Stringname =    "Charbel"initial : Charinitial =    'C'age : Intage =    32favoriteNumber : FloatfavoriteNumber =    3.14isAccessibilibat : BoolisAccessibilibat =    True

Composite types are a combination of one or more basic types. For example:

accessibilibats : List Stringaccessibilibats =    [ "Kristine", "Tessa", "Charbel" ]

Ellie

Type aliases

Type aliases allow us to give a new name to an existing type. For example:

type alias Name = Stringtype alias Age = Inttype alias Person =    { name : Name    , age : Age    }charbel : Personcharbel = { name = "Charbel", age = 32 }

Ellie

Type variables

Type variables are used to define generic types. For example:

identity : a -> aidentity x = xidentity 1 == 1

The function identity is defined to take in a value of any type a and return a value of the same type a. This allows identity to be used with any type of value, as long as the type of the value passed as an argument is consistent with the type of the value returned.

Custom types

Elm also supports custom types, known as algebraic data types, which are defined using the type keyword and consist of a set of constructors. For example:

type Shape    = Circle Float    | Rectangle Float Floatarea : Shape -> Floatarea shape =    case shape of        Circle radius ->            pi * radius ^ 2        Rectangle width height ->            width * height

Shape is an algebraic data type that represents two types of geometric shapes: a Circle and a Rectangle.

An algebraic data type is a type that is defined by a set of constructors, each of which may contain zero or more arguments. In the given example, Shape is an algebraic data type with two constructors: Circle and Rectangle.

The Circle type consists of a single field representing the radius of the circle. The Rectangle type consists of two fields representing the width and height of the rectangle.

The function area is defined to take in a value of the Shape type and return a value of the Float type. The function uses pattern matching to determine which type of Shape has been passed as an argument and then calculates the area of the shape accordingly.

Ellie

Functions

Functions are declared using the assignment operator =. The left side of the operator consists of the function name and its parameters, while the right side contains the function's body. For example:

add : Int -> Int -> Intadd x y =    x + ygreet : String -> Stringgreet name =    "Hello, " ++ name ++ "!"

Ellie

Conditionals

Elm also supports if expressions and case expressions, which are used for conditional execution and pattern matching. For example:

type Person    = Student String Int    | Teacher String    | Administrator Stringgreet : Person -> Stringgreet person =    case person of        Student name age ->            if age < 18 then                "Hello, " ++ name ++ "! Welcome to school."            else                "Hello, " ++ name ++ "! How are you enjoying your studies?"        Teacher name ->            "Hello, " ++ name ++ "! It's great to see you back in the classroom."        Administrator name ->            "Hello, " ++ name ++ "! Thank you for all of your hard work and dedication to the school."

Ellie

Tuples

Tuple types are used to represent a fixed-size collection of values of potentially different types. They are defined using parentheses and commas, with the type of each element specified in the type annotation. For example:

type alias Tamagotchi =    ( String, Int )feedTamagotchi : Tamagotchi -> TamagotchifeedTamagotchi ( name, hunger ) =    ( name    , if hunger > 0 then        hunger - 1      else        hunger    )

Ellie

Records

Record types are used to represent a collection of named values of potentially different types. They are defined using curly braces and the field : type syntax, with the type of each field specified in the type annotation. For example:

type alias Person =    { name : String    , age : Int    }

Lists

Lists are a composite type in Elm, used to represent a series of values of the same type. Lists can be constructed using the [ and ] characters and separated by commas. For example:

strings : List Stringstrings =    [ "Kristine", "Tessa", "Charbel" ]integers : List Intintegers =    [ 1, 2, 3 ]customTypes : List ShapecustomTypes =    [ Circle 1, Rectangle 2 3 ]

Lists can also be constructed using the :: operator, also known as "cons". This operator prepends an element to the front of a list. The following three expressions are equivalent:

integers : List Intintegers =    1 :: [2, 3]integers : List Intintegers =    1 :: 2 :: 3 :: []integers : List Intintegers =    [ 1, 2, 3 ]

Lists also have a number of built-in functions for manipulating and transforming their contents, such as map, filter, and foldl. For example:

double : List Int -> List Intdouble numbers =    List.map (\x -> x * 2) numbersdouble [ 1, 2, 3 ] == [ 2, 4, 6 ]even : List Int -> List Inteven numbers =    List.filter (\x -> remainderBy 2 x == 0) numberseven [ 1, 2, 3 ] == [ 2 ]sum : List Int -> Intsum numbers =    List.foldl (\acc x -> acc + x) 0 numberssum [ 1, 2, 3 ] == 6

Ellie

Statically-typed functional programming fundamentals

Mathematical functions

Mathematical functions are mappings that associate a set of input values, known as the domain, with a set of output values, known as the range. These mappings are often denoted by the notation f: X -> Y, where X is the domain and Y is the range. A mathematical function is a rule that takes one or more inputs and produces a single output. In other words, a function can be thought of as a machine that takes an input and produces a unique output.

For instance, consider the function f: R -> R, defined by f(x) = x^2. This function takes a single input x, which belongs to the set of real numbers (denoted by R), and returns an output y, also belonging to the set of real numbers. If we provide the input 2, the function returns 4, since 2^2 = 4. The function f is applied to 2 to obtain 4. The process of applying a function to its arguments in order to obtain a result is known as function application.

Types

f(x) = x^2 in Elm is defined as follows:

square : Float -> Floatsquare x =    x^2

square : Float -> Float is the type signature of the function square, which indicates that the domain and the range of square are the set of all floating-point numbers, denoted Float. This is equivalent to the mathematical notation f: R -> R.

square is a pure function.

Ellie

Pure functions

A pure function is equivalent to a mathematical function.

A pure function is characterized by determinism.

Determinism

Please note that the mathematical notation used in this text to illustrate functional programming concepts may not be fully supported by external references, as I have not found any functional programming references that include such notation. However, I have taken care to ensure its accuracy.

Determinism refers to the property of a function in which the output is always the same given the same input. This means that the function will produce the same result every time it is called with the same arguments, regardless of any external state or context. In other words, a deterministic function is one that has no randomness or external dependencies. This can be formally defined as follows:

f(x) = f(x) x D, where D is the domain of the function f.

or

x1, x2 D, (x1 = x2) => (f(x1) = f(x2)), where D is the domain of the function f.

or

f(x) = y f(x) = y' => y = y' x D, y R, y' R, where D is the domain of the function f and R is the range of the function f.

A pure function is also characterized by referential transparency.

Referential transparency

Referential transparency refers to the property of a function in which the function can be replaced with its result without affecting the behavior of the program. This means that it can be treated as a value, and the program will behave the same way regardless of whether the function is called or its result is used directly. Formally, this can be written as follows:

f(x) = y f(x) = y' x D, y R, y' R, where D is the domain of the function f and R is the range of the function f.

Consider the following function, which takes a floating-point number as input and returns the square of that floating-point number as output:

square : Float -> Floatsquare x =    x ^ 2

The following expression:

square 3 + 1 == 10

can be replaced with

(3 ^ 2) + 1 == 10

or equivalently

9 + 1 == 10

without affecting the behavior of the program.

This function is both deterministic and referentially transparent, as it always returns the same result given the same input, and can be replaced with its return value without affecting the behavior of the program. It also has no side effects, as it does not modify the state of the program in any way.

Side effects

Side effects refer to any observable changes to the state of a program that are not reflected in the return value of a function or that occur as a result of a function's execution. Specifically, a pure function f with input x and output y is said to have a side effect if the execution of f(x) results in a change in the global state g such that g g', where g' is the state of the program before the execution of f(x).

Side effects can introduce unintended complexity and unpredictability into the program.

To mitigate the negative impacts of side effects, functional programming languages often employ a number of principles and design patterns, such as immutability and monads.

Immutability

Immutability refers to the property of an object or data structure to remain unchanged over time. In other words, once an object has been created, it cannot be modified in any way.

Mathematically, we can define immutability as follows: given an object x and an operation f that attempts to modify x, the result of applying f to x is a new object y, such that x and y are distinct and x remains unchanged. This can be formally represented as:

f(x) = y, x y, x' = x, where x' is the value of x before the execution of f(x).

In functional programming languages, immutability is often achieved through the use of immutable data types. These types cannot be modified after they have been created, and any attempt to do so will result in the creation of a new object.

For example, in Elm, the following code creates an immutable string:

greeting : Stringgreeting =    "Hello"

If we try to modify the string by concatenating a new string to it, we will actually create a new string object:

modifiedGreeting : StringmodifiedGreeting =    greeting ++ ", how are you?"

In this case, the original string greeting remains unchanged, while modifiedGreeting is a new string that contains the original greeting and the additional text. A better name for modifiedGreeting would be newGreeting.

Ellie

Monads

A monadic structure is a means of abstracting and composing computations that may contain side effects or non-determinism, or computations that may fail or return no result.

Maybe

One particularly useful example of monadic structures is the Maybe type, which represents a computation that may or may not produce a result. In Elm, the Maybe type is defined as follows:

type Maybe a    = Just a    | Nothing

This definition establishes the two possible constructors for Maybe values: Just, which wraps a value of type a, and Nothing, which represents the absence of a value.

To illustrate the utility of Maybe, consider the following scenario: we have a list of integers, and we want to find the first even number in the list. However, it is possible that the list does not contain any even numbers, in which case we want to return Nothing.

Here is how we could implement this function in Elm:

findFirstEven : List Int -> Maybe IntfindFirstEven list =    case list of        [] ->            Nothing        x :: xs ->            if remainderBy 2 x == 0 then                Just x            else                findFirstEven xs

This function uses pattern matching to examine the given list. If the list is empty, it returns Nothing. If the list is non-empty, it checks the first element to see if it is even. If it is, it wraps the value in a Just constructor and returns it. If it is not, it recursively calls itself on the tail of the list.

Using Maybe in this way allows us to concisely express the idea that a computation may or may not produce a result, without the need for error handling or exceptions.

For example, suppose we have a function that takes an integer as an input and returns a string indicating whether the integer is even or odd:

stringify : Int -> Stringstringify int =    if remainderBy 2 int == 0 then        String.fromInt int ++ " is even"    else        String.fromInt int ++ " is odd"

We can then use this function to stringify the result of our findFirstEven function, like so:

findAndStringify : List Int -> Maybe StringfindAndStringify list =    findFirstEven list       |> Maybe.map stringify

The function Maybe.map applies a given function to a value that is wrapped within the Maybe constructor, provided the constructor is of the Just type. If the Maybe value is a Nothing constructor, Maybe.map will return Nothing without applying the function.

Ellie

Result

Another example of a monadic structure in Elm is the Result type, which represents the result of a computation that may either succeed or fail. This type is defined as follows:

type Result error value    = Ok value    | Err error

The Result type has two constructors: Ok and Err. The Ok constructor represents a successful computation, and is used to wrap the value that was computed. The Err constructor represents a failed computation, and is used to wrap the error value that was produced.

To use the Result type, we can define a function that performs some computation and returns a Result value. For example, suppose we have a function divide that takes two integers and returns their quotient, but only if the denominator is non-zero:

divide : Int -> Int -> Result String Intdivide numerator denominator =    if denominator == 0 then        Err "division by zero"    else        Ok (numerator // denominator)

The divide function returns a Result value, which we can pattern match on to handle the success and failure cases. For example, we might use the divide function as follows:

case divide numerator denominator of    Ok result ->        "The result is: " ++ String.fromInt result    Err error ->        "An error occurred: " ++ error

In this example, if the divide function is called with a non-zero denominator, it will return an Ok value, containing the quotient of the two numbers. If the denominator is zero, it will return an Err value, containing an error message.

Ellie

Higher-order functions

A higher-order function is a function that takes one or more functions as arguments, or returns a function as a result.

In Elm, a simple example of a higher-order function is the List.map function, which takes a function and a list as arguments, and applies the function to each element of the list, returning a new list with the transformed elements. For instance, the following code applies the function double to each element of the list [1, 2, 3], returning a new list [2, 4, 6]:

double : Int -> Intdouble x =    x * 2doubleList : List IntdoubleList =    List.map double [ 1, 2, 3 ]

Another example is the List.filter function, which takes a predicate function and a list as arguments, and returns a new list with only the elements that satisfy the predicate. For instance, the following code filters the list [1, 2, 3] to only include even numbers, returning a new list [2]:

isEven : Int -> BoolisEven x =    remainderBy 2 x == 0evenList : List IntevenList =    List.filter isEven [ 1, 2, 3 ]

Higher-order functions enable the creation of abstractions, allowing us to define complex operations in terms of simpler ones. They also allow for the creation of functions that are customized for specific purposes, through the use of anonymous functions or partially-applied functions.

Ellie

Anonymous functions

An anonymous function, also known as a lambda function, is a function that is not bound to a specific name.

In Elm, anonymous functions are defined using the \ character. For instance, the following code defines an anonymous function that doubles its argument:

List.map (\x -> x * 2) [1, 2, 3]

returning the list [2, 4, 6].

Partially-applied functions

A partially-applied function is a function that has had one or more of its arguments fixed to specific values. This results in a new function that takes fewer arguments and is a specialization of the original function.

Mathematically, given a function f(x, y, z) and fixed values a, b, we can create a partially-applied function g(z) = f(a, b, z). This new function g is a specialization of f that always applies the values a and b to the first and second arguments of f, respectively, and allows the third argument to vary.

For instance, the following code defines a function doubleList that doubles each element of a list:

doubleList : List Int -> List IntdoubleList =    List.map (\x -> x * 2)

doubleList is a partially applied function that takes a list as its argument and returns a new list with each element doubled by applying the function (\x -> x * 2) to each element of the input list. We can then use this function to double the elements of any list:

doubleList [1, 2, 3]

Ellie

The Elm Architecture

At its core, the Elm architecture consists of three main components: the model, the view, and the update function.

The model is a representation of the state of the application. It is immutable and can only be updated through the update function.

The view is a function that takes the model as input and returns a representation of the model as HTML.

The update function takes the current model and a message as input, and returns a new model as output.

The architecture follows a predictable pattern of flow, known as the "update loop". This loop begins with the model, which is passed to the view function as an argument. The view function then returns a representation of the model's state as HTML. When the user interacts with the interface, the update function is called, passing the current model state and the user input as arguments. The update function then produces a new model state, which is passed back to the view function and the cycle begins anew.

Elm also includes subscriptions and commands.

Subscriptions are functions that are used to handle continuous or asynchronous inputs, such as timers or global event listeners. Subscriptions are used to update the model in response to these events.

Commands are a way for an Elm program to execute side-effects, such as making HTTP requests or generating random numbers.

Here is an application that keeps track of the number of seconds that have elapsed since the application started.

Caveat: This is not recommended for the creation of an accurate clock in Elm. Ticks and intervals can be affected by the workload of the event loop. Instead, it is recommended to retrieve the current time from the browser and track the difference in seconds.

module Main exposing (..)import Browserimport Html exposing (..)import Time{-- The main function is the entry point of the application. It isresponsible for initializing the application and connecting it to theDOM. --}main =    Browser.element        { init = init        , view = view        , update = update        , subscriptions = subscriptions        }{-- The Model type is used to represent the state of the application.In this case, the Model type has a single field, `seconds`, whichrepresents the number of seconds that have elapsed since theapplication started. --}type alias Model =    { seconds : Int }{-- The init function is responsible for initializing the application.In this case, the init function returns a Model with a `seconds` fieldinitialized to 0, and a `Cmd.none` value, which represents a commandthat does nothing. --}init : () -> ( Model, Cmd Msg )init _ =    ( Model 0, Cmd.none ){-- The Msg type is used to represent all possible messages that theapplication can receive. In this case, the only message that theapplication can receive is a `Tick` message, which is sent by the`Time` module every second. --}type Msg    = Tick Time.Posix{-- The update function is responsible for updating the application'smodel in response to a message. In this case, the update functionreceives a `Tick` message and increments the `seconds` field of themodel by 1. --}update : Msg -> Model -> ( Model, Cmd Msg )update msg model =    case msg of        Tick _ ->            ( Model (model.seconds + 1), Cmd.none ){-- The subscriptions function uses the `Time` module to send a `Tick`message every second. --}subscriptions : Model -> Sub Msgsubscriptions _ =    Time.every 1000 Tick{-- The view function is responsible for rendering the application'smodel as HTML. In this case, the view function renders the `seconds`field of the model as text. --}view : Model -> Html Msgview model =    text ("Seconds: " ++ String.fromInt model.seconds)

Ellie

Conway's Game of Life

Rules

According to Wikipedia, the rules are as follows:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by overpopulation.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

These rules, which compare the behavior of the automaton to real life, can be condensed into the following:

• Any live cell with two or three live neighbours survives.
• Any dead cell with three live neighbours becomes a live cell.
• All other live cells die in the next generation. Similarly, all other dead cells stay dead.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

For clarity, we will emphasize the following terms:

The universe of the Game of Life is an infinite, two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead (or populated and unpopulated, respectively). Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

...

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed, live or dead; births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick. Each generation is a pure function of the preceding one. The rules continue to be applied repeatedly to create further generations.

Implementation

We begin by modeling the state of the universe, which includes the grid of cells and the current generation:

type alias Model =    { grid : Grid, generation : Generation }

The grid of cells is a two-dimensional structure representing the spatial arrangement of cells in the universe, and as such, we define a type alias, Grid, which is a list of lists of cells:

type alias Grid =    List (List Cell)

Cell is a custom type, which allows us to define a fixed set of possible values to represent the possible states of a single cell within the grid. In this case, either Live or Dead:

type Cell    = Live    | Dead

Generation represents the current iteration of the universe as an integer:

type alias Generation =    Int

We define a type alias, NextGenerationModel, to represent a function that takes the current model and returns the next generation model:

type alias NextGenerationModel =    Model -> Model

The nextGenerationModel function takes the current model and returns the subsequent model, with the grid updated to the next generation grid and the generation incremented by one:

nextGenerationModel : NextGenerationModelnextGenerationModel model =    { grid = nextGenerationGrid model.grid    , generation = model.generation + 1    }

The nextGenerationGrid function takes the current grid and returns the next generation grid by applying the nextGenerationCell function to each cell in the grid:

nextGenerationGrid : Grid -> GridnextGenerationGrid grid =    List.indexedMap (\x row -> List.indexedMap (\y cell -> nextGenerationCell grid ( x, y ) cell) row) grid

The nextGenerationCell function takes the current grid, the coordinates of a cell in the grid, and the cell's current state and returns the cell's state in the next generation. The state of the cell in the next generation is determined based on the number of live neighbors of the cell, which is calculated by the liveNeighbors function:

type alias Coordinates =    ( Int, Int )nextGenerationCell : Grid -> Coordinates -> Cell -> CellnextGenerationCell grid ( x, y ) cell =    let        liveNeighbors_ =            liveNeighbors ( x, y ) grid    in    case cell of        Live ->            if liveNeighbors_ == 2 || liveNeighbors_ == 3 then                Live            else                Dead        Dead ->            if liveNeighbors_ == 3 then                Live            else                Dead

The liveNeighbors function takes the grid and the coordinates of a cell in the grid and returns the number of live neighbors of the cell by mapping over a list of coordinates representing the positions of the cell's neighbors, and using the getCell function to retrieve the cell values at those positions:

liveNeighbors : Grid -> Coordinates -> IntliveNeighbors grid ( x, y ) =    let        neighbors =            [ ( x - 1, y - 1 )            , ( x, y - 1 )            , ( x + 1, y - 1 )            , ( x - 1, y )            , ( x + 1, y )            , ( x - 1, y + 1 )            , ( x, y + 1 )            , ( x + 1, y + 1 )            ]        countLiveNeighbors cell =            case cell of                Live ->                    1                Dead ->                    0        liveNeighborCount =            List.sum (List.map countLiveNeighbors (List.map (getCell grid) neighbors))    in    liveNeighborCount

getCell is a function that retrieves a cell from the grid of cells given the cell coordinates. We use the modBy function to wrap the indices around to the other side of the grid if they are out of bounds:

It is important to note that the grid of cells in this system is finite, but we treat it as if it were infinite by wrapping around the edges. This means that the cell located immediately to the left of the leftmost cell becomes the rightmost cell, and the cell above the topmost cell becomes the bottommost cell.

getCell : Grid -> Coordinates -> CellgetCell grid ( x, y ) =    let        length =            List.length grid        x_ =            x |> modBy length        y_ =            y |> modBy length    in    case List.head (List.drop x_ grid) of        Just row ->            case List.head (List.drop y_ row) of                Just cell ->                    cell                Nothing ->                    Dead        Nothing ->            Dead

The update function is responsible for updating the application's model in response to a message. In this case, the update function receives a Tick message and returns the next generation model by applying the nextGenerationModel function to the current model:

update : Msg -> Model -> ( Model, Cmd Msg )update msg model =    case msg of        Tick _ ->            ( nextGenerationModel model            , Cmd.none            )

The subscriptions function uses the Time module to send a Tick message every 200 milliseconds, enabling us to simulate the passage of time within the universe:

subscriptions : Model -> Sub Msgsubscriptions _ =    Time.every 200 Tick

The view function is responsible for rendering the application's model as HTML. In this case, the view function renders the grid of cells and the current generation number:

view : Model -> Html Msgview model =    div []        [ renderGrid model.grid        , text ("Generation: " ++ String.fromInt model.generation)        ]

Here is the complete implementation.

module Main exposing (..)import Browserimport Html exposing (..)import Html.Attributes exposing (style)import Timetype alias Model =    { grid : Grid, generation : Generation }type alias Grid =    List (List Cell)type Cell    = Live    | Deadtype alias Generation =    Inttype alias NextGenerationModel =    Model -> Modelmain =    Browser.element        { init = init        , view = view        , update = update        , subscriptions = subscriptions        }seed : Modelseed =    { grid =        [ [ Dead, Dead, Dead, Dead, Dead ]        , [ Dead, Dead, Live, Dead, Dead ]        , [ Dead, Dead, Dead, Live, Dead ]        , [ Dead, Live, Live, Live, Dead ]        , [ Dead, Dead, Dead, Dead, Dead ]        ]    , generation = 0    }init : () -> ( Model, Cmd Msg )init _ =    ( seed, Cmd.none )type Msg    = Tick Time.Posixupdate : Msg -> Model -> ( Model, Cmd Msg )update msg model =    case msg of        Tick _ ->            ( nextGenerationModel model            , Cmd.none            )subscriptions : Model -> Sub Msgsubscriptions _ =    Time.every 200 Tickview : Model -> Html Msgview model =    div []        [ renderGrid model.grid        , text ("Generation: " ++ String.fromInt model.generation)        ]nextGenerationModel : NextGenerationModelnextGenerationModel model =    { grid = nextGenerationGrid model.grid    , generation = model.generation + 1    }nextGenerationGrid : Grid -> GridnextGenerationGrid grid =    List.indexedMap (\x row -> List.indexedMap (\y cell -> nextGenerationCell grid ( x, y ) cell) row) gridtype alias Coordinates =    ( Int, Int )nextGenerationCell : Grid -> Coordinates -> Cell -> CellnextGenerationCell grid ( x, y ) cell =    let        liveNeighbors_ =            liveNeighbors grid ( x, y )    in    case cell of        Live ->            if liveNeighbors_ == 2 || liveNeighbors_ == 3 then                Live            else                Dead        Dead ->            if liveNeighbors_ == 3 then                Live            else                DeadliveNeighbors : Grid -> Coordinates -> IntliveNeighbors grid ( x, y ) =    let        neighbors =            [ ( x - 1, y - 1 )            , ( x, y - 1 )            , ( x + 1, y - 1 )            , ( x - 1, y )            , ( x + 1, y )            , ( x - 1, y + 1 )            , ( x, y + 1 )            , ( x + 1, y + 1 )            ]        countLiveNeighbors cell =            case cell of                Live ->                    1                Dead ->                    0        liveNeighborCount =            List.sum (List.map countLiveNeighbors (List.map (getCell grid) neighbors))    in    liveNeighborCountgetCell : Grid -> Coordinates -> CellgetCell grid ( x, y ) =    let        length =            List.length grid        x_ =            x |> modBy length        y_ =            y |> modBy length    in    case List.head (List.drop x_ grid) of        Just row ->            case List.head (List.drop y_ row) of                Just cell ->                    cell                Nothing ->                    Dead        Nothing ->            DeadrenderGrid : Grid -> Html MsgrenderGrid grid =    div []        (List.map (\row -> div [ style "display" "flex" ] (List.map renderCell row)) grid)renderCell : Cell -> Html MsgrenderCell cell =    div        [ style "width" "16px"        , style "height" "16px"        , style "border" ".5px solid #ccc"        , style "transition" "background-color 150ms ease-out"        , style "background-color"            (case cell of                Live ->                    "#222"                Dead ->                    "#fff"            )        ]        []

Ellie

Determinism in the Game of Life

Conway's Game of Life is a deterministic system in which the state of a cell in a given generation is exclusively determined by the state of its eight neighbors in the preceding generation. These rules are simple and deterministic, yet they give rise to a wide range of patterns and behaviors, from stable configurations to oscillating patterns to seemingly random behavior. In a functional programming language, pure functions can effectively handle the deterministic nature of the Game of Life, and the behavior of a functional program, which is determined by the composition and application of these functions, can also be complex and varied, even though it is based on simple, deterministic rules.

Emergence

The Game of Life exhibits emergent behavior, which is the result of the interactions between individual cells in the system. This emergent behavior is not directly observable in any individual cell. Instead, it is only observable in the behavior of the system as a whole.

Emergent behavior, or the emergence of complex behaviors from the interactions of individual components, is a common characteristic of many systems. One way to carefully control these interactions is through the use of functional programming and a strong type system.

Functional programming can be used to effectively manage complexity in such systems. Pure functions allow for better understanding of a system's behavior, as the behavior of each function can be evaluated in isolation. In the Game of Life, for instance, we can be confident that the state of a cell will only depend on the state of its neighbors, and that the function will not have any unintended side effects on the rest of the system. Additionally, composition of functions allows for the creation of complex behaviors by combining simpler, easily understood components.

A strong type system helps enforce the control of interactions between individual components by preventing the mixing of incompatible types and providing explicit type annotations that clearly communicate the intended use of each component.

For example, in a system simulating the behavior of a flock of birds, each bird could be represented by an object with certain attributes, such as position and velocity, and certain behaviors, such as the ability to move and change direction. A specific Bird type could be defined with explicit type annotations for each attribute and behavior. This would prevent errors such as trying to add a bird's position to its velocity or trying to call a non-existent behavior on a bird object. Furthermore, explicit type annotations enable developers to more easily understand how the system is intended to work and consider the potential consequences of modifying it.

Conclusion

In summary, Conway's Game of Life is an example of how the use of pure functions and immutable data structures allows for the effective handling of determinism, and how the ability to evaluate the behavior of functions in isolation allows for better understanding of emergent behavior.

Finally, statically-typed functional programming languages significantly improve the reliability of complex systems and make them easier to maintain over time. By providing a clear and explicit structure to the code, these languages make it easier for developers to understand the intent and functionality of a program, leading to code reuse and the introduction of new features without disrupting the overall system.

References

• https://guide.elm-lang.org/
• https://package.elm-lang.org/packages/elm/core/latest/
• https://www.manning.com/books/elm-in-action
• https://rosettacode.org/wiki/Rosetta_Code
• https://en.wikibooks.org/wiki/Haskell
• https://wiki.haskell.org/All_About_Monads
• https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
• https://en.wikipedia.org/wiki/Boids

Acknowledgements

Thanks to the accessibilibats and Blake for encouraging me to write this article.

Thanks to Richard for his excellent Elm in Action book, which was an invaluable resource for learning Elm.

Thanks to Kristine, Tessa, and Brian Hicks for their thorough feedback on this article.

About the author

Charbel is an engineer at NoRedInk. Charbel has been dedicated to improving accessibility for students with disabilities since joining NoRedInk and the accessibility team, known as the Accessibilibats, in July 2022, and has truly enjoyed the opportunity to make a positive impact in this area.

If you're interested in learning more about Charbel's work, be sure to follow him on Twitter @charbelrami.