Thu, 23 Nov 1995 18:57:07 GMT

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) |

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.