日: 2016年12月23日

構文木変形の難しさ

構文木の変形には、一種のロマンがあります（たぶん ;)

しかし、実際には「死ぬほど大変」です。この記事を読んでいる人は、おそらくF# Compiler ServiceやRoslynを日常的に触っていると思う :) ので、それがいかに大変かおわかりいただけると思います。LINQのExpressionTreeも大概ですが、あれが更に複雑になったものと思ってもらえれば良いと思います。

# なお、ExpressionTreeについては、Advent LINQの後半の記事や、Final LINQ Extensions IIIが参考になると思います。

前述のsample-filterで示したような変形を実現するには、狙った場所に対応する構文木がどのような構造で現れ、それをどのように変形すれば目的を達成できるのかを、慎重に検討しなければなりません。

構文木は再帰構造で定義されます。そのため、いい加減な判定を行うと、意図しない箇所を変形してしまう可能性があります。また、ソースコード上では些細な違いでも、構文木上ではドラスティックに変わってしまったりすることもあります。

例えば、以下のようなコードを考えます:

// 一般的な.NETのメソッド（タプル形式）
let output1 (a: int, b: string, c: double) =
  System.Console.WriteLine("output1: {0}:{1}:{2}", a, b, c)

// F#関数（カリー化可能形式）
let output2 (a: int) (b: string) (c: double) =
  System.Console.WriteLine("output2: {0}:{1}:{2}", a, b, c)

output1は、典型的な.NET標準のメソッドと呼べるでしょう。しかし、output2はF#らしい「関数」です。このoutput2を呼び出すコードを書いたとします:

// 一般的な.NETのメソッド呼び出し（タプル形式）
// (int * string * double) -> unit
output1 (123, "ABC", 456.789)

// F#関数の呼び出し（カリー化可能形式）
// int -> string -> double -> unit
output2 123 "ABC" 456.789

.NETメソッド形式は、以下のF#関数と区別して「タプル形式」と呼んでいます。構文木上でも、引数部分が「タプル」のように見え、一つのタプル値を引数に渡しているかのように解釈されます。F#関数は「カリー化可能形式」です。カリー化可能の場合の関数呼び出しは、部分適用された関数が連続的に適用されていくような感じに解釈されます。そして、構文木上もネストされた関数呼び出し（Appノード）で表現されます。

構文木が可視化できないと、ここら辺の検討が絶望的に大変なので、小さなツールですが構文木をF#コードっぽくダンプするツールを作りました（可視化が目的だったので、完成度は高くありません）。これを使うと、以下のような出力が得られます:

// 以下がoutput1の呼び出し
Ast.SynExpr.App( (* expr1 *)          // App - output1(...)
  ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
  false (* isInfix *),
  Ast.SynExpr.Ident( (* funcExpr *)
    output1 (* Item *)),
  Ast.SynExpr.Paren( (* argExpr *)    // Paren --> Tuple : タプル形式の引数
    Ast.SynExpr.Tuple( (* expr *)
      [ (* exprs *)                   // タプルの中身をリストで表現
        Ast.SynExpr.Const( (* [0] *)
          Ast.SynConst.Int32( (* constant *)
            123 (* Item *)));
        Ast.SynExpr.Const( (* [1] *)
          Ast.SynConst.String( (* constant *)
            "ABC" (* text *)));
        Ast.SynExpr.Const( (* [2] *)
          Ast.SynConst.Double( (* constant *)
            456.789 (* Item *)))],
      [ (* commaRanges *)]),
    range>.Some( (* rightParenRange *)))),

// 以下がoutput2の呼び出し
Ast.SynExpr.App( (* expr2 *)          // App - 456.789の適用
  ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
  false (* isInfix *),
  Ast.SynExpr.App( (* funcExpr *)     // App - "ABC"の適用
    ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
    false (* isInfix *),
    Ast.SynExpr.App( (* funcExpr *)   // App - output2に対して123の適用
      ExprAtomicFlag.NonAtomic (* exprAtomicFlag *),
      false (* isInfix *),
      Ast.SynExpr.Ident( (* funcExpr *)
        output2 (* Item *)),
      Ast.SynExpr.Const( (* argExpr *)
        Ast.SynConst.Int32( (* constant *)
          123 (* Item *)))),
    Ast.SynExpr.Const( (* argExpr *)
      Ast.SynConst.String( (* constant *)
        "ABC" (* text *)))),
  Ast.SynExpr.Const( (* argExpr *)
    Ast.SynConst.Double( (* constant *)
      456.789 (* Item *))))),

