2
\$\begingroup\$

I was recently intrigued by the Hindley Milner algorithm (for type inference) and decided to implement it in python. After implementing it, I got the feeling that the implementation was incorrect. I also felt that it wasn't very pythonic, and was sort of inefficient. Here is my code (it isn't as long as it looks-- there is just a lot of documentation):

ie_ast.py

class InferenceError(Exception): pass
class Type: pass
class Node: pass


class Int(Type, Node):
    def __init__(self, number):
        """A basic integer node

        Args:
            number: a integer
        """
        self.number = number

    def get_type(self):
        return self

    def show(self):
        return "int"


class Float(Type, Node):
    def __init__(self, number):
        """A basic float node

        Args:
            number: a float
        """
        self.number = number

    def get_type(self):
        return self

    def show(self):
        return "float"


class String(Type, Node):
    def __init__(self, string):
        """A basic string node

        Args:
            string: a string
        """
        self.string = string

    def get_type(self):
        return self

    def show(self):
        return "string"


class Bool(Type, Node):
    def __init__(self, _bool):
        """A basic boolean node

        Args:
            _bool: a boolean
        """
        self._bool = _bool

    def get_type(self):
        return self

    def show(self):
        return "bool"


class Void(Type, Node):
    def __init__(self):
        """No type"""

    def get_type(self):
        return self

    def show(self):
        return "void"

class Wildcard(Type, Node):
    def __init__(self):
        """Genric type (for return smts)"""

    def get_type(self):
        return self

    def show(self):
        return "wildcard"


class Unknown(Type, Node):
    def __init__(self):
        """A currently unknow type"""

    def get_type(self):
        return self

    def show(self):
        return "unknown"


class Ident(Node):
    def __init__(self, name):
        """An identifer

        Args:
            name: a name
        """
        self.name = name
        self.type = Unknown()

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type


class BinOp(Node):
    def __init__(self, left, op, right):
        """A binary operation node

        Args:
            left: the left hand side node
            op: the opertaion (+/-/*//)
            right: the right hand side node
        """
        self.left = left
        self.op = op
        self.right = right
        self.type = Unknown()

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type


class IfElse(Node):
    def __init__(self, condition, if_program, else_program):
        """A if-else node

        Args:
            condition: a Bool of true/false
            if_program: what to do if the condition evaluates as true
            else_program: what to do if the condition evaluates as false
        """
        self.condition = condition
        self.if_program = if_program
        self.else_program = else_program
        self.if_program_type = Unknown()
        self.else_program_type = Unknown()
        self.type = Unknown()

    def annotate_if_program_type(self, _type):
        self.if_program_type = _type

    def annotate_else_program_type(self, _type):
        self.else_program_type = _type

    def get_if_program_type(self):
        return self.if_program_type

    def get_else_program_type(self):
        return self.else_program_type

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type


class VarDef(Node):
    def __init__(self, name, value):
        """A variable node node

        Args:
            name: the variable's name
            value: the variable's value
        """
        self.name = name
        self.value = value
        self.type = Unknown()

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type


class FuncDef(Node):
    def __init__(self, name, args, program):
        """A function node

        Args:
            name: the function's name
            args: the function's arguments of an unknown type
            program: the function's program
        """
        self.name = name
        self.args = args
        self.program = program
        self.type = Unknown()

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type


class FuncCall(Node):
    def __init__(self, name, args):
        """A function call node

        Args:
            name: the function's name
            args: the function's arguments
        """
        self.name = name
        self.args = args
        self.type = Unknown() if self.name.name != "return" else Wildcard()

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type

ie.py

from ie_ast import *

