함수 응용 프로그램이있는 형식화 된 추상 구문 트리

Question

함수 응용 프로그램을 나타낼 수있는 형식화 된 추상 구문 트리 데이터 형식을 작성하려고합니다. 내가 잘못이 문제에 접근하고있다 -

은 지금까지 나는

이

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

내가 마지막 줄에 '모든 B의'같은 것을 작성하는 F #에서 방법이라고 생각하지 않습니다 있나요?

Answer 1

일반적으로 F # 유형 시스템은 입력 된 추상 구문 트리를 사용자의 예제와 같이 (직접적으로) 정의하기에 충분하지 않습니다. 이것은 F #에서 지원되지 않는 generalized algebraic data types (GADTs)을 사용하여 수행 할 수 있습니다 (Haskell과 OCaml에서 사용 가능하지만). F #에서 이것을 사용하는 것이 좋겠지 만 언어가 좀 더 복잡해 졌다고 생각합니다.

변수 변수 'b이 정의되어 있지 않기 때문에 기술적으로 컴파일러가 불평합니다. 그러나 물론 그것을 정의하면 다른 의미를 갖는 Expr<'a, 'b> 유형이 생깁니다.

F #에서 이것을 표현하고 싶다면 인터페이스를 기반으로하는 해결 방법을 사용해야합니다 (인터페이스에 일반 메서드가있어서 제약 조건을 표현할 수 있습니다). 여기에 exists 'b과 같은 제약 조건을 표현할 수 있습니다. 이것은 아마 곧 매우 추한 것, 그래서 그것이 좋은 방법이라고 생각하지 않는다,하지만 이런 식으로 뭔가 보일 것이다 :

을 :

// 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) -> string n) 42의 식 트리를 표현하기를, 당신은 뭔가를 쓸 수

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 

내가 말했듯이, 이것은 조금 정말 극단적 인 해결 방법, 그래서 내가 생각하지 않습니다 :

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

식을 평가하는 기능은 다음과 같이 쓸 수있다 실제로 사용하는 것은 좋은 생각입니다. 이 일을하는 F # 방식이 형식이 지정되지 않은 Expr 유형을 사용하는 것이 겠지요. 프로젝트의 전반적인 목표에 대해 좀 더 자세히 기술 할 수 있습니까 (다른 좋은 접근 방법이있을 수 있습니다)?