anastasatos

Slide1: 

Automatically Restructuring Programs for the Web Matthews, Graunke, Krishnamurthi, Findler, Felleisen

Slide2: 

 50% of Web pages are generated on demand. The so-called Web 'scripts' are nowadays complex, evolving programs. However, existing technology is inadequate. Web Scripts

Slide3: 

fun input msg = print msg; read fun adder = print (input '1st number?') + (input '2nd number?') Pro: interaction is computation driven;  natural programming style. Interactive Programming Paradigm

Slide4: 

Web scripts must terminate after producing one single page (exception: Fast CGI);  control information is erased between user interactions (Fast CGI solves this problem). Back button + window cloning;  the client becomes a co-routine with unbounded resumption points (Fast CGI can’t solve it). Serious Engineering Problem

Slide5: 

Solution: come up with a hack to explicitly store/recover state per hand. Current Approaches fun produce-html msg hidden-mark env = ... fun adder = hidden-mark = extract-hidden-mark env = extract-env ans = extract-answer if hidden-mark = undefined then produce-html '1st number?' 'step 1' [] else if hidden-mark = 'step 1' then produce-html '2nd number?' 'step 2' [ans] else if hidden-mark = 'step 2' then produce-html ((hd env) + ans) 'done' []

Slide6: 

Program Inversion: the interaction becomes user driven! Current Approaches But inversion is: unnatural; complicated; error prone, if done per hand; counter-productive.

Slide7: 

Use a PL that can explicitly manipulate continuations to grab and store them on the server [Queinnec 2000]. Problems: most PLs don’t support call/cc  existing infrastructure becomes useless; distributed garbage collection problem; timeouts are an imperfect solution. A Better Solution?

Slide8: 

use existing, well understood FP techniques to automatically transform them into programs for the Web. Write usual interactive programs in your favourite PL and environment; Use a PL that has call/cc. A Better Solution?

Slide9: 

continuation passing style (CPS), lambda lifting, defunctionalization. How can we grab, send, and resume continuations in an arbitrary PL? By transforming the program with: The Preprocessing Solution One last step generates a program for the web.

Slide10: 

fun adder = input '1st number?' λ n0 =andgt; input '2nd number?' λ n1 =andgt; print n0 + n1 fun input msg = print msg; read fun adder = print (input '1st number?') + (input '2nd number?') fun input msg f = print msg; f read Continuation Passing Style

Lambda lifting: 

Lambda lifting fun input msg f env = print msg; f env read fun adder = input '1st number?' f0 [] fun f0 [] n0 = input '2nd number?' f1 [n0] fun f1 [n0] n1 = print n0 + n1 fun input msg f = print msg; f read fun adder = input '1st number?' λ n0 =andgt; input '2nd number?' λ n1 =andgt; print n0 + n1

Defunctionalization: 

fun adder = input '1st number?' 0 [] fun f0 [] n0 = input '2nd number?' 1 [n0] fun f0 [n0] n1 = print n0 + n1 fun apply idx env = funs.idx env vector funs = {f0, f1} Defunctionalization fun input msg idx env = print msg; apply idx env read fun input msg f env = print msg; f env read fun adder = input '1st number?' f0 [] fun f0 [] n0 = input '2nd number?' f1 [n0] fun f0 [n0] n1 = print n0 + n1

Slide13: 

CPS: the only function that interacts with the user (input) is passed a continuation. λ lifting: the structure of the program is flattened; all functions are named and global. Defunctionalization: no function is passed or returned. Till now, the function input simply executes the continuation passed to it... What have we done till now? The Preprocessing Solution

Interactive Program  CGI Program: 

Interactive Program  CGI Program fun input msg idx env = produce-html msg idx env fun input msg idx env = print msg; apply idx env read vector funs... fun apply... fun adder = input '1st number?' 0 [] fun f0... fun f1... fun adder = idx = extract-idx; env = extract-env; ans = extract-answer; apply idx env ans; handle NoCont =andgt; input '1st number?' 0 [] vector funs... fun apply... fun f0... fun f1...

You can do it also in C...: 

