带函数应用的类型化抽象语法树 [英] Typed abstract syntax tree with function application

问题描述

我正在尝试编写一个可以表示
函数应用程序的类型化抽象语法树数据类型。

I am trying to write a typed abstract syntax tree datatype that can represent function application.

到目前为止，我已经拥有

So far I have

type Expr<'a> =
    | Constant    of 'a
    | Application of Expr<'b -> 'a> * Expr<'b> // error: The type parameter 'b' is not defined

我不认为在F＃中的最后一行写 for all b之类的东西-我是错误地解决了这个问题吗？

I don't think there is a way in F# to write something like 'for all b' on that last line - am I approaching this problem wrongly?

推荐答案

在通常，F＃类型系统的表现力不足以（直接）将类型化的抽象语法树定义为示例中的树。可以使用F＃不支持的通用代数数据类型（GADT）来完成（尽管它们在Haskell和OCaml中可用）。最好在F＃中使用它，但我认为这会使语言更加复杂。

In general, the F# type system is not expressive enough to (directly) define a typed abstract syntax tree as the one in your example. This can be done using generalized algebraic data types (GADTs) which are not supported in F# (although they are available in Haskell and OCaml). It would be nice to have this in F#, but I think it makes the language a bit more complex.

从技术上讲，编译器在抱怨，因为类型变量'b 未定义。但是，当然，如果定义了它，则会得到 Expr<’a，’b> 的意思。

Technically speaking, the compiler is complaining because the type variable 'b is not defined. But of course, if you define it, then you get type Expr<'a, 'b> which has a different meaning.

如果要用F＃表示，则必须使用基于接口的解决方法（接口可以具有通用方法，这为您提供了一种表达方法像这样的约束存在'b ，您在这里需要）。这可能很快就会变得很丑陋，所以我认为这不是一个好方法，但是它看起来像这样：

If you wanted to express this in F#, you'd have to use a workaround based on interfaces (an interface can have generic method, which give you a way to express constraint like exists 'b which you need here). This will probably get very ugly very soon, so I do not think it is a good approach, but it would look something like this:

// Represents an application that returns 'a but consists
// of an argument 'b and a function 'b -> 'a
type IApplication<'a> =
  abstract Appl<'b> : Expr<'b -> 'a> * Expr<'b> -> unit

and Expr<'a> = 
  // Constant just stores a value...
  | Constant    of 'a 
  // An application is something that we can call with an 
  // implementation (handler). The function then calls the
  // 'Appl' method of the handler we provide. As this method
  // is generic, it will be called with an appropriate type
  // argument 'b that represents the type of the argument.
  | Application of (IApplication<'a> -> unit) 

表示（fun（n：int）->字符串n）42 ，您可以这样写：

let expr = 
  Application(fun appl -> 
    appl.Appl(Constant(fun (n:int) -> string n), 
              Constant(42)))

一个用来评估表达式的函数可以这样写：

A function to evaluate the expression can be written like this:

let rec eval<'T> : Expr<'T> -> 'T = function
  | Constant(v) -> v   // Just return the constant
  | Application(f) ->
      // We use a bit of dirty mutable state (to keep types simpler for now)
      let res = ref None
      // Call the function with a 'handler' that evaluates function application
      f { new IApplication<'T> with
            member x.Appl<'A>(efunc : Expr<'A -> 'T>, earg : Expr<'A>) = 
              // Here we get function 'efunc' and argument 'earg'
              // The type 'A is the type of the argument (which can be
              // anything, depending on the created AST)
              let f = eval<'A -> 'T> efunc
              let a = eval<'A> earg
              res := Some <| (f a) }
      res.Value.Value

正如我所说，这有点真正的极端解决方法，因此我认为实际使用它不是一个好主意。我想这样做的F＃方法是使用无类型的 Expr 类型。您能否写更多有关项目总体目标的信息（也许还有另一种好方法）？

As I said, this is a bit really extreme workaround, so I do not think it is a good idea to actually use it. I suppose the F# way of doing this would be to use untyped Expr type. Can you write a bit more about the overall goal of your project (perhaps there is another good approach)?

这篇关于带函数应用的类型化抽象语法树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！