Hello everyone! After a year of work, I am finally presenting the result of my Master's thesis!🎉🎓 I developed and studied a live programming environment that can provide meaningful information about the runtime behaviour of a program in practically every edit state, while retaining the intuitive and flexible interface of text editors. To provide meaningful runtime behaviour information in edit states containing incomplete programs with syntax, type or logic errors, the programming environment has to isolate errors and continue functioning for unaffected parts of the program. I call this error tolerance. Tolerance of syntax errors is realized with an integrated structure editor that incorporates a notion of incompleteness I call construction sites. Essentially, these are abstract syntax tree nodes that can contain arbitrary characters and other AST nodes. Evaluation of the program continues "around errors" instead of aborting with an exception or resulting in some "undefined" value. Because the results this produces are much more informative than an exception or undefined value, they can help the programmer find the sources of issues and resolve them much better. Because the programming environment is often evaluating unfinished code, evaluation diverges much more often. The programming environment handles this smoothly by only evaluating parts of the runtime information that are displayed and providing a mode of evaluation where the number of reductions is limited by a configurable number. This enables partial results in cases of non-termination. You can try out the editor for yourself at https://cdfa.github.io/frugel/ 👀 or by downloading a much better performing native executable from GitHub. I also created a demo video 📺 (WebArchive version (still uploading), Google Drive version) and attached a draft version of the thesis. I hope to follow up this week with a version that fixes some bugs. This Wednesday, I will be giving an online presentation about it. If you are interested in attending, I can PM you a link to watch it. Please let me know what you think!

I'll have to dig into it later, but this sounds awesome.

This seems worth a PhD..

I just noticed that the web version was not working on Chrome. This should be fixed now!

This is really smart, Colin. If the text always generates a valid AST because of construction sites, could you use it to maintain isomorphism between the text and another representation, like a visual block interface, by creating visual blocks for construction sites? So that people using something like Blockly could switch back and forth between the text and visual coding environments at will, even while the code was being run? That seems like a huge win.

There is not quite an isomorphism, because if you convert the AST to plain text, you lose information that allows you to isolate the syntax error. However, you could definitely add a visual block interface and use the structure editor as a textual one

Very interesting! I noticed the other day golang's ast has "BadExpr", "BadStmt" and "BadDecl" types which could serve a similar purpose (have not tried them yet though). https://pkg.go.dev/go/ast

Oh cool! Wonder how the parser works with that. I don't know much about go, but seems that it only consists of two source positions, so probably just represents a sequence of characters in the text source

After trying it out this morning the go parser seems limited: it can parse lone expressions, but not statements. In order to parse a statement you have to provide a complete package, e.g. to parse the function foo:

package foobar

func foo() string {
	return "foobar"
}

You could imagine pre-pending code with a faux package declaration in order to parse it but it is worse than that; there is a restricted set of statements that can appear in the top level declaration of a package, so some statements will need to be wrapped in a faux function declaration in order to parse them ...

Thanks for sharing your experience with the go parser! The feedback on the thesis is also much appreciated. Apparently, my supervisor and second reader are failing to understand some parts of it and aren't giving me a great grade (sufficient to graduate, but not still unfair imo).

Just watched this and skimmed your thesis. Looks great. I didn't see whether you're serializing the AST with construction sites? That's a really interesting topic for me, hopefully not even that hard in principle... I've been thinking for a long time about semi machine-readable state like this, not just for code but any other structured data. Similar ideas pop up when you think about search patterns over structured data (where the construction site-like part is treated as a sort of hierarchical wild card), multi-selections in a tree structure (like, say, search results), directly manipulating databases with strict schemas, etc. "As specific as desired" is one of my cross-cutting guiding principles, and your work fits right in. I probably need to look at Hazel, too.

Nice work! In section “7.3 Lamdu”:

For example, if we attempt to insert a number where a function is expected, the expression is transformed to an application term with a hole for the argument. This term can then be typed as a free type variable. However, the number is inserted in the function position of the application term, which still results in a type error.

The last sentence is incorrect. The number is actually inserted in the argument of the application term in the underlying language, and there is no type error. Perhaps the confusion stems from the sugared surface language showing it as a number with a question mark next to it (which we call a “fragment” with a number in it).

@Andrew F Yeah I could definitely see the idea being applied to structured data more generally! It's basically allowing less structure with the highest granularity possible. Not sure exactly what you mean with "whether I'm serializing the AST with construction sites", but there is a partial linearization step in the edit loop where the AST is mostly serialized. However, this step is "partial" in the senses that construction sites in the AST are preserved. To do this, it serializes the AST to a construction site (called a root construction site) instead of plain text.

@cdfa yes, wrapping type errors in “fragments” was a key feature of Lamdu since 2013! And was at a novel solution for this problem (it was later adopted by Hazel too)

Displaying bodies of (partially applied) functions is definitely challenging, mostly because of variable capture and preserving the names of binders. It's even worse when the same function values can show up in several places because you would like to see the same "fresh" variable names/identifiers in all places

So to clarify, yes, Lamdu does completely prevent type errors. The code always type-checks.

@yairchu Ah cool! Is the mechanism documented anywhere currently?

Closest thing to documentation would be our short 10 mins video on the topic The mechanism is very close to Hazel’s although our solution is more general and works also for refactorings, and we also have a novel solution for cross-definition changes

Something I thought is very cool is that Lamdu has some I/O capabilities. If I understand correctly, you're currently asking the user when to run I/O actions, but this seems to get in the way of live programming. Do you have plans for more advanced solutions?

I would like to hear about your ideas for more advanced solutions 🙂 One idea we have in mind is that you should be able to “record” results of IO interactions and then re-evaluate from recorded runs. Then you could modify the program up to a point where the IO actions that it invoked changed.

So for example, if you make an API request and you're modifying code that uses the returned data, it would not make the request after every edit but reuse saved data? Would you "snapshot" other program state (like values of variables) that is also relevant to the code processing the request's data as well, or recompute it from literals/other cached data?

if you make an API request and you’re modifying code that uses the returned data, it would not make the request after every edit but reuse saved data?

Exactly.

Would you “snapshot” other program state (like values of variables) that is also relevant to the code processing the request’s data as well, or recompute it from literals/other cached data?

Only the descriptions for the IO actions and their results will be saved, the other stuff will be recomputed normally

Separate detecting side effects from deciding how to deal with them. The former is key, and it's some tedious but fairly straightforward work, tagging low-level primitives in your standard libraries that invoke OS syscalls. Once you have such primitives tagged the UI can do a variety of things when they're directly or indirectly invoked. Record and replay (won't help for launching rockets), switch to a mocked or fake version. Most important, the UI will be able to ask the programmer what they'd like.

This discussion is assuming that we did this distinction (which we did)

I updated the thesis based on @yairchu’s comments. I cannot edit my initial message, but the latest version can be found here. The surface language showing a ? after the number was indeed what threw me off.

@cdfa I just came across Tree Sitter https://tree-sitter.github.io/tree-sitter/ which might interest you

Great that you mention it! I encountered tree-sitter as well while working on Frugel and it's error recovery capabilities are pretty impressive. However, the fact that it does error recovery is also the reason I did not use it in Frugel, because guessing at the programmer's intent is inherent to error recovery. That this can yield unintended results is also demonstrated by this article.