# 機能設計書 85-内部ラムダ変換

## 概要

本ドキュメントは、F#コンパイラにおける内部ラムダのトップレベル関数への変換（TLR: Top Level Representation）機能の設計について記述する。この機能は、ネストしたラムダ式を静的メソッドに変換し、クロージャ割り当てを削減することでパフォーマンスを向上させる。

### 本機能の処理概要

**業務上の目的・背景**：
F#のネストしたラムダ式は、通常クロージャオブジェクトとしてヒープに割り当てられる。本機能は、特定の条件を満たす内部関数をトップレベルの静的メソッドに変換（ラムダリフティング）することで、クロージャの作成を回避し、呼び出しオーバーヘッドを削減する。これにより、再帰関数や頻繁に呼び出される関数のパフォーマンスが向上する。

**機能の利用シーン**：
- 再帰的な内部関数のコンパイル時
- 複数の引数を持つカリー化された関数のコンパイル時
- 自由変数を持つがTLR条件を満たす関数のコンパイル時

**主要な処理内容**：
1. TLR対象の決定とアリティの計算（pass1）
2. 必要な型パラメータと環境の計算（pass2）
3. 環境パッキングと新関数の作成（step3）
4. 定義と呼び出しサイトの書き換え（pass4）
5. 束縛IDの一意性確保（pass5）

**関連システム・外部連携**：
- TypedTree: 型付き抽象構文木の入力元
- TypedTreeOps: TAST操作ユーティリティ
- GlobalUsageAnalysis: 使用情報の収集（DetupleArgs.fsと共有）

**権限による制御**：
特になし。コンパイラ内部の最適化フェーズとして自動的に適用される。

## 関連画面

該当なし（コンパイラ内部機能）

## 機能種別

コンパイラ最適化機能（ラムダリフティング）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| g | TcGlobals | Yes | コンパイラグローバル状態 | null不可 |
| expr | TypedImplFile | Yes | 変換対象の型付き実装ファイル | 有効なTAST |

### 入力データソース

- 型検査済みTAST（TypedTree）
- 関数の使用情報（GlobalUsageAnalysis）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| expr | TypedImplFile | 変換後の型付き実装ファイル |

### 出力先

最適化済みTASTとしてコンパイルパイプラインに渡される

## 処理フロー

### 処理シーケンス

```
1. pass1: TLR対象とアリティの決定
   └─ DetermineTLRAndArities
      ├─ GetUsageInfoOfImplFile: 使用情報の収集
      ├─ SelectTLRVals: TLR候補の選択
      ├─ IsValueRecursionFree: 値再帰がないことを確認
      └─ GetValsBoundUnderShouldInline: インライン対象下の値を除外

2. pass2: 必要な環境の計算
   └─ DetermineReqdItems
      ├─ ExprEnvIntercept: 式をフォールドして環境要件を収集
      ├─ LogRequiredFrom: 環境要件を記録
      ├─ CloseReqdTypars: 型パラメータ要件を閉包
      └─ DumpReqdValMap: デバッグ出力

3. step3: 環境パッキングと新関数作成
   └─ ChooseReqdItemPackings / CreateNewValuesForTLR
      ├─ 環境パック型の選択
      ├─ fHat（変換後関数）の作成
      └─ envpack（環境パック）の作成

4. pass4: 定義と呼び出しの書き換え
   └─ TransformExpr / TransformBindings
      ├─ 定義サイトの変換
      └─ 呼び出しサイトの変換

5. pass5: 束縛IDの一意性確保
   └─ copyExpr
```

### フローチャート

