2.7.17 Vacant Address Space

Not every possible pattern has been used by the virtual machine as a way of encoding a function. The following patterns, where a, b, and c are non-nil trees, do not represent anything useful.

unary forms

((nil,nil),((nil,nil),(nil,((nil,a),nil))))
((nil,nil),((nil,nil),(nil,(nil,(nil,a)))))

binary forms

((nil,nil),((nil,nil),(a,b)))
((nil,nil),((a,nil),(b,nil)))
((nil,nil),((a,nil),(nil,b)))

ternary forms

((nil,nil),((a,b),(c,nil)))
((nil,nil),((a,b),(nil,c)))
((nil,nil),((a,nil),(b,c)))
((nil,nil),((nil,a),(b,c)))

These patterns are detected by the virtual machine simply to avoid blowing it up, but they always cause an error message to be reported.

P55

For f matching any of the first three trees in the above list,
   f_n x_n = [[('unsupported hook',nil)]]_(n+1)

P56

For the remaining trees f in the above list,
   f_n x_n = [[('unrecognized combinator (code m)',nil)]]_(n+1)

Here, m is a numeric constant dependent on which tree f was used. The unsupported hook message is meant to be more informative than the unrecognized combinator message, suggesting that a feature intended for future use is not yet available.

This list has been assembled for the benefit of readers considering the addition of backward compatible extensions to the virtual code semantics, who are undeterred by the facts that

• the computational model is already universal
• virtual code applications are already interoperable with all kinds of high performance software having a text based or console interface by way of the interact combinator
• an unlimited number of built in library functions can be added by way of the library combinator as described in Implementing new library functions
• the C code in avram makes fairly intricate use of pointers with a careful policy of reference counting and storage reclamation
• there is also a performance penalty incurred by further extensions to the semantics, even for applications that don't use them, because a pattern recognition algorithm in the interpreter has more cases to consider.

Nevertheless, a new functional form combining a pair of functions to be interpreted in a new way by the virtual machine could be defined using any of the binary forms above, for example, with a as the virtual code for one of the functions and b as that of the other. Such a form would not conflict with any existing applications, provided that both a and b are not nil, which is true of any valid representation for a function.

Virtual machine architects, take note. There are infinitely many trees fitting these patterns, but it would be possible to use them up by assigning them without adequate foresight. For example, if interpretations were assigned to the four ternary forms, the three binary forms, and one of the remaining unary forms, then the only unassigned pattern could be of the form

     ((nil,nil),((nil,nil),(nil,(nil,(nil,a)))))

Assigning an interpretation to it would leave no further room for backward compatible expansion. On the other hand, any tree of the following form also fits the above pattern,

     ((nil,nil),((nil,nil),(nil,(nil,(nil,(b,c))))))

with any values for b and c. Different meanings could be chosen for the case where both are nil, both are non-nil, or one is nil and the other non-nil, allowing two unary forms, one binary, and one constant. If at least one of these patterns is reserved for future enhancements, then a potentially inexhaustible supply of address space remains and there will be no need for incompatible changes later.