Can programming be liberated from the von Neumann style? (1978)

https://dl.acm.org/doi/10.1145/359576.359579

by tosh • 5 years ago

169 129 5 years ago

dl.acm.org

Even when this paper was published, Backus' comments toward APL did it a massive disservice.

Modern descendants of the language have freed it entirely from "expression/statement" splits, and the collection of operators has grown richer. More than any other family, APLs today represent the most successful realization of function-level programming as yearned for in this paper.

rackjack• 5 years ago

Joy [1] is a function-level stack-oriented (read: FORTH-y) programming language inspired by Backus's FP. Funny how these things end up connected.

[1] https://en.wikipedia.org/wiki/Joy_(programming_language)

brylie• 5 years ago

This style of programming, such as unnamed arguments, sounds very difficult to understand. An important part of programming is thinking clearly by using simple and explicit writing style. Clear code should be as close as possible to explaining the problem domain and how you would like to influence the outcome.

jhomedall• 5 years ago

It most likely sounds difficult to understand because you are not familiar with it. Try working through the first few exercises in SICP; you'll see that it can be quite straightforward.

Jweb_Guru2• 5 years ago

As someone who's spent many, many hours proving things in Coq, I concur with the original post--pointfree stuff is usually much less easy to read than the same function with named variables. A lot of that comes down to not being able to tell what's going on at all if you don't already know the arity of the functions you're using.

dirkt• 5 years ago

Nevertheless, most mainstream imperative languages (e.g. Java) have adopted lambdas, "fluent" style, async/await (which is a Monad), and other functional features in the last years, and continue to adopt them.

carapace3• 5 years ago

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

JoshuaAshton• 5 years ago

b sqr 4 a c * * - sqrt

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

js82• 5 years ago

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.

morelisp2• 5 years ago

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.

js82• 5 years ago

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.

ardit332• 5 years ago

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.

gmfawcett• 5 years ago

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.)

beders• 5 years ago

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.

youerbt• 5 years ago

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.

carapace3• 5 years ago

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

IIAOPSW• 5 years ago

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.

foxes• 5 years ago

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

vajrabum• 5 years ago

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.

carapace3• 5 years ago

Ah, that's a great book, thanks!

akomtu• 5 years ago

On a half serious note, the traditional 0-1 computing model is the origin of mental polarisation in our society, because such model permits no shades of gray. A better model would use probabilistic bits where each bit represents a probability density.

njdullea• 5 years ago

So there wasn't 'mental polarisation' in society before computational models were created? Don't think that's correct..

kstrauser• 5 years ago

That’s why I use only floats in my code, and a patched Python interpreter that replaces “if” with “seemslikely”.

agubelu• 5 years ago

#define true (rand() < 0.99)

Banana699• 5 years ago

you meant a 0% serious note right?

The 0s and 1s are in the human brain friend not the computers. You can make computing as probabilistic as your heart desires, people will not stop simplifying and caricaturing the world to fit their biases, not by one "bit".

xkeysc0re• 5 years ago

If only ternary computing had won! https://en.wikipedia.org/wiki/Ternary_computer

andrewmcwatters4• 5 years ago

I would like a system that produces “true,” “false,” and “enthusiastic” results. Enthusiasm left as an exercise for the implementor.

andrewmcwatters4• 5 years ago

I await our enlightened future where we can run programs that have differing state that can be simultaneously true.

What one thread on my CPU calculates as true is it’s truth. Other threads might not agree, because it’s not their truth.

Apocryphon• 5 years ago

Isn't that what quantum computing is on about

asimjalis• 5 years ago

Maybe.

systemsignal• 5 years ago

Design a computer that does this. If it works significantly better you’d become a billionaire

sakex• 5 years ago

Ever heard of int?

15rthughes• 5 years ago

Adding the integers 2 and 2 together is definitely a grey area.

fighterpilot• 5 years ago

This reminds me of this passage from the satirical FeministSoftwareFoundation:

"The traditional binary foundation of 1s and 0s is deeply problematic: 1 is inherently phallic and thus misogynistic. Also, some 1s are 0s, and some 0s are 1s. It is not fair to give them immutable labels. Instead, we have 0s and Os as our fundamental binary logic gates. They symbolise/-ize the varying, natural, and beautiful differences of the female vaginal opening.

0 is to take the conventional value of 0.

O is 50% of the time 0, and 50% of the time 1. The determination of this depends on how the underlying logic feels at the moment."

cyclohexane• 5 years ago

Haven't heard "satire" that shite in ages lol

discreteevent• 5 years ago

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...

ipnon3• 5 years ago

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.

brazzy2• 5 years ago

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.

marcosdumay2• 5 years ago

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.)

amw-zero3• 5 years ago

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.

spicybbq• 5 years ago

This whole interview is on YouTube as well:

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

mumblemumble4• 5 years ago

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.

dustingetz3• 5 years ago

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

catgary2• 5 years ago

Moggi solved it in his thesis in ‘88.

lukashrb• 5 years ago

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

dang3• 5 years ago

The pdf is at https://dl.acm.org/doi/10.1145/359576.359579

