jb proto imp

38 %
63 %
Information about jb proto imp

Published on June 17, 2007

Author: Lilly

Source: authorstream.com

Proto Implementation:  Proto Implementation Jonathan Bachrach MIT AI Lab Outline:  Outline Goals AST Runtime Compilation to C AST transformations C output strategy C runtime Bootstrapping Beyond Based on LiSP chaps 6, 9 and 10 Fun-o-dylan Proto Goals:  Proto Goals Minimal complexity of combined Language Runtime Compiler What Proto’s Not:  What Proto’s Not High performance Sophisticated Proto Architecture:  Proto Architecture Abstract Syntax Tree:  Abstract Syntax Tree Object-oriented syntactic tree representation Program converted into an object Syntax normalized and checked AST objects can easily be evaluated and transformed AST Classes:  AST Classes andlt;bindingandgt; andlt;functionandgt; andlt;constantandgt; andlt;referenceandgt; andlt;assignmentandgt; andlt;alternativeandgt; andlt;sequentialandgt; andlt;applicationandgt; andlt;fix-letandgt; andlt;argument-listandgt; andlt;localsandgt; andlt;bind-exitandgt; andlt;unwind-protectandgt; andlt;monitorandgt; Categorization Local and global Types of functions Example AST:  Example AST (fun (x y) (if (andgt; x y) x y)) Sexpr to AST Conversion:  Sexpr to AST Conversion Analogous to interpretation but produces AST instead of performing evaluation objectify takes sexpr and static environment as arguments and returns AST Magic bindings are defined for each special form and trigger custom converters AST Interpretation:  AST Interpretation eval takes an AST object and an environment and interprets the object AST conversion has already performed some of the interpretation needed in a naïve interpreter Use fast interpreter environments Proto Runtime:  Proto Runtime Objects Functions Tagging Proto Objects:  Proto Objects Prototyped based object system Lazy Traits Created when object is cloned or When slot is added to object Proto Functions:  Proto Functions Dispatch cache Tree of association list Traits as keys Subtrees or methods as values Supports singletons with secondary dispatch Folds slot access into cache by storing slot offset as values Tagging:  Tagging Tagging/Boxing scheme hidden with macros Uses low order two tag bits Encodes four cases: 00 -- pointer 01 -- andlt;intandgt; 10 -- andlt;chrandgt; 11 -- andlt;locandgt; Compilation to C:  Compilation to C AST transformations Name mangling Representations Expressions Tail calls Code Walking:  Code Walking Destructive graph walker (dm update-walk! ((g andlt;funandgt;) o (args ...)) (for ((slot (object-slots o)) (let ((x (slot-value o slot))) (when (isa? x andlt;programandgt;) (set (slot-value o slot) (apply g o args))) o) Boxing:  Boxing Remove assignments in favor of side-effects Box is Created with make-box and Accessed with box-value(-setter) Make analysis simpler (SSA) Allows for a flattened closure environment representation Boxing Walk:  Boxing Walk (dm insert-box! ((o andlt;programandgt;)) (update-walk! insert-box! o)) (dm insert-box! ((o andlt;local-referenceandgt;)) (if (binding-mutable? (reference-binding o)) (isa andlt;box-readandgt; (set box-reference o)) o)) (dm insert-box! ((o andlt;local-assignmentandgt;)) (isa andlt;box-writeandgt; (set assignment-reference (assignment-reference o)) (set assignment-form (insert-box! (assignment-form o))))) ;; ... Closure Flattening:  Closure Flattening C does not support nested functions Lambda-lifting migrates lambda’s toward the exterior in such a way there are no more interior lambda’s Basic idea is Transform lambdas into flat-funs which have flat environments Flat environments record all free variables and assign canonical ordering Use lift! Flat Function Example:  Flat Function Example (df f (x) (fun (y) x)) (df fun-1 (m y) (env-elt m 0)) (df f (m x) (fab-fun fun-1 x)) Environments are flattened All closed over variables regardless of nesting are collected Their position in this list defines an offset Environment accessed through closure which is passed through in calling convention argument m Collecting Top Level Inits:  Collecting Top Level Inits Pull out nested functions and quotations so that they are top level initialized Create and assign these objects to gensym created anonymously named bindings Depart from LiSP by having the scope of top-level initialization be at the top-level-form instead of at the whole file granularity extract-things! Collecting Top Level Initializations Example:  Collecting Top Level Initializations Example (df boo (x) (lst (+ x 1) ‘(1))) (df hoo () 1) ==andgt; (dv lit-1 (%ib %1)) (dv lit-2 (%pair (%ib %1) %nil)) (df boo (x) (lst (+ x lit-1) lit-2)) (dv lit-3 (%ib %1)) (df hoo () lit-3) Collecting Temporary Variables:  Collecting Temporary Variables C does not support nested functions and more importantly doesn’t support nested variables with same names (fun (x) (let ((x (if (== x nul) 0 x))) (+ x 1))) Must remove name conflicts gather-temporaries! (fun (x) (let ((x-1 (if (== x nul) 0 x))) (+ x-1 1))) Ready to Output C:  Ready to Output C AST graph sufficiently transformed Basically a pretty printing exercise Need to tie down C runtime hooks Name Mangling:  Name Mangling Goal reversible for demangling Use uppercase characters to encode C - =andgt; _ ! =andgt; X $ =andgt; D ... Module prefix Renamed local variables C Runtime:  C Runtime Basic Types Primitives Calling Convention Non Local Exits Boxes GC Symbol Table Printing Performance Considerations Basic Types:  Basic Types typedef void* P; #define PNUL ((P)0) typedef float PFLO; typedef long PINT; typedef unsigned long PADR; typedef char PCHR; typedef unsigned long PLOG; typedef FILE* PPORT; typedef union { PINT i; PFLO f; } INTFLO; Primitives:  Primitives Arithmetic Macros andlt;floandgt; Objects Allocation Cloning Slot access Basic types andlt;vecandgt; andlt;lstandgt; andlt;strandgt; Functions Closures FUNINIT FUNSHELL FUNFAB I/O Calling Convention:  Calling Convention Unknown calls andlt;genandgt; and andlt;metandgt; and otherwise cases Congruency checking CHECK_TYPE CHECK_ARITY Temporary argument stack Cons up optional arguments %apply Also %mep-apply CALLN:  CALLN P CALLN (P fun, int n, ...) { int i, j; P traits = YPobject_traits(fun); if (traits == YLmetG_traits) { int arity = FUNARITY(fun); P specs = FUNSPECS(fun); int naryp = FUNNARYP(fun); va_list ap; va_start(ap, n); for (i = 0; i andlt; arity; i++) { P arg = va_arg(ap, P); PUSH(arg); CHECK_TYPE(arg, Phead(specs)); specs = Ptail(specs); } if (naryp) { int nopts = n - arity; P opts = Ynil; for (i = 0; i andlt; nopts; i++) a[i] = va_arg(ap, P); for (i = nopts - 1; i andgt;= 0; i--) opts = YPpair(a[i], opts); PUSH(opts); } CHECK_ARITY(naryp,n,arity); va_end(ap); return (FUNCODE(fun))(fun); } else if (traits == YLgenG_traits) { /* ... */ } else { return CALL1(Yunknown_function_error, fun); } } Non Local Exits:  Non Local Exits Uses C’s longjmp C Structures bind_exit_frame unwind_protect_frame C Support routines nlx_step do_exit Conversion using thunks with_exit with_cleanup Example Non Local Exit:  Example Non Local Exit (lab (ret) (ret 1)) =andgt; (%with-exit (fun () (ret 1))) ;; using P with_exit (P fun) { BIND_EXIT_FRAME frame = MAKE_BIND_EXIT_FRAME(); P exit = YPmet(andamp;do_exit, YPpair(YLanyG, Ynil), YPfalse, YPib((P)1), FABENV(1, frame)); if (!setjmp(frame-andgt;destination)) return CALL1(fun, exit); else return frame-andgt;value; } Boxes:  Boxes C support BOXVAL BOXFAB Can remove boxes if in same environment GC:  GC Boehm collector Written in C Public domain Conservative Only need GC_alloc Symbol Table:  Symbol Table Register during C definition Build up for Mapping over native bindings Used for integrating with interpreter environment Debugging using original names Reverse mapping from address to name Printing:  Printing Builtin printing knows object format des print Callable from GDB Indispensable for low level debugging Performance:  Performance Inlining INLINE macro Primitives Specialize a few CALLn versions Stack allocation Optional arguments Basic C File Breakdown:  Basic C File Breakdown (dm generate-c-program (out e prg ct-env) (generate-header out e) (generate-global-environment out ct-env) (generate-quotation-forwards out (program-quotations prg)) (generate-function-forwards out (program-definitions prg)) (generate-function-bodies out (program-definitions prg)) (generate-main out (program-form prg)) (generate-trailer out) prg) Actual C File:  Actual C File /* PROTO 2 C $REVISION: 0.1 $ */ #include 'proto.h' /* GLOBAL ENVIRONMENT: */ DEF(YOfun_specs,'@fun-specs'); /* ... */ /* FORWARD QUOTATIONS: */ DEFLIT(lit_739); /* ... */ /* FUNCTIONS: */ extern P YPPtraits (P); /* ... */ LOCFOR(fun_loop_91); /* ... */ FUNFOR(Ytraits_ordered_parents); /* ... */ /* FUNCTION CODES: */ P YPPtraits(P owner_) { /* ... */ } /* ... */ P Y___main___() { /* ... */ } /* ... */ int main(int argc, char* argv[]) { YPinit_world(argc, argv); (((P)Y___main___())); return(0); } Expressions:  Expressions Utilize C’s expression oriented constructs T ? C : A (E1, E2, …, En) Avoids creating intermediate temporaries and/or register allocation Unfortunately makes debugging difficult Example of Expressions:  Example of Expressions (seq (doit) (if (done?) #t #f)) ==andgt; (CALL0(Ydoit), CALL0(YdoneQ) !== Yfalse ? Ytrue : Yfalse)) Primitives:  Primitives Used for bootstrapping and efficiency Called with normal C calling convention No Proto argument stack Arguments are always coerced to P Code only Examples: C runtime primitives like %i+ Booting primitives like @len Example Primitive:  Example Primitive (dp len (x) (if (%empty? x) (%raw 0) (%i+ (%%len (%tail x)) (%raw 1)))) ==andgt; P YPPlen(P x_) { return (((P)YPemptyQ((P)x_) != YPfalse) ? (P)0 : (P)YPiA((P)YPPlen((P)YPtail((P)x_)), (P)1)); } Functions:  Functions Arguments passed on special stack Suboptimal but very easy for C runtime Called through using congruence checker trampoline Function pointer passed in only required argument Used for accessing closed over variables Temporaries declared as C local variables Example Function:  Example Function (df not ((x andlt;anyandgt;) =andgt; andlt;logandgt;) (%bb (%eq? x #f))) ==andgt; FUNCODEDEF(Ynot) { ARG(x_); return (P)YPbb((P)(P)YPeqQ((P)x_,(P)YPfalse)); } Tail Calls and Loops:  Tail Calls and Loops Naïve C emission misses causes inefficient stack growth Simple approach can regain some Detect self-recursive calls Declare Label at beginning of body Argument shadow variables Turn self-recursive calls into Argument xfers + Goto Example Loop:  Example Loop (df @fill ((x andlt;lstandgt;) (f andlt;funandgt;) =andgt; andlt;lstandgt;) (rep loop ((x x)) (if (@empty? p) x (seq (set (@head p) f) (loop (@tail p)))))) ==andgt; FUNCODEDEF(fun_loop_232) { ARG(x_); P res, a1; loop: res = (((P)YOemptyQ((P)CHKREF(Yp)) != YPfalse) ? x_ : ((P)YOhead_setter((P)FREEREF(0),(P)CHKREF(Yp)), (a1=(P)YOtail((P)CHKREF(Yp)),x_=a1,PNUL))); if (res == PNUL) goto loop; else return res; } Advanced Topics:  Advanced Topics Alternative Bootstrapping Compiler based Minimal boot that reads virgin code through Compilation to C Separate compilation Static creation of data C runtime Tail calls Global register assignment with gcc Proto Status:  Proto Status In CVS and almost ready to release ast-linearize and p2c untested native Future:  Future Improved C runtime Faster calling convention Native / dynamic backend Temporary allocation Calling convention GC interactions Cache flushing Reading List:  Reading List Queinnec: LiSP

Add a comment

Related presentations

Related pages


Hier sollte eine Beschreibung angezeigt werden, diese Seite lässt dies jedoch nicht zu.
Read more

Stanley Proto J7324H 6 Point 1/2" Drive Deep Impact Socket ...

Stanley Proto J7324H 6 Point 1/2" Drive Deep Impact Socket, 3/4" - - Amazon.com ... Sold by: JB Tool Sales Add to Cart. $7.93 ...
Read more

Proto J72156 Set Skt Imp 3 8 1 2dr 10p Sockets - sears.com

Sears home. Store Locator; Local Ad; Coupons; Gift Ideas. Gifts; Gift Cards; Gift Registry; Credit Card
Read more

Proto Jfeos11 Socket Set Oxygen Sensor 11 Piece 6rku7

"proto jfeos11 socket set oxygen sensor 11 piece 6rku7" ... Sold by JB Tool Sales. ... Stanley-Proto Ind Tools 3/8 DR. SKT IMP SET 11PC.
Read more

Gerson Porto | LinkedIn

Gerson Porto. Representante Comercial na Porto a Porto com Imp e Exp Ltda. Location Curitiba, Paraná, Brazil Industry Restaurants
Read more

[android-x86] jb-x86: Enabling touchpad as a mouse in ...

[android-x86] jb-x86: Enabling touchpad as a mouse in generic/x86; Ron M. Feb 10, ... By adding psmouse.proto=imps to the kernel command line, ...
Read more

Deutsche Biographie - Pontanus, Jacobus

... historiae Mauricii Tiberii Imp. Lib. VIII., Item Georgii Phranzae Proto-Vestiarii Chronicorum ... Lit. wiss. Jb. d. Görres-Ges. 3, 1928, S. 45-85 ...
Read more

Error-Prone DNA Repair System in Enteroaggregative ...

0021-9193/07/$08.00 0 doi:10.1128/JB ... common among EAEC even though they are absent in proto- ... the 2.4-kb imp operon from Shigella ...
Read more

Mo delling - sandilands.info

Mo delling the W AP T ransaction Service using ... sgordon,jb g @spri.levels.un isa ... unication proto col, it is imp ortan t to ensure the cor-
Read more

Jb Pioneiro | LinkedIn

View Jb Pioneiro’s professional profile on LinkedIn. LinkedIn is the world's largest business network, helping professionals like Jb Pioneiro discover ...
Read more