22 ms·
> Are we still talking about models other than functional here? Because I'm surprised to hear you say that if so. TBH, I didn't understand your question, so I
by pron 9y ago
> Are we still talking about models other than functional here? Because I'm surprised to hear you say that if so.
TBH, I didn't understand your question, so I may have written something irrelevant. In any event, the functional denotation does not distinguish between two different algorithms for computing the same function, and cannot relate different expressions of the same algorithm (or none). This is not necessarily a disadvantage, but rather a conscious choice with various tradeoffs. But this choice has implications both on the ability to analyze and compose programs, especially when they're not sequential.
> whatever your example was supposed to show, you didn't actually use the monadicity of the state monad at all
Let me try again. Hopefully, these examples will make my point clearer. Consider:
fac5 :: Int -> IO ()
fac5 0 = writeFile "fac.txt" "1"
fac5 n = do
fac5 (n - 1)
f' <- readFile "fac.txt"
evaluate (force f') -- WTF
writeFile "fac.txt" $ show (n * (read f' :: Int))
fac6 :: Int -> State Int ()
fac6 0 = put 1
fac6 n = do
fac6 (n - 1)
f' <- get
put $ n * f'
There is simply no way to relate fac5 and fac6 to fac1 or fac2, even though they're the same computation. A lambda expression is opaque; you can't extract its internal operation to transform it into an "imperative" monad (the problem isn't that the expression is opaque, although making it transparent, as Lisp does, is one way of adding more power to languages based on LC; formalisms that don't use functional denotations allow for more powerful composition and an easier way to compare and relate algorithms while still having opaque expressions, but ones that don't represent functions).
There is a way to relate fac5 and fac6, but that requires rewriting them and extracting some common monad (maybe the free monad?) that will give them both the same denotation. (This, BTW, is another problem with functional formalisms. For example, in TLA+ (or even in Java, as you’ll see below), you just write your algorithm and then prove whatever it is that you want, and if your proposition is provable, this can always be done, by some completion theorems. However, in Lean, or let alone in Idris, you have to write your program with what you want to prove about it in mind. Oh, you also want to state a proposition about complexity? You have to rewrite the program with types that express complexity.)
Now, let's see how this can be done in formalisms with other denotations. Let's look at classical imperative programs, but first we need to understand what the denotation is (unfortunately, even people who are interested in the mathematics of programming often learn the mathematics of functional programs and not that of imperative ones). In imperative classical programs, the denotation of every statement is a transformation on state. It is not necessarily a function, as some statements are nondeterministic from the perspective of the static program, like generating a random number or reading input, which put the following state in one of many possible ones. Mathematically, there are two ways to describe this. We can view each statement as a relation on the previous state and the next one (the state machine denotation), or as the set of all propositions that are true in the preceding and following state (the Hoare triplet denotation). For our purposes, both are equally fine, but in my example it may be easier to consider the Hoare logic one, as I won’t be representing the relation formally.
How do we express this denotation formally? Well, as my example is in Java, I could use JML, a formal specification language embedded in Java programs, which, among other things allows you to create “ghost” variables and functions (those are variables that are not necessary for the computation, but are used to state things formally about the denotation) that are then removed from the program. But, to make things simpler (and I assume you don’t know JML), we’ll note that ordinary assertions do exactly that. They express a proposition that is either among the true ones or the false ones for that state. I’ll mark my ghost variables and functions in comments (unlike the Haskell programs, which I tested because I don’t really know Haskell, I didn’t test the Java ones, so forgive me if I’ve made some mistakes):
class Factorial {
// reasoning helpers:
int N; // ghost
int factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); } // oracle
long stackDepth(String name) {// the number of consecutive frames of the given method in the call stack
return StackWalker.getInstance().walk(stack ->
stack.dropWhile(f -> !f.getMethodName().equals(name))
.takeWhile(f -> f.getMethodName().equals(name))
.count());
}
// programs:
void fac1(int n) { N = n; /* ghost */ _fac1(n); }
int _fac1(int k) {
int f;
if (k == 0)
f = 1;
else
f = k * _fac1(k - 1);
// denotational specification
long n = k + stackDepth("_fac1") - 1; // ghost
assert( f == factorial(k) && n == N );
return f;
}
int fac2(int n) {
N = n; // ghost
int f = 1;
for (int k = 1; k <= n; k++) {
f = f * k;
// denotational specification
assert( f == factorial(k) && n == N );
}
return f;
}
void fac5(int n) { N = n; /* ghost */ _fac5(n); }
void _fac5(int k) {
// assuming appropriate methods, writeFile and readFile
if (k == 0)
writeFile("fac.txt", 1);
else {
_fac5(k - 1);
writeFile("fac.txt", k * readFile("fac.txt"));
}
// denotational specification
int f = readFile("fac.txt"); // ghost
long n = k + stackDepth("_fac5") - 1; // ghost
assert( f == factorial(k) && n == N );
}
void fac6(int n) { N = n; /* ghost */ _fac6(n); }
int F;
void _fac6(int k) {
if (k == 0)
F = 1;
else {
_fac6(k - 1);
F = k * F;
}
// denotational specification
int f = F; // ghost
long n = k + stackDepth("_fac6") - 1; // ghost
assert (f == factorial(k) && n == N);
}
}
As you can see, while the programs are very different from one another, the denotation of all is isomorphic, as is easily shown.
- pron 9y agoMinor correction: the fac1 Haskell program could be transformed to have the same meaning as fac6, but not the same as fac5, nor to the generalization of 5 and 6 employing the free monad.
- lmm 9y agoI still don't see what you're claiming (and I certainly don't see it as involving any equivalence between recursion and the state monad). If we want to reason operationally about fac5 and fac6, as you do in your Java/asserts example (if we're talking about things like stack depth it's definitely operational rather than denotational, that's the point of that terminological distinction), it's no harder to do that in Haskell; everything you've written there would translate very directly. The difference is that we can also reason about them denotationally; all we'd need is to define the equivalence between readFile/writeFile and get/put. I mean, IO specifically is, by design, the place we put things that we don't care to ascribe formal denotational semantics to, but that's not true for monads in general; plenty of monads form algebras that you can compare, reduce, and put in a canonical form like any other kind of expression; State has canonical semantics as a function and has its equivalence defined like the equivalence of functions (which are of course not something we can compare directly for equality, but that equality is still well defined - just not always provable). For an even clearer example, Writer literally is just a pair of values, and you can compare two Writer values directly for equality like any other value. Monads are a convenient tool for managing effects that we want to reason about operationally - they allow us to divide our program into a fragment we reason about denotationally and a fragment we reason about operationally - so you often see them used for that kind of effect, but to imagine that there's any difficulty in reasoning about them denotationally is to get it backwards. > There is a way to relate fac5 and fac6, but that requires rewriting them and extracting some common monad (maybe the free monad?) that will give them both the same denotation. You could write the function polymorphically (that's basically all final tagless style is). Or you could use a free monad as you suggest. Either way you can write expressions in terms of a set of effects (using coproducts in the general version of the free case) and then define the implementation of those effects later. > For example, in TLA+ (or even in Java, as you’ll see below), you just write your algorithm and then prove whatever it is that you want, True enough, but at the cost of doing twice as much work. With the functional approach you effectively just write your proof and get the algorithm for free. > and if your proposition is provable, this can always be done, by some completion theorems. Surely this can't be true in general - doesn't the halting problem make it impossible? > However, in Lean, or let alone in Idris, you have to write your program with what you want to prove about it in mind. Oh, you also want to state a proposition about complexity? You have to rewrite the program with types that express complexity.) True up to a point. You do have to delineate your effectful parts from your pure parts, and your pure parts are permanently pure since the pure fragment of the language has a very broad set of equivalences - as with any equivalence there's no way to make it unequivalent after you've used it in reasoning, so there's no way to recover a distinction between effects of pure code. It's the same for any kind of program analysis though - if you want to analyse the complexity of a program you can't reuse any of the analysis you did of some previous program property, you have to re-analyse every single function in terms of the new effect. So isn't it the same piece of work either way? But yeah, introducing this very broad equivalence has its costs - but without it you're left dealing with a space of possibilities that's far too large to reason about.