untitled

Size: px

Start display at page:

Download "untitled"

ゆきうなだ
5 years ago
Views:

1 PPL 2006

12 MinCaml (myth)

14 vs. vs. vs.

15 Haskell ( ML ( caml.inria.fr) Standard ML (SML), Objective Caml (OCaml) Scheme (

16 low level GCC C GCJ Java javac Java JVM ocamlc OCaml OCaml VM ocamlopt OCaml MLj SML JVM etc.

17 (MinCaml) let rec gcd m n = if m = 0 then n else if m <= n then gcd m (n - m) else gcd n (m - n)

18 (MinCaml SPARC) let rec gcd m n = if m = 0 then n else if m <= n then gcd m (n - m) else gcd n (m - n) gcd.7: cmp %i2, 0 bne be_else.17 nop mov %i3, %i2 retl nop be_else.17: cmp %i2, %i3 bg ble_else.18 nop sub %i3, %i2, %i3 b gcd.7 nop ble_else.18: sub %i2, %i3, %i2 mov %i3, %o4 mov %i2, %i3 mov %o4, %i2 b gcd.7 nop

19 (* MinCaml main.ml *) Emit.f outchan (RegAlloc.f (Simm13.f (Virtual.f (Closure.f (iter!limit (Alpha.f (KNormal.f (Typing.f (Parser.exp Lexer.token l))))))))) > wc --lines *.ml* 46 alpha.ml 2 alpha.mli 18 assoc.ml 1 assoc.mli 38 beta.ml 1 beta.mli 106 closure.ml 33 closure.mli 50 constfold.ml 2020 total

20 MinCaml OCaml minimal ML

21 MinCaml (1/2) M, N ::= c op(m 1,...,M n ) if M then N 1 else N 2 let x = M in N x let rec xy 1... y n = M in N MN 1... N n...

22 MinCaml (2/2) M, N ::=... (M 1,...,M n ) let (x 1,...,x n ) = M in N Array.create MN M.(N) M 1.(M 2 ) M 3

24 OCamlLex/OCamlYacc Cf. packrat parsing ( tricky x-y x(-y)parse simple_exp exp

25 OCaml peculiar int

27 : MinCaml SPARC

28 K ML Kit ( MinCaml SPARC : (x-y)-(y-z) let tmp1 = x - y in let tmp2 = y - z in tmp1 - tmp2 4, 5

29 12345-x let tmp1 = in let tmp2 = x in tmp1 - tmp2 let tmp1 = in tmp1 - x let insert_let e k = match e with Var(x) -> k x _ -> let x = gensym () in Let(x, e, k x)

31 α "fresh" : let x = in let x = x in -x let x 1 = in let x 2 = x in -x 2 6

32 let rec f x y z = M in... (f a b c)... let rec f x y z = M in... ([a,b,c/x,y,z]m')... Mf... heuristics

33 let x = 7 in let y = 3 in x y let x = 7 in let y = 3 in 4

34 let let rec let x = M in N N x N M

36 Closure KSPARC

37 1: (OCaml) let quad x = let dbl y = y + y in dbl (dbl x) in quad 3 let dbl y = y + y ;; let quad x = dbl (dbl x) ;; quad 3

38 2: let make_adder x = let adder y = x + y in adder in (make_adder 3) 7??? let adder y = x + y ;; let make_adder x = adder ;; (make_adder 3) 7 x???

39 ? : adder x () a. C, C++ b.! GCC c. Scheme, ML, Java (inner class)

40 Closure (closure) : closure let make_adder x = (adder, x) ;; : let (body, fv) = make_adder 3 in body 7 fv : let adder y x = x + y ;;

41 2 let make_adder x = let adder y = x + y in adder in (make_adder 3) 7 let adder y x = x + y ;; let make_adder x = (adder, x) ;; apply_closure(make_adder 3, 7) apply_closure((body, fv), arg) body arg fv

42 Closure 13,14 let rec 1. =closure Closure 4. Closure ( )

43 Closure make_closure apply_closure : let f x = x + 3 in f 7 let L f x () = x + 3 ;; make_closure f = (L f, ()) in apply_closure f 7

44 1. closure 2. 1.closure closure let x = 1 in let f y = x + y in (* *) let g z = z + 2 in (* *) (if... then f else g) 3 (* *) fg closure

46 17,18

47 greedy mov MinCaml

48 pretty print (register shuffling) call

50 : Sun Fire V880 Ultra SPARC III 1.2GHz 8 GB Solaris 9 : MinCaml (32 bit, -iter inline 100) OCamlOpt (32 bit, -unsafe -inline 100) GCC (32 bit & 64 bit, -O3) GCC (32 bit "flat", -O3)

51 min-caml ocamlopt gcc -m32 gcc -m64 gcc -m32 -mflat 1 0 ack fib tak

52 min-caml ocamlopt gcc -m32 gcc -m64 gcc -m32 -mflat raytrace harmonic mandelbrot huffman

e ::= c op(e 1,..., e n ) if e 1 then e 2 else e 3 let x = e 1 in e 2 x let rec x y 1... y n = e 1 in e 2 e e 1... e n (e 1,..., e n ) let (x 1,..., x

e ::= c op(e 1,..., e n ) if e 1 then e 2 else e 3 let x = e 1 in e 2 x let rec x y 1... y n = e 1 in e 2 e e 1... e n (e 1,..., e n ) let (x 1,..., x n ) = e 1 in e 2 Array.create e 1 e 2 e 1.(e 2 ) e