News for hackers. Stuff that matters.
Re:Static torrent website with peer-to-peer queries over Bit... by octoberfranklin on Wednesday March 09, 2022 @02:37AM (#30611891)
This approach to mobile code in functional languages has been tried repeatedly since the 1990s.

> each function is identified by a hash of its AST.

That encoding for mobile code only works if the expression has no free variables (i.e. is closed).

It turns out that it is surprisingly difficult to write code which you can be sure has no free variables at particular points (the "send this code to another machine for execution" points). Especially in functional languages. If you write a higher-order functional, you know nothing about the closedness of its argument. If you require that all function arguments be closed it breaks all the useful functional programming techniques. The only way to make it workable is to check closedness only on those values which need to be mobile.

If you do the closedness-check at runtime, toy examples will work fine and the technique looks quite powerful, but once your codebase gets to a meaningful level of complexity it turns into a game of whack-a-mole with closedness heisenbugs. You quickly discover that closedness is data-dependent.

In order to check closedness statically you need quite a sophisticated system of modal types. MetaOCaml was the most usable result of all this research:

https://okmij.org/ftp/ML/MetaOCaml.html

The important upshot here is that this isn't just some check you can slap onto the compiler. The programmer has to think about these types, and craft them carefully, as an integral part of the programming process. Basically you aren't just writing a program, you're writing a program plus a proof that it won't try to mobilize open code. Writing formal machine-checked proofs is not something that most programmers are good at.

Re:Static torrent website with peer-to-peer queries over Bit... by reggieband on Wednesday March 09, 2022 @02:03PM (#30618636)
I agree a complete system capable of something as magical sounding as I described would be both extremely complex to implement and probably even a nightmare to program within.

As to the specific discussion of free variables and open/closed arguments, I have to admit I have no background or education in the theory behind programming languages. Other than going through about 50% of SICP about a decade ago, I also have very little experience with functional languages.

What has been fuelling this interest lately is learning a bit more about stack based languages like Forth. My extremely primitive understanding of such programming models suggests that a function/word in that kind of programming context is closed over some defined portion of the stack. So my naive mind considers that one could grab as much stack as necessary along with the word to be executed and just pipe that over to some other execution context. Of course, details matter and there are probably several important ones that I haven't even considered that would make this naive assumption border on impossible. However, it at least seems more reasonable to attempt than crawling through a heap trying to gather everything.

Re:Static torrent website with peer-to-peer queries over Bit... by pharmakom on Wednesday March 09, 2022 @08:34AM (#30614219)
Would it be possible to copy any captured variables with the function? I’m sure smart people have figured out why this wouldn’t work.
Re:Static torrent website with peer-to-peer queries over Bit... by jlokier on Wednesday March 09, 2022 @11:07AM (#30616017)
In pure functional programs it's possible to copy the state (monad/environment/free variables), but it's not always efficient, depending on what those are.

In general programs, doesn't have to be functional, the environment is stateful and often has abstract, black box processes. This can be transferred as well, by copying some things, transforming others, and in general where necessary using a two-way pipe of some kind. By analogy, imagine creating a WebSocket at the same time as making a JSON-RPC call.

Except for the black boxes, this kind of transfer can be taken further to make a general distributed system. Think things like Paxos, Raft, CRDTs. If the data is also mobile to where it is used, this performs well for many tasks. When that is done, in some ways everything comes back to messages and state again and doesn't need specific pipes. That's more robust then the simple form of transfer.

The resulting architecture is often much faster than the non-distributed version for many tasks, and robust, but it takes a lot of tricky parts to make a general purpose architecture with those qualities and stay high performance.

Re:Static torrent website with peer-to-peer queries over Bit... by octoberfranklin on Wednesday March 09, 2022 @02:15PM (#30618757)
It's not a question of efficiency. You can copy values but you can't copy unbound free variables.
Re:Static torrent website with peer-to-peer queries over Bit... by jlokier on Friday March 11, 2022 @03:53AM (#30637786)
> you can't copy unbound free variables.

You can copy them in a pure functional program if the function AST you're transporting is sufficiently expressive, because the values of the unbound free variables in pure FP are available at the point where the function is defined, so can be inlined into it, and included in its hash.

But when it's not pure FP, then indeed you can't copy the values into the function AST, because the environment at the point of each call to the function is what matters.

(The pipe stuff is just for making it more efficient, and handling black boxes which sit outside the paradigm of concrete values, things like I/O monads and devices).

Re:Static torrent website with peer-to-peer queries over Bit... by octoberfranklin on Wednesday March 09, 2022 @02:13PM (#30618732)
How do you copy a variable? You can only copy values. A free variable has no value. You're confusing capture with closedness.

Here's a trivial example:

  \f -> \y -> (runRemotely (\x -> f y x))
The expression passed to runRemotely has a free variable "y". How are you going to serialize (\x -> f y x) in order to send it across the network? When you hit the "y", what are you going to do?

For this trivial minimalist example you might cook up a one-off hack like lambda-abstracting the free variables in the runRemotely expression and then reapplying to the returned value, but there are much more complicated and insidious examples where these workarounds don't work.

Re:Static torrent website with peer-to-peer queries over Bit... by pharmakom on Thursday March 10, 2022 @02:54AM (#30624309)
I was talking in the context of pure functional programming. You can send the AST of a lambda.
Re:Static torrent website with peer-to-peer queries over Bit... by octoberfranklin on Friday March 11, 2022 @07:05AM (#30638850)
THERE IS NO LAMBDA.

It's a free variable, not a variable bound by a lambda.

Re:Static torrent website with peer-to-peer queries over Bit... by beecafe on Friday March 11, 2022 @07:16AM (#30638911)
Use typed holes
Re:Static torrent website with peer-to-peer queries over Bit... by octoberfranklin on Saturday March 12, 2022 @10:05AM (#30651848)
You can't serialize holes. You can't even compare them for equality (partly because it is far from clear what that should even mean).