嵌套函数和词法作用域是如何用 JVM 语言编译的?
How are nested functions and lexical scope compiled in JVM languages?
作为我的问题的一个具体示例,这是 Python 中的一个片段(它应该对最广泛的人来说是可读的,并且无论如何都有一个 JVM 实现):
def memo(f):
cache = {}
def g(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return g
工业级语言如何编译这样的定义,以实现静态作用域?如果我们只有嵌套定义但没有高阶函数值参数或 return 值,à la Pascal(因此不需要闭包)怎么办?我猜计算静态链接已经过时了,因为您无法访问方法调用的堆栈帧。那么一般是怎么做的呢?他们建立匿名内部 类 吗?拉姆达提升?还有别的吗?
抱歉,如果这是一个以前被问过的问题;好像一定是,但是我还没找到什么很对的。
我将从 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))))
内部classes(在问题和评论中提到)是为程序员提供的便利,编译器不需要它们1。每个 Clojure 函数定义(不是函数调用!)对应于一个顶层 class 实现 clojure.lang.IFn(通常通过一些抽象助手 class)。在class中,每个封闭的词法变量都保存为一个字段;这些在构造函数中初始化。所以这个函数定义扩展为:
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 版本中,内部 classes 在 JVM 级别不存在 - 它们是java 编译器翻译成具有秘密访问机制的单独顶级 classes 的虚构,就像 Clojure 将嵌套函数翻译成顶级 classes 一样。在 Java 的更新版本中,VM 本身确实理解嵌套 classes.
为了完整起见,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
}
作为我的问题的一个具体示例,这是 Python 中的一个片段(它应该对最广泛的人来说是可读的,并且无论如何都有一个 JVM 实现):
def memo(f):
cache = {}
def g(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return g
工业级语言如何编译这样的定义,以实现静态作用域?如果我们只有嵌套定义但没有高阶函数值参数或 return 值,à la Pascal(因此不需要闭包)怎么办?我猜计算静态链接已经过时了,因为您无法访问方法调用的堆栈帧。那么一般是怎么做的呢?他们建立匿名内部 类 吗?拉姆达提升?还有别的吗?
抱歉,如果这是一个以前被问过的问题;好像一定是,但是我还没找到什么很对的。
我将从 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))))
内部classes(在问题和评论中提到)是为程序员提供的便利,编译器不需要它们1。每个 Clojure 函数定义(不是函数调用!)对应于一个顶层 class 实现 clojure.lang.IFn(通常通过一些抽象助手 class)。在class中,每个封闭的词法变量都保存为一个字段;这些在构造函数中初始化。所以这个函数定义扩展为:
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 版本中,内部 classes 在 JVM 级别不存在 - 它们是java 编译器翻译成具有秘密访问机制的单独顶级 classes 的虚构,就像 Clojure 将嵌套函数翻译成顶级 classes 一样。在 Java 的更新版本中,VM 本身确实理解嵌套 classes.
为了完整起见,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
}