基于类型的编译

2025-09-26
四川
本文字数：4353 字
阅读完需：约 14 分钟

当我们开始把动态类型语言的代码编译到一个静态语言后端时候，就涉及到一个类型固化或者说类型冻结的过程，让我们看看刚才生成的 Zeta 中间代码

1: Call(Idx(Var(1), Const(2)), [], Var(2))2: Binary(Mul, Var(2), Const(3), Var(3))3: Binary(Sub, Var(3), Const(4), Var(4))4: Call(Idx(Var(4), Const(5)), [], Var(5))5: Binary(Sub, Var(5), Const(6), Var(6))6: Call(Idx(Var(6), Const(7)), [Const(8), Const(6)], Var(7))7: Call(Fn(1), [Const(6), Var(7), Idx(Var(0), Const(9))], Var(8))8: Binary(Mul, Var(8), Idx(Var(0), Const(10)), Var(9))9: Ret(Some(Var(9)))

复制代码

显然，这里面是没有任何类型信息的，我们要能够为一个函数生成代码，一个充分必要条件是能够有一个确定的规则，为所有的 Type::Any 能够找到一个确定的类型。

第一步就是参数，我们目前的函数是规定了参数的，如果没有固定的参数，则需要为每一种参数组合生成一段代码，也就是说，同一个 Fn 会有很多不同参数的函数体，是不是很熟悉，这就是 C++ 的模板代码生成了。

要实现类型系统根据类型接入的时机不同，我们有动态和静态两种方案，C++ Rust 等语言采用的都是静态方案，也就是在书写代码的时候，需要明确类型。

但是我们的 Zeta 是动态类型的，所以在只有在运行的时候，或者生成最终代码的时候才会固化类型，刚才看到的中间形态是没有类型的，完全动态执行没关系，类型可以在用到的时候再确定，但是生成代码就麻烦了，因为调用其他函数的时候，如果那个函数是动态的，你是不知道返回的类型的，又不能打断当前的生成过程，去生成那个函数的代码，那样整个生成器的逻辑将会极度复杂。

所以我们必须引入类型推断的概念，也就是说，在使用特定类型的参数调用一个动态类型函数的时候，快速通过代码推断出返回值，整个推断过程非常快，因为我们只需要过一遍顶层结构就够了。

所以我们引入一个 TypedModule 定义是这样的

#[derive(Debug, Clone)]pub struct FnBody {                             //函数体 按需生成各种类型的实现    pub def: FnDef,    pub variants: Vec<(Vec<Type>, Type)>,    pub code: Vec<Statement>,}
impl FnBody {    pub fn get_variant(&mut self, args: &[Type])-> Option<usize> {        self.variants.iter().position(|v| v.0 == args)    }}
#[derive(Debug, Clone)]pub struct Module {    pub consts: Vec<Dynamic>,    pub fns: Vec<FnBody>,    pub defs: Vec<(bool, StructDef)>,}

复制代码

我们看到，每个函数根据自己的传入的参数不同有一个变体的列表。

我们使用下面的函数获取某个符号的类型

    fn get_type(&self, s: &Symbol, vars: &[Type]) -> Option<Type> {        match s {            Symbol::Const(c)=> {                println!("const {:?}", self.module.consts[*c]);                Some(self.module.consts[*c].get_type())            },            Symbol::Var(v) => {                Some(vars[*v].clone())            }            Symbol::Idx(obj, _) => {                let obj_ty = self.get_type(obj, vars)?;                match obj_ty {                    Type::Array(ty, _)=> { return Some((*ty).clone()); }                    Type::Vec(ty, _)=> { return Some((*ty).clone()); }                    _=> {                        panic!("{:?}", obj)                    }                }            }            _=> { panic!()}        }    }

复制代码

这里面 vars 是当前调用帧的缓存，这是编译过程，所以使用递归没有啥问题。

这是获取某个函数返回类型，这是最重要的

    pub fn get_fn_type(&mut self, fn_idx: usize, mut args: Vec<Type>)-> Option<Type> {        match self.module.fns[fn_idx].get_variant(&args) {            Some(idx) => Some(self.module.fns[fn_idx].variants[idx].1.clone()),            None => {                for (arg, ty) in args.iter().zip(self.module.fns[fn_idx].def.args.iter()) {                    if arg != ty {                        panic!("")                    }                }                if self.module.fns[fn_idx].code.is_empty() {                    (self.native_type)(&self.module.fns[fn_idx].def.name, args)                } else {                    let code = self.module.fns[fn_idx].code.clone();                    self.deduce(&code, &mut args)                }            }        }    }