dang3• 5 years ago

Some past related threads:

Can Programming Be Liberated from the von Neumann Style? (1977) [pdf] - https://news.ycombinator.com/item?id=21855249 - Dec 2019 (32 comments)

Can Programming Be Liberated from the von Neumann Style? (1977) [pdf] - https://news.ycombinator.com/item?id=14673817 - June 2017 (3 comments)

Can Programming Be Liberated from the von Neumann Style? (1978) [pdf] - https://news.ycombinator.com/item?id=13210988 - Dec 2016 (107 comments)

Can Programming Be Liberated From The Von Neumann Style? (1977) [pdf] - https://news.ycombinator.com/item?id=12159792 - July 2016 (175 comments)

Can Programming Be Liberated from the von Neumann Style? (1978) [pdf] - https://news.ycombinator.com/item?id=10182712 - Sept 2015 (57 comments)

Can Programming Be Liberated From The Von Neumann Style? (1977) [pdf] - https://news.ycombinator.com/item?id=7671379 - April 2014 (72 comments)

Can Programming Be Liberated from the von Neumann Style? (classic) - https://news.ycombinator.com/item?id=768057 - Aug 2009 (34 comments)

failwhaleshark2• 5 years ago

Feature request for the submit page: live AI fuzzy suggestions of URLs to prevent dupe submits.

dang3• 5 years ago