You can do it also in C... #include andlt;stdio.handgt; typedef struct { int code; void *env; } closure; typedef void (*closuretype)(void*, void*); void input(char *s, closure *k); closure *make_closure( int code, void *env){ closure *k = (closure*) malloc(sizeof(closure)); k-andgt;code = code, k-andgt;env = env; return k; } void f0(void *env, void *n0) { closure *k = make_closure(1, n0); input('2nd number?', k); } void f1(void *n0, void *n1) { printf('%d\n', (int) n0 + (int) n1); } closuretype closures[] = {f0, f1}; void apply(closure *k, void *args){ int code = k-andgt;code; void *env = k-andgt;env; free(k); (*(closures[code]))(env, args); } void input(char *s, closure *k){ char buffer[10]; int i; printf('%s', s); fgets(buffer,10, stdin); i = atoi(buffer); apply(k, (void *) i); } int main() { closure *k = make_closure(0, (void *) 0); input('1st number?', k); return 0; }

…or even in BASIC...: 

…or even in BASIC... The dispatcher: REM adder ... IF idx = 0 THEN GOTO 100 ELSE IF idx = 1 THEN GOTO 200 ... 100 REM f0 ... 200 REM f1 ...

Save Store in Cookies: 

Solution: save the store in a cookie. val high_score = ref 0; ... high_score := !high_score + 1; Save Store in Cookies Problem: the store is independent from the continuations.

Problem: Race Conditions: 

Problem: Race Conditions Buy a flatscreen... Web Server Balance=900€ Balance=160€ Buy a scanner... Web Client 154.34.0.1

Solution: Sequence Numbers: 

Solution: Sequence Numbers Buy a flatscreen... Web Server 154.34.0.1:7665671 SEQ=7665671 Balance=900€ Balance=160€ Buy a scanner... (Reintroduces the server side storage management problem.) Web Client 154.34.0.1

Security/Efficiency: 

Security/Efficiency Problem: a malicious user may forge the continuation; a curious user may inspect sensitive data. Solution: encrypt/sign continuation. Problem: continuations may be large pieces of data. Solution: compress them.

Problem: Debugging: 

Problem: Debugging Executed code bears little resemblance to programmer’s code. How do you debug it? Answer: still an open question... Ad hoc solution for PL’s with call/cc: don’t preprocess; reimplement the input function to store continuations and send HTML to Web browser; reimplement the main function to resume current continuation.

Slide22: 

Paul Graunke, Shriram Krishnamurthi, Robert Bruce Findler, Matthias Felleisen (2001): Automatically Restructuring Programs for the Web. Jacob Matthews, Paul Graunke, Shriram Krishnamurthi, Robert Bruce Findler, Matthias Felleisen (2004): Automatically Restructuring Programs for the Web. Christian Queinnec (2000): The influence of browsers on evaluators or, continuations to program Web servers. In: ACM SIGPLAN International Conference on Functional Programming. Andrew W. Appel (1992): Compiling with Continuations. Cambridge University Press. Thomas Johnson (1985): Lambda Lifting: Transforming Programs to Recursive Equations. In: Proceedings of the Conference on Functional Programming Languages and Computer Architecture. Nancy, France. John C. Reynolds (1972): Definitional Interpreters for Higher-Order Programming Languages. In: Proceedings of the 25th ACM National Conference. pp. 717–740. Literature

Conclusion: 

Conclusion Automatic restructuring of programs for the Web enables programmers to: use existing paradigms and tools; structure programs in a natural way; be more productive.

Slide24: 

 DISJUNCTION  CONJUNCTION  NEGATION  IMPLIES  IFF  EMPTY SET  OMEGA  IN  NOT IN  UNION  INTERSECTION  SUBSET  SUPERSET 2 POWERSET  CARTESIAN PRODUCT  EXISTS  FORALL , = (NOT) EQUAL TO ,  LESS (GREATER) THAN ,  LESS (GREATER) THAN OR EQUAL TO  CIRCA ≡ EQUIVALENT ∑ SUM ∏ PRODUCT  TO  DIVISION √ ROOT ∫ INTEGRAL ∞ INFINITY ∆, , ,  DELTA, DELTA, SMALL DELTA, SIGMA , ,  SMALL PSI, ALPHA, BETA