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

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


--

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