Macrofication: Refactoring by
Reverse Macro Expansion
Christopher Schuster, Tim Disney, Cormac Flanagan
University of California, Santa Cruz
{cschuste, tdisney, cormac}@ucsc.edu

Example: Bubble Sort in JavaScript


function bubbleSort(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = i; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        swap(arr[j], arr[j + 1]);

      }
    }
  }
}
function swap(arr, i, j) {
  var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}


macro { swap($a, $b); }
   => { var tmp = $a; $a = $b; $b = tmp; }

Macro Expansion



macro
   { swap($a, $b);}


=> { var tmp = $a;
     $a = $b;
     $b = tmp; }


swap(arr[j], arr[j+1]);

    ⇩

{$a:`arr[j]`,$b:`arr[j+1]`}

    ⇩

var tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

Reverse Macro Expansion


macro
   { swap($a, $b);}


=> { var tmp = $a;
     $a = $b;
     $b = tmp; }

swap(point.x, point.y);

    ⇧

{$a:`point.x`,$b:`point.y`}

    ⇧

var tmp = point.x;
point.x = point.y;
point.y = tmp;

Demo

Implementation

Github Repository: https://github.com/mozilla/sweet.js

Online Live Demo: http://sweetjs.org/browser/editor.html

Related Work

Macro systems

Disney, Faubion, Herman and Flanagan.
Sweeten your JavaScript: Hygienic macros for ES5. (DLS'14).

LISP, Scheme, Racket, Rust, Template Haskell

Resugaring

Pombrio and Krishnamurthi.
Resugaring: Lifting Evaluation Sequences Through Syntactic Sugar. (PLDI'14).

Related Research Areas: Refactoring, Term Rewriting Systems, Pattern Matching, Unification, ...

Pattern Matching Repeated Variables: swap


macro
   { swap($a, $b);}


=> { var tmp = $a;
     $a = $b;
     $b = tmp; }

swap(x, y);

    ⇧

{$a:`x`,$b:`y`}    ✗

    ⇧

var x = 12, y = 23;
var tmp = x;
x = yy + 1;
y = tmp;

Repitition groups: Class Definition Macro

class Person {
  constructor(name) {
    this.name = name;
  }
  sayName() {
    alert(this.name);
  }
}

function Person(name) {
  this.name = name;
}
Person.prototype.sayName =
  function() {
    alert(this.name);
  };

macro { class $cname {
          constructor ($cparams...) $cbody
          $($mname ($mparams...) $mbody)...
        } }
   => { function $cname ($cparams...) $cbody
        $($cname.prototype.$mname =
          function ($mparams...) $mbody;)... }

Extended Pattern Matching Algorithm

Non-deterministic Macrofication


macro { inc $x } => { $x + 1 }

Problem 1: Overlapping rules


macro { inc 1 }  => { 3 }
macro { inc $x } => { $x + 1 }

Problem 2: Conflicts between order of expansion


macro { inc $x } => { $x + 1 }

Hygiene


macro { swap($a, $b) }
   => { var tmp = $a; $a = $b; $b = tmp; }

Problem 3: Hygiene


macro { swap($a, $b) }
   => { var tmp = $a; $a = $b; $b = tmp; }

Ensuring Refactoring Correctness

Naive reverse expansion produces incorrect results

Correct refactoring depends on context and scoping

Solution: Macro-expand original and refactored code and enforce syntactic equivalence

expand(source) =α expand(refactor(source))

Syntactic equivalence may reject valid refactoring candiates

Case Study

Can the macrofication refactoring be applied to real world code?

Task: Refactor BackboneJS, a MVC library for JavaScript, by replacing its prototype definitions with ES2015 class definitions

Is it fast enough for interactive use?

Benchmark: Find all macrofication candidates in the ru-lang project

Project	LOC	Time to refactor	Macros	Macrofications
Backbone.js	1633	0.9s	1	5
ru-lang	257	17.0s	27	52

Discussion

Advantages

Preserves program behavior and thereby avoids bugs by manual refactoring
Given a macro, refactoring can be performed interactively with little effort
- Future work: Macrofication for non-macro refactoring

Disadvantages

Refactoring requires macro provided by the programmer
- Future work: Infer / Synthesize new macros
Larger macros often project-specific
Potential refactoring options can be missed due to minor differences between the macro template and the code
- Future work: Behavioral instead of syntactic equivalence

Thank you!

Appendix: sweet.js macro syntax


let macro = macro {
  rule {
     { $name $pat ... } => { $tmpl ... }
  } => {
    macro $name {
      rule { $pat ... } => { $tmpl ... }
    }
  }
}

Macrofication: Refactoring byReverse Macro Expansion Christopher Schuster, Tim Disney, Cormac Flanagan University of California, Santa Cruz {cschuste, tdisney, cormac}@ucsc.edu