class InferenceEngine:
    def __init__(self):
        """Builds a type table for a supplied ast"""
        # built in functions
        self.built_ins = ["println", "return"]

    def infer(self, node_list, type_table, actual_node_list):
        """Inference machinery

           Args:
                node_list: a list of nodes
                type_table: the table to read and write types
                actual_node_list: None if it node_list is the base program.
                    If it is not None, it must the base_program

            Returns:
                An annotated node_list
        """
        if actual_node_list is None:
            actual_node_list = node_list

        for node in node_list:
            if isinstance(node, Ident):
                self.infer_ident(node, type_table, actual_node_list)
            elif isinstance(node, BinOp):
                self.infer_bin_op(node, type_table, actual_node_list)
            elif isinstance(node, IfElse):
                self.infer_if_else(node, type_table, actual_node_list)
            elif isinstance(node, VarDef):
                self.infer_var_def(node, type_table, actual_node_list)
            elif isinstance(node, FuncDef):
                self.infer_func_def(node, type_table, actual_node_list)
            elif isinstance(node, FuncCall):
                self.infer_func_call(node, type_table, actual_node_list)
            elif isinstance(node, Int):
                # int does not need to be type checked because it is
                # a basic type, and can't be reduced
                pass
            elif isinstance(node, Float):
                # float does not need to be type checked because it is
                # a basic type, and can't be reduced
                pass
            elif isinstance(node, String):
                # string does not need to be type checked because it is
                # a basic type, and can't be reduced
                pass
            elif isinstance(node, Bool):
                # bool does not need to be type checked because it is
                # a basic type, and can't be reduced
                pass
        return node_list

    def infer_ident(self, node, type_table, node_list):
        """Gets the type of any identifier

           Args:
                node: the ident node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An annotated ident
        """
        node.annotate_type(type_table[node.name])

    def infer_bin_op(self, node, type_table, node_list):
        """Infers the type of any binop (+/-/*//)

           Args:
                node: the binop node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An annotated binop node
        """
        left_type = self.infer([node.left], type_table,
                               node_list)[0].get_type()
        right_type = self.infer([node.right], type_table,
                                node_list)[0].get_type()

        # check if the left type and right type are not the same
        if type(left_type) is not type(right_type):
            raise InferenceError("incompatible types")

        node.annotate_type(left_type)

    def infer_if_else(self, node, type_table, node_list):
        """Infers the type of a if-else smt (and runs type checks)

           Args:
                node: an if-else node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An annotated (and type checked) if-else node
        """
        condition_type = self.infer([node.condition], type_table,
                                    node_list)[0].get_type()

        # makes sure that the condition's type is bool
        if not isinstance(condition_type, Bool):
            raise InferenceError(
                "expected if-else condition to be of type bool")

        # look for returns statements in the if program
        # this is done to make sure all of them return the
        # same type
        if_ret_types = self.look_for_return_smts(node.if_program, self,
                                                 type_table)
        if if_ret_types:
            if not len(set(map(type, if_ret_types))) == 1:
                raise InferenceError(
                    "if program has multiple return statements that don't return the same thing"
                )
            node.if_program_type = if_ret_types[0]
        else:
            node.if_program_type = Void()

        # look for returns statements in the else program
        # this is done to make sure all of them return the
        # same type
        else_ret_types = self.look_for_return_smts(node.else_program, self,
                                                   type_table)
        if else_ret_types:
            if not len(set(map(type, else_ret_types))) == 1:
                raise InferenceError(
                    "else program has multiple return statements that don't return the same thing"
                )
            node.else_program_type = else_ret_types[0]
        else:
            node.else_program_type = Void()

        # can't say the if and else statement's program don't return
        # the same type if one of them is unknown
        if type(node.if_program_type) is not type(
                node.else_program_type) and not isinstance(
                    node.if_program_type, Unknown) and not isinstance(
                        node.else_program_type, Unknown):
            raise InferenceError(
                "if statement and else statement return different types")

        node.annotate_type(
            node.if_program_type if not isinstance(
                node.if_program_type, Unknown) else node.else_program_type)

    def infer_var_def(self, node, type_table, node_list):
        """Gets the type of any variable

           Args:
                node: a vardef node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An annotated vardef node
        """
        var_type = self.infer([node.value], type_table,
                              node_list)[0].get_type()
        type_table[node.name.name] = var_type
        node.annotate_type(var_type)

    def infer_func_def(self, node, type_table, node_list, skip_args=False):
        """Attempts to get the type of a function upon definition

           Args:
                node: a funcdef node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An (maybe almost) annotated funcdef node
        """
        # inserts itself into the type table for when
        # it is called
        type_table[node.name.name] = node

        if not skip_args:
            for arg in node.args:
                type_table[arg.name] = Unknown()
                arg.annotate_type(Unknown())

        # gets the program's node annotated with their respective types
        node.program = self.infer(node.program, type_table, node_list)
        return_types = self.look_for_return_smts(node.program, self,
                                                 type_table)

        # removes all the returns that have a type of unknown
        filtered_rets = [
            elm for elm in return_types if not isinstance(elm, Unknown)
        ]

        # checks is the function's program has return statements
        # that don't return the same type
        if filtered_rets:
            if not len(set(map(type, filtered_rets))) == 1:
                raise InferenceError(
                    "function has return statements with incompatible types")
            node.annotate_type(filtered_rets[0])
        else:
            node.annotate_type(Void())

        if skip_args:
            return node

    def infer_func_call(self, node, type_table, node_list):
        """Infers the type of a function, intern getting its own type

           Args:
                node: a funccall node
                type_table: the table to read and write types
                actual_node_list: the base program

            Returns:
                An annotated funccall node
        """
        if node.name.name not in self.built_ins:
            # get the function previously inserted into the type table
            func = type_table[node.name.name]

            # annotate the function's args with the types of the
            # arguments supplied to the function call
            for arg, call_arg in zip(func.args, node.args):
                arg_type = self.infer([call_arg], type_table,
                                      node_list)[0].get_type()
                type_table[arg.name] = arg_type
                arg.annotate_type(arg_type)

            # now that we know the args types we can completely
            # infer the function's program's types, thus
            # getting the function's type
            changed_func = self.infer_func_def(func, type_table, node_list,
                                               True)
            node.annotate_type(changed_func.get_type())
            type_table[node.name.name] = changed_func
            node_list[node_list.index(func)] = changed_func
        else:
            # annotate the node with the type of its argument
            node.annotate_type(
                self.infer(node.args, type_table, node_list)[0].get_type())

    def look_for_return_smts(self, program, ie, type_table):
        """Looks for return smts in a given program

           Args:
                program: the program to search in
                ie: an inference engine
                type_table: the table to read and write types

            Returns:
                All the return smt type in a given program
        """
        return_smts = []
        for program_node in program:
            if isinstance(program_node,
                          FuncCall) and program_node.name.name == "return":
                # insert into the return smts list the type of the argument
                return_smts.append(
                    ie.infer(program_node.args, type_table,
                             None)[0].get_type())
            elif isinstance(program_node, IfElse):
                return_smts.extend(
                    ie.infer(
                        self.look_for_return_smts(program_node.if_program, ie,
                                                  type_table), type_table,
                        None))
                return_smts.extend(
                    ie.infer(
                        self.look_for_return_smts(program_node.else_program,
                                                  ie, type_table), type_table,
                        None))

        return return_smts

