[nightski]

You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. The approaches & data structures aren't always the same.

In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post.

There are many good resources on this. I've referenced a few below. Of course there are many more.

[1] https://www.amazon.com/Pearls-Functional-Algorithm-Design-Ri...

[2] https://www.amazon.com/Purely-Functional-Data-Structures-Oka...

[3] https://www.amazon.com/Algorithm-Design-Haskell-Richard-Bird...

[4] https://www.amazon.com/Structure-Interpretation-Computer-Pro...

[dehrmann]

> You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole.

This might be part of the problem with FP. Every popular CPU architecture is imperative.

[nightski]

I was more talking about how you approach solving problems, not the execution model. You can still get tight imperative loops in FP, it's just approached differently than in a traditionally imperative language.

Everything is a tradeoff. FP gives you a lot of flexibility in how you trade space and time of the execution of your program. It's also not a magic wand, just a really powerful tool.

[chriswarbo]

I find this unconvincing. Electronic circuits are well described as a Cartesian Closed Category; and hence by lambda calculus (i.e. we can give semantics to functional programs by interpreting them as descriptions of circuits; as opposed to the "usual" interpretations of x86_64 machine code, or symbolic values, etc.)

Imperative systems are "fitting a square peg in a round hole" by introducing hacks like 'clock signals', 'pipeline flushes', etc.

[hither_shores]

The category with linear circuits as its morphisms, labelled sets of electronic terminals as its objects, and laying circuits in parallel as the monoidal product (which is the usual notion of the category of circuits; perhaps you have something more sophisticated in mind, but if so you should specify that) is not cartesian closed.

One of the many ways to demonstrate this: all linear circuits have duals (voltage <-> current, series <-> parallel, and so on), but in a cartesian closed category only the terminal object is dualizable.

What you're probably thinking of is the fact that this category is compact closed. The corresponding internal language is going to be some sort of process calculus (I think the pi calculus is too strong, but not sure), not the lambda calculus.

[imtringued]

No, that's the easy part. Computation with FP is very easy. The problems start the moment you have to do persistence and communication. Those aren't part of any pure functional paradigm.

[TuringTest]

> Every popular CPU architecture is imperative.

That's arguable, given that every (deterministic) imperative computation can be expressed as a pure functional program. "Imperative" is more of a viewpoint that the developer is using to understand the behavior of the computer, rather than a property of the machine itself.

A pure functional analysis will describe a computation on that "imperative" architecture as an inmutable, monotonic sequence of all the states that the CPU goes through over time; or maybe, if you know enough PL theory, as a chain of rewritings of a program-long expression that is updated, one term at a time, when each expression is replaced by the result of a function as it consumes its input parameters.

And no viewpoint is inherently better than the other (except that the functional version can be analyzed in a natural way with mathematical tools, which is often difficult with the imperative description).

[kortex]

Nope, unless you do some serious contortions and basically say that the universe is a lambda calculus that operates on each moment in time to produce a new view of reality.

Computers that do anything useful have all manner of I/O. Highly oversimplified in modern architecture, but you can think of I/O as a bunch of memory cells that are DMA'd by external forces. Literally the exact opposite of functional, IO registers are the epitome of global mutable state. Then you have interrupts and the CPU operates in response to these events.

The viewpoint of "computers are mutable state" is inherently better because of parsimony - it requires less degrees of indirection to explain what is happening. Just because you could shoehorn reality into a physical model, does not make it equally valid. You basically need to break it down to the Schrodinger equation level to have a purely functional model when even idealized gates are involved because propagation delay impacts things like how fast you can DMA.

[TuringTest]

> Just because you could shoehorn reality into a physical model, does not make it equally valid.

Hey, physicists do it all the time. Having mathematical representations of how things work in the real world often turn out to give you complex devices that you wouldn't get by intuition alone. Thanks to doing it, we have Special Relativity and Schrodinger equations, that bring you advantages as GPS and insanely-high-speed networks.

There's nothing wrong with modelling interrupts and mutable state as static mathematical entities a.k.a. functions; and if you think it is, you don't know enough about functional programming - in fact, doing it allows for advanced tactics like automatic verification and very high scale generation of electronic devices.

