Re: call-time choice and extensionality

From: Juan Rodriguez Hortala <juanrh_at_fdi.ucm.es>
Date: Wed, 24 Aug 2011 09:47:35 +0200

El 24/08/11 06:48, Sebastian Fischer escribió:
> I think we need a different notion of extensionality for (possibly
> higher-order) expressions. A possible candidate that is in the spirit
> of Wikipedia's high-level description is observable equivalence itself
> because it judges objects based on their external properties. However,
> observational equivalence is of little use to decide if a language
> satisfies extensionality because it is defined in terms of all
> contexts the language provides. If there is, for example, a comparison
> operator that can distinguish expressions based on their definition,
> observational equivalence degrades to intensional equality.
Hi list

Sebastian, for what you say here maybe what you need is a fully abstract
semantics
(http://en.wikipedia.org/wiki/Denotational_semantics#Abstraction), in
which equality of denotations is equivalent to observable equivalence in
any context. Then you could say that two expressions are extensionaly
equivalent iff they have the same denotation in that semantics. We made
some advances regarding a fully abstract semantics for higher order FLP
in http://arxiv.org/abs/1002.1833, but it only works for programs
without extra variables.

Greetings

-- 
------------------------------------------------------------------------
Juan Rodríguez Hortalá
Profesor Ayudante Doctor / PhD Assistant Professor
Grupo de Programación Declarativa / Declarative Programming Group
E-Mail : juanrh_at_fdi.ucm.es
Home Page: http://gpd.sip.ucm.es/juanrh/
Tel: + 34 913947646
Despacho / Office: 220 (2ª planta / 2nd floor)
Dept. Sistemas Informáticos y Computación / Department of Computer Systems and Computing
Universidad Complutense de Madrid
Facultad de Informática
C/ Profesor José García Santesmases, s/n
E - 28040 Madrid. Spain
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mi Aug 24 2011 - 10:45:39 CEST

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:10 CET