2.7.3 A Minimal Set of Properties

For any trees x, y, and k, and any non-nil trees p, f, and g, the new invisible operator satisfies these conditions. In these expressions and hereafter, increasing abuse of notation is perpetrated by not writing the cons in expressions of the form cons(x,y).

P0

(nil,(nil,nil)) x = x

P1

(nil,((nil,nil),nil)) (x,y) = x

P2

(nil,(nil,(nil,nil))) (x,y) = y

P3

((nil,k),nil) x = k

P4

(((nil,(nil,nil)),nil),nil) (f,x) = f (f,x)

P5

((f,g),nil) x = f g x

P6

((f,nil),g) x = (f x,g x)

P7

((p,f),g) x = f x if p x is a non-nil tree, but g x if p x = nil

Although other properties remain to be described, it is worth pausing at this point because there is ample food for thought in the ones already given. An obvious question would be that of their origin. The short answer is that they have been chosen arbitrarily to be true by definition of the operator. At best, the completion of the construction may lead to a more satisfactory answer based on aesthetic or engineering grounds.

A more important question would be that of the relevance of the mystery operator and its properties to the stated purpose of this section, which is to specify the virtual machine code semantics. The answer lies in that the operator induces a function for any given tree t, such that the value returned by the function when given an argument x is t x. This function is the one that is implemented by the virtual code t, which is to say the way an application will behave if we put t in its virtual code file. An equivalent way of looking at the situation is that the virtual machine does nothing but compute the result of this operator, taking the tree in the virtual code file as its left operand and the input data as the right operand. By knowing what the operator will do with a given pair of operands, we know what to put into the virtual code file to get the function we want.

It is worthwhile to note that properties P0 to P7 are sufficient for universality in the sense of Turing equivalence. That means that any computable function could be implemented by the suitable choice of a tree t without recourse to any other properties of the operator. A compiler writer who finds this material boring could therefore stop reading at this point and carry out the task of targeting any general purpose programming language to the virtual machine based on the specifications already given. However, such an implementation would not take advantage of the features for list processing, exception handling, or profiling that are also built into the virtual machine and have yet to be described.

This document was generated on November 8, 2012 using texi2html 1.82.