scala - JVM 语言中如何编译嵌套函数和词法作用域？

Question

作为我的问题的一个具体示例，这是 Python 中的一个片段(它应该对最广泛的人可读，并且无论如何都有一个 JVM 实现):

def memo(f):
  cache = {}
  def g(*args):
    if args not in cache:
      cache[args] = f(*args)
    return cache[args]
  return g

工业级语言如何编译这样的定义，以实现静态作用域？如果我们只有嵌套定义但没有更高阶的函数值参数或返回值，像 Pascal 那样(因此不需要闭包)怎么办？我猜计算静态链接已经过时了，因为您无法访问方法调用的堆栈帧。那么一般是怎么做的呢？他们构建匿名内部类吗？ Lambda 提升？还有什么？

对不起，如果这是以前被问过的问题；似乎必须如此，但我还没有发现任何正确的地方。

Answer 1

我将从 Clojure 的角度回答您的问题，Clojure 是唯一一种我非常了解其翻译策略的 JVM 语言。为具体起见，我已将您的 Python 翻译为以下 Clojure(不是惯用的或线程安全的，但这在这里并不重要):

(defn memo [f]
  (let [cache (atom {})]
    (fn g [& args]
      (when-not (contains? (@cache args))
        (swap! cache assoc args (apply f args)))
      (get @cache args))))

内部类(在问题和评论中提到)对程序员来说很方便，编译器不需要它们1。每个 Clojure 函数定义(不是函数调用!)对应于一个实现 clojure.lang.IFn 的顶级类(通常通过一些抽象的辅助类)。在那个类中，每个封闭的词法变量都保存为一个字段；这些在构造函数中初始化。所以这个函数定义扩展为:

class memo extends AFunction {
  // static constants...
  public Object invoke(Object f) {
    Object cache = ...;
    return new memo$g__1723(cache);
  }
}

class memo$g__1723 extends RestFn {
  static Object swap_BANG_ = RT.var("clojure.core", "swap!");
  static Object assoc = RT.var("clojure.core", "assoc");
  static Object apply = RT.var("clojure.core", "apply");
  // ... more static constants for each function used ...

  Object f;
  Object cache;

  public memo$g__1723(Object f, Object cache) {
    this.f = f;
    this.cache = cache;
  }

  public int getRequiredArity() { return 0;}

  public Object applyTo(ISeq args) {
    Object cache = this.cache;
    if (/*...*/) {
      ((IFn)swap_BANG_).invoke(cache, assoc, args,
          ((IFn)apply).invoke(this.f, args));
    }
    return /*...*/;
  }
}

1事实上，在 Clojure 所针对的 Java 版本中，内部类并不存在于 JVM 级别——它们是 Java 编译器通过 secret 访问机制将内部类转换为单独的顶级类的虚构，就像 Clojure 将嵌套函数转换为顶级类(class)。在最新版本的 Java 中，VM 本身确实理解嵌套类。

为完整起见， memo 的完整反汇编字节码其内部功能如下。

$ javap -c -p 'tmp$memo' 'tmp$memo$g__1723'
Compiled from "tmp.clj"
public final class tmp$memo extends clojure.lang.AFunction {
  public static final clojure.lang.Var const__0;

  public tmp$memo();
    Code:
       0: aload_0
       1: invokespecial #9                  // Method clojure/lang/AFunction."<init>":()V
       4: return

  public static java.lang.Object invokeStatic(java.lang.Object);
    Code:
       0: getstatic     #15                 // Field const__0:Lclojure/lang/Var;
       3: invokevirtual #21                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
       6: checkcast     #23                 // class clojure/lang/IFn
       9: getstatic     #29                 // Field clojure/lang/PersistentArrayMap.EMPTY:Lclojure/lang/PersistentArrayMap;
      12: invokeinterface #32,  2           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
      17: astore_1
      18: new           #34                 // class tmp$memo$g__1723
      21: dup
      22: aload_1
      23: aconst_null
      24: astore_1
      25: aload_0
      26: aconst_null
      27: astore_0
      28: invokespecial #37                 // Method tmp$memo$g__1723."<init>":(Ljava/lang/Object;Ljava/lang/Object;)V
      31: areturn

  public java.lang.Object invoke(java.lang.Object);
    Code:
       0: aload_1
       1: aconst_null
       2: astore_1
       3: invokestatic  #42                 // Method invokeStatic:(Ljava/lang/Object;)Ljava/lang/Object;
       6: areturn

  public static {};
    Code:
       0: ldc           #45                 // String clojure.core
       2: ldc           #47                 // String atom
       4: invokestatic  #53                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
       7: checkcast     #17                 // class clojure/lang/Var
      10: putstatic     #15                 // Field const__0:Lclojure/lang/Var;
      13: return
}
Compiled from "tmp.clj"
public final class tmp$memo$g__1723 extends clojure.lang.RestFn {
  java.lang.Object cache;

