Algebrick

It’s a gem providing algebraic types and pattern matching and seamlessly integrating with standard features of Ruby.

Quick example

# Let's define a Tree
Tree = Algebrick.type do |tree|
  variants Empty = atom,
           Leaf  = type { fields Integer },
           Node  = type { fields tree, tree }
end                                                # => Tree(Empty | Leaf | Node)

# Now types `Tree(Empty | Leaf | Node)`, `Empty`, `Leaf(Integer)` and `Node(Tree, Tree)` are defined.
# Let's add a method, don't miss the **pattern matching** example.
module Tree
  # compute depth of a tree
  def depth
    match self,
          (on Empty, 0),
          (on Leaf, 1),
          # ~ will store and pass matched parts to variables left and right
          (on Node.(~any, ~any) do |left, right|
            1 + [left.depth, right.depth].max
          end)
  end
end 

# Method defined in module `Tree` are passed down to **all** values of type Tree.
Empty.depth                                        # => 0
Leaf[10].depth                                     # => 1
Node[Leaf[4], Empty].depth                         # => 2
Node[Empty, Node[Leaf[1], Empty]].depth            # => 3

Algebraic types

Algebraic types are:

In Haskell algebraic type looks like this:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree
          
depth :: Tree -> Int
depth Empty = 0
depth (Leaf n) = 1
depth (Node l r) = 1 + max (depth l) (depth r)

depth (Node Empty (Leaf 5)) -- => 2

This snippet defines type Tree which has 3 possible values:

and function depth to calculate depth of a tree which is called on the last line and evaluates to 2.

Same Tree type and depth method can be also defined with this gem as it was shown in Quick Example.

Algebrick implementation

