Master thesis Describing Live programming using program transformations and a callstack explicit interpreter by Olov Johansson LITH-IDA-EX--06/045--SE Supervisor : Tobias Nurmiranta Dept. of Computer and Information Science at Linko�ping University Examiner : Anders Haraldsson, Associate professor Dept. of Computer and Information Science at Link�oping University Abstract A formalization of how to apply incremental modi�cations to a running program while deterministically preserving state is presented. These are described using source code transformations converted to abstract syntax tree and callstack transformations. A rationale for why dynamically typed languages bene�t most from the concept is given, as are explanations to the selected programming language and implementation using an explicit callstack. Keywords : live programming, incremental, program transformations, explicit callstack, dynamic programming language, interpreted, javascript iii iv Acknowledgements Thanks to my examiner Anders Haraldsson and my supervisor Tobias Nur- miranta for being positive and encouraging, for interesting and helpful dis- cussions and for letting me hack and write away. Thanks to Brendan Eich and the Mozilla organization for writing �ne software and releasing it as free software for others to build their work on. v vi Contents 1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Typographic conventions . . . . . . . . . . . . . . . . . . . . 3 1.4 Report and source code availability . . . . . . . . . . . . . . 4 1.5 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Live programming justi�ed 5 2.1 Type information as programmer aid . . . . . . . . . . . . . 5 2.2 Identi�er veri�cation as programmer aid . . . . . . . . . . . 6 2.3 REPL as programmer aid . . . . . . . . . . . . . . . . . . . 7 2.4 Debugging is a two way process . . . . . . . . . . . . . . . . 8 2.5 Three mantras . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6 Levelling up tests and design by contract . . . . . . . . . . 10 2.7 Delivering via Live programming . . . . . . . . . . . . . . . 10 2.8 How to deliver it . . . . . . . . . . . . . . . . . . . . . . . . 12 2.9 Proof of concept prototype . . . . . . . . . . . . . . . . . . 13 3 JavaScript 17 3.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Logical operators . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 De�nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5 Dynamic (and weak) type . . . . . . . . . . . . . . . . . . . 20 vii viii CONTENTS 3.6 Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.7 Prototype-based object model . . . . . . . . . . . . . . . . . 21 3.8 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 JavaScript interpreter implementation 25 4.1 Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1.1 AST structure . . . . . . . . . . . . . . . . . . . . . 26 4.2 Evaluator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.1 Implicit callstack . . . . . . . . . . . . . . . . . . . . 27 4.2.2 Explicit callstack . . . . . . . . . . . . . . . . . . . . 31 4.2.3 Reference and value arguments . . . . . . . . . . . . 35 4.2.4 Function and constructor calls . . . . . . . . . . . . 36 4.3 Active/passive terminology . . . . . . . . . . . . . . . . . . 37 4.3.1 Source code correspondence . . . . . . . . . . . . . . 39 5 Source code transformations 41 5.1 Insertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.1.1 Insertion into an active block sequence . . . . . . . . 42 5.1.2 Insertion into an active comma sequence . . . . . . . 42 5.1.3 Insertion into an active variable declaration sequence 43 5.1.4 Insertion into an active array initializer . . . . . . . 43 5.1.5 Insertion into an active object initializer . . . . . . . 44 5.1.6 Insertion into an active arguments list . . . . . . . . 44 5.1.7 Insertion into a parameter list of an active function . 44 5.2 Deletions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.3 Replace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.3.1 Replace an active statement or expression . . . . . . 46 5.3.2 Compatible replace . . . . . . . . . . . . . . . . . . . 47 5.3.3 Replace a passive statement or expression . . . . . . 47 5.4 Expand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.4.1 Expand an active statement or expression . . . . . . 48 5.4.2 Expand a passive statement or expression . . . . . . 50 5.5 Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.5.1 Reduce an active statement or expression . . . . . . 51 5.5.2 Reduce a passive statement or expression . . . . . . 52 5.6 Swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 CONTENTS ix 5.6.1 Swap active statements or expressions . . . . . . . . 52 5.6.2 Swap passive statements or expressions . . . . . . . 54 5.7 Updating scope . . . . . . . . . . . . . . . . . . . . . . . . . 54 6 AST and callstack transformations 57 6.1 Insertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 6.1.1 Insertion into an active sequence . . . . . . . . . . . 58 6.1.2 Insertion into an active array initializer . . . . . . . 59 6.1.3 Insertion into a parameter list of an active function . 61 6.2 Deletions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6.3 Replace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6.4 Expand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.5 Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.6 Swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 7 Related work 69 7.1 Stackless Python . . . . . . . . . . . . . . . . . . . . . . . . 69 7.2 The \Lisp machines" . . . . . . . . . . . . . . . . . . . . . . 70 7.3 Smalltalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.4 Visual Studio 2005 . . . . . . . . . . . . . . . . . . . . . . . 70 8 Discussion 73 8.1 The prototype environment . . . . . . . . . . . . . . . . . . 74 8.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 A Sample Live programming session 77 B AST for GCD program 83 Bibliography 91 x CONTENTS