Kotlin: A Language with a Bright Future
venturi-group.com
venturi-group.com
E.g. already there's no way to reuse logic between code paths that operate on Kotlin nullable types, Java Options (needed for compatibility with Java streams or more generally other JVM libraries), or rust-style Result types (for which there are several Kotlin libraries already, because it's a very useful concept and the language mostly has the facilities to support it), even though all three behave almost identically and you would often want to do the same thing in all three cases. But since the language won't let you represent what these types have in common, your only option is to copy/paste the code.
I don't think so. Java has been used successfully in large codebases, probably more so than Scala, and Kotlin, like Go, is a language following Java philosophy.
> I think Kotlin has literally every one of those ad hoc solutions built into the language, but stubbornly avoids making the generalisation.
1. Ask yourself why does it stubbornly avoid making such generalizations. There are very, very good reasons. 2. Kotlin has delimited continuations, which express anything monads can (with a minor, unimportant caveat, which has to do with the particular features of Kotlin coroutines), in a way that blends much more nicely with imperative languages features that abound in both Kotlin and Scala, and composes much more nicely than monads (although that requires a feature currently absent an Kotlin's coroutines, but the feature is largely unnecessary for the kind of code Kotlin aims at).
> already there's no way to reuse logic between code paths that operate on Kotlin nullable types, Java Options
That's not really accurate. Kotlin does this blending at least as well if not better than Java. Java options are not really intended to be used in the same way they're used in Scala.
> or rust-style Result types (for which there are several Kotlin libraries already, because it's a very useful concept and the language mostly has the facilities to support it)
Those are not idiomatic in Kotlin, and some (like me) think that the Kotlin idioms are better, at least for the kind of code it aims to support.
> But since the language won't let you represent what these types have in common, your only option is to copy/paste the code.
I don't think it is a language's job to support all idioms out there, even if they can be useful in some circumstances. Languages following the Java philosophy -- as opposed to Scala -- aim to be at least somewhat opinionated, and encourage similar coding patterns in all cases, even if some idiom can be marginally better suited in some specific case. It's a tradeoff between code homogeneity and being "multi-paradigm", which can only be settled by the values of the language. There is no right or wrong answer here. Kotlin's values are very, very different from Scala (even if many features are shared), which is why Kotlin was created in the first place. Its designers wanted a modern language in the Java tradition (I know that from directly talking to them), not in the Scala tradition.
Java didn't have anything like as many ad-hoc language-level features as Kotlin has - checked exceptions are the only thing that's really comparable, and their reputation is decidedly mixed (note even Kotlin hasn't included them).
> Kotlin has delimited continuations, which express anything monads can (with a minor, unimportant caveat, which has to do with the particular features of Kotlin coroutines)
They can, but only in the same sense that an untyped language can express anything that a typed language can. They can express any effect but they can't express restricted subsets of effects. You could presumably write a continuation-based equivalent of traverse (though I'd be interested to see what it looks like in practice), but you can't give it the level of type safety it should have, and you can't write sequence when your effects aren't representable.
> Kotlin does this blending at least as well if not better than Java.
Not convinced; nulls aren't integrated as tightly into the language in Java (e.g. no elvis operator) and you don't have to deal with platform types. You can write Option-oriented code without it being a second-class citizen, though admittedly the second-class citizen experience in Kotlin may not be so much worse than the first-class citizen experience in Java.
> I don't think it is a language's job to support all idioms out there, even if they can be useful in some circumstances.
Yes and no. A language doesn't have to support everything out there, but putting together any of the features it does support should work the right way; it's not at all clear that this is the case for kotlin . And certainly when you end up copy-pasting code because you're using the same logic but the language doesn't let you express how it's the same, that's a problem with your language.
That is not the case. Sometimes language designers and maintainers _deliberately_ avoid language constructs that allow for more generic code. More generic is not always better, definitely not when you have to read and understand the code, and find a bug in it, for example. The more layers of abstractions you have, the harder it is to construct a model of it in your mind.
(An example of this approach is Erlang, where parameterized modules were introduced as an unsupported, "beta" feature at some point, then a few major versions later they were removed. Why? Take this opinion, for example:
"I would gladly reconsider my somewhat harshly critical position on parameterized modules if shown a clear example of how their use improves the readability or expressiveness of code. Until then I would urge that they didn't become an official part of the Erlang language."
http://erlang.org/pipermail/erlang-questions/2010-February/0...)
This is not true. E.g., see my blog post, http://blog.paralleluniverse.co/2015/08/07/scoped-continuati..., with references to work by Oleg Kiselyov on typed continuations. Having said that, restricting effects is one of those solutions in search of a problem, at least at the moment. It is very questionable whether this has any substantial benefit, and the Java philosophy calls for adopting only features that have proven their (significant!) worth. On top of that, Scala can't restrict effects, either.
> You can write Option-oriented code without it being a second-class citizen
Which, BTW, Java discourages. Option is mainly recommended for use in functional composition in streams. For general null-safety, Java has pluggable nullability types (and many other useful pluggable types), similar to Kotlin's built-in nullability types. See https://checkerframework.org/. Unfortunately, it's not yet seeing much adoption, largely due to the relatively low-key marketing of Checker and the fact that it's been not too user-friendly until quite recently. However, this is the recommended solution, e.g. in the Java tutorial: https://docs.oracle.com/javase/tutorial/java/annotations/typ....
> putting together any of the features it does support should work the right way; it's not at all clear that this is the case for kotlin
Right, and certainly Kotlin has not yet proven itself (and neither has Scala), but in my opinion, this is quite clearly not the case for Scala. E.g., monads and the imperative control structures in Scala simply do not compose. You must commit to one or the other.
> And certainly when you end up copy-pasting code because you're using the same logic but the language doesn't let you express how it's the same, that's a problem with your language.
Not when that's required for non-idiomatic code. And, BTW, I believe that the pure functional paradigm in general suffers very strongly from this in a way that's very essential to the core of the paradigm (because typed monads introduce a dependence of code structure on a nominal type, i.e., the same computation can be expressed using different monads -- or no monads at all -- in a way that is non-composable or requires awful monad transformers).
So a theoretical type system extension that Kotlin doesn't actually have could solve this, and looks ok in simple examples. That's not terribly reassuring and not much help to anyone writing Kotlin today; anyone wanting to do the equivalent of something basic like traverse or, I don't know, cataM will still have to either copy/paste their code or give up type safety.
> On top of that, Scala can't restrict effects, either.
In theory no. In practice I use traverse all the time without worrying about whether the function I called was secretly throwing an exception or modifying a global variable, and it hasn't caused a bug yet; the community and culture can mostly work around the lack of hard restrictions at the language level.
> Which, BTW, Java discourages. Option is mainly recommended for use in functional composition in streams.
I know that's the official line, but it still works in a first-class way in practice (which to my mind is the sign of good language design; you can't expect language designers to anticipate all your needs, so it's important that things continue to work even if used in unexpected ways).
> I believe that the pure functional paradigm in general suffers very strongly from this in a way that's very essential to the core of the paradigm (because typed monads introduce a dependence of code structure on a nominal type, i.e., the same computation can be expressed using different monads -- or no monads at all -- in a way that is non-composable or requires aweful monad transformers).
There are now ways to avoid having to copy-paste in that situation e.g. MTL-style code ("final tagless") or free coproduct style.
There is nothing to solve unless a problem is identified, which, to date, none has (except within the context of pure FP).
> and looks ok in simple examples
Kiselyov treats general cases, and AFICT, his work on algebraic effect systems uses exactly the same approach.
> it hasn't caused a bug yet; the community and culture can mostly work around the lack of hard restrictions at the language level.
Well, you were talking about language support. The fact is that monadic style and the imperative control structures provided by Scala simply do not mix well, so why does Scala have both? Anyway, Kotlin doesn't want to buy into that programming paradigm. That's just your aesthetic choice.
> There are now ways to avoid having to copy-paste in that situation e.g. MTL-style code ("final tagless") or free coproduct style.
While I'm only a little familiar with free algebras from a theoretical POV, and all I know about "final tagless" is that it aims to achieve something similar to object algebras in OOP code, I believe those "free interpreter" styles are both expensive performance-wise (they require to represent code as a runtime data structure), and just expose an underlying fundamental problem in the language (there is also the deep problem -- which is mostly theoretical, but I'm also interested in theory, and find the FP theory to be both weak and complex compared to newer alternatives -- that monadic code can be computationally identical to non-monadic code, e.g. simple recursion vs. running in a state monad, yet the two have completely different denotations and inhabit incomparable types; if monadic code is the more general form, there are theories that do something similar, but in a way that's more uniform, simpler, and much more amenable to formal analysis; but I digress).
In general, one could say that any language with extensive DSL capabilities can fix any problem, but there are very good reasons to avoid powerful DSL support. This is one of the things I find most interesting in Kotlin. It offers some DSL support (inline functions, builders), which seems powerful, yet still doesn't take embedding too far. Is this a sweet spot? Does it do harm by adding features that don't solve hard problems yet introduce complexity? I don't know, but it will be interesting to see.
Which control structures? "for" extends very nicely to monadic style, as do if/else expressions. I guess do/while and throw/catch don't, but the language syntax is flexible enough that it doesn't really matter, because these builtin control structures are only barely more privileged than user-defined functions. (To answer your question, probably Java compatibility). I mean, don't get me wrong, I'd like to see them removed from the language, but it's not like anything would go wrong if you used while in a monadic context. throw I will grant you doesn't mix well with the rest of the language; the JVM means the possibility of exceptions is something we have to live with, but from a pure language design point of view it would be better to be without it, sure.
> That's just your aesthetic choice.
Aesthetics have nothing to do with it; it's my experience of what does and doesn't produce reliable, maintainable code.
> "free interpreter" styles are both expensive performance-wise
Free interpreter style can be expensive performance-wise; final tagless doesn't have that problem (indeed I see a lot of similarity between that style and various effect/ambient handler styles, for better and for worse).
> that monadic code can be computationally identical to non-monadic code, e.g. simple recursion vs. running in a state monad, yet the two have completely different denotations and inhabit incomparable types
What do state and recursion have to do with each other? Are you assuming some unmodelled language-level feature like mutable variables?
Why? Because you are drawn to the pure FP style. That's great, but that's an aesthetic choice, and certainly not one shared among all programmers.
> but it's not like anything would go wrong if you used while in a monadic context. throw I will grant you doesn't mix well with the rest of the language
Eh. You can't use while to loop over some effectful monad.
> Aesthetics have nothing to do with it; it's my experience of what does and doesn't produce reliable, maintainable code.
Yes, but seeing that that experience is far from universal, that makes it an aesthetic choice. It makes you more productive because you are more comfortable with that style.
> What do state and recursion have to do with each other?
You could translate any recursive function into one making use of a state monad. While the two express the same computation, I think their denotation is too different to construct an isomorphism between the two; this is an essential problem with the lambda calculus (in all its manifestations), that can express computations as either functions or monads. This is not a problem with simpler, more composable paradigms, that express computation in a way more amenable to mathematical manipulation (e.g., synchronous programming a-la Eve), and eschew the problematic representation of computation as functions.
No, because they're special cases at the language level that don't need to be there. It shouldn't be a language builtin if we can achieve the same thing with a plain old library function. That's not an aesthetic preference, that's language design.
> You could translate any recursive function into one making use of a state monad.
What and how would you translate? I can't see what you mean at all, particularly because it's very normal to write a recursive function that uses the state monad - I do this quite a lot.
That is an aesthetic preference, and this is why: sometimes you don't want a general abstraction that allows you to express certain constructs because that same general abstraction may be used to express constructs that you don't want your programmers to create. In that case, you want an ad hoc builtin construct instead of a more general abstraction.
The things that you want or don't want in order to maximize some value function are exactly what aesthetics is. There is no mathematical theorem, or no natural law, determining which value function I aim to optimize, and therefore no objective rule for deciding which language features are "correct", and no absolute measure for what constitutes good design. The only measure for good design is whether or not the product optimizes the value function that you've chosen on aesthetic grounds.
> What and how would you translate?
Think of writing a factorial function recursively and one using some looping monad. The two have isomorphic operational semantics, but completely different denotations. Monads basically let you express any kind of computation, including those that you can express with plain lambda terms. In addition -- and this is important -- some computations can _only_ be expressed with monads (assuming you don't have linear types). This means that lambda calculus contains two different, and incompatible, ways of expressing computation. This makes program analysis unnecessarily complicated (unless your program is just a sequential computation, in which case lambda calculus is a nice formalism because that's the usage it's been invented for). Formalisms invented for general (i.e., not necessarily sequential) computation, including sequential, concurrent and interactive, don't have this problem, and have just a single, simple and uniform way to express any kind of computation. This makes them amenable to mathematical analysis, something the pure-FP model has difficulty with (you'll note that when analyzing pure FP, various ad-hoc frameworks need to be invented, e.g., a message-passing model for concurrency etc.).
This quote explains the crucial aesthetics component of formal systems:
We do not attach any character of uniqueness or absolute truth to any particular system of logic. The entities of formal logic are abstractions, invented because of their use in describing and systematizing facts of experience or observation, and their properties, determined in rough outline by this intended use, depend for their exact character on the arbitrary choice of the inventor... [T]here exist, undoubtedly, more than one formal system whose use as a logic is feasible, and of these systems one may be more pleasing or more convenient than another, but it cannot be said that one is right and the other wrong.
The quote is from a 1932 paper called A Set of Postulates for the Foundation of Logic, in which Alonzo Church first introduced the formal system that would become his lambda calculus.
"Pleasing or convenient" is aesthetics, and the thing Church tried to make pleasing or convenient when he later turned his (inconsistent) logic into a universal computation calculus was how people in the 1920s and '30s thought of computation in the context of mathematics. In more modern, computer science terms, that thing was sequential, batch computation, namely something that takes a value and produces a value. I think that most programs written today are not sequential; if not concurrent or distributed, they are at least interactive, and while they may contain a great number of sequential computation bits, those bits are not the tricky, subtle or complex things about them, and therefore form the part of least concern (even if they form the majority of lines of code).
On the other hand, in the '70s and '80s, more modern formal systems were invented that incorporate cleanly, elegantly and simply all (or, most importantly, the trick) parts of computation into a mathematical framework. Part of the reason why so much emphasis is placed on lambda calculi by contemporary logicians (AKA programming language theorists) is precisely that this calculus is so well studied because it so old. But programmers aren't logicians, and so they do not require the oldest and best understood formal system, designed to optimize concerns that they may not share.
It's true that many paradigms can be embedded as DSLs in functional languages, but that's not helpful. That a language achieves its goals doesn't mean its host is equally appropriate.
If that were true there would be no point talking about language design at all. I don't believe that; the programming community does manage to eventually achieve rough consensus about which language designs are good and which are bad, and ultimately there is a fact of the matter when it comes to productivity, however difficult we find it to actually measure.
> Think of writing a factorial function recursively and one using some looping monad. The two have isomorphic operational semantics, but completely different denotations. Monads basically let you express any kind of computation, including those that you can express with plain lambda terms. In addition -- and this is important -- some computations can _only_ be expressed with monads (assuming you don't have linear types). This means that lambda calculus contains two different, and incompatible, ways of expressing computation.
I don't think I've ever seen this "looping monad"; certainly what you're describing doesn't sound at all like the usual state monad. Could you point towards an implementation of the kind of monad you're talking about?
That aside, the normal representation of recursion in the lambda calculus is already that you form a structure that represents the recursion to happen and then pass it to an operator that actually does the recursion (a Y combinator or similar), so I don't see this notion that any monad-like representation would be substantially different.
> Formalisms invented for general (i.e., not necessarily sequential) computation, including sequential, concurrent and interactive, don't have this problem, and have just a single, simple and uniform way to express any kind of computation. This makes them amenable to mathematical analysis, something the pure-FP model has difficulty with (you'll note that when analyzing pure FP, various ad-hoc frameworks need to be invented, e.g., a message-passing model for concurrency etc.)
Your own talks have covered the theme that doing formal reasoning about the full operational state space of any nontrivial program is impractical because that state space is so large. If we're to hope to be able to do practical analysis of programs we have to have a representation that collapses that space hugely. Identifying expressions with their reductions (i.e. their evaluation) does not come cheap, but it pays a huge dividend in terms of how much it simplifies the space that we need to reason about - and my experience is that this does not just benefit the formal model, it helps the human programmer's reasoning in the same way. Even back when I worked in Java, those things that don't fit neatly into the FP framework - concurrency, exceptions - were the biggest sources of bugs. And now that I've used FP-compatible abstractions for these things - however ad-hoc those abstractions were at first - I've found that bug incidence has gone way down.
Why not? People talk about music, art and, well, design, all the time.
> the programming community does manage to eventually achieve rough consensus about which language designs are good and which are bad
That still doesn't mean there's no large aesthetic component.
> ultimately there is a fact of the matter when it comes to productivity, however difficult we find it to actually measure.
I agree, except that very large differences in just about anything are pretty easy to measure. I think it is almost an established fact at this point that no great differences in productivity exist between modern languages.
> Identifying expressions with their reductions (i.e. their evaluation) does not come cheap, but it pays a huge dividend in terms of how much it simplifies the space that we need to reason about
All formalisms have expressions and reductions. Their denotation is just different. For FP it's so-called "partial functions" (which resemble computable functions); for classical imperative languages it's Hoare triplets (or some other mathematical object). It's just that the denotation offered by lambda calculus is inconvenient when it comes to interactive/concurrent/distributed programs, precisely because the lambda calculus itself cannot directly represent any of them in its reductions, rather delegating them to externally defined mechanisms (IO types, message passing etc.).
> and my experience is that this does not just benefit the formal model, it helps the human programmer's reasoning in the same way.
I agree, but lambda calculus is quite bad at this compared to alternatives. Where it's good -- sequential programs -- not much help is needed. You can have immutability and the thing FP advocates mistakenly call "referential transparency" (when they really mean a simple denotation) in formalisms that are much better suited to modern programming than lambda calculus.
And I really wouldn't mind saying, well, LC doesn't help with the hard stuff, but it does help with the easy stuff, so we should all adopt if there had been any evidence that pure FP yields a large benefit, but there isn't.
> I've found that bug incidence has gone way down.
I believe you, but think that your experience isn't at all universal. Others may find employing better discipline (including precise and even formal analysis of programs/algorithms) in the languages they like to yield more of an impact, while adopting a very different programming style to be a distraction that just hurts overall productivity.
> I don't think I've ever seen this "looping monad"; certainly what you're describing doesn't sound at all like the usual state monad. Could you point towards an implementation of the kind of monad you're talking about?
Ugh, you made me look up Haskell syntax :)
So, you can have:
fac1 :: Int -> Int
fac1 0 = 1
fac1 n = n * fac1 (n-1)
fac2 :: Int -> Int
fac2 n = go n 1 1
where
go n i x = if i <= n then (go n (i+1) (i*x)) else x
fac3 :: Int -> Cont r Int
fac3 0 = return 1
fac3 n = do
a <- fac3 (n-1)
cont $ \k -> k (a * n)
fac4 :: (Int, Int, Int) -> State (Int,Int,Int) ()
fac4 (n, i, accum) = put (if i < n then (n, i+1, i * accum) else (n, i, accum))
All really express the same computation -- the operational semantics are isomorphic (I could have gotten some of the details a bit wrong, but in general) -- but the functional denotation does not express that. Even in classical imperative languages the denotation (say, using Hoare triplets) is isomorphic. The reason is that the functional denotation, is, well, a function and not a computation. This is a great simplification in sequential programs, but becomes very problematic when interaction/concurrency is involved.
> That aside, the normal representation of recursion in the lambda calculus is already that you form a structure that represents the recursion to happen and then pass it to an operator that actually does the recursion (a Y combinator or similar)
1. FP programming languages are not really Church’s lambda calculus, and the Y combinator in them is implicit. You cannot define a Y combinator in a typed LC. (scratch that -- this is wrong; see comment below)
2. The problem exists even in “proper” LC, as passing the “step function” to a Y combinator or in a monad still yields isomorphic operational semantics that are incomparable types.
Well actually ... http://r6.ca/blog/20060919T084800Z.html
But that's besides the point. Haskell already has a perfectly good recursion combinator called `fix`.
BTW, I've been told that the limitation of LC I discussed is handled nicely in computational type theories, like PRL, which, I'm told, is similar in many ways to the formalisms I do like (and so should be able to relate the different expressions of the factorial computation), but I know nothing about PRL so I can't really discuss it. I can't judge on how simple PRL is, seeing that the documentation is quite horrific, but my point is that there are very simple formalisms, both for formal proofs, like TLA+ (see my talk https://www.youtube.com/watch?v=15uy9Ga-14I), and for programming, like Eve (IMO, the most advanced, publicly available programming language, in terms of PL theory), that make this very, very easy; and they're far easier to learn and much more uniform than Haskell.
Well if they have different denotations they're necessarily not identified, no?
> (fac4 doesn't really express the full computation, but I wanted to make clear what's going on; fac3 is a better, though less clear example)
Well, fac3 is still old-fashioned recursion on its face. I guess you could say it's constructing the recursion to happen later, but that seems like an expected mirror image to how the Y combinator does it - you can compose the recursion and the computation either way around (and I'm not sure from a YC-style perspective we recognise any distinction; as far as I can see Cont r a is equivalent to a). I'm not really sure what you're getting at with fac4 (did you mean to read the values from the state rather than accepting them as function parameters?) - it would only represent recursion if you applied a function that does recursion on it, on it's own it's no more recursive than an ordinary function. Again this is exactly what happens with a plain old function and the Y combinator, so the State monad isn't making any difference. I mean, you can make a monad have an unusual denotation by passing it to an unusual "interpreter" function, sure, but the same is true for any function or value.
But their operational semantics are isomorphic. That means there's something problematic in the denotation.
> I mean, you can make a monad have an unusual denotation by passing it to an unusual "interpreter" function, sure, but the same is true for any function or value.
Not really, and that's the point. With functional denotation you have bubble-sort and mergesort with the same denotation, yet two implementations of mergesort with different, incomparable, ones (well, you can convert some monadic expressions back into ordinary functions by interpreting them, but there is no way to transform an ordinary function into a monadic form). This is not a universal property of all systems for expressing computation. In some, if two computations do "essentially" the same thing, there will be a transformation between them. This is an actual theorem proved by Martín Abadi and Leslie Lamport in the '90s [1] (in fact, they proved something stronger: even if an algorithm is an implementation, a refinement, of another, there will be a mapping between them, but in some cases one or two variables would need to be added to the more concrete of the two).
Now, this is exactly the aesthetic (or pragmatic, but in any case -- not universal) part of design. Obviously, computations are not functions, but formalisms may obscure some details in order to gain convenience. I claim that the design that represents computations as functions is a very convenient one for sequential programs, and a rather inadequate one for interactive/concurrent programs, which make up most of the programs we write today.
[1]: https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/r...
Are we still talking about models other than functional here? Because I'm surprised to hear you say that if so.
> Not really, and that's the point. With functional denotation you have bubble-sort and mergesort with the same denotation, yet two implementations of mergesort with different, incomparable, ones (well, you can convert some monadic expressions back into ordinary functions by interpreting them, but there is no way to transform an ordinary function into a monadic form). This is not a universal property of all systems for expressing computation. In some, if two computations do "essentially" the same thing, there will be a transformation between them.
You can use 4 to denote 5 by passing it to a function that adds 1 before using it. You can use f(x) = -x to denote multiplication by 2 if you only use it in a mod 3 context. There will be a transformation, sure, but there's a transformation in the examples you've given as well. I mean fundamentally, whatever your example was supposed to show, you didn't actually use the monadicity of the state monad at all, so your conclusions apply just as much to non-monad values.
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 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);
}
}
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.
I'm not reasoning operationally. I'm reasoning denotationally, in the imperative denotation (of Hoare logic). Denotational does not equal functional.
> if we're talking about things like stack depth it's definitely operational rather than denotational, that's the point of that terminological distinction
Not true. In imperative languages, the stack is a part of the state, and the state is a part of the denotation.
> The difference is that we can also reason about them denotationally
You mean using functional denotation, or equationally. The functional denotational semantics contribute, IMO, to the least tricky parts of a program, yet come for a cost (if enforced, as in Haskell; you can have pure functions in ML and Java, too). There is nothing intrinsically superior about it. It's a denotational semantics that's convenient for specific uses, and not so convenient for others. In addition, some people are aesthetically drawn to it (I guess they like thinking of computation as functions), while others, like me, are not particularly drawn to it.
> all we'd need is to define the equivalence between readFile/writeFile and get/put.
Yes, I said that can be done with, say, a free monad, but it still cannot be done to relate fac1 to fac5, even though they are the exact same algorithm.
> I mean, IO specifically is, by design, the place we put things that we don't care to ascribe formal denotational semantics to
Well, the denotational semantics for imperative languages is very easily applied to IO, and is beautifully and elegantly done in a language like Eve.
> plenty of monads form algebras that you can compare, reduce, and put in a canonical form like any other kind of expression
Sure, except that most modern programs are interactive/concurrent/distributed, and so their trickiest bits require IO and nondeterminism in general. That's why I said that languages with a mathematical framework that elegantly handles IO and nondeterminism are better suited to modern programs.
> 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.
Ah, but other formalisms allow you to reason in a simple, elegant denotation even about things that require operational reasoning in Haskell. This is exactly why Haskell degrades to something that's little better than classical imperative languages precisely where programs get interesting and tricky. I am not comparing Haskell to itself; I'm comparing it to different, newer formalisms.
> With the functional approach you effectively just write your proof and get the algorithm for free.
1. That's not due to the functional approach. You could, in principle, generate an algorithm from any constructive proof, regardless of formalism.
2. To the best of my knowledge, no one has ever done that for anything that can be considered a real, nontrivial system. Program extraction from proofs is still very much a research topic, and very far from practical use.
> Surely this can't be true in general - doesn't the halting problem make it impossible?
Which is why I said if the proposition is provable. This is called "relative completeness", i.e., if a proposition is provable in some formal system X, then it is also provable in my formal system Y.
> You do have to delineate your effectful parts from your pure parts
Again, you are thinking inside one particular formalism. Effects are "impure" (i.e. break the denotation) only within the functional formalism. They are perfectly pure in TLA+ or Eve precisely because their denotation is not functional, yet simple and elegant.
2. I believe I understand the semantics of Haskell (or, at least that of strict FP languages) well enough, certainly for the purpose of this discussion.
3. The semantics of Eve is essentially that of Dedalus [1], which, in turn, is similar to the semantics of all synchronous languages (which have been very successfully used in industry for formally verified safety-critical real-time software and hardware), and are heavily inspired by linear temporal logic (in fact, the logic and the PLs were developed practically hand in hand). Dedalus is especially inspired by Lamport's TLA, a particularly simple and particularly powerful linear temporal logic. I've written about TLA (which forms the computational logic part of TLA+) here https://pron.github.io/posts/tlaplus_part3 (the two previous installments are not strictly necessary, but if you're interested in program analysis and find that post interesting, you may want to read part 4 as well).
[1]: Dedalus: Datalog in Time and Space https://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-...
let x = 1 + 1
in x * x
let x = 1 + 1
y = 1 + 1
in x * y
let x = 1 + 1
in x * x
(\x -> x * x) (1 + 1)
Similarly,
let x = 1 + 1
y = 1 + 1
in x * y
(\x -> \y -> x * y) (1 + 1) (1 + 1)
As 4 = 4, the denotation of these two expressions is equal.
2. Functional semantics are convenient for sequential programs.
[1]: Perhaps there's been a misunderstanding. Functional semantics means that expressions denote things similar to functions. Usually, operational semantics are state-machine semantics, certainly not functional semantics. If you'd asked for the state machine semantics, I would have described those.
I'm all in favour of you promoting technologies and approches that you think are beneficial. What I would ask you to stop doing (again) is critiquing Haskell without really understanding it.
Heh, well, in a way I guess you could say I made that "term" up, but it's not an atomic term. The formal semantics of a syntactic term is some object (in the semantic domain of the formalism) mapped to that term. If that object is a function (or something close to it), what you have is functional semantics. Similarly, you have relational semantics, behavior semantics, and any other kind that you may find useful; even evidence semantics, which assigns evidence objects to terms.
I've heard some academics refer to it as "value semantics", which, I guess, hints to the fact that the denotation of a lambda application is the value that the lambda term reduces to, but I find that terminology to be unclear. I've heard Haskell programmers (in the pseudo-mathematical atmosphere that seems to be common in that community) refer to it as "referential transparency", which is downright misleading because referential transparency does actually have sort-of a well-defined meaning, and it's not quite that. I've heard Conal Elliot refer to it simply as "denotational" (as in "functional programming is denotational programming"), which is also misleading because not all denotations are functions. So, I find "functional semantics" to be both precise and clear.
> You also seem to believe that it's the only semantics that functional programmers care about and this is why I say you have a big misunderstanding about Haskell.
Where did you get that? What I may have said or alluded to, in so many words, is that denotational semantics are important for writing and analyzing programs, and I find that functional semantics don't make a great fit for non-sequential programs. After all, it only pays to think "denotationally" if the denotation is simple and a natural fit for the domain.
https://news.ycombinator.com/item?id=11907547
I'm afraid I still can't understand your position.
Then take my "good" and "bad" as shorthand for "more" and "less" appealing/convenient.
> 3. The semantics of Eve is essentially that of Dedalus
If expanded on that as much as you have expanded on the semantics of Haskell in this thread then we might actually learn something very interesting!
So why are you upset when I say that I don't find pure FP to be appealing or convenient for concurrent/interactive/distributed programs? I think that the very notion of representing computation as functions in such circumstances is ill-advised, and results in a very inconvenient, very unnatural (at least for me), and very hard-to-reason-about formalism compare to alternatives. Nevertheless, my opinion is subjective, and I can accept that some may not share it.
> If expanded on that as much as you have expanded on the semantics of Haskell in this thread then we might actually learn something very interesting!
I did. Read my blog post (which is the general theory), and then read the Dedalus paper. Some time ago you asked me to write something about TLA(+). I have, my posts (especially parts 3 and 4) are aimed precisely to get people away from what Lamport calls the "Whorfian syndrome", which is confusing the analysis of a particular formalism with that of computation or programs in general. In addition, I strongly recommend reading the overview paper, Binary Relations for Abstraction and Refinement [1] by David A Schmidt (who also wrote the book Denotational Semantics: A Methodology for Language Development). While the last section of that paper discusses temporal logic, the paper really applies to all programs in all programming languages.
[1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16....
I'm not sure "upset" is the right word but what I object to is your repeated mischaracterisations and misunderstandings of Haskell, especially of how it is used by industry programmers.
And I object to false claims that pure FP is somehow "better designed" than other approaches (which is how this entire discussion started). Design is a matter of aesthetics (completely subjective) and pragmatics (also subjective, but can be measured empirically) -- not theory -- and aesthetics and pragmatics are the sources of value -- again, not theory.
By that definition then you could call any operational semantics "denotational" and the distinction between the two would be pointless.
> The functional denotational semantics contribute, IMO, to the least tricky parts of a program
Largely agreed (though it depends on your domain; it's very possible to have genuinely tricky business logic in the pure parts of your code, or indeed to have some genuinely tricky code that you only ever runs once to output a computed result) but in a well-factored functional-style program you can move the vast majority of program code/logic into those "least tricky parts", and have a machine-enforced separation between the two. So you can restrict the more expensive forms of analysis to a small subset of your code, and get a much better cost/benefit.
> it still cannot be done to relate fac1 to fac5, even though they are the exact same algorithm.
If you deliberately choose to use operations that are deliberately defined to not have a formal denotation then your code won't have a formal denotation. Complaining about that is like complaining that if you write a cast in your code then you can violate type safety. IO is explicitly an "escape hatch" to be used as a last resort.
If you use a monad that has semantics, or you choose to model (some subset of) IO, you can relate them. E.g. if your model of IO follows our common-sense informal semantics (where we e.g. pretend concurrent access to the same file wouldn't happen - this is a choice you have to make when modelling, because in some contexts the ability of another process to interfere with fac.txt would be an important difference between fac1 and fac5 and we wouldn't actually want them to be equivalent), (writeFile x y *> readFile x >>= (evaluate . force) >>= (writeFile x) . f) = writeFile x (f y) would be an equation in that model. Using that and using read . show = id (and show 1 = "1"), we can reduce fac5 equationally to writeFile "fac.txt" . show . fac1 (or to a normal form of fac1 if we want a full reduction, but we don't need to). The whole exercise is little different from reducing an arithmetic expression to 4 as you did in another reply.
> Well, the denotational semantics for imperative languages is very easily applied to IO, and is beautifully and elegantly done in a language like Eve.
So terminology aside, what's the problem? Use operational semantics to reason about IO, which you can do just as well in a Haskell-like language as in a non-Haskell-like language (I find the synchronous logic approach horribly confusing, but if you like it I see no reason you couldn't apply it to Haskell IO. Making the modelling of IO easier is not really a priority for me, because I spend so little of my time reasoning about IO, but it's not like I'm opposed). Use denotational semantics to reason about non-IO - which can be done much more cheaply because the space of possibilities to consider is so much smaller.
> most modern programs are interactive/concurrent/distributed, and so their trickiest bits require IO and nondeterminism in general.
Not my experience - the only cases I've seen where the tricky logic couldn't be unpicked from the IO and nondeterminism, the entire code was incomprehensible (not just to me but to everyone who tried). And conversely, doing that unpicking has always made the logic easier for a human reader to follow.
While there is some debate over what exactly can be called "denotational semantics", it is widely accepted that denotational semantics must display certain characteristics. Hoare logic does display those characteristics and is, AFAIK, considered denotational.
> in a well-factored functional-style program you can move the vast majority of program code/logic into those "least tricky parts", and have a machine-enforced separation between the two. So you can restrict the more expensive forms of analysis to a small subset of your code, and get a much better cost/benefit.
1. I know, but I don't find that approach appealing in the least.
2. Other approaches have the language and its theory cleanly deal with effects -- just as with computation -- and so don't require such a separation and actually help with the tricky effectful/concurrent bits because they were designed for that purpose. FP was designed for a different purpose.
> If you deliberately choose to use operations that are deliberately defined to not have a formal denotation then your code won't have a formal denotation.
But that is a feature of the functional formalism, not of all formalisms. All of these programs have the same hoare-logic denotation (in classical imperative languages), and the same behavioral denotation (say in TLA). A denotation is not a feature of an algorithm; it's a feature of the particular formalism used to express the algorithm (although some formalisms may possibly have more than one reasonable denotational semantics).
> IO is explicitly an "escape hatch" to be used as a last resort.
Yes, in the functional formalism. Not in every language. I wanted to show a particular property of functional languages that I find unappealing.
> E.g. if your model of IO follows our common-sense informal semantics (where we e.g. pretend concurrent access to the same file wouldn't happen - this is a choice you have to make when modelling, because in some contexts the ability of another process to interfere with fac.txt would be an important difference between fac1 and fac5 and we wouldn't actually want them to be equivalent)
Ah, but that's why I've specifically chosen this example. Other formalisms have no difficulty assigning simple and natural semantics in either case (and if we disallow concurrent writes but allow concurrent reads, all versions of the algorithm would have isomorphic denotations). The reason you run into any sort of difficulty here is because your chosen denotation is that of a function, and functions are not a good representation of interactive or concurrent processes. Other denotations used in other formalisms have no problem with that.
> So terminology aside, what's the problem?
There's no problem. I just want to point out why pure FP is not so well-designed for all circumstances, as, for example, its denotation is a bad fit in many circumstances. If you personally do find the aesthetics of FP appealing, and have no problem separating effects from computation, enjoying the benefits of pure FP for the pure computational part -- good for you! I was just trying to show why it is not a universally "better" formalism, and why there may be very good pragmatic and aesthetic reasons not to choose it.
> Yes, in the functional formalism. Not in every language. I wanted to show a particular property of functional languages that I find unappealing.
I would expect any practical formalism to have escape hatches, just as I expect any practical type system to allow casting - and I find it absurd to see either as a downside for the language.
> Other formalisms have no difficulty assigning simple and natural semantics in either case (and if we disallow concurrent writes but allow concurrent reads, all versions of the algorithm would have isomorphic denotations).
If another program overwrites fac.txt then the semantics you gave in your ghost variables and assertions example would be simple, natural, and wrong (and wrong in a way that's a common source of security vulnerabilities). If your formalism makes fac1 and fac5 equivalent, as you've said it does, then there's no way to then make them un-equivalent.
Really they're equivalent for the purposes of some kinds of analysis under certain constraints and they're not equivalent for other purposes. The functional formalism handles this essentially as well as possible: it allows you to do any analysis that doesn't depend on how you're modelling the filesystem interactions "ahead of time", but forces you to make an explicit choice of model when your analysis is fundamentally dependent on that model.
Sure, but not every formalism needs the escape hatch to do IO. I don't see it as a downside. FP is beautifully adapted to sequential programs, perhaps more so than other formalisms. It's not the best fit for interactive/concurrent. Also, an unappealing property to one may not be a problem at all to another. You may not be bothered by this, but I am, and that's OK. I like Java, and I assume you like it less, and that's OK, too.
> If another program overwrites fac.txt then the semantics you gave in your ghost variables and assertions example would be simple, natural, and wrong
If another program overwrites fac.txt, I cannot assume `readFile` to return anything other than a string, if that. I.e., I have nondeterminism about the next state. That's fine, because the next-state relation need not be a function, but you're right that in that case the semantics would be different from the other programs.
> Really they're equivalent for the purposes of some kinds of analysis under certain constraints and they're not equivalent for other purposes.
No. A specific denotational semantics is either equivalent for those programs or not. I can either guarantee that the next state is deterministic, or I can't. However, you are right that using this kind of semantics can create a situation where one program is a refinement of another. For example, one program can say that the current and next values of the variable x are even integers. Another can say that they're always 2 or 4. This makes program 2 an instance of program 1. Just as in FP you have the notion of a cartesian-closed category (sort of) on types, where every program is an object in that category, in this other kind of formalism you have a lattice that relates all programs. It's just a different theory.
> The functional formalism handles this essentially as well as possible
Not really, because IO is essentially nondeterministic, and functions don't model nondeterminism well (but relations do!). That's exactly why you need to stuff IO, or anything else that doesn't quite fit the concept of a function, in a monad (which can express all forms of nondeterminism). It's a neat trick, but, like you say, it's sort of an escape hatch. That doesn't mean that all formalisms need to do this for IO, concurrency or other forms of nondeterminism. Functions aren't a great fit for nondeterminism, but other mathematical objects really have no problem with it.
It sounds like that's only achieved by weakening the formalism so far that its guarantees are no stronger than what you have when using the "escape hatch" in the functional world. If the assertions in your Java fac5 are not necessarily true then it seems like analysis in your formalism told us nothing at all about fac5 - and if the assertions don't tell us anything about fac5 then a reader couldn't trust that they tell us anything about fac1 either.
> No. A specific denotational semantics is either equivalent for those programs or not.
I don't think that contradicts what I said at all. Certainly when analysing these programs we would want to be able to talk about whether they are equivalent, and we would want to consider them as equivalent in certain senses and as inequivalent in other senses. A formalism that can't accommodate that would be less useful (other things being equal) than one that can.
This is where the aesthetics and pragmatics come into play. In terms of program analysis, the language doesn't really matter (there are actual theorems that prove that no language structure can be exploited to make proving things easier), so in a sense you are right (but this also means that proving general propositions about Haskell is no easier than proving them about assembly code -- which is, unfortunately, true). However, there are questions of convenience. Just as Haskell is easier to analyze than C for sequential code, those other formalisms are easier to analyze and work with than Haskell for interactive and/or concurrent programs.
> I don't think that contradicts what I said at all. Certainly when analysing these programs we would want to be able to talk about whether they are equivalent, and we would want to consider them as equivalent in certain senses and as inequivalent in other senses. A formalism that can't accommodate that would be less useful (other things being equal) than one that can.
If you read part 4 of my post series on TLA+[1], you'll see that a formalism like TLA allows you to rigorously, mathematically and formally define the "sense" of equivalence that you're interested in. This is not quite possible in functional formalisms. The reason is as follows: computations simply cannot be fully described by functions (unless you describe them essentially as state machines using a monad). Bubble-sort and mergesort compute the same function, but they use different computation. A formalism that allows you to describe arbitrary computations precisely can then allow you to pick your "level of detail". TLA places all computations in a nice Boolean algebra, where all algorithms are neatly organized in a Boolean lattice. You can then define (in two lines) a operator, `ExtensionallyEquivalent(_, _)`, that captures the functional equivalence, but also define other forms of equivalence, down to the most detailed ones. It is completely flexible in the forms of equivalence it can describe.
Nevertheless, you won't hear me say that TLA is "better" than functional formalisms, because that extreme flexibility comes at a cost. Simple sequential compositions are more cumbersome in TLA, and since most of the time, when writing sequential programs like compilers, we're not interested in reasoning about interaction or concurrency, functional programming is more convenient. It was mostly designed to write compilers and similarly sequential programs, and I think it is hard to beat in that domain. Because of that it also excels at symbol manipulation (e.g., it is so convenient to define expression types using algebraic data types) -- that is what it was invented for.
[1]: https://pron.github.io/posts/tlaplus_part4 it probably requires reading at least part 3 first.
Yes and no. Fundamentally no formalism will ever allow you to use more detail than the formalism has; even if the formalism lets you refine existing descriptions, adding those refinements will break symmetries that previously existed, so there's no way to get away from having to redo your analysis. TLA sets that baseline level of detail at a lower level (or equivalently is more precise), but I think you'd still encounter the same kind of problems if you wanted to model the machine state at a lower level of detail (e.g. as an extreme example, if you wanted to analyse vulnerability to rowhammer-like issues). We can choose a more or less detailed model, trading off how much detail we can talk about versus how complex our description space is and how many or few symmetries we have, but there will always be finer details not captured in our model.
> If you read part 4 of my post series on TLA+[1], you'll see that a formalism like TLA allows you to rigorously, mathematically and formally define the "sense" of equivalence that you're interested in. This is not quite possible in functional formalisms. The reason is as follows: computations simply cannot be fully described by functions (unless you describe them essentially as state machines using a monad). Bubble-sort and mergesort compute the same function, but they use different computation. A formalism that allows you to describe arbitrary computations precisely can then allow you to pick your "level of detail". TLA places all computations in a nice Boolean algebra, where all algorithms are neatly organized in a Boolean lattice. You can then define (in two lines) a operator, `ExtensionallyEquivalent(_, _)`, that captures the functional equivalence, but also define other forms of equivalence, down to the most detailed ones. It is completely flexible in the forms of equivalence it can describe.
So what I don't see is why you would ever not want the higher-level tools, even if working in a lower-level formalism. A lot of the time we are analysing only in terms of denotation (sorted list) rather than operation (bubble sort or merge sort); I'd certainly expect to be able to recover that kind of equivalence as you say, and it's good that the formalism makes it easy. But in that case then surely, even if I were working in something like TLA, I'd still want to be able to talk about whether two procedures implemented the same function if the filesystem operated in a certain way. I'd still want to cheaply compare functions for equivalence "up to" fiddlier aspects that I could separately analyse in more detail. I'd still want monads.
No, because TLA is not a programming language. It's a way to describe computation using math. What you're saying is analogous to saying that there is no way math would allow us to describe physics at arbitrary levels of detail.
> adding those refinements will break symmetries that previously existed
The very definition of refinement is that this can't happen. Formally, if A refines B, then A => B. And so, every feature C of B, i.e., B => C, is also a feature of A, because A => C, due to the transitivity of implication.
> but I think you'd still encounter the same kind of problems if you wanted to model the machine state at a lower level of detail
No, because of universal computation. Once your logic can talk about a single computational step, and thanks to TLA's logical time that then allows you to break that step down further, you really can talk about arbitrary detail. Of course, while true, this is a theoretical possibility. No one is going to actually specify the program at the level of the electrons in the CPU. If someone does, they will encounter a difficulty that isn't about a theoretical limit of formalisms, but one specific to TLA, which is that the logic does not currently allow making probabilistic statements about programs.
> but there will always be finer details not captured in our model.
Sure, in our model -- yes. But not necessarily in our formalism.
> So what I don't see is why you would ever not want the higher-level tools, even if working in a lower-level formalism.
TLA is not a lower-level formalism, although it may sometimes be less convenient for some sequential computations. But because its denotation fully captures the notion of computation, it allows arbitrary levels of detail. Functions are a fundamentally lossy way of speaking about computations; sequences are not. Indeed, sometimes functions are very convenient, but they become not so convenient when concurrency/interaction is involved.
> A lot of the time we are analysing only in terms of denotation (sorted list) rather than operation (bubble sort or merge sort)
Again, you mean in terms of a functional denotation, i.e. the denotation of a function. The denotation of TLA is behavior (a sequence of steps), and while you can easily define an "extensional equivalence" operator on behaviors, one that looks only on the first step (input) and last step (output), the essential denotation in TLA does differentiate between bubble- and merge-sort.
> I'd still want to be able to talk about whether two procedures implemented the same function if the filesystem operated in a certain way.
That's very easy:
ExtensionallyEquivalent(A, B) ≜
∀ x : ∃ y : (A ∧ (input = x) ⇒ ◇□(output = y)) ≣ (B ∧ (input = x) ⇒ ◇□(output = y))
> I'd still want monads.
You wouldn't, because, as you've seen, while you can define a weaker equivalence on sequences, there is no need for a special construct to define different kinds of computation. The only reason monads are used in the first place is that functions cannot describe arbitrary non-sequential computation. Monads aren't a "real" feature of computation; they're a tool of a formalism used to describe computation.
It is very important to me to point out that TLA+ is not a programming language. Synchronous languages like Eve, however, do share many of its properties.
Then these refinements evidently can't model distinctions that are sometimes important.
> The denotation of TLA is behavior (a sequence of steps)
Again, that's operation rather than denotation. Terminology isn't that important, but why not use the standard terms?
> The only reason monads are used in the first place is that functions cannot describe arbitrary non-sequential computation.
They're useful because they allow us to decompose a program into fragments that can be reasoned about separately. That's a useful capability when you want to reason about a computation that is inconvenient to model as a function, sure, but that's by no means the only reason. States really and truly are functions, Writers really and truly are plain values, there is no difficulty at all in describing those things in functional terms. But it's still convenient to use the monad constructs.
> Monads aren't a "real" feature of computation; they're a tool of a formalism used to describe computation.
They are a real feature: computation genuinely conforms to the monad laws, and so results about monads will be true about computation. We don't have to make use of these facts if we don't want to, but they remain true.
I don't understand. A refinement is a description at a lower level of detail. It may be a little hard to imagine if you're not used to formalisms that allow for nondeterminism, but it works like this: the high level description, say, does not describe the precise state of the stack. In the TLA theory, this means that the state of the stack can be anything, and the formula describes an infinite set of behaviors for arbitrary states of the stack. A refinement that does describe the state of the stack would denote a subset of those behaviors.
> Again, that's operation rather than denotation. Terminology isn't that important, but why not use the standard terms?
Because that's just not true. The denotational semantics of the first-order logic statement over the natural numbers `x > 4 ∧ x < 8` is the set {5,6,7}. The operational semantics of, say `⊦ x > 2 ⇒ x > 1` in Peano arithmetic is the proof of that theorem. In lambda calculus, the denotational semantics of `λ x . x + 1` is the function `f(x) = x + 1`. Its operational semantics is the sequence of reductions. Your denotation and operation are dependent on the formalism, not on what it describes. The denotation of a TLA formula is, like all first-order logics, a set (actually, a class) of models that satisfy it, which, in the case of TLA is a set of infinite sequences with some equality relation over them. The operational semantics of TLA are more similar to that of formal logic, and are basically proofs. Operation and denotation are formalism-dependent.
> They're useful because they allow us to decompose a program into fragments that can be reasoned about separately.
... with functions! If your primitive building block isn't functions but sequences, then your compositions are different, your reasoning is different, your denotation is different, and you don't need monads.
> States really and truly are functions, Writers really and truly are plain values, there is no difficulty at all in describing those things in functional terms.
Computation is an abstraction of some physical process. I don't know what it means for a physical process to be "really and truly a function". Mathematics are a description of that process. You can describe the same process using different mathematical means. So maybe state is really and truly a function, but it's also really and truly a sequence. It then becomes an aesthetic and pragmatic question as to which you would choose.
> They are a real feature: computation genuinely conforms to the monad laws, and so results about monads will be true about computation. We don't have to make use of these facts if we don't want to, but they remain true.
See my paragraph above. These monad laws are true once you describe computation using functions and monads. I don't know what it means for them to be "really" true. It's really a philosophical question. In any event, once you describe computation as sequences rather than functions, monads are unnecessary. I guess the most accurate thing to say is that if one describes computation with functions, then the monad laws necessarily hold etc.
This, BTW, is one of the things Lamport always like pointing out when explaining what math is, and he always warns about confusing language, or a description, with reality.
The main thing I'm trying to do in this discussion is not to claim that another approach is universally "better" than FP, but just to dispel the false notion that the functional approach is the "right", "mathematical" way of describing computation. It is one mathematical approach, with its pros and cons, and there are others (classical imperative, process calculi, TLA etc.), with their respective pros and cons. None can be said to be universally better than the others. They can be more or less convenient depending on what it is that you want to do and your personal aesthetic preferences.
Fair enough, and I can see how that would allow you to defer making the choice as late as possible, in the same way as not giving a monad semantics. Still, I think the fundamental issue has to remain: if you perform an analysis that doesn't care about the state of the stack, and then want to reanalyse while considering the state of the stack, things that were equivalent in your first analysis are not equivalent in your second analysis so you can't reuse results and symmetries from the previous analysis in the new analysis. That has to be true under any formalism, any model, any what-have-you.
> The denotational semantics of the first-order logic statement over the natural numbers `x > 4 ∧ x < 8` is the set {5,6,7}. The operational semantics of, say `⊦ x > 2 ⇒ x > 1` in Peano arithmetic is the proof of that theorem. In lambda calculus, the denotational semantics of `λ x . x + 1` is the function `f(x) = x + 1`. Its operational semantics is the sequence of reductions. Your denotation and operation are dependent on the formalism, not on what it describes. The denotation of a TLA formula is, like all first-order logics, a set (actually, a class) of models that satisfy it, which, in the case of TLA is a set of infinite sequences with some equality relation over them. The operational semantics of TLA are more similar to that of formal logic, and are basically proofs. Operation and denotation are formalism-dependent.
You're confusing the program with the description of the program, because of course in the lambda calculus they're one and the same. The operational semantics is the sequence of operations performed to execute the program. In the lambda calculus that happens to be the sequence of reductions, because a lambda-calculus description of a program is the program and reduction is how you execute it, but that's specific to that programming language.
> ... with functions! If your primitive building block isn't functions but sequences, then your compositions are different, your reasoning is different, your denotation is different, and you don't need monads.
But I thought you said I could reason about value equivalence in TLA, using your extensional equality? Certainly I want to reason that way (most of the time), because it's a lot more convenient and simpler than reasoning about sequences of operations.
> Computation is an abstraction of some physical process. I don't know what it means for a physical process to be "really and truly a function".
I meant State-the-monad rather than state-the-general-concept. (Though I would say that a physical process can be a function in exactly the same sense and to exactly the same extent that it can be a computation).
> So maybe state is really and truly a function, but it's also really and truly a sequence.
Maybe it is. My point is that "The only reason monads are used in the first place is that functions cannot describe arbitrary non-sequential computation." is wrong; monads are useful for working with computations that are perfectly adequately described by functions.
> The main thing I'm trying to do in this discussion is not to claim that another approach is universally "better" than FP, but just to dispel the false notion that the functional approach is the "right", "mathematical" way of describing computation. It is one mathematical approach, with its pros and cons, and there are others (classical imperative, process calculi, TLA etc.), with their respective pros and cons. None can be said to be universally better than the others. They can be more or less convenient depending on what it is that you want to do and your personal aesthetic preferences.
So I think there are two different kinds of thing to talk about here: a) specific choice of formalism and model - whether that be lamba calculus, TLA or something else b) the broader notion of whether we analyse program fragments as sequences of operations on a pervasive state that changes over a pervasive time, or as expressions in a term reduction system. I'm agnostic about specific formalism, but I think being able to analyse programs as expressions where we consider expressions with the same reduction as equivalent is a vital capability that I would want any formalism I used to have. And I think there's a close-to-objective sense in which that technique/approach is valuable: the space of possibilities we have to consider when working with terms in a language can be so much smaller than the space we have to consider when working with operations on a state. (And in practice, the only form of verified formal proof of properties of program fragments that sees use in "normal" industrial code (i.e. ordinary webapps and the like, not high-assurance environments) is Haskell-like typesystems). I could believe that a different formalism could work, but I can't believe that state-based reasoning could ever displace expression-based reasoning, since (as seen in your own talk examples) even very short expressions can correspond to absolutely enormous spaces of possible states.
No, that's just not true. If you have an order relation (a Boolean lattice, in fact), and B => C, then if A => B, then A => C. I.e., any proposition C that is true for your level-of-detail B, then it is also true for your finer level-of-detail A.
> because of course in the lambda calculus they're one and the same
This is a philosophical question, but I don't think it's accurate to say that. For one, the lambda calculus alone does not really describe a computation. Only a lambda expression combined with a state-machine -- i.e., an evaluation strategy -- defines a computation.
> Certainly I want to reason that way (most of the time), because it's a lot more convenient and simpler than reasoning about sequences of operations.
I don't know how you can say either of those things. It's true that I'm a beginner at Lean, but proving things in TLA+ is usually much easier. It's not so much a sequence vs a function, but that you naturally get this beautiful "lattice of abstraction". It allows you to prove that, say, a general description of the Quicksort, one that simply cannot be written in any programming language as it leaves unspecified how a pivot is chosen as well as other details, indeed sorts, and then you can show that a particular implementation is a refinement of that high-level description, and you automatically know it sorts correctly.
In addition, this style allows you to write your program however you like, and only then prove things about it, rather than write it with specific properties in mind (e.g., if you want to prove worst-case complexity, you must either write your program as a monad or use types that include a cost model). I've heard that some functional type theories, in particular, proof refinement logic, PRL, allows you to do the same, but it's not something that you can just do in Lean/Coq (unless you embed TLA in them).
Also, by far the most common proof technique of global program correctness (regardless of formalism) is the inductive invariant technique. Namely, say your program is P, and that your global correctness property (say, "the database is always consistent") is S, and you want to show that P => S, the inductive invariant technique finds an invariant I, such that I => S, that I is true in your initial state, and that if I is true for any state s of your program, then it is also true for any state s' reachable from s. This may not be how you prove properties of some simple functions, but it is by far the most common way to prove a global property for an entire program. Behavioral semantics makes this particularly convenient.
> monads are useful for working with computations that are perfectly adequately described by functions.
Right, but they're still part of the "functional algebra". You don't use them if your computations are represented by an entirely different algebra. They are not used in process calculi, and they are not used in TLA. They just don't serve any role whatsovever in describing computations in those mathematical theories.
> the broader notion of whether we analyse program fragments as sequences of operations on a pervasive state that changes over a pervasive time, or as expressions in a term reduction system.
Not exactly. A "term-reduction system", more commonly called an abstract rewriting system, is also a state machine. The difference, rather, is in denotation. Whether you're working in a system where the denotational semantics of a term is a so-called partial function, or one where the semantics of a term is different, say, a set of sequences, as in TLA.
> I'm agnostic about specific formalism, but I think being able to analyse programs as expressions where we consider expressions with the same reduction as equivalent is a vital capability that I would want any formalism I used to have.
You get that anyway. Even in Java. That was precisely what Christopher Strachey showed when he first introduced the term "referential transparency" to programming languages[1] -- that imperative languages are referentially transparent. In Java, if you have an expression e, you can replace any sub expression, x, with another y, that has the same denotation, without changing the denotation of e. The difference between Java, Haskell and TLA is just what that denotation is. In Haskell, it is a "partial function"; in Java it's a predicate transformer [3] (i.e., a Hoare triplet); in TLA it's a set of sequences. This choice has both aesthetic and prgamatic consequences. I completely agree that the functional denotation and the behavior denotation are both normally more convenient than a Hoare triplet.
> And I think there's a close-to-objective sense in which that technique/approach is valuable: the space of possibilities we have to consider when working with terms in a language can be so much smaller than the space we have to consider when working with operations on a state.
This is simply not true on multiple levels. One, you always "work on terms" when working syntactically. The question is what is the semantics of the term. It is 100% false that a semantic domain of partial functions makes your state space in any way smaller than if your semantics domain is sets of behaviors. It's just not true.
> And in practice, the only form of verified formal proof of properties of program fragments that sees use in "normal" industrial code (i.e. ordinary webapps and the like, not high-assurance environments) is Haskell-like typesystems
This is 100% false. Haskell's type system (without clever tricks such as singleton types) is so weak that the properties it "verifies" fall far, far below what is normally regarded as "formal verification". OTOH, the most common formal verification in industry is done on hardware and realtime software systems, which normally employs model checkers, and uses temporal logic, and semantics very similar to those of TLA or Eve. Eve brings the formalism that's so far been used for formally-verified development in the safety-critical world to the mainstream. In addition, some well-known companies using formal verification, like Altran UK, use Ada SPARK, which uses Hoare logic. Haskell-style programming is just nowhere near what people call formal verification, and those who use formal verification rarely use Haskell.
> I can't believe that state-based reasoning could ever displace expression-based reasoning, since (as seen in your own talk examples) even very short expressions can correspond to absolutely enormous spaces of possible states.
This is just mathematically wrong, because if you think of the cardinality of functions you'd realize that it's the same as (normally bigger, actually) than that of sequences (e.g. the set of functions from the natural numbers to the natural numbers is exactly that of sequences of natural numbers). In fact, this makes it harder to create automated formal reasoning tools (model checkers and static analysis tools employing abstract interpretation) for functional languages.
You're also wrong because already that style is far more common in formal verification. You don't have to take my word for it. Here are Xavier Leroy and Simon-Peyton Jones bemoan that the state of formal methods in FP is so far behind that of even "classical" imperative programming languages [4].
[1]: https://en.wikipedia.org/wiki/Abstract_rewriting_system
[2]: https://stackoverflow.com/a/9859966/750563
[3]: https://en.wikipedia.org/wiki/Predicate_transformer_semantic...
[4]: http://homepages.inf.ed.ac.uk/stg/Milner2012/Monday_Panel-ht...
Well of course, as long as you make the denotation fine grained enough! Any language is referentially transparent if every expression is only denotationally equal to itself. The point is that Haskell's equational theory is very rich and Java's isn't. From there we conclude that Haskell's is more useful. Whether it's useful enough is another issue, but claiming the Java is referentially transparent is almost vacuous.
> [4]: http://homepages.inf.ed.ac.uk/stg/Milner2012/Monday_Panel-ht....
To you know the precise time in the video?
Of course it's true. There's a surjection from behivours to partial functions. Proving things about denotational semantics is obviously easier than proving things about operational semantics. It's just less useful.
> > I can't believe that state-based reasoning could ever displace expression-based reasoning, since (as seen in your own talk examples) even very short expressions can correspond to absolutely enormous spaces of possible states.
> This is just mathematically wrong, because if you think of the cardinality of functions you'd realize that it's the same as (normally bigger, actually) than that of sequences (e.g. the set of functions from the natural numbers to the natural numbers is exactly that of sequences of natural numbers).
I think you must have misunderstood. Here's a simple example. There are finitely many partial functions between finite sets A and B but infinitely many sequences of state transitions that take states in A to states in B.
No, it is false. If all your functions were on simple types, then you would be correct (although the cardinality is still the same), but in order to express some programs using function semantics, you need to have higher-order functions, which vastly increase your state space.
> Proving things about denotational semantics is obviously easier than proving things about operational semantics. It's just less useful.
Again, what operational and denotational semantics are depends entirely on the formalism. The operational semantics of TLA don't even express the computation at all.
> There are finitely many partial functions between finite sets A and B but infinitely many sequences of state transitions that take states in A to states in B.
But the sequences exist in a lattice! I'm being very imprecise (to say the least; this is actually wrong, but conveys the idea) here, but just to give you an intuition, the sequence <1, 5, 6, 7, 8, 12, 0, 2, 1, 8, 6> is "smaller" in the lattice than the sequence <1, 6>. If your proposition is true for the latter, it is automatically true for the former. You never work with all possible sequences. In fact, there are infinite levels of them. Between any two states in a TLA+ behavior, there is an unbounded (yet finite) number of other states that are implicitly ignored. So what? The "state space" of which you reason is exactly the same as that of a "function" (assuming the function has enough information to prove the proposition, i.e., that it's not about complexity etc.).
> Be careful to pay attention to what lmm actually claimed. The claim was about "proof of properties of program fragments ... in "normal" industrial code ... ordinary webapps".
AFAIK, the only industrial grade, web programs etc., for which formal methods are used are Amazons AWS and some of Oracle's web services, that use TLA+. Whether or not someone uses Haskell, Haskell simply falls too short of "formal methods".
> Any language is referentially transparent if every expression is only denotationally equal to itself.
No, that's just not true. The only way that would work is if your denotation is the syntax itself, and that's just not what people mean when they talk about semantics in general. Template Haskell and Lisp are not referentially transparent. Regardless of what the denotation of term a is, you cannot replace it with any term b having the same denotation (and one exists unless your "denotation" is the syntax) while preserving the denotation of the complete expression.
> claiming the Java is referentially transparent is almost vacuous.
Except that the person who claimed it was Christopher Strachey in a seminal paper of programming language theory. No, it is not vacuous in the least.
> From there we conclude that Haskell's is more useful.
I know you very strongly believe that (and I do not), but there's neither the theoretical justification nor the empirical evidence (at least so far) to support that. From the fact that you can assign simple and clear semantics to some kinds of computation you most certainly cannot conclude that the formalism is more useful in general. It all comes down to aesthetics and pragmatics. You like Haskell better than Java (and I like Java better than Haskell), and you are more productive in Haskell than Java (and I'm more productive in Java). That's all. Unless we have evidence of either being universally more productive than the other, we simply cannot make such claims. And that's OK! You can evangelize Haskell showing people what you like about it and why you think it's great. I just don't like these sweeping claims that have no justification. This applies to everything, BTW, even to Scheme, ML, Java and TLA+ -- all of which I really like. I can rarely if ever bring myself to believe that some approach to software is universally (or close to it) better than others, unless there is some very compelling evidence.
> Do you know the precise time in the video?
No. I remember Leroy mentioning it at the very beginning, and then they discuss it at some later point, as well.
The info you have provided about TLA+ is extremely useful and I hope you can see that I have made a good faith effort to understand your point of view. However, I do not feel an equal effort back towards my position, so I'm afraid I'll have to leave it there.
TLA+ isn't, like, a 'better Haskell'. It's more of a 'better UML' or 'a better sack of flowcharts', especially when you are dealing with concurrency. It's an exhaustive checker on the spec.
You _can_ use it in the way pron is talking about, but that's not how most people outside academia use it that way.
I dislike the notion of "better" altogether when it comes to software. My point is that FP is not the only nor the most convenient way to reason about software. It has pros and cons, like any other approach; it sometimes very elegant, and sometimes less so. Preference is determined largely by a personal aesthetic preference. I have no qualms whatsoever with those who are more aesthetically drawn to the functional representation of programs. I have a problem with those claiming it is superior to other approaches without any reasonable justification. I am also extremely opposed to claims that people who prefer a non-pure-FP programming language over Haskell do that only because they don't know better. There are very good reasons to prefer either, and they're almost never universal, but depend both on the domain and the team.
Also, I'm not comparing TLA+ to Haskell, but rather TLA+ to Lean/Coq, and Eve to Haskell. Synchronous programming languages like Eve (or Esterel/SCADE for realtime systems) are to TLA+ what Haskell is to Lean/Agda (roughly).
> You _can_ use it in the way pron is talking about, but that's not how most people outside academia use it that way.
I think that you'll find that once you start specifying complex systems (like a distributed database), the refinement relations is extremely useful (in fact, pretty much essential), and is used in practice often (for whatever definition of often is reasonable for formal methods). It makes model-checking (and proofs, but those are rarely used outside academia) much more tractable. I used three levels of refinement, with refinement maps between them, when specifying a distributed database.
Refinement is the killer-feature that allows TLA+ to scale. For simple algorithms it is indeed overkill.
> This is 100% false. Haskell's type system (without clever tricks such as singleton types) is so weak that the properties it "verifies" fall far, far below what is normally regarded as "formal verification".
Be careful to pay attention to what lmm actually claimed. The claim was about "proof of properties of program fragments ... in "normal" industrial code ... ordinary webapps".
Fundamentally, many pairs of real programs are equivalent at a coarse level and inequivalent at a finer level, so no formalism could ever escape that. We might have analysed programs X and Y in terms of their input and output and concluded they both print the same output when given the same input. But X uses mergesort and Y uses bubblesort. If we now want to compare the runtime of X and Y, we can't reuse our analysis, because fragments that we previously considered equivalent are no longer equivalent, symmetries that we previously made use of are now broken. The only way a formalism could let us reuse our analysis is if that formalism made us do all the work we'd do to compare the runtime even when we only want to compare the output. There's an excluded middle here.
> For one, the lambda calculus alone does not really describe a computation. Only a lambda expression combined with a state-machine -- i.e., an evaluation strategy -- defines a computation.
You do indeed need a description of how the computation is performed - an operational semantics - but state machines are not the only form of computation. For the lambda calculus reduction is evaluation - what you did in https://news.ycombinator.com/item?id=15786021 was computation, with no state machine in sight. The whole point of the Church-Turing thesis is that state machines and expression reduction are equivalent descriptions of computation.
> this style allows you to write your program however you like, and only then prove things about it, rather than write it with specific properties in mind (e.g., if you want to prove worst-case complexity, you must either write your program as a monad or use types that include a cost model).
This attitude has never made sense to me. Of course I'm writing my program with specific properties in mind - I'm not just writing some random program and then seeing what properties it has, I'm writing the program because I need a program with certain properties. If I've got a requirement for a particular worst-case complexity, I can't write any useful subcomponents without thinking about worst-case complexity; I want worst-case complexity to be visible for every line I write, as soon as I write it.
> A "term-reduction system", more commonly called an abstract rewriting system, is also a state machine.
No it isn't. It's a different formalism for describing computation, per Church-Turing. You can simulate one with the other, but neither subsumes the other; a rewriting system isn't a state machine any more than a state machine is a rewriting system.
> You get that anyway. Even in Java. That was precisely what Christopher Strachey showed when he first introduced the term "referential transparency" to programming languages[1] -- that imperative languages are referentially transparent. In Java, if you have an expression e, you can replace any sub expression, x, with another y, that has the same denotation, without changing the denotation of e. The difference between Java, Haskell and TLA is just what that denotation is. In Haskell, it is a "partial function"; in Java it's a predicate transformer [3] (i.e., a Hoare triplet); in TLA it's a set of sequences. This choice has both aesthetic and prgamatic consequences. I completely agree that the functional denotation and the behavior denotation are both normally more convenient than a Hoare triplet.
Any collection of symbols can be given a trivial "denotational semantics", but this "denotational semantics of Java" would not capture the things that make Java Java, because the relations between "expressions" (which would not correspond to Java expressions) bear no relation to the definition of Java-as-it's-usually-understood, the denotations of Java functions would not be functions. To be able to meaningfully talk about denotational semantics for a language, the semantics of a sequence of symbols in our denotation should match the way the sequence of symbols is understood by a reader, otherwise we just have two different languages that use the same symbols - and I don't think most people would read a line of Java and understand it to mean a Hoare triple. I'm not even convinced you've produced something compositional (GCL programs are just sequences of statements and can be composed by concatenation, so the Hoare triple semantics is valid for them, but Java programs are not structured that way), so it may not be a denotational semantics at all.
> you always "work on terms" when working syntactically
Exactly - what I'm saying is I want a toolset that makes it easy to work syntactically. I want referential transparency in terms of the common-sense meaning of the syntax, not in terms of some contrived meaning that exists only for analysis. I want a denotational semantics where things that look like function application denote function application, things that look like equality denote equality, and so on.
> It is 100% false that a semantic domain of partial functions makes your state space in any way smaller than if your semantics domain is sets of behaviors.
There are only 9 possible partial functions of type Boolean => Boolean, whereas there's a combinatorially huge number of possible behaviours. But most of the time I don't even have to reason about the specifics of a function, because just knowing that it is a function - that applying it to the same input always means its return value when applied to that input - provides me with enough information to greatly simplify the space of possibilities to think about. If I have some code like:
{
val a = f(2, 4, 5)
g(a, a)
}
g(f(2, 4, 5), f(2, 4, 5))
> Haskell's type system (without clever tricks such as singleton types) is so weak that the properties it "verifies" fall far, far below what is normally regarded as "formal verification".
Be that as it may, what I said stands: properties of program fragments are formally proven, in a verified way, in normal industrial code, every day using Haskell-like type systems. No other approach can say that; Eve may be aiming for mainstream but it's nowhere near as mainstream as Haskell. I'm a lot more confident in our ability extend that approach to cover the properties we care about, than in our ability to get the overhead of state-oriented approaches low enough to use for normal industrial code.
> This is just mathematically wrong, because if you think of the cardinality of functions you'd realize that it's the same as (normally bigger, actually) than that of sequences (e.g. the set of functions from the natural numbers to the natural numbers is exactly that of sequences of natural numbers).
Just thinking about sequences of state operations doesn't tell me enough to understand a program; I can't understand the composition of two sequences of state operations without understanding the full state. Whereas to understand the composition of two functions I only have to understand the return value of the first function, and that's generally taken from a much smaller space of possibilities than the space of possible program states. (Of course a state operation is equivalent to a function from program state to program state, and such functions would be just as hard to understand as state operations - but most functions are defined on much smaller spaces).
> Here are Xavier Leroy and Simon-Peyton Jones bemoan that the state of formal methods in FP is so far behind that of even "classical" imperative programming languages [4].
I don't do videos; I'll happily read written stuff but that talk didn't seem to be listed in the slides section of that site.
You keep saying that, but TLA is a formalism specifically designed to do just that. It defines a lattice of algorithms, where one is "smaller" than another if it is a refinement of it.
> If we now want to compare the runtime of X and Y, we can't reuse our analysis, because fragments that we previously considered equivalent are no longer equivalent, symmetries that we previously made use of are now broken.
No, that's not true, because equality and equivalence aren't the same. You can work with an equivalence relation knowing full well there are finer equivalences (think, e.g. of quotient types). In fact, in a partial order (like a lattice), for every element a, we can define an equivalence relation ~a, s.t. x ~a y iff x ≤ a and y ≤ a, i.e., all elements less than a are ~a-equivalent. You can work with programs like that, saying, e.g., that a is "any program that sorts", and so all sorting programs are ~a equivalent. Still, theorems that make use of this equivalence relation (or any other) do not assume that it's an equality relation.
I don't want to presume, but you maybe you're just used to a formalism where the only equivalence (on the denotation in that formalism) is equality (the extensional function equality). To make this more familiar, I can point out that typed functional languages also have weaker notions of equivalence, as they have one level of abstraction/refinement (assuming no subtypes) -- that between types and their inhabitants; the relation between type parameters and concrete types might be another level, as is typeclasses. You normally have theorems about functions based just on types, and that are true for all inhabitants (or theorems about a polymorphic signature that is true for all type instances). You don't need to rework your theorems for every type inhabitant (or every type instance). In a formalism like TLA, this abstraction/refinement relation is a lattice with infinite levels (a little similar to a formalism with subtypes). Instead of just having types (which express nondeterminism, i.e., the type Int -> Int nondeterministically represents some Int -> Int computation) and inhabitants, you have arbitrary levels of nondeterminism (or abstraction), where more refined programs can be instances of more abstract ones (i.e., ones with more nondeterminism).
> but state machines are not the only form of computation. For the lambda calculus reduction is evaluation - what you did in https://news.ycombinator.com/item?id=15786021 was computation, with no state machine in sight.
Evaluation is a state machine. The substitution I did -- that's a state machine. A state machine is not a Turing machine. It is anything that has states (e.g. expressions) and transitions between them (e.g. reductions).
> The whole point of the Church-Turing thesis is that state machines and expression reduction are equivalent descriptions of computation.
Not quite. That inference rules (reductions) form computation was known since Leibniz in the 17th century. Church's claim was that even the simple reductions of the simple lambda calculus can express any computation expressible by any formalism. Turing explained why that is -- because all formalisms and inference rules are special cases of state machines. Gödel then called Turing's explanation "a miracle", as for the first time we had a definition of what a formal system is and how it works.
> Of course I'm writing my program with specific properties in mind - I'm not just writing some random program and then seeing what properties it has, I'm writing the program because I need a program with certain properties.
It's not always that simple. Suppose I ask you to write a sorting program and you come up with mergesort. You then notice that aside from just sorting it has the property of being stable for incomparable elements. That's something that's nice to be able to prove without rewriting the program.
> You can simulate one with the other, but neither subsumes the other; a rewriting system isn't a state machine any more than a state machine is a rewriting system.
A rewriting system is very much a state machine (albeit often a nondeterministic one, due to evaluation order).
> Any collection of symbols can be given a trivial "denotational semantics", but this "denotational semantics of Java" would not capture the things that make Java Java, because the relations between "expressions" (which would not correspond to Java expressions) bear no relation to the definition of Java-as-it's-usually-understood, the denotations of Java functions would not be functions.
I don't know where you get that. Formal methods for Java (like Infer [1]) make use of this denotation all the time, and programmers who carefully think about their Java programs do it just as effectively as those who carefully think about their Haskell programs. Sometimes their work is harder, and sometimes it isn't, and in any event, there are many other considerations to take into account (e.g., analyzing programs from syntax is not the only nor the "best" way to analyze programs; we also analyze programs as they run using dynamic analysis tools, profilers and tracing).
Of course the denotation of Java methods isn't functions. The standard denotation for imperative languages is that of Hoare logic (or "Predicate transformer semantics" [2]). If I write a Java method that isn't pure, I don't think of it as a function. In fact, I rarely think of computations functions.
> I want referential transparency in terms of the common-sense meaning of the syntax, not in terms of some contrived meaning that exists only for analysis.
It's not contrived at all, and it's rather intuitive: every Java statement is a transformation of program state.
Now, I completely agree with you that functional semantics are more convenient (as they're simpler, more local etc.), but they stop being convenient once the program isn't sequential. The question is, is it worth it to use a language that enforces (by enforced purity) this function semantics on the entire program if it's only really helpful for some bits of it. There is no right answer to this question. Some would prefer that language and some wouldn't, and both would be perfectly justified.
> There are only 9 possible partial functions of type Boolean => Boolean, whereas there's a combinatorially huge number of possible behaviours.
How many possible partial functions are there for (Int -> Int) -> (Int -> Int)?
> and I've only had to think about a few lines
That's really, really good! But 1/ that still doesn't mean that purity needs to be enforced everywhere, and 2/ this helps but only with the easy part.
> properties of program fragments are formally proven, in a verified way, in normal industrial code, every day using Haskell-like type systems.
In that case, many, many more systems (many, many times over) are formally proven using Java-like type systems.
> I'm a lot more confident in our ability extend that approach to cover the properties we care about, than in our ability to get the overhead of state-oriented approaches low enough to use for normal industrial code.
That's an overhead that you're imagining. In fact, it's much easier to build formal tools for what you call "state-oriented" approaches than for pure functional languages because of the latter's dependence on higher-order functions.
> Just thinking about sequences of state operations doesn't tell me enough to understand a program; I can't understand the composition of two sequences of state operations without understanding the full state... Of course a state operation is equivalent to a function from program state to program state, and such functions would be just as hard to understand as state operations - but most functions are defined on much smaller spaces
Look, you're trying to extrapolate from bits of information. We're talking about a system that's based on temporal logic, by far the most useful logic for formal methods to date, and one that has so far directly yielded two Turing awards. You can try to imagine what that system would look like or you can read my posts/watch my talk. You're not actually dealing with the elements of sequences as you may imagine, just as you're not dealing with sets of pairs when you're analyzing functions. We're talking about an elegant algebra of program behaviors, that I don't wish to fully describe in a HN comment, partly because I've already described it elsewhere.
Anyway, once again, I'm not by any means trying to claim that Java is better than Haskell or that Eve is better than Haskell etc. I'm just trying to say that your conlusions (that Haskell is better than Java) are based neither on a good theoretical justification -- 1/ the fact that you can easily reason about sequential programs is very nice, but most programs today aren't sequential, and so we get to tradeoffs again, and 2/ you seem unfamiliar with the vast body of research on other kinds of program analysis; AFAIK, nobody claims that those other methods are any "better" or "worse" than the functional one; just different -- nor on any empirical data (which is far more important). I just don't like this discourse that X is better than Y without a careful definition of what "better" means and without some very compelling evidence.
[1]: http://fbinfer.com/docs/separation-logic-and-bi-abduction.ht...
[2]: https://en.wikipedia.org/wiki/Predicate_transformer_semantic...
Well, sure. But showing that two programs are ~-equivalent will be no help in attempting to show that they do (or don't) have the same runtime. The fact that I don't have to switch formalisms to talk about runtime doesn't actually help me, because I still have to redo all my analysis.
> A state machine is not a Turing machine. It is anything that has states (e.g. expressions) and transitions between them (e.g. reductions).
"State machine" is generally understood to mean a finite state machine i.e. a Turing machine.
> That inference rules (reductions) form computation was known since Leibniz in the 17th century.
Indeed; they are if anything the most natural definition of computation, contra your description of computation as a physical process. The "miracle" of Church-Turing is that the mechanistic finite state machine is equivalent to the more natural rewriting system, paving the way for mechanical computation.
> Turing explained why that is -- because all formalisms and inference rules are special cases of state machines.
He didn't show anything about a state machine in your generic sense of "anything that has states and transitions between them". He showed an equivalence between reduction and finite state machines. Neither is a special case of the other, they're just equivalent.
> It's not always that simple. Suppose I ask you to write a sorting program and you come up with mergesort. You then notice that aside from just sorting it has the property of being stable for incomparable elements. That's something that's nice to be able to prove without rewriting the program.
If stability was part of the requirements I would've wanted to pay attention to it all along; if it wasn't then it's unlikely to become one. Accidentally implementing a future requirement seems like a very rare coincidence.
> If I write a Java method that isn't pure, I don't think of it as a function. In fact, I rarely think of computations functions.
I suspect that's pretty unusual. I mean, it's pretty normal to call them "functions".
> It's not contrived at all, and it's rather intuitive: every Java statement is a transformation of program state.
The trouble is that "a transformation of program state" is not an easy thing to think about. It could do absolutely anything.
> How many possible partial functions are there for (Int -> Int) -> (Int -> Int)?
A lot, so a well-structured program wouldn't use a function with a signature like that. The space of possibilities for e.g. (a -> b) -> (a -> b) is much smaller.
> That's really, really good! But 1/ that still doesn't mean that purity needs to be enforced everywhere, and 2/ this helps but only with the easy part.
My experience has been that it can all, or almost all, be put in the easy part. I just haven't had these problems with nonsequentiality that you claim. Maybe there's a niche where they're important, but I don't see the use case the broader industry - webapps, business process automation, that kind of thing.
> In that case, many, many more systems (many, many times over) are formally proven using Java-like type systems.
Sure, not that I'd really distinguish between the two at the level we've been talking at. That the Java type system has been successfully used extensively in practice is a good, hopeful thing about it - though that people commonly cite Java's verbosity as a reason for leaving the language is a mark against that. Unfortunately I've found that in practical Java programs one almost always needs to go around the type system and/or can't practically represent important properties like "this function is only called during an open database transaction" or "this object graph contains only objects that we know how to represent as JSON", due to lacking monads, lacking records, perhaps due to lacking purity. To achieve the defect rates I believe the industry will need in the future, I believe we need a couple of small extensions over the Java type system: higher-kinded types, some form of record-like types (i.e. the ability to work generically with maps where the type of each value is known, but different for different keys), maybe linearity, maybe polykinds. Not some radical new model to learn, just ordinary functions with ordinary return values the way every industrial programmer is already used to thinking about the easy parts of their program with and a few clever techniques to allow us to extend the same approach to work on the hard parts as well.
> You can try to imagine what that system would look like or you can read my posts/watch my talk. You're not actually dealing with the elements of sequences as you may imagine, just as you're not dealing with sets of pairs when you're analyzing functions. We're talking about an elegant algebra of program behaviors, that I don't wish to fully describe in a HN comment, partly because I've already described it elsewhere.
I've tried to read your posts, repeatedly. I just struggle to find the "there" there; I have no intuitions about any of these objects that don't boil down to the same thing as your shadow-variables-and-assertions example; I can't see what they're supposed to do for me that plain old functions and values and types make hard - I can't even do the things that were previously easy.
> the fact that you can easily reason about sequential programs is very nice, but most programs today aren't sequential, and so we get to tradeoffs again
I'm just not convinced there's a balanced tradeoff here. To do functional reasoning you keep a natural, familiar semantics (functions as functions and so on) in plain-old mathematics that you already use when reasoning about the easy parts of your program, you factor out commonality as functions the same way you already do when programming. We're talking about making a few small generalisations of the type system, that's all. It's such a small step, but it's enough to let you prove so many of the things you actually care about in plain old industrial programming; I really can't see why a Java or Kotlin programer would prefer to jump to analysing their programs with a whole new formalism; that seems like a much bigger cost, and there's no visible space for it to have a correspondingly greater benefit.
I'm not sure what you mean by "runtime" -- perhaps something equivalent to Haskell operational semantics -- but in other formalisms the entire system is different. For example, in TLA there is no distinction between the "runtime" and the "function denotation" -- these concepts simply do not exist -- they are both arbitrary points in the same denotational lattice. You can even say that A and B are two different refinements (implementations) of Quicksort, B and C are refinements of Mergesort, and all four are refinements of Sort. What is true for Sort is true for all four. What is true for Quicksort is true for A and B. Those are just arbitrary levels of abstraction. There is no defined concept of "function" which is a specific level of abstraction.
> "State machine" is generally understood to mean a finite state machine i.e. a Turing machine.
A Turing machine is certainly not a finite state machine, and abstract rewriting systems are also state machines. In fact, if you'll google for papers on the operational semantics of lambda calculus (or related PLs), I'm sure the term state machine will come up.
> Indeed; they are if anything the most natural definition of computation, contra your description of computation as a physical process. The "miracle" of Church-Turing is that the mechanistic finite state machine is equivalent to the more natural rewriting system, paving the way for mechanical computation.
Where "more natural" meaning you like it better because that aesthetic appeals to you :) There is just no accepted standard here. In fact, vast subfields of CS never consider the formal-system description, and they are much, much larger than those subfields who prefer working in formal systems.
> He didn't show anything about a state machine in your generic sense of "anything that has states and transitions between them". He showed an equivalence between reduction and finite state machines. Neither is a special case of the other, they're just equivalent.
Not quite. Read his paper, it is very readable. He defines (for the first time!) a general notion of computation, and from it creates an arbitrary instance of it (which is not a finite state machine) which we now call "Turing machines" just for the sake of rigorous mathematical analysis. Turing was the first to define computation in general.
> If stability was part of the requirements I would've wanted to pay attention to it all along; if it wasn't then it's unlikely to become one.
My experience has been different.
> I mean, it's pretty normal to call them "functions".
First, they're not called functions in Java, but "methods", but let's say C. It's pretty normal to call Haskell functions "functions", even though they're not. The term "function" in programming has a long history, and it's because the idea resembles mathematical functions. I agree Haskell functions resemble mathematical functions much more than C functions, but neither of them are actual functions.
> My experience has been that it can all, or almost all, be put in the easy part. I just haven't had these problems with nonsequentiality that you claim. Maybe there's a niche where they're important, but I don't see the use case the broader industry - webapps, business process automation, that kind of thing.
Well, we've had different experiences, then, but I don't need to trust my experience. There's no evidence that writing applications in Haskell is significantly cheaper than writing them in Java or Kotlin.
> "this function is only called during an open database transaction" or "this object graph contains only objects that we know how to represent as JSON", due to lacking monads, lacking records, perhaps due to lacking purity.
This is actually easier in Java than in Haskell. That's what JML[1], arguably the most sophisticated contract system out there, is for (although, admittedly, very few people use it; then again, very few people use Haskell). I don't know why you keep bringing up monads when they are a feature of a formalism, not a general solution to a problem.
> To achieve the defect rates I believe the industry will need in the future, I believe we need a couple of small extensions over the Java type system: higher-kinded types, some form of record-like types (i.e. the ability to work generically with maps where the type of each value is known, but different for different keys), maybe linearity, maybe polykinds.
The difference is that I come from a formal methods direction. I don't look at solutions just in FP. I look at the entire formal methods field and see which solutions are promising for the problems. While I don't know if any would work, both research and a few decades of experience in safety-critical realtime systems show that the synchronous approach, now taken by Eve, is much more promising from a correctness perspective. If your only point of reference is FP, I don't know how you can claim that the (quite clunky, IMO) solutions FP comes up with are the best way forward. Read up on what the general formal methods community is reasearching so you'll have something to compare the FP approach to.
> It's such a small step, but it's enough to let you prove so many of the things you actually care about in plain old industrial programming; I really can't see why a Java or Kotlin programer would prefer to jump to analysing their programs with a whole new formalism; that seems like a much bigger cost, and there's no visible space for it to have a correspondingly greater benefit.
They don't need to jump anywhere. The current formal tools for Java are far more sophisticarted than those available for Haskell. That people don't use them is a different matter, but it's both a shorter jump and arguably a similar if not greater benfit to go from programming in Java to programming in Java and running a static analyzer than to go from programming in Java to programming in Haskell (even assuming Haskell was no worse than Java in any regard, and I find that this is not at all the case).
Church's definition of the lambda calculus actually slightly predates Turing's definition, and Goedel's definition was even earlier. There are bidirectional equivalences between all three; neither is an instance of the other.
> This is actually easier in Java than in Haskell. That's what JML[1], arguably the most sophisticated contract system out there, is for (although, admittedly, very few people use it; then again, very few people use Haskell).
> They don't need to jump anywhere. The current formal tools for Java are far more sophisticarted than those available for Haskell. That people don't use them is a different matter, but it's both a shorter jump and arguably a similar if not greater benfit to go from programming in Java to programming in Java and running a static analyzer than to go from programming in Java to programming in Haskell
I would think Haskell is substantially more popular than JML, though I could be wrong. I did make an effort to use a contract-based system with Java code and found it was ultimately harder than switching languages. Partly that's a question of tooling, but I think the biggest barrier was the semantic model.
> If your only point of reference is FP, I don't know how you can claim that the (quite clunky, IMO) solutions FP comes up with are the best way forward.
I'd make two points here: 1. The things FP does are largely just the application of widely agreed programming principles - separating concerns, making each function do one thing, explicitly distinguishing interface from implementation. I can imagine needing another formalism as well, but I can't imagine wanting to not have monads or records, and the minor type system enhancements needed to accommodate them seem like such a tiny cost compared to the benefits. Even if you only use the functional techniques for some parts of your analysis, and do other analysis using other techniques, a small language feature that makes the functional techniques much more effective is still worthwhile. 2. I feel like I gave a fair test in terms of the time and effort I put in - if anything I put much more effort into trying to use the non-FP approaches. FP solves the problems I have, and I didn't have to stop working and learn a new formalism; I was able to incrementally get there, starting by doing the same stuff I was already doing in Java, and remaining productive every step of the way. Whereas I sunk hours into thinking about preconditions and postconditions and never got anything out of it.
Read the papers, then. You'll find striking differences between Church's and Turing's papers. For one, Church doesn't define what computation is. Instead, he attempts to justify why the lambda calculus is universal, and even then he gets caught in circular reasoning, at which point he gives up and writes in a footnote something like, well, if I can't do this, I don't know how anyone can define computation. Turing's paper, however, was one of the biggest philosophical breakthroughs at least since the 17th century, and regarded by Gödel as a miracle. It is true that Church published his proof of the undecidability of logic ahead of Turing, but his paper does not contain an analysis of what computation is, whereas precisely that is considered the main achievement of Turing's paper.
> I would think Haskell is substantially more popular than JML, though I could be wrong.
I would think so, too, but it's still very fringe.
> I did make an effort to use a contract-based system with Java code and found it was ultimately harder than switching languages. Partly that's a question of tooling, but I think the biggest barrier was the semantic model.
I've had the opposoite experience. Even if Haskell dominated Java as a language (which I absolutely don't think it does), I wouldn't consider it worth switching because the bottom-line benefits are too small (if they exist at all), while the tooling and ecosystem (both libraries and hiring) is so lacking that the significant hit would dwarf any gains.
> The things FP does are largely just the application of widely agreed programming principles - separating concerns, making each function do one thing, explicitly distinguishing interface from implementation.
I disagree that FP has any advantage here over most programming languages.
> I can't imagine wanting to not have monads or records, and the minor type system enhancements needed to accommodate them seem like such a tiny cost compared to the benefits.
First, most languages have records (including Eve and TLA+). Second, monads are completely meaningless and useless once functions are not how you describe computation. They are very much a formalism-dependent construct. Lastly, while I like type systems, I think about the problem not the solution. The problem is cheap specification and verification of simple propeties. Types are not the only way of doing that, and when considering the future of programming, we cannot constrain ourselves to solutions found within a very narrow sub-discipline while ignoring the full body of research.
> I feel like I gave a fair test in terms of the time and effort I put in - if anything I put much more effort into trying to use the non-FP approaches. FP solves the problems I have, and I didn't have to stop working and learn a new formalism; I was able to incrementally get there, starting by doing the same stuff I was already doing in Java, and remaining productive every step of the way. Whereas I sunk hours into thinking about preconditions and postconditions and never got anything out of it.
I fully believe that. I've had the exact opposite experience, ever since starting to work with Scheme and SML almost twenty years ago. I don't think Java dominates Haskell and I don't think Haskell dominates Java. Each works better for different people and different circumstances, and there is currently no evidence that either is significantly ahead of the other in terms of the bottom-line.
I have no problem arguing for days over this feature and that, this design philosophy or the other. I just don't like claims that the evidence does not support.
I found these problems were worse when trying to use contracts; since they're not part of standard Java, the tooling and ecosystem doesn't work nicely with them. Automated refactoring in the IDE won't update the annotations properly. You go to use an existing library and find that the published annotations were for a previous version and no longer match the current API, or you can't find which version they go with - or worst of all, they still match the method signatures but are no longer true. And the hiring problem is the same. Ultimately the point I suspect we may have to disagree on is that I'm a lot more confident most Java programmers could learn Haskell than I am that most Java programmers could learn a contract-like approach, because I really think the latter is a much bigger conceptual leap.
> I disagree that FP has any advantage here over most programming languages.
I see programmers in other languages having to go around the language to get these things - e.g. the popularity of annotation-based AOP in Java codebases, and the use of monkeypatching to address similar problems in scripting languages - in a way that doesn't happen in (Haskell-like) FP languages.
> monads are completely meaningless and useless once functions are not how you describe computation. They are very much a formalism-dependent construct.
Be that as it may, I thought we agreed that we frequently do want to do the functions-and-values kind of reasoning about our programs, even if we only do it for the "easy parts".
> Lastly, while I like type systems, I think about the problem not the solution. The problem is cheap specification and verification of simple propeties. Types are not the only way of doing that, and when considering the future of programming, we cannot constrain ourselves to solutions found within a very narrow sub-discipline while ignoring the full body of research.
If there's an adequate solution in that narrow sub-discipline then we can. If the cheapest, most familiar approach works then there's no reason to look at more expensive approaches. Almost all programmers working in the industry have at least some basic familiarity with type systems. I'm not against exploring more radical approaches - that's part of what research is for - but when it comes to advocating something for industrial use, let's be sure we've exhausted the easy options first.
Right. There are always tradeoffs.
> And the hiring problem is the same.
I don't think so. A Java programmer can be trained in JML in a day.
> Be that as it may, I thought we agreed that we frequently do want to do the functions-and-values kind of reasoning about our programs, even if we only do it for the "easy parts".
Sure, but pure "functions" can be reasoned about as functions even in Java.
> If there's an adequate solution in that narrow sub-discipline then we can. If the cheapest, most familiar approach works then there's no reason to look at more expensive approaches.
It's neither the cheapest nor the most familiar. Virtually no formally verified programs encode correctness properties in types. Contracts are far more common.
> I'm not against exploring more radical approaches
It's not more radical. If you look at the programs of formal methods conferences, you'll find that the typed-FP approach is in the minority. I think that part of the problem is that some FP people have isolated themselves in a bubble that they sometimes forget how small it is.
This I don't believe, not in the general case. If it were that easy we'd see a lot more people doing it. (And I'm pretty sure I've put more than a day's worth in over the years).
> Sure, but pure "functions" can be reasoned about as functions even in Java.
It's much harder without monads. You lose the ability to cleanly divide the return value of a function that's composed from smaller functions into two visibly orthogonal aspects that you can provably think separately about, so you have to understand all aspects of what the intermediate values represent at once.
It is that easy. What is hard isn't knowing JML, but gaining experience with specification in general. This is a skill that is required regardless of formalism (and is actually why Idris and Java+JML, despite being very different, are still much more similar than they are different; same goes for TLA+ and Lean).
One of the reasons I would encourage those who are interested in correctness to read Schmidt's overview of abstraction/refinement relations [1] -- which forms the core of possibly the most important idea in all of program analysis: abstract interpretation -- is that it allows one to see type systems, contracts, refinement logics etc. as different expressions of this same core idea; specifically of a Galois connection between different abstraction levels, be they a program and its type, a program and its contract, or different abstraction levels in a formalism like TLA.
> It's much harder without monads.
But you have monads in Java. In fact, there are many more Java programmers using monads (e.g., Stream and CompletableFuture) than Haskell and Scala programmers using monads combined. What you can't do is abstract over all monads, which is of questionable value even in Haskell (and Java has other ways of abstracting over common patterns).
The goal now is to remove the need for monads in Java. Monads are equivalent to delimited continuations, but delimited continuations compose more easily (algebraic effect systems are modeled after them) and they fit much more nicely with imperative constructs like loops and exceptions. Delimited continuations are the monads of imperative programming, and they are coming to Java.
[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.4...
A broad library of standard functions is certainly valuable; working in Java with Stream and CompletableFuture one naturally finds oneself wanting traverse, cataM and dozens of other such helpers. Maybe the ability to abstract over monads is only useful to library authors, but the libraries they produce are then immensely useful for regular programmers.
> Monads are equivalent to delimited continuations, but delimited continuations compose more easily
Perhaps, but at the cost of completely incomprehensible code. We've known for years or decades that continuation-based style can produce higher-performance code than conventional approaches, but they've seen limited adoption even in high-performance environment; many, perhaps most programmers (myself included) just don't and can't "get" them.
I find libraries that help developers save a few lines of code here and there not worth changing a programming paradigm. By far the biggest boost comes from reuse-in-the-large. I fully agree that languages with such higher-order constructs allow writing more reusable code than classical imperative languages. But "more", in this case, does not translate to big savings and does not justify a change of paradigm. We are deep in diminishing returns territory there, even if pure FP had no disadvantages.
But those higher-order constructs do not require a pure language, and could be added to Java/Kotlin once there are no bigger-impact improvements to be made, and if it's judged that their meager contribution justifies adding complexity to the language. Not every added utility automatically translates to "we should do it." Its cost must be weighed as well. Languages like Java/Kotlin choose to be more conservative in the cost/benefit of the features they embrace compared to languages like Scala.
> Perhaps, but at the cost of completely incomprehensible code.
Quite the opposite. Ordinary imperative code (i.e., blocking threads) is programming with continuations. Continuations are the core abstraction of imperative languages, just as partial functions are the core abstraction of pure-functional ones, and all the core constructs in those languages -- loops, exceptions -- are built to work with them. The complex code you're thinking of is analogous to very complex code that can be achieved with monads. While it could be done, there is no reason to ever do it.
I find being able to reduce code in the small yields exponential returns in the large. If one can reduce the size of plain code by say 10%, making functions and classes shorter and easier to comprehend, then that takes some of them below the threshold where they need to be split up, and unlocks further opportunities to see and factor out commonality, reducing code size and class counts further. That might take you below the threshold for needing to separate a layer in the larger component, and that in turn allows more reuse; that might take a component below the threshold of needing splitting up, and that might take the project below the threshold where it needs multiple developers or multiple teams involved.
You don't have to change paradigm. I can understand (though I don't agree with) wanting more operational features in a language. But I can't understand being so hostile to these conservative but useful features.
> But those higher-order constructs do not require a pure language, and could be added to Java/Kotlin once there are no bigger-impact improvements to be made, and if it's judged that their meager contribution justifies adding complexity to the language. Not every added utility automatically translates to "we should do it." Its cost must be weighed as well.
Costs should indeed be weighed, but HKT has one of the strongest cases in terms of power-to-weight: it's a very cautious extension of the type system that doesn't really make the language any more complex, since it just means permitting type parameters to be used in ways that concrete types are already allowed to be used. And virtually every application can benefit; I use traverse virtually every day. Features like language-level null or delegation have a much higher risk (they change more of the rules of the language, a reader has to be aware of them even if they aren't using them directly and when they're not necessarily visible in a function signature) and are less broadly applicable.
> Quite the opposite. Ordinary imperative code (i.e., blocking threads) is programming with continuations. Continuations are the core abstraction of imperative languages, just as partial functions are the core abstraction of pure-functional ones, and all the core constructs in those languages -- loops, exceptions -- are built to work with them.
Threads, loops and exceptions are notorious sources of bugs and incomprehensible code. To the extent that they're the core of imperative programming, imperative programming is a bad thing.
I am not hostile to them, just skeptical of their cost/benefit. I don't think every useful feature has a place in every language. Different languages should have different thresholds for the cost/benefit of features they want. It's perfectly legitimate for Scala to have a low threshold, and for Kotlin/Java to have a high one. In fact, a high threshold on cost/benefit is one of the cornerstones of the Java design philosophy, as laid down by James Gosling back in the 90s. He said that his design philosophy for Java specifically excludes features that are just a good idea, and only includes features that solve major problems (of course, what constitutes a major problem is neither universal in time nor in space; as coding fashions change, problems that were once minor can become major). You may prefer to use a language with a different design philosophy, but I think that philosophy is certainly reasonable. Again, without any kind of empirical data, I don't see how this can be settled by anything other than personal aesthetic preference.
> HKT has one of the strongest cases in terms of power-to-weight: it's a very cautious extension of the type system that doesn't really make the language any more complex, since it just means permitting type parameters to be used in ways that concrete types are already allowed to be used.
Maybe, and maybe Java and Kotlin should get HKT one day. But I don't think this feature would be the most important one to add right now, and I can certainly see strong arguments against encouraging higher-order abstractions in general. For one, I find that abstractions-in-the-small take precious mental resources away from far more important things. For another (although related), I think they encourage abstract code of the kind that was common in Java frameworks like Spring, which took Java a long time to discourage in favor of simpler, more concrete code, YAGNI etc.
> Threads, loops and exceptions are notorious sources of bugs and incomprehensible code.
OK, but I strongly disagree (BTW, by "threads" I'm not implying any kind of communication mechanism, like shared memory; Erlang is also based on threads. I just mean one or more sequential instruction stream that can block).
I see the fact that Spring was immensely popular in Java for a while as demonstrating just the opposite: that overgeneralisation and second-system effect happen to everyone, even in a language whose design philosophy was oriented towards avoiding it. I see Java's adoption of generics and lambdas as acknowledgement that omitting those features didn't help encourage simpler code, it just made complex code even worse. I think it's the same for HKT and similar abstraction tools.
This is great! I'm a bit puzzled by why you're combative against the Haskell community on this issue because I believe they would be one of the early adopters of such new technology.
That being said, there are a few unanswered questions.
1. How do we really get the feel for the benefits of this model? Sure, I can struggle through tutorials on TLA, white papers on Daedalus, and the Eve live demo, but from the little I've seen it's not yet obvious to me how they solve my problems as a day-to-day jobbing programmer. The benefits of Haskell, on the other hand, became clear to me after browsing the Haskell Reddit and noticing that pretty much every post solved a problem I was currently having in my Python codebase.
2. Does the model you're describing really handle polymorphism and higher order functions? Given that polymorphism and higher order functions are known to be incompatible with set theoretic models I remain sceptical.
Of course there is (synchronous programming), but it may not necessarily be the best fit for all situations, either, and FP may well be more appropriate for sequential programs. Personally, I don't have a problem with not using the "best" at all times. I do have a problem with insisting that some formalism is "best". Like Church wrote, there is simply no such thing.
> I'm a bit puzzled by why you're combative against the Haskell community
My only problem is with claims that either state that Haskell is universally/objectively superior to other approaches because it possesses some property or other or with claims that mistake features of a specific formalism with those of computation in general.
> How do we really get the feel for the benefits of this model? Sure, I can struggle through tutorials on TLA, white papers on Daedalus, and the Eve live demo, but from the little I've seen it's not yet obvious to me how they solve my problems as a day-to-day jobbing programmer.
That's OK. I'm not trying to sell you this approach or make you an advocate for it. I just want people to stop equating FP with "math", as it is certainly not the only "mathematical" approach to programming, nor make claims about its universal superiority.
> The benefits of Haskell, on the other hand, became clear to me after browsing the Haskell Reddit and noticing that pretty much every post solved a problem I was currently having in my Python codebase.
That's great! Haskell works great for some people in some cases, and may not be the best for everyone in every case. You can still advocate for Haskell and tell people how elegant you find the approach and how well it solved your problems. Just don't make universal claims that can't be backed up.
> Does the model you're describing really handle polymorphism and higher order functions?
Polymorphism and higher-order functions are not concepts in computation; they're concepts in functional programming. A model where computations are not represented as functions, obviously has other means of expressing things. For example, dynamical systems are normally expressed using first-order ODEs only, but they can still express any system, even one where the derivative is itself a dynamical process, and so you'd think is a "higher order" system. When you have forms of composition other than function composition, your objects are just different.
Having said that, TLA+ has polymorphism and higher-order functions (only that's not how you represent computation).
> Given that polymorphism and higher order functions are known to be incompatible with set theoretic models I remain sceptical.
I assume you referring to TLA+, which uses set theory as the "data logic". When people say that polymorphism doesn't have a set-theoretic model, they mean that a polymorphic function, say `id :: a -> a`, cannot correspond to a set theoretic function. That doesn't mean it cannot be represented as something else. But, as you're talking about set theory, and so, I assume, referring to formal methods like TLA+, I have to say that I'm not sure at all what the status of polymorphism is in type-theory based proof assistants, which, like TLA+ but unlike Haskell, must be consistent. For example, in Lean, the id "function is:
universe u
def id {α : Sort u} (x : α) := x
BTW, if you want to write something similar to the above Lean definition in TLA+, you'd write:
Id(u) ≜ [x ∈ u ↦ x]
Id(x) = x
> Of course there is (synchronous programming)
So you say! And I'm keeping an open mind on it but I still don't grasp what it's useful for in the life of a day-to-day jobbing programmer like myself.
> Polymorphism and higher-order functions are not concepts in computation
Let's leave polymorphism to one side for a moment, but higher-order "programming"/"computation"/whatever is definitely a concept that's more widely applicable than just in functional programming. Any time you "manipulate a computation" you are doing "higher-order" computation. The universal Turing machine is an example of "higher-order" computation and the proof of the halting lemma requires "higher-order" computation.
Now it's possible that the models you are describing do not allow you to abstract over computation and thus are not "higher-order". If that's the case then either they are weaker than needed to talk about computation in general or they are very remarkable demonstrations that higher-order computation is generally not needed in practice!
Ah, this is something I specifically address in my TLA+ post series, probably because I heard it come up from you and others. Higher-order is strictly a formal property, i.e., it is a quality of a description of a system, not of a system itself. The best example is from continuous dynamical system. If the derivative of a system is a dynamical system itself, using one formalization you get a higher-order ODE. But people usually prefer describing all dynamical systems using first-order ODEs. The system of equations is first-order, but it still describes a "system that modifies a system". How? Because the "higher-order" function composition can be expressed as first-order composition of a different kind. Instead of writing:
x'' = 2
x' = y ∧ y' = 2
You don't even have to take my word about TLA. Robin Milner, who was one of the leading advocates and theoreticians of functional programming, moved in the eighties from the lambda calculus to process calculi. He still insisted on algebraic composition, but process calculi are "first-order" yet still equivalent to the lambda calculus. Instead of a function taking a function, you have two processes composed in parallel.
> Now it's possible that the models you are describing do not allow you to abstract over computation and thus are not "higher-order". If that's the case then either they are weaker than needed to talk about computation in general or they are very remarkable demonstrations that higher-order computation is generally not needed in practice!
Not only do they allow to abstract over computation, they organize all computations into a lattice. I.e. if computation b is an abstraction of a (or a is a refinement of b), then a ≤ b in the lattice. So instead of saying that b is a parameterized computation, and that there exists some x s.t. a = b(x), we have that nice order relation; order and nondeterminism are used instead of parameterization. In fact, in TLA this is even used for first-order computations. Instead of saying that F is a computation parameterized by some natural number parameter, we say that F has a "degree of nondeterminism freedom" of a dimension of natural numbers.
That's one of the greatest strengths of such formalisms, as this greatly simplifies formal verification (and one of the reasons why synchronous languages are the languages most amenable so far to formal verification).
This is an example of a computation that is specifically tailored for functional languages, so let's instead start with something conceptually simpler for TLA, but downright impossible in FP: Plotkin's parallel or. Here you have a computation that takes two arbitrary computations, and simulates them in lockstep. [1]
Doing what you ask is certainly possible in TLA (in part 4), but that's just not how it's normally done. TLA allows you to abstract computations, i.e., extract some of their arbitrary features. As sequential computations of the kind you describe can correspond to functions and can be abstracted into function, that's exactly what you'll do in TLA+. You won't say "my computation runs an arbitrary computation over all elements of a list" (as is possible for Plotkin's or) because in order for that to make sense, that other computation must have certain features and cannot be arbitrary. In particular, it needs to behave like a function. So, what you'll write is a computation that runs something that can be represented as a function over all elements of a list. So, it will simply be:
CONSTANTS T, R (* the "type" of elements in the in/out list *)
VARIABLES in, out, f
Map ≜ ∧ in ∈ Seq(T)
∧ f ∈ [T → R]
∧ □[∧ out' = Append(out, f[Head(in)])
∧ in' = Tail(in)
∧ UNCHANGED f]_⟨f, in, out⟩
Of course, this computation is then abstracted (for use by others) simply into:
Map(list, f) ≜ [i ∈ DOMAIN list ↦ f[list[i]]]
CONSTANTS T, R
map[list ∈ Seq(T), f ∈ [T → R]] ≜ [i ∈ DOMAIN list ↦ f[list[i]]]
In any event, f here is a function, not a computation. If for some reason you want to actually use a computation, you would need to specify more precisely what your expectations are of that computation (e.g., that it can take an argument at all). But, again, that's not how it's normally done in TLA+.
[1]: See here https://pron.github.io/posts/tlaplus_part3#plotkins-parallel... or here https://www.youtube.com/watch?v=15uy9Ga-14I
Yes, absolutely I want to use a computation! The point is that I want to understand how TLA+ can abstract over computations.
Doing a "map" of a completely arbitrary computation f, would look like this:
CONSTANTS T (* the "type" of elements in the in/out list *)
VARIABLES in, out, f_param, f_result, f_done
Map ≜ ∧ in ∈ Seq(T)
∧ f_param = Head(in)
∧ □[∧ f_done = TRUE ∧ f_done' = FALSE (* wait for f to work *)
∧ out' = Append(out, f_result])
∧ f_param' = Head(in) (* send another element to f *)
∧ in' = Tail(in)
∧ UNCHANGED f_result
]_⟨f_param, in, out⟩ (* we don't allow f to change f_param, in or out *)
Map ∧ f
f ⇒ □(f_done = FALSE ↝ f_done = TRUE)
This is similar to how ODEs and processes in process calculi are composed, and all of this can be abstracted nicely into a "subroutine call" operator as I do in part 4. It is more cumbersome than sequential formalisms as composition is parallel "by default", but the technique is never used in practice precisely because of the Boolean algebra of computation that allows you to abstract appropriate computations as functions.
[1]: This is the exact spot in the video: https://youtu.be/15uy9Ga-14I?t=37m34s
Also, I've given it some more thought, and I think that my original (slightly corrected) answer is actually the better way (even when dealing with computation), and I'll explain why below:
CONSTANTS T, R (* the "type" of elements in the in/out list *)
VARIABLES in, out, f
Map ≜ ∧ in ∈ Seq(T)
∧ f ∈ [T → R]
∧ □[∧ Len(in) > 0
∧ out' = Append(out, f[Head(in)])
∧ in' = Tail(in)
∧ UNCHANGED f]_⟨f, in, out⟩
Map can then be composed with another computation that implements the mapping, and, if you watch the talk you'll see that the other computation may take as many steps as it likes due to stuttering invariance. The f function merely encodes our assumption about the mapping computation's behavior, namely that it always yields the same output to the same input. Without this assumption, the specification will simply look like:
CONSTANTS T, R (* the "type" of elements in the in/out list *)
VARIABLES in, out
Map ≜ ∧ in ∈ Seq(T)
∧ □[∧ Len(in) > 0 (* sorry, forgot this before; must stop when the list is empty *)
∧ out' = ∃ y ∈ R : Append(out, y) (* completely nondeterministic in R *)
∧ in' = Tail(in)]_⟨f, in, out⟩
I may add this with the explanation to the posts.
With respect to TLA+, here's how I'd say it solves problem as a day-to-day jobbing programmer: you know the saying "Weeks of programming can save you hours of planning?" TLA+ is a tool to make planning less tedious and error prone. You can write your plan as a specification, then check if that specification actually meets your required invariants.
If you're expecting to write a couple dozen lines of code, TLA+ is probably not gonna help a lot. If you're expecting to write a couple thousand lines of code, it can save you a ton of pain. But you still have to implement your specification correctly, and that's where things like ADTs can help quite a lot.
The operational semantics are certainly not isomorphic. fac1 consumes stack, for example, and fac2 doesn't.
Why? Intuitively, wouldn't you consider Euclid's algorithm operating on unary and binary representations of numbers isomorphic despite the exponential difference in complexity? We can have complexity preserving isomorphisms and non-preserving isomorphisms, and it's quite easy to see from the mappings which is which. That's exactly why, if you're writing a reduction to prove complexity bounds, you must show that the reduction itself is polynomial. Otherwise, you get a mapping, but not one that preserves complexity.
> What is your notion of "isomorphism" here?
The usual one: bisimulation [1] (the operational semantics of the lambda calculus is just a state machine, where the current expression is the state, and the reductions are transitions), or refinement mappings in both directions, if you like, as in my talk.
Also, you can clearly see in my Java examples how the imperative denotation is preserved in all versions of the program.
> Why?
Because the operational semantics is very specifically intended to capture how the program executes as a sequence of state changes happening over time, typically with reference to some stack and heap. It is the denotational semantics whose notion of meaning is what the program calculates, i.e. the "end result of the computation".
> We can have complexity preserving isomorphisms and non-preserving isomorphisms, and it's quite easy to see from the mappings which is which.
Those can't be isomorphisms of operational semantics because part of operational semantics is the complexity. How else would you define complexity other than by reference to operational semantics? Any "isomorphism" of operational semantics by definition preserves the complexity.
> Wouldn't you intuitively consider Euclid's algorithm operating on unary and binary representations of numbers isomorphic
No, not at all. In fact let's make it simpler: I wouldn't even consider addition of unary integers to be operationally isomorphic to addition of binary integers. Denotationally they're the same, of course.
(There's a more subtle point which I think you're not making but I'll mention it all the same: yes, I consider the "Euclid's algorithm" part of "Euclid's algorithm operating on unary integers" to be the same as the "Euclid's algorithm" part of "Euclid's algorithm operating on binary integers".)
> > What is your notion of "isomorphism" here?
> The usual one: bisimulation (or a refinement mapping in both directions, if you like).
I'm not especially familiar with the notion of bisimulation but if you can demonstrate that the addition of unary integers is bisimilar to the addition of binary integers then I would be very interested!
First, operational semantics is usually a state machine (e.g., in the case of lambda calculus, the current expression is the state and the reductions are transitions). Second, there is no a-priori requirement that mapping the states of two state machines preserve complexity. You can add this restriction if you want to show they have the same complexity (as in polynomial reduction when showing membership of complexity classes), but that's an additional constraint.
> It is the denotational semantics whose notion of meaning is the "end result of the computation".
No. That's just the functional denotational semantics (i.e., the matehmatical meaning of a program is a so-called "partial function", which resembles a function). Imperative programs can have a Hoare-logic denotation (which I used in my Java example). TLA has a behavior denotation (the mathematical meaning of a program is a set of its possible behaviors, where a behavior is an infinite sequence of states, where a "terminating" computation is defined to be one where some state is reached in a finite number of steps, and then "stutters" forever). A language such as Eve can use a denotation where every block is a relation on the current and next state, and the entire program is such a relation, made by intersecting all blocks.
> No, not at all. In fact let's make it simpler: I wouldn't even consider addition of unary integers to be operationally isomorphic to addition of binary integers.
Well, in program analysis, the ordinary (homo/iso)morphism between programs is the (bi)simulation relation, and in this case the two are isomorphic.
> Denotationally they're the same, of course.
No, again, this depends on what your denotation is. In Haskell, for example, even two instances of Euclid's algorithm using a binary representation may not be denotationally equivalent, as in my example, but in TLA, for example, they would be.
> yes, I consider the "Euclid's algorithm" part of "Euclid's algorithm operating on unary integers" to be the same as the "Euclid's algorithm" part of "Euclid's algorithm operating on binary integers"
Ah, and the simulation relation (or the much nicer refinement relation in TLA) precisely and mathematically captures the notion of what it means for two programs to implement the same algorithm. In TLA, A => S and B => S iff A and B implement the same algorithm S. I.e., in TLA, you have a very simple and precise operator that defines the notion of abstraction.
> I'm not especially familiar with the notion of bisimulation but if you can demonstrate that the addition of unary integers is bisimilar to the addition of binary integers then I would be very interested!
Picture a graph where each node is the state of the computation, and the edges signify transitions. If you want to think in terms of LC, the state can be some lambda expression, and the transitions are reductions. In the case of deterministic programs with a fixed input (let's say that we're only considering the computation of factorial(5)), it's a linear graph. There is a subtlety here, as the lambda calculus does not specify a reduction order and so creates a non-linear graph, with different paths representing different reduction orders. But normally, programming languages come with an evaluation strategy, a state machine, that accompanies the LC (by-name for Haskell, by-value for ML).
BTW, if we label each node with the set of all atomic propositions that are true in that state, we get what is known as the Kripke structure of the program, which is the canonical program representation in all of program analysis.
A simulation relation is a relation from program A to program B that maps states to states and transitions to transitions, such that for every transition that A makes, B can match it with a mapped transition that leads to a mapped state. If the relation is invertible, we say that it's a bisimulation, and it forms an isomorphism on programs. You can see that whether you label the states with a number in unary or in binary, the graph is the same, so clearly an invertible relation exists.
See Wikipedia for a more precise treatment: https://en.wikipedia.org/wiki/Bisimulation
If you want, you can place further restrictions on the mapping, such as bounding its complexity to show tighter similarity. Here I show how you can describe an actual lattice relating programs to one another: https://pron.github.io/posts/tlaplus_part4#equivalence-abstr... The following section (which does not require any previous knowledge of TLA), specifically discusses (bi)simulation: https://pron.github.io/posts/tlaplus_part4#other-notions-of-...
Even more puzzling to me is how you can consider unary addition to be isomorphic to binary addition. I am no bisimulation expert but unary addition involves a single state change whilst binary addition requires many.
I will have to drop out of the debate, yet again, with the feeling we are living in completely different worlds.
Oh, I think that ship sailed long ago. This started as a discussion on Kotlin. :)
> The point is that fac1 and fac2 do two completely different things when executed on a computer.
But they don't. You must define some equivalence relation to determine whether executions are "completely different". You could go very concretely, all the way down to memory addresses or even to logic gates in the CPU, but then the very same Haskell program may be considered to be completely different from itself when compiled by different compiler versions. So, when working with powerful systems like TLA, you get to decide how fine-grained your equivalence is, but when talking about programs and languages, you go by the semantics of the language and use (bi)simulation, as it's the homo/isomorphism normally used in programming language theory (it was first proposed, I believe, by Robin Milner). Such an isomorphism exists between the things those programs do in the computer.
> Even more puzzling to me is how you can consider unary addition to be isomorphic to binary addition. I am no bisimulation expert but unary addition involves a single state change whilst binary addition requires many.
Because you are allowed to map a single state in one graph to multiple ones in the other. That's the difference between a function and a relation.
> I will have to drop out of the debate, yet again, with the feeling we are living in completely different worlds.
Well, all I can say is that this particular branch of the discussion began when I pointed out that the functional denotation is one particular choice, made to obtain certain tradeoffs, while others, with other tradeoffs, exist. If by your world you mean the world when you only consider the theory of functional programming, then indeed there's no point discussing it within the broader context of programming language theory/program analysis. Afer all, the theory of functional programming is a strict subset of programming language theory. I don't know how to compare FP to itself, nor do I know how to compare the mathematics of FP to some imprecise notion of imperative programming. I can try to compare the mathematics of FP to the mathematics of imperative.
Functional programmers care about all sorts of semantics, including operational and denotational semantics. I see no reason the sorts of analysis you give in your Java examples couldn't equally be applied to functional programs not least because functional programs can be trivially rewritten as imperative ones (see CBPV).
Oh, but that's because FP fans call it "referential transparency"; I'm sure you've come across that term. While the terminology is incorrect (for one, Java is also referentially transparent), when FP fans say "referential transparency", they mean "value semantics", i.e., that the meaning of a function application is its normal form, or, in other words, they simply mean "functional denotation". This is exactly what enables the equational reasoning FP fans like to talk about.
> I see no reason the sorts of analysis you give in your Java examples couldn't equally be applied to functional programs
They could (I know it's possible to write assertions in Haskell), but then they no longer operate on the denotation of the language. You can also use unsafePerformIO in Haskell, but if you do that, you may break the mental model the language aims to create.
> not least because functional programs can be trivially rewritten as imperative ones (see CBPV).
Again, they could, but not in a way that preserves the benefits for which the formalism was designed for. Similarly, pure functional programs could be written in Java, but that's not the idiomatic way.
To take us back to where we started, we are talking about language design, and while many languages can imitate the style of others, they are optimized for certain pragmatic and aesthetic concerns. That is my whole point.
If that were your whole point we could have avoided this thread. No one disputes that.
In fact your point seems to be that Java/imperative languages are better than Haskell/functional languages, for a reason that you have tried to elaborate and that I have failed to understand.
Not at all. My point is that the reason for preferring a formalism is largely aesthetic and pragmatic, and almost never mathematical or universal. Indeed, one pragmatic reason to prefer classical imperative programming is that in many cases, it makes formal reasoning easier, something that comes as a surprise to those familiar with the math of FP but not of imperative (you don't have to take my word for it; here are Xavier Leroy and Simon Peyton Jones saying that: http://homepages.inf.ed.ac.uk/stg/Milner2012/Monday_Panel-ht...).
But if you knew me you'd know that I don't care much for programming languages at all, partly because personally I don't feel much of a difference and partly because the empirical evidence so far show that there is little if any practical difference between them (at least modern ones). So I resist any attempt (by lmm this time) to claim that functional languages are "better designed" because of one or other of their properties. They are not, but they may be languages that lmm or you find aesthetically appealing, and more productive because they match how you like to think about programs.
I'm skeptical of all languages, but I am at least hopeful of languages that haven't yet had the chance of proving themselves, which is why I'm curious about Eve, the most theoretically-advanced language that I know of, and one whose semantics I personally find appealing (actually, some of the ideas behind Eve have proven themselves quite spectacularly in realtime, which is why I'm even more hopeful).
The group’s pretty quiet at the moment whilst we’re building up the community but stick with us as we’re aiming to grow it rapidly.
https://publicslack.com/slacks/https-venturisvoice-slack-com...
for {
a <- list1
b <- list2
} { do something}
for {
a <- whatever1
b <- whatever2
} yield { ... }
https://en.wikipedia.org/wiki/Set-builder_notation#Sets_defi...
Erlang [1]:
[X || X <- [1,2,a,3,4,b,5,6], X > 3].
Pythagorean triplets
[ {A,B,C} ||
A <- lists:seq(1,N),
B <- lists:seq(1,N),
C <- lists:seq(1,N),
A+B+C =< N,
A*A+B*B == C*C
].
Yeah, I think that was a huge mistake, because the most common case is one-level and if you have one level the syntax is just the reverse of a regular for, but in a two-level comprehension (the rare case) you have to remember that it's not a reversal, it's a cyclic permutation.
i.e. most of the examples you see look like this, and these two are equivalent:
[y for i in x]
for i in x: y
[z for j in y for i in x]
for i in x: for j in y: z
for j in y: for i in x: z
You do not need monads everywhere. Once you have a hammer, every problem looks like a nail. Monads are as ad hoc as any other solution listed there: that is, not ad hoc at all. These are all choices made by designers of the language. A generalized solution (shoving monads everywhere) may as well be much worse than a specific solution to a specific problem.
BTW. List comprehensions are amazing as long as they are not written with Pythonic syntax, but that's a minor complaint.
Clearly they're not ad-hoc, since they can be used for all of those examples and more, whereas each of the ad-hoc solutions has to be implemented separately as a language-level feature.
> A generalized solution (shoving monads everywhere) may as well be much worse than a specific solution to a specific problem.
I think this is true in the small. Of course a dedicated syntax like async/await is going to be better suited to that specific problem than reusing a general-purpose solution like do notation. But once you're working on a larger codebase, being able to support new effects in a plain old library rather than having to have them built into the language by the language maintainer (or, worse, hacked-in by bytecode manipulation configured through annotations or something), and being able to generalise over multiple different effects or different representations of the same effect, is much more important.
(I do hold out hope that it's possible to get the best of both worlds by having dedicated syntax but only as lightweight sugar over the general-purpose syntax)
I won't hold my breath waiting for large projects coming out of Haskell.
If anything, boring and ad-hoc seem to win in the "large codebase" space. It's enough to look at all the projects that have come out (and keep coming out) of Java, and at the projects that are now coming out of Go and Rust. And then at the barren wasteland that is Haskell (or other languages so proud of their monads).
> they can be used for all of those examples and more
There's a probably a reason hardly anyone uses them as a language-level feature.
Well, boring languages will always win if you're counting lines, because they use a lot more lines to do the same thing. I work on a large Scala project and have worked on others before; these are real projects that produce a lot of business value, and would have been a lot more difficult or even impossible without those language features.
Nope. Never did I say or imply "number of lines".
But let's talk about the number of lines then. It looks like "boring languages" are quite happy without monads even though "once you're working on a larger codebase, being able to support new effects... and being able to generalise... is much more important." Seems to me, this statement must be supported by data.
Meanwhile let's talk about large projects. You know, the Hadoops, and the Cassandras, and the Kafkas, and the ActiveMQs, and the Tinkerpops, and the Mesoses, and the Nettys, and the Kuberneteses, and the Dockers, and the <insert dozens of other names here> of this world.
They are all developed and have taken over the world without monads at language level. Either they are small projects (they aren't) or the need to shove monads everywhere is highly exaggerated. Because I've yet to see an abundance of projects of the same calibre from the Haskell (and friends) world.
Kafka is written in Scala. That aside, I'm not convinced those are such large projects. How much logic do they need? People build large projects on top of them - I've done so - but where's the complexity in the components themselves?
Who cares about metaphors explaining the nature of a Monad, or type theory yadda yadda. This article shows precisely the problem Monads solves for real world programmers. Very few other Monad tutorials do this, and none as well as this article.
Well done and much thanks to the author!
override def covariantInstance[C]: Applicative[C =>: ?] =
new Applicative[C =>: ?] with SndCovariant[C] {
def point[A](a: => A): C =>: A = arr(_ => a)
def ap[A, B](fa: => (C =>: A))(f: => (C =>: (A => B))): (C =>: B) = <<<(arr((y: (A => B, A)) => y._1(y._2)), combine(f, fa))
}
class applicativeCovariantInstanceStringString<C>: Applicative<EqualsGreaterThanColon<C, String, String>> {
fun point(a: () => String): EqualsGreaterThanColon<C, String> = arr(_ => a())
fun ap(fa: () => EqualsGreaterThanColon<C, String>))(f: () => EqualsGreaterThanColon<C, String => String>): EqualsGreaterThanColon<C, String> = LessThanLessThanLessThan(arr((y: Pair<String => String, String>) => y.first(y.second)), combine(f, fa))
}
class applicativeCovariantInstanceStringInt<C>: Applicative<EqualsGreaterThanColon<C, String, Int>> {
fun point(a: () => String): EqualsGreaterThanColon<C, String> = arr(_ => a())
fun ap(fa: () => EqualsGreaterThanColon<C, String>))(f: () => EqualsGreaterThanColon<C, String => Int>): EqualsGreaterThanColon<C, Int> = LessThanLessThanLessThan(arr((y: Pair<String => Int, String>) => y.first(y.second)), combine(f, fa))
}
class applicativeCovariantInstanceStringFloat<C>: Applicative<EqualsGreaterThanColon<C, String, Float>> {
fun point(a: () => String): EqualsGreaterThanColon<C, String> = arr(_ => a())
fun ap(fa: () => EqualsGreaterThanColon<C, String>))(f: () => EqualsGreaterThanColon<C, String => Float>): EqualsGreaterThanColon<C, Float> = LessThanLessThanLessThan(arr((y: Pair<String => Float, String>) => y.first(y.second)), combine(f, fa))
}
class applicativeCovariantInstanceIntString<C>: Applicative<EqualsGreaterThanColon<C, Int, String>> {
fun point(a: () => Int): EqualsGreaterThanColon<C, Int> = arr(_ => a())
fun ap(fa: () => EqualsGreaterThanColon<C, Int>))(f: () => EqualsGreaterThanColon<C, Int => String>): EqualsGreaterThanColon<C, String> = LessThanLessThanLessThan(arr((y: Pair<Int => String, Int>) => y.first(y.second)), combine(f, fa))
}
// and so on for all other pairs of types
Part of designing a good abstraction is the interface communicating usage and intent, which should be tailored to the problem domain and the audience.
1. Just because a while loop subsumes the functionality of a for loop doesn't make the for loop useless. 2. Algebraic data types are technically subsumed by inheritance and predicate dispatch [1]. That doesn't make ADTs useless, because often you don't want to lug the extra baggage of the more powerful model around with you, especially for simple use cases.
The other problem is that "more general" is in the eye of the beholder. For example, to a Smalltalk programmer, most use cases for monads look pretty primitive, as they're limited to user-defined control flow on a sequence of operations, nothing more complicated; they'd be implemented in Smalltalk as operations on arrays of blocks. Keep in mind that Smalltalk doesn't even have if statements in the language proper: `ifTrue:` and friends are methods of the Boolean class. Similar things apply to other control structures, such as `whileTrue:`, not to mention that plenty of data types offer their own control structures. And the continuation monad in the article looks a lot less impressive compared to Seaside [2], one of the original continuation-based webservers. (I'll also add that the reason for `.then(..)` or `async/await` is often that the underlying languages do not support continuations, not that they model the non-existent continuations imperfectly.)
[1] See "Predicate Dispatch: A Unified Theory of Dispatch" by Michael Ernst, Craig Kaplan, and Craig Chambers, https://homes.cs.washington.edu/~mernst/pubs/dispatching-eco...
I think here you're assuming that a feature that allows more possibilities to be expressed subsumes one that doesn't, and I would disagree; being able to clearly restrict the possibilities is important too. As an exaggerated example, replacing all the language builtins with a single builtin that took a parameter to say which builtin it was wouldn't be an improvement. (At the same time being able to talk about different builtins in a uniform way - e.g. being able to use a builtin function as a value - is a useful generalisation - I see monads as more like this).
> to a Smalltalk programmer, most use cases for monads look pretty primitive, as they're limited to user-defined control flow on a sequence of operations, nothing more complicated; they'd be implemented in Smalltalk as operations on arrays of blocks.
The Free monad is essentially that (it's a type-aligned sequence of things that look like Kleisli arrows, which is pretty much the type-safe equivalent of an array of blocks), and it's well-known that you can emulate any monad that way (specific concrete monadic types are nice to have as well though, for the cases where you do want to talk about that specific type). If you're saying that monads are something banal rather than something complex and impressive then I completely agree.
> Keep in mind that Smalltalk doesn't even have if statements in the language proper: `ifTrue:` and friends are methods of the Boolean class. Similar things apply to other control structures, such as `whileTrue:`, not to mention that plenty of data types offer their own control structures.
Sure - this is how control flow tends to work in monad-oriented languages too, with constructs like ifM . I don't see a conflict between this style and what I see as the good aspects of Smalltalk at all; rather I see this style as a way to get those aspects while having type safety as well.
The point here is not that Smalltalk is better or worse; the point is that Smalltalk's approach can be seen as more general. In other words, it's a matter of perspective as to what is considered to be a sufficient amount of generality.
Types are orthogonal to that (see Strongtalk).
Edit: To clarify something:
> The Free monad is essentially that (it's a type-aligned sequence of things that look like Kleisli arrows, which is pretty much the type-safe equivalent of an array of blocks), and it's well-known that you can emulate any monad that way (specific concrete monadic types are nice to have as well though, for the cases where you do want to talk about that specific type). If you're saying that monads are something banal rather than something complex and impressive then I completely agree.
Partly that (I've said before that I much prefer the F# terminology of "computation expressions" to get the purpose across), but my larger point is that this would be considered to be a very specific and limited application to a Smalltalk programmer. Again, it's not about Smalltalk being better or worse, it's about "can be generalized" as a matter of perspective.
How so? What's the generality that's missing here? Again, completely permissive doesn't necessarily mean more general.
> Partly that (I've said before that I much prefer the F# terminology of "computation expressions" to get the purpose across), but my larger point is that this would be considered to be a very specific and limited application to a Smalltalk programmer.
Sure; again, this is true from the functional/monad-oriented perspective too. Monads are a synecdoche because they happen to come up quite often, but they're really just one reusable construction among many, and certainly admit a couple of useful generalisations.
Monads – or rather, what Haskell and Scala use monads for, to distinguish that from the category theory concept – are primarily about "enriched" function composition (yes, I know that I'm simplifying here). That is useful, but also very limiting when the logic with which you want to glue pieces of code together does not fit that schema. A lot of the usefulness of monads also depends on the language supporting the syntactic sugar ("do" in Haskell or "for" in Scala) to make the resulting code readable.
> Monads are a synecdoche because they happen to come up quite often, but they're really just one reusable construction among many, and certainly admit a couple of useful generalisations.
I'd argue that monads are an artifact of pure functional programming (or attempts to approximate pure functional programming in impure languages). As soon as you have mutable local state and closures, virtually all use cases of monads for programming (not counting actual category theory applications) disappear.
Note that I'm saying mutable local state. The arguments against mutable global state do not really apply to local state.
Thus, for those other languages, most of the practical need for monads disappears and monads really become a more limited way of expressing higher-order program logic.
What kind of logic might that be? You keep saying there's a generalisation but you keep not showing what it actually is.
> A lot of the usefulness of monads also depends on the language supporting the syntactic sugar ("do" in Haskell or "for" in Scala) to make the resulting code readable.
Up to a point. I've done some work with (free) applicatives lately, which have no direct language support, but it turns out you can get a lot of the value anyway.
> I'd argue that monads are an artifact of pure functional programming (or attempts to approximate pure functional programming in impure languages). As soon as you have mutable local state and closures, virtually all use cases of monads for programming (not counting actual category theory applications) disappear.
I find them useful for any kind of cross-cutting concern - all the AOP examples. Audit logs, database transactions, validation, authorization, that kind of thing. To solve these things with something state-like that state has to be pseudo-global and has most of the problems of global state; to solve them with closures you need a way to compose closures at which point you're most of the way to monads.
The group’s pretty quiet at the moment whilst we’re building up the community but stick with us as we’re aiming to grow it rapidly.
https://publicslack.com/slacks/https-venturisvoice-slack-com...
For JS, you can use all you favorite front-end frameworks like react (here's an example by JetBrains themselves https://github.com/Kotlin/kotlin-fullstack-sample) or cycle. And you can import typescript definitions.
Also first class IDE integration.
So yeah, bright future is an understatement.
I guess clojure/clojurescript and scala.js are somewhat similar however I feel like Kotlin has an insane amount of momentum behind it right now.
With Kotlin you'll be running compiled code. If you wanted to right now though, you could (should be able to?) use Kotlin to build a React Native app with it's just target.
[1] https://blog.jetbrains.com/kotlin/2017/04/use-kotlin-with-np...
C/C++ can do that if you accept Emscripten.
Java can do that if you accept GWT.
Though I think what really sets it apart (on the web side) is that it interops pretty well with other js libs.
I think what sets it apart is the interopability with it's current targets. Really slick
Edit:fixed typo
Yeah, pls no.
> Java can do that if you accept GWT.
Yeah, I don't. Google abandoned it, you should too.
The JNV / JS / Native targets are also really promising, though I haven't played around with them much. The JS and Native runtimes are a bit limited since they don't include the Java standard library, from what I can tell.
I think that they ship with the Kotlin standard library which is close enough.
> various lisps have been doing it for decades
There's an insanely long road from having a prototype of a language to having a production ready thing. There isn't a lisp where I could achieve the same experience.
It isnt a mature enough language to be trusted so soon, no body has a sufficient enough industry grade experience with it. Especially with large code bases.
I mean, Google adopted it as a first class citizen language on android which counts for something.
> no body has a sufficient enough industry grade experience with it. Especially with large code bases.
There aren't really any "new" features in Kotlin, as in features you haven't seen before. If you've been programming Java and know some Haskell/Ocaml or idk what else, you are good to go.
Something but not much. It works on JVM, talk to all Java libs and tooling is taken care by Intellij. It is low or little effort from Google to support. Unlike other language fans who clamor for Android support from Google, here hard work is done by someone else. So Google support looks most like a co-branding deal.
Don't get me wrong, I like Kotlin, but Ceylon did the multi platform thing much better.
They have real platform modules, built into the language (not just a build tool trick), and a language specification that was written from the start with multiple platforms in mind.
But it never took off (yet), and Kotlin's support is good enough, so it will have to do I guess :).
Lisps have been doing this since forever (including the now defunct LinJ for Java which compiled into code that was very often mistaken for hand-written Java).
Hell, Emscripten takes everything LLVMable and gives it that ability.
> This is unprecedented.
Only for sufficiently narrow "this".
I like kotlin for several reasons but this one isn't on the top of my list. If you like cross-platform development, you might want to check out haxe.
The group’s pretty quiet at the moment whilst we’re building up the community but stick with us as we’re aiming to grow it rapidly.
https://publicslack.com/slacks/https-venturisvoice-slack-com...
At its peak, Eclipse released Xtend. At that point, Eclipse was the IntelliJ of today, everyone assumed Xtend would be the next Java with full support of Eclipse tooling. Today, well, anyone remembers it? But its still there, check the features: http://www.eclipse.org/xtend/documentation/index.html.
You will see thousands of articles on kotlin vs java, but only a handful on kotlin vs xtend, because of the cycle.
Groovy. Same cycle, same result.
Javascript has a large share of syntactic forks. All of them had this hype-cycle. Coffeescript was "de-facto way" to write cross-browser eloquent javascript at one point.
There are few lessons from history: Syntactic language forks are what they are - forks. It takes equal amount of tooling and expertise to maintain them. When the next two versions of Java releases, the hype cycle will again turn tides. "X is the better Y", "Groovy is the better Java" - never, there is only one Java, there is no better Java.
The best approach is to make the language itself extensible. Look at ES-next and babel. Every language addition is a proposal, and proposals can be implemented as language plugins with stages 3/2/1/0. This effectively rendered most syntactic forks almost meaningless and unnecessary. Have an idea? Extend to the language directly! The most important part - tooling - which is eslint, AST parsing, intermediate representations, code formatting, etc - have been shifted to work on top of language plugins. Now some of you will talk against babel, and how different projects use different babel settings - but given all the history, babel is the best way to pragmatically evolve a language we've ever had so far.
Java has a longer mature JSR and language proposal process, just like ES. I really regret that Jetbrains decided to create yet another language fork, while being in the position to create the next babel for java.
Will Kotlin be different from all the previous cycles? Only real 2020 will tell, but until then, the only reference available is history.
Even the article quote something around those lines: “The syntax for Kotlin, like Apple’s Swift, is clean and modern. The reaction amongst developers learning Kotlin is not dissimilar to the initial experiences with Ruby years ago. The syntax is so intuitively designed that even without any previous exposure it’s almost possible to guess it.”
The question would be: Am I missing something? Is syntax the only reason that makes people excited about it? or are there any new abstractions/ideas that are exclusive for Kotlin?
But that's just one example and a subjective one at that. Not everyone will feel the same way and for those who don't there's no compelling reason to 'start using Kotlin' - if what you have works then stick with it.
There's also Kotlin native and Kotlin JS - allowing Kotlin code to be compiled to native binaries as well as to javascript is pretty compelling and will (imo) pay dividends. Both are still very much in development though.
Beyond that, it's nothing that you couldn't cobble together without the standard Guava + Commons + Lombok + Quasar/EASync etc. libraries and plugins that you'd use on every project written in Java, as well as that terseness you mentioned that makes people excited (see Kotlin data classes [1] vs Lombok data classes [2], if/try returns values and destructuring [5], coroutine support for lightweight threading and generators [6], null safety w/o optionals and smart casting, etc. [7]).
In my opinion, it's hard to know what value those features provide without actually trying them out yourself. If you want to be certain that you're not missing something, I'd suggest writing up a little script to try out some of its features.
edit: Just noticed the other responses on this thread. It's also very useful for starting fights with Scala developers, apparently.
[1]: https://kotlinlang.org/docs/reference/data-classes.html
[2]: https://projectlombok.org/features/Data
[3]: https://kotlinlang.org/docs/tutorials/javascript/kotlin-to-j...
[4]: https://kotlinlang.org/docs/reference/native-overview.html
[5]: https://kotlinlang.org/docs/reference/control-flow.html
That with combination of precise refactorings, unlike in case or ruby. And without unnecessary complexity of scala.
Programming languages are basically nothing but syntactic sugar over machine code.
Really excited to see how Native progresses as well. I've got a handful of projects what would benefit from having the 90% core written in Kotlin with some JVM and Native portions plugged in, ultimately meaning the library is available on both JVM and Native.
A language isn't a "real" language unless you can live in it and be blissfully ignorant of anything else. I don't need to know C in order to use Go, or Python. I don't need to know Ruby in order to use JavaScript. But it'll be relatively impossible to write code in Kotlin without interacting with Java constantly. Which means context switching and maybe even bugs.
For web services I use Sparkjava but I'm thinking of moving to Javalin or http4k because Sparkjava has really slow release cycles.
JSON is either Gson or Jackson. I prefer Jackson just because I know it better but they're both great.
I use JDBI for database work but I don't have too much of that in my backend right now. GRPC for cross service communication.
Back in 2015/2016 I used Vert.x a bunch but I really didn't like the async programming model. YMMV.
Generally I stick to using well known / common libraries written for Java and then later look for a Kotlin version if I have time to dick around a bit. I think this is what I love the most about Kotlin is the great interop with existing Java libraries.
All whilst avoiding adding clever/stupid things (cf. Scala, Go, Rust).
The group’s pretty quiet at the moment whilst we’re building up the community but stick with us as we’re aiming to grow it rapidly.
https://publicslack.com/slacks/https-venturisvoice-slack-com...
Scala was much better than Java but now the gap has closed and while its still nice to work with, I feel most applications would be better to stick to mainstream Java.
Kotlin is interesting but after Scala experience I'm reluctant to invest all over again. Is it worth it?
To answer your specific question, however, if you're doing Android development it's worth it :) otherwise, it's up to you/your specific situation.
[1]: https://kotlinlang.org/docs/reference/type-safe-builders.htm...
If you want to, Kotlin can be practically Java without the over-verbosity and some nice extra features. In time you'll be writing less Java-Kotlin and more Kotlin-Kotlin, if you get what I mean. To me the syntax and structure is so resembling to Java that I haven't really had any confusions at all, most of my gotta-read-the-docs moments involve the concepts that you can use that aren't present in Java (along with the `when` version of `switch` which I've grown to love).
Google made their Java fork, for Java 7 and 8 they only cherry picked features, even after migrating to OpenJDK.
The newly introduced bytecodes are not supported and the situation will only get worse with Java 9 and the new OpenJDK release schedule.
Specially given the lack of updates across the Android eco-system.
So only something like Kotlin allows to enjoy modern JVM languages while targeting Android.