Mindshift: Part 15

The entire Mindshift blog series has moved to langram.org/mindshift-series.

Click here to read Mindshift: Part 15 on langram.org

Thank you

Chris W

Advertisements

Building blocks of language, structure and thought

As I travel on my path to perhaps what I deem as some sort of enlightenment, back in time via Clojure to one of the great ancestors of language, structure and computational thought (Lisp), I continue to come across a simple theme.

Building Blocks

That theme is the concept of basic building blocks with which vast cathedrals can be constructed. Those building blocks are, in Lisp terms at least, car, cdr and cons.

One of my companions on this path is Daniel Higginbotham’s Clojure for the Brave and True. In Part II, covering Language Fundamentals, Clojure’s abstractions, or interfaces, are discussed. One of the Clojure philosophies is that the abstraction idea allows a simplified collection of functions that work across a range of different data structures. Abstracting action patterns from concrete implementations allows this to happen. This is nicely illustrated with a look the first, rest and cons functions from the sequence (or ‘seq’) abstraction.

Screen Shot 2016-02-01 at 07.12.54There’s a close parallel between first, rest & cons in Clojure and car, cdr & cons in other Lisps such as Scheme. And there’s an inherent and implicit beauty in a collection of constructs so simple yet collectively so powerful. You can read about the origins of the terms car and cdr on the Wikipedia page, which have a depth and a degree of venerability of their own. Essentially both sets of functions implement a linked list, which can be simply illustrated, as shown in the book and elsewhere, as a sequence of connected nodes, like this:

node1              node2              node3
+--------------+   +--------------+   +--------------+
| value | next |-->| value | next |-->| value | next |
+--------------+   +--------------+   +--------------+
    |                  |                  |
    V                  V                  V
  "one"              "two"              "three"

Implementing a linked list

Daniel goes on to show how such a linked list of nodes like this, along with the three functions, can be simply implemented in, say, JavaScript. Given that these nodes could be represented like this in JavaScript:

node3 = { value: "three", next: null }
node2 = { value: "two", next: node3 }
node1 = { value: "one", next: node2 }

then the first, rest and cons functions could be implemented as follows:

function first(n) { return n.value; }
function rest(n) { return n.next; }
function cons(newval, n) { return { value: newval, next: n }; }

With those basic building blocks implemented, you can even build the next level, for example, he shows that map might be implemented thus:

function map(s, f) {
  if (s === null) {
    return null;
  } else {
    return cons(f(first(s)), map(rest(s), f));
  }
}

To me, there’s a beauty there that is twofold. It’s implemented using the three core functions we’ve already seen, the core atoms, if you will. Moreover, there’s a beauty in the recursion and the “first and rest pattern” I touched upon earlier in “A meditation on reduction“.

Using the building blocks

Let’s look at another example of how those simple building blocks are put together to form something greater. This time, we’ll take inspiration from a presentation by Marc Feeley: “The 90 minute Scheme to C compiler“. In a slide on tail calls and garbage collection, the sample code, in Scheme (a dialect of Lisp), is shown with a tail call recursion approach thus:

(define f
  (lambda (n x) 
    (if (= n 0) 
        (car x) 
        (f (- n 1) 
           (cons (cdr x) 
                 (+ (car x) 
                    (cdr x)))))))

If you stare long enough at this you’ll realise two things: It really only uses the core functions car (first), cdr (rest) and cons. And it’s a little generator for finding the Nth term of the Fibonacci sequence:

(f 20 (cons 1 1)) ; => 10946

I love that even the example call uses cons to construct the second parameter.

I read today, in “Farewell, Marvin Minsky (1927–2016)” by Stephen Wolfram, how Marvin said that “programming languages are the only ones that people are expected to learn to write before they can read”. This is a great observation, and one that I’d like to think about a bit more. But before I do, I’d at least like to consider that studying the building blocks of language helps in reading, as well as writing.

 

 

 

 

 

 

 

 

 

Mindshift: Part 8

Using Minimal Functions To Build Predicates And Boolean Operators

In the last exciting episode of the Mindshift blog, we looked at how subtraction can be performed when our counting system only allows us to count upwards from zero.

Now we need to expand our range of predicate functions to perform various equality or equivalence tests, and from these, then build up a wider range of functional tools.

