Fermé pour inventaire
Histoire et mécanique des « closures »
Frédéric Cabestre
Soy cantor, soy embustero
Me gusta el juego y el vino, tengo alma de marinero
¿Qué le voy a hacer si yo nací en el Mediterráneo?— Juan Manuel Serrat
$\lambda$
val aList = 1..100 val filteredList = aList.filter({ x -> x % 2 == 0 }) println(filteredList) /* [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100] */Kotlin
(defun filter (fn list) (cond ((null list) nil) (t (cond ((funcall (eval fn) (car list)) (cons (car list) (filter fn (cdr list)))) (t (filter fn (cdr list))))))) (filter '(lambda (x) (= (mod x 2) 0)) '(1 2 3 4 5 6))Lisp
val aList = 1..100 val filteredList = aList.filter({ x -> x % 2 == 0 }) println(filteredList) /* [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100] */Kotlin
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> { return filterTo(ArrayList<T>(), predicate) }Kotlin
val aList = 1..100 val filteredList = aList.filter({ x -> x % 2 == 0 }) println(filteredList) /* [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100] */Kotlin
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> { return filterTo(ArrayList<T>(), predicate) }Kotlin
(Int) -> Boolean (Int, String) -> String ((Float) -> Float) -> Float (Float) -> (Float) -> FloatKotlin
aList.filter({ x -> x % 2 == 0 })Kotlin
aList.filter({ x -> x % 2 == 0 })Kotlin
aList.filter({ it % 2 == 0 })Kotlin
aList.filter({ x -> x % 2 == 0 })Kotlin
aList.filter({ it % 2 == 0 })Kotlin
aList.filter { it % 2 == 0 }Kotlin
fun longComputation(x: Int): Int { return x * x // 🤡 } fun parametricPredicate(x: Int, y: Int): Boolean { val c = longComputation(x) return y % c == 0 }Kotlin
fun main() { val aList = 1..100 val filteredList = aList.filter { y -> parametricPredicate(3, y) } println(filteredList) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
fun longComputation(x: Int): Int { return x * x // 🤡 } fun parametricPredicate(x: Int, y: Int): Boolean { val c = longComputation(x) return y % c == 0 }Kotlin
fun main() { val aList = 1..100 val filteredList = aList.filter { y -> parametricPredicate(3, y) } println(filteredList) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
Curryfication
$f: (A, B) \rightarrow C$
$f: A \rightarrow (B \rightarrow C)$
fun parametricPredicate(x: Int, y: Int): Boolean { val c = longComputation(x) return y % c == 0 }Kotlin
fun main() { val aList = 1..100 val predicate = { y -> parametricPredicate(3, y) } println(aList.filter(predicate)) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun main() { val aList = 1..100 val predicate = parametricPredicate(3) println(aList.filter(predicate)) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun main() { val aList = 1..100 val predicate = parametricPredicate(3) println(aList.filter(predicate)) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun main() { val aList = 1..100 val predicate = parametricPredicate(3) println(aList.filter(predicate)) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun main() { val aList = 1..100 val predicate = parametricPredicate(3) println(aList.filter(predicate)) /* [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99] */ }Kotlin
Lisp 1.5
1958
John MacCarthy
Funarg Problem
fun longComputation(x: Int): Int { return x * x } fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } } fun main() { val c = 42 val predicate: (Int) -> Boolean = parametricPredicate(3) if (predicate(81)) println("Ok") else println("Ko") }Kotlin
Les fonctions (récursives) décortiquées
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
Scheme
1975
Guy L. Steele Jr.
$x$
Variable
$\lambda x.\,M$
Abstraction
$M\,N$
Application
$\lambda x.\,(f\,x) \rightarrow f$
$\eta$-reduction
$\lambda x.\,M[x] \rightarrow \lambda y.\,M[y]$
$\alpha$-conversion
$(\lambda x.\,M)\:E \rightarrow M[x:=E]$
$\beta$-reduction
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
fun main() {
val c = 42
val predicate: (Int) -> Boolean = parametricPredicate(3)
if (predicate(81)) println("Ok") else println("Ko")
}
fun parametricPredicate(x: Int): (Int) -> Boolean {
val c = longComputation(x)
return { y -> y % c == 0 }
}
fun longComputation(x: Int): Int {
return x * x
}
Clojure
2007
Rich Hickey
$\lambda$-lifting
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun parametricPredicateLambda(c: Int, y: Int): Boolean = y % c == 0 fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> parametricPredicateLambda(c, y) } }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun parametricPredicateLambda(c: Int, y: Int): Boolean = y % c == 0 fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> parametricPredicateLambda(c, y) } }Kotlin
fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> y % c == 0 } }Kotlin
fun parametricPredicateLambda(c: Int, y: Int): Boolean = y % c == 0 fun parametricPredicate(x: Int): (Int) -> Boolean { val c = longComputation(x) return { y -> parametricPredicateLambda(c, y) } }Kotlin
Closure conversion
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
fun parametricPredicate(x: Int): Closure<Int, Int, Boolean> { val c = longComputation(x) return Closure(c, ::parametricPredicateLambda) } fun main() { val c = 42 val predicate: Closure<Int, Int, Boolean> = parametricPredicate(3) if (predicate.code(predicate.capture, 81)) println("Ok") else println("Ko") }Kotlin
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
fun parametricPredicate(x: Int): Closure<Int, Int, Boolean> { val c = longComputation(x) return Closure(c, ::parametricPredicateLambda) } fun main() { val c = 42 val predicate: Closure<Int, Int, Boolean> = parametricPredicate(3) if (predicate.code(predicate.capture, 81)) println("Ok") else println("Ko") }Kotlin
data class Closure<C, I, O>(val capture: C, val code: (C, I) -> O)Kotlin
fun parametricPredicate(x: Int): Closure<Int, Int, Boolean> { val c = longComputation(x) return Closure(c, ::parametricPredicateLambda) } fun main() { val c = 42 val predicate: Closure<Int, Int, Boolean> = parametricPredicate(3) if (predicate.code(predicate.capture, 81)) println("Ok") else println("Ko") }Kotlin
Java 8
2014
public static int longComputation(int x) { return x * x; } public static IntPredicate parametricPredicate(int x) { var c = longComputation(x); return y -> y % c == 0; } void main() { var aStream = IntStream.rangeClosed(0, 100); var predicate = parametricPredicate(3); IntStream filteredStream = aStream.filter(predicate); System.out.println( filteredStream. mapToObj(Integer::toString). collect(Collectors.joining(",", "[", "]"))); } // [0,9,18,27,36,45,54,63,72,81,90,99]Java
public static int longComputation(int x) { return x * x; } public static IntPredicate parametricPredicate(int x) { var c = longComputation(x); return y -> y % c == 0; } void main() { var aStream = IntStream.rangeClosed(0, 100); var predicate = parametricPredicate(3); IntStream filteredStream = aStream.filter(predicate); System.out.println( filteredStream. mapToObj(Integer::toString). collect(Collectors.joining(",", "[", "]"))); } // [0,9,18,27,36,45,54,63,72,81,90,99]Java
public static int longComputation(int x) { return x * x; } public static IntPredicate parametricPredicate(int x) { var c = longComputation(x); return y -> y % c == 0; } void main() { var aStream = IntStream.rangeClosed(0, 100); var predicate = parametricPredicate(3); IntStream filteredStream = aStream.filter(predicate); System.out.println( filteredStream. mapToObj(Integer::toString). collect(Collectors.joining(",", "[", "]"))); } // [0,9,18,27,36,45,54,63,72,81,90,99]Java
@FunctionalInterface public interface IntPredicate { boolean test(int value); }Java
@FunctionalInterface public interface IntPredicate { boolean test(int value); }Java
@FunctionalInterface public interface IntPredicate { boolean test(int value); }Java
public static boolean parametricPredicateLambda(int c, int y) { return y % c == 0; } public static class Closure implements IntPredicate { private final int c; public Closure(int c) { this.c = c; } @Override public boolean test(int value) { return parametricPredicateLambda(c, value); } }Java
public static boolean parametricPredicateLambda(int c, int y) { return y % c == 0; } public static class Closure implements IntPredicate { private final int c; public Closure(int c) { this.c = c; } @Override public boolean test(int value) { return parametricPredicateLambda(c, value); } }Java
public static boolean parametricPredicateLambda(int c, int y) { return y % c == 0; } public static class Closure implements IntPredicate { private final int c; public Closure(int c) { this.c = c; } @Override public boolean test(int value) { return parametricPredicateLambda(c, value); } }Java
public static boolean parametricPredicateLambda(int c, int y) { return y % c == 0; } public static class Closure implements IntPredicate { private final int c; public Closure(int c) { this.c = c; } @Override public boolean test(int value) { return parametricPredicateLambda(c, value); } }Java
public static boolean parametricPredicateLambda(int c, int y) { return y % c == 0; } public static class Closure implements IntPredicate { private final int c; public Closure(int c) { this.c = c; } @Override public boolean test(int value) { return parametricPredicateLambda(c, value); } }Java
public static int longComputation(int x) { return x * x; } public static IntPredicate parametricPredicate(int x) { var c = longComputation(x); return new Closure(c); }Java
var predicate = parametricPredicate(3); predicate(81);Java
public static int longComputation(int x) { return x * x; } public static IntPredicate parametricPredicate(int x) { var c = longComputation(x); return new Closure(c); }Java
var predicate = parametricPredicate(3);predicate(81);predicate.test(81);Java
private static boolean lambda$parametricPredicate$0(int, int); descriptor: (II)Z flags: (0x100a) ACC_PRIVATE, ACC_STATIC, ACC_SYNTHETIC Code: stack=2, locals=2, args_size=2 0: iload_1 1: iload_0 2: irem 3: ifne 10 6: iconst_1 7: goto 11 10: iconst_0 11: ireturn LineNumberTable: line 15: 0 StackMapTable: number_of_entries = 2 frame_type = 10 /* same */ frame_type = 64 /* same_locals_1_stack_item */ stack = [ int ]Bytecode
private static boolean lambda$parametricPredicate$0(int, int); descriptor: (II)Z flags: (0x100a) ACC_PRIVATE, ACC_STATIC, ACC_SYNTHETIC Code: stack=2, locals=2, args_size=2 0: iload_1 1: iload_0 2: irem 3: ifne 10 6: iconst_1 7: goto 11 10: iconst_0 11: ireturn LineNumberTable: line 15: 0 StackMapTable: number_of_entries = 2 frame_type = 10 /* same */ frame_type = 64 /* same_locals_1_stack_item */ stack = [ int ]Bytecode
public static java.util.function.IntPredicate parametricPredicate(int); descriptor: (I)Ljava/util/function/IntPredicate; flags: (0x0009) ACC_PUBLIC, ACC_STATIC Code: stack=1, locals=2, args_size=1 0: iload_0 1: invokestatic #7 // Method longComputation:(I)I 4: istore_1 5: iload_1 6: invokedynamic #13, 0 // InvokeDynamic #0:test:(I)Ljava/util/function/IntPredicate; 11: areturn LineNumberTable: line 14: 0 line 15: 5Bytecode
public static java.util.function.IntPredicate parametricPredicate(int); descriptor: (I)Ljava/util/function/IntPredicate; flags: (0x0009) ACC_PUBLIC, ACC_STATIC Code: stack=1, locals=2, args_size=1 0: iload_0 1: invokestatic #7 // Method longComputation:(I)I 4: istore_1 5: iload_1 6: invokedynamic #13, 0 // InvokeDynamic #0:test:(I)Ljava/util/function/IntPredicate; 11: areturn LineNumberTable: line 14: 0 line 15: 5Bytecode
public static java.util.function.IntPredicate parametricPredicate(int); descriptor: (I)Ljava/util/function/IntPredicate; flags: (0x0009) ACC_PUBLIC, ACC_STATIC Code: stack=1, locals=2, args_size=1 0: iload_0 1: invokestatic #7 // Method longComputation:(I)I 4: istore_1 5: iload_1 6: invokedynamic #13, 0 // InvokeDynamic #0:test:(I)Ljava/util/function/IntPredicate; 11: areturn LineNumberTable: line 14: 0 line 15: 5Bytecode
BootstrapMethods: 0: #94 REF_invokeStatic java/lang/invoke/LambdaMetafactory.metafactory:( Ljava/lang/invoke/MethodHandles$Lookup; Ljava/lang/String;Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodHandle; Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite; Method arguments: #79 (I)Z #81 REF_invokeStatic Main.lambda$parametricPredicate$0:(II)Z #79 (I)ZBytecode
BootstrapMethods: 0: #94 REF_invokeStatic java/lang/invoke/LambdaMetafactory.metafactory:( Ljava/lang/invoke/MethodHandles$Lookup; Ljava/lang/String;Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodHandle; Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite; Method arguments: #79 (I)Z #81 REF_invokeStatic Main.lambda$parametricPredicate$0:(II)Z #79 (I)ZBytecode
BootstrapMethods: 0: #94 REF_invokeStatic java/lang/invoke/LambdaMetafactory.metafactory:( Ljava/lang/invoke/MethodHandles$Lookup; Ljava/lang/String;Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodType; Ljava/lang/invoke/MethodHandle; Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite; Method arguments: #79 (I)Z #81 REF_invokeStatic Main.lambda$parametricPredicate$0:(II)Z #79 (I)ZBytecode
Pour Conclure
fn long_computation(x: i64) -> i64 { x * x } fn parametric_predicate(x: i64) -> impl FnMut(&i64) -> bool { let c = long_computation(x); move |y| { y % c == 0 } } fn main() { let a_range = 1 .. 100; let predicate = parametric_predicate(3); let filtered_range = a_range.filter(predicate); println!("{:?}", filtered_range.collect::<Vec<i64>>()) } // [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99]Rust
fn long_computation(x: i64) -> i64 { x * x } fn parametric_predicate(x: i64) -> impl FnMut(&i64) -> bool { let c = long_computation(x); move |y| { y % c == 0 } } fn main() { let a_range = 1 .. 100; let predicate = parametric_predicate(3); let filtered_range = a_range.filter(predicate); println!("{:?}", filtered_range.collect::<Vec<i64>>()) } // [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99]Rust
fn long_computation(x: i64) -> i64 { x * x } fn parametric_predicate(x: i64) -> impl FnMut(&i64) -> bool { let c = long_computation(x); move |y| { y % c == 0 } } fn main() { let a_range = 1 .. 100; let predicate = parametric_predicate(3); let filtered_range = a_range.filter(predicate); println!("{:?}", filtered_range.collect::<Vec<i64>>()) } // [9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99]Rust
Frédéric Cabestre
Merci
Feedback
Présentation
