stinkey
Forum adept
- Joined
- Sep 8, 2020
- Messages
- 225
- Reaction score
- 74
Recursion.
Recursion.
Recursion.
Recursion.
In case you don't know what recursion is, here is a basic explanation: you split a problem into smaller and smaller pieces, one example being a tree with branches coming off from the main trunk and smaller branches coming off of those branches and even smaller branches coming off of the small branches, etc. Recursion is useful in many things, such as maze generation, and like the example above stated, tree generation.
Usually, when using recursion, you would make a function, and inside that function, you call that same function again. For example, in Python:
But how might you go about doing this in DF?
At first, this may seem simple. Just call a function over and over, right? I bet many people have actually done this before on DF.
But no, it is not that simple. One of the big, important parts of recursion is to avoid mutating state. This means that if I define a variable outside of a function and set it to "foo", then in a function I with "foo" as an argument, set that variable from the arguments to "bar", then return out of the function, the original variable will still be "foo" and not "bar" because whatever happened in the function does not affect things outside of it. The function should only take in arguments and spit out return values.
In DF, functions do not have arguments, nor do they have return values. This makes the only way to add an argument setting a variable outside of the function to some value, then accessing that variable while inside the function. The only way to add a return value is by setting a variable while inside of a function, then accessing that variable outside the function.
Most programming languages have scopes. Variables defined in functions cannot be accessed outside of them. Arguments are an example of this. However, DF does not really have scoping or any of this kind of thing; there are local variables, but functions and if-statements and loops act as jumps and not separate scopes, meaning local variables, while specific to the scope of the event, will still act as if the event were just one huge thread. Thus, recursion is impossible
Or is it?
Processes, when called, have a special tag. Local variables: Don't copy, copy, and share. If we were to set a local variable before calling this, then call a process with "copy", any actions performed on the variable in the process will not be reflected back in the main thread. This opens doors to many possibilities with recursion.
But not entirely.
Sure, making a flood-fill is much more easily done using this method, but what if, say, we wanted to invert a binary tree using recursion?
What a binary tree is, if you don't know:
Basically, there is a node, which stores its own value, and two other nodes, which then in turn store values and other nodes, like branches on a tree, in pairs of two. Thus, the name, "binary tree". When you "invert" a binary tree, you flip the left and right positions in each node, like this:
A simple binary tree inversion implementation in JavaScript:
Unlike the aforementioned flood-fill, the binary tree inversion requires you to not just call a function repeatedly, but also to return values from those function calls. How would we go about doing this in DF?
Easy: just set a variable at the end of the process, then access that variable in the main thread, right?
Nope. we already set the process scope to "copy" and not "share", meaning we cannot access variables from the process.
Then, set it to "share", right?
Yet again, no. This would mean we could not have the function arguments and scoping or absence of state mutation that is so crucial to recursion.
Thus, we come to the conclusion that without insane and unintuitive code, we cannot fully use recursion in DF.
This problem cannot be simply solved by adding function arguments and return values; it stems from the very way functions work in DF. Like I said before, they are like jumps and gotos, not actual functions, and lack a specific scope. Arguments would also work unintuitively; with the way DF currently works, this in essence would just be a hidden set var, doing nothing to help with the issue of scoping. Functions in DF can only mutate state, and even with an addition of return values because of the lack of scoping you would still be mutating state, only hidden by the return value.
Yes, you might be able to do some stuff with lists, though it would be needlessly complex and inefficient. If any of you can think of a better way, please do tell me.
Recursion.
Recursion.
Recursion.
In case you don't know what recursion is, here is a basic explanation: you split a problem into smaller and smaller pieces, one example being a tree with branches coming off from the main trunk and smaller branches coming off of those branches and even smaller branches coming off of the small branches, etc. Recursion is useful in many things, such as maze generation, and like the example above stated, tree generation.
Usually, when using recursion, you would make a function, and inside that function, you call that same function again. For example, in Python:
Python:
def myFunction(args):
if condition:
return
# do stuff to "args"
myFunction(args)
myFunction("foo")But how might you go about doing this in DF?
At first, this may seem simple. Just call a function over and over, right? I bet many people have actually done this before on DF.
But no, it is not that simple. One of the big, important parts of recursion is to avoid mutating state. This means that if I define a variable outside of a function and set it to "foo", then in a function I with "foo" as an argument, set that variable from the arguments to "bar", then return out of the function, the original variable will still be "foo" and not "bar" because whatever happened in the function does not affect things outside of it. The function should only take in arguments and spit out return values.
In DF, functions do not have arguments, nor do they have return values. This makes the only way to add an argument setting a variable outside of the function to some value, then accessing that variable while inside the function. The only way to add a return value is by setting a variable while inside of a function, then accessing that variable outside the function.
Most programming languages have scopes. Variables defined in functions cannot be accessed outside of them. Arguments are an example of this. However, DF does not really have scoping or any of this kind of thing; there are local variables, but functions and if-statements and loops act as jumps and not separate scopes, meaning local variables, while specific to the scope of the event, will still act as if the event were just one huge thread. Thus, recursion is impossible
Or is it?
Processes, when called, have a special tag. Local variables: Don't copy, copy, and share. If we were to set a local variable before calling this, then call a process with "copy", any actions performed on the variable in the process will not be reflected back in the main thread. This opens doors to many possibilities with recursion.
But not entirely.
Sure, making a flood-fill is much more easily done using this method, but what if, say, we wanted to invert a binary tree using recursion?
What a binary tree is, if you don't know:
Code:
1
/ \
2 3
/ \ / \
4 5 6 7Basically, there is a node, which stores its own value, and two other nodes, which then in turn store values and other nodes, like branches on a tree, in pairs of two. Thus, the name, "binary tree". When you "invert" a binary tree, you flip the left and right positions in each node, like this:
Code:
1
/ \
3 2
/ \ / \
7 6 5 4A simple binary tree inversion implementation in JavaScript:
JavaScript:
class TreeNode { // a class defining how the binary tree is layed out; this isn't the focus of what I'm trying to show, though
constructor(value, left, right) {
this.value = value; // the node's own value
this.left = left; // the node to the left and right
this.right = right;
}
}
function InvertBinaryTree(root) { // the actual function
if (root.value == null) return null; // stop if there are no more values to go through, so the function doesn't run indefinitely
let left = root.left;
let right = root.right;
root.left = InvertBinaryTree(right); // here, we use recursion by calling the function inside the function
root.right = InvertBinaryTree(left);
return root // return the flipped node
}Unlike the aforementioned flood-fill, the binary tree inversion requires you to not just call a function repeatedly, but also to return values from those function calls. How would we go about doing this in DF?
Easy: just set a variable at the end of the process, then access that variable in the main thread, right?
Nope. we already set the process scope to "copy" and not "share", meaning we cannot access variables from the process.
Then, set it to "share", right?
Yet again, no. This would mean we could not have the function arguments and scoping or absence of state mutation that is so crucial to recursion.
Thus, we come to the conclusion that without insane and unintuitive code, we cannot fully use recursion in DF.
This problem cannot be simply solved by adding function arguments and return values; it stems from the very way functions work in DF. Like I said before, they are like jumps and gotos, not actual functions, and lack a specific scope. Arguments would also work unintuitively; with the way DF currently works, this in essence would just be a hidden set var, doing nothing to help with the issue of scoping. Functions in DF can only mutate state, and even with an addition of return values because of the lack of scoping you would still be mutating state, only hidden by the return value.
Yes, you might be able to do some stuff with lists, though it would be needlessly complex and inefficient. If any of you can think of a better way, please do tell me.
Last edited:
Feathers McGraw
