COMPUTATIONAL AND LOGIC NOTES
A page full of ways to describe functions and model computation.
JECTIVE PROPERTIES
How elements from a domain map to its codomain.
injective:: a function that preserves distinctness between its inputs and outputs
surjective:: a function where its inputs cover all possible outputs
bijective:: exactly one-to-one match between a single input and single output. it's a combination of injective and surjective.
MORPHIC PROPERTIES
Various ways structures/categories are mapped/morphed to other ones.
homomorphic:: A->B (same shape of structures)
endomorphic:: A->A (same structures)
isomorphic:: A->B B->A (inversible structures)
DESCRIPTIVE METHODS
There are two ways to describe all things in existence.
intensional:: a term described by properties (e.g. a car is a machine with 4 tires and a steering wheel)
extensional:: a term described by all instances of the properties (e.g. all instances of objects with 4 tires and a wheel are cars)
COMPUTATIONAL MODELS
Ways to symbolically represent computation.
LAMBDA CALCULUS
An extremely useful model to represent computation.
(^x.M)N == ?:: MN
lambda calculus variable?:: x
lambda calculus abstraction?:: (^x.M)
lambda calculus application?:: (M N)
lambda calculus term/expression?:: any variable or abstraction
lambda calculus α-conversion:: (^x.M[x]) -> (^y.M[y])
lambda calculus β-reduction:: ((^x.M)E) -> (^x.M[x:=E])
lambda calculus η-conversion:: (^x.M x) -> (M x)
lambda calculus free variable?:: (^x.z) z is free because it is not bound
redex:: reducible expression
de bruijn index notation:: ^^^3 1 (2 1) higher number means further scope
LAMBDA-MU CALCULUS
An extension of Lambda calculus - gives it the ability to name terms, giving the
ability to arbitrarily trigger computations.
Imagine having a tree of functions, where each function can be tagged with the
same name:
....
function thing(x, y) {
return x + y
}
function thing2() {
return [b]function(p) { return p + 1 };
}
function thing3() {
return 3 + [b]function(p) { return p * 2};
}
thing(thing2(), thing3())
b = 9;
At this point, 9 would be applied to all functions tagged as 'b'.
I am using a mix of the notation of regular programming and lambda-mu.
Just to be explicit, here 'b = 9' means more than assignment, but also
"apply to all functions".
....
This means lambda-mu pass an arbitrary amount of arguments to
sub-expressions/terms/functions!
In lambda-mu it is impossible to reduce the lambda-mu variables, other than
doing a pointless tag: (lambda-mu a.[a]u) -> (u), since this is the same as just
applying (u) to everything: (w v x y z u)
This means you can do things we are familiar with in modern languages, like
javascript:
....
function thing4(a, b, c) {
return a + b + c.sum();
}
....
But the special thing is, we can call the function with different `c`'s, like
passing an array each time!
....
thing4(9, 1, [2, 3]);
thing5 = (thing4.bind(9).bind(1));
thing5([7, 3]);
....
You could also see it as a function with a variable-length of arguments! Like
`printf` in C.
PROCESS / PI CALCULUS
Taking lambda calculus and creating a more object oriented system from it.
Nothing here yet.
ALGEBRAIC DATA STRUCTURES / ABSTRACT ALGEBRA
Various mathematical / abstract structures that are widely applicable to many
domains / fields of study or even business logic.
ring:: an abelian group with a secondary operator
field:: a ring with additive inverse and multiplicative inverse
OTHER
kolmogorov complexity:: the length of a program / description language that describes/expands/creates a string of equal or larger size