In some of the preceding posts of this series on an artificial life system in the Joy programming language, we have programmed a number of proteins. Conditional execution has been a crucial component of these protein programs. The need for branching logic has surfaced mostly in the recursive sections of our programs: if the base case is met then terminate else recurse.
Nevertheless, the use of the
ifte (if-then-else) and
false Joy functions isn't as pure as it could be for our purposes. First, I would like to limit the data types to only functions and quotations (lists of functions). We have already banished numbers and sets, but had to hold on to Booleans. Second, the
ifte function strikes me as being too high-level to be implemented as a primitive.
To be fair, "high-level primitives", numbers, sets, booleans, and strings are perfectly acceptable in Joy proper. For our purposes of constructing an artificial life system, however, we are looking for a minimal but useful subset of Joy.
The small set of functions/combinators
unit that we have encountered so far is enough to render Joy Turing-complete. It's actually more than enough because it turns out that a set of only two appropriately defined combinators will suffice. Take for instance the Ess-Kay (SK) system or some of the more exotic systems invented by Brent Kirby in his Theory of Concatenative Combinators. As such, it is not surprizing that many of these primitive combinators can be expressed in terms of some of the others:
cat == [[i] dip i] cons cons unit ==  cons cons == [unit] dip cat swap == unit dip dip == swap unit cat i i == [] dip dip pop
Could it also be possible to express
false in terms of these combinators?
We have treated
ifte as a primitive function so far. This means that it isn't a composite of other Joy functions. It is instead considered to be a given of the language, implemented in Elixir, the language in which we have implemented the Joy interpreter. Here is the implementation in Elixir:
def ifte(stack) do [else_quot, then_quot, if_quot | rest] = stack [result | _] = __execute(rest, if_quot) quot = if result !== false do then_quot else else_quot end __execute(rest, quot) end
It expects three quotations on the stack. At the top it expects the quoted else-block, below it the quoted then-block and below that the quoted if-block (the predicate). After having popped these quotations from the stack, it executes the if-block against the remainder of the stack. It then pops the resulting (usually boolean) value from the stack, checks that it is not equal to
false, in which case it executes the then-block against the stack as if the if-block was never executed. That is, before executing the then-block the stack is restored to the state in which is was prior to executing the if-block. If, on the other hand, the if-block leaves a
false on the stack, the else-block is executed, also against a restored stack.
This implementation allows us to call
ifte like this:
[if-block] [then-block] [else-block] ifte
For example (allowing integers and strings):
2 3 [<] ["the first value is smaller"] ["the second value is smaller"] ifte
Which would leave
2 3 "the first value is smaller" on the stack. There are two things to notice. All three of the quotations (if, then and else), when executed, only see
2 3 on the stack. In addition, if the if-block is executed and leaves anything other than
false on the stack, the then-block will be executed.
Our Elixir implementation of Joy treats all functions that don't have explicit definitions as if they simply place themselves on the stack. This means that the boolean
false, which are actually functions, would simply place themselves on the stack when executed. However, we could also explicitly implement
false in Elixir like this:
def unquote(true)(stack) do [true | stack] end def unquote(false)(stack) do [false | stack] end
unquote macro is required, because
false are something like reserved words in Elixir. In fact,
false are not strictly speaking booleans, but rather atoms:
iex(1)> true == :true true iex(2)> false == :false true
Their boolean semantics comes from the functions and macros (
and, etc.) that act on them. This is also true for our Joy implementation. The fact that the
true Joy function acts in the way that one would expect from the boolean
true can be entirely ascribed to the implementation of the
ifte function that acts on it.
This is good news because it means that we can make (compositions) of other Joy functions to assume the behaviour and meaning of booleans simply by how we implement
ifte and other functions that act on booleans. Let's take a short detour to the land of Church encoding, before we attempt to eliminate
false as Joy primitives.
Functions are the only primitive data types in untyped lambda calculus. It is nevertheless possible to represent numerals, booleans, lists, sets, characters and strings as higher order functions in untyped lambda calculus using Church encoding (named after Alonzo Church).
Similarly, everything in Joy is either a function or a quotation (list of functions). Some functions look like numerals, for instance the function
2 looks like the numeral
2, but it is still strictly speaking only a function. However, because of the Church-Turing thesis we can go one step further and eliminate even these literal-mimicking functions and replace them with compositions of a minimal base of primitive functions.
Church booleans are representations of the boolean true and false data types in terms of higher order functions (functions and quotations in Joy). Church booleans revolve around the concept of choice. Given
a represents truth, whereas selecting
b represents falsity:
true == λa.λb.a false == λa.λb.b
In case the lambda calculus notation is not all that clear, here are the same definitions as anonymous functions in Elixir:
true = fn a, b do a end false = fn a, b do b end
Let's turn to Joy to help us understand these definitions a bit better.
The two definitions of true and false as seen above can be represented in Joy as follows:
A B true == A A B false == B
That is, supposing that A is below B on the stack, then the function
true effectively pops B off the stack. Whereas, for an identical stack, the function
false would first swap A and B, then pop A off the stack. While these definitions agree with their counterparts in lambda calculus, they are still treated here as primitives. Let's see if we can change that.
We have already hinted at the solution.
true == [pop i] false == [swap pop i]
In what way do these definitions confer the semantics of boolean data types on the
false functions? There is nothing in these definitions that inherently make them boolean. Instead, the boolean semantics comes from how we define other functions such as
ifte that act on
then is a function that we would like to execute if a certain program
pred evaluates to true and that
else is a function that we would like to execute if
pred evaluates to false. We could make use of the primitive
ifte, which would expect
[else] to be on top of the stack, with
[then] just below it, and
[pred] below that.
ifte first executes
[pred] which evaluates (hopefully) to a boolean. If false,
[else] is executed, otherwise
[then] is executed.
In other words, we'd like
[true] [then] [else] ifte to evaluate to
[false] [then] [else] ifte to
else. But we are in search of a pure Joy implementation. Here is a first attempt:
ifte == dig2 i i
dig2 ==  cons cons dip digs out the element that is two positions below the top of the stack and places it on top of the stack. Let's see how it pans out:
[true] [then] [else] ifte [true] [then] [else] dig2 i i (definition of ifte) [then] [else] [true] i i (dig2) [then] [else] true i (i) [then] [else] [pop i] i (definition of true) [then] [else] pop i (i) [then] i (pop) then (i)
Similarly, for when
[pred] evaluates to
[false] [then] [else] ifte [false] [then] [else] dig2 i i (definition of ifte) [then] [else] [false] i i (dig2) [then] [else] false i (i) [then] [else] [swap pop i] i (definition of false) [then] [else] swap pop i (i) [else] [then] pop i (swap) [else] (pop) else (i)
However, this definition of
ifte is only sufficient if
pred doesn't have to perform operations on the stack. If
pred needs to operate on the stack, it would need to dig below
[then] [else] in order to get to the stack. While that is an option, we can get around this problem with a more robust definition of
ifte == unit cons unit cat i swap cat i
Let's see it in action (again permitting the numeral-like functions
3, and the comparison function
2 3 [<] [then] [else] ifte 2 3 [<] [then] [else] unit cons unit cat i swap cat i (definition of ifte) 2 3 [<] [then] [[else]] cons unit cat i swap cat i (unit) 2 3 [<] [[then] [else]] unit cat i swap cat i (cons) 2 3 [<] [[[then] [else]]] cat i swap cat i (unit) 2 3 [< [[then] [else]]] i swap cat i (cat) 2 3 < [[then] [else]] swap cat i (i) true [[then] [else]] swap cat i (<) [pop i] [[then] [else]] swap cat i (definition of true) [[then] [else]] [pop i] cat i (swap) [[then] [else] pop i] i (cat) [then] [else] pop i (i) [then] i (pop) then (i)
The corresponding evaluation with
> instead of
< is left as an exercise to the reader. This definition of
ifte essentially ensures that
[pred] is evaluated against the stack that is below
[then] [else] and assumes that the result is a quoted boolean. It then brings the boolean to the top of the stack and executes it, which in turn conditionally executes either the
[then] or the
[else] quotations. It only works as expected if
[pred] evaluates to exactly
Finally, after executing
ifte primitive restored the stack to what it was before executing
[pred]. This allows
[else] to operate on the data that
[pred] used to make a decision. Our composite definition of
ifte doesn't have this property (yet).
We can now also define
First we define the function
branch. It is similar to
ifte, but expects a boolean in stead of a predicate:
true [then] [else] branch == then false [then] [else] branch == else
branch is roughly the composition of
dip. We can define it as:
branch == unit cons swap cat i
branch turns out to be very useful in the definitions of the boolean operators
xor. First up, here is
or == [pop true]  branch
We expect that the following holds:
true true or == true true false or == true false true or == true false false or == false
Here are some worked examples.
false true or false true [pop true]  unit cons swap cat i (definition of or and branch) false true [pop true] [] cons swap cat i (unit) false true [[pop true] ] swap cat i (cons) false [[pop true] ] true cat i (swap) false [[pop true] ] [pop i] cat i (definition of true) false [[pop true]  pop i] i (cat) false [pop true]  pop i (i) false [pop true] i (pop) true (i pop true)
true false or true false [pop true]  branch true false [pop true]  unit cons swap cat i true false [pop true] [] cons swap cat i true false [[pop true] ] swap cat i true [[pop true]] false cat i true [[pop true]] [swap pop i] cat i true [[pop true] swap pop i] i true [pop true] swap pop i true [pop true] pop i true  i true
The definition of
and uses the same line of logic:
and ==  [pop false] branch
A worked example:
true true and true true  [pop false] branch true true  [pop false] unit cons swap cat i true true  [[pop false]] cons swap cat i true true [ [pop false]] swap cat i true [ [pop false]] true cat i true [ [pop false]] [pop i] cat i true [ [pop false] pop i] i true  [pop false] pop i true  i true
not essentially replaces
false and the other way around:
not == [false] [true] branch
Here are worked examples for the only two cases that we have to consider:
false not false [false] [true] branch false [false] [true] unit cons swap cat i false [false] [[true]] cons swap cat i false [[false] [true]] swap cat i [[false] [true]] false cat i [[false] [true]] [swap pop i] cat i [[false] [true] swap pop i] i [[true] [false] pop i] i [true] [false] pop i [true] i true
true not true [false] [true] branch true [false] [true] unit cons swap cat i true [[false] [true]] swap cat i [[false] [true]] true cat i [[false] [true]] [pop i] cat i [[false] [true] pop i] i [false] [true] pop i [false] i false
Finally, we can define
xor in terms of
xor == [[false] [true] branch]  branch xor == [not]  branch
And here are worked examples for all the possible cases:
true true xor true true [not]  branch true true [not]  unit cons swap cat i true true [[not] ] swap cat i true [[not] ] true cat i true [[not] ] [pop i] cat i true [[not]  pop i] i true [not]  pop i true [not] i true not false
false false xor false false [not]  branch false false [not]  unit cons swap cat i false false [[not] ] swap cat i false [[not] ] false cat i false [[not] ] [swap pop i] cat i false [[not]  swap pop i] i false  [not] pop i false  i false
true false xor true false [not]  branch true false [not]  unit cons swap cat i true false [[not] ] swap cat i true [[not] ] false cat i true [[not] ] [swap pop i] cat i true [[not]  swap pop i] i true [not]  swap pop i true  i true
false true xor false true [not]  branch false true [not]  unit cons swap cat i false true [[not] ] swap cat i false [[not] ] true cat i false [[not] ] [pop i] cat i false [[not]  pop i] i false [not]  pop i false [not] i false not true
false in some of the more low-level Joy primitives, we have eliminated the need to treat them as amino acids in our artificial life system. Doing so is mostly a matter of personal preference. The goal is not to minimize the number of required amino acids to the bare minimum, but rather to arrive at a pleasing middle ground.
One aspect that we have neglected in this post is the requirement of a predicate function that will actually yield
[pop i] for true and
[swap pop i] for false. In our example we used the primitive
<, which isn't actually part of our artificial life system. While it is trivial to come up with a function (composition) that will yield either one of these booleans, such a function would still have to know when to yield the one or the other in some meaningful way that is arbitrary yet deterministic.
Knowing that 2 is less than 3 was built into the definition of
<, which is therefore primitive. Therefore, in order to use
ifte, or rather
unit cons unit cat i swap cat i in a way that makes it mean what the primitive
ifte meant, we still need a predicate function of sorts. The current predicate that we rely on in our protein programs has been
equal, a function that checks if the two top elements of the stack are equal. We'll see how we can replace that with something more fuzzy. Life loves fuzzy.