Hacker News Reader

Comment by carapace | Hacker News Reader

The thing in this paper that I see missing from most discussions of Functional Programming is the use of an algebra to derive programs.

I've worked a bit with an FP concatenative language Joy and this sort of algebraic manipulation is easy and fun, and seems to permit (nearly) bug-free development.

Here's a very simple example of deriving a function for the quadratic formula:

https://joypy.osdn.io/notebooks/Quadratic.html

A more complex example deriving a combinator "treestep" to process tree datastructures:

https://joypy.osdn.io/notebooks/Treestep.html

View on HN

I came across this paper recently while looking at Kitten (it was actually mentioned in HN before): http://evincarofautumn.blogspot.com/2012/02/why-concatenativ...

I think really explains the idea. I always liked combinatory logic more than lambda calculus, although it didn't click to me that the concatenative languages are essentially the formalism for it (as opposed to ML-style syntax).

Although I would say functional programming is somewhat orthogonal concept, the concatenative languages can have functions with side effects, like Forth does.

Perhaps the universe is state based, and not function based...

Programing language are away to represent reality, and manipulate it to your desire.

Object Oriented, and Procedural programing both use functions to manipulate state, while in pure functional languages you use functions and unnamed variables to present state.

The problem is when you communicate, you always do it with state and not functions. From API to storing data as it allows to very different systems to understand each other without to have the same internals. A java web based api/program and a swift/objective-c program running in a phone can easily communicate with each other via state (aka, rest of soap apis), and they don't have to know the internal state of each other.

You can save functions, and pass them along, but the other part has to know how to run it, and have the same type of hardware in order to run it.

I really think pure functional programming is a mathematicians pipe-dream, and theoretical CS nerds trying to shoehorn Math/Algebra equations into being the default type of programing paradigm, but for practical Computer Science problems the von Neumann style (statements and expressions) has won as it is the most practical

The only true successful alternative to von neuman state type of languages, is really SQL and its derivatives, which is a declarative style of programing language. You can pass SQL queries around, and they will be understood by all kinds of systems. But, ultimately they all act on some kind of state/data in a table.

> The problem is when you communicate, you always do it with state and not functions.

I'm not sure that's true. A "callback" is way of communicating with a function as the message. Callbacks are a way for systems to communicate while hiding their implementation details. (One could argue that the callback itself is a first-order object -- a piece of state -- but nonetheless we are communicating with state and functions then.)

Callbacks are a signal that your operation is done, and the data is ready... usually they have some kind of state (i.e. success, error, the data read from disk/api, etc).

They are usually used within one program itself, and not across systems. Something like the Firebase real time database, or webhooks, are for callback achross systems, but they always are used to pass data/state, and not functions itself.

Again, SQL and maybe Regex (which is not a full programming language anyway), as the most successful alternatives to normal Object Oriented/procedural programing.

Most functional languages have not become successful. I learned Prolog in the 90s, and I could see how it might be useful in some situations, but it is hard to do anything practical with it.

Some functional concepts, like map/reduce, have become popular in mainstream languages, as they are useful in certain scenarios, but pure functional languages have not.

This sounds like a byproduct of your natural-language rather than a fact about the universe per se. Native American languages rather famously define things by function rather than by state (Eg names like "runs with wolves"). In a different timeline where North America was never settled by Europeans, perhaps functional programming would be the default and Von Neumann style would be the weird thing nerds think about.

Well, if you go down to the machine code all functions are data, no?

Did you just compare passing data to passing functions?

Because absolutely nothing about transferring data is specific to the program language paradigm chosen.

Here's a task for you: Build a graph of objects holding state with your chosen OO language. Now write that state to disk and read it back in - guaranteeing a consistent state.

Oops, a thread mutated some of the state while writing to disk?

Damn it, need to add a some synchronization stuff. In all my objects. Oh now all my mutations need to go through a semaphore?

No, wait I'll implement the Memento pattern for all my objects, that will help? (nope, it won't, you still need to synchronize across threads)

If you operate on immutable data, that exercise in a functional language is literally two lines of code.

Of course, with pure functional programming with no state under the hood, you would have failed at your original challenge of "build a graph" without further constraints (it's rather hard to ensure totality or that every pointer is accessible when you allow arbitrary cycles).

I'm also not sure why you feel functional programming relieves you of the responsibility of making sure appropriate barriers are created between writes and reads to disk--message passing is more fundamental than programming paradigms, and you physically must make sure your messages synchronize somehow (and that you can recover from corrupted state, if there's a crash). Just writing once simply is not enough here! Also, without mutable state, how do I find the new head (where the appended stuff starts?). This has historically been a very annoying problem to deal with!

Not that I think most of these concerns affect us much during day-to-day programming, by the way! I just find this a particularly poor example of the benefits of FP. In pretty much any useful distributed system, there will be some moving parts that need to be synchronized (like the actual messages to the storage layer), some state that needs to be maintained (root information a bootloader can follow to restore the system), and some weird domain specific stuff that's very hard to encode in types (like crash recovery, in this case). This is true whether or not what you want to do is conceptually purely functional--someone has to make decisions at each of these points about whether and how to expose the inner workings of the system, often in a way that trades off against things like flexibility, space overhead, reliability, and performance. And those decisions have to be relayed to the computer via some programming language that can talk state (or embedded into the hardware).

Accepting that reality doesn't mean that everything has to be written in a "multiparadigm language" or anything like that, but it does mean being cautious about declaring that your favorite technique will automatically solve the issues plaguing another area of CS.

This is just a comment about implicit vs. explicit state. What you described is not inherent to OO, though of course it's much easier to have implicit state in OO.

I'm working in a codebase now that is very OO, but also is very diligent about having state be explicit. The exercise you described would also be 2 lines of code in this project.

Except I would say quantum computation, which is truly more natural, considering the universe is quantum, definitely feels more functional flavored.

> Perhaps the universe is state based, and not function based...

That didn't stop physics, why should it stop CS? No paradigm won, game is not over yet.

Richard Bird has pursued the algebraic approach in a lazy functional language context. He and Ooge de Moor presented their work on the algebraic approach to lazy functional languages in a textbook form in the book Algebra of Programming in late 90s. Not terribly update to date but still really great stuff and a place to start if you're wanting to understand the more up to date stuff. That book can be found on the web. Don't try to buy it on Amazon. They have a highway robbery price. If you need to buy it you might try Google Shopping. I saw several copies for under $10.

Ah, that's a great book, thanks!

b sqr 4 a c * * - sqrt

Yeah no. This being "bug free" seems like a joke.

I don't see an objective reason this is more or less clear than

    sqrt(sqr(b) - 4 * a * c)

    (sqrt (- (sqr b) (* 4 a c))

Honestly, by objective measures the traditional style is probably the worst. The Forth style makes it easy to see large stacks because you'll see long sequences of literals. The sexp style makes it easier to work with subexpressions. Both the Forth and sexp style don't require remembering PEMDAS. The sexp style is easier to parse, and the Forth style doesn't even need a parser.

The only thing going for the traditional style is that it is an ugly approximation of mathematical notation - but that notation itself loses most of its value in the uglifying.

This is just a "minor usability issue". Seriously. In Factor, you can solve this with references to local variables, which under the covers manipulate the stack as needed. It can also typecheck, so you wouldn't be able to write the expression in a way which unbalances the stack.

Reply on news.ycombinator.com