First, some context: I'm reading this blog post by Andrej Bauer.

So, I stumbled in these terms: "observational equivalence" and "contextual equivalence".

I know almost nothing about operational semantics ... I know it gives meaning for terms by it's reduction to normal form, if I'm not wrong.

Extensional equality says that two functions are equal if they always give the same result for the same input, for some definition of same result.

From what Wikipedia says about observational equivalence I can't see how is not the same thing as extensional equality .

So my question is: how these things (all three things) are related and what distinguish them?

My question maybe be simple to answer. But if not because I should know more operational semantics to be able to understand the answer, them I would be glad to be informed about some literature about this subject.

  • $\begingroup$ Your definition of extensional equality isn't a full definition yet, because you need to define what you mean by "same result", and there are multiple possible definitions of that. $\endgroup$ – D.W. May 24 '17 at 20:25
  • $\begingroup$ I confess that I'm having a hard time to define "same result". I could imagine as example alpha-equivalence of Lambda Calculus. $\endgroup$ – Rafael Castro May 24 '17 at 20:32
  • $\begingroup$ Terms don't need to be functions or even represent functions. Typically the value of observational equality is when they don't represent (mathematical) functions. I'm not sure how you see them as the same when they don't even apply to the same things. $\endgroup$ – Derek Elkins May 24 '17 at 22:01
  • $\begingroup$ @DerekElkins I hadn't noticed that they don't represent functions. Also, the Wikipedia says something about a notion of context that I'm not familiar with. As you can see, I don't know what "observational equivalence" is. $\endgroup$ – Rafael Castro May 25 '17 at 1:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.