Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!rex!caesar!fs
From: fs@caesar.cs.tulane.edu (Frank Silbermann)
Newsgroups: comp.lang.functional
Subject: Re: Intermediate Codes for Functional Languages
Message-ID: <5504@rex.cs.tulane.edu>
Date: 20 Dec 90 20:59:34 GMT
References: <1990Dec18.174225.27885@rice.edu> <5487@rex.cs.tulane.edu> <1990Dec20.190014.20982@rice.edu>
Sender: news@rex.cs.tulane.edu
Organization: Computer Science Dept., Tulane Univ., New Orleans, LA
Lines: 70


>>Aside from a desire to avoid unnecessary complexity,
>>what are some of the advantages of using a domain
>>that contains only those elements which can be denoted from the language?
>>(I ask this because sometimes adding extra elements
>>can make some aspects simpler -- just as judicious use
>>of "don't cares" can simplify manufacture of a logic gate.)

In article <1990Dec20.190014.20982@rice.edu> rama@titan.rice.edu
(Ramarao Kanneganti) writes:
>
>	The disadvantage I am aware of is: The equalities that hold in the
>	operational world do not hold in the denotational model. That is, if
>	you are using the denotational model to prove equalities between two
>	terms, even if they are unequal, you may not be able to conclude that
>	they are operationally unequal.
>
>	Ex: In the standard continuous model for functions in a sequential
>	language: 
> 
>	F_i = ...
>			if (f true bot)
>				if (not (f false false))
>				then i else bot
>
>	Operationally F_1 and F_2 are equal. They always diverge. However,
>	denotations of F_1 and F_2 are not equal. One of the "extra" elements
>	in the domain, i.e. parallel-or make F_i converge to i.

It seems more important, for the sake of referential transparency,
that denotational equality should imply operational equality.
(Is this what is meant by "adequacy" of the model?)

However, I don't forsee anybody complaining,
"I compared the execution of two programs on all possible inputs,
and though my denotational semantics says the programs are not the same,
after watching both for all eternity I noticed that
both results are equally undefined on everything I tried!"

The notion of operational equality seems incomplete to me,
because you _cannot_ compare their behavior on all possible inputs
if some of those inputs cannot be expressed in the language.

>	A similar example can be manufactured in case of "strict" cons also.

>>Will the advantages still hold, even when other constructors
>>(i.e function abstraction) _do_ result in extra domain elements?

>	By this, I assume that through some other constructor,
>	you are able to create the "extra" domain elements
>	that have been left out in the domain. In this case,
>	unless you use types to identify the exact
>	subdomain you are working with, I do not see the same disadvantage.
>	Eg: Introducing parallel-or as a a member of function type.
>	If you do not prohibit parallel-or being used as a function,
>	the above example would not create any problem.

Uh, I didn't understand that last part.
Could you please explain it again, more concretely?

My question was,
"Since our language is not going to be fully abstract anyway
(due to lack of provision for defining parallel functions),
what _further_ loss results from replacement of a strict-cons
by a lazy cons accessed from within a strict function
(so that arguments are verified as being above bottom
before application of the lazy cons)?

Frank Silbermann	fs@cs.tulane.edu
Tulane University	New Orleans, Louisianna  USA