Those less degrees of indirection may make it simple to build some kinds of programs; but they also introduce complexity in modelling the possible states of the system when you allow for arbitrary, unchecked side effects. So no, that representation is not inherently better - only most suited for some tasks than others; but the converse is also true for functional models of computation. If you think it is always better, it's because you're not taking all possible scenarios and utilities into account.

(Besides, as I already said elsewhere, "computers are mutable state" is not incompatible with functional representation; as mutable state can be represented with it). It seems that you're confusing mutable, wich is a property of computational devices, with 'imperative' which is a style of writing source code and defining relations between statements in your written program.

> Literally the exact opposite of functional, IO registers are the epitome of global mutable state.

Yup, you definitively don't know what functional programming is if you think you can't have global mutable state in it. In fact, every top-level Haskell program is defined as a global mutable IO monad...

[whimsicalism]

Not really arguable, IMO.

Just because both lambda calculus and assembly are Turing complete does not mean that CPU architecture isn't clearly imperative.

[TuringTest]

How do you define "imperative" in a way that precludes a functional description of your definition? I'd say that if you're able to do that, you'd have found a contradiction in Turing completeness and win you a Turing award.

Also, this: https://news.ycombinator.com/item?id=30883863

[whimsicalism]

Just because every program in C is also expressable in Haskell does not mean that C is Haskell or that C is a functional programming language.

The same is true of CPUs, which at their base level execute instructions line-by-line to move and load things in and out of stateful registers as well as doing simple mathematics.

Not going to keep arguing, as I can see from your other comments that you are going to try to hold this line, and also your reasoning doesn't really make sense.

Everyone has heard of Turing completeness. It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.

[TuringTest]

> It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.

No, it means that every computable program or device can be described through functional semantics, and therefore that very same program running on that same hardware can be described mathematically with them (not an 'equivalent' program, but the same program with the same runtime behaviour, just described in low level with a different format).

That's a core principle of computer science that predates computers themselves, and people arguing about the benefits of the imperative style tend to be unaware of this fact, making their arguments look weak.

[dahfizz]

You're definitely stretching here. I could just as easily argue that "all of main memory" is the output of any function. Therefore every function is a pure function, and C is a function language. Using your definition, the concept of functional programming is meaningless.

Main memory is state. Registers and cache are state. The entire purpose of the CPU is to mutate state.

[nightski]

No, I don't believe you could argue C is purely functional by framing memory as the output of the function because C doesn't treat it as such. Memory in C can be changed even if it is not listed in the inputs or outputs of the function.

He's not really stretching the definition, that's just the lens through which FP looks at the world.

Of course there is state. FP doesn't prohibit state, it just makes it explicit and referentially transparent. But this is in the semantics, not the execution model of the program.

[dahfizz]

> Memory in C can be changed even if it is not listed in the inputs or outputs of the function.

If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'.

If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you can't make that leap for assembly.

[nightski]

It's not syntax, it is semantics. There is a lot to programming language theory/design and this is all formalized. C does not have the semantics you are describing in the formal specifications (C99, etc..). Could they have developed a version of C with these semantics? Possibly. Rust was a step in that direction with it's borrow checker.

[rramadass]

I think anybody who wants to understand Functional Programming should start with Lambda Calculus.

I highly recommend An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson.

You can then see how to express Functional Techniques in your language of choice (i.e. one you already know well eg; Functional Programming in C++ by Ivan Cukic) before learning a new Functional Language. This is to avoid the confusion in syntax/semantic expression of unfamiliar concepts which is a bit too much for a beginning student to handle simultaneously.

[exdsq]

Thanks for these links, commenting to find them later.

[Jtsummers]

If you select the timestamp of a comment (also when you reply to it) you can favorite it. This is much cleaner than leaving scattered "to find them later" comments around this site (in fact, I'm pretty sure it was added precisely to avoid those kinds of comments). You can also favorite submissions themselves. Favorites can be found in your profile.

[bckr]

you can click the timestamp and just keep the URL somewhere, like your browser's bookmarks

[exdsq]

Cool, didn’t know that! Cheers