There’s Nothing There, Or Is There?

It would be pretty handy if we could determine whether a quantity function is ZERO or not. To put that in fancier language, how can we tell whether or not a quantity function has zero magnitude?

Lets remind ourselves of the basic definition of ZERO and ONE (ignoring the use of the SUCC function)

// ZERO and ONE
var ZERO = transform => start_value => start_value;
var ONE  = transform => start_value => transform(start_value);

Notice how the transform function is used inside the ZERO function – it isn’t. It’s completely ignored; all that happens inside ZERO is that the second parameter (start_value) is returned unmodified.

Aside

Let’s hold the definition of ZERO up against the definition of another function we’ve seen already – FALSE.
// ZERO and FALSE
var ZERO  = transform => start_value => start_value;
var FALSE = true_part => false_part  => false_part;
Ok, the parameter names are different, but the functionality is identical! Both ZERO and FALSE brainlessly return their second parameter unmodified.
This now provides us with a (possibly unexpected) way to demonstrate that it is far more than simply computing convention to evaluate Boolean false to zero – they are in fact functionally indistinguishable.

The only circumstance under which a quantity function will ignore its transformation function is when its magnitude is zero, and any non-zero quantity function will always apply its transform function some number of times to the start value.

Therefore, we can get a quantity function to reveal its magnitude by passing it a transformation function that, if called, will always return FALSE. We can pass a starting value of TRUE knowing that this will be returned only when the quantity function has a magnitude of zero.

// Define an IS_ZERO function
var IS_ZERO = qtyFn => qtyFn(dont_care => FALSE)(TRUE);

// A function to reify the Boolean functions TRUE and FALSE
var to_boolean = fn => fn(true)(false);

IS_ZERO(ZERO);             // -> Boolean function TRUE
to_boolean(IS_ZERO(ZERO)); // -> JavaScript primitive 'true'

IS_ZERO(ONE);             // -> Boolean function FALSE
to_boolean(IS_ZERO(ONE)); // -> JavaScript primitive 'false'

So now that we can determine whether a quantity function has a magnitude of zero, we can now define the “less than or equal to” predicate.

Less Is More (Than a Negative Number)

You might recall from the previous blog that our counting system cannot handle negative numbers. This means that we will get odd results such as 5 - 8 = 0 instead of the expected -3.

Apart from limiting all our calculations to give positive answers, this is in fact a useful feature that allows us to check whether one number is greater than another number.

All we need to do is subtract one number from the other, then pass the result to our new IS_ZERO function. And there you have it, a definition for the “less than or equal to” predicate.

// Define an IS_ZERO function
var IS_ZERO = qtyFn => qtyFn(dont_care => FALSE)(TRUE);

// A function to reify the Boolean functions TRUE and FALSE
var to_boolean = fn => fn(true)(false);

// Define an IS_LTE function
var IS_LTE = val1 => val2 => IS_ZERO(SUBTRACT(val1)(val2));

IS_LTE(TWO)(FIVE);                // -> TRUE, 2 is <= to 5
to_boolean(IS_LTE(TWO)(FIVE));    // -> JavaScript primitive 'true'

IS_LTE(SEVEN)(THREE);             // -> FALSE, 7 is not <= to 3
to_boolean(IS_LTE(SEVEN)(THREE)); // -> JavaScript primitive 'false'

Boolean Operators

Using the Boolean values of TRUE and FALSE, the normal Boolean operators of NOT, AND, OR and XOR can be defined.

// Define Boolean the values TRUE and FALSE
var TRUE  = true_part => false_value => true_part;
var FALSE = true_part => false_part => false_part;

// Define the Boolean Operators
var AND = bool1 => bool2 => bool1(bool2)(FALSE);
var OR  = bool1 => bool2 => bool1(TRUE)(bool2);
var NOT = bool  => bool(FALSE)(TRUE);
var XOR = bool1 => bool2 => bool1(NOT(bool2))(bool2);

AND(FALSE)(FALSE);   // -> FALSE
AND(TRUE)(FALSE);    // -> FALSE
AND(FALSE)(TRUE);    // -> FALSE
AND(TRUE)(TRUE);     // -> TRUE

