如何基于带嵌套链接的活动记录在Java中实现给定SML嵌套函数

背景说明 #

需要在不支持原生嵌套函数的Java中，模拟实现SML的三层嵌套函数逻辑，要求使用带嵌套链接的活动记录技术解决非局部变量访问问题。

待实现的SML原始代码 #

fun h (x,y) =
  let
    val z = x+1
    fun g w =
      let
        val z = y + 1
        fun f x =
          if x = 0 then 0
          else z + x + g(w - 1)
      in
        if w = 0 then x
        else z + f(w - 1)
      end
  in
    if x = 0 then g y
    else z + g(h(x - 1, y))
  end;

当前未完成的Java代码 #

public int f(int w, int x, int y, int z) {
    if (x == 0) {
        return 0;
    } 
    else {
        return (z + x + g(w - 1, y));
    }
}

public int g(int w, int y) {
    int z = y + 1;
    return z;
}

public void h(int w, int x, int y) {
    int z = x + 1;
    g(w, y);
    f(w, x, y, z);
}

public void last(int w, int x, int y, int z) {
    
}

作业要求 #

1. 函数g嵌套在h内、f嵌套在g内，最终完整复现上述SML代码的计算逻辑
2. 必须使用带嵌套链接的活动记录技术解决外层函数非局部变量的访问问题
3. 无需设计通用活动记录，仅需为h、g、f三个函数分别定义对应活动记录即可
4. 每个活动记录需包含以下信息：
   • 所属函数的名称
   • 存储所有局部变量及其值的符号表
   • 返回地址，即当前函数执行完毕、恢复调用方活动记录后继续执行的位置
   • 指向调用方活动记录的指针
   • 用于解析非局部变量的嵌套链接
   • 存储当前计算返回结果的位置

实现思路与完整代码 #

首先定义活动记录基类，再分别实现三个函数的专属活动记录，通过嵌套链接逐层向上查找非局部变量，无需将外层变量作为参数传递给内层函数：

活动记录定义 #

import java.util.HashMap;
import java.util.Map;

// 活动记录基类
abstract class ActivationRecord {
    String funcName; // 所属函数名
    Map<String, Integer> localVars = new HashMap<>(); // 局部变量符号表
    int returnAddress; // 返回地址，用整数标记执行位置即可
    ActivationRecord caller; // 调用方活动记录指针
    ActivationRecord nestedLink; // 嵌套链接，指向外层函数的活动记录
    int result; // 存储返回结果
}

// h函数的活动记录（最外层函数）
class HActivationRecord extends ActivationRecord {
    public HActivationRecord(int x, int y, ActivationRecord caller) {
        this.funcName = "h";
        this.localVars.put("x", x);
        this.localVars.put("y", y);
        this.localVars.put("z", x + 1); // h内部定义的局部变量z
        this.caller = caller;
        this.nestedLink = null; // 最外层函数无外层作用域，嵌套链接为空
    }
}

// g函数的活动记录（嵌套在h内）
class GActivationRecord extends ActivationRecord {
    public GActivationRecord(int w, ActivationRecord caller, ActivationRecord nestedLink) {
        this.funcName = "g";
        this.localVars.put("w", w);
        // 非局部变量y通过嵌套链接从h的活动记录获取
        int y = nestedLink.localVars.get("y");
        this.localVars.put("z", y + 1); // g内部定义的局部变量z
        this.caller = caller;
        this.nestedLink = nestedLink; // 嵌套链接指向外层h的活动记录
    }
}

// f函数的活动记录（嵌套在g内）
class FActivationRecord extends ActivationRecord {
    public FActivationRecord(int x, ActivationRecord caller, ActivationRecord nestedLink) {
        this.funcName = "f";
        this.localVars.put("x", x);
        this.caller = caller;
        this.nestedLink = nestedLink; // 嵌套链接指向外层g的活动记录
    }
}

函数逻辑实现 #

public class NestedFuncSimulator {
    // 执行f函数逻辑
    private static int execF(FActivationRecord ar) {
        int x = ar.localVars.get("x");
        if (x == 0) {
            ar.result = 0;
            return 0;
        }
        // 非局部变量z从g的活动记录（当前ar的嵌套链接）获取
        int z_g = ar.nestedLink.localVars.get("z");
        // 非局部变量w从g的活动记录获取
        int w_g = ar.nestedLink.localVars.get("w");
        // 创建g的活动记录，嵌套链接指向g的外层h的活动记录
        GActivationRecord gAr = new GActivationRecord(w_g - 1, ar, ar.nestedLink.nestedLink);
        int gRes = execG(gAr);
        ar.result = z_g + x + gRes;
        return ar.result;
    }

    // 执行g函数逻辑
    private static int execG(GActivationRecord ar) {
        int w = ar.localVars.get("w");
        // 非局部变量x从h的活动记录（当前ar的嵌套链接）获取
        int x_h = ar.nestedLink.localVars.get("x");
        if (w == 0) {
            ar.result = x_h;
            return x_h;
        }
        int z_g = ar.localVars.get("z");
        // 创建f的活动记录，嵌套链接指向当前g的活动记录
        FActivationRecord fAr = new FActivationRecord(w - 1, ar, ar);
        int fRes = execF(fAr);
        ar.result = z_g + fRes;
        return ar.result;
    }

    // 对外暴露的h函数执行入口
    public static int execH(int x, int y) {
        HActivationRecord ar = new HActivationRecord(x, y, null);
        if (x == 0) {
            // 调用g，参数为y，嵌套链接指向当前h的活动记录
            GActivationRecord gAr = new GActivationRecord(y, ar, ar);
            ar.result = execG(gAr);
            return ar.result;
        }
        int z_h = ar.localVars.get("z");
        // 递归调用h(x-1,y)
        int hRes = execH(x - 1, y);
        // 调用g，参数为h的返回值，嵌套链接指向当前h的活动记录
        GActivationRecord gAr = new GActivationRecord(hRes, ar, ar);
        int gRes = execG(gAr);
        ar.result = z_h + gRes;
        return ar.result;
    }

    // 测试入口
    public static void main(String[] args) {
        // 该函数计算结果增长极快，仅用小参数测试即可，示例为h(1,1)
        System.out.println(execH(1, 1));
    }
}

非局部变量访问规则说明 #

所有内层函数需要访问的外层变量都无需作为参数传递，仅通过自身活动记录的嵌套链接向上逐层查找即可，完全复现SML嵌套函数的作用域规则：

• f访问g的z、w：直接通过f的嵌套链接（指向g活动记录）读取对应变量
• g访问h的x、y：直接通过g的嵌套链接（指向h活动记录）读取对应变量

内容的提问来源于stack exchange，提问作者Reddy