Rc-lang开发周记18 简单类型推导
Homura 我摸到了！
 2022-05-08 11:17:10      1.6k 字  7 分钟  

timg.jpg

不要小看我，这种程度我也可以做得出！非pixiv

本周主要都在了解MIR相关，但是还存有非常多的问题，因此先来讲一下之前写的TypeInfer的内容

我将Infer的过程分为了两部分。第一部分是最纯粹的类型推导，第二部分是实际将ast转换为带有类型信息的ast。

Type

目前先这样做了一个非常简易的样子

1
2
3
4
5
6
7
8
9
enum Type:
  case Boolean
  case String
  case Int32
  case Float
  case Nil
  case Fn(ret: Type, params: List[Type])
  case Infer
  case Err(msg: String)

Typed

对于类型相关的操作来讲，首先本身是有类型的才能进行infer，因此有了这样一个trait

1
2
3
4
5
6
7
8
9
10
11
12
trait Typed {
  var ty:Type = Type.Infer

  def withTy(ty: Type): this.type = {
    this.ty = ty
    this
  }

  def withInfer: this.type = withTy(infer)

  def infer: Type = Infer(this)
}

注意这里默认的是Type.Infer，表示需要Infer才行

infer的过程则是调用了case object Infer（单例对象），后面会讲到

用的时候直接mixin这个trait即可

1
2
3
4
5
6
enum Expr extends ASTNode with Typed:
  case Number(v: Int)
  case Identifier(ident: Ident)

enum Item extends ASTNode with Typed:
  case Method(decl: MethodDecl, body: Block) extends Item with Typed

TyCtxt

ctxt的部分主要存放一个全局符号表，以及一个局部符号表（这里的符号表只包含了类型信息）

而局部符号表又分为了当前scope以及outer的两部分。

接口也很简单，简单的添加与查找，以及进入一个新的scope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
case class TyCtxt(val global:Map[Ident, Type] = Map[Ident, Type]()) {
  var outer = List[Map[Ident, Type]]()
  var local = Map[Ident, Type]()

  def lookup(ident: Ident): Option[Type] = {
    val ty = local.get(ident) orElse outer.find(_.contains(ident)) orElse global.get(ident)
    ty.asInstanceOf[Option[Type]]
  }

  def enter[T](f: => T): T = {
    outer ::= local
    local = Map[Ident, Type]()
    val result = f
    local = outer.head
    outer = outer.tail
    result
  }

  def addLocal(k: Ident, v: Type): Unit = {
    local += (k -> v)
  }
}

关于enter的参数需要讲一下，既不是一个f: T，也不是一个f: () ⇒ T。

使用f: ⇒ T的写法可以推迟实际传进来的求值过程。既可以接受一个简单的T，也可以接受一个函数计算结果的T，同样也可以接受一个() ⇒ T

看一个测试就明白了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
it("nested") {
  tyCtxt.enter(() => {
    val id = Ident("a")
    val ty = Nil
    tyCtxt.addLocal(id, ty)
    tyCtxt.enter(testEnter(id))
    assert(tyCtxt.enter(id) == String)
    assert(tyCtxt.lookup(id).contains(ty))
  })
}

def testEnter(id: Ident): Type = {
	assert(tyCtxt.local.isEmpty)
  val innerTy = String
  tyCtxt.addLocal(id, innerTy)
  assert(tyCtxt.lookup(id).contains(innerTy))
  innerTy
}

可以看到这里的enter存在两种写法。

在进入testEnter之前添加了local，进入之后local变成了空的，也就是说进入了一个新的scope。

最初是觉得每次tyCtxt.enter(() ⇒ f())都要写() ⇒ 感到非常麻烦，后来发现了这样的写法

Infer

成员变量只有一个tyCtxt

1
2
3
4
case object Infer {
  var tyCtxt: TyCtxt = TyCtxt()
	...
}

infer的入口处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def apply(typed: Typed, force: Boolean = false): Type = {
  infer(typed, force)
}

private def infer(typed: Typed, force: Boolean): Type = {
  if(!force && typed.ty != Type.Infer) {
    typed.ty
  } else {
    infer(typed)
  }
}

private def infer(typed: Typed): Type = {
  typed match
    case expr: Expr => infer(expr)
    case item: Item => infer(item)
    case method: Item.Method => infer(method)
    case stmt: Stmt => infer(stmt)
    case _ => ???
}

