Instantly share code, notes, and snippets.

# lazywithclass/blog-post.md

Last active July 12, 2017 16:14
Show Gist options
• Save lazywithclass/5ba4ba7198c195a661f62c08e49deef1 to your computer and use it in GitHub Desktop.
Implementing racket/trace in JavaScript

## 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 `n`s 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'),

// 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'),

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