复制代码

这里面引入了一个函数指针，当这个函数是外部定义的时候，我们使用这个函数指针获取外部定义的返回类型

下面是推断类型的函数，比生成代码和执行简单多了，没有处理的情况我们都先 panic！

    pub fn deduce(&mut self, statements: &[Statement], vars: &mut Vec<Type>)-> Option<Type> {        for st in statements {            match st {                Statement::Unary(_, src, dest)=> {                    if let Some(t) = self.get_type(src, vars) {                        set_idx(vars, dest.get_var().unwrap(), t);                    }                }                Statement::Binary(_, s1, s2, dest) => {                    match (self.get_type(s1, vars), self.get_type(s2, vars)) {                        (Some(t1), Some(t2)) => {                            if t1.is_array() || t1.is_vec() {                                set_idx(vars, dest.get_var().unwrap(), t1);                            } else if t2.is_array() || t2.is_vec() {                                set_idx(vars, dest.get_var().unwrap(), t2);                            } else {                                set_idx(vars, dest.get_var().unwrap(), t1);     //以后检查兼容性                            }                        }                        (None, Some(t2)) => {                            s1.get_var().map(|idx| set_idx(vars, idx, t2.clone()));                            set_idx(vars, dest.get_var().unwrap(), t2);                        }                        (Some(t1), None) => {                            s2.get_var().map(|idx| set_idx(vars, idx, t1.clone()));                            set_idx(vars, dest.get_var().unwrap(), t1);                        }                        (None, None) => {                            panic!("Unreachable")                        }                    }                }                Statement::Call(func, args, ret_val) => {                    if let Symbol::Idx(obj, method) = func {        //处理成员函数                        if let Some(idx) = method.get_const() {                            let mut call_arg = vec![self.get_type(obj, vars).unwrap()];                            for arg in args {                                call_arg.push(self.get_type(arg, vars).unwrap());                            }                            let name = smol_str::SmolStr::try_from(self.module.consts[idx].clone()).unwrap(); //成员函数                            if let Some(idx) = ret_val.get_var() {                                if let Some(ty) = (self.native_type)(&name, call_arg) {                                    set_idx(vars, idx, ty);                                }                            }                        } else {                            panic!("Method index not found");                        }                    } else {                        let mut call_arg = Vec::with_capacity(args.len());                        for arg in args {                            call_arg.push(self.get_type(arg, vars).unwrap());                        }                        if let Some(t) = self.get_fn_type(func.get_fn().unwrap(), call_arg) {                            if let Some(idx) = ret_val.get_var() {                                set_idx(vars, idx, t);                            }                        }                    }                }                Statement::Assign(left, right) => {                    if let Some(t) = self.get_type(left, vars) {                        set_idx(vars, right.get_var().unwrap(), t);                    } else if let Some(t) = self.get_type(right, vars) {                        set_idx(vars, left.get_var().unwrap(), t);                    }                }                Statement::While(cond, _, body) => {                    self.deduce(cond, vars);                    self.deduce(body, vars);                }                Statement::Ret(r)=> {                    return r.as_ref().and_then(|r| self.get_type(r, vars) );                }                _=> { panic!() }            }        }        None    }

复制代码

现在我们使用 TypeModule 去推断类型


        let module = module::Module::from(compiler);        let mut m = module::TypedModule::new(module, |name, args| {            match name {                "fract" | "abs" | "clamp" => args.get(0).cloned(),                "mix" => args.get(1).cloned(),                n => { panic!("{}", n) }            }        });

复制代码

这是使用无类型的 module 创建一个有类型的 TypedModule 指定 native 函数的类型

刚才的 Zeta 代码

    const K = [1.0, 2.0/3.0, 1.0/3.0];    fn hsv2rgb(hsv: [f32; 3]) {        let rgb = (((hsv[0] + K).fract() * 6.0f32 - 3.0f32).abs() - 1.0).clamp(0.0, 1.0);        return mix(1.0f32, rgb, hsv[1]) * hsv[2];    }    pub fn main() {        hsv2rgb([0.3333333333333333f32, 1.0, 1.0]);    }

复制代码

使用这句调用