It's important to understand that this submission doesn't count as a dupe by HN's standards. On HN, reposts are fine after a year or so, and/or if an article hasn't had significant attention before (the latter isn't the case here, but often is). https://news.ycombinator.com/newsfaq.html

People post links to past discussions are not because they're bad (look at all those reposts!) but because they're good (wow, interesting comments from the past!) - at least in the best case.

Because there's so much randomness in what gets noticed on /newest, overzealous dupe detection would prevent many good articles from ever getting discussed. That would be a poor trade for better deduplication! HN's dupe detector is therefore left porous on purpose (https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...), so good stories get multiple chances to get attention. We will probably implement karma sharing amongst the various submitters of an article, though, at least when it's a first-time discussion.

amw-zero3• 5 years ago

No thank you. It's perfectly fine to discuss something that's been discussed before. I get something new out of this paper every time I read it. We are all learning and growing every day. The conversation wasn't complete just because this has been discussed before.

mikewarot5• 5 years ago

Spreadsheets and FPGAs are two places where there's no focus on a "program counter".

Metamine was amazing... he had figured out how to safely mix procedural and reactive code in one place without going insane in the process:

https://web.archive.org/web/20201101065701/https://github.co...

I watched a set of videos on YouTube that were amazing, but now I can't find any links to them. 8( I would really like to know where it went.

[Edit: I found a fork of the repository at https://github.com/caminadab/metamine

Of course I forked that fork to have a copy for safety]

breck• 5 years ago

Metamine looks amazing. I don’t know if I’ve seen it before. Thanks for sharing. Now I’m really curious.

hcs• 5 years ago

Metamine looks interesting, thanks!

Here's a tutorial video I found demonstrating programming the game Snake http://web.archive.org/web/20201014024057if_/https://www.you...

Found from a Reddit discussion http://web.archive.org/web/20201130115327/https://www.reddit...

mikewarot5• 5 years ago

In Metamine there are two different modes of assignment

  x = y      is an equation, any time the expression y changes, x will be recomputed

  a := b     is an assignment, it only happens once, like we're all used to.

It is profoundly powerful to be able to use them both in one program. There appears to be a type associated with them, you can't assign to an equation variable, and vice versa.

taeric6• 5 years ago

Pretty sure this is used in the likes of metafont, as well. Is a great tool where it is applicable. Oddly not that applicable in most programs. Especially if the "plumbing" variety.

vgel• 5 years ago

Svelte does something similar with its `$: x = ...` syntax. I wonder if it was inspired.

geokon2• 5 years ago

Don't you accomplish nearly the same thing with memoized functions?

This seems to just provide a wrapper that obfuscates things

nielsole• 5 years ago

OPA's Rego has the same syntax and semantics

AndresNavarro• 5 years ago

Spreadsheets and FPGAs are two places where there's no focus on a "program counter".

I'll give you spreadsheets, but while it's not the "focus" you will very often see softcores and lots of state machines being used in FPGAs. Some things are just easier to reason about and write that way.

mikewarot5• 5 years ago

Yes, softcores are often used to set up peripherals, and some light duty computation, but the real time aspect of an FPGA is something best set up in Verilog or VHDL, or those type of things.

andrewmcwatters4• 5 years ago

I'm too unknowledgeable to know, but I consistently get the feeling when I interact with a new programming language that they all fail to encompass everything that a modern system is capable of, or that they provide mechanisms with such high overheads that they're no better, or even worse, than programming languages of yesteryear.

One example of this for me is that you don't need special drivers for making your program run on a CPU; that would sound quite strange to most developers I think.

But many high-end systems have full blown GPUs on them that we basically never use unless they're specifically interfaced with for video purposes, scientific computing, etc.

Even then, you still have to use specific interfaces to access that hardware. It's not intrinsic to the language.

But say I wanted to run some generic routines across CUDA cores/Stream Processors, I have to explicitly move into the realm of GPGPU programming to do that, and then you have to write "compute kernel" code. It's not just... programming. It's fully terminology'd, it's own thing.

There's no standard library for any programming languages that automatically sends your routines to the GPU.

I don't know how all of this should be approached. I've been exposed to all of these systems, but they're all clearly isolated.

All I know is that it doesn't feel right. I fully engage development efforts feeling like I'm not using the full compute power I have available to me, and a part of that I think is that today we just don't think like developers did 50 years ago.

We have so much compute resource available to us, I think in some very fundamental ways--industry wide--we no longer understand how to use these systems. I know I don't.

I'm consistently asking myself why certain operations I write take milliseconds for some reason instead of microseconds. That's tremendously concerning to me.

fleischhauf• 5 years ago

While i agree that it is more difficult to distribute computational load between cpu and gpu than it aught to be, Gpu is not necessary faster for all workloads than cpu, it is very specific. Most of computations can probably be executex faster on cpu.

ledauphin• 5 years ago

agreed, but i take the GP's argument to be that the languages aren't sufficiently expressive to allow us to communicate generically about workloads in a way that allows a system to correctly determine whether they would be faster on a CPU or not.

taeric6• 5 years ago

You say we don't need drivers for the CPU, but there is still software that had trouble running on the M1. And there is plenty I can't get to run on a raspberry pi.

Jetrel• 5 years ago

Quite arguably, we do - such a driver would be a "compiler". Most compilers do some really wild things to reshape your code to take (some) advantage of new processor features.

There's a huge amount of "brain offloading" that's deferred to the compiler guys, and in a ton of ways, that's the point of having a driver as well; they adapt generic commands like "write a file to disk" to work for you on any kind of disk; compilers adapt your C (or whatever) code to work on e.g. any of the current intel chips of the last N years (within which there are quite a few breaking incompatibilities; I've had code compiled for a really particular i7 CPU actually not work on a different one, because it was taking advantage of new instructions only available on that particular chip - when I reconfigured my compiler to hit a wider compatibility target, the issue went away.

So yeah - there's a huge amount of knowledge "hidden away" there.

kaba05• 5 years ago

To be honest, we don’t even manage parallel computations on the CPU well. In most languages there is basic SIMD at most with some autovectorization. But if you don’t write your code with threads explicitly, you will only ever use one core.

fulafel3• 5 years ago

Most (I assume you meant implementations) don't have even basic SIMD support like that. Even big and popular ones, such as JS, JVM, Python, Lua, .NET, Go... A couple of those do have simd intrinsics.

michael1999• 5 years ago

What are your compiler, assembler, glibc, and the kernel, except specialized drivers for your cpu?

They are certainly more polished than the tools around GPUs or other io co-processors, but I don’t see the difference.

m1kal• 5 years ago

Julia with ArrayFire seems to be straightforward, efficient and easy to use.

int_19h2• 5 years ago

C++/AMP (https://docs.microsoft.com/en-us/cpp/parallel/amp/cpp-amp-ov...) is something along those lines. I dunno if it strictly satisfies your "intrinsic to the language" requirement - you still have to explicitly request GPU processing by using the appropriate parallel_* algorithms and restrict(amp) - but it's intrinsic in a sense that compiler takes a C++ lambda and compiles it to run on the GPU.

But I don't think that you could reasonably make something that just automatically sends any random routine to the GPU, or at least not efficiently. The processing model is just inherently different.

RcouF1uZ4gsC• 5 years ago

Given the question is still being asked after 43 years since the paper was published, my guess is the answer is “no”.

I would not be surprised though if this paper is still posted in the HN equivalent in 2078.

adamzerner• 5 years ago

Eric Normand has a great podcast episode where he talks through the paper, summarizing and commenting on it in a way that targets a more general audience.

https://lispcast.com/can-programming-be-liberated-from-the-v...

todd8• 5 years ago

John Backus won the Turing award in 1977 and gave a Turing Award Lecture with the same title. I was in the audience and it made a big impression on me. I had just finished my Masters degree in computer science and had decided to work for a few years before returning to grad school for more.

It was an interesting time to be in CS. To be fair, CS has remained interesting to me to this day. But back then, right out of school, I felt like I knew something about almost every area of CS, maybe not much but at least something. So everything seemed possible.

The field has become so large that even after a lifetime of working and studying in the field of CS, even a modest understanding of one slice of CS is all we can hope for. Nevertheless, it stays fascinating.

eyelovewe• 5 years ago

I’m under the impression that it must actually function in the contrary: i.e. exotic non von Neumann hardware requires new programming approaches.

Example: a systolic array, which you are only likely to encounter as an FPGA bitstream, by its very nature requires a different approach. Flow based programming is a better match for this specific system.

What we have seen since this paper was written is often the shoehorning of new concepts under control of standard von Neumann style programming, whatever the reasons may be, often including programmer familiarity.

Can programming be liberated from the von Neumann style? (1978)

Related Stories