anastasatos

Information about anastasatos

Published on June 15, 2007

Author: Me_I

Source: authorstream.com

Content

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

Related presentations


Other presentations created by Me_I

body language
15. 06. 2007
0 views

body language

Pregnant Man Delivers Baby Girl
06. 07. 2008
0 views

Pregnant Man Delivers Baby Girl

Pregnant Man delivers baby girl
04. 07. 2008
0 views

Pregnant Man delivers baby girl

Interview guide
22. 04. 2008
0 views

Interview guide

Price
17. 04. 2008
0 views

Price

valuation models
17. 04. 2008
0 views

valuation models

Stan Mcmillen
14. 04. 2008
0 views

Stan Mcmillen

ABch11
13. 04. 2008
0 views

ABch11

IPStrategy mozambique
10. 04. 2008
0 views

IPStrategy mozambique

magaddinometrans01
09. 04. 2008
0 views

magaddinometrans01

lecture7 07 time cmp
07. 04. 2008
0 views

lecture7 07 time cmp

Easter
09. 07. 2007
0 views

Easter

PHSC1013 Reactions
02. 01. 2008
0 views

PHSC1013 Reactions

Digestive System Disorders
26. 03. 2008
0 views

Digestive System Disorders

ABC on HIV AIDS
16. 06. 2007
0 views

ABC on HIV AIDS

plateau
09. 07. 2007
0 views

plateau

4 YCCC 1500 Competition K1IR
16. 06. 2007
0 views

4 YCCC 1500 Competition K1IR

2DShapes
16. 06. 2007
0 views

2DShapes

Analyzing Political Cartoons 1
15. 06. 2007
0 views

Analyzing Political Cartoons 1

kwanza
09. 07. 2007
0 views

kwanza

7 passions
16. 06. 2007
0 views

7 passions

GreekDrama
09. 07. 2007
0 views

GreekDrama

L9medicine
12. 10. 2007
0 views

L9medicine

Business opportunities 2005
18. 10. 2007
0 views

Business opportunities 2005

Rocio Guirao Diaz
03. 09. 2007
0 views

Rocio Guirao Diaz

Jorge Tellez Fuentes
22. 10. 2007
0 views

Jorge Tellez Fuentes

87 81
22. 10. 2007
0 views

87 81

Active Aging Steps
27. 11. 2007
0 views

Active Aging Steps

Yafei ECG poster final
15. 11. 2007
0 views

Yafei ECG poster final

NACAA Conference FSEP
29. 12. 2007
0 views

NACAA Conference FSEP

chem 101 chapter 6 slides
04. 01. 2008
0 views

chem 101 chapter 6 slides

comp intel
03. 10. 2007
0 views

comp intel

03n 0203 ts00002 LEACH
19. 11. 2007
0 views

03n 0203 ts00002 LEACH

mikelle
28. 12. 2007
0 views

mikelle

Dear God
03. 10. 2007
0 views

Dear God

Team Leader Training 12 11 06
09. 07. 2007
0 views

Team Leader Training 12 11 06

Schneider and Schmitt
09. 07. 2007
0 views

Schneider and Schmitt

paraguay
09. 07. 2007
0 views

paraguay

mowbjan06
09. 07. 2007
0 views

mowbjan06

mlk 2
09. 07. 2007
0 views

mlk 2

Mayan Cosmology
09. 07. 2007
0 views

Mayan Cosmology

GCSE ART D of Dead
09. 07. 2007
0 views

GCSE ART D of Dead

Enter the 2007 Art Comp1
09. 07. 2007
0 views

Enter the 2007 Art Comp1

cases
24. 02. 2008
0 views

cases

a032405
09. 10. 2007
0 views

a032405

sfa ch2
01. 01. 2008
0 views

sfa ch2

6 12USAITAsecondpanel
22. 10. 2007
0 views

6 12USAITAsecondpanel

Gatekeepers 6
11. 12. 2007
0 views

Gatekeepers 6

EU New Member States Brno NA
18. 03. 2008
0 views

EU New Member States Brno NA

Rym Kefi
05. 01. 2008
0 views

Rym Kefi

Chinese Dynasties
25. 03. 2008
0 views

Chinese Dynasties

2 4 Adams Hallam
07. 10. 2007
0 views

2 4 Adams Hallam

Wings of the Centennial
09. 07. 2007
0 views

Wings of the Centennial

Creating a User Group 2005
30. 03. 2008
0 views

Creating a User Group 2005

