News for hackers. Stuff that matters.
Re:Clio: A functional, distributed programming language that... by crowdhailer on Thursday March 18, 2021 @10:32AM (#26503094)
I'm struggling to get my head around why this is a distributed programming language.

I saw the await key word for parallel fib but would like a bit more information about what's actually happening to be parallel.

Re:Clio: A functional, distributed programming language that... by dvh on Thursday March 18, 2021 @07:19AM (#26501517)
I made something similar (temporal distribution rather than spatial) an it was 70x slower than javascript, how slow compared to JS is clio?
Re:Clio: A functional, distributed programming language that... by speedgoose on Thursday March 18, 2021 @08:13AM (#26501840)
I wrote the fib example in plain JavaScript without async, just old recursively in a loop, and it ran twice as slow compared to Clio.

It's not a very high quality benchmark, but the overhead doesn't seem bad on tiny examples.

Re:Clio: A functional, distributed programming language that... by SamBam on Thursday March 18, 2021 @08:41AM (#26502044)
Since Clio compiles to JS, that speed up must be available in vanilla JS as well.

Is it the use of web workers that makes that twice as fast?

Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @08:43AM (#26502067)
Clio has automatic parallelisation. JavaScript does not.
Re:Clio: A functional, distributed programming language that... by mcherm on Thursday March 18, 2021 @08:52AM (#26502142)
How is generation of fibonacci numbers parallelized? I mean, I can think of some ways to do it but I have trouble believing that any compiler could generate them.
Re:Clio: A functional, distributed programming language that... by cepher on Thursday March 18, 2021 @01:00PM (#26504790)
I know that a parallel prefix algorithm [1] can be used to calculate fib(n), since we can use repeated matrix multiplications (a formulation appropriate for a prefix sum algorithm). The computation time can be O(n/p + log p), where p is the number of processors. However, I’m not sure what other approaches there are.

[1] https://en.m.wikipedia.org/wiki/Prefix_sum

Re:Clio: A functional, distributed programming language that... by wccrawford on Thursday March 18, 2021 @09:18AM (#26502338)
So far as I can tell, they typically "parallelize" it by not memoizing it. It looks like they actually calculate the whole thing recursively, twice.

That said, I found a parallel solution that was interesting and should provide a speedup, but with a large increase in complexity of the code.

https://stackoverflow.com/a/16464865/388173

Re:Clio: A functional, distributed programming language that... by nonameiguess on Thursday March 18, 2021 @10:24AM (#26503001)
Great link and I like the mention of the fact there is actually an analytical formula for the Fibonacci number as well that allows computing it in constant time. Unfortunately, machine precision issues make it nearly impossible to accurately calculate anything large enough to be worth the speedup you get as there is no practical way to store enough of the digits in square root of 5, so you need a symbolic algebra implementation that can compute an exact answer and reduce it to a natural number.
Re:Clio: A functional, distributed programming language that... by vlovich123 on Thursday March 18, 2021 @06:41PM (#26508315)
Why symbolic algebra vs infinite precision floating point which is comparatively much cheaper computationally (& memory wise too?)?
Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @08:55AM (#26502158)
> How is generation of fibonacci numbers parallelized?

Not sure if you're joking or not? Fib is the classic first parallel benchmark, especially for functional languages. The two tasks in each step are embarrassingly parallel.

> I have trouble believing that any compiler could generate them

Hah! I'd say I'd have a hard time believing compilers can automatically parallelise anything else... because fib is usually the only thing they're shown being able to do!

Re:Clio: A functional, distributed programming language that... by spenczar5 on Thursday March 18, 2021 @11:34AM (#26503731)
Uh, Fibonacci is not embarrassingly parallel. That term has a precise technical meaning; it is that the parallel processes have no dependencies and require no communication.

Fibonacci computations depend upon prior results, which is why it is a poor fit for parallelization in general. While, yes, it is possible to fork on every recurrence and join to wait for the result, the overhead of that is gigantic and dwarfs any benefits.

Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @11:47AM (#26503892)
> Fibonacci is not embarrassingly parallel

Just take a look at the code we’re talking about yourself. See the operator a + b between the two recursions? There are zero data or control dependencies between a and b. They can be perfectly distributed, which is why it’s been used as an example here.

Also read the note directed at the 'algorithms police' here https://cilk.mit.edu/programming/ which I think will pre-empt the point you're going to make next.

Re:Clio: A functional, distributed programming language that... by spenczar5 on Thursday March 18, 2021 @10:13PM (#26509604)
Okay, so let's look at fib(5).

It starts two tasks, fib(4) and fib(3). It waits for them to complete. There are now 3 tasks, but 2 are running.

fib(4) starts two tasks, fib(3) (second edition) and fib(2). It waits for them to complete. There are now 5 tasks (fib(5), fib(4), fib(3), fib(3), and fib(2)), and 3 are running (fib(3), fib(3), and fib(2)).

fib(3) (the first one) starts two tasks, fib(2) and fib(1). It waits for them to complete. 7 tasks, 4 are running.

fib(3) (the other one) starts fib(2) and fib(1). It waits for them to complete. 9 tasks, 5 are running.

We keep going like this. Notice how many tasks are not running at any given time because they depend upon other tasks to complete. This is nowhere near an embarrassingly parallel problem.

For an actual embarrassingly parallel problem, consider something like "this 1GB slice of memory contains a continuous sequence of 64-bit floating point numbers. Please square each number in place."

This can be divided among any number of processes trivially, with actually zero coordination.

There's also "nearly embarassingly parallel," where a minor amount of coordination is required in a final step. You can parallelize "compute the max of an array of integers", for example, by splitting it into N chunks, having each one compute their own max, and then taking the max of the maxes.

But Fibonacci is nowhere close to those.

Re:Clio: A functional, distributed programming language that... by throwaway4good on Thursday March 18, 2021 @09:22AM (#26502373)
Really? Can you expand on that? I have seen Fibonacci being the poster child of the usefulness of memoization and maybe tail recursion, but never parallelization.
Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @09:43AM (#26502594)
> I have seen Fibonacci being the poster child of the usefulness of memoization and maybe tail recursion, but never parallelization.

That baffles me. I think I've hardly read a paper on parallel functional programming that doesn't start with fib.

Here's example that agrees that it's the hello-world of parallelisation.

https://wiki.haskell.org/Haskell_for_multicores

It's trivial for a compiler to automatically parallelise it - for every binary operator evaluate the two operands in parallel - done.

Re:Clio: A functional, distributed programming language that... by johnday on Thursday March 18, 2021 @10:52AM (#26503295)
The reason `fib` is a useful benchmark here is not because `fib` is an inherently parallel problem, but because the functionality is obvious and it's easy to parallelise.

Computing fib with memoisation from 1 will certainly be faster than (parallel) recursion without memoisation and data sharing.

Re:Clio: A functional, distributed programming language that... by firebacon on Thursday March 18, 2021 @11:06AM (#26503444)
Interesting to consider the total complexity of that approach though.

An iterative fibonacci solution runs in linear time. Calculating the N'th fibonacci number requires O(N) serial operations.

A fully parallel, recursive solution without memoization requires that each value in the sequence is computed more than once. Consider the example of fib(4):

   fib(4) = fib(3) + fib(2)
   fib(3) = fib(2) + fib(1)
   fib(2) = fib(1) + fib(0)
You can see, that if we run this in parallel, the value of fib(1) has to be calculated twice. As the tree of operation branches out, more and more duplicate calculations are required.

A quick google suggests that the time complexity of the recursive approach is O(2^N).

Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @11:15AM (#26503540)
> An iterative fibonacci solution runs in linear time.

Absolutely nobody is under the impression that the naive parallel implementation of fib is actually useful code or the most efficient way to do it. You're missing the point if you're suggesting a different way to do it in the first place.

It's just something to use as a running example... like on the original article this whole thread is about.

Re:Clio: A functional, distributed programming language that... by SamBam on Thursday March 18, 2021 @01:06PM (#26504880)
Ok, but it's a bit odd that you kept reacting with incredulity at people not knowing that fib was THE parallel example to know, and then it turns out it's a poor example because synchronous fib with memoization (which is the way many people learn it in any early CS class, and which wouldn't be possible async) is so much faster.

I think maybe if there hadn't been such a vibe of "what, you don't know X?!?" then it would have just been an interesting fact to mention that parallelization demos often use fib, because it's an easy example to grok (though a confusing one if you already understand the faster method).

Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @08:14AM (#26501849)
This language compiles to JavaScript, so it's 0x slower than JavaScript. Comparing similarly named functions between Clio and vanilla JS obviously wouldn't be fair as the feature-set between the two are not equal.
Re:Clio: A functional, distributed programming language that... by elwell on Thursday March 18, 2021 @09:00AM (#26502192)
The benchmark should be based on idiomatic code in both languages for a same (or similar) input -> output.
Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @09:20AM (#26502354)
You could do that but then your comparison is obviously biased and not very useful.
Re:Clio: A functional, distributed programming language that... by dandellion on Thursday March 18, 2021 @09:25AM (#26502410)
Picking a language is very subjective, so that's exactly the kind of biased comparison that I want to judge something like this.
Re:Clio: A functional, distributed programming language that... by kangalioo on Thursday March 18, 2021 @09:24AM (#26502390)
Arguing that two programming languages must be considered to have the same performance just because they compile down to the same technology, is flawed.

Otherwise you couldn't make performance comparisons between C, Rust, Go, Haskell, Julia, because they all compile to assembly

Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @09:26AM (#26502423)
I'm not saying you can't, I'm saying that since the code that eventually gets executed the same way just one layer down, it's not useful to JUST consider the performance.

You're not using TypeScript to get faster JS execution. You're using TypeScript to get types in JS. Compare development speed and avoiding bugs together with performance in that case. Same for Clio.

Re:Clio: A functional, distributed programming language that... by spenczar5 on Thursday March 18, 2021 @10:07AM (#26502825)
Ok, but I still want to know how much of a performance tax I am paying to know whether it’s the right tool for the job. If it’s a thousand times slower, maybe that overwhelms the benefits of extra features.
Re:Clio: A functional, distributed programming language that... by Fellshard on Thursday March 18, 2021 @11:44AM (#26503847)
And what if every statement I write in the upper language compiles down to one loop that runs a hundred times? The target language is a lower bound, not an upper bound.
Re:Clio: A functional, distributed programming language that... by path411 on Thursday March 18, 2021 @01:27PM (#26505171)
Every language compiles to assembly so it must be as fast as assembly?
Re:Clio: A functional, distributed programming language that... by ubertaco on Thursday March 18, 2021 @08:24AM (#26501912)
As a heads up, on the front page for the language (https://clio-lang.org/), there's a "Visit our tutorial page" link that 404's. There is a tutorial though, if you go to the "Learn" link, so prolly the other link just needs to be updated.
Re:Clio: A functional, distributed programming language that... by coolreader18 on Thursday March 18, 2021 @03:47PM (#26506762)
Hmm, I'm not sure about this at the moment, at least based on the available documentation - the first thing I tried to do was extend the "parallel fib" example to be fully parallel inside `fib` itself[0] but I wasn't able to figure out how to create a `sum :: [int] -> int` function at first (it wasn't clear that arrays are just JS Arrays, and I can just call methods on them) and I'm still not sure why my code doesn't output anything.

[0]: https://clio-playground-pouyae.vercel.app/ with code:

    fn fib n:
      if n < 2: n
      else: [n-1 n-2]
        -> * await |fib|
        -> *
          console.log
          sum

    fn sum arr:
      arr.reduce add 0
    fn add a b:
      a + b

    export fn main args:
      [5 6]
        -> * await |fib|
        -> * item: console.log item
Re:Clio: A functional, distributed programming language that... by avinassh on Thursday March 18, 2021 @08:55AM (#26502157)
What is a distributed programming language?
Re:Clio: A functional, distributed programming language that... by keithalewis on Thursday March 18, 2021 @11:13AM (#26503519)
A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable. - Leslie Lamport
Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @09:23AM (#26502385)
Distributed computing is when you take a bunch of tasks one computer (or CPU/computing units of choice) usually do and spread it out to many computers (or CPU/computing units of choice). This is to give faster execution compared to if you did the work sequentially and is generally a pattern that is gaining more and more popularity as of late.

A distributed programming language in this context means that the programming facilitates this paradigm so it's easy to do distributed programming with the language. In the case of Clio, it also means it is distributed by default, so you write code like normal and it's executed in a distributed fashion.

Re:Clio: A functional, distributed programming language that... by mirekrusin on Thursday March 18, 2021 @04:43PM (#26507333)
btw. julia implements fantastic idea in its ssh cluster manager - such a simple thing yet so powerfull; without knowing much about the language I was able to distribute some computation across all computers I had at home, really awesome. As a side note it was also so easy to drop it on GPU. I'm really impressed by julia, I'd love to use it more at work.
Re:Clio: A functional, distributed programming language that... by toolslive on Thursday March 18, 2021 @07:46AM (#26501670)
I couldn't find any information on the type system, But by the look of it, there's no type inference. Is that correct?
Re:Clio: A functional, distributed programming language that... by zemnmez on Thursday March 18, 2021 @08:22AM (#26501898)
How do you make a parallel language that transpiles to a reentrant one?
Re:Clio: A functional, distributed programming language that... by twiss on Thursday March 18, 2021 @08:27AM (#26501932)
Re:Clio: A functional, distributed programming language that... by brundolf on Thursday March 18, 2021 @01:45PM (#26505377)
To get more specific for those who may not be as familiar with the nuances of JS: JS can start parallel threads, it just - importantly - cannot share memory between them (instead it must pass messages, copying data at boundaries). This eliminates a large number of benefits and usecases that tend to be associated with "multithreaded programming", but saying JS "isn't multi-threaded" isn't quite true.
Re:Clio: A functional, distributed programming language that... by twiss on Thursday March 18, 2021 @02:01PM (#26505544)
For what it's worth, there's some limited ability to share memory (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...), though you can only share binary data, not other types, and it only works in secure and cross-origin isolated contexts, due to security concerns.

That being said, at first glance it doesn't look like Clio is using this, instead it's passing messages as you suggest. It might actually be interesting to use SharedArrayBuffers as a compilation target, as they're probably hard to use correctly manually. That being said, WebAssembly threads (https://github.com/WebAssembly/threads) may be more appropriate for this.

For completeness, Workers can also transfer memory (https://developer.mozilla.org/en-US/docs/Web/API/Transferabl...) with less security restrictions. They can also collaborate by accessing a shared database (https://developer.mozilla.org/en-US/docs/Web/API/IndexedDB_A...) though this is obviously slower than shared memory.

Re:Clio: A functional, distributed programming language that... by chrisseaton on Thursday March 18, 2021 @08:25AM (#26501921)
Can you use the Web Workers API and lower to a message passing model?
Re:Clio: A functional, distributed programming language that... by cies on Thursday March 18, 2021 @09:23AM (#26502383)
> Suitable for scientific programming

How's that possible? JS does not have a good reputation in sci prog, why would clio have?

Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @09:25AM (#26502403)
Because Clio is not JS, it compiles to JS?

There is plenty of ways of making JS handle any "scientific programming" you can throw at it. It'll probably run slower than what you can do by default in python-land or Julia, but since Clio seems to automatically parallize your code, it might have a chance.

Re:Clio: A functional, distributed programming language that... by cies on Thursday March 18, 2021 @10:50AM (#26503274)
Sorry that's just an unfair claim. With this explanation every general purpose programming language handles "scientific programming".
Re:Clio: A functional, distributed programming language that... by capableweb on Thursday March 18, 2021 @11:09AM (#26503478)
No, that's a weird conclusion if I ever saw one.

What can be claimed though is that any general purpose programming language "can be made to" handle scientific programming. I'm not saying you should, but it's possible for sure.

Libraries like big.js for example make arbitrary-precision decimal arithmetic possible on JS, which many considered impossible to do in JS.

Re:Clio: A functional, distributed programming language that... by hctaw on Thursday March 18, 2021 @11:39AM (#26503772)
I'd be interested to see at what scale parallel evaluation in Clio beats serial evaluation that has been compiled to native machine code with basic compiler optimizations, for scientific computing (say, solving nonlinear differential equations).

My guess is it's enormous, but I could be wrong since contemporary JS engines do quite well with numeric computing.

But there's a wealth of scientific computing that can't be magically made to be parallel and the parallel equivalents are often slower due to duplicated arithmetic and overhead in setting up the computation (recursive computations are particularly bad about this) - finding a parallel evaluation strategy that is actually faster is nontrivial.

It's really not a safe assumption that parallel = faster.

Re:Clio: A functional, distributed programming language that... by mgerullis on Thursday March 18, 2021 @10:55AM (#26503321)
V8 is quite a lot faster than python (in most comparisons, not all)
Re:Clio: A functional, distributed programming language that... by cies on Thursday March 18, 2021 @11:39AM (#26503780)
We're talking specifically about sci prog here. I think for one the ecosystem is just not there on JS.
Re:Clio: A functional, distributed programming language that... by Garlef on Thursday March 18, 2021 @11:03AM (#26503409)
isn't python fast because it uses specific c++ (or c?) modules in the background?

for example keras is a wrapper for tensorflow (c++). numpy relies on c if i understand this correctly.

Re:Clio: A functional, distributed programming language that... by hctaw on Thursday March 18, 2021 @11:42AM (#26503815)
I think it's more apt to say that Python isn't fast, but it has FFI that can be used to interface with things that are fast.

The same is true of JS though, and most interpreted languages that have an escape hatch for FFI. The difficulty of getting it to work may vary.

Re:Clio: A functional, distributed programming language that... by vmchale on Thursday March 18, 2021 @01:23PM (#26505117)
It sounds way too slow too.
Re:Clio: A functional, distributed programming language that... by efdb on Thursday March 18, 2021 @07:09AM (#26501469)
i really like the syntax, very intuitive use of ->
Re:Clio: A functional, distributed programming language that... by runeks on Thursday March 18, 2021 @11:14AM (#26503527)
I wonder if there’s such a thing as intuitive syntax.

As far as I can see, the arrow signifies function application. Why do you consider “a -> f” more intuitive than, say, “f(a)” or “f a”?

Re:Clio: A functional, distributed programming language that... by aloisdg on Thursday March 18, 2021 @11:35AM (#26503737)
because a -> f -> g -> h is better than h(g(f(a))). It is the functional way of doing the OOP fluent builder pattern: a.f().g().h()

It is the pipe operator (F#, Elixir, Haxe, etc.). There is a proposal to add it to js too.

Re:Clio: A functional, distributed programming language that... by mlajtos on Thursday March 18, 2021 @11:55AM (#26503978)
On top of that, it is a symmetrical to fat arrow functions, which is a shorthand for lambda:

fun: x => x * 2

res: 4 -> fun

Re:Clio: A functional, distributed programming language that... by vorticalbox on Thursday March 18, 2021 @03:05PM (#26506314)
I have always used ramdajs for this.

const R = require('ramda');

R.pipe(a,f,g,h)

Re:Clio: A functional, distributed programming language that... by nudpiedo on Friday March 19, 2021 @11:27AM (#26514414)
I got a bit late to the party, but I have to say it looks awesome. It seems an ML + APL descendant. Looking forward for more as I see they are puting good design and pragmatism together first.
Re:Clio: A functional, distributed programming language that... by transfire on Thursday March 18, 2021 @12:27PM (#26504372)
I just want to know what the `-> *` is all about. I assume `->` is a pipe like sugar, but what about the asterisk?
Re:Clio: A functional, distributed programming language that... by liminal on Thursday March 18, 2021 @02:52PM (#26506146)
I think I worked out it's an array.map function that takes the same three arguments: (value, index, array)
Re:Clio: A functional, distributed programming language that... by montebicyclelo on Thursday March 18, 2021 @11:55AM (#26503977)
Would be interesting to see a discussion of this vs Elm, which I guess is the incumbent functional programming language that compiles to Js (?).
Re:Clio: A functional, distributed programming language that... by lelanthran on Thursday March 18, 2021 @09:41AM (#26502568)
So many programming languages popping up like mushrooms overnight...

That does it - I'm creating my own programming language (again) which is going to be a mashup of C++ and Lisp; I shall call it "Thee-Pluth-Pluth".

Re:Clio: A functional, distributed programming language that... by dunefox on Thursday March 18, 2021 @11:17AM (#26503555)
Re:Clio: A functional, distributed programming language that... by egonschiele on Thursday March 18, 2021 @11:57AM (#26503992)
Is this a bad place to post my language that compiles to JS and PHP?

https://github.com/egonschiele/salty

Re:Clio: A functional, distributed programming language that... by dastx on Thursday March 18, 2021 @10:13AM (#26502883)
Don't forget the blackjack and hookers.
Re:Clio: A functional, distributed programming language that... by lelanthran on Friday March 19, 2021 @03:36AM (#26510843)
Actually, forget about the language.
Re:Clio: A functional, distributed programming language that... by wealthyyy on Thursday March 18, 2021 @11:26AM (#26503628)
I built my own language recently and called it Casi-no.
Re:Clio: A functional, distributed programming language that... by e-clinton on Thursday March 18, 2021 @07:24AM (#26501545)
Beautiful syntax indeed. Has a very rustie feel