Re: Request: Ref to Scott's proof of recursive structure minimality

dirkd@daimi.aau.dk (Dirk Dussart)
Thu, 23 Nov 1995 18:57:07 GMT

          From comp.compilers

Related articles
Request: Ref to Scott's proof of recursive structure minimality Terrence Brannon (1995-11-04)
Re: Request: Ref to Scott's proof of recursive structure minimality cliffc@ami.sps.mot.com (1995-11-06)
Re: Request: Ref to Scott's proof of recursive structure minimality dirkd@daimi.aau.dk (1995-11-23)
| List of all articles for this month |

Newsgroups: comp.compilers
From: dirkd@daimi.aau.dk (Dirk Dussart)
Keywords: theory, functional
Organization: DAIMI, Computer Science Dept. at Aarhus University
References: 95-11-028 95-11-075
Date: Thu, 23 Nov 1995 18:57:07 GMT

Cliff Click (cliffc@ami.sps.mot.com) wrote:
: Terrence Brannon (brannon@rana.usc.edu) writes:


: > I am reading a book called "Functional Programming" by
: > B.J. Maclennan. He states:
: >
: > "Scott(1974) showed that recursive structure declarations
: > always have a unique minimum solution."
: >
: > However, there is no ref to this paper in his biblio. Can anyone point
: > me to the proper paper?




: P.S. This is not to say that Scott didn't prove it in '74, it's just
: that I also don't have a reference to Scott.


A guess would be that Maclennan refers to Dana Scott and domain
theory. Domain theory allows us to solve recursive domain equations.
A quite natural interpretation of recursive structures is to use least
fixed points and this refered to as the unique mimimal solution, since
least fixed points are unique up to isomorphism.


If you want to find more about this theory, consult any book on
denotational semantics: e.g Schmidt's book


-- Dirk


--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.