Lambda the Ultimate

I actually came up with the concept in china. I originally wanted to call it East, since it's where the idea was born. It's also a combination of EAsy and faST (FASY being another option.) not to mention an acronym: "Editor for Abstract Syntax Trees". Unfortunately, google code claimed that the name "east" was already taken, so I changed it to its current form.

In Chinese, dongxi is also used as an euphemism as could be imagined. Or perhaps I hang out with the wrong people.

I'm not big on structure editors. You could get most of the benefits in an unstructured editor using clever incremental parsing/type checking techniques that are well understood by now.

It is true that clever incremental parsing/type checking gives many of the advantages usually associated with structure editors while keeping the text based interface which we all know and love. There are, however, some things which cannot be achieved in text:

- arguments can appear anywhere in function names and function names can include spaces and characters from other languages, allowing the source code to appear like human language (something similar to inform 7). It is possible to write programs in Japanese (using kana).

- the user is forced to only add from a finite list of options, a kind of exact completion, thus a user cannot make a type unsafe choice.

- smart code formatting automatically expands/retracts the source tree, graphically showing the user the local structure while keeping the source code compact.

- the user does not need to learn a syntax. Instead, the user can conceptualize based on the name of the action such as "add a function" or "include a module"

- the user can then use the structure editor when asking for input (see http://www.youtube.com/watch?v=JTlRpE7Y_X4 )

- "token types" allow the users to exactly represent languages with bindings, such as the language of closed lambda terms.

- Since incremental parsing is not needed, this is way is potentially faster.

I don't really agree with any of these bullets except maybe the last which is true but almost not worth discussing. Some of this requires IDE support over what Notepad provides, but isn't incompatible with incremental parse. Not supporting whitespace in identifiers is a trade-off that allows whitespace to be the separator between tokens - it could be something else.

I'd like to hear why you disagree with each point. However, I may not have made my points as clearly as I should have.

for function names:

the following are legal function names:

the average of (float) and (float)
(float) is greater than (float)
if (bool) then (a) else (a)

so that you can write code like:

if the average of x and y is greater than 2 then ... else ...

for the exact completion argument:

it is simply not possible to write something like this:

"hello" - "world"

Another point I forgot to make: all function calls are implicitly qualified with its module but these qualifications are not shown to the user. The user chooses the module when calling it, but this is painless thanks to the completion mechanism.

If anyone wants a clearer idea of what I mean I suggest they try it out or that they look at some of the videos I posted in the tutorial.

Right, there's nothing preventing english-like function names (or at least the functional equivalence) with a more conventional parser/IDE.

In fact, Algol 60 allowed calls that looked like

        The_average_of (float) and: (float);

The idea was that commas in argument lists could be replaced by )identifier:(.
(Uhh, maybe I have the colon and the identifier swapped. And maybe it allowed spaces instead of underscores; there's no good reason why not -- it was legal in FORTRAN. Algol 60's lexical behavior was always a gray area. It's been a long time...) And of course Smalltalk 80 calls look fairly similar.

so: the average of (float) and: (float);. The BNF defined this alternative to comma as ')', label, '('.

Of course, in order to do that you had to strop your reserved words, writing either 'if' or IF, depending on the compiler, or (for publication) if. Simple if was an identifier.

the following are legal function names:

the average of (float) and (float)
(float) is greater than (float)
if (bool) then (a) else (a)

Something like mixfix parsing allows this, but I don't really think it's such a good idea. I don't understand your point about "hello"-"world".

If anyone wants a clearer idea of what I mean I suggest they try it out or that they look at some of the videos I posted in the tutorial.

I've looked at a few of the videos. It's a mouse based interface, which I wouldn't want to use for the majority of programming tasks. You can add a mouse based insertion mechanism on top of text based format (see eclipse), but it looks generally more difficult to me to start with a structural approach and retrofit parsability from text. Removing parsing ambiguity from the grammar should be done up front.

- the user is forced to only add from a finite list of options, a kind of exact completion, thus a user cannot make a type unsafe choice.

This is just IDE support.

- smart code formatting automatically expands/retracts the source tree, graphically showing the user the local structure while keeping the source code compact.

Again, this is just IDE support.

- the user does not need to learn a syntax. Instead, the user can conceptualize based on the name of the action such as "add a function" or "include a module"

The nice thing about a mouse driven visual interface is that it's easier to explore all the possible options. The bad thing is it's generally going to be slower and the user has to figure out where things are in the interface. Once you know you want "if X then Y" to show up on the screen, it's trivial to get it there using text editing. If you have to find it in some drop down or memorize a shortcut stroke for it, that's annoying. So we probably ought to have both, and again, text is the one you need to get right up front.

- the user can then use the structure editor when asking for input (see http://www.youtube.com/watch?v=JTlRpE7Y_X4 )

This is just saying that you can expose the IDE UI to the language through a library. That's not unique to the structural approach.

- "token types" allow the users to exactly represent languages with bindings, such as the language of closed lambda terms.

Text based languages need to have the concept of a parse error state. This is the price you pay for letting users edit code as text. But modulo this parse error state, closed lambda terms can be modeled exactly.

- Since incremental parsing is not needed, this is way is potentially faster.

Note that you could speed up text based parsing if you were willing to have more than just a plain text data structure representing the text.

the mouse based interface is optional and is presented only so that user's can see what's going on. In fact, the mouse based interface was added after the keyboard interface. You can view a video of me using the keyboard interface here:

http://www.youtube.com/watch?v=SSZBc2ohR2o

To input an "if (bool) then (a) else (a)", the user need only write "if" and Eastwest will list it as an option (most probably the first). This is fast because the user doesn't need to write "then" or "else". In my experience, it can be faster than editing text.

A description of the keyboard bindings can be found here:

http://sites.google.com/site/rathereasy/eastwest/tutorial#TOC-Keybindings

"hello" - "world" will never get accepted by the structure editor. Once you select that you want to call the " (float) - (float) " function, the structure editor will know that the first argument is a float, thus it will never accept "hello" as a valid option. In a standard IDE, the user can input anything he wants and he can make unparseable or untypeable additions. This is not the case in Eastwest.

Using the structure to get input from the user is a unique way to get input. It saves the programmer from having to write a GUI or a parser. Granted, the machanism of using the IDE through a library is not new but I've never seen it done to systematically get a value of any type. This is especially useful since the programmer will always get a well formed value; consequently, he does not need to have error messages.

Eastwest supports automatic expansion/retraction/formatting of the source code based on code size and cursor position which, in my experience, does away with manual formatting. If you know of any IDEs that do this, please let me know.

(a) you just have to define your tokens differently so that they can include whitespace. I've implemented incremental tokenizers that are flow sensitive that can basically do this (which you need to deal with comments in C-like languages). Your argument might have to do more with the fact that there is no good grammar for having whitespace in identifier names, but this can be solved with more syntax.

(b) Incremental type checking lets the user know when a type unsafe choice is made immediately, and can also prioritize choices based on type information (though if you are typing in an expression path, this isn't what you want anyways!). I've also done this.

(c) How is that different from automatic code formatting?

(d) This works fine with absolute beginners (see Alice) but doesn't even begin to scale to beginner programmers. Syntax is an important aspect of a language...and the user still has to learn the language!

(e) Don't get it (sorry, youtube is blocked by the greatfirewall of China, perhaps too many dongxi's there).

(f) you can do a lot with a tokenizer these days, much more than most languages do...

(g) Not an issue. Incremental parsing is fast enough, I've always been able to incrementally parse in the UI thread without noticeable slow down, even for huge files. The slow part that needs attention is always going to be type checking. Besides, you slow down the user significantly by having them think in discrete "good edits" and then use the UI to express those edits.

I'm not trying to slam your work, but your premise is hard for me to swallow, and it seems like we've been on this path before and the drawbacks of structured editing are already known to be game-enders. You either have to focus on defeating this criticism (not easy) or focus on unique features that you can only get with a structured editor (e.g., see Alice or even Subtext).

(a) Eastwest not only allows whitespaces and chinese/japanese/arabic/... characters, it also allows placing arguments anywhere. Some people have responded that they've seen this in Algol-60, but I don't know of any currently used programming language which supports it.

(b) The big winners for exact completion are beginners. I have to admit that experienced programmers would be happy with having an error message as soon as an unsound choice is made. However, I see no reason for letting the user make an unsound choice in the first place.

(c) It is different because the formatting which change depending on the cursor position. So that the expression " 2 + 3 " will be displayed as one line unless the 2 or the 3 is selected. You will need to watch the videos to really understand it.

(d) This is what is special about Eastwest: the user does not need to know the syntactic details about the language. Instead, he simply needs to get familiar with the concepts (which usually correspond to some kind of text on the screen.) In this manner, I can completely change the syntactic details and the user will still be able to easily adapt. Again, You'll need to watch the videos or try it out yourself.

(e) -

(f) I'd like to see a language which uses a tokenizer in this way. Furthermore, token types (mostly) do away with error messages.

(g) I consistently find IDEs which incrementally parse less responsive. I admit that this is a purely subjective and personal opinion.

I can understand your reservations with respect to using a structure editor to interact with a programming language. What is different here is that I also want to show that structure editors are ideal for domain specific languages especially those which are not often used and easily forgotten. Eastwest is a programming language made for creating user interfaces for domain specific language and specifying their interpretation. In this manner it serves two purposes: show that a structure editor can be used for a full fledged programming language and, for those who are skeptical about this first point, to show that it can be used for domain specific languages.

It's too bad you can't view the videos. Is there any way I can make them available to you?

Sean,

I think your critique is a bit fast. We have no evidence that the structure editing approach can't in principle be made to work, only that it can be tricky to match some of the ergonomic qualities of free text editing. (Intentional Software are betting their business on it.) Moreover, a similar claim could be made for incremental parsing/semantic analysis. We've been trying that for several decades (think Ensemble/Harmonia, etc), and the state of the art is still extremely primitive: just witness Eclipse or Visual Studio.

Indeed, the kind of fancy incremental parsers, type checkers and code formatters you allude to are really just structure editors made a little more user-friendly. A structure editor that works well can present the "illusion" of freely editable text. Conversely, a fancy syntactically- and semantically-aware text editor can present the "illusion" of directly manipulable semantic structure. Sufficiently well implemented, they collapse functionally into the same thing.

I'm going to stand by my critique. The ergonomics of structured editing is a show stopper for anyone but novices. Anything that puts you into a rigid mode where you have to fix something before continuing is bad in most cases; e.g., consider evil modal dialog boxes. Imagine a word processor that forced you to fix spelling mistakes before typing the next word!

The difference between a structure editor and a smart editor are mostly of ideology and technique. In the former case, ideology dictates that edits must be made in correct chunks where feedback and assistance are in the foreground, while in the latter case, ideology allows for free form editing with background feedback and assistance.
By technique, the former is an exercise in forward engineering (tree building) while the latter is an exercise in backward engineering (via compilation), which is definitely trickier than forward engineering. Smart editors are much more viable for real developers, even in the sorry state they are in today (e.g., Eclipse or Visual Studio). Can they converge? Could a structure editor be made to look like a smart editor? Sure, but then...its ideology has changed to that of a smart editor (in that it is allowing for free form editing). Not sure if Intentional Software is going to be able to climb over these obstacles (how much impact have they had???).

I actually know things can be better Java/C# support from my Scala plugin experience. Incremental parsing is an easy problem, you just memoize your parse trees from your regular batch parser and increase error recovery by tracking brace pairs (in a C-like language). Error recovery is very important in the incremental world: a parse error shouldn't destroy good parse information that were already computed. Incremental type checking involves more memoization and error recovery, but you can reuse your existing compiler if it is based on functional programming principles (i.e., well-modularized state). It is definitely tricky, and my biggest regret is not having enough time (one or two more years) to finish the work up to some level of robustness.

I think I was inviting you to drop the ideological distinction in favour of a functional characterisation, because ultimately it's how systems behave that matters, not the ideologies of their designers, and an ideological definition of what counts as a "structure editor" only ends up begging the question.

Perhaps. But I guess my point was that once your structure editor feels like a free form editor, is it still a structure editor? If we go purely by functional characterization, then the difference is in the tree building/processing approach (compilation vs. explicit construction).

Somebody needs to do usability study research to measure what the differences are.

People who use IDEs put up with a lot of b.s. and have high pain tolerances, though. Resharper...

But the usability of structure editors has been studied somewhat. They are great for beginners and horrible for everyone else because they stick you into a mode and force you to follow a certain order in program definition. IDEs surely are bad, but we use them and we miss them when we have to go back to something like Emacs (or at least many of us do).

I don't think there will be a comparison between a compilation-based smart editor and construction-based structure editor until there is a viable structure editor with which we can compare against. Few people go in that direction so....

Do you any references to studies examining the usability of structure editors?

No. As far as I know, no one has done a study that has scientifically measured the usability of structure editors for non-novice programmers. There is a study at CMU on structure editor viability for refactoring tasks, but I remember it wasn't related to writing new code.

As far as I can tell, the modal editing problem of structure editors was simply termed "the usability problem" when structured editing research was popular in the early 80s, I don't know whether anyone did any tests to validate the use of this term.

Here's some very relevant research. From the abstract:

A detailed study of Java programmers' text editing found that the full flexibility of unstructured text was not utilized for the vast majority of programmers' character-level edits. Rather, programmers used a small set of editing patterns to achieve their modifications, which accounted for all of the edits observed in the study. About two-thirds of the edits were of name and list structures and most edits preserved structure except for temporary omissions of delimiters. These findings inform the design of a new class of more flexible structured program editors that may avoid well-known usability problems of traditional structured editors, while providing more sophisticated support such as more universal code completion and smarter copy and paste.

Thanks for the heads up.

Design Requirements for More Flexible Structured Editors from a Study of Programmers’ Text Editing[PDF]

To what extent would you attributed the sluggishness of recent releases of IntelliJ IDEA to trying to make the unstructured approach work?

It just seems like these unstructured text IDEs are getting slower and slower as they do more ad-hoc things to text, both in analysis and synthesis.

Awhile back I bought some books on advanced pattern matching concepts to look into doing a sort of hybrid structured/unstructured editor. I never really got anywhere with it, because I realized it was a rabbit hole requiring a labor of love to get any results out of.

The problem with most smart editors is that they are not truly incremental: they work by silently reprocessing entire text buffers as fast as possible, which sometimes isn't fast enough. The Scala plugin was unique in the way that it was actually incremental at the tree level (both parsing and type checking, not every AST tree, but certain large-grained trees like classes and methods). Sadly, this was also its downfall, as it made certain assumptions about the compiler (no magical maps that record dependencies in order-sensitive ways) that maybe shouldn't have been made. But at least I know its possible...

The easy problem is incremental parsing, which is also the least important (re-parsing large buffers can be made fast) but is important if you want to do decent error recovery (so transient parse errors don't destroy good existing parse trees). Type checking also isn't that hard, there are some tricks with managing the symbol table (re-typing a tree, remove entries already entered the last time that tree was processed). Once you have incremental parsing and type checking, most of your important IDE features are easily implemented (intellisense, real time error and type feedback). Any feature beyond that...say advanced bug checking or what not requires the appropriate incremental algorithms. If no incremental algorithm exists (say for global refactoring), then we should use structured-editor like modal methods.

I spent a couple of years down the rabbit hole and even though the problems aren't easy, its definitely doable by a team of smart programmers within a reasonable amount of time (say 3 programmers @ 2 years could put out a kick-ass Scala plugin). I have no idea why Eclipse JDT and Visual Studio C# support are so lacking given the size of the teams involved. Perhaps the techniques used are just outmoded, they are re-using too much legacy code, and so on...I have no experience with IntelliJ, but my discussion with the developers suggests that they focus on tackling other problems.

Most smart editors actually use what's known by some text buffer editing afficionados as "the reduced document model" or "reduced model". It sounds like you are describing this approach. [Edit: This model can usually be optimized using Ropes data structures.]

Developing plug-ins for Visual Studio up until 2010 was very painful. 2010 is supposedly making it better but I've not given it a try. The secret sauce is MEF, which to me is no secret sauce at all, dumbing down what it is about it's basically an emacs style plug-in model with better engineering constructs (app domains, assemblies, then namespaces as opposed to "RMS-style") and crappier syntax. But the average guy can code VB.NET extensions and not use elisp.

Edit; And yes, I am pretty sure that if Visual Studio and Eclipse have crappy models for documents, then legacy code (i.e., third-party plug-ins) required for backwards compatibility will drag it down. At this point, many would refuse to upgrade to VSTS2010 if Resharper just died. In 2005, the SLOC figure for VS was 6 million plus. Hate to wonder what it is now. I know from reading the code and studying the models for NetBeans Schliemann and GSF projects that most people don't come up with good enough data structures, and thus code-dig themselves into mantle of the earth's crust.

[Edit: Ah, just found MobWrite via this Hacker News link. This is similar to what I had in mind, except my purpose wasn't collaborative editing.]

Or 东西 for those of us from the simplified world.

you'll have to install libpcre-ocaml-dev (if you're using debian)

What do you mean by "you definitely do not want to limit the user to constructs which already exist"?
If you're talking about an FFI, one exists, though currently undocumented. You can call functions written in O'Caml. The implementation was done using the Lazy module so that the function "if _ then _ else _" is defined as an external function.

As for the F-keys, I agree that they are a little far for the user. I originally had it set to alt-X (as you proposed). Unfortunately this didn't work on some keymaps. In the future I'll simply make it so that both work.

I think radial menus are more useful than dropdown lists, as an FYI

I have tried Eastwest (see below for instalation tips).
I have also read your blog entry.
I must say it's wrong that non-mouse support is lacking.
See the calculator demo, it's pretty apparent that the mouse keeps still.
Actually the keyboard support is excellent and you don't need mouse at all.
(that doesn't mean the usability is astounding, to judge it you have to test the real thing)

My deriv example could be a nice demo, unfortunately Eastwest doesn't accept immediate floats in patterns.
I hope Eastwest will improve to the point where at least some serious toy interpreters can be done.

I've introduced literal patterns into Eastwest version 0.1.3. Any token type (int, float, string, etc...) can have literal patterns. You might need to install the latest OSET.

I've encoded typed lambda calculus with type inference; thought you might be interested:

http://sites.google.com/site/rathereasy/eastwest/tutorial#TOC-Lambda-calculus-with-type-inference

Lambda calculus with gadt is a fanstatic demo.
I expected an example like that.
GADT are a really cool thing from the Haskell world that fit Eastwest like a glove because your environment is so much language-oriented.

About literal patterns, one problem is they rely on branches ordering, so one wants to be able to (re-)order branches.

Thanks for the feedback!
Eastwest is based on SDL. This is definitely not because I have a preference for SDL; rather, it was a last resort that finally made Eastwest work. This is why copy/paste is not possible at the moment and why inputting unicode is only possible if the character is on your keyboard. If someone writes an ocaml library to fetch the copy buffer then getting copy/paste would become trivial. Getting unicode input (through an IME), however, will require much more work.

I don't see how I can fix this bullet:
"once edited code blocks feel quite rigid, there's not much you can do except copy/move/delete"
seems like the nature of the beast

Everything else you mentioned is spot on and easily fixable. I'll post on this thread when it is done (shouldn't take too long). I don't know if Eastwest will ever be ready for "real world usage"; I just hope it can inspire someone to write something that will be.

The "insert unicode" menu option lets you display any of the unicode characters you mentioned

grab the oset source here:
svn checkout http://oset.googlecode.com/svn/trunk/ oset-read-only

then do a make reinstall. You'll then have to get the eastwest sources here:

svn checkout http://eastwest.googlecode.com/svn/trunk/ eastwest-read-only

both these commands are on the google code pages. It's largely untested, so feel free to send me an email if you find anything that's not right.

I have actually tested Eastwest r106 and emailed you a report.
Seems you did not received it.
I guess the skeptic audience is gone now so i can make it public.

The r106 update starts to realize the full Eastwest potential.
Unicode is a great addition that gives more cachet to your already syntax rich language.
I also discovered how much freedom when naming thing and how it challenges my usual naming conventions.

However, the more i test it the more i find things to be improved :

1. Too bad deleting/moving branches still doesn't work for me.
2. I miss higher order functions.
3. A quite annoying event is at page bottom when the popup menu is out of window. Certainly when the menu box can't fit the page bottom then it should popup in the opposite direction.
4. The popup command output can't be unfolded and seems pretty difficult to read even with a limited size language and example.

My output syntax test exemple is to input 3cos² (x²+1) that is derived as (it can't be unfolded) :

(-12) * x * sin x power 2 + (1) * cos x power 2 + (1)

sin x power 2 + (1) that sounds much like (sin x)² + 1 but actually is sin (x² + 1).
Thus your innovative syntax comes with a cost in the readibility department: it doesn't scale up, especially as one can't destructure it.

Anyway, it's still one of the most impressive technological demo i have seen. Thanks for your great work.

I love the call to replace >=, with ≥ 's.

Maybe someday someone will make a math or programmer's keyboard to mesh with it!

Most rich math programming environments like Maple and Mathematica allow you to enter key chords to generate math symbols, e.g. "replace >=, with ≥".

Fortress is the first general purpose programming language, though, to allow this.

Maple's implementation sucks, by the way, and has be fraught with bugs.