Observation
09. 07. 2007
0 views

Observation

usingmypyramidadult
04. 03. 2008
0 views

usingmypyramidadult

Stefan Stanciugelu
15. 10. 2007
0 views

Stefan Stanciugelu

carreira
19. 06. 2007
0 views

carreira

Capitalization Part 2
19. 06. 2007
0 views

Capitalization Part 2

Caceres 2007
19. 06. 2007
0 views

Caceres 2007

CHETEMPOFA
18. 06. 2007
0 views

CHETEMPOFA

cervantes
18. 06. 2007
0 views

cervantes

CEIS 23 06
18. 06. 2007
0 views

CEIS 23 06

cartoon classics
18. 06. 2007
0 views

cartoon classics

cardiac2
19. 06. 2007
0 views

cardiac2

hphennalect
09. 07. 2007
0 views

hphennalect

Current Presentation March06
18. 06. 2007
0 views

Current Presentation March06

cul 18
18. 06. 2007
0 views

cul 18

competitive rviews
18. 06. 2007
0 views

competitive rviews

company wbc
18. 06. 2007
0 views

company wbc

City Guide Mobile web en
18. 06. 2007
0 views

City Guide Mobile web en

MICROIII Aula11
14. 11. 2007
0 views

MICROIII Aula11

comunicado2
22. 10. 2007
0 views

comunicado2

Camilla Schreiner UiO
19. 06. 2007
0 views

Camilla Schreiner UiO

verb som laanord
27. 09. 2007
0 views

verb som laanord

LCWS05 gao 1
12. 10. 2007
0 views

LCWS05 gao 1

ambiguity
16. 06. 2007
0 views

ambiguity

all about burgers 1
16. 06. 2007
0 views

all about burgers 1

AGME 1
16. 06. 2007
0 views

AGME 1

Advanced ADO
16. 06. 2007
0 views

Advanced ADO

adolposter winkles
16. 06. 2007
0 views

adolposter winkles

AbrahamseOverviewAM
16. 06. 2007
0 views

AbrahamseOverviewAM

31 Presentation
16. 06. 2007
0 views

31 Presentation

303lec09
16. 06. 2007
0 views

303lec09

04 06 training
15. 06. 2007
0 views

04 06 training

Brian PM FINAL
15. 06. 2007
0 views

Brian PM FINAL

Berkeley ISSC Feb 07
15. 06. 2007
0 views

Berkeley ISSC Feb 07

Autism 06 BU handout
15. 06. 2007
0 views

Autism 06 BU handout

Attraction
15. 06. 2007
0 views

Attraction

Asali
15. 06. 2007
0 views

Asali

April Showers
15. 06. 2007
0 views

April Showers

APA San Diego
15. 06. 2007
0 views

APA San Diego

ap05blogs
15. 06. 2007
0 views

ap05blogs

Analyzing Political Cartoons
15. 06. 2007
0 views

Analyzing Political Cartoons

analyzing cartoons incent asia
15. 06. 2007
0 views

analyzing cartoons incent asia

africanamericanhumor
16. 06. 2007
0 views

africanamericanhumor

americanpoplanguage
15. 06. 2007
0 views

americanpoplanguage

mainmenu2007changes jml
06. 03. 2008
0 views

mainmenu2007changes jml

StephenAbram RecreatingServices3
10. 03. 2008
0 views

StephenAbram RecreatingServices3

Joanna Krupa
03. 09. 2007
0 views

Joanna Krupa

HowtheWestWasWon
19. 02. 2008
0 views

HowtheWestWasWon

accidental humor
16. 06. 2007
0 views

accidental humor

keyes
03. 01. 2008
0 views

keyes

VolkswagenCoaching
16. 11. 2007
0 views

VolkswagenCoaching

07 kauai1
26. 02. 2008
0 views

07 kauai1

Urban Waters and Ports html
30. 12. 2007
0 views

Urban Waters and Ports html

awakening
15. 06. 2007
0 views

awakening

RR11 NIA Hodes
03. 01. 2008
0 views

RR11 NIA Hodes

AAAR diesel1
29. 02. 2008
0 views

AAAR diesel1

RSS AnnualMtg3
29. 09. 2007
0 views

RSS AnnualMtg3

USTC
29. 11. 2007
0 views

USTC

ESS Adv Plan Present 4 18
09. 07. 2007
0 views

ESS Adv Plan Present 4 18

CMR0101
18. 06. 2007
0 views

CMR0101