Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!att!emory!samsung!crackers!jjmhome!smds!rh
From: rh@smds.UUCP (Richard Harter)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 5: some clarifications
Summary: But is the statement true?
Message-ID: <211@smds.UUCP>
Date: 23 Oct 90 03:37:56 GMT
References: <66257@lanl.gov>
Organization: SMDS Inc., Concord, MA
Lines: 48

In article <66257@lanl.gov>, jlg@lanl.gov (Jim Giles) writes:

= I _have_ made the statement that
= all high-level data structures can be expressed as some combination of
= seven structures (and three attributes)...

= 1) atomic types (integers, floats, etc.)
= 2) enumerated types
= 3) arrays (one or _more_ dimensions)
= 4) sequences (variable size, one dimensional)
= 5) unions (always tagged)
= 6) Records (or STRUCTS, or whatever you want to call them).
= 7  Recursive data structures (just records with one or more recursive
=    components)

= Attributes are applicable to individual variables, not to whole data
= types.  Attributes are as follows:

= a) static, automatic, or dynamic....
= b) aliased...
= c) map ... as ....

Interesting.  Is this an opinion, or is this something that you can
prove?  Offhand it seems to that there are three requirements which
must be met to establish this claim.

I.	You need a specification or description of "high-level data
	structures" that is both general enough to actually include
	all high-level data structures and is detailed enough so that
	you can actually use it in proofs.

II.	You need to be able to show that the cited list can in fact
	express all high-level data structures.

III.	You also need to be able to show that this expression is
	effective, i.e. that the implementation cost in time and space
	of expressing an arbitrary high level structure in terms of
	the cited seven structures is of the same order as that of
	the arbitrary structure.

Has all of this been done?  If it has, it might be useful to post
references to the relevant work.
	
-- 
Richard Harter, Software Maintenance and Development Systems, Inc.
Net address: jjmhome!smds!rh Phone: 508-369-7398 
US Mail: SMDS Inc., PO Box 555, Concord MA 01742
This sentence no verb.  This sentence short.  This signature done.