  java.lang.Object f;

  public static final clojure.lang.Var const__0;

  public static final clojure.lang.Var const__1;

  public static final clojure.lang.Var const__2;

  public static final clojure.lang.Var const__3;

  public static final clojure.lang.Var const__4;

  public tmp$memo$g__1723(java.lang.Object, java.lang.Object);
    Code:
       0: aload_0
       1: invokespecial #13                 // Method clojure/lang/RestFn."<init>":()V
       4: aload_0
       5: aload_1
       6: putfield      #15                 // Field cache:Ljava/lang/Object;
       9: aload_0
      10: aload_2
      11: putfield      #17                 // Field f:Ljava/lang/Object;
      14: return

  public java.lang.Object doInvoke(java.lang.Object);
    Code:
       0: getstatic     #23                 // Field const__0:Lclojure/lang/Var;
       3: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
       6: checkcast     #31                 // class clojure/lang/IFn
       9: getstatic     #34                 // Field const__1:Lclojure/lang/Var;
      12: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
      15: checkcast     #31                 // class clojure/lang/IFn
      18: aload_0
      19: getfield      #15                 // Field cache:Ljava/lang/Object;
      22: invokeinterface #37,  2           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
      27: checkcast     #31                 // class clojure/lang/IFn
      30: aload_1
      31: invokeinterface #37,  2           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
      36: invokeinterface #37,  2           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
      41: dup
      42: ifnull        56
      45: getstatic     #43                 // Field java/lang/Boolean.FALSE:Ljava/lang/Boolean;
      48: if_acmpeq     57
      51: aconst_null
      52: pop
      53: goto          102
      56: pop
      57: getstatic     #46                 // Field const__2:Lclojure/lang/Var;
      60: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
      63: checkcast     #31                 // class clojure/lang/IFn
      66: aload_0
      67: getfield      #15                 // Field cache:Ljava/lang/Object;
      70: getstatic     #49                 // Field const__3:Lclojure/lang/Var;
      73: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
      76: aload_1
      77: getstatic     #52                 // Field const__4:Lclojure/lang/Var;
      80: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
      83: checkcast     #31                 // class clojure/lang/IFn
      86: aload_0
      87: getfield      #17                 // Field f:Ljava/lang/Object;
      90: aload_1
      91: invokeinterface #55,  3           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
      96: invokeinterface #58,  5           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
     101: pop
     102: getstatic     #34                 // Field const__1:Lclojure/lang/Var;
     105: invokevirtual #29                 // Method clojure/lang/Var.getRawRoot:()Ljava/lang/Object;
     108: checkcast     #31                 // class clojure/lang/IFn
     111: aload_0
     112: getfield      #15                 // Field cache:Ljava/lang/Object;
     115: invokeinterface #37,  2           // InterfaceMethod clojure/lang/IFn.invoke:(Ljava/lang/Object;)Ljava/lang/Object;
     120: aload_1
     121: aconst_null
     122: astore_1
     123: invokestatic  #63                 // Method clojure/lang/RT.get:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
     126: areturn

  public int getRequiredArity();
    Code:
       0: iconst_0
       1: ireturn

  public static {};
    Code:
       0: ldc           #70                 // String clojure.core
       2: ldc           #72                 // String contains?
       4: invokestatic  #76                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
       7: checkcast     #25                 // class clojure/lang/Var
      10: putstatic     #23                 // Field const__0:Lclojure/lang/Var;
      13: ldc           #70                 // String clojure.core
      15: ldc           #78                 // String deref
      17: invokestatic  #76                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
      20: checkcast     #25                 // class clojure/lang/Var
      23: putstatic     #34                 // Field const__1:Lclojure/lang/Var;
      26: ldc           #70                 // String clojure.core
      28: ldc           #80                 // String swap!
      30: invokestatic  #76                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
      33: checkcast     #25                 // class clojure/lang/Var
      36: putstatic     #46                 // Field const__2:Lclojure/lang/Var;
      39: ldc           #70                 // String clojure.core
      41: ldc           #82                 // String assoc
      43: invokestatic  #76                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
      46: checkcast     #25                 // class clojure/lang/Var
      49: putstatic     #49                 // Field const__3:Lclojure/lang/Var;
      52: ldc           #70                 // String clojure.core
      54: ldc           #84                 // String apply
      56: invokestatic  #76                 // Method clojure/lang/RT.var:(Ljava/lang/String;Ljava/lang/String;)Lclojure/lang/Var;
      59: checkcast     #25                 // class clojure/lang/Var
      62: putstatic     #52                 // Field const__4:Lclojure/lang/Var;
      65: return
}