在OCaml中实现类型方程生成器 [英] Implementing type equation generator in OCaml

问题描述

  type exp = 
 | CONST的int 
 | VAR 
 |添加exp * exp 
 | exp * exp 
 |的SUB ISZERO的exp 
 | IF的exp * exp * exp 
 | LET var * exp * exp 
 | var * exp 
 |的PROC CALL exp * exp 
和var = string 
 
 type typ = TyInt | TyBool | Ty * typ * typ | Tyvar的TyVar 
和tyvar =字符串
 
类型typ_eqn =（typ * typ）列表
 
模块TEnv =结构
类型t = var  - > ; typ 
 let empty = fun _  - > （失败类型Env是空的）
 let extend（x，t）tenv = fun y  - >如果x = y then t else（tenv y）
 let find tenv x = tenv x 
 end 
 
 let rec gen_equations：TEnv.t  - > exp  - >典型 - > typ_eqn 
 =有趣的生活 - >与
 |匹配CONST n  - > [（ty，TyInt）] 
 | VAR x  - > [（ty，TEnv.find tenv x）] 
 | ADD（e1，e2） - > [（ty，TyInt）] @ 
 [gen_equations（tenv，e1，TyInt）] @ 
 [gen_equations（tenv，e2，TyInt）] 
  pre> 
 
 
我试图实现我最近在课堂上学到的类型方程生成器。 
 
 
但是当我尝试使用上述方法实现ADD表达式时，我得到一个错误，说：该表达式具有类型（'a  - >'b  - > typ_eqn）列表，但表达式需要类型（typ * typ）列表。 
 
 
 
不添加两个或更多typ_eqn类型列表，基本上与（typ * typ）列表相同？
 
 
 
编辑：
  let rec gen_equations：TEnv.t  - > exp  - >典型 - > typ_eqn 
 =有趣的生活 - >与
 |匹配CONST n  - > [（ty，TyInt）] 
 | VAR x  - > [（ty，TEnv.find tenv x）] 
 | ADD（e1，e2） - > 
让l1 = [（ty，TyInt）]在
中让l2 = gen_equations（tenv，e1，TyInt）在
中让l3 = gen_equations（tenv，e2，TyInt）in 
 l1 :: l2 :: l3 
  
我也试过这种方法，但是这给了我一个错误信息：
 
 
 
该表达式具有类型（typ * typ）列表，但表达式预期为类型（typ * typ）。 
 
 
为什么突然想到不同的东西???  
 
解决方案 
在第一个版本中，你写 [gen_equations（tenv，e1，TyInt）] ，但 gen_equations 已经返回一个列表。您可以尝试编写 gen_equations tenv e1 TyInt （注意从非安全类型转换为curry类型）。
 
 
在第二个版本，您使用 :: 来加入两个列表。但 :: 用于将元素连接到列表。您可以尝试 l1 @ l2 @ l3 。
 
 
 
 更新 
 
 
 
在这两个版本中，您都以非干扰形式调用 gen_equations ，但它是以curried形式定义的。像这样调用： gen_equations tenv e1 TyInt 。
 
type exp = 
  | CONST of int
  | VAR of var
  | ADD of exp * exp
  | SUB of exp * exp
  | ISZERO of exp
  | IF of exp * exp * exp
  | LET of var * exp * exp
  | PROC of var * exp
  | CALL of exp * exp
and var = string

type typ = TyInt | TyBool | TyFun of typ * typ | TyVar of tyvar
and tyvar = string

type typ_eqn = (typ * typ) list

module TEnv = struct
  type t = var -> typ
  let empty = fun _ -> raise (Failure "Type Env is empty")
  let extend (x,t) tenv = fun y -> if x = y then t else (tenv y)
  let find tenv x = tenv x
end

let rec gen_equations : TEnv.t -> exp -> typ -> typ_eqn 
=fun tenv e ty -> match e with
| CONST n -> [(ty, TyInt)]
| VAR x -> [(ty, TEnv.find tenv x)]
| ADD (e1,e2) -> [(ty, TyInt)]@
    [gen_equations (tenv, e1, TyInt)]@
    [gen_equations (tenv, e2, TyInt)]
Hi, I'm trying to implement the type equation generator that I recently learned in class.

But when I tried implementing the ADD expression using the above method, I get an error saying, "This expression has type ('a -> 'b -> typ_eqn) list, but an expression was expected of type (typ * typ) list." 

Isn't appending two or more typ_eqn type lists basically the same thing as (typ * typ) list?

edit:
let rec gen_equations : TEnv.t -> exp -> typ -> typ_eqn 
=fun tenv e ty -> match e with
| CONST n -> [(ty, TyInt)]
| VAR x -> [(ty, TEnv.find tenv x)]
| ADD (e1,e2) -> let l1 = [(ty, TyInt)] in
    let l2 = gen_equations (tenv, e1, TyInt) in
    let l3 = gen_equations (tenv, e2, TyInt) in
    l1::l2::l3
I've tried this method too, but this gives me an error message: 

"This expression has type (typ * typ) list, but an expression was expected of type (typ * typ)."

Why is this suddenly expecting something different???
解决方案
In your first version you write [gen_equations (tenv, e1, TyInt)], but gen_equations already returns a list. You might try writing just gen_equations tenv e1 TyInt (note change from uncurried to curried form).

In your second version, you're using :: to join two lists. But :: is for joining an element to a list. You might try l1 @ l2 @ l3.

Update

In both versions, you're calling gen_equations in uncurried form, but it is defined in curried form. Call like this: gen_equations tenv e1 TyInt.

                        
这篇关于在OCaml中实现类型方程生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！