Investigations into Iconic Representations of Combinators
Antoni Diller · OpenGrey (Institut de l'Information Scientifique et Technique) · 2000
Various properties of two bracket abstraction algorithms, previously introduced, are discussed and some of them are proved in this paper. Algorithm (L) is uni-variate and uses yes-no representations, whereas algorithm (M) is multi-variate and uses array representations. It is shown that (a) both algorithms are structure-preserving, (b) there is a straightforward connection between [x] P and [x] Q, produced by algorithm (L), if the primal components of Q, except the first, are a permutation of the primal components of P , except the first, (c) there is a simple connection between the two abstracts produced when algorithm (L) is used repeatedly on the same input term, but the abstractions are performed in a different order in each case, (d) there is a straightforward connection between the array representations produced by algorithm (M) and the yes-no representations produced when algorithm (L) is used to abstract the same variables individually from the same input term and (e) using algorithm (M) multi-variate abstraction can be “partitioned”.