This idea touches on (or rather, even expands on) an idea I've had brewing for a while. For those unfamiliar, there is a programming language called Unison [1] that has a nice feature where each function is identified by a hash of its AST. I often thought a cluster environment, maybe something BEAM-ish, would be an interesting idea where functions are retrievable based on a pair of (`func-name`, `hash`). You could have some kind of execution environment (maybe a lightweight process) that receives a hash identifying the function to execute and some pointer to the data (probably a URL) to act as input.
Given tech like described in the linked article, you could reasonably lookup such a function from a peer-to-peer network.
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:
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.
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.
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.
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).
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.
Comments
This idea touches on (or rather, even expands on) an idea I've had brewing for a while. For those unfamiliar, there is a programming language called Unison [1] that has a nice feature where each function is identified by a hash of its AST. I often thought a cluster environment, maybe something BEAM-ish, would be an interesting idea where functions are retrievable based on a pair of (`func-name`, `hash`). You could have some kind of execution environment (maybe a lightweight process) that receives a hash identifying the function to execute and some pointer to the data (probably a URL) to act as input.
Given tech like described in the linked article, you could reasonably lookup such a function from a peer-to-peer network.
1. https://www.unison-lang.org/
This approach to mobile code in functional languages has been tried repeatedly since the 1990s.
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.
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.
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.
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.
It's not a question of efficiency. You can copy values but 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).
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:
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.
I was talking in the context of pure functional programming. You can send the AST of a lambda.
THERE IS NO LAMBDA.
It's a free variable, not a variable bound by a lambda.
Use typed holes
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).