pop@cs.umass.edu (06/08/90)
Richard O'Keefe states: > In a language with one-way matching (in the head of an equation, match > against existing terms, on the right hand side, construct new ones) > it can be determined at compile time when to use the constructor and > when to use the recogniser and projections. Indeed, as long as you > have a recogniser and projections, e.g. > view f(X:T) => (e_1:T_1,...,E_n:T_n) if test. > you can use pattern-matching *syntax* in one-way pattern matching > without requiring access to a constructor at all. (Presumably this > is the "view" mechanism that has been mentioned here.) But this is precisely my point about the use of constructors and destructors: The POP-2 Reference Manual [Burstall and Popplestone 1968 ] states: [my comments in square brackets]. "We can now state some relationships between the various functions on data structures. We will use a and b for data structures, x_1,....x_i,..x_k for items occurring ass components, s_1,.... s_1...s_k for selectors, u_1...u_i...u_k for update routines, c for a constructor, and d for a destructor. (a) s_1(a),....s_k(a) is the same n-tuple as d(a), that is they have equal elements. [equal in the manual is used to mean "identically equal", i.e. the LISP EQ, i.e. == in POP-11] (b) s_i(c(x_1...x_i...x_k))= x_i is true. (c) c(s_1(x),..s_k(x)) = x is always false, but the left-hand expression is equivalent to x. [This of course restricts the interpretation to conventional constructors, rather than e.g. standardising constructors like consword in POP] [The next two properties apply to updaters, and so are not relevant to the functional subset of POP] (g) From (a) and (b) above, d(c(x_1....x_k)) is the same n-tuple as x_1....x_k, that is, they have equal elements." Thus the destructor, d, together with a recogniser provides the minimum apparatus necessary to compile pattern recognition. Recognisers were not provided by the original POP-2 system, as they are in POP-11, instead a function samedata was provided to determine if two items were of the same data-class. This of course would not support abstraction. It should be noted that the "tuples", referred to in in the POP-2 manual are NOT items, as used in the technical sense of that manual. I.e. they do not have the status accorded to items in the "Items Charter of Rights" [Popplestone 1968] (e.g. they cannot be the value of variables), but instead are sequences of values existing on the open stack. In this, they differ from the tuples of ML, etc., and are `lightweight' in the sense that there is no garbage collection overhead associated with their creation. Thus the destructors described above are a practical way of implementing pattern recognition, at least in a stack based system like the POPLOG Virtual Machine, and, I understand, the various LISP machines, and require less baggage than explicit reference to selectors (or projection functions). I have a POP-11 let macro that does a partial implementation. let modulus(pt(x,y)) = sqrt(x^2+y^2). Produces the machine-oriented POP-11 code: [define modulus ( x__3 ) ; lvars x__3 ; lvars x y ; ; destpt ( x__3 ) -> y -> x ; return ( sqrt ( ^ ( x , 2 ) + ^ ( y , 2 ) ) ) ; enddefine ;] Which is then compiled using _popval_ I have assumed that smart ML compilers would be able to avoid the on-heap creation of tuples in many circumstances, and could in particular exploit destructors producing lightweight tuples, planting coercion functions between the lightweight, and heavyweight, heap-based representation of tuples as required. The POPLOG SML implementation is rather disappointing in this respect. Popplestone R.J.[1968] "The Design Philosophy of POP-2", Machine Intelligence 3, (Ed.D.Michie) Edinburgh University Press. Burstall, R.M. and Popplestone, R.J., [1968] The POP-2 Reference Manual, Machine Intelligence 2, pp. 205-46, eds Dale,E. and Michie,D. Oliver and Boyd, Edinburgh, Scotland.