🚀 go-pugleaf

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.