OR(FALSE)(FALSE);    // -> FALSE
OR(TRUE)(FALSE);     // -> TRUE
OR(FALSE)(TRUE);     // -> TRUE
OR(TRUE)(TRUE);      // -> TRUE

NOT(FALSE);          // -> TRUE
NOT(TRUE);           // -> FALSE

XOR(FALSE)(FALSE);   // -> FALSE
XOR(TRUE)(FALSE);    // -> TRUE
XOR(FALSE)(TRUE);    // -> TRUE
XOR(TRUE)(TRUE);     // -> FALSE

Now that we have a “not” and a “less than or equal” operator, it is quite straight forward to adapt this to create a “less than” operator.

// Define an IS_LT function
var IS_LT = val1 => val2 => NOT(IS_LTE(val2)(val1));

Now that we have these tools available to us, we can start to look at arithmetic operations such as division and modulus. What makes these operations harder to implement is not only that they need to perform a SUBTRACT operation an unknown number of times, they must also be defined recursively.

I know I’ve been cheating slightly by assigning names such as TRUE, ZERO and MULTIPLY to our function definitions, but this is to account for our severely limited human ability to interpret long expressions. Really, names such as ZERO and MULTIPLY behave as macros that are substituted at runtime for the functions they represent.

Here, we also run up against another problem. Any recursively defined function must be able to make reference to itself; but if we create a DIV function that refers to itself directly by name, then we have broken our rule that functions may not directly refer to themselves by name.

At first, you might think this arbitrary restriction requires us to perform some pointless mental gymnastics simply to overcome our own self-imposed hurdles. Whilst this might be true from one particular perspective, from the wider perspective of wanting understanding the nature of computation, overcoming this hurdle leads us to an understanding of one of the most important constructs in functional programming – the Y-combinator.

Chris W

Mindshift: Part 7

Ordering a Takeaway

Subtraction, That Is, Not Fish & Chips…

In the previous Mindshift blog, we looked at how minimal JavaScript arrow functions can be used to define firstly a PAIR of values, and secondly how extracting the first or second item from such a PAIR yields a definition of the Boolean values of TRUE and FALSE.

So now that we have these definitions under our belt, we can look at how subtraction is implemented.

In the same way that the addition of a and b is defined as the b’th successor of a, so subtracting b from a amounts to nothing more than finding the b’th predecessor of a.

So the task for this blog is to develop a predecessor function1 and then from that, develop a SUBTRACT function.

Counting Backwards, Or Not…

First however, we must understand the constraints of our current counting system.

  1. We always start counting from zero
  2. We can only count upwards. I.E. this system provides no way to represent negative number

This does restrict the functionality of our SUBTRACT function, but that’s not an issue here for two reasons:

  1. We said we are only going to define the counting numbers, and by definition, these are the positive integers.
  2. Our primary focus is to understand the use of abstract functions, not create a full mathematical toolbox.

So given that our implementation cannot actually count backwards, we will have to think of the predecessor of a number in a different way.

The way we do can this is to think of numbers as pairs such as (n-1,n). Then, to derive the predecessor of a number, we start counting up from zero – but always keeping track of the numbers as pairs. This means that when we’ve finished counting up to n (the second number in our pair), the required predecessor will be the first number of the pair.

In the previous blog, we saw how the PAIR function operates, so now we need to apply that function to our situation.

Counting in Pairs

What we need now is a function that creates not just the successor of a single quantity function, but creates the successors of a PAIR of quantity functions. So what we need here is a SUCC_PAIR function.

Here, we will implement the “shift and increment” principle. A new pair of numbers is constructed as follows:

  • The first number in the new pair is the second number from the old pair
  • The second number of the new pair is the successor of the second number of the old pair.
// Abstract function to represent any two things and a function to apply
// to them

var PAIR = val1 => val2 => fn => fn(val1)(val2);

// Abstract functions representing TRUE and FALSE
var TRUE  = true_part => false_part => true_part;
var FALSE = true_part => false_part => false_part;

// Create a new version of the successor function that can operate on a
// pair of quantity functions.
// This function receives PAIR(n-1)(n) and performs a "shift and
// increment" operation in order to return PAIR(n)(n+1)

var SUCC_PAIR = pair => PAIR(pair(FALSE))(SUCC(pair(FALSE)));

