I'm implementing a small recursive function that traverses a tree recursively. At some point in the traversal I need to set a flag, and it has to be accessible to other executions of the function. Since Zig doesn't support closures, is there a way to do this without using global variables, and without piping this flag in/out this recursive function?
#No closures - how to implement performant recursive function with non-global state?
white temple
If closures were supported I'd write this like:
pub fn doRecursiveStuff() {
var flag = false
const closure = () -> { ... }
closure()
}
faint stag
I often just write a _doRecursiveStuff helper which just additionally takes the state as an argument, in similar situations.
Ultimately though, that is the observation: you just pass the stuff through, which means you need to put the stuff somewhere.
Closures you return in languages that have them will generally heap allocate the state and then pass a pointer to that state through to the function when it calls it.
You generally have to allocate, because the closure being invoked might store a pointer to a piece of its data - thus it cannot move afterwards.
You could model a closure in a language like Zig like this, for example:
const Closure1 = struct {
func: *const fn(data: *Data, ...),
data: Data,
};
const Data = struct {
x: i32, // this is the variable that was captured, or whatever
};
Then it's just closure.func(&closure.data, ...) or whathaveyou.
It depends a bit on what you're actually trying to do though.
Funnily enough, this is actually rather like how std.mem.Allocator works.
Just that there, data: Data is data: *anyopaque.
...which is also what you'd need to do here if you wanted to store a list of closures, since every closure is different.
(Two closures could only really be the same otherwise if they captured the same state, and nothing else.)
But at this point, you're not really talking about a closure any more.
Ultimately, the problem being solved is just a question of "where does the captured data live?"
Which is just a data/memory management problem; adding functions to it kinda just complicates it unnecessarily.
If you can give me a more specific example of what closure might do in your example, then I could maybe make a more concrete example of how to translate it.
frail dust
I often just write a `_doRecursiveStuff` helper which just additionally takes th...
(the compiler sometimes does something like this, often with doThing wrapping doThingInner)
white temple
@faint stag this is very helpful, thanks! I was writing it using a global variable, but I think I might go with a private helper function. The thing is, in my case I need to pass this flag into every call of this function, but also return it, because it may have been updated. And then, if a node in the tree has multiple children, I need to take the resulting flag of the call for each child and use it as an argument to the next. it's a bit unwieldy compared to just using a global variable. Do you think using a global variable would be problematic?
faint stag
<@201094465815969794> this is very helpful, thanks! I was writing it using a glo...
I'd have to see more context to entirely judge that, but I might just pass a pointer to the flag down the callstack instead.
Relying on global vars breaks the minute you have threading, or if you want to have multiple unrelated invocations
white temple
I see. Here's the relevant code:
// Global flag on whether to clone the argument or use directly
var clone_arg = false;
/// Traverses an AST subtree, substituting occurrences of the specified variable with the given AST.
/// Makes copies of the argument AST when needed.
pub fn substitute(self: @This(), ast: *Ast, node_idx: Ast.NodeIdx, ident: Ast.SourceSlice, arg_idx: Ast.NodeIdx) Allocator.Error!Ast.NodeIdx {
clone_arg = false;
return self._substitute(ast, node_idx, ident, arg_idx);
}
fn _substitute(self: @This(), ast: *Ast, node_idx: Ast.NodeIdx, ident: Ast.SourceSlice, arg_idx: Ast.NodeIdx) Allocator.Error!Ast.NodeIdx {
var node = ast.nodes.slice().get(node_idx);
switch (node) {
.ident => if (std.mem.eql(u8, node.ident, ident)) {
// Substitute with the argument, cloning if needed
if (clone_arg) {
return try ast.cloneNode(arg_idx);
} else {
// Every subsequent time we encounter this ident we'll need to clone the argument
clone_arg = true;
return arg_idx;
// TODO: free ident node
}
},
.abstraction => {
const new_body_idx = try self.substitute(ast, node.abstraction.rhs, ident, arg_idx);
if (new_body_idx < Ast.NullNodeIdx) {
node.abstraction.rhs = new_body_idx;
}
},
.application => {
const new_func_idx = try self.substitute(ast, node.application.lhs, ident, arg_idx);
if (new_func_idx < Ast.NullNodeIdx) {
node.application.lhs = new_func_idx;
}
const new_arg_idx = try self.substitute(ast, node.application.rhs, ident, arg_idx);
if (new_arg_idx < Ast.NullNodeIdx) {
node.application.rhs = new_arg_idx;
}
},
.rule => {
std.debug.print("Error: can't substitute inside rule", .{});
},
}
return Ast.NullNodeIdx;
}
This is working nicely now - but maybe worth refactoring in the future to not rely on the global var
faint stag
I see. Here's the relevant code:
```rust
// Global flag on whether to clone the ...
I'm not 100% sure what precisely you're trying to accomplish, but in my estimation:
In this case, I would recurse into _substitute instead, and add a clone_arg: bool parameter to it.
As it stands, there's not much being added by the two functions because one just calls the other.
Then substitute just does
return self._substitute(ast, node_idex, ident, arg_idx, false);
// ^^^^^ this is the clone arg
Then if you recurse, you set it as appropriate.
To put it another way, the point of the outer function is to be a helper, because callers don't care about the clone detail - only the inner recursing part does.
white temple
_substitute would need to return an updated clone_arg to be passed to subsequent calls of _substitute as an argument. This would only be needed for the "application" case, which has two children