Skip to content

Yadriggy Walker

Jump to bottom
chibash edited this page Jan 2, 2019 · 1 revision

A tree walker for the abstract syntax trees (ASTs), or an implementation of Visitor pattern. This DSL is used for traversing the ASTs obtained by calling Yadriggy::reify. It can take account of the user types defined by the syntax checker of Yadriggy. The implementation of this DSL does not use Yadriggy. It is a normal DSL embedded in Ruby.

Yadriggy::Checker

This is the root class of the tree walker. Its behavior is similar to a case statement (or a switch statement) for the ASTs:

class SimpleChecker < Yadriggy::Checker
  rule(Number) do
    'number'
  end

  rule(Identifier) do
    'identifier'
  end

  rule(Binary) do
    v1 = check(ast.left)
    v2 = check(ast.right)
    "#{v1}#{ast.op}#{v2}"
  end
end

This class is used as follows:

checker = SimpleChecker.new
ast = Yadriggy::reify { k + 3 }.tree.body
checker.check(ast)    # `identifier+number`

The check method selects a rule for the type of the AST node given as the argument. The rules are given by the rule method. In the case above, three rules are given. They are for the Number class, the Identifier class, and the Binary class. Since ast is an instance of Binary node representing k + 3, the rule for Binary is selected. Then, the check method executes the body of the selected rule and returns the result. Note that the rule for Binary includes nested calls to check. They also select and execute the corresponding rules; the first one is for Identifier and the second one is for Number.

The check method first tries to select the rule for the user type of the given AST node. The user type is attached by the syntax checker Yadriggy::Syntax. If no such rule is found (or the user type is not attached), then it selects the rule for the concrete class of the AST node. If no rule for that class is found, it next selects the rule for its super class, the super class of that super class, and so on. Finally, if no rule is selected, an exception is thrown.

The check method executes the body of the selected rule. The result of this execution is returned by the check method.

Methods in Checker

The Checker class defines several methods. They are available in the body of the rules and in the subclasses of Checker.

proceed(an_ast, envi=nil)

This applies the rule supplied for the super class.

Type
an_ast ASTnode the current AST
envi Object the current environment
return Object The result of the application of the rule

an_ast and envi are used when executing that rule. The proceed method is used in the body of the rule overriding the corresponding one in the super class:

class VerboseChecker < SimpleChecker
  rule(Number) do
    puts 'Number'
    proceed(ast)    # invokes rule(Number) in SimpleChecker
  end
end

ast()

This obtains the current AST.

Type
return ASTnode the current AST

ast_env()

This obtains the current environment.

Type
return Object the current environment

The Checker class does not require that the type of the environments is a specific class. It can be any class since the Checker class does not access it. (The programmer of) a subclass of Checker will choose the type of the environments. For example, when a subclass of Checker is an AST walker for type checking, the environment will be an object representing a type environment, which is a map from names to types.

check_all(an_ast)

This applies a rule to the given AST. It returns the result of the application of the rule or throws a CheckError. This is the entry point of the checker. It first invokes check with an_ast and then executes the blocks recorded by check_later.

Type
an_ast ASTree or ASTnode the AST
return Object the result

check(an_ast, ast_env=nil)

This selects a rule for the AST given for an_ast and then executes the rule. It returns the result of executing the rule.

Type
an_ast ASTree or ASTnode the AST
envi Object the environment
return Object the result

check_later(&proc)

This records a block, which will be executed later by check_all. See the type_assert_later method shown below.

error!(an_ast, msg='')

This reports an error.

Type
an_ast ASTree or ASTnode the AST causing the error
msg String the error message

It is used in the body of a rule:

class NumberChecker < Yadriggy::Checker
  rule(Number) do
    'number'
  end

  rule(Identifier) do
    error!(ast, "#{ast.name} is not valid")
  end
end

error_found!(an_ast, msg='')

This is the same as error! except it raises an exception.

errors?()

This returns true when the execution of a rule causes an error. It will be called after check.