main.py

from ie import InferenceEngine
from ie_ast import *

# example usage
"""
foo = 123 + 123
foobar = True
if foobar:
    pi
else:
    3.1415

println(foo)
def bar(a, b, c):
    baz = foobar
    if foobar:
        if false:
            return a + b
        else:
            return c + b
    else:
        if true:
            return 123
        else:
            return 321
abc = bar(12.2, 123321, foo) * foo / 456
"""
ie = InferenceEngine()
type_table = {}
program = [
    VarDef(Ident("foo"), BinOp(Int("123"), "+", Int("123"))),
    VarDef(Ident("foobar"), Bool("true")),
    IfElse(Ident("foobar"), [String("pi")], [Float("3.1415")]),
    FuncCall(Ident("println"), [Ident("foo")]),
    FuncDef(
        Ident("bar"),
        [Ident("a"), Ident("b"), Ident("c")], [
            VarDef(Ident("baz"), Ident("foobar")),
            IfElse(
                Ident("foobar"), [
                    IfElse(
                        Bool("false"), [
                            FuncCall(
                                Ident("return"),
                                [BinOp(Ident("a"), "+", Ident("b"))])
                        ], [
                            FuncCall(
                                Ident("return"),
                                [BinOp(Ident("c"), "+", Ident("b"))])
                        ])
                ], [
                    IfElse(
                        Bool("true"),
                        [FuncCall(Ident("return"), [Int("123")])],
                        [FuncCall(Ident("return"), [Int("321")])])
                ])
        ]),
    VarDef(
        Ident("abc"),
        BinOp(
            FuncCall(
                Ident("bar"),
                [Int("12.12"), Int("123321"),
                 Ident("foo")]), "*", BinOp(Ident("foo"), "/", Int("456")))),
]

infered = ie.infer(program, type_table, None)

# print out the type table
print("type table:")
print({k: v.get_type().show() for k, v in type_table.items()})

Does this follow the hindley milner algorithm, and is there some way I could make it better?

\$\endgroup\$
  • \$\begingroup\$ Maybe the files could have been better named! \$\endgroup\$ – Abdur-Rahmaan Janhangeer Apr 10 at 6:16
2
\$\begingroup\$

Your first file could be a lot shorter if you made the Type class slightly more than a useless empty namespace:

class Type:
    name = None

    def get_type(self):
        return self

    def show(self):
        if self.name is None:
            raise NotImplementedError
        return self.name

Then all your other types get shorter:

class Int(Type, Node):
     """A basic integer node"""
    name = "int"

    def __init__(self, number):
        """A basic integer node

        Args:
            number: an integer
        """
        self.number = number

Especially the ones that don't need any argument in the constructor:

class Void(Type, Node):
    """No type"""
    name = "void"

It could be argued that the show method should be called __str__ or __repr__, making them magic methods, depending on your need.

Similarly for Node:

class Node:

    def annotate_type(self, _type):
        self.type = _type

    def get_type(self):
        return self.type

At this point you could also realize that there is no need to have these getters and setters in the first place. In Python using a plain attribute is usually preferred. You can always start with an attribute and add getters and setters if you need them (i.e. if they do more than just getting and setting an attribute) by using property.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.