```mermaid
flowchart TD
    A[開始] --> B[pass1: DetermineTLRAndArities]
    B --> C{TLR対象あり?}
    C -->|No| Z[変換なしで終了]
    C -->|Yes| D[pass2: DetermineReqdItems]
    D --> E[step3: CreateNewValuesForTLR]
    E --> F[pass4: TransformExpr]
    F --> G[pass5: copyExpr]
    G --> H[終了]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-85-01 | TLR拒否条件 | mutable、ValInline.Never、byref、メンバー、既存ValReprInfo、ResumableCode、InlineIfLambdaは除外 | IsRefusedTLR関数 |
| BR-85-02 | アリティ決定 | min(仮引数数, 最大適用引数数)をアリティとする | SelectTLRVals関数 |
| BR-85-03 | 値再帰チェック | 相互再帰グループ内で非ラムダ束縛がある場合はTLR不可 | IsValueRecursionFree関数 |
| BR-85-04 | 環境要件 | アリティ充足呼び出しはReqdSubEnv、不足呼び出しはReqdVal | LogRequiredFrom関数 |

### 計算ロジック

- **TLR条件**: (a)十分な引数、(b)自由型パラメータなし、(c)自由変数がTLRで適切に呼び出される
- **アリティ計算**: `min(nFormals, nMaxApplied)`
- **環境パック**: 直接呼び出しにはsubenv、それ以外には値そのものを含む

## データベース操作仕様

該当なし（メモリ内変換のみ）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| internalError | 内部エラー | 予期しない状態 | エラー終了（バグを示す） |

### リトライ仕様

リトライなし。

## トランザクション仕様

該当なし（ステートレス変換）

## パフォーマンス要件

- 変換処理はコンパイル時のみ実行
- TLR変換によりクロージャ割り当てを削減
- 静的メソッド呼び出しによる呼び出しオーバーヘッド削減

## セキュリティ考慮事項

該当なし

## 備考

- トップレベル関数とメソッドは既にTLR表現を持つため対象外（33-35行目コメント）
- `verboseTLR`変数でデバッグ出力を制御可能
- 相互再帰関数は共通の環境（fclass）を共有

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

まず、TLR変換で使用される主要なデータ型を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | BindingGroupSharingSameReqdItems型（300-313行目） |
| 1-2 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | ReqdItem型（320-326行目） |
| 1-3 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | ReqdItemsForDefn型（339-362行目） |

**主要な型定義**:
- **300-313行目**: `BindingGroupSharingSameReqdItems` - 共通環境を共有する相互再帰バインディンググループ
- **320-326行目**: `ReqdItem` - 環境要件（ReqdSubEnv: 環境全体, ReqdVal: 値そのもの）
- **339-362行目**: `ReqdItemsForDefn` - 定義に必要な型パラメータと値/サブ環境

**読解のコツ**: TLR変換の核心は「どの値/環境が必要か」を計算すること。ReqdItemがその単位。

#### Step 2: pass1を理解する

TLR対象の決定とアリティ計算を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | Pass1_DetermineTLRAndArities（173-239行目） |
| 2-2 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | IsRefusedTLR関数（146-158行目） |

**主要処理フロー**:
- **146-158行目**: `IsRefusedTLR` - TLR拒否条件
  - mutable、ValInline.Never、byref、メンバー、既存ValReprInfo、ResumableCode、InlineIfLambda
- **175-179行目**: `GetMaxNumArgsAtUses` - 最大適用引数数の取得
- **181-202行目**: `SelectTLRVals` - TLR候補の選択
- **206-210行目**: `IsValueRecursionFree` - 値再帰チェック
- **216-239行目**: `DetermineTLRAndArities` - メイン関数

#### Step 3: pass2を理解する

必要な環境要件の計算を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | Pass2_DetermineReqdItems（374行目〜） |
| 3-2 | InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | ExprEnvIntercept関数（494-566行目） |

**主要処理フロー**:
- **423-430行目**: `state` - 収集状態（stack、reqdItemsMap、fclassM、revDeclist、recShortCallS）
- **440-446行目**: `PushFrame` - 新しいfclass用のフレームをプッシュ
- **449-460行目**: `SaveFrame` - 収集した環境を保存
- **463-472行目**: `LogRequiredFrom` - 環境要件を記録
- **494-566行目**: `ExprEnvIntercept` - 式をフォールドして要件を収集
- **571-600行目**: `CloseReqdTypars` - 型パラメータ要件の閉包（固定点計算）

### プログラム呼び出し階層図

```
MakeTopLevelRepresentationDecisions (g, expr)
    │
    ├─ pass1: DetermineTLRAndArities (g, expr)
    │      ├─ GetUsageInfoOfImplFile (g, expr)
    │      ├─ SelectTLRVals (g, xinfo, f, e)
    │      │      └─ IsRefusedTLR (g, f)
    │      │      └─ GetMaxNumArgsAtUses (xinfo, f)
    │      ├─ IsValueRecursionFree (xinfo, f)
    │      └─ GetValsBoundUnderShouldInline (xinfo)
    │
    ├─ pass2: DetermineReqdItems (g, expr, tlrS, arityM)
    │      ├─ FoldExpr (ExprEnvIntercept, state0, expr)
    │      │      ├─ accInstance / LogRequiredFrom / LogShortCall
    │      │      ├─ accBinds / PushFrame / SaveFrame
    │      │      └─ FreeInBindings
    │      ├─ CloseReqdTypars (fclassM, reqdItemsMap)
    │      └─ DumpReqdValMap (reqdItemsMap)
    │
    ├─ step3: ChooseReqdItemPackings / CreateNewValuesForTLR
    │      ├─ 環境パック型の決定
    │      ├─ fHat (変換後関数) の作成
    │      └─ envpack (環境パック) の作成
    │
    ├─ pass4: TransformExpr / TransformBindings
    │      ├─ 定義サイトの変換
    │      │      └─ [[f = LAM tps. lam xs. body]] → fHat = LAM (tps ++ reqdTypars). lam (xs ++ env). ...
    │      └─ 呼び出しサイトの変換
    │             └─ [[f @ tps args]] → fHat @ (tps ++ reqdTypars) (args ++ envpack)
    │
    └─ pass5: copyExpr
           └─ 束縛IDの一意性を確保
