Commit Checklist

11-Mar-2014 10:58AM

  • Are all the features in the specification implemented?
  • If things are different to the specification, are the reasons good enough?
  • Is there enough test coverage?
  • Do the unit-test's I wrote pass?
  • Are there any regressive failures?
  • Does it build?
  • It's OK to check in now.

Church Encoded Numbers with Lambda Calculus

05-Jan-2014 06:55AM

So the saga of Programming with Patterns continues, this time with Lambda calculus. Here are the things worth knowing about Lambda Calculus for laymen like myself.

Lambda Calculus is an equivalent of Turing Machines in its computational ability. Unlike Turing Machines, rather than dealing with operations on state, Lambda Calculus is composed purely of functions, specifically lambda functions. These are pure functions with no side affects, and as you can observe, the universe seems composed purely of the side affects of phenomena. Despite this, just like in typical mathematics, we can create abstractions that simulate the universe and ideas to perform the computation of our desires!

In our lesson with Barry Jay on Lambda Calculus, we were exposed to Church Encoding, an equivalent of Natural Numbers. Wikipedia will do a better job of explaining the theory than I ever could, but below I give an example of these implemented in the Pattern Calculus language bondi, using different variable names to our lecturer for clear and intuitive understanding.

( Remember that things in these parens are comments)

(* The aim here is to create numbers that can be used as:
 ~~three increment 0;;
> 3
~~ (add four five) increment 0;;
> 9
*)

let zero = fun f -> fun x -> x;;
(*Zero is equivalent to:
Number zero (Function increment, Number startingNum) {
     return startingNum;
}
*)

