Hi all!
We are trying to introduce function and lambda into TableGen in ⚙ D148915 [TableGen] Introduce function and lambda.
The original need come from modeling RISCV Vector Scheduler in ⚙ D146198 [RISCV] Make Latency/ResourceCycles relevant to LMUL. Though we can define some subroutines via Using Classes as Subroutines, but sometimes we need to pass function(lambda) as template arguments.
We have implemented something like below.
1. The design
1.1 Function Type
The type of a function is represented as:
function<rettype[, argtype ]*>
This type represents a function who returns a value of the rettype and may have several argument types argtype (can be empty). The return type and argument type are arbitrary; it can even be another function type.
Two function types are compatible if their return type and argument types are compatible.
1.2 Function
A function statement defines an function that can be called.
FunctionDefinition: "function" FunctionID Function
FunctionID: TokIdentifier
Function: FunctionArgList ":" ReturnType FunctionBody
FunctionArgList: "(" (Declaration ("," `Declaration`)*)? ")"
ReturnType: Type
FunctionBody: "{" FunctionBodyItem+ "}"
FunctionBodyItem: Return
:| Defvar
:| Assert
Return: "return" Value ";"
A function can be parameterized by a list of “function arguments” whose values can be used in the function’s body.
If a function argument is not assigned a default value with =, it is uninitialized (has the “value” ?) and must be specified in the function argument list when the function is called (required argument). If an argument is assigned a default value, then it need not be specified in the argument list (optional argument). In the declaration, all required function arguments must precede any optional arguments. The function argument default values are evaluated from left to right.
The name of function is treated as a function reference to itself. As a result, the function name literals can be used in arguments as values with compatible function types.
Recursive function is supported(see 3. Example).
1.2 Lambda (anonymous function)
A lambda (or anonymous function) can be defined by keyword function.
LambdaDefinition: "function" Function
A lambda is a function with anonymous name and all captured variables. It can be treated as a function reference to the anonymous function, so it can even be returned.
Beside arguments and variables defined by defvar in inner scope, a lambda can capture outer variables(like iterator of foreach statement; arguments of outer class, multiclass or function; variables defined by defvar in outer scope). In particular, the priorities of variable capture are:
- Variables defined by
defvarin inner scope. - Arguments of lambda.
- Variables defined by
defvarin outer scope. - Iterator of foreach statement.
- Arguments of outer class, multiclass or function.
- Variables in global scope…
Currently, the fields of a class can’t be captured.
1.3 Function call
The function can be called with funcname(args). However, there is a grammar ambiguity between DAG and function call. For example:
(op1 (op2 a, b), c) <=> (op1(op2 a, b), c)
^ ^
DAG Call
When parsing this expression, we can treat it as a DAG expression with operator op1 and arguments ((op2 a, b) and c). Or, we can treat it as a wrong DAG expression whose operator is a function call op1(op2 a, b) (though its arguments are wrong). The key point here is that we don’t know whether it’s a new DAG expression or a function call when emitting (.
Currently, to resolve this ambiguity and not increase the complexity of TableGen parser, calls inside DAGs should add a single quote before arguments, like funcname'(args).
DAG: (op1 (op2 a, b), c)
Call: (op1 funcname'(a, b), c)
Note: I am still thinking a more elegant way to solve this ambiguity.
2. The implementation
In short:
- Add a new RecTy
FunctionRecTyto present function types. - Add a new TypedInit
FuncRefInitto present function references. The captures of lambda are contained. - Add a new TypedInit
FuncCallInitto present function calls.
In our implementation, structure Record is used to present function/lambda just like normal class or records.
2.1 FunctionRecTy
It’s a new RecTy that contains a return type and a list of RecTy to present argument types.
typeIsConvertibleTo is overrided, so if a FunctionRecTy can be compatible with others if their return types and all argument types are compatible.
2.2 FuncRefInit
It’s a new TypedInit that present function references. It contains a pointer to Record and a list of captured variables. Its type is the function type it is referring to.
Two FuncRefInit of the same Record are different if their captured variables are different. So if part of captured variables are resolved, then it becomes a new function reference(which is used to implement returning lambda).
2.3 FuncCallInit
It’s a new TypedInit that present function references. It contains a pointer to FuncRefInit and a list of actual arguments. Its type is the return type of FuncRefInit.
The execution of a function call is almost like what VarDefInit has done (which can be used in class-based subroutines), except that we will take all captured variables into consideration.
Example
function fib(int n):int{
return !if(!lt(n, 2),
1,
!add(
fib(!sub(n, 1)),
fib(!sub(n, 2))
)
);
}
foreach n = 0...9 in {
def "fib_" # n {
int value = fib(n);
}
}
// The result is:
// def fib_0 { int value = 1; }
// def fib_1 { int value = 1; }
// def fib_2 { int value = 2; }
// def fib_3 { int value = 3; }
// def fib_4 { int value = 5; }
// def fib_5 { int value = 8; }
// def fib_6 { int value = 13; }
// def fib_7 { int value = 21; }
// def fib_8 { int value = 34; }
// def fib_9 { int value = 55; }
function func_return_lambda(int func_arg): function<int, int> {
return function(int lambda_arg): int {
return !add(func_arg, lambda_arg);
};
}
def test {
defvar lambda0 = func_return_lambda(233);
defvar lambda1 = func_return_lambda(2333);
int value0 = lambda0(233);
int value1 = lambda1(2333);
}
// def test {
// int value0 = 466;
// int value1 = 4666;
// }
// ---- Object-Oriented Programming ---- //
class Shape {
function<int> getArea;
}
class Square<int l>: Shape {
int length = l;
let getArea = function():int{
return !mul(l, l);
};
}
class Triangle<int b, int h>: Shape {
int base = b;
int height = h;
let getArea = function():int{
return !div(!mul(b, h), 2);
};
}
def square:Square<4>;
def triangle:Triangle<4, 4>;
class TestGetArea<Shape shape> {
int value = shape.getArea();
}
def area_of_square: TestGetArea<square>;
def area_of_triangle: TestGetArea<triangle>;
// The result is:
// def area_of_square { int value = 16; }
// def area_of_triangle { int value = 8; }
So, if you are interesting in this, please feel free to help reviewing this patch or give some feedbacks.
Thanks!