出力が冗長で見難いのですが、output1とoutput2では、引数がリストで表現されているか、ネストされた関数として表現されているかで全く構造が異なることが分かります。カリー化可能形式とは、実は以下のような呼び出しであることが分かります:

// F#関数の呼び出し（カリー化可能形式）
// int -> string -> double -> unit
output2 123 "ABC" 456.789

// 実はこういう事:
((output2 123) "ABC") 456.789

// さらに分解すると:
let f1 = output2 123  // f1は高階関数
let f2 = f1 "ABC"     // f2は高階関数
f2 456.789

ソースコードの些細な違いが、構文木上で大幅に異なる表現となる場合があるため、ビジターパターンで探索する場合に注意が必要です。実際のところ非常に難しい…

# 余談ですが、構文木の解析が非常に大変だった経験から、先日のNGK2016BのLTネタ: 「You will be assimilated. Resistance is futile.」が生み出された、みたいな背景があります。Roslynなので、fscxとは全然関係ないのですが :)

// コンテキストクラス（関数を抜ける際に実行するメソッドを定義）
type SampleAspectContext internal (body: string) =
  // Finish aspect (trigger are leaved method with return value)
  member __.Leave(result: 'T) : 'T =
    Console.WriteLine("Leave: " + body)
    result
  // Finish aspect (trigger are leaved method with exception)
  member __.Caught(ex: exn) : unit =
    Console.WriteLine("Caught: " + body + ": " + ex.ToString())

// 関数を呼び出す際に呼び出されるメソッドを定義
type SampleAspect() =
  // Start aspect (trigger are entered method)
  static member Enter(methodName: string, fileName: string, line: int, column: int, args: obj[]) =
    let body =
      String.Format
        ("{0}({1}, {2}): {3}({4})",
         fileName,
         line,
         column,
         methodName,
         String.Join(", ", args |> Seq.map (sprintf "%A")))
    Console.WriteLine("Enter: " + body)
    new SampleAspectContext(body)

// SampleAspectクラスをアスペクトとして使用するフィルタを定義する
[<Sealed>]
type SampleAspectLoggerDeclaration() =
  // 依存関係を増やさないために、クラス名を文字列で指定
  inherit DeclareFscxInjectAspectVisitor("SampleAspectLogger.SampleAspect")

let f11 (a: int, b: string, c: int) =
  output1(a + c, b, 123.456)

let f11 (a: int, b: string, c: int) =
  let __arg_0 = a + c
  let __arg_1 = b
  let __arg_2 = 123.456
  let __context =
    SampleAspectLogger.SampleAspect.Enter
      ("f11", "SampleCode.fs", 2, 3, [|__arg_0, __arg_1, __arg_2|])
  try
    __context.Leave(output1(__arg_0, __arg_1, __arg_2))
  with
  | ex ->
    __context.Caught(ex)
    reraise()

The filter’s middleware

So we can do anything by filter library AND implementation are very hard work. Then I’m thinking about how to do easier it…
I’m trying to design the helper library: “FSharp.Expandable.Compiler.Aspect.”

Will we have what intercept anything (by fscx)? This library is “Middleware” for fscx, we can safe implements for insert custom code between enter and leave function points. Today, we are calling the “AOP (Aspect oriented paradigm)” for this technics.

If we use this helper library by develop filter library in this case, our filter code are simple, safe and more easier.

For example below:

// This is "Aspect context" class
type SampleAspectContext internal (body: string) =
  // Finish aspect (trigger are leaved method with return value)
  member __.Leave(result: 'T) : 'T =
    Console.WriteLine("Leave: " + body)
    result
  // Finish aspect (trigger are leaved method with exception)
  member __.Caught(ex: exn) : unit =
    Console.WriteLine("Caught: " + body + ": " + ex.ToString())

// This is "Aspect" class
type SampleAspect() =
  // Start aspect (trigger are entered method)
  static member Enter(methodName: string, fileName: string, line: int, column: int, args: obj[]) =
    let body =
      String.Format
        ("{0}({1}, {2}): {3}({4})",
         fileName,
         line,
         column,
         methodName,
         String.Join(", ", args |> Seq.map (sprintf "%A")))
    Console.WriteLine("Enter: " + body)
    new SampleAspectContext(body)

This sample codes (Called “Aspect code”) are printing to console for function call message between enter and leave (include caught exception). “SampleAspect.Enter(…)” method is calling from before function call and “SampleAspectContext.Leave(…)” or “Caught(…)”
methods are calling from after function called.

“Enter(…)” method received the method name, source code file name, line/column number and will be calling with arguments. This sample codes prints these information to Console and create instance for “SampleAspectContext” class and return.

“Leave(…)” or “Caught(…)” handles to print leave messages. “Leave(…)” can receive for function called result. “Caught(…)” can receive for exception instance.

These aspect codes are truly “Duck-typed.” fscx will be identicate and not require any base classes and any interfaces. Because if request these types, we have .NET assembly referencing problem and fix this problem for very hard on packaging by NuGet :(

Ready for aspect named “SampleAspect” class. Next step, how to identicate this aspect for “FSharp.Expandable.Compiler.Aspect?” :

// This is declaring for aspect: "SampleAspect" class.
// Class name is free.
[<Sealed>]
type SampleAspectLoggerDeclaration() =
  // Construct with aspect class name. This is duck-typed naming (by string.)
  inherit DeclareFscxInjectAspectVisitor("SampleAspectLogger.SampleAspect")

Totally aspect tips: Aspect codes and this declaration requests loose types, so we can write aspects by C#.

This declaration contains on filter library, fscx can find and translate:

• If fscx is targeting for a function, fscx insert custom AST nodes before calling function. Call to “SampleAspect.Enter(…)”
• And fscx insert custom AST nodes after called function. Call to “SampleAspectContext.Leave(…)” or “Caught(…).” Leave with called function result value, Caught with exception instance by (inserted) try-with block.

This sample code fragment:

let f11 (a: int, b: string, c: int) =
  output1(a + c, b, 123.456)

Translate to:

let f11 (a: int, b: string, c: int) =
  let __arg_0 = a + c
  let __arg_1 = b
  let __arg_2 = 123.456
  let __context =
    SampleAspectLogger.SampleAspect.Enter
      ("f11", "SampleCode.fs", 2, 3, [|__arg_0, __arg_1, __arg_2|])
  try
    __context.Leave(output1(__arg_0, __arg_1, __arg_2))
  with
  | ex ->
    __context.Caught(ex)
    reraise()

This sample code declare “f11(…)” by tupled arguments method, sure can translate for function by curryable arguments.

Totally at this point: We have only the aspect classes “SampleAspect, SampleAspectContext” and aspect declaration “SampleAspectLoggerDeclaration”. These are contains no AST translation codes… Oh I made it! :)

Currently, I’m developing “FSharp.Expandable.Compiler.Aspect” now and not finish, because how to set where insert aspects to the target function.

Conclusion

fscx is challenging project for me. This project has several points:

• fscx is easy-usage (by install NuGet) for any filter users.
• We can develop any auto translation by ASTs (but very difficult).
• We can develop easier any AOP based senarios by using fscx’s middleware.
• All filter libraries can deploy by NuGet packaged.

The myth: We write OOP based codes by F# that’s hassle. Because if we become to FP, a little bit tired for declare many class and/or interface word elements. (It’s myth! don’t make seriously :)

We often write for UI codes, for example how to implement “INotifyPropertyChanged.” fscx is capable for can filtering auto-implement this interface, these senarios capsule to the middleware and running this code by no runtime cost. Finally we can construct ecosystem for filter libraries.

Acknowledgments: Thanks cooperation for On the road corporation and Mr. bleis.

Thank you for reading, welcome any comments! Happy christmas!!