> Classes as concept, are nothing more than extensible modules
If you're talking about ML-style modules, that really can't be farther from the truth, both in theory and how they're used in practice.
Modules can be used (among many other things) to implement abstract data types, which are conceptually a bit easier to compare to objects[0]. Then you'd have to go into structural vs nominal typing, functors vs generics, etc.
That's not entirely accurate. Abstract data types (e.g. ML modules) can also be modeled as existential types and don't have the same problems.
I think it's the particular combination of only having nominal typing, only allowing the oo-flavor of data abstraction, and encouraging programming with state and using inheritance for code reuse that leads to the object-spaghetti nonsense in heavily-oo Java/C++ codebases.
I just mean that (at least in Haskell) existential types provide information hiding & combine functions with data. In fact, they're implemented with dynamic dispatch, just as with OOP.
The problem is not that OO languages have these features; the problem is that they lack other features common to functional languages.
One big difference is that java interfaces can't contain member types. They describe the methods of one particular type. Imagine you could define an interface for an entire java package.
Another big one is that module types are structural: you don't have to declare all the module types implemented by a module when you define the module.
Actually, they're the "other side" of products types, which are sometimes called "records" or "structs". Maybe they're occasionally used to solve the same problem, but inheritance is unrelated. Inheritance is a variety of ad-hoc methods for sharing code with quite different semantics in every language where it's implemented.
In a way C++ is using higher-order functions conceptually too for polymorphic runtime dispatch. Because it uses vtables, which are lists of function pointers--essentially the object doing the dispatch is a HOF which calls one of the functions it has a pointer to.
All this is just made explicit, and the boilerplate OOP mechanisms stripped away, when you just directly pass first-class functions around.
I guess I just don't understand the connection between first class functions and multiple dispatch. I have a function "add()" that works differently for strings and numbers. How can I replicate that behavior with higher order functions?
The key idea is delegating the type-specific operations to specific implementations which handle them, and then statically (at compile time) choosing which specific implementation you're calling.
In OCaml (ReasonML) you have to pass in the implementations manually, but Haskell and Scala have the ability to automatically choose the implementation based on the types of the arguments, so that it looks dynamic even though it's static and type-safe.
This is a really annoying meme in "pop" FP. Equational reasoning isn't limited to "pure" languages. Effectful functions, as you probably are aware, are just functions of type A -> T B.
I haven't claimed that equational reasoning is limited to pure languages, that's more a property of the code, rather than the language. But you can only achieve equational reasoning with referential transparency and that means the code itself needs to be pure. TFA does not show pure code.
> Effectful functions, as you probably are aware, are just functions of type A -> T B
Not sure how to parse that. But if T in your example is meant to be some IO type, then it is pure along with any transformations on it, until you do unsafePerformIO or something equivalent and you only need to do that once, at the end of the program.
> I haven't claimed that equational reasoning is limited to pure languages
Sorry, I may have read that into your comment.
> the code itself needs to be pure
But that's also incorrect. Just because you can't replace an effectful computation with a value doesn't mean you can't reason equationally. You can also have benign effects that are unobservable, for example, memoization.
> Not sure how to parse that
I meant that functions with effects are just functions with computation type at the meta level. I.e. there's nothing more "mathematical" about only allowing nontermination in your language. It's just the simplest case.
Why is the complexity of parsing well-formed states from strings somehow interesting? If you generalize to trees and pick the right alphabet, suddenly every element of your datatype is a well-formed lambda term.
It's also unclear if you're talking about the complexity of type inference or type checking, what annotations you're allowing, etc. Your claims about complexity re: states of typed languages are too hand-wavy to engage with.
And yet there's still a glaring error: for a very popular machine model, namely the C abstract machine, it's undecidable whether a state is meaningful (regardless of how you set up your parsing problem).
So, you have an interesting idea about the difference between machine models and languages but it clearly doesn't hold together. People have been studying the relationship between machine models and languages for quite some time, and it's relatively well understood. Machine models are one of the many ways to give semantics to languages. They just don't have many useful properties compared to more "abstract" approaches, and are mostly used to reason about implementation.
> If you generalize to trees and pick the right alphabet, suddenly every element of your datatype is a well-formed lambda term.
How would you feed trees to the computation? Also, once types are involved, nothing can help you. I admit that untyped LC is somewhat of a borderline case.
> It's also unclear if you're talking about the complexity of type inference or type checking
Doesn't matter in this case. Pick a string representation -- any representation -- and see if it's well-formed. You can include the types and then only type checking would be necessary, or not -- and then it's type inference. Either way, the complexity is significant.
> namely the C abstract machine
That's not a machine model.
> it's undecidable whether a state is meaningful
The same goes for any language and your definition on "meaningful". You can always say that something meaningful is a little finer-grained than the language can express, or the validating the language itself is also undecidable. Got simple types? Only primes are meaningful.
> They just don't have many useful properties compared to more "abstract" approaches, and are mostly used to reason about implementation.
My point is that they're not comparable. A glass of water doesn't have the same useful properties as a blender, yet they're both made of molecules. However, there's an objective difference: a blender consumes far more energy, so of course you can use that energy to do more things.
:) You're just pushing the complexity into the validation of the algebraic type.
Look, a typed formalism does extra work of proving the type safety of the input. Checking a proof has a non-negligible complexity. If that cost could be ignored, then I have a computation model that solves NP problems in zero time: it has a type system that requires that the types form a proof certificate for the problem. All (obviously valid) inputs are then trivially reduced to "yes". In fact, you know very well that some type systems are Turing complete. If the complexity of validation is ignored, then those models can compute anything that's computable in zero time.
Types can prove things. The cost of the proof is well known, and is related to the difficulty of the problem. The universe doesn't let computational complexity slide. What, you think that God says, "oh, you clever boy, you chose a typed model so I'll let you have this proof for free!" ?
> You're just pushing the complexity into the validation of the algebraic type.
Who says it needs to be validated, any more than your string needs to be validated?
> The universe doesn't let computational complexity slide. What, you think that God says, "oh, you clever boy, you chose a typed model so I'll let you have this proof for free!" ?
You're responding to something completely unrelated to my statement.
To be clear: I wasn't suggesting a typed lambda calculus.
A tree is still more complex than strings, because it has rules: one parent per node and no cycles. Those need to be validated. But I have absolutely no problem accepting that it is possible to find an encoding of untyped LC which would bring it very close to a TM encoding. This wouldn't be surprising as LC doesn't do more computational work than TM at the validation step (unlike typed formalisms).
I specifically wrote that untyped LC is a borderline case, and it's unclear where precisely we want to draw the line. What is absoutely clear is that System F and TM are essentially, qualitatively and objectively very different, and when people try to compare them, they often, without noticing, describe two different computational problems, with two different complexities.
You're positing some new notion of complexity, without a definition, where lists are somehow fundamentally different than trees. Sorry, but that kind of claim requires more than just just an appeal to intuitions about how they might be implemented on a typical CPU. They're both just initial algebras.
The fact that your grand ideas about machine and language models doesn't apply to the lambda calculus should be a hint. We know how lambda calculus relates to typed languages: it's a degenerate case with a single type. Any differences in the complexity of type-inference or checking are between language models. You can't (without wildly waving your hands) formulate a meaningfully comparable problem for TM states.
> A tree is still more complex than strings, because it has rules: one parent per node and no cycles. Those need to be validated.
Hmm, I'm not convinced that this is sufficient to show that strings are simpler.
After all, a string has rules too: a cell in the string is either at the beginning, or the end, or the middle, and it has neighbours left, right or not at all depending on those conditions, and at most one such neighbour in each direction. Even appeal to the physical world doesn't help. If I have a physical piece of DNA, how do I know it hasn't mutated so that two different strands branch off it and it becomes, essentially, a degenerate tree?
I do think that the thrust of your argument is correct but it's not as clear cut (at least not yet) as you seem to be making out.
> What is absoutely clear is that System F and TM are essentially, qualitatively and objectively very different
Absolutely agreed! If they weren't, I'd be happy writing my day-to-day code in Turing Machines.
Since you seem to have thought about the fine details of this much more than you are letting on here and on your blog post I suggest you post an addendum (or even a new blog post) to be more precise about what exactly they are. There's a lot missing as it stands, and interested readers like myself are left to fill in the blanks.
You're still, at some point, simulating the steps of some abstract machine in your head to understand what the debugger is telling you.
The simplest case is replacing an expression with its value, given an environment of lexical bindings that are apprent from the source program. Not much investigation necessary. That's FP.
For OO code, you just need to keep track of a lot more context: the state of the receiver of the currently executing method, its heirarchy of parent classes, the runtime class of each object because late binding is pervasive. Of course you can write code that doesn't use any OO features, but the languages clearly aren't designed for it. See: any number of "functional C++" articles.
And, of course, you can get the same kind of highly dynamic behavior in FP languages by explicitly using open recursion, higher-order state and hiding everything behind existentials. But very few codebases do that because the vast, vast majority of the time just one of these features is enough to solve a problem.
OO context is internalized linguistically, via lots of metaphors. Those metaphors can lie, of course, but your brain can apply abstractions to the state of the machine to deal with its complexity, for better or worse. Ideal FP debugging, which I don't think exists in practice, relies on ultimate truth with equational reasoning realized through techniques like referential transparency. In the ideal case, you just reason about the equation and there are no hidden surprises, fuzzy metaphorical reasoning is minimized. In practice, there is still plenty of metaphorical reasoning going on for any non-trivial program as even explicit state necessarily becomes implicit as it increases in quantity (our brains can't handle seeing everything even if it is technically all in front of us).
OO thinking optimizes for the less ideal cases that are far more common. Ideal FP has this ideal mathematical view of the world that rarely pans out in practice, while less ideal FP just resorts to OO-style metaphors and abstraction in practice. For the kinds of experiences I work on (heavily reactive, lots of state, complex interactions), this works well for me, and we are developing techniques to make it less painful (live programming). "Worse is better", as RPG would say.
It sounds like we agree that lexically scoped immutable values are easier to understand, either precisely or with fuzzy metaphors. I'm not sure what "ideal" FP is or how it might have a certain "mathematical view of the world". The features I mentioned are just a subset of semantics that every high-level language programmer already knows, but are pointlessly hobbled in popular languages.
Why should expressing something basic like a tagged union require a detour through the quirks of a particular object system? Ditto for polymorphism, modularity, etc, etc. Clearly we disagree on how useful objects really are in practice, fine. Why not add these domain-specific features on top of a core language with simple semantics? It worked fine for lisps. Luckily, after a couple of decades of "everything is an object!" nonsense, that seems to be where newer languages (Rust, Swift) are headed.
You mean CLOS? This is exactly the context RPG coined "worse is better".
Languages are not so much a collection of features but mindsets. So polymorphism, dynamic dispatch, subtyping, etc...do not define OOP so much as they are leveraged by those languages to enable reasoning with names and metaphors. Calling them just domain specific features misses the point like talking about some dish only as the sum of its ingredients.
Tagged unions and GADTs are quite different in expressiveness and modularity, I still remember the mega case matches used in scalac. Should one function really be given so much functionality when a layered design with several virtual method implementations would be much more amenable to change and modular reasoning? Well, I guess it's a matter of how you view code.
Languages are not so much a collection of features ...
If you want to define objects precisely, even just to have a language spec, they are absolutely made up of sums, products, recursive types, etc. Whatever useful metaphors one might have to work with objects doesn't change what they actually are. If you give the programmer access to these building blocks, you get ML.
Calling them just domain specific ...
I meant that the particular way they're combined to get OOP is domain-specific.
Again, I'm just asking: why mess with the basics? Why require encoding simple, universal concepts in terms of an ad-hoc object system? You can still have an object system on top, if you find that helps with the really complicated cases, but why encode the parts of your code that are simple in terms of much more complicated, derived concepts?
> The notation g ∘ f is read as "g of f "...