checker = NumberChecker.new
ast = Yadriggy::reify { foo }.tree.body
checker.check(ast)
if checker.errors?
  puts checker.error_messages
end

error_messages()

This gets an array of error messages. It returns an array of String.

last_error()

This gets the last error messages. It returns a String.

Yadriggy::TypeChecker

This is a subclass of Checker. It provides utility methods for using Checker for type checking.

Methods

typecheck(an_ast)

This performs the type checking for the given AST and returns the type of the given AST. It is the entry point of the type checker. It can be regarded as an alias of check_all.

The returned value is a Yadriggy::Type object or an instance of its subclass.

Type
an_ast ASTree, ASTnode, or nil the AST
return Type the type of the given AST

type_env()

This returns a Yadriggy::TypeChecker::TypeEnv object representing the current type environment. It is equivalent to the ast_env method.

type(an_ast, ast_tenv=nil)

This computes the type of the given AST under the given type environment. The pair of the given AST and the resulting type is memoized in this TypeChecker object to avoid redundant computation of the type. Except this memoization, type can be regarded as an alias of check.

Type
an_ast ASTnode or nil the AST
ast_tenv TypeEnv the type environment
return Type the type of the given AST

type_as(an_ast, a_type)

This method sets the type of the given AST an_ast to the given type a_type. The pair of the given AST and its type is memoized in this TypeChecker object.

Type
an_ast ASTnode or nil the AST
ast_tenv TypeEnv the type environment
return Type the type of the given AST

type?(an_ast)

This method returns the type of the given AST an_ast. The type has to have been already computed by the type method. This method searches this TypeChecker object. It returns the type if the pair of the given AST and the type is memoized. Otherwise, if the pair is not memoized, it returns nil.

type_assert_later(&proc)

This method can be regarded as an alias of the check_later method in Checker. When this method is called within the body of a rule, the given block is executed after the execution of all the rules currently running finishes. (Note that the rule may include a nested call to type, which runs another rule. Thus, the execution of the given block is postponed until all these rules finish.)

For example, when a function definition is type-checked, it might be necessary to memoize the function signature (the parameter types and the return type) before the function body is type-checked. Without memoizing the function signature, a recursive call to the function could not be typed. For example,

rule(Def) do    # rule for function definition
  type_assert_later do
      # check the type of the function body
      s = type_env.new_tenv
      body_t = type(ast.body, s)
  end
  # return the function signature
  get_function_signature(ast)
end

The function body ast.body is type-checked after the function signature returned by get_function_signature is memoized as the function's type.

add_typedef(key)

This makes a new TypeDef object and binds it to the class (or instance) given by key. If there is the TypeDef object for key, this method returns it. The TypeDef object is a map to types from the instance variables and the methods declared in the class (or the particular instance) given by key.

Type
key Module or Object the class or the instance
return TypeDef the TypeDef object for the given key

typedef(key)

This method returns the TypeDef object bound to key. If key is nil, then it returns nil.

Type
key Module, Object, or nil the class or the instance
return TypeDef or nil the TypeDef object for the given key

Yadriggy::TypeChecker::TypeEnv

The TypeEnv class represents a type environment. It is a map from local variable names to their types.

Methods

new_tenv()

This makes and returns a new type environment. Its initial contents are the same as the callee type environment. For example, type_env.new_tenv makes a copy of type_env.

bind_name(name, type)

This updates the environment to map the given name to the given type.

Type
name Name, String, Symbol, or nil the name
type Type the type
return Type the given type

bound_name?(name)

This returns the type bound to the given name. If no type is bound to the name, this method returns nil.

Type
name Name, String, Symbol, or nil the name
return Type or nil the type bound to the name

Yadriggy::TypeChecker::TypeDef

The TypeDef class represents a map from the names of instance variables and method to their types.

Methods

[]=(name, type)

This method updates the TypeDef object to map the given name to the given type. The name should denote an instance variable or a method.

Type
name String, Symbol the name
type Type the type of the name
return Type the given type

This method returns the type of the instance variable or method with the given name.

Type
name String, Symbol the name
return Type or nil the type of the name
Clone this wiki locally