force也很好理解，不是force的情况下原来有type则直接返回，而不是进行推导

Expr infer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private def infer(expr: Expr): Type = {
  expr match
    case Number(v) => Int32
    case Identifier(ident) => lookup(ident)
    case Bool(b) => Boolean
    case Binary(op, lhs, rhs) => common(lhs, rhs)
    case Str(str) => String
    case If(cond, true_branch, false_branch) => false_branch match
      case Some(fBr) => common(true_branch, fBr)
      case None => infer(true_branch)
    case Return(expr) => infer(expr)
    case Block(stmts) => tyCtxt.enter(infer(stmts.last))
    case Call(target, args) => lookup(target)
}

Infer的部分主要还是在于表达式的类型推导，实际上也很直观。有的种类表达式自身类型是确定了，需要考虑id的就去lookup，像if和binary这种通过common来获取。

lookup

1
2
3
private def lookup(ident: Ident): Type = {
  tyCtxt.lookup(ident).getOrElse(Err(s"$ident not found"))
}

简单的在ctxt中查找符号的信息

common

1
2
3
4
5
private def common(lhs: Expr, rhs: Expr): Type = {
  val lt = infer(lhs)
  val rt = infer(rhs)
  if lt == rt then lt else Err("failed")
}

这里我还抱有一些疑问，在这里产生一个TypeErr是否合适，但是如果lhs和rhs的类型是不兼容的情况那也无法得出一个正确的Type

虽然名字叫common，然而这里做的非常简单，只是简单判别类型是否相同而没有考虑到type compatible

enter

1
2
3
4
5
6
7
8
def enter[T](tyCtxt: TyCtxt, f: => T): T = {
  this.tyCtxt = tyCtxt
  tyCtxt.enter(f)
}

def enter[T](f: => T): T = {
  tyCtxt.enter(f)
}

除了普通的enter，还支持通过指定一个typeCtxt来推导

Translator

1
2
3
4
5
6
7
8
9
case object TypedTranslator {
  var tyCtxt: TyCtxt = TyCtxt()
  def apply(tyCtxt: TyCtxt)(module: RcModule): RcModule = {
    // update local table in TypedTranslator will cause Infer ctxt update
    // because of pass a typCtxt by Ref
    Infer.enter(tyCtxt, RcModuleTrans(module))
  }
  ...
}

这里传递一个ctxt的引用给Infer，之后在translator里面通过tyCtxt更新各种local信息，这样Infer只做infer就可以了，不需要关心其他的事情。翻译的最小单元则是一个Module

translator主要的想法就是通过infer获取类型，之后返回一个保存有意义的类型信息的ASTNode

Expr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def exprTrans(expr: Expr): Expr =
	(expr match
    case Binary(op, lhs, rhs) => Binary(op, lhs.withInfer, rhs.withInfer)
    case If(cond, true_branch, false_branch) => {
      val false_br = false_branch match
        case Some(fBr) => Some(fBr.withInfer)
        case None => None
      If(cond.withInfer,
        true_branch.withInfer.asInstanceOf[Block],
        false_br)
    }
    case Call(target, args) => Call(target, args.map(_.withInfer))
    case Return(expr) => Return(expr.withInfer)
    case Block(stmts) => tyCtxt.enter(Block(stmts.map(stmtTrans)))
    case _ => expr).withInfer

可以看到就是简单的将参数withInfer，之后重新构建起这个表达式，并且将这个表达式整体进行infer。

为了避免一个个调用withInfer，因此在最后将expr的结果统一调用withInfer

对于Stmt的部分本质做法是差不多的，就不再赘述了

最后

下周开始会开始专注于适合优化层面IR的内容了。最早我给自己规定的每天写一部分功能，不过我后来已经将写与学习成为了习惯，因此不会再局限于每天写这种事情。现在更多的是了解各种不同的做法，分析不同做法之间的差异（了解这些的过程有些上瘾，一不小心就会陷进去）。也因此下周开始的内容可能写的篇幅会少一些，会多一些对比分析

  • 本文标题：Rc-lang开发周记18 简单类型推导
  • 本文作者：Homura
  • 创建时间：2022-05-08 11:17:10
  • 本文链接：https://homura.live/2022/05/08/rc-lang-dev/rc-lang-dev-18/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！