Title
#share-your-work
c

cdfa

01/23/2022, 6:24 AM
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!
a

Andrew F

01/23/2022, 6:28 AM
I'll have to dig into it later, but this sounds awesome.
Kartik Agaram

Kartik Agaram

01/23/2022, 6:29 AM
This seems worth a PhD..
c

cdfa

01/24/2022, 3:15 AM
I just noticed that the web version was not working on Chrome. This should be fixed now!
3:16 AM
There also seems to be a bug when using the online version in firefox where the application gets stuck (possibly after many edit actions in quick succession). Will look into it as soon as I have time
j

Jason Morris

01/24/2022, 2:03 PM
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.
c

cdfa

01/24/2022, 3:06 PM
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
dnmfarrell

dnmfarrell

01/25/2022, 4:17 PM
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
c

cdfa

01/25/2022, 7:34 PM
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
dnmfarrell

dnmfarrell

01/26/2022, 2:54 PM
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 ...
1:35 AM
I really enjoyed reading your thesis, thanks for sharing. The described issues with IDEs and "strict" structure editors resonate with my experience. Construction sites seem very promising. And perhaps "fuel" is a common concept but I hadn't heard of it and appreciated the explanation ... and its utility!
c

cdfa

01/27/2022, 10:56 AM
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).
12:07 PM
I just uploaded the presentation! https://archive.org/details/presentation_202201 Sorry if the volume is a bit low. If it's too quiet, I can upload a louder version later. The last 20 minutes is questions.
a

Andrew F

01/28/2022, 7:33 PM
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.
y

yairchu

01/30/2022, 12:13 PM
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).
12:15 PM
However, evaluation is not continued around hole arguments in application terms or under partially applied lambda terms and function values are not displayed.
True, however this isn’t by design, just that we didn’t get to it yet. So much to do 🙂
c

cdfa

01/30/2022, 2:24 PM
@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.
2:27 PM
@yairchu Oh I should have another look with this information in mind. Does your editor completely prevent type errors then? Thanks for pointing it out in any case. I'll update the online version of the thesis when I can.
y

yairchu

01/30/2022, 2:35 PM
@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)
c

cdfa

01/30/2022, 2:35 PM
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
y

yairchu

01/30/2022, 2:36 PM
So to clarify, yes, Lamdu does completely prevent type errors. The code always type-checks.
c

cdfa

01/30/2022, 2:37 PM
@yairchu Ah cool! Is the mechanism documented anywhere currently?
y

yairchu

01/30/2022, 2:41 PM
Closest thing to documentation would be our short 10 mins video on the topic

https://youtu.be/viF1bVTOO6k

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
c

cdfa

01/30/2022, 2:44 PM
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?
y

yairchu

01/30/2022, 2:47 PM
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.
c

cdfa

01/30/2022, 3:03 PM
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?
3:10 PM
Currently, my main concern is making it safe to automatically run I/O actions. If you're building a system that could launch rockets, you wouldn't want to launch the rockets repeatedly, but still find out if you would get a "rockets launched successful" return message from the external system depending on how you tweak parameters of the launch call. To do it safely, you also need a "test" version of the external system, which the programming environment could help the user set up. I think with an explicitly set up test environment (a bit like a Docker container) that the programming environment can reset when necessary, it should be possible to make running I/O actions automatically safe. It's also a lot of work though🙃
y

yairchu

01/30/2022, 3:19 PM
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
Kartik Agaram

Kartik Agaram

01/30/2022, 3:26 PM
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.
y

yairchu

01/30/2022, 7:40 PM
This discussion is assuming that we did this distinction (which we did)
c

cdfa

02/03/2022, 12:16 PM
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.
dnmfarrell

dnmfarrell

03/16/2022, 7:49 PM
@cdfa I just came across Tree Sitter https://tree-sitter.github.io/tree-sitter/ which might interest you
c

cdfa

07/20/2022, 7:12 PM
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.
7:14 PM
Another minor reason I didn't use it is because you have to parse the generic AST representation it uses to your main implementation language. So you still have to do some parsing yourself (at least I think so, please correct me if I'm wrong)
7:14 PM
And sorry to bump such and old thread everyone 😅