Comment by discreteevent | Hacker News Reader

Comment by discreteevent | Hacker News Reader

Booch: Your functional programming work was unsuccessful.

Backus: Yes.

Booch: Let’s dwell upon that for a moment, because there were some other papers that I saw after your Turing Award lecture [“Can Programming Be Liberat ed From the von Neummann Style”, 1977] which was also a turning point. Because I’d describe it as a wake-up call to the language developers and programmers, saying there’s a different way of looking at the world here. The world was going down a very different path. Let me pursue that point of why you think it didn’t succeed.

Backus: Well, because the fundamental paradigm did not include a way of dealing with real time. It was a way of saying how to transform this thing into that thing, but there was no element of time involved, and that was where it got hung up.

Booch: That’s a problem you wrestled with for literally years.

Backus: Yeah, and unsuccessfully.

http://archive.computerhistory.org/resources/access/text/201...

The rest of the interview provides an interesting context there. He retried in 1991, and, since then, he seemed to have been extremely uninterested in keeping up to speed with any newer programming languages.

Meanwhile, Haskell 1.0 entered the world in 1990, and the Haskell community figured out how to use monads to solve the time problem in 1993. So, it's not necessarily that the problem wasn't solved, it just wasn't solved by him, and he perhaps wasn't aware of the solution.

comonad encodes time, but first good paper i know of that describes this is 2006

which paper?

Well, more generally speaking comonads encode costate i.e. context, but I haven’t yet seen them being used represent time. Do you have a link to the paper?

http://cs.ioc.ee/~tarmo/papers/essence.pdf also it needs to be updated for cofree comonad

Thank you!

Well, the interview never really addresses this clearly and directly, but my sense was that it seemed that the biggest problem he was grappling with was dealing with situations where things have to happen in a certain order. The formulation of functional programming that he presented in Can Programming be Liberated from the Von Neumann Style? is, at least to my reading, pure and lazy. For a while at least, nobody really knew how to deal with things where time matters in even the most basic way - ensuring that they happen in a certain order, or even at all - in a pure and lazy language. The Haskell community figured out how to use monads to crack that problem in the early 1990s. Haskell 1.0 didn't have monadic IO, what it had instead was, from what I've read, kind of an unwieldy hack.

SPJ covers these sorts of issues in some detail in his paper Tackling the Awkward Squad: https://www.microsoft.com/en-us/research/publication/tacklin...

Did Clean have uniqueness typing from it's inception ('87)? That's another way to deal with time.

IO solves the "time problem" by just encoding a von Neumann machine in the functional language, which is less like a liberation than a peace treaty.

Maybe my imagination is too small, but what else could a solution look like? You want sequencing, and IO gives you exactly that.

stream, signal, and differential programming

Perhaps. But I think that you're also wandering away from the plot. Clinging to our contemporary way of thinking about this stuff isn't really going to help us understand what he was grappling with 30, 40 years ago. It's more likely to muddy the waters.

I don't see any evidence in there that Backus was looking for anything quite so lofty as the stuff you're bringing up. While it's true he wrote the paper that kicked off the whole idea behind FP, we've also got to keep in mind that, as he repeatedly mentions in the interview, he was a lifelong Fortran programmer who, in marked contrast to most fans of FP nowadays, held a lifelong affinity for Fortran. It sounds to me like encoding Von Neumann bits into the functional language so that you're there when you need them is exactly the sort of thing he was looking for. To my reading, his Turing lecture would seem to suggest the same.

Could you provide a link or example?

I feel like Hagino had talked about coinductive data types in the early 90’s.

Moggi solved it in his thesis in ‘88.

I would really appreciate if someone takes the time to enlighten me how monads solve the problem.

Check out that Tackling the Awkward Squad that I mentioned elsewhere. It's about as lucid an explanation of the what and why as I've ever seen, by one of the original authors of Haskell.

https://www.microsoft.com/en-us/research/publication/tacklin...

With pure code you cannot really do much of practical value. You can perhaps compute values, solve relational or logic problems, do math, etc., but you only end up with results at the end of computations. Even that may require monads to print out or somehow follow a specific sequence, if the language is pure enough. Pure lazy code simply won't do anything, and evaluation order of lazy execution is variable, undefined even. Purity taken too far, won't do anything useful by itself.

So you use monads to add magic while starting off evaluations, often in specific sequences. They make up code blocks that are explicit about having side-effects. So are often used to separate pure code from impure code, as the magic monads can do could be anything one would like to add. So it's kind of like an impure addon to the existing language, but also by being explicit and more precise about the taints on purity. Each monad do different things, so are kind of like different addons.

However, monads may generally be used purely too. They are more general tools than just the famous IO monad. So the concept of monads are reused for abstraction. It's useful that so many things are solved by reusing the same general pattern. To explain all of that would require more context of the language itself, ie. Haskell. I'm sure somone with more experience has a short and easy explanation! :)

There are StackOverflow pages and such that have good explanations for those with a bit of familiarity with Haskell.

Reactive paradigm programming seems to have handled this problem is a satisfactorily functional way. But these higher reactive layers are almost always built on Von Neumann paradigm languages like JavaScript. So long as bare metal looks more like a Turing machine than a Church calculus we will struggle to take functional paradigm from top to bottom.

The whole thing still runs in and has to interact with the real world where everything is governed by time and state. You can't avoid having the impedance mismatch somewhere in your stack.

The inability to deal with time and state is not fundamental to functional PLs (though possibly a difficulty for pure FPs). Erlang handles time, state, AND space (though isn't that just time?) fantastically. Perhaps unsurprisingly, the lead creator was a Physics PhD (candidate dropout? I don't remember). Concepts of giving up on absolute synchronicity, for example, reliability of transmissions across unreliable channels, permeate the feel of the (functional) system. It is decidedly not pure functional programming though, as the choice of a functional system was made more of a pragmatic / developer ergonomic choice than a theoretical one.

Yes it is, and Erlang isn't a counterexample. As you noted, it's not a "pure" FP, and it is exactly the messaging elements that let it handle these things.

Q: Erlang "object-oriented" after all?

A: Yes.

http://erlang.org/pipermail/erlang-questions/2009-November/0...

In a talk he admitted that Erlang is the unification of OO and FP, although he didn’t realize it when he created the language.

He also mentioned Hoare‘s CSP as an inspiration with the caveat that he didn’t agree with the lock-step synchronization as messages should be async. Makes sense from a physicist‘s perspective.

I'm sorry, I have a lot of respect for Joe Armstrong but this is simply something he got wrong, probably because he didn't fully understand smalltalk objects. Before he 'admitted' as such, he understandably thought OO was stroustrop style OO. Then someone pointed out to him that originally OO was smalltalk OO, which admittedly looks vaguely like erlang message passing. But there are critical differences.

something can be both object-oriented and functional. they're not exclusive.

However, although erlang's process model superficially looks like smalltalk objects, if you design your erlang program like a smalltalk program, your performance will suffer and you will be in a world of hurt when stuff breaks. The point of message passing concurrency in erlang is to create failure domains, not to organize your code.

In short, please do not structure your erlang program like smalltalk OO, and it is definitely not what a contemporary programmer would call OO.

> something can be both object-oriented and functional. they're not exclusive

Indeed: not a "pure" FP, and it is exactly the messaging elements that let it handle these things

> However, although erlang's process model superficially looks like smalltalk objects

Did anybody claim Erlang objects were like Smalltalk objects?

When anyone claims erlang processes are like objects they are referring to the message passing nature of the processes, which is directly analogous to smalltalk objects. There is no other reasonable way to call erlang object oriented. I am aware that Joe Armstrong got swept up in this analogy. My point is following this superficial similarly to it's logical conclusion will result in shit code, so you really shouldn't make that analogy.

It's so bad there is an explicit admonition against doing it in the elixir std lib docs.

> the message passing nature of the processes

Yes.

> which is directly analogous to smalltalk objects.

No. Definitely not "directly", because Smalltalk messages are synchronous, whereas Erlang messages are asynchronous.

Both are special cases of the general concept of "messaging", and arguably the Erlang instance more closely matches what Alan Kay had in mind. (See his description of objects and messages as lots of little autonomous computers exchanging messages).

> I am aware that Joe Armstrong got swept up in this analogy.

Not sure what you mean with "swept up". He realised it is obviously true. Considering he created the language, he might have had an idea of what he was talking about.

> so you really shouldn't make that analogy.

You shouldn't naively equate Erlang messaging with Smalltalk messaging, but the only who has done this here is you.

¯\_(ツ)_/¯

> Definitely not "directly", because Smalltalk messages are synchronous, whereas Erlang messages are asynchronous.

I think you have a problem comprehending English. Directly does not mean exactly. Most of the rest of what you wrote is basically rehashing what I am claiming.

> Considering he created the language, he might have had an idea of what he was talking about.

No shit. However, he did not know as much about OO, or the history of OO, because he was at the time it was picking up steam very much busy building erlang. 2009 is around the time of the turning point in Joe's understanding of OO:

http://erlang.org/pipermail/erlang-questions/2009-November/0...

> "swept up"

Someone pointed out the full history of OO to him, he realized that his naive understanding of OO (Basically, C++ objects) was not complete, and he quickly grabbed on to his new understanding. Ok great. It also sounds diplomatic, and also now everyone who complained that his language was not OO and therefore bad can be shut up. What would you do?

> but the only who has done this here is you

