[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Question on terminology

[Forgive me if I missed the following point in the volume of articles
on letrec].

In the current debate about letrec, I've noticed many references to
circular data structures as "recursive."  With all due respect, is
this a proper use of the term?  I've usually seen the term "recursive
data TYPE"" used to refer to types that are recursively defined, as in
"a list is either null or comprises a head of arbitrary type and a
tail that is a list."  Alternatively, I have seen recursive data
structures defined as those that contain components having the same
type ("same type", not "pointers to objects of the same type",
although of course, pointers might be used in the implementation).
C.A.R.  Hoare, among others, have used the latter terminology (which,
because it does not mention "pointers", actually excludes circular
structures, since an object cannot contain itself.)

Even discounting the definitions of such people as Hoare---who is
famous but far outside the Lisp community---I don't like the equation
of "recursive" and "circular" for the simple reason that MY recursive
programs, at least, eventually terminate.  (Usually)

Paul Hilfinger