Explore alternative tree styles

[dhess]

I get the feeling that adults are having trouble understanding how we're rendering trees with the explicit application $ operator and spines. (We have no actionable data from our beginner tests because we haven't spent much time with them on function application, but IMO there's no reason to think that beginners/students will have an easier time.)

I don't think we should abandon our current style, but we should probably look into supporting other styles, as well. This old Viz Figma design is instructive and enumerates all the obvious alternative approaches:

https://www.figma.com/file/CIZdrV2zzo1jcnltVifDGG/Viz?node-id=21%3A52

Our current style is called "binary tree view" in that Figma document. My hunch is that the rose tree style will have similar problems, though it is somewhat similar to text view and possibly will make the leap to trees easier.

I think the "apply tree view" will be the easiest to understand, and will be particularly helpful if we try to teach trees via arithmetic expressions, IMO. Therefore, this is my first choice of the alternatives.

(I think the hybrid text-tree view is also interesting, especially once we've implemented code folding, but I'm not sure it's very intuitive. It might be worth testing later down the line.)

[georgefst]

I think the "apply tree view" will be the easiest to understand

This would make it difficult to explore evaluation as incrementally as we currently do. What would inlining a function look like?

[dhess]

That's a good point, and one of the reasons I called this issue, "Explore alternative tree styles," rather than, "Implement alternative tree styles." I expect this exploration will lead to some questions about our current eval approach.

Part of this exploration is motivated by the fact that, so far, nobody understands our eval mode. At least part of the confusion is because we don't have nice animations and because you have to switch so many screens to see steps & details. But we should also think about, and possibly implement + test, some slightly less small-step approaches, look for tree renderings that are easier to understand, etc.

[dhess]

FYI, my hunch about bigger-step evaluation being easier to follow isn't completely unsubstantiated. Last summer, when I was teaching our summer intern using our Haskell course, I introduced her to equational reasoning/evaluation by "big step" substitution of simple text-based expressions, using a whiteboard. It worked really well and didn't require all the minutiae we have in our current eval mode.

[dhess]

I want to further expand on my last comment about teaching equational reasoning through big-step substitution.

Viz had a quite different, big(ger)-step approach to evaluation than Vonnegut does. For example, we substituted terms in patterns without providing the student with any explicit semantics. Given the following set of rules:

and False _ = False
and True a = a

let p = True
let q = False

If the student evaluated the expression and $ p $ q, we showed more or less the following sequence of reductions:

and $ p $ q => and $ True $ q => q => False

I'm eliding the visual bits where we showed how each function argument was matched to its corresponding pattern parameter, etc. But the gist is that we assumed the student understood that True was being substituted for p, and that they didn't need to have this spelled out.

My concern at the time was that we might be assuming too much. Maybe students wouldn't understand the substitution process. I wondered whether there was a way we could show how that substitution happens using additional rules, rules that the student could easily understand. This first occurred to me when @brprice and I were reading the Rainbow Scheme paper, in which they visualized the environment in which symbols were looked up, as a sort of sidecar tacked onto the evaluation trace.

Anyway, I asked Harry to consider this, and other small-step rules, when developing the initial pass at a visual evaluator in Vonnegut, and he came up with the clever idea of using let bindings for this, so that the student wouldn't need to understand how substitution worked in function application so long as they understood how let worked. This is how we ended up with our current approach.

So, when considering how big the steps should be in the evaluator, there's a continuum. On the bigger step side, it might be easier to follow the big picture, so long as the student understands what's implied between each step. On the smaller step side, it might be harder to follow the big picture, but each individual step should be easier to understand on its own.

Early feedback from Vonnegut's eval mode indicates that we might be inundating the student in too much detail, and losing the forest for the trees. (Pun not intended.) But it's hard to judge given that we don't currently do a good job of connecting the small steps very well.

At the very least, even if we keep our small-step evaluator, I think we can justify implementing a bigger-step approach, more like Viz's, given that students will eventually understand the small steps and probably then just want to see atomic term rewriting, without all the machinery.

[georgefst]

I'm very fond of our small-step evaluator, and have a strong hunch that it'd be significantly more understandable with better tree rendering, and animations. I find it difficult to follow at the moment, because of how different the trees can look between "small" steps, due to differences in layout which we have little control over with the current implementation.

I do agree that we should make it easier to skip steps, for more advanced students.

[dhess]

Just to clarify my thinking, I do think we should fix the issues with the small-step evaluator before we move on to alternative approaches.

(However, if that proves too difficult or becomes just a massive time sink, we might need to reprioritize, if we're in a time crunch. There is a lot of work to do on it!)

[dhess]

This project generates some very pretty (non-interactive) ~"apply trees"~ binary trees: https://projectultimatum.org/cgi-bin/lambda

One nice touch are the backlinks from variable uses to their binders. (We have discussed this idea before. I'm not sure it would work well for large programs, but it might be a good idea to draw them dynamically when a variable use is selected in the tree.)

[georgefst]

This project generates some very pretty (non-interactive) "apply trees": https://projectultimatum.org/cgi-bin/lambda

Are those actually "apply trees"? They appear to be essentially the same as our "binary tree" style, only using @ instead of $.

In fact, to check we're all on the same page, what are we actually proposing that lambdas look like in "apply tree" style? Perhaps this hasn't been discussed, but it's a crucial detail and I can't come up with an obvious answer. For the sake of an example, how might we render (λx.x) a b?

[dhess]

Sure, let's call them binary trees. I sometimes say "apply tree" because it shows the application as a separate, explicit node, but you could also draw those with >2 children, so binary tree is more precise.

[georgefst]

I sometimes say "apply tree" because it shows the application as a separate, explicit node

Ah. This is the source of confusion then, since the Figma doc uses "apply tree" to refer to the one design in which this is not the case.

[dhess]

Yeah, it's a misnomer that I keep bringing up, so feel free to keep correcting me :)

[georgefst]

Incidentally, in last Thursday's meeting on the testing report, we discussed the idea of showing all arguments to an application at the same y-axis, along with possibly visually distinguishing leaf nodes from branch nodes.

It occurs to me after revisiting this Figma doc, that we might then simultaneously get the benefits of both the "binary tree" and "rose tree" views. i.e. it becomes easy to visualise application in both curried and uncurried form.

[dhess]

That's true, but it still has the problem that the most intuitive way to read the tree is from bottom left up, whereas for trees where the function is at the root, you can read top down, left-to-right. This is one reason why I think #85 might be useful.