```

### データフロー図

```
[入力]                        [pass1]                       [pass2]

TypedImplFile
    │
    ▼
GetUsageInfoOfImplFile ────▶ xinfo (Results)
                                   │
                                   ▼
                            SelectTLRVals
                                   │
                                   ├─▶ tlrS (TLR対象の集合)
                                   │
                                   └─▶ arityM (f → arity マップ)
                                              │
                                              ▼
                            DetermineReqdItems
                                   │
                                   ├─▶ reqdItemsMap (fclass → ReqdItemsForDefn)
                                   │
                                   ├─▶ fclassM (f → fclass)
                                   │
                                   └─▶ declist (fclass リスト)
                                              │
                                              ▼
                            ChooseReqdItemPackings / CreateNewValuesForTLR
                                   │
                                   ├─▶ fHatMap (f → fHat)
                                   │
                                   └─▶ envpackMap (f → envpack expr)
                                              │
                                              ▼
                            TransformExpr / TransformBindings
                                              │
                                              ▼
                                        copyExpr
                                              │
                                              ▼
                                    変換済みTypedImplFile
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| InnerLambdasToTopLevelFuncs.fs | `src/Compiler/Optimize/InnerLambdasToTopLevelFuncs.fs` | ソース | TLR変換の実装 |
| DetupleArgs.fs | `src/Compiler/Optimize/DetupleArgs.fs` | ソース | GlobalUsageAnalysis（共有） |
| TypedTree.fs | `src/Compiler/TypedTree/TypedTree.fs` | ソース | TAST型定義 |
| TypedTreeOps.fs | `src/Compiler/TypedTree/TypedTreeOps.fs` | ソース | TAST操作ユーティリティ |
| TcGlobals.fs | `src/Compiler/TypedTree/TcGlobals.fs` | ソース | グローバル型情報 |