Nope, so is Joe Armstrong.

Monadic IO, Uniqueness types (as in: Clean), voluntarily working in a pure subset until the End of the World (Scala), effect-first languages, etc. We can impose actual semantics upon an ultimately imperative computer. Is it restrictive? Yeah, but that's, like the point, man. Restricting what can happen allows us to reason about what might happen given a piece of 'random' code. In an imperative-only world, Capabilities serve a similar function.

The fact that the world is made up of elementary particles subject to the 'laws' of thermodynamics has very little impact on the semantics we choose for our programming languages. (If you want to take your appeal to 'nature' that far.)

I was replying to a comment that specifically bemoaned that the low level hardware is not functional.

Of course, but in the end everything is an abstraction. You can use functional reactive programming to expose a stateful API, for example; there’s nothing wrong with that.

And on the other end of the spectrum, if you go low level enough you realize that everything is stateful in the machine, so you will need to build (or already have) functional abstractions on top of that.

Bottom line, it’s almost impossible to have a single paradigm on all levels of your stack.

I will call reactive paradigms "satisfactory" after I get to see any real framework on it that is easy to read and write large programs on.

Yes, they are very promising. But since every single widely deployed language (and "widely" here includes things like Haskell) is a bad fit to it, we are missing some more development before that promise is fulfilled or failed.

(And by the way, the JS frameworks, popular as they are can not claim to be free from the Von Neumann constraints. That requires a pure language.)

I've always found Arrowized FRP to be really nice to work with.

The abstract concept of arrowized FRP is quite promising.

The practical implementations are either way too complex for everyday usage¹, or specialized into a narrow application. Also, arrows create a completely different sublanguage on any mainstream language that supports it; a sublanguage where things don't compose as nicely.

1 - You can't demand that people will convert a simple procedure into a series of unrelated steps spread all around, that's a receipt for bad code. The fact that people do such things on unrelated domains is not a reason to have it here, it creates bad code there too.

Angular uses RxJS as a primitive. It's a breeze writing reactive components and applications that way.

I have yet to see even a medium size program stay "a breeze" due to choice of this kind. Tons and tons of small parts that give the facade of easy breezy. But then the whole that they make up is left incomprehensible. Would be delighted to see counter evidence.

Netflix uses RxJS for their UI.[0] Not the end all be all but some evidence.

[0] https://www.youtube.com/watch?v=AslncyG8whg

Not entirely sure how I rank this evidence. Pretty sure the UI had gotten less to my liking as the years go by.

Still, definitely counts as evidence. Thanks!

I agree. For me, when I'm working with something where I can get functionality like Differential Datalog [1] is when I move over to a reactive-ish paradigm. It's half the answer, and there is a lot of state-related stuff in the other half.

There are probably other ways to provide the rest of the pieces, rules engines, some of those DSLs that describe stream graphs with composable nodes, other incremental querying stuff I can't remember right now ...

[1] https://github.com/vmware/differential-datalog

I'm not sure it meets your criteria but R Shiny (https://shiny.rstudio.com/) is purely reactive.

> So long as bare metal looks more like a Turing machine than a Church calculus

This will always be the case. The Turing machine is simply a much better model for implementing a machine capable of executing programs. The Lambda calculus (and math in general) are obviously better tools for _reasoning_, but the reason that reasoning in them is so powerful is precisely because you don't have to consider the execution cost of certain operations to reason about them.

Think about all of the common set theory operations. It is trivial to write: PrimeNumbers ⊆ NaturalNumbers, however, think about _computing_ the result of this expression. Generating prime numbers is not a simple computational task, and even if it were, you can only ever verify it for a subset of the natural numbers since computation is inherently finite.

It's all fun and games until you need to execute the program. The functional style is great in terms of expressivity, but you want a Turing machine at the bottom executing it if you ever want the program to finish in your lifetime.

I may not get your point - but a mathematical expression in itself is not functional - as far as I know. You have to give a definition that will likely be an infinite recursive function - which is strictly equivalent in what it can do to a Turing machine.

General recursive function, you mean.

The point is that creating hardware that executes a Turing machine or something like it is easy, but constructing hardware that executes a general recursive function is so hard that it has never been done.

My point was that a random mathematical expression will not be constructive in itself. And you are right, that either general recursive functions or lambda expressions are required to be equivalent to Turing machines. And while I agree that recursive functions are hard to execute on hardware - but certain aspects of it are apparent in CPU design — out-of-order execution is sort of lambda-like.

I think you're a few levels ahead of me in the theory (at least), but it just blew my mind to think about the fact that it's easier to compute all the numbers than it is to just compute the prime numbers. :brain-explode-emoji:

This whole interview is on YouTube as well:

https://www.youtube.com/watch?v=dDsWTyLEgbk

Reply on news.ycombinator.com