[TYPES] CPO semantics of recursive types

Achim Jung A.Jung at cs.bham.ac.uk
Thu Oct 26 10:05:51 EDT 2006


Malcolm, for cpos and continuous functions we have solutions to all 
recursive domain equations, for example, D =  [D -> D].

If [D -> D] is interpreted as the (pointwise ordered) cpo of monotone 
functions then D = [D -> D] has only the one-point cpo as a solution. This 
was first shown in the paper

@Article{davies71,
   author = 	{R. O. Davies and A. Hayes and G. Rousseau},
   title = 	{Complete Lattices and the Generalized {Cantor}
 		  Theorem},
   journal = 	{Proceedings of the AMS},
   year = 	1971,
   volume = 	27,
   pages = 	{253--258}
}

Best regards,

Achim.

-------------------------------------------------------------------------
  Prof Achim Jung			Tel.: (+44) 121 41 44776
  School of Computer Science		Sec.: (+44) 121 41 43711
  The University of Birmingham		Fax.: (+44) 121 41 44281
  Edgbaston				Email: A.Jung at cs.bham.ac.uk
  BIRMINGHAM, B15 2TT			Web: http://www.cs.bham.ac.uk
  England
-------------------------------------------------------------------------



On Thu, 26 Oct 2006, Malcolm Tyrrell wrote:

> [ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
>
>
> Hello,
>
> I have a question concerning the denotational semantics of
> recursive types using complete partial orders.
>
> For a programming language, the domain for a function type T->U is
> defined as the space of all continuous functions from the domain of T
> to the domain of U. I understand that recursively defined domains
> have solutions in this semantics.
>
> I am working with a specification language, and the domains I'm using
> for function types T->U is the space of all *monotonic* functions from
> the domain of T to the domain of U. Can anyone tell me (or even better,
> point me to a reference) whether this has any ramifications for the
> existence of recursively defined domains?
>
> Thanks for any help,
>
> Malcolm.
>


More information about the Types-list mailing list