16
$\begingroup$

Q1. When can we say that two programs (written in some programming language like C++) are different?

The first extreme is to say that two programs are equivalent iff they are identical. The other extreme is to say two programs are equivalent iff they compute the same function (or show the same observable behavior in similar environments). But these are not good: not all programs checking primality are the same. We can add a line of code with no effect on the result and we would still consider it the same program.

Q2. Are programs and algorithms the same kind of object? If not, what is the definition of an algorithm and how does it differ from the definition of a program? When can we say two algorithms are equivalent?

Improve this question
$\endgroup$
7
  • $\begingroup$ The program isomorphism problem? Can't one ask "is this program isomorphic to the program that always halts?" and recover the Halting Problem? If we restrict ourselves to the Bounded Halting Program Problem isn't this just graph isomorphism? $\endgroup$
    – user834
    Dec 13, 2011 at 19:53
  • 5
    $\begingroup$ When are two algorithms the same? arxiv.org/abs/0811.0811 $\endgroup$
    – sdcvvc
    Dec 14, 2011 at 1:51
  • 1
    $\begingroup$ Wouldn't it depend entirely on the context? Getting a bit philosophical here, but a bolted-down chair and an upside-down bolted-down chair are the same thing physically but not the same in terms of the idea of a chair. $\endgroup$
    – Rei Miyasaka
    Dec 14, 2011 at 6:16
  • $\begingroup$ Slightly off-topic, but, since proofs are programs ... gowers.wordpress.com/2007/10/04/… $\endgroup$
    – Radu GRIGore
    Jan 3, 2012 at 13:44
  • 1
    $\begingroup$ The following article is very related. I have only skimmed through it some time ago, but Blass and Gurevic usually write really well (I just don't recall reading anything else by Dershowitz, not saying it usually isn't very readable). research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf WHEN ARE TWO ALGORITHMS THE SAME? ANDREAS BLASS, NACHUM DERSHOWITZ, AND YURI GUREVICH $\endgroup$
    – kasterma
    Nov 17, 2013 at 13:00

3 Answers 3

Reset to default
19
$\begingroup$

Q1: There are many notions of program equivalence (trace equivalence, contextual equivalence, observational equivalence, bisimilarity) which may or may not take into account things such as time, resource usage, nondeterminism, termination. A lot of work has been done on finding usable notions of program equivalence. For example: Operationally-Based Theories of Program Equivalence by Andy Pitts. But this barely scratches the surface. This should be useful even if you are interested in when two programs are not equivalent. One can even reason about non-halting programs (using bisimulation and coinduction).

Q2: One possible answer to part of this question is that interactive programs are not algorithms (assuming that one considers an algorithm to take all of its input at once, but this narrow definition excludes online algorithms). A program could be a collection of interacting processes that also interact with their environment. This certainly doesn't match with the Turing-machine/Recursion theory notion of algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ IO and side effects in general are not covered by classical algorithm notions at all. $\endgroup$
    – Raphael
    Dec 15, 2011 at 13:04
15
$\begingroup$

The other extreme is to say two programs are equivalent iff they compute the same function (or show the same observable behavior in similar environments). But these are not good: not all programs checking primality are the same. We can add a line of code with no effect on the result and we would still consider it the same program.

This is not an extreme: program equivalence must be defined relative to a notion of observation.

The most common definition in PL research is contextual equivalence. In contextual equivalence, the idea is that we observe programs by using them as components of larger programs (the context). So if two programs compute the same final value for all contexts, then they are judged to be equal. Since this definition quantifies over all possible program contexts, it is difficult to work with directly. So a typical research program in PL is to find compositional reasoning principles which imply contextual equivalence.

However, this is not the only possible notion of observation. For example, we can easily say that the memory, time, or power behavior of a program is observable. In this case, fewer program equivalences hold, since we can distinguish more programs (eg, mergesort is now distinguishable from quicksort). If you want to (say) design languages immune to timing channel attacks, or to design space-bounded programming languages, then this is the sort of thing you have to do.

Also, we may choose to judge some of the intermediate states of a computation as observable. This always happens for concurrent languages, due to the possibility of interference. But you might want to take this view even for sequential languages --- for example, if you want to ensure that no computations store unencrypted data in main memory, then you have to regard writes to main memory as observable.

Basically, there is no single notion of program equivalence; it is always relative to the notion of observation you pick, and that depends on the application you have in mind.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ It's worth pointing out that there is no unique notion of contextual equivalence (or contextual congruence) either, for example if the programming language in question is interactive (i.e. does not yield a value). $\endgroup$
    – Martin Berger
    Dec 14, 2011 at 14:52
  • $\begingroup$ While the rest of your answer is excellent, I think that I disagree with this: "program equivalence must be defined relative to a notion of observation". That's only true for observational notions of equivalence. $\alpha$-equivalence isn't such a notion, but it's very much a kind of program equivalence. $\endgroup$
    – Sam Tobin-Hochstadt
    Dec 14, 2011 at 15:19
  • 1
    $\begingroup$ @NeelKrishnaswami, I think this is just begging the question. $\alpha$ is an equivalence, and there are programming languages where it doesn't respect observational equivalence. See Wand's "The Theory of Fexprs is Trivial". Other times, it's not an equivalence that you can use for optimization, for example if debugging is important. Both of these add observations that violate $\alpha$. $\endgroup$
    – Sam Tobin-Hochstadt
    Dec 15, 2011 at 18:01
  • 1
    $\begingroup$ @SamTobin-Hochstadt. Ok, let us forget "usual". The feeling I get is that you are saying the same thing that Neel said, which was quite well-thought out in my opinion. Your idea, which is still vague to me, can be formalized in Neel's framework by picking the right kind of observations and the right kind of program contexts. $\endgroup$
    – Uday Reddy
    Mar 6, 2012 at 23:41
  • 1
    $\begingroup$ @UdayReddy Consider the $\lambda$-calculus. What context can distinguish $\lambda x.x$ from $\lambda y.y$? None. We could change the language so that we can make this distinction, but then we lost the concept we had before -- observational equivalence in the lambda-calculus is a useful tool. Instead, we should recognize that in the LC, we can't distinguish the terms with in-language observations, even though they're different terms. $\endgroup$
    – Sam Tobin-Hochstadt
    Mar 9, 2012 at 1:35
2
$\begingroup$

Q2: I think usual theoretical definitions don't really distinguish between algorithms and programs, but "algorithm" as commonly used is more like a class of programs. For me an algorithm is sort of like a program with some subroutines left not fully specified (i.e. their desired behavior is defined but not their implementation). For example, the Gaussian elimination algorithm doesn't really specify how integer multiplication is to be performed.

I am sorry if this is naive. I don't do PL research.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The idea is probably that there are multiple implementations for those subroutines and you don't care which is chosen as long as it performs according to your specification. $\endgroup$
    – Raphael
    Dec 15, 2011 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.