Algebrick distinguishes 4 kinds of algebraic types:

  1. Atom - type that has only one value, e.g. Empty.
  2. Product - type that has a set number of fields with given type, e.g. Leaf(Integer)
  3. Variant - type that is one of the set variants, e.g. Tree(Empty | Leaf(Integer) | Node(Tree, Tree), meaning that values Empty, Leaf[1], Node[Empty, Empry] have all type Tree.
  4. ProductVariant - will be created when a recursive type like List(Empty | List(Integer, List)) is defined. List has two variants: Empty and itself. Simultaneously it has fields as a product type.

Atom type is implemented with Algebrick::Atom and the rest is implemented with Algebrick::ProductVariant which behaves differently based on what is set: fields, variants, or both.

More information can be found at https://en.wikipedia.org/wiki/Algebraic_data_type.

Documentation

Type definition

# Let's define some types
Maybe = Algebrick.type do
  variants None = atom,
           Some = type { fields Numeric }
end                                                # => Maybe(None | Some)

# where the Maybe actually is:
Maybe.class                                        # => Algebrick::ProductVariant
Maybe.class.superclass                             # => Algebrick::Type
Maybe.class.superclass.superclass                  # => Module
Maybe.class.superclass.superclass.superclass       # => Object

# if there is a circular dependency you can define the dependent types inside the block like this:
Tree = Algebrick.type do |tree|
  variants Empty = type,
           Leaf  = type { fields Integer },
           Node  = type { fields tree, tree }
end                                                # => Tree(Empty | Leaf | Node)
Empty                                              # => Empty
Leaf                                               # => Leaf(Integer)
Node                                               # => Node(Tree, Tree)

Value creation

# Let's define a Tree
Tree = Algebrick.type do |tree|
  variants Empty = type,
           Leaf  = type { fields Integer },
           Node  = type { fields tree, tree }
end                                                # => Tree(Empty | Leaf | Node)

# Values of atomic types are represented by itself,
# they are theirs own value.
Empty.kind_of? Algebrick::Value                    # => true
Empty.kind_of? Algebrick::Type                     # => true
Empty.kind_of? Empty                               # => true

# Values of product types are constructed with #[] and they are immutable.
Leaf[1].kind_of? Algebrick::Value                  # => true
Leaf[1].kind_of? Leaf                              # => true
Node[Empty, Empty].kind_of? Node                   # => true

# Variant does not have its own values, it uses atoms and products.
Leaf[1].kind_of? Tree                              # => true
Empty.kind_of? Tree                                # => true

# Product can have its fields named.
BinaryTree = BTree = Algebrick.type do |btree|
  fields! value: Integer, left: btree, right: btree
  variants Tip = atom, btree
end
    # => BTree(Tip | BTree(value: Integer, left: BTree, right: BTree))

# Then values can be created with names
tree1      = BTree[value: 1, left: Tip, right: Tip]
    # => BTree[value: 1, left: Tip, right: Tip]
# or without them as before.
BTree[0, Tip, tree1]
    # => BTree[value: 0, left: Tip, right: BTree[value: 1, left: Tip, right: Tip]]

# Fields of products can be read as follows:
# 1. When type has only one field method #value is defined
Leaf[1].value                                      # => 1
# 2. By multi-assign
v, left, right = BTree[value: 1, left: Tip, right: Tip]
    # => BTree[value: 1, left: Tip, right: Tip]
[v, left, right]                                   # => [1, Tip, Tip]
# 3. With #[] method when fields are named
BTree[value: 1, left: Tip, right: Tip][:value]     # => 1
BTree[value: 1, left: Tip, right: Tip][:left]      # => Tip
# 4. With methods named by fields when fields are named
#    (it can be disabled if fields are defined with #fields instead of #fields!)
BTree[1, Tip, Tip].value                           # => 1
BTree[1, Tip, Tip].left                            # => Tip

# Product instantiation raises TypeError when being constructed with wrong type.
Leaf['a'] rescue $!
    # => #<TypeError: Value (String) 'a' is not any of: Integer.>
Node[nil, Empty] rescue $!
    # => #<TypeError: Value (NilClass) '' is not any of: Tree(Empty | Leaf | Node).>

Behaviour extending

Maybe = Algebrick.type do
  variants None = atom,
           Some = type { fields Object }
end                                                # => Maybe(None | Some)

# Types can be extended with usual syntax for modules and using Ruby supports module reopening.
module Maybe
  def maybe(&block)
    case self
    when None
    when Some
      block.call value
    end
  end
end 

# #maybe method is defined on both values (None, Some) of Maybe.
None.maybe { |_| raise 'never ever happens' }      # => nil
# Block is called with the value.
Some[1].maybe { |v| v*2 }                          # => 2

# It also works as expected when modules like Comparable are included.
Season = Algebrick.type do
  variants Spring = atom,
           Summer = atom,
           Autumn = atom,
           Winter = atom
end                                                # => Season(Spring | Summer | Autumn | Winter)

module Season
  include Comparable
  ORDER = Season.variants.each_with_index.each_with_object({}) { |(season, i), h| h[season] = i }

  def <=>(other)
    Type! other, Season
    ORDER[self] <=> ORDER[other]
  end
end 

Quarter = Algebrick.type do
  fields! year: Integer, season: Season
end                                                # => Quarter(year: Integer, season: Season)

module Quarter
  include Comparable

  def <=>(other)
    Type! other, Quarter
    [year, season] <=> [other.year, other.season]
  end
end 

# Now Quarters and Seasons can be compared as expected.
[Winter, Summer, Spring, Autumn].sort              # => [Spring, Summer, Autumn, Winter]
Quarter[2013, Spring] < Quarter[2013, Summer]      # => true
Quarter[2014, Spring] > Quarter[2013, Summer]      # => true
Quarter[2014, Spring] == Quarter[2014, Spring]     # => true
[Quarter[2013, Spring], Quarter[2013, Summer], Quarter[2014, Spring]].sort
    # => [Quarter[year: 2013, season: Spring], Quarter[year: 2013, season: Summer], Quarter[year: 2014, season: Spring]]

Pattern matching

Pattern matching is implemented with helper objects defined in ALgebrick::Matchers. They use standard #=== method to match against values.

# Let's define a tree and binary tree to demonstrate the pattern matching abilities.
Tree = Algebrick.type do |tree|
  variants Empty = type,
           Leaf  = type { fields Integer },
           Node  = type { fields tree, tree }
end                                                # => Tree(Empty | Leaf | Node)

BinaryTree = BTree = Algebrick.type do |btree|
  fields! value: Comparable, left: btree, right: btree
  variants Empty, btree
end
    # => BTree(Empty | BTree(value: Comparable, left: BTree, right: BTree))

extend Algebrick::Matching                         # => main

# Product matchers are constructed with #.() syntax.
Leaf.(any) === Leaf[1]                             # => true
Leaf.(1) === Leaf[1]                               # => true
Leaf.(2) === Leaf[1]                               # => false
# There are also some shortcuts to use when product has more fields.
BTree.()                                           # => BTree.(any, any, any)
BTree.(value: any, left: Empty)                    # => BTree.(any, Empty, any)
BTree.(value: any, left: Empty) === BTree[1, Empty, Empty]
    # => true

# Any object responding to #=== can be converted to matcher.
(1..2).to_m                                        # => Wrapper.(1..2)
(1..2).to_m === 2                                  # => true
Empty.to_m                                         # => Empty.to_m
# As matchers are using standard #=== method it does not have to be always converted.
Empty === Empty                                    # => true
Leaf === Leaf[1]                                   # => true

# Tree matches all its values.
[Empty, Leaf[1], Node[Empty, Empty]].all? { |v| Tree === v }
    # => true

# There is also a #match method in Matching module to make pattern matching easier.
match Leaf[1], # supply the value for matching
      # if Leaf.(0) matches :zero is returned
      (on Leaf.(0), :zero),
      # when computation of the result needs to be avoided use block
      # if Leaf.(1) matches block is called and its result is returned
      (on Leaf.(1) do
        (1..10000).inject(:*) # expensive computation
        :one # which is :one in this case
      end)                                         # => :one

# Alternatively case can be used.
case Leaf[1]
when Leaf.(0)
  :zero
when Leaf.(1)
  (1..10000).inject(:*) # expensive computation
  :one
end                                                # => :one

# But that won't work nicely with value deconstruction.
# Each matcher can be marked with #~ method to store value against which is being matched,
# each matched value is passed to the block, ...
match Leaf[0],
      (on ~Leaf.(~any) do |leaf, value|
        [leaf, value]
      end)                                         # => [Leaf[0], 0]

btree = BTree[1,
              BTree[0, Empty, Empty],
              Empty]
    # => BTree[value: 1, left: BTree[value: 0, left: Empty, right: Empty], right: Empty]
match btree,
      (on BTree.(any, ~any, ~any) do |left, right|
        [left, right]
      end)
    # => [BTree[value: 0, left: Empty, right: Empty], Empty]

# or alternatively you can use Ruby's multi-assignment feature.
match btree,
      (on ~BTree do |(_, left, right)|
        [left, right]
      end)
    # => [BTree[value: 0, left: Empty, right: Empty], Empty]


# Matchers also support logical operations #& for and, #| for or, and #! for negation.
Color = Algebrick.type do
  variants Black = atom,
           White = atom,
           Pink  = atom,
           Grey  = type { fields scale: Float }
end                                                # => Color(Black | White | Pink | Grey)

def color?(color)
  match color,
        on(Black | Grey.(-> v { v < 0.2 }), 'black-ish'),
        on(White | Grey.(-> v { v > 0.8 }), 'white-ish'),
        on(Grey.(-> v { v >= 0.2 }) & Grey.(-> v { v <= 0.8 }), 'grey-ish'),
        on(Pink, "that's not a color ;)")
end                                                # => :color?

color? Black                                       # => "black-ish"
color? Grey[0.1]                                   # => "black-ish"
color? Grey[0.3]                                   # => "grey-ish"
color? Grey[0.9]                                   # => "white-ish"
color? White                                       # => "white-ish"
color? Pink                                        # => "that's not a color ;)"

# A more complicated example of extracting node's value and values of its left and right side
# using also logical operators to allow Empty sides.
match BTree[0, Empty, BTree[1, Empty, Empty]],
      (on BTree.({ value: ~any,
                   left:  Empty | BTree.(value: ~any),
                   right: Empty | BTree.(value: ~any) }) do |value, left, right|
        { left: left, value: value, right: right }
      end)                                         # => {:left=>nil, :value=>0, :right=>1}

# It also supports matching against Ruby Arrays
Array.() === []                                    # => true
Array.() === [1]                                   # => false
Array.(*any) === []                                # => true
Array.(*any) === [1]                               # => true
Array.(*any) === [1, 2]                            # => true
Array.(1, *any) === []                             # => false
Array.(1, *any) === [1]                            # => true
Array.(1, *any) === [1, 2]                         # => true

match [],
      on(~Array.to_m) { |v| v }                    # => []
match [],
      on(~Array.()) { |v| v }                      # => []
match [1, 2],
      on(~Array.(*any)) { |v| v }                  # => [1, 2]
match [1, 2],
      on(~Array.(*any)) { |(v, _)| v }             # => 1
match [1, 2, 3],
      on(Array.(any, *~any)) { |v| v }             # => [2, 3]
match [:first, 1, 2, 3],
      on(Array.(:first, ~any, *any)) { |v| v }     # => 1
match [:+, 1, 2, :foo, :bar],
      (on Array.(:+, ~Integer.to_m, ~Integer.to_m, *~any) do |int1, int2, rest|
        { sum: int1 + int2, rest: rest }
      end)                                         # => {:sum=>3, :rest=>[:foo, :bar]}


# There is also a more funky syntax for matching
# using #>, #>> and Ruby 1.9 syntax for lambdas `-> {}`.
match Leaf[1],
      Leaf.(0) >> :zero,
      Leaf.(~any) >-> value do
        (1..value).inject(:*) # an expensive computation
      end                                          # => 1

Parametrized types

# Let's define Tree but this time parameterized by :value_type,
Tree = Algebrick.type(:value_type) do |tree|
  variants Empty = atom,
           Leaf  = type(:value_type) { fields value: :value_type },
           Node  = type(:value_type) { fields left: tree, right: tree }
end

# with method depth defined as before.
module Tree
  def depth
    match self,
          Empty >> 0,
          Leaf >> 1,
          Node.(~any, ~any) >-> left, right do
            1 + [left.depth, right.depth].max
          end
  end
end 

# Then Tree, Leaf, Node are
Tree.class                                         # => Algebrick::ParametrizedType
[Tree, Leaf, Node]
    # => [Tree[value_type], Leaf[value_type], Node[value_type]]
# which servers as factories to actual types.
Tree[Float]                                        # => Tree[Float](Empty | Leaf[Float] | Node[Float])
Tree[String]                                       # => Tree[String](Empty | Leaf[String] | Node[String])

# Types cannot be mixed.
Leaf[Integer]['1'] rescue $!
    # => #<TypeError: Value (String) '1' is not any of: Integer.>
Node[Integer][Leaf[String]['a'], Empty] rescue $!
    # => #<TypeError: Value (Leaf[String](value: String)) 'Leaf[String][value: a]' is not any of: Tree[Integer](Empty | Leaf[Integer] | Node[Integer]).>
Leaf[String]['1']                                  # => Leaf[String][value: 1]

# Depth method works as before.
integer_tree = Node[Integer][Leaf[Integer][2], Empty]
    # => Node[Integer][left: Leaf[Integer][value: 2], right: Empty]
integer_tree.depth                                 # => 2
string_tree = Node[String][Empty, Empty]           # => Node[String][left: Empty, right: Empty]
string_tree.depth                                  # => 1

What is it good for?

Defining data structures

Examples are coming shortly.

Serialization

Algebraic types also play nice with JSON serialization and de-serialization making it ideal for defining message-based cross-process communication.

extend Algebrick::Matching                         # => main

# Lets define message-protocol for a cross-process communication.
Request = Algebrick.type do
  User = type { fields login: String, password: String }

  variants CreateUser = type { fields User },
           GetUser    = type { fields login: String }
end                                                # => Request(CreateUser | GetUser)

Response = Algebrick.type do
  variants Success = type { fields Object },
           Failure = type { fields error: String }
end                                                # => Response(Success | Failure)

Message = Algebrick.type { variants Request, Response }
    # => Message(Request | Response)

require 'algebrick/serializer'                     # => true
require 'multi_json'                               # => true

# Prepare a message for sending.
serializer   = Algebrick::Serializer.new           # => #<Algebrick::Serializer:0x007fab42bdf6d8>
request      = CreateUser[User['root', 'lajDh4']]
    # => CreateUser[User[login: root, password: lajDh4]]
raw_request  = MultiJson.dump serializer.dump(request)
    # => "{\"algebrick_type\":\"CreateUser\",\"algebrick_fields\":[{\"algebrick_type\":\"User\",\"login\":\"root\",\"password\":\"lajDh4\"}]}"

# Receive the message.
response     = match serializer.load(MultiJson.load(raw_request)),
                     (on CreateUser.(~any) do |user|
                       # create the user and send success
                       Success[user]
                     end)                          # => Success[User[login: root, password: lajDh4]]

# Send response.
response_raw = MultiJson.dump serializer.dump(response)
    # => "{\"algebrick_type\":\"Success\",\"algebrick_fields\":[{\"algebrick_type\":\"User\",\"login\":\"root\",\"password\":\"lajDh4\"}]}"

# Receive response.
serializer.load(MultiJson.load(response_raw))      # => Success[User[login: root, password: lajDh4]]

Message matching in Actor pattern

Just a small snippet how it can be used in Actor model world.

Work = Algebrick.type do
  fields key: String, work: Proc
end

Finished = Algebrick.type do
  fields key: String, result: Object, worker: Worker
end

class Worker < AbstractActor
  def initialize(executor)
    super()
    @executor = executor
  end

  def on_message(message)
    match message,
          Work.(~any, ~any) >-> key, work do
            @executor.tell Finished[key, work.call, self]
          end
  end
end