Calculus

Encapsulation. One of the basic principles of modern software development. We hide implementation details of the entity and expose to outer world just safe interface for this entity. That's great idea because of many reasons. Erlang and Elixir ecosystem supports this principle a lot: we have private functions and macros inside our modules, we have internal states inside our processes. But unfortunately there is one place where encapsulation is completely broken at the moment (Erlang/OTP 22, Elixir 1.9.1). This place is term of user defined data type, like record or structure.

This package introduces another way to define a new data type and safe interface for it. Inspired by Alonzo Church. Powered by Lambda Calculus.

Installation

The package can be installed by adding calculus to your list of dependencies in mix.exs:

def deps do
  [
    {:calculus, "~> 0.3"}
  ]
end

Readme!

This pretty long readme contains detailed information about the problem which is the cause of this library, also description of idea which is foundation of this library and step-by-step example. I strongly recommend to read it, but if you are sure that you don't need these details and you can figure out everything from concrete examples, you can find them here:

Simple Stack data type example (smart constructor, push and pop methods)
- code
- tests
OOP-like User data type example (smart constructor, setters, getters, methods)
- code
- tests

Problem

First of all, let's figure out what's wrong with Elixir structs. For instance let's consider URI data type which is part of standard library (Elixir 1.9.1).

First statement:

default constructor %URI{} of data type URI is always public

Somebody can say "hey, this is not a constructor function, it's a syntactic sugar for value, literal Elixir term". But anyway, this is expression and value of this expression is Elixir struct of URI type. For simplicity I'll call this thing as default constructor. And this default constructor is always public. Indeed, you can write in any place or your program something like this:

iex> uri = %URI{host: :BANG}
%URI{
  authority: nil,
  fragment: nil,
  host: :BANG,
  path: nil,
  port: nil,
  query: nil,
  scheme: nil,
  userinfo: nil
}

Is uri term valid value of the URI type? Probably not, let's try to do something with it:

iex> URI.to_string(uri)

** (FunctionClauseError) no function clause matching in String.contains?/2

Oops, this value of URI type caused exception. Default constructor does not validate arguments, and this is a problem in our case because host at least have to be value of String.t type. As a solution of this problem, developers introduced concept of smart constructors. Do we have a smart constructor for URI type? Probably here it is:

iex> uri = URI.parse("https://hello.world")
%URI{
  authority: "hello.world",
  fragment: nil,
  host: "hello.world",
  path: nil,
  port: 443,
  query: nil,
  scheme: "https",
  userinfo: nil
}

Beautiful. We have a smart constructor which creates value of the type URI properly. But remember our first statement? Default constructor is always public, which means that we can just hope that people will use smart constructor instead of default one. Concept of the smart constructors implies fact that we will hide unsafe default constructors. But we can't reach it with Elixir structs.

Second statement:

all fields of URI value are public

That's also true, because we can access any field of URI value in any place of our program (where this value exists):

iex> uri = URI.parse("https://hello.world")
iex> %URI{host: host} = uri
iex> host
"hello.world"

Concept of Elixir structs does not distinguish fields which are meant to be used in external world and fields which are meant only for internal usage. Sad but true, we just can write some documentation and hope that people will read it, follow our guidelines and will not change or rely on data which is meant to be private.

Third statement:

all fields of URI value are mutable (in functional meaning)

This sentence looks weird because all Erlang/Elixir terms are immutable, right? I will explain what I meant by example:

iex> uri0 = URI.parse("https://hello.world")
iex> uri1 = %URI{uri0 | port: -80}
iex> URI.to_string(uri1)
"https://hello.world:-80"

Let's consider what happened here:

We create proper uri0 value with smart constructor
We create new value uri1 based on uri0 by replacing the port with -80
We apply to_string function to new uri1 value (and what scares - it worked)

This means that even if smart constructor has been used to create proper value of the type URI, we can just hope that this proper value will not be corrupted later.

