{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# What do I mean by algebra?\n",
"\n",
"When I say algebra, I don't think about implementing i.e. DSL for linear algebra in Python. I think about algebra in general as in \"a set of objects and a collection of operations on them\".\n",
"\n",
"I like algebras, when they are used in programming. Probably the most well-known is Relational Algebra. The object in Relational Algebra is a *relation*, with operations like *join*, *projection* and *union*. The nice thing about having something that works like an algebra is, that you always work with the same type of object, reusing the box of tools without breaking the flow.\n",
"\n",
"\n",
" \n",
"That is one of the reasons I like Pythons collections. Pythons sets and list actually have quite a nice algebra built around them."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Who should read this?\n",
"\n",
"Anybody who is interested with using algebraic design patterns in Python.\n",
"I have three kinds of people in mind as my target audience.\n",
"\n",
"* Me :-) Lets be clear, this is mostly a record for my future self, to remind me that I once understood something about this. \n",
"* People familliar with these concepts in haskell, wanting to see them in dynamically typed language like Python\n",
"* People interested in these algebraic patterns that know Python and don't have resources to learn i.e. haskell.\n",
"\n",
"If you are somebody interested, but wants to see these in haskell rather than python, go read [Bartosz Milewski's Programming Cafe](https://bartoszmilewski.com/), or [haskellforall by Gabriel Gonzalez](http://www.haskellforall.com/)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"{1, 2, 3, 4, 5}"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{1,2,3} | {3,4,5}"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"{3}"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{1,2,3} & {3,4,}"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"{1, 2}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"{1,2,3} - {3,4,5}"
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"And what I really like is, that all the laws I remember about sets from discrete math still work. For example, with union as `|` and empty set as `set()`:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = {1,2,3}\n",
"a == a|set()==set()|a\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b = {3,4,5}\n",
"c = {5,6,7}\n",
"(a | b) | c == a | (b | c)"
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"My personal preference is to use these math-like operators over calling methods on objects, even though methpd calls would produce the same result, and often would be more efficient"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = {1,2}\n",
"a.add(3)\n",
"a.add(4)\n",
"a.remove(2)\n",
"a == ({1,2} | {3} | {4}) - {2}"
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"To be honest, I probably would write this code with method calls, because they are more readable than operators: "
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"outputExpanded": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a == {1,2,3}.union({3,4}).difference({2})"
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"I don't really want to have operators everywhere, what I want is composability. Now-days we might call this *fluent* interface, but I want to go one step further, I want the interface to conform to predefined set of rules.\n",
"\n",
"This is what I mean when I say algebra:\n",
"* interfaces I work with *compose* with each other, they interoperate well, they are *fluent*\n",
"* the implementation is *lawful*, it conforms to predefined rules"
]
},
{
"cell_type": "markdown",
"metadata": {
"outputExpanded": false
},
"source": [
"# Why?\n",
"\n",
"So I have been watching too many talks from Scala conferences and reading too many posts from haskell enthusiasts.\n",
"And now I envy them. Because I am mostly working with javascript and python and barely anybody even knows what `monad` *is*, while on the scala-side they are using co-free co-monads to implement cool, extensible DSLs.\n",
"\n",
"Ok, there is fantasy-land and Ramda, but last time my colleague was trying to show off Ramda to the rest of the team, he mostly got puzzled looks from the most of them. And there isn't much in Python.\n",
"\n",
"But I still want to try all of those cool things I see in the typed functional languages."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Algebraic laws\n",
"\n",
"So, how might those predefined rules look like? For example lets have an binary operations $\\circ$ and $\\diamond$ some objects of some set $S$ that *will work with this operation*. Rules we might be interested in:\n",
"\n",
"* **set is closed under the operation**: \n",
"$$\\forall a,b \\in S: a \\circ b \\in S$$\n",
"\n",
"* **operation is associative**: \n",
"$$\\forall a,b,c \\in S: a \\circ (b \\circ c) = (a \\circ b) \\circ c$$\n",
"\n",
"* **identity element exists**:\n",
"$$ \\exists e \\in S, \\forall a \\in S: e \\circ a = a = a \\circ e$$\n",
"* **inverse element exist**:\n",
"$$ \\forall a \\in S \\exists b \\in S: a \\circ b = e = b \\circ a$$\n",
"* **operation is commutative**:\n",
"$$\\forall a,b \\in S: a \\circ b = b \\circ a$$\n",
"* **distributivity for $\\circ$ and $\\diamond$**:\n",
"$$\\forall a,b,c \\in S: a \\circ (b \\diamond c) = a = (a \\circ b) \\diamond (a \\circ c)$$\n",
"\n",
"* **absorbtion for $\\circ$ and $\\diamond$**:\n",
"$$\\forall a,b \\in S: a \\circ (a \\diamond b) = a = a \\diamond (a \\circ b)$$\n",
"\n",
"* **idempotence**\n",
"$$ \\forall a \\in S: a \\circ a = a$$\n",
"\n",
"There are many known algebraic structures that are defined by adhering to some of these. For example:\n",
"\n",
"* **monoid** is a *set is closed under the operation*, that is *associative* and has *identity* element. Strings with concat operation, or lists with append are monoids.\n",
"* **group** is a **monoid**, where for every element in set *inverse* exists. These are i.e. integers with addition, more interestingly set of $n \\times n$ invertible matrices with matrix multiplication operation.\n",
"* **semilattice** is is a *set is closed under the operation*, that is *associative*, *comutative* and *idempotent*. Integers and operation max(a,b), or min(a,b) form a semilattice\n",
"* **bounded semilattice** is a **semilattice** that is a **monoid**, for example, positive integers, max and 1.\n",
"* **lattice** is a set that has two operations that form a **semilatice**, where *absorbtion* for the two operations holds \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Monoids are useful\n",
"\n",
"There actually already is a pattern that is fairly similiar to monoid. It is the [Null Object pattern](https://en.wikipedia.org/wiki/Null_Object_pattern). But, because monoids have additional structure, with restctions on the operation to be *closed* and *associative*.\n",
"\n",
"Strings with concat (and `\"\"`), or lists with append (and `[]`), sets with union (and `set()`), dictionaries with union (and `{}`). What is even more interesting is that you can nest them, i.e. tuple of monoids is still monoid."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Latices are useful\n",
"\n",
"Another of the things where this might be helpful, is in distributed systems. When i.e. doing a replication of some data over a wire:\n",
"* **your requests could arive in wrong order**, but if updates would be *commutative*, this wouldn't be a problem \n",
"* **Same bit of data might be re-sent multiple times**, but if the updates would be *idempotent*, this wouldn't be a problem\n",
"\n",
"So we want a thing that is *commutative* and *idempotent* and that sounds like a **lattice**. There is [a good talk by Lindsey Kuper](https://www.youtube.com/watch?v=8dFO5Ir0xqY) about their usefulness in parallel programming.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Combining the power of abstract math with clarity of abstract math\n",
"\n",
"I think this nicely sums up the sentiment I have about using algebraic patterns. Because I like math. And I like the guarantees it gives me. That if I know that something is *commutative* I don't need to care if I do $a \\circ b$ or $b \\circ a$. That if something is *monoid* I can always initialize a value with its *identity element*.\n",
"\n",
"On the other hand, I understand that it might bring additional complexity where it wasn't needed previously. Using *lattices* for your data makes things simpler when you start scaling across your cluster, but they might not support all the operations you need. Or you just don't have them in a library for your language and the one you need is just too complex to implement yourself.\n",
"\n",
"So, lets keep that in mind. Next time, monoids?"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
},
"nikola": {
"category": "",
"date": "2017-05-11 17:23:02 UTC+02:00",
"description": "",
"link": "",
"slug": "algebraic-patterns-in-python",
"tags": "algebraic-patterns",
"title": "Algebraic patterns in Python",
"type": "text"
}
},
"nbformat": 4,
"nbformat_minor": 2
}