Now let’s use this function to create the next two successor pairs to PAIR(ZERO)(ZERO) – which we expect to be PAIR(ZERO)(ONE) and PAIR(ONE)(TWO).

// Starting from PAIR(ZERO)(ZERO), create the next two successive pairs.
var p00 = PAIR(ZERO)(ZERO);
var p01 = SUCC_PAIR(p00);
var p12 = SUCC_PAIR(p01);

to_integer(p01(TRUE));    // -> 0
to_integer(p01(FALSE));   // -> 1

to_integer(p12(TRUE));    // -> 1
to_integer(p12(FALSE));   // -> 2

When Did Last See Your Father – Or Any Other Predecessor?

Lastly, to find the predecessor of any particular number n, we need to invoke the SUCC_PAIR function n times on the PAIR(ZERO)(ZERO), and the required predecessor will then be the first number of the resulting pair.

Do you remember how a quantity function works? A quantity function applies the transformation function to the starting value as many times as is represented by that quantity function.

Q: What’s our transformation function going to be?
A: The SUCC_PAIR function.

Q: What’s our starting value going to be?
A: We will define our starting point for counting to be PAIR(ZERO)(ZERO).

This means that the predecessor of any particular quantity function can be obtained by a two-step process: first, pass SUCC_PAIR and PAIR(ZERO)(ZERO) to the quantity function as the transformation function and starting value, and second, extract the first value from the resulting pair.

// Create a PREDecessor function by using SUCC_PAIR as the transformation
// function, and PAIR(ZERO)(ZERO) as the starting value. This will return
// a number PAIR where we are interested only in the first number.
// Therefore, pass the resulting pair to TRUE in order to extract the
// required value.

var PRED = qtyFn => qtyFn(SUCC_PAIR)(PAIR(ZERO)(ZERO))(TRUE);

PRED(EIGHT);              // -> The quantity function SEVEN
to_integer(PRED(EIGHT));  // -> 7

Phew! That was a lot of hard work just to create a predecessor function, but finally we’re in a position to define a SUBTRACT function.

Subtraction Engine

Since subtraction is non-commutative, we must stipulate that SUBTRACT always takes the second quantity away from the first; but apart from that, we’re using exactly the same principle as has been used before. In other words, to subtract b from a, apply the PRED function b times starting from a.

// Create a SUBTRACT function by applying the PRED function n times to the
// start value: where n is the second parameter and start_value is the
// first parameter.

var SUBTRACT = qtyFn1 => qtyFn2 => qtyFn2(PRED)(qtyFn1);

SUBTRACT(EIGHT)(FIVE);             // -> the quantity function THREE
to_integer(SUBTRACT(EIGHT)(FIVE)); // -> 3
to_integer(SUBTRACT(FIVE)(EIGHT)); // -> 0 Uh??
// Our counting system can't handle negative numbers, so this is the best
// it can do

Now that we have the ability to perform any subtraction whose answer is greater than or equal to zero2, we can start to look at other arithmetic operations such as modulus and division; but, as always, there’s a catch – in fact there are two catches caused by the fact that both the modulus and division operators are implemented using repeated subtraction:

  1. We must perform the SUBTRACT operation until the divisor becomes bigger than the remainder – yet, we have no functions such as IS_ZERO or IS_LTE (is less than or equal to).
  2. Then there’s the thornier problem that since we have no idea how many times to the SUBTRACT function will need to be called, it must called recursively.

Teeny weeny problem… Our ground rules state that all functions must be anonymous. Therefore, how can the function SUBTRACT call itself without referring to it by name?

This is where something called the Y-Combinator comes in; but more of that later.

Chris W


Footnotes

1) The definition of the predecessor function shown in this blog is not the only way this functionality could be implemented, but it is the simplest to understand. The following definition of the predecessor function is also widely used:

var PRED = n => f => x => n(g => h => h(g(f)))(y => x)(y => y);

Whilst this definition is equally valid, it is much harder to understand because it involves the use of nested wrapper functions – so we won’t look at this implementation here.

2) It might seem ridiculous to you that we have created a SUBTRACT function that yields zero when asked what 5 - 8 is. But this is not so wacky as it might seem. For more information on this type of operation, look up Monus – but be warned – you’ll be venturing into the lands of Abstract Algebra and Group Theory. Here be dragons.