We have 3 statements about Elixir structures. Don’t you think that we rely on hope too much? As we know, "Hope is Not a Strategy" ©. What if I will say you that we can have real smart constructors, real private fields, real immutable fields and many other fun things almost for free? And we can do it without any relatively expensive stuff like processes? Well, we really can, and all that we need - just one simple thing. It is λ-expression.

Idea

Mathematical theory says us that λ-calculus is Turing complete, it is a universal model of computation that can be used to simulate any Turing machine. This statement means that using λ-expressions we can express things which we don't have in our language by default.

For example, let's imagine that we don't have boolean type in Elixir (it's not so far from the truth). To implement boolean type from scratch, we should understand real nature of boolean type. What is the value of boolean type? This is the choice between 2 possibilities. And we have only 2 values of this type (true and false). So we should have 2 λ-expressions which are representing all possible choices between 2 possibilities. There is only one way how we can express this (well, we can swap λtrue and λfalse definitions, and it will be other way, but it will be isomorphic thing):

iex> λtrue = fn x, _ -> x end
#Function<13.91303403/2 in :erl_eval.expr/5>
iex> λfalse = fn _, x -> x end
#Function<13.91303403/2 in :erl_eval.expr/5>

Now we have definitions of all values of λbool type without having bool type itself, let's implement λand function to show that it will behave in our λ-world the same way like and behaves in normal world. First of all, let's write signatures of both functions

and(bool, bool)    :: bool
λand(λbool, λbool) :: λbool

As you can see, they are isomorphic. According type specifications, knowledge about boolean logic and our definitions of λtrue and λfalse, our new λand function will look like:

iex> λand = fn left, right -> left.(right, left) end
#Function<13.91303403/2 in :erl_eval.expr/5>

Let's use pin operator and pattern matching to show that behaviour of λand function is correct (remember, we still can't use normal boolean type, because we imagined that it just not exist):

iex> ^λtrue = λand.(λtrue, λtrue)
#Function<13.91303403/2 in :erl_eval.expr/5>
iex> ^λfalse = λand.(λfalse, λtrue)
#Function<13.91303403/2 in :erl_eval.expr/5>
iex> ^λfalse = λand.(λtrue, λfalse)
#Function<13.91303403/2 in :erl_eval.expr/5>
iex> ^λfalse = λand.(λfalse, λfalse)
#Function<13.91303403/2 in :erl_eval.expr/5>

As you can see, if we know the behaviour of the thing - we can express it in terms of λ-expressions and create isomorphic λ-thing from the void. If we can describe thing - it exists (at least in λ-world).

Usage (simple example)

This library is based on idea described above. It just provides syntactic sugar to express new types in terms of λ-expressions to create new things which Elixir don't have by default. For simplicity, I'll just name this new kind of types as λ-types. Let's implement simple λ-type Stack which will have just push and pop methods:

defmodule Stack do
  use Calculus

  defcalculus state do
    {:push, x} ->
      calculus(state: [x | state], return: :ok)

    :pop ->
      case state do
        [] -> calculus(state: state, return: {:error, :empty_stack})
        [x | xs] -> calculus(state: xs, return: {:ok, x})
      end
  end
end

defcalculus is syntactic sugar, a macro which accepts 2 arguments:

internal representation of your data type (parameter state in this example)
do block of code, any amount of clauses which describe behaviour of data type against incoming data. For simplicity let's name these clauses as methods

Every method returns calculus expression which have 2 parameters

state is updated internal state of λ-type
return is term which is sent to outer world as result of the method call

Let's run this code and check what do we have for our Stack λ-type (type "Stack." in iex and press "tab")

iex> Stack.
is?/1       return/1

Not a lot. We have 2 functions is? and return which are generated by defcalculus macro. Let's check documentation generated for these functions:

iex(1)> h Stack.is?

  def is?(it)

  @spec is?(term()) :: boolean()

  • Accepts any term
  • Returns true if term is value of Stack λ-type, otherwise returns false

iex> h Stack.return

  def return(it)

  @spec return(Stack.t()) :: term()

  • Accepts value of Stack λ-type
  • Returns result of the latest

Calculus

Install / Use

README

Calculus

Installation

Readme!

Problem

Idea

Usage (simple example)