As I understand the terms intensional and extensional, the effect of abstracting functionality into a procedure is to convert a somewhat extensional description of a program into a more intensional one. When you call a procedure, you're specifying the caller's behavior in an intensional way; if the procedure changes internally, the caller's behavior may change, even though the caller didn't change. That's the whole point of procedures; it's how they save us effort both in writing and reasoning about programs.
Determining equivalence seems to me like it's really at the root of how we work with large systems. I am making a change to code which someone or something uses; is the behavior here "observationally equivalent" to the old behavior in ways which are important to external entities?
2 comments:
As I understand the terms intensional and extensional, the effect of abstracting functionality into a procedure is to convert a somewhat extensional description of a program into a more intensional one. When you call a procedure, you're specifying the caller's behavior in an intensional way; if the procedure changes internally, the caller's behavior may change, even though the caller didn't change. That's the whole point of procedures; it's how they save us effort both in writing and reasoning about programs.
Determining equivalence seems to me like it's really at the root of how we work with large systems. I am making a change to code which someone or something uses; is the behavior here "observationally equivalent" to the old behavior in ways which are important to external entities?
Where do you draw the line between "the same" and "equivalent"?
Given two programs / subroutines / routines / functions / procedures / method calls, P1 and P2, input X and output Y.
1) Given X, P1 and P2 both output Y, but possibly different types of Y (say, 5 vs 5.0)
2) Given X, P1 and P2 both output Y, each with the same type.
Up to this point, nothing is said about the implementation of P1 and P2. Now, given that condition 2 is satisfied:
3) P1 and P2 use different algorithms and data structures.
4) P1 and P2 use the same algorithms, but different data structures.
5) P1 and P2 use the same algorithms and the same data structures.
Given condition 5 holds:
6) AST of P1 and P2 differ.
7) AST of P1 and P2 are the same, but variable names and types differ.
8) AST of P1 and P2 are the same, variable names differ, types are the same.
9) AST of P1 and P2 match.
Given 9 holds:
10) P1 and P2 are compiled to different architures.
11) P1 and P2 are compiled for the same architecture, but different optimization options.
12) P1 and P2 are compiled for the same architecture, and are compiled with the same options.
Given 12:
13) P1 and P2 are compiled on different machines.
14) P1 and P2 are compiled on the same machine.
15) P1 is copied and renamed P2.
I think that's it.
Post a Comment