Category Theory in Computing Languages

​Is there any connection between category theory and the way computer languages work? by Thorsten Altenkirch 

Yes, lots.

Just one example: a function with 2 inputs from A and B and results from C would have the type A x B -> C but in functional languages like Haskell we are using A -> (B -> C), i.e. a function that returns a function. This “currying” is exactly a the categorical definition of a cartesian closed category as one where Hom(AxB,C) is isomorphic to Hom(A,B -> C) and in this false you can replace Hom(X,Y) with X -> Y.

It is well known that effects in functional programming can be modelled by monads which is a concept from category theory. Nowadays a weaker structure called applicative functors has become very popular – needless to say also a concept from Category Theory.

Not all languages are functional (yet) but even non-functional languages can be understood using concepts from category theory.

See also: 

Free Categories, Free MonoIds, Monads = MonoId+Endofunctor

Monad Diagram

Category Theory for Functional Programming

Category Theory is called “The Mathematics of Mathematics“, also the “Abstract Nonsense“.

image

Key Motivations for Category Theory 范畴 :
1. Programming is Math.
2. Object-Oriented is based on Set Theory which has 2 weaknesses:
◇ Set has contradiction: The famous “Russell’s Barber Paradox”.

image

image

Data Immutability for Concurrent Processing : OO can’t control the mutable state of objects, making debugging impossible.

Category (“cat“) has 3 properties:
1. Objects
eg. Set, List, Group, Vector Space, anything…
2. Arrows (“Morphism”, between Objects) which are Associative
eg. function, sheaf, etc
3. Identity Object

Note: If the Identity is “0” or “Nothing”, then it is called Free Category.

Extensions :
1. “Cat” = Category of categories, is also a category.
2. Functor 函子 = Arrows between Categories.
3. Monoid = A Category with ONLY 1 Object.

image

image

Monoid (么半群) is a very powerful concept (used in Natural Language Processing) — basically it is a Group with No ‘I‘nverse (Mo‘No‘-‘I‘-d).

image

image

Note: In the pure Functional Programming Language Haskell:
Monad (单子) = Monoid with endo-functor.
Endo- = to itself (自己) eg. “f : A -> A”

image

Recommended :
1. The Best Book on Category Theory : Lawvere et al, Cambridge (2009, 2nd Edition)

image

2. A humorous book on Category Theory by Dr. Eugenia Cheng (2016): (found in Singapore NLB Loan book #501.1 CHE)

image

Math Education Evolution: From Function to Set to Category

Interesting Math education evolves since 19th century.

“Elementary Math from An Advanced Standpoint” (3 volumes) was proposed by German Göttingen School Felix Klein (19th century) :
1)  Math teaching based on Function (graph) which is visible to students. This has influenced  all Secondary school Math worldwide.

2) Geometry = Group

After WW1, French felt being  behind the German school, the “Bourbaki” Ecole Normale Supérieure students rewrote all Math teachings – aka “Abstract Math” – based on the structure “Set” as the foundation to build further algebraic structures (group, ring, field, vector space…) and all Math.

After WW2, the American prof MacLane & Eilenburg summarised all these Bourbaki structures into one super-structure: “Category” (范畴) with a “morphism” (aka ‘relation’) between them.

Grothendieck proposed rewriting the Bourbaki Abstract Math from ‘Set’ to ‘Category’, but was rejected by the jealous Bourbaki founder Andre Weil.

Category is still a graduate syllabus Math,  also called “Abstract Nonsense”! It is very useful in IT  Functional Programming for “Artificial Intelligence” – the next revolution in “Our Human Brain” !

Java Family

Year Ver Code Name Description
1995 1.0 Java Applets
1977 1.1 Java Event, Beans, Internationalization
Dec 1978 1.2 Java 2 J2SE, J2EE, J2ME, Java Card
2000 1.3 Java 2 J2SE 1.3
2002 1.4 Java 2 J2SE 1.4
2004 1.5 Java 5 J2SE 1.5
Nov 2006 6 Java 6 Open-Source Java SE 6. “Multithreading” by Doug Lea
May 2007 OpenJDK free software
2010 Oracle acquired Sun
Jul 2011 7 Java 7 “Dolphin”
Mar 2014 8 Java 8 Lambda Function

Javac: Java Compiler

Java Distributions:

1. JDK (Java Developer Kit )
◇JRE & Javac & tools

2. JRE (Java Runtime Environment)
◇ JVM & core class libraries
◇ Windows / Mac / Linux

Java is Object-Oriented Programming (OOP):
1. Class
public class Employee {

public int age;
public double salary;

public Employee () { [<– constructor with no arg]
}

public Employee (int ageValue, double salaryValue) { [<- constructor with args]

age = ageValue;
salary = salaryValue;

}
}

2. Construct = create / instantiate objects from the Class template.

3. Constructor : used to construct an object
◇ Every class must have at least 1 constructor (default add one by compiler)
◇ Same name as the Class
◇ It is like a Method without return value.

3. Method
returnType methodName (args)

returnType : primitive | object | void

void : (method returns nothing)

Examples:
♡ Primitive : int

int add (int a, int b)

♡ Object : Address

Address getAddress ()

◇ Void
(Special Method)

public static void main (String [] args)

static members are not tied to class instances. The method main acts as the entry point to a class, is static because it must be called before any object is created (instantiated).

Naming Conventions:
◇ Class: Employee , Address
◇ Fields: firstName, maxAge, blockNumber…
◇ Method: getAddress ()