let successor = fun n -> fun f -> fun x -> n f (f x);;
(*
Let successor = (lambda (Function zeroOrSuccessor) { 
                               lambda (Function increment) { 
                                         Number (Function startingNum) {
                                                   return zeroOrSuccessor(increment, increment( startingNum ) );
}}}

So what happens is that every layer of successor increments "startingNum" until it reaches the zero function and startingNum is returned.
*)

let one = successor zero;;
let two = successor one;;
let three = successor two;;
let four = successor three;;
let five = successor four;;
let six = successor five;;
(*These numbers can be seen as:
 three ~= (successor (successor (successor zero)))
and can be evaluated with (three inc 0) 
*)



(* Typical increment function. *)
let increment = fun x -> x + 1;;


let plus = fun x -> fun y -> ((x successor) y);;
let expt = fun x -> fun y -> (y x)
let mul = fun x -> fun y -> (x (y successor) zero);;

But why does this matter?

The following is conjecture, and should only be taken with a grain of salt. Obviously, a computer that implements Church Encoding is slower than the typical bit manipulation, but what it does show is that Lambda Calculus can produce an abstraction that is functionally identical to Natural Numbers represented with bits. As with anything equivalent, they can be swapped out without impact to their universe, so long as Types are used to enforce that the swapped out abstractions aren't used invalidly. Because of that, we can enjoy both the power and expressiveness of completely functional language without sacrificing the speed advantages of our modern computer chips.


Compound Calculus

05-Jan-2014 06:54AM

So Compound Calculus is an extension to lambda calculus meant to look a bit like Lisp, though not quite, because we don't have types yet. I'll add more on this later, but for now, here is a definition of "select" using compound calculus-ish data structures within bondi.

let rec select1 =
  fun f x -> if isPair x 
    then (append (select1 f (car x)) (select1 f (cdr x))) 
    else (if (f x) 
      then [x] 
      else []);;

let rec update1 =
  fun f u x -> if isPair x 
    then (append (update1 f u (car x)) (update1 f u (cdr x))) 
    else (if (f x) 
      then [(u x)] 
      else []);;

A Thought about Thought

05-Jan-2014 06:48AM

I have a thought to share, and it's only a little one, but it hurts a little to think about. I want to read a book about the structures and abstractions we use to hold ideas in our heads. This is too vague a definition given the level of mummery around thought and consciousness and all of that other crap, so I'll try another definition. I want to read about the categories of symbols and shapes we manipulate in our head to simulate abstract representations of ideas. Still too vague.

Consider this thought exercise. The aim is to hold the entire picture of what's being said until you can no longer comprehend the meaning of the statement. What you want to do, is consider the relationship between two peoples perspectives of which colour the first person is thinking of and it goes like this:

  • Level One: Daniel is picturing the colour red.
  • Level Two: Shari thinks Daniel is picturing the colour orange.
  • Level Three: Daniel thinks, Shari thinks Daniel is picturing the colour yellow.
  • Level Four: Shari thinks, Daniel thinks, Shari thinks Daniel is picturing the colour green.
  • Level Five: Daniel thinks, Shari thinks. Daniel thinks, Shari thinks Daniel is picturing the colour blue.
  • Level Six: And so on...

The first level of this game is trivial. We can hold a direct picture of the relationship between "red" and "Daniel" in our heads, and intuitively this is the basis of higher level thought. The second level is also easy as we consider only two perspectives and so we can hold a picture of Daniels and Shari's relationship, even though it means holding three objects (Daniel, Shari, the colour red) and two relationships (thinks, picturing).

When I'm tired, the third level is barely accessible. When I'm at peak awareness I struggle to imagine level four and the levels beyond are completely beyond me. By this stage the sentences are words symbolic of some relationship between Daniel and Shari, but the number of levels and relationships is too deep to model. Most of us are reduced to creating a mental algorithm that can generate the sentence when we need it. The point of this game is to show that at least some types of higher level thought can be defined as mental pictures, but others require us to create symbols and algorithms that represent those structures.

Now here is the problem. What are the categories for the different symbolic tools and shapes we use to picture ideas in our day to day lives? There are a whole bunch of easily conceived of patterns we use, that as far as I know don't have formal categories . Here are a few:

  • Picturing a single relationship between entities. (Level One)
  • Picturing a list of relationships that can be applied to a pair of entities
  • Picturing a pair of entities and a set of actions that can be performed to derive relationships.
  • Picturing an algorithm that can recursively form a sentence that represents potentially infinitely recursive relationships between two entities. (Level Six and beyond)
  • Visually simulating an entities relationship with other entities on a two dimensional space whilst applying an internal list of transformations based on collisions with other entities. (Interestingly, this is easier to imagine than Level Four, but contains seemingly more complex abstractions.)
  • A tree of rules that apply transformations to an entity.
Some category names are obvious, such as stealing the term "Decision Tree" from computer science and intuitively, every computer science data structure definition can be used to categorise our different thought abstractions. My primary with this post is to raise the possibility that we can define useful abstracting techniques for dealing with difficult, multi-dimensional thought structures. If we are able to identify our own thought structures, we may be able to consciously optimise difficult ideas into more consumable chunks, and then communicate our internal macro's with other people in something other than our usual metaphor's to explain currently difficult to articulate ideas.

Problems with consciously analysing our own thought structures

And there most definitely are some. Here is my list so far:

  • Analysing your own thought abstractions adds more complexity, possibly making it harder to hold the abstraction itself in your head.
  • This might be another path of philosophical redundancy for the usual party of self-interested non-contributors to explore.
  • If thought abstractions are categorised poorly, we could be restricting ourselves from those which are unnamed.
  • This is something deeply personal to each of us so our differing perspectives may be true for each of us, thus rendering this concept redundant.

There is no conclusion to this thought yet. It is something to be played around with, and I hope it is interesting enough for other people to play with too. If this exists, I'd be deeply interested in learning about it, though have strong fears that as a meta-science it will be defended by an impenetrable wall of arcane jargon. I'd love if there were practical application to this idea, to better understand and describe overly complex systems in more human terms.


Music for a Bad Night

05-Jan-2014 06:16AM


Bondi API

05-Jan-2014 06:14AM

Pattern Calculus is a book by Dr. Barry Jay a lecturer at UTS. It features a language based on, ML called Bondi. Below are is some documentation I created for this language.

API

Types

  • Unit
  • Ref
  • Int
  • Float
  • String
  • Char
  • Cons
  • BinProd
  • Konstant (seriously?)
  • Identity
  • ParamProduct
  • Okay
  • Nested
  • Represent
  • Maybe

Infix Functions

name use description
String of the same type.
minus Num of the same type.
times Num of the same type.
divide Num of the same type.
negate negate Num to its negative.
lessthan Val of the same type.
- Num of the same type.
- -Num of the same type.
/ Num of the same type.
&& [arg] && [arg] AND boolean operator
|| [arg] || [arg] OR boolean operator
== [arg] == [arg] Equals operator.
: [wildcard] : [Type] Declares that the wild card will be of [Type]. This can only be used in pattern matching.
: [function name] : [Type1] -> [Type2] Declares that the function will take an argument of Type 1 and return an argument of Type 2
< [Val] [ [Val] Returns true if first value is less than second.
<= [Val] [= [Val] Returns true if first value is less or equal to second.
> [Val] > [Val] Returns true if first value is greater than second.
>= [Val] >= [Val] Returns true if first value is greater or equal to second.
;
->
[] [] Returns Nil
[] [[arg1],[arg2],[function] [arg3]] Returns a list of args, evaluating any unseparated functions. Lists can only contain one type of argument. Unknown if inheritance applies at this stage.
() () Absolutely nothing.
() ([function] [arg] [arg]) Executes functions in parens before other functions
() ([function],[arg],[arg]) Creates a cons list of the listed arguments
() ([function] [arg],[arg]) Evaluates function on arg, and returns a list of the comma separated args.
() ((((([function] [arg]))))) Returns the value of function

Functions

name use description
not not [arg] Should be obvious.
toString toString [arg] Converts the argument into a string.
print print [arg] Prints arg as string
println println [arg] prints arg on new line
forall forall [low] [high] [function] Apply function on all in range.
iter iter [Function] [Par] NFI
plus plus [List of two numbers OR List of Two Even lists of numbers] Either adds the two numbers together, or creates a new list of added numbers
clone [& args] Performs a shallow clone of arguments using divide and conquer
let let [rec/ext] [varname] = [Term] [optional in] Define global variables. Rec indicates recursion allowed, ext = NFI, in causes let to have temporary scope.
apply2all apply2all [function] [AnyArgs] Currently, NFI
datatype datatype [Name] [& args] = [Type] of [& args] and [Type] of [& args] and [& args] Create a new Type with the listed arguments, and define types of its arguments. The "and", "of" and "=" keywords are required syntactic sugar.
fst fst [Tuple] Returns the first element of a Tuple
snd snd [Tuple] Returns the second element of a Tuple
deconstruct decconstruct NFI
reconstruct reconstruct NFI
map map [function] [A deconstructable type] Create a clone of a datastruction with all arguments changed by the mapped function.
while while [boolean] do [function] else [function] While loop.
fun fun [& args] -> [function definition] Create a lambda function.
foldleft foldleft [function] [arg1] [List] Performs a recursive reduce, consuming the fist element in List until empty.
foldright foldright [function] [arg1] [List] peforms a recursive reduce, consuming the last element of List until empty.
zipwith zipwith [function] [List containing Lists] Creates a new list by mapping the function on the nth value in each list.