Very little innovation in programming languages has happened regarding new realities at the hardware level especially transition from serial to parallel execution.
STM: https://cs.brown.edu/~mph/HerlihyM93/herlihy93transactional....
Region based memory management: https://en.wikipedia.org/wiki/Region-based_memory_management
Rust lifetimes, originally from Cyclone: https://en.wikipedia.org/wiki/Cyclone_%28programming_languag...
Mutable value semantics: https://arxiv.org/pdf/2106.12678.pdf
See Rayon.
Region based memory management was first conceived in 1967 and is achievable by any programming language that lets you manage memory yourself.
Mutable value semantics in native code have been available since at least 1980 with Ada.
Lifetimes in Cyclone seem the best example of PL research in the last 50 years you have there, as it’s only 20 years old.
Overall, I’m still unsure if this list proves the point that there is active useful research in the PL space or if it proves that there’s very little in the PL space to research. More research is probably required.
STM is not about hardware, it's literally "software transactional memory" and is meant to be implemented in software without hardware support (beyond a CAS instruction or a similar set of instructions, perhaps). As a software component it could be part of libraries or part of a programming language as part of that language's general concurrency model.
As others have pointed out, there's STM research in PL, it's not entirely about hardware. (The link I gave wasn't great, sorry.)
> Mutable value semantics in native code have been available since at least 1980 with Ada.
Could you link to the relevant docs? I wasn't aware Ada had anything like this.
Is this implemented under the hood with deep copying? Because if so, that would explain why it hasn't started to catch on anywhere until now. Swift and Hylo have much more efficient implementations that "copy all the time".
https://www.jot.fm/issues/issue_2022_02/article2.pdf
> Region based memory management was first conceived in 1967
There's active research in this general space. I met someone who was working in it on a train, though I forget the details.
> and is achievable by any programming language that lets you manage memory yourself
Sure. I mean Rust lifetime discipline is "achievable" in C too, so long as you're very very careful.
> Lifetimes in Cyclone seem the best example of PL research in the last 50 years you have there, as it’s only 20 years old.
It typically takes 10+ years for PL research to go from papers to research languages to being incorporated into"real" languages.
> More research is probably required.
Always.
This is like when I hear people claim that physics has not advanced in the last 50-70 years.
FP is also particularly well suited for cloud computing and parallel computation.
> Very little innovation in programming languages has happened regarding new realities at the hardware level especially transition from serial to parallel execution
But, as always, the sufficiently smart compiler never shows up. So we're left with the humans doing the tuning, and as you say, FP is kind of antithetical to that approach.
C compilers don’t produce 100% optimal assembly language in all cases, but typically the assumptions they make are light. The executable code they output is somewhat predictable and often close enough to hand-optimised assembly in efficiency that we ignore the difference. But this whole approach to programming was originally designed for single-threaded execution on a CPU with a chunk of RAM for storage.
What happens if we never find a way to get a single core to run much faster but processors come with ever more cores and introduce other new features for parallel execution? What happens if we evolve towards ever more distributed systems, but farming out big jobs to a set of specialised components in the cloud at a much lower level than we do today? What happens if systems start coming with other kinds of memory that have different characteristics to RAM as standard, from content-addressable memory we already have today to who-knows-what as quantum technology evolves?
If we change the rules then maybe a different style of programming will end up being more efficient. It’s true that today’s functional programming languages that control mutation and other side effects usually don’t compile down to machine code as efficiently as a well-written C program can. The heavier runtimes to manage responsibilities like garbage collection and the reliance on purely functional data structures that we don’t yet know how to convert to efficient imperative code under the hood are bottlenecks. But on the other hand, those languages can make much stronger assumptions than a lower-level language like C in other ways, and maybe those assumptions will allow compilers to safely allocate different behaviour to new hardware in ways that weren’t possible before, and maybe dividing a big job into 500 quantum foobar jobs that each run half as fast as a single-threaded foobaz job still ends up doing the job 200x faster overall.
Lol, since when? C compilers literally will run some of your code at build time, and only write the results into the binary and they do all sort of crazy "mental gymnastics" to make people believe it is still a dumb single-pass compiler.
I am (perhaps obviously) biased, here, but I tend to just roll my eyes whenever any of my colleagues suggests we should use functional programming to solve a problem. There are actually very few real-world use cases where it's objectively better.
It’s not just you. Functional Programming really does not adequately solve any of the problems that its advocates claim while refusing to provide any evidence.
And it’s not “biased” to write these claims off.
And yet, without any substance, the debate rages.
Nobody asked (until now, so thank you for asking!), and this is a fairly well discussed topic for anyone who cares to search!
You will probably get a lot of slightly different answers depending on who you ask or where you look, but I think a very strong common thread is "referential transparency". Functional programming gives you that, and that is the property that makes FP particularly well suited for parallel computation. Referential transparency is related to the concept of "function purity" (in the sense that either one usually guarantees the other), which you will often hear people talk about as well. The two concepts are so intimately tied that sometimes I wonder if they're two different perspectives on the same thing.
This, along with the fact that FP has been an active area of research (an important part of innovation) for a long time, is why I brought it up.
https://en.wikipedia.org/wiki/Functional_programming
https://en.wikipedia.org/wiki/Pure_function
https://en.wikipedia.org/wiki/Referential_transparency
https://softwareengineering.stackexchange.com/questions/2938...
---
> programmers can just use functions to code and end up with functional programming, it isn't an obscure style
That's not how it works. Note that functional programming has nothing to do with merely "writing functions".
---
> without any substance, the debate rages
The substance is there and there is plenty of it, but learning requires work.
Isn't referential transparency (the property of a function that allows it to be replaced by its equivalent output) a consequence of function purity? In other words: could a pure function not be referentially transparent?
Also, I remember Robert C. Martin describing the functional programming paradigm as a "restriction upon assignment". I kind of like this definition as the rest seems to flow from it: if you can't assign, you can't mutate. If you can't mutate, you have pure functions, which are referentially transparent.
Yes there are pure functions which are not referentially transparent. A pure function with side effects, such as printing a result to standard output, is not referentially transparent. You can't replace the function with it's return value, since that doesn't replicate the printing side effect.
But not all FP languages have to be so puritan to only allow pure functions, most have escape hatches and it is just good form to prefer purity (even in more mainstream languages!). The most common way to circumvent this problem is through a Monad, which very naively put, just a description of the order of side-effecting functions, and their inter-dependencies. This will later get executed at a specific place, e.g. the main function -- the point is, that a large part of the code will be pure, and much easier to reason about.
-Haskell is faster than C (lol)
-FP gives you free concurrency
-FP makes code more testable
-FP is easier to read
-FP is easier to consume for people
-FP results in no bugs
-FP is easier to change
-FP will literally suck your peepee
-Actually FP is the second coming for Christ
It’s really funny how you also pretend you’ve never heard of all the silver bullet claims that are incessantly plaguing every programming forum.
What’s also really funny is your multiple alt accounts manipulating your votes. You must be real secure in those those claims.
Not that that matter because all of those claims are demonstrably false anyway!
> -Actually FP is the second coming for Christ
On a style point, you've rather undermined yourself that these are common claims because there are entries on this list that are clearly fabricated, as well as others that look like wilful misinterpretations of what someone else said. That casts doubt on the more reasonable entries. There are annoying FP evangelists out there, but the overall tone pattern matches straw-manning.
You'd have made it easier for everyone taking the whole list seriously. Transparently mixing fact and fiction just makes it harder for people who aren't already part of a conversation.
> -Haskell is faster than C (lol)
If they regularly claim that you should easily be able to point to several recent examples. Can you?
They absolutely solve real issues, and it's just sticking your head into sand to say otherwise.
All problems that can be solved with code are math problems. Proofs and programs are isomorphic (see the Curry-Howard correspondence).
---
Edit: this is a factually accurate comment, delivered dispassionately. It's not controversial or new-- it's something we've known for longer than the C language has existed. Why the downvote? Like I said, see this: https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
In your example, the two things are separated by at a minimum one layer of emergence: your example is more like saying biology is just chemistry. In maths and programming, they are both at the same level, no emergence.
I also haven’t found what you say to be true at all— As I’ve been learning more maths and more programming, and learning more about the link between the two, I have found that the ability to see problems from more than one angle has had a dramatic impact on how clearly I think and how efficiently I solve problems. Not useless whatsoever.
But that's quite different from your other claim. Maths and programming are not at the same level. When one writes a "hello world" program, math does not figure into the final text of the code at all. Similarly, when one writes code to implement a system interacting with multiple dependencies, one is not doing mathematics, except in the trivial sense of your original comment. That is to say, at such a remote distance that it's meaningless to describe the activity as a mathematical one.
I definitely see the parallel, but I'm not actually sure this is true.
A lot of the deep functional stuff I'm learning right now are more about finding connections and shortcuts between things that we used think were different.
For me, comparing functional programming to older languages is more like comparing "tally marks" or "roman numerals " to a modern "place value system".
Now back to the physics analogy. The gap between quantum physics and chemistry is both a theoretical and computation limit.
There are also seen to be very distinct layers where the lower level don't seem to correlate with higher levels.
But I can also see this might apply to the Curry-Howard correspondence.
Hmmm. I have to think about it more...
First, not all problems that can be solved with code are math problems. Take driving a serial port, for instance. There might be some aspects of it that are mathematical, but mostly it's a matter of interfacing with the chip spec.
Second, even for problems that are isomorphic to a math problem... the thing about isomorphisms is that they aren't identical. One form or the other is often easier to deal with. (That's one of the reasons we care about isomorphisms - we can turn hard problems into easier ones.)
Well, which is easier, writing programs or doing proofs? Almost always, writing programs is easier. This is why it's (almost) completely irrelevant.
Nobody wants to write code that way. So nobody cares. They're not going to care, either, no matter how forcefully you point out Curry-Howard.
Now, as you say elsewhere, you can gain insights from math that can change your code. That's true. But I suspect that most of the time, you don't actually write the code as a proof.
It served its purpose, but we've outgrown it.
Also, just think about all the optimizations your "serial" programming language does -- are your yourself really write all those mutations? Or is that the compiler, that in many cases can do a much better job? Now what if the language's semantics allowed even more freedom for the compiler in exchange for more restrictions on the language? Sure, we still don't have "sufficiently advanced compilers" that would replace programmers, but FP languages absolutely trade blows with most imperative languages in many different kinds of problems. Very visibly when parallelism comes to the picture, as it turns out, a smart parallel-aware data structure will easily beat out their serial counterparts here.
Yes. Yes, it is because all of that rescheduling and reordering is completely hidden at great effort and expense to make it seem like the instruction stream is executing in exactly in the order specified. If it weren't, lines of code would essentially execute in an indeterminate order and no programs would function.
As I understand it, Futhark aims to leverage GPUs in particular, and that approach seems to be what makes it unique within the category of FP languages?
The Futhark programming model is standard functional combinators: map, reduce, scan, etc. You can do that in any Functional language, and it is mostly trivial to rewrite a Futhark program in Haskell or SML or OCaml. Futhark removes a lot of things (like recursive data structures) to make efficient parallel execution easier (and even possible), and adds various minor conveniences. But you don't really need to add something for functional programming to be suitable for parallelism; you just have to avoid certain common things (like linked lists or laziness).
And it's not like every academic idea that worked in a paper has worked as well as hoped when someone tried to turn it into a production-quality ecosystem.
I've always assumed that, by now, I would be able to write code, in a semi mainstream language, and it would be made somewhat parallel, by the compiler. No need for threads, or me thinking of it.
There's projects like https://polly.llvm.org, but I guess I assumed there would be more progress through the decades.
[1] https://en.wikipedia.org/wiki/Embarrassingly_parallel#:~:tex....
The other big impossible task is that most code isn't written to be able to take advantage of theoretical autoparallelization--you really want data to be in struct-of-arrays format, but most code tends to be written in array-of-struct format. This means that vectorization cost model (even if proven, whether by user assertion or sufficiently smart compiler, legal) sees it needs to do a lot of gathers and scatters and gives up on a viable path to vectorization really quickly.
And the majority of software we've inherited is written this way.
In the 90s this didnt matter, since dereferencing a pointer was comparably expensive to arithmetical operations. But with modern CPUs with massive caches and more native parallelisation, the difference is dramatic.
So, even now, the majority of languages we're using; and almost all code we've inherited today, are as far away as you can get from efficiently using modern CPUs.
The task is first to change all these languages to enable ergonomic programming without tons of indirection -- we're very far away from even providing basic tools for performant code
Some of the SIMD operations feel very reminicent of APL primitives
I wanted to point towards a programming paradigm that's approach enables you to take advantage of the parallel execution possible within chips today due to the notation being both precise in intent yet vague in execution. Take summing an array (`+/vector`) or selecting values given a boolean mask (`mask/values`) - both these very simple expressions are expressible directly in SIMD instructions, as there's no for loop index enforcing an order.
As you noted, polyhedral compilers work on a pretty restricted subset of programs, but are fairly impressive in what they do. There has been research on distributed code generation [1] as well as GPUs [2]. While there has been work on generalizing the model [3], I think the amount of parallelization that a compiler can do is still very limited by its ability to analyze the code (which is to say, highly restricted).
Then you've got a large class of data-parallel-ish constructs like Rayon [4] as well as executors which may work their way into the C++ standard at some point [5]. How much safety these provide depends greatly on the underlying language. Generally speaking, the constructs here are usually pretty restricted (think parallel map), but often you can write more-or-less arbitrary code inside, which is often not the case in the polyhedral compilers.
If you don't care so much about safety and just want access to every parallel programming construct under the sun, Chapel [6] may be interesting to you. There is no attempt here, as best I can tell, to offer any sort of safety guarantees, but maybe that's fine.
On the other end of the spectrum you have languages like Pony [7] that do very much care about safety, but (I assume, haven't looked deeply) this comes with tradeoffs in expressiveness.
(I work in this area too [8].)
Overall, there are some very stringent tradeoffs involved in parallelizing code and while it certainly has been and continues to be a very active area of research, there's only so much you can do to tackle fundamentally intractable analysis problems that pop up in the area of program parallelization.
[1]: https://www.csa.iisc.ac.in/~udayb/publications/uday-sc13.pdf
[2]: https://arxiv.org/pdf/1804.10694.pdf
[3]: https://inria.hal.science/file/index/docid/551087/filename/B...
[4]: https://docs.rs/rayon/latest/rayon/
[5]: https://github.com/NVIDIA/stdexec (disclaimer: I did a quick Google search on this, not 100% sure this is the best link)
Mutation (and other effects) makes the order of computations important. If you're writing to and reading from variables, the compiler is not free to move those operations around, or schedule them simultaneously.
And you probably don't want to be rid of all mutation. So what if you separated the mutating from the non-mutating? Well you'd need a sufficiently powerful type system. Likely one without nulls - as they can punch a hole through any type checking.
If you want this stuff in the mainstream, you at least have to get all the nulls and mutation out of the mainstream, which I don't think will happen.
The industry for the most part heeded "goto considered harmful" (1968), but hasn't done so with "the null reference is my billion dollar mistake (2009)". Maybe we just have to wait.
* Go, with goroutines and heavy use of channels.
* Rust which is free of data races and generally improves the safety of multithreaded programming via Sync, Send and just safer APIs (e.g. Mutex).
* Chapel, which is a language designed primarily for multithreaded and multiprocess computing.
Those are just the ones I know about. There's obviously way more.