[QST] Recusively Generating AST Expressions (C++ libcudf)

[shriramch]

I would like to implement a function that can generate AST expressions, for example, by recursively converting a different expression class, such as an Apache Arrow arrow::compute::expression object, to a cudf::ast::expression object.

Is this even possible? libcudf's AST expression classes only accept references that are owned by the caller function; this is a problem since we can not recurse anymore. Is there any way to do this, to implement functions that can generate AST expressions instead of hardcoding expressions in a caller?

[bdice]

@shriramch You can use an owning object like a std::deque<expression> or std::list<expression> where references are stable (std::vector can reallocate and invalidate references). The lifetime of the AST expressions would then be tied to the lifetime of that container, and you can return it or pass it around.

[bdice]

For an example of constructing an expression tree, see this benchmark:

cudf/cpp/benchmarks/ast/transform.cpp

Lines 65 to 87 in 23bb2ed

	// Note that a std::list is required here because of its guarantees against reference invalidation
	// when items are added or removed. References to items in a std::vector are not safe if the
	// vector must re-allocate.
	auto expressions = std::list<cudf::ast::operation>();
	// Construct tree that chains additions like (((a + b) + c) + d)
	auto const op = cudf::ast::ast_operator::ADD;
	if (reuse_columns) {
	expressions.push_back(cudf::ast::operation(op, column_refs.at(0), column_refs.at(0)));
	for (cudf::size_type i = 0; i < tree_levels - 1; i++) {
	expressions.push_back(cudf::ast::operation(op, expressions.back(), column_refs.at(0)));
	}
	} else {
	expressions.push_back(cudf::ast::operation(op, column_refs.at(0), column_refs.at(1)));
	std::transform(std::next(column_refs.cbegin(), 2),
	column_refs.cend(),
	std::back_inserter(expressions),
	[&](auto const& column_ref) {
	return cudf::ast::operation(op, expressions.back(), column_ref);
	});
	}
	auto const& expression_tree_root = expressions.back();

[vyasr]

FWIW we'd also be OK with changing the current model, see #10744. If you would like to make that change, a PR is welcome!

[shriramch]

@bdice Thank you, this approach worked.

[shriramch]

@vyasr Sure, I'd like to try this.

[vyasr]

@shriramch OK great! Feel free to post here if you need help in getting a development environment set up for cudf!

[shriramch]

@vyasr Is it possible to get a remote development environment? Unfortunately I can't do this on my current PC.

[vyasr]

Would you be able to spin up an EC2 or GCP instance for this? I think getting access on one of the cloud services would be the easiest. Paperspace is another good option.