В прошлой статье мы реализовывали алгоритм унификации (unification) на Rust-е. Теперь давайте применим его на реальном примере - простое lambda исчисление.

Синтаксис

Синтаксис выражений у нашего простого lambda calculus-а будет выглядеть так:

<expr> ::= <identifier>
        |  \ <identifier> . <expr>
        | ( <expr> <expr> )

В данном случае \ <identifier> . <expr> это синтаксис для лямбд:

\x.x
 ^ параметр лямбды
   ^ "возвращаемое" значение
\x.\y.x
\x.\y.y
\a.((\x.\y.y) a)

А <expr> <expr>, для применений:

\x.\y.(x y)
       ^ лямбда
         ^ аргумент

Теперь когда с синтаксисом мы ознакомились, мы можем приступить к самому сладкому: реализации!

Токенизация (сканирование, или лексический анализ, или ...)

Первое, что нам нужно сделать с исходником на нашем простеньком языке программирования это превратить его в список токенов, то есть токенизировать:

Токен - здесь можно рассматривать как грамматическую единицу языка: разные виды пунктуации, название (идентификатор), иногда пробелы, ключевые слова и т.д.

Разметим структуру токена в нашем языке:

#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub enum Token {
    Lambda, // `\`
    OpenParent, // `(`
    CloseParent, // `)`
    Dot, // `.`
    Name(String), // identifier
}

Реализуем токенизацию!

pub fn tokenize(source: &str) -> Vec<Token> {
    let mut chars = source.chars().peekable();
    let mut tokens = Vec::new();

    while let Some(c) = chars.next() {
        match c {
            '(' => tokens.push(Token::OpenParent),
            ')' => tokens.push(Token::CloseParent),
            '\\' => tokens.push(Token::Lambda),
            '.' => tokens.push(Token::Dot),
            _ => {

Здесь мы обрабатываем токены состоящие из единичных символов - пунктуацию. Теперь самое интересное - идентификаторы:

                if c.is_whitespace() {
                    // ignore
                } else if c.is_alphabetic() || c == '_' {
                    ...
                } else {
                    panic!("unexpected character `{}`", c);
                }
            }
        }
    }

    tokens
}

Здесь мы делаем несколько вещей. Во-первых, мы пропускаем пробелы в нашей программе (никакого значения даже с точки зрения синтаксиса они здесь не имеют). Во-вторых, если мы обнаруживаем невалидный символ, мы выводим ошибку (пока-что делаем панику, что позже исправим). В-третьих обрабатываем идентификаторы:

                    let mut name = String::new();

                    name.push(c);

                    while let Some(&c) = chars.peek() {
                        if c.is_alphanumeric() || c == '_' {
                            name.push(c);
                            chars.next();
                        } else {
                            break;
                        }
                    }

                    tokens.push(Token::Name(name));

Пока следующий символ это либо число, либо буква, либо '_', мы продолжаем идти дальше и добавлять символы в нашу строку name, иначе мы прерываем цикл и идем сканировать следующие токены.

Парсер

Теперь же, когда мы имеем список токенов (с которым работать проще, нежели чем с исходным кодом), мы должны провести синтаксический анализ:

Парсер берет список токенов и преобразует его в абстрактное синтаксическое дерево или AST.

Первое, что мы должны сделать - разметить AST для выражений:

#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub enum Expression {
    Lambda {
        parameter: String,
        value: Box<Self>,
    },
    Apply {
        callee: Box<Self>,
        argument: Box<Self>,
    },
    Variable {
        name: String,
    },
}

Я надеюсь, здесь вопросов не должно быть.

Теперь мы должны создать структуру, которая будет хранить итератор по токенам, для того, чтобы по ним проходиться:

struct ParseState<I>
where
    I: Iterator<Item = Token>,
{
    tokens: Peekable<I>,
}

impl<I> ParseState<I>
where
    I: Iterator<Item = Token>,
{
    fn new(tokens: I) -> Self {
        Self {
            tokens: tokens.peekable(),
        }
    }

Теперь можно приступить к самому интересному! Начнем с выражений завернутых в скобки:

    fn parse_parenthesized_expression(&mut self) -> Expression {
        let inner_expression = self.parse_expression();

        if !matches!(self.tokens.next(), Some(Token::CloseParent)) {
            panic!("expected `)`");
        }

        inner_expression
    }

Здесь мы не проверяем на открывающую скобку, потому-что предполагается, что при вызове функции она уже обработана.

Теперь обработка лямбд:

    fn parse_lambda(&mut self) -> Expression {
        let parameter = match self.tokens.next() {
            Some(Token::Name(name)) => name,
            _ => panic!("expected identifier"),
        };

        if !matches!(self.tokens.next(), Some(Token::Dot)) {
            panic!("expected `.`");
        }

        let value = self.parse_primary_expression();

        Expression::Lambda {
            parameter,
            value: Box::new(value),
        }
    }

Здесь тоже предполагается, что \ уже обработан.

В данном случае мы можем заметить метод parse_primary_expression. Это по сути парсинг всех выражений кроме применений (<expr> <expr>), потому-что например здесь:

\x.x a

Мы парсим не x a цельно, а берем толькоx. И поэтому получаем совершенно другой порядок действий, так как \x.x и a это два раздельных выражения.

Реализуем этот самый метод!

    fn parse_primary_expression(&mut self) -> Expression {
        match self.tokens.next() {
            Some(Token::Lambda) => self.parse_lambda(),
            Some(Token::OpenParent) => self.parse_parenthesized_expression(),
            Some(Token::Name(name)) => Expression::Variable { name },
            _ => panic!("expected expression"),
        }
    }

Здесь мы вызываем все функции, которые мы написали до этого и еще обрабатываем простые переменные.

Теперь же нам нужно обрабатывать применения (<expr> <expr>):

    fn parse_expression(&mut self) -> Expression {
        let mut left = self.parse_primary_expression();

        while !matches!(
              self.tokens.peek(), 
              Some(Token::CloseParent) | None) {
            let argument = self.parse_primary_expression();

            left = Expression::Apply {
                callee: Box::new(left),
                argument: Box::new(argument),
            };
        }

        left
    }
}

Здесь мы продолжаем анализировать выражения пока не встретим закрывающую скобку или пока не уткнемся в конец входных данных:

          while !matches!(
              self.tokens.peek(), 
              Some(Token::CloseParent) | None) { ... }

Ну и самое логичное, мы анализируем аргумент при применении и сохраняем это все в AST:

            let argument = self.parse_primary_expression();

            left = Expression::Apply {
                callee: Box::new(left),
                argument: Box::new(argument),
            };

Таким образом мы реализовали простой парсер за ~130 строк кода для lambda исчисления. А теперь то чего мы так долго ждали:

Type inference

Помните в прошлой статье, я говорил про type constraint-ы? Так-вот пока для простоты у нас будет только 1 вид constraint-ов - равенство:

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum Constraint {
    Eq { left: Arc<Type>, right: Arc<Type> },
}

То есть как раньше пояснялось, constraint требует, чтобы тип были равны. Соответственно unification будет как раньше принимать левый и правый тип и давать нам новые замены (substitutions).

Теперь, так как мы уже начинаем работать со scope-ами, нам нужно где-то хранить информацию о типах. Мы пока-что сделаем это самым очевидным способом:

#[derive(Debug, Clone, PartialEq, Eq, Default)]
struct Environment {
    variables: HashMap<String, Arc<Type>>,
}

impl Environment {
    fn new() -> Self {
        Self::default()
    }
}

Теперь создадим контекст для нашего type inference-а:

#[derive(Debug, PartialEq, Eq)]
struct InferenceContext<'env> {
    constraints: Vec<Constraint>,
    environment: &'env mut Environment,
    last_type_variable_index: usize,
}

impl<'env> InferenceContext<'env> {
    fn new(environment: &'env mut Environment) -> Self {
        Self {
            constraints: Vec::new(),
            environment,
            last_type_variable_index: 0,
        }
    }

Как видим, здесь есть интересное поле - last_type_variable_index. Нужно оно для генерации новых уникальных переменных типа. Помните?

Напишем функции, которые будут генерировать новые переменные типов и сами типы заполнители:

    fn fresh_type_variable(&mut self) -> TypeVariable {
        self.last_type_variable_index += 1;
        TypeVariable(self.last_type_variable_index)
    }

    fn type_placeholder(&mut self) -> Arc<Type> {
        Arc::new(Type::Variable(self.fresh_type_variable()))
    }

А теперь делаем завершающие штрихи. Напишем функцию, которую назовем infer_type. Она будет возвращать тип данного выражения:

    fn infer_type(&mut self, expression: &Expression) -> Arc<Type> {
        match expression {
            Expression::Variable { name } => self
                .environment
                .variables
                .get(name)
                .unwrap_or_else(|| panic!("unbound variable: {}", name))
                .clone(),

Первое, что мы должны обработать это самый простой случай. Если выражение - переменная, берем информацию о типе из scope-а.

            Expression::Lambda {
                parameter,
                value,
            } => {
                let parameter_type = self.type_placeholder();

                self.environment
                    .variables
                    .insert(parameter.clone(), parameter_type.clone());

                let value_type = self.infer_type(value);

                Arc::new(Type::Constructor(TypeConstructor {
                    name: "Function".to_owned(),
                    generics: vec![parameter_type, value_type],
                }))
            }

С лямбдами все поинтереснее. Во-первых, мы не знаем тип параметра лямбды. Единственное, что мы можем узнать это ее возвращаемое значение, что мы и делаем:

                let value_type = self.infer_type(value);

Соответственно, для типа параметра, мы пока оставим переменную типа (которую после можно будет убрать с помощью замен) и конечно же добавляем в текущий scope, чтобы можно было использовать параметр, при анализации возвращаемого значения:

                let parameter_type = self.type_placeholder();

                self.environment
                    .variables
                    .insert(parameter.clone(), parameter_type.clone());

Заметим, что мы возвращаем type constructor, с названием Function:

                Arc::new(Type::Constructor(TypeConstructor {
                    name: "Function".to_owned(),
                    generics: vec![parameter_type, value_type],
                }))

В данном случае, первый generic аргумент это тип параметра лямбды, а второй это тип возвращаемого значения.

Теперь приступим к анализации применений:

            Expression::Apply { callee, argument } => {
                let callee_type = self.infer_type(callee);
                let argument_type = self.infer_type(argument);

                let return_type = self.type_placeholder();

                self.constraints.push(Constraint::Eq {
                    left: callee_type.clone(),
                    right: Arc::new(Type::Constructor(TypeConstructor {
                        name: "Function".to_owned(),
                        generics: vec![argument_type.clone(), return_type.clone()],
                    })),
                });

                return_type
            }
        }
    }

Во-первых, мы анализируем типы самой лямбды и аргумента. Возвращаемое значение, мы бы в теории могли бы узнать если бы не типовые переменные. Вместо такого наивного подхода, мы можем пока пометить возвращаемое значение как переменную типа и использовать type constraint:

                self.constraints.push(Constraint::Eq {
                    left: callee_type.clone(),
                    right: Arc::new(Type::Constructor(TypeConstructor {
                        name: "Function".to_owned(),
                        generics: vec![argument_type.clone(), return_type.clone()],
                    })),
                });

А исходя из информации, что Function<A, ?t> = Function<A, B> мы и так узнаем тип возвращаемого значения (?t = B), а еще и во-вторых проверим типы на type mismatch.

Поздравляю, мы почти закончили!

Теперь, нам нужна функция, которая будет проходиться по type constraint-ам и применять нашу написанную в прошлой статье функцию unify, чтобы получать замены для типовых переменных:

    fn solve(self) -> HashMap<TypeVariable, Arc<Type>> {
        let mut substitutions = HashMap::new();

        for constraint in self.constraints {
            match constraint {
                Constraint::Eq { left, right } => {
                    unify(left, right, &mut substitutions);
                }
            }
        }

        substitutions
    }
}

А теперь самое сладкое, проверим работает ли наш алгоритм:

fn main() {
    let mut environment = Environment::new();

    environment.variables.insert(
        "add".to_owned(),
        tconst!(
            "Function",
            tconst!("int"),
            tconst!("Function", tconst!("int"), tconst!("int"))
        ),
    );

    let expression = ParseState::new(tokenize("\\a.(add a a)").into_iter()).parse_expression();

    let mut context = InferenceContext::new(&mut environment);
    let ty = context.infer_type(&expression);
    let substitutions = context.solve();

    println!("{:?}", ty.substitute(&substitutions));
}

Как видим алгоритм понял, что тип выражения \a.(add a a) если add это Function<int, Function<int, int>> это Function<int, int>, что звучит логично:

Constructor(TypeConstructor { name: "Function", generics: [Constructor(TypeConstructor { name: "int", generics: [] }), Constructor(TypeConstructor { name: "int", generics: [] })] })

Github

Весь исходный код, который я предоставляю в статьях теперь можно найти здесь.

Окончание

Спасибо большое за внимание! Я следующих статьях, мы будем говорить о более продвинутых способах реализации type inference, интересных фишках и много другого!