Skip to content

Instantly share code, notes, and snippets.

@lazywithclass

lazywithclass/blog-post.md

Last active July 12, 2017 16:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lazywithclass/5ba4ba7198c195a661f62c08e49deef1 to your computer and use it in GitHub Desktop.
Save lazywithclass/5ba4ba7198c195a661f62c08e49deef1 to your computer and use it in GitHub Desktop.
Download ZIP
Implementing racket/trace in JavaScript
Raw
blog-post.md

Implementing racket/trace in JavaScript - lazyblog

This is a blog post / diary of my journey through this task, as I'm writing this words I have no idea how and if I will be able to achieve the goal. But, if you're reading this, then probably there's hope.

Why

racket/trace prints calls to a function, that could be useful when dealing with recursion:

(require racket/trace)

(define sum
  "returns the sum of numbers from 0 to n"
  (lambda (n)
    (cond
      ((= n 0) 0)
      (else (+ n (sum (- n 1)))))))

;; instrumentation
(trace sum)

(sum 4)

Once we execute that code we get

>(sum 4)
> (sum 3)
> >(sum 2)
> > (sum 1)
> > >(sum 0)
< < <0
< < 1
< <3
< 6
<10

I think it's pretty great, I would've loved something like this when I first encountered recursion. It is showing the different calls to sum, as n decreases, then once the base case is hit the ns from the previous steps are summed, to give 10 (4 + 3 + 2 + 1 = 10).

How

I don't know how to write such a thing. Either in JavaScript, Racket, or whatever.

AST?

Suppose we want to trace the following

function sum(n) {
  return n === 0) 0 : n + sum(n - 1)
}

To instrument the code to trace n through the recursive calls I would

function trace() {
  let args = []
  return function _tracer() {
    if (_tracer.caller) args.push(_tracer.caller.arguments)
    return args
  }
}

let tracer = trace()

function fact(n) {
  tracer()
  return n < 2 ? 1 : n * fact(n - 1);
}

fact(10)

tracer()

So to get the parameters one would have to

  • inject trace definition in the source file
  • add the call to tracer() in the function under tracing
  • execute the function
  • call tracer() to get back the data and manipulate it

which is not what Racket does, this is what they do (from the docs)

trace(id) Each id must be bound to a procedure in the environment of the trace expression. Each id is set!ed to a new procedure that traces procedure calls and returns by printing the arguments and results of the call via current-trace-notify.

It seems to me they are not changing the AST, rather they are doing something at language level. Something.

Back to the drawing board

racket/trace is defined here, I looked into that for a couple days without much success, there is too much new syntax for me to look at, and I don't have this kind of mental power to push through right now, partly because I am going through Type Driven Development with Idris and partly because I am looking for a job!

So I am now back to the drawing board.

I would love to have a hacky solution I could use to spike a workflow, so that this new tool could be integrated in my Spacemacs, the idea is to also extend Node.js REPL so that it has more features and also the existing one could be smoother (eval last expression for example is not really working).

The lazy in me in asking "there has to be something we could start from, are you nuts?!? You want the brain dude to start something from scratch? You did once and it went pretty dire in the first period, remember?".

So I am thinking about TraceGL (by Mozilla), I remember it had some nice features that could do what I want, so hopefully reading JavaScript source will sound more palatable to my lazy self.

Is that light that over there at the end?

After some source reading and some rage I think I got a hacky enough version that I could use for something

// `define` definition skipped, because it's super long and because I don't think I get it
// I think Mozilla devs did that to have an easy way to replace `require`
// I took it from here https://github.com/traceglMPL/tracegl/blob/master/core/define.js

// you have to call it, don't ask
define()

const instrument = require('./tracegl/trace/instrument'),
      vm = require('vm');
      fs = require('fs'),
      content = fs.readFileSync('./instrumented-treis.js').toString()

// looks like the only meaningful parameter here is `content`
var instrumented = instrument('file-path', content, 1, {})
const script = new vm.Script(instrumented.output);
script.runInThisContext()

which produces

{"i":1,"g":1,"d":1,"u":0,"t":1496162575237,"a":null}
{"i":2,"g":2,"d":2,"u":1,"t":1496162575238,"a":[5]}
{"i":2,"g":3,"d":3,"u":1,"t":1496162575238,"a":[4]}
{"i":2,"g":4,"d":4,"u":1,"t":1496162575238,"a":[3]}
{"i":2,"g":5,"d":5,"u":1,"t":1496162575238,"a":[2]}
{"i":2,"g":6,"d":6,"u":1,"t":1496162575238,"a":[1]}
{"b4":true,"g":7,"i":3,"d":6,"v":1,"c":5}
{"b4":false,"g":8,"i":3,"d":5,"v":2,"c":5}
{"b4":false,"g":9,"i":3,"d":4,"v":6,"c":5}
{"b4":false,"g":10,"i":3,"d":3,"v":24,"c":5}
{"b4":false,"g":11,"i":3,"d":2,"v":120,"c":7}

Hey look ma'! No hands! (which is me bragging about something I didn't write but works as I want)

I didn't say it before but I will now: their source looks like it came out from a code minifier nightmare. But I'm grateful for it.

So by staring enough at those lines it becomes clear that property a holds an array of arguments passed to the function and property v holds the increasing number, which ends up being 120, which is fact(5). So now we have everything we need, what remains is

  • extract that info from script.runInThisContext()
  • surround that with some Elisp enough to be called with a key combination
  • present the information

Some coding from me

Extract that info.

It doesn't look like it is being written neither to process.stdin neither to process.stdout. I think I should probably have a look at the instrumented function

// lots of functions defined here, among others there's a promising one called `dump`

function fact(n) {
  var _$_g2 = _$_.f(2, arguments, this, _$_g1);
  var _$_b = {};
  try {
    return (_$_.e(3, _$_b, ((_$_b.b4 = n < 2) ? 1 : n * (_$_.c(5, fact(n - 1))))));;
    _$_.e(6, _$_b)
  } catch (x) {
    _$_.e(6, _$_b, x, 1);
    throw x;
  }
}

;
(_$_.c(7, fact(5)));
_$_.e(8, _$_b)

I think the interesting parts are where arguments

var _$_g2 = _$_.f(2, arguments, this, _$_g1);

and recursive step

return (_$_.e(3, _$_b, ((_$_b.b4 = n < 2) ? 1 : n * (_$_.c(5, fact(n - 1))))));;

are captured. The first is pretty straightforward, whatever those other parameters are we are passing arguments to some _$_.f function. The second... lol. Let's try another way.

I will override process.stderr.write so it will behave as I want it to

const instrument = require('./tracegl/trace/instrument'),
      vm = require('vm'),
      fs = require('fs'),
      content = fs.readFileSync('./source.js').toString()

function parse(line) {
  line = line.replace('\u001f', '').replace('\u0017', '')
  line = JSON.parse(line)
  // line.d is the number of the nested level we are in, it was difficult to find out
  // but pretty handy to use, since now I can use it to indent on the right
  console.log(Array(line.d).fill().join('    '), line.a || '', line.v || '')
}

let instrumented = instrument('a', content, 1, {})
vm.runInThisContext(
  `global.process.stderr.write = ${parse};` +
  instrumented.output
);

...which seems to work pretty well. With a small amount of Elisp, this is how the result looks like in my setup (bottom left of the screenshot), while this is the repo.

Next steps

From here I have to figure out the following

  • license from the code I took from TraceGL, where should I put it? Can I do what I did?
  • it would be useful to make it work in such a way that when a region is selected in an Emacs buffer, with function declaration and function call, then it would show the above output
  • figure out how the instrumentation works
  • polish the code and publish it
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment