<SYSTEM_TASK:>
Solve the following problem using Python, implementing the functions described below, one line at a time
<END_TASK>
<USER_TASK:>
Description:
 def validate_functions(ast: BELAst, bo):
 """Recursively validate function signatures Determine if function matches one of the available signatures. Also, 2. Add optional to AST Arg (optional means it is not a fixed, required argument and needs to be sorted for canonicalization, e.g. reactants(A, B, C) ) Args: bo: bel object Returns: bel object """


    if isinstance(ast, Function):
        log.debug(f"Validating: {ast.name}, {ast.function_type}, {ast.args}")
        function_signatures = bo.spec["functions"]["signatures"][ast.name]["signatures"]

        function_name = ast.name
        (valid_function, messages) = check_function_args(
            ast.args, function_signatures, function_name
        )
        if not valid_function:
            message = ", ".join(messages)
            bo.validation_messages.append(
                (
                    "ERROR",
                    "Invalid BEL Statement function {} - problem with function signatures: {}".format(
                        ast.to_string(), message
                    ),
                )
            )
            bo.parse_valid = False

    # Recursively process every NSArg by processing BELAst and Functions
    if hasattr(ast, "args"):
        for arg in ast.args:
            validate_functions(arg, bo)

    return bo