Hacker News new | comments | show | ask | jobs | submit login
Final “STEPS Toward the Reinvention of Programming” Paper [pdf] (vpri.org)
138 points by e12e on May 12, 2016 | hide | past | web | favorite | 64 comments

This is a strange paper. It reads a lot like "Personal Dynamic Media", Kay's paper from the 1970s, which led to the Alto and Smalltalk. Back then, this was all new. Now, it's not.

The big thing here seems to be defining domain-specific languages (they don't use that term) which allow certain classes of problems to be written concisely. The examples given of those language look rather conventional:

    selectionWatcher <- 
        DocEditor.selectedDocBox :b 
        this.textContents(if b then b.printString() else "")
Their approach to GUI programming:

        ^ KSSimpleLayout new
        keep: #topLeft  of: ’titleBar’ to: 0@0;
        keep: #right    of: ’titleBar’ to: #right offset: 0;
        keep: #height   of: ’titleBar’ to: 25;
These are constraints for a constraint engine, which is a good idea not original with them. But writing constraints as text is painful. You can do that sort of thing in CAD programs such as Autodesk Inventor from the GUI, and you get useful error messages when you overconstrain or underconstrain. That's how web page layout really ought to work.

They created about 100 domain-specific languages, and in each, the demo programs are short, because the languages are well-matched to the specific problem. But they didn't get to the point where they put users on these languages. That's needed to find out if they're as concise as claimed, or the users end up writing complex code to get around limitations of the language.

There are widely used domain-specific languages, such as Matlab and Excel. In each of those, stuff the language designer thought of is easy, and hard stuff is really ugly. That's what usually happens.

Not seeing the big breakthrough here.

The big breakthrough is making it easy to create new DSLs for any situation. Every area of the OS has its own language (and you can just add more if you feel the need) so that the whole OS including networking and GUI is very compact, understandable, and hackable. This particular project focused on compactness, just to prove that it is quantitatively more expressive.

I was studying Racket lately, and it sounds very familiar now. DSLs, or dialects as Racket calls them, is surely way to go and improve productivity, it should however, always be possible to descent down, or escape from that DSL, where needed, to avoid the hacks that work around a certain limitation of this or that DSL. (lisp macros, wink wink)

That sounds like Lisp to me. As someone who writes lots of Common Lisp code, this sounds exactly what I'm doing daily.

"But writing constraints as text is painful."

I find writing the anchors in QML (Qt Quick's layout language) to be quite pleasant and easy.


    Rectangle {
        Rectangle {
            id: a
            anchors.top: parent.top
            anchors.bottom: parent.bottom
            anchors.left: parent.left
            width: parent.width / 2
       Rectangle {
            anchors.top: parent.top
            anchors.bottom: parent.bottom
            anchors.left: a.right
            anchors.right: parent.right
The two most "interesting" parts of this are the width: parent.width / 2 and anchors.left: a.right

There is much much more, much of which makes it more concise, but that's the basics.

That's because you're a programmer, not a graphic designer.

Oh, I didn't realise the context was non programmers. My bad.

One of the demos of their research was a "A full TCP/IP stack in under 200 LoC" (2008), see https://news.ycombinator.com/item?id=846028 , Described in http://www.vpri.org/pdf/tr2007008_steps.pdf

It appears as an example in the cola source: https://github.com/robertpfeiffer/cola/tree/master/function/...

One of the key issues was that they started STEPS with the premise that they needed NSF funding for running the FONC project on super computers. This strategy is to "time travel" 10 years into the future, like Alan Kay did at Parc to develop the Alto.

In this last phase of the STEPS project, sub-systems like the graphics system were close to running fast enough on commodity hardware, that they changed course during this last phase, abandoning time sloted for design iterations and exploration, to focus on optimization instead.

And unless they were researching parallel programming, a supercomputer wouldn't run desktop GUI software any faster anyway. Maybe this wasn't obvious back in 2007.

I think they were looking at custom architectures implemented in FPGAs.

Im not usually an advocate of 'you need to hire a UX/UI person' but this really needs a good one. Its trying to show people a lot of different information and theres no graphical clarity to it at all. Worse it looks like the worst kind of interfaces from the early 1990s. Its painfully obvious nobody on the team has any graphic/visual background. I guess its just the difficulty of projects coming from a university/science/research basis where these things arent valued because they are hard to quantify.

> I guess its just the difficulty of projects coming from a university/science/research basis where these things arent valued because they are hard to quantify.

IMHO rather because in research projects at universities there is no position (in the sense that one can spend money on it) for people who aren't either researcher or administration. UX people surely have their importance but they neither bring research results nor they are a "necessary evil" (adminstration - which is no contradiction that good adminstration personal can be really helpful).

Well, there are HCI researchers who do design/UX/UI; more straight up design research in CS would be nice though.

I can't believe this group of incredibly smart people have produced this not-so-impressive paper. Sure, the size of source codes is a big problem. but is LOC the most cost-effective issue to investigate into? Why none of the existing module approaches work? Is this really a language problem can be magically solved by FPR? Can this 20k app handle Chinese characters? How many corner cases does it handle?

Abstraction leaks, and I don't believe in any silver bullet.

Is it the magical solution to all of life's problems? No. It is damn impressive. Yes.

Right now we live in a world where everything we do depends on multiple layers of 10s-100s of millions of lines of code each for the compilers, the operating systems, the browsers or platform libraries (ex Qt). It's physically impossible to read a significant amount of the code in any of these layers, much less understand it. Then we get to add in modules and libraries like Boost or Js-Framework-Melange-Of-The-Week and we don't even know how anything we are doing with the topmost platform level even works. We've gone from Fortran to this in 60 years. What is this going to look like in another 60 years?

An alternative future is something like Nile. Reading Nile's code requires some up-front study. That sounds like work compared to "I can look at a for-loop in any package and know instantly that it is for-looping er... something... for some reason..." But, it's the kind of up-front study that is reasonable for a smart high schooler to pull off. With reasonable effort, that kid could understand literally every character of the Nile source and start making major, sweeping modifications. Contrast that with Cairo --which at a high level is not much more complex than Nile, but I'll be damned if anyone but it's maintainers can claim to understand every line and make major changes.

Spot on. That's the whole point. The closest thing I've seen to this in something even near a mainstream language is REBOL/RED projects. They're sending whole apps that fit on floppies using DSL-based methods while majority are rendering web pages & doing basic libraries in mere megabytes. (!?) Keeps growing and how could we possibly handle it?

Good to see some work in a different direction.

> kid could understand literally every character of the Nile source and start making major, sweeping modification

This also improves security: auditing correctness and writing mandatory access control policies in another DSL.

In 60 years the software will write itself


That's what they thought a couple of decades ago too. I've heard of some research into programming languages decades ago not getting funded because "in a few years we won't need programming languages anyway". It might be true this time, but it might not.

Ok, but progress is progress. What does it matter what happened 20 years ago?

It's not "an app". It's an Operating System that runs on bare hardware, and the applications one would need. It aims to do the useful work that a word processor, DTP program, drawing program, web browser and the file system, drivers, rendering sub-system, networking stack and much more does. All in ~20kLOC.

I seem to recall they support full unicode, by the way (which makes sense today, there's not many good reason to not try for full utf-8 compliance unless you want to do some entirely different encoding (like a simpler, prefix-based one) and then do conversion at the edges of your system)).

Like in my other reply I make a strong demand for reproduce able science.

Where is the integration build of frank? Just one binary with source that work, alan kay did run some demos on a mac. Its too bad that this great software is now starving on some researcher archives :(

I call for reproducible science:


Where is the CI Server of the project? It can't be that hard.

You're looking at the cleaned up final summary report to the funder of a research project. There isn't any CI. This wasn't a project to build a system. This was research to explore the possibility that operating system and application software can be radically simpler than it is today. Over a number of years they investigated many different systems which addressed aspects of the problem, wrote papers about them and yes made source codes and other artifacts available. It's (mostly) all here http://www.vpri.org/html/writings.php, http://tinlizzie.org, and http://tinlizzie.org/dbjr/. So no, CI is not that hard. It's also not what they were paid to do.

It's not about LOC being cost-effective, it's about orthogonality. When you're gaining knowledge about something, you're expanding your data set. When you're getting wisdom(understanding) about something, you're contracting it.

Everything that we're doing currently points to a huge scattering of knowledge but little-to-no understanding. So that's what Alan was shooting for: trying to express everything with as little as possible.

The reason we can't do it yet is that, while we think we know what we're doing, we still don't understand what we're doing.

You may not believe in a silver bullet but very smart people believe we can do vastly better. I think you may agree that we need to at least try.

Thank you very much for the explanation. I think I get the point but remain skeptical. Is knowledge (even a totally man-made subdomain like OS/App) fundamentally scattered in nature, or can be modelled in the scale of 0.1% of the original size?

It's kind of odd that Alan Kay, the visionary of DynaBook, who advocates the importance of exchanging of ideas, has the belief that a single man should be able to handle thing of the scale of industry. Karl Max believes in social labour division, and I think he is right.

I think Kay believes that the scale of our current industries are a lot smaller than they could be. That the reason that they currently require us to divide our labour so extremely is incidental complexity we have built for ourselves in 60 years of small, short-sighted steps. If we could slow down and think about how to simplify what we are doing, each person should be able to handle large chunks of our current industries and together we could move on to more interesting things. Instead of struggling to reproduce the functionality of a WYSIWYG document editor from the 90s in HTML5, maybe we could move on to more easily create new classes of software that do not resemble what came before.

Agreed, except I think you mean from the 70's. PARC invented WYSIWYG word processing, I think it was Butler Lampson's gig. As I recall that went out to users before many of their other inventions.

As you know three sub-atomic particles (electrons, protons and neutrons) give us the 118 elements which construct everything. All hardware can be founded on a single NAND gate. I think he's looking for that kind of fundamental core to software -- and it's missing.

I am personally quite sure that software construction will one day be a form of mathematics with symmetry being found in everything from biology and neurology to physics.

As promised, here's one that creates a theory for programs that can be used in practical ways:




If doing the first in Scheme, methods like this tie it to hardware:


yes, I got your point but consider this: there are only 26 English characters yet I can't finish Ulysses.

That's funny. OK, I get your point as well.

My only counter might be that Ulysses is a monumental work of art. We don't have anything like that in software -- and not just because we don't have a Joyce. We lack that standardized alphabet. That we compile/interpret programs, that we have a completely different language for data access, that we have in-memory data structures, I could go on and on -- it's all getting in our way from creating something monumental. (I feel like I'm cheating a bit; I've seen the other side and it's beautiful.)

Whaaaaat?? Just a NAND gate? Nah, hardware is done on a combination of standard cell library, RAM, ROM/flash, and analog components. You can't even get the volatage right with just a NAND gate.

Far as symmetry, there's potential there given some work is reducing it to math and simple constructs. Hardware too. Ill try to rrmember to give you a link when I'm off work.

When just about any system starts its lifecycle, it can fit within the brain of 1 or a few people. As the system grows, new people come in and start working on just one tiny piece. Each of those pieces then grows until it strains the limits of the person or people working on it, and usually is broken into further pieces, or has new parts built on top of it.

As this process unfolds, what once was a simple system that could be fully understood and reliably reasoned about balloons into a monstrosity with 20 layers and thousands of complicated moving parts which no person has any hope of reasoning about fully. The abstractions start “leaking” because the people working on them have gaps in understanding which leads to interface mismatches all over the place, and all kinds of bugs and other software flaws.

But in general, most of the complexity is incidental, created out of the goop of the program itself and the institutional structures of the programmers working on it rather than the inherent challenges of the problems it tackles.

Alan Kay’s idea is: what if we focus really really hard on cutting that complexity down, and spend years of disciplined effort simplifying our abstractions until a full usable computer system can have its source code printed at normal size in one medium-length book, instead of needing a whole library of books. Maybe such a system wouldn’t be used “in production”, day to day, but it might inspire us to simplify and refactor our foundations elsewhere.

According to your description, the root cause of the complexity is head count and lack of communication, which I respectfully disagree. Most of the web apps have the `User` class and it does more or less same thing. I challenge this world to provide a single solution makes everyone happy. Complexity comes from specific use cases, and they are not incidents.

OK, let's say you are right, and Alan Kay has come up with a 20 kLOC functional system. Everyone starts to coding on it and quickly produce 100+ distributions and millions of Apps. Surprise, the old problem comes back!

It's an ecosystem/social/management problem that is about human, not technology.

It's not the same Scale of problem.

When you have reduced what took 200 million LOC (win + office) to 20k.

Everybody would need to write 10s of thousands of apps to be in the same mess we are in, not hundreds.

This is Alan Kay and other computer scientists having a bit of an academic wank. It says up at the top that this work is not intended to replace conventional operating systems and applications, but to speculate.

Old-school coders lament that the last completely understandable computer was some model by Commodore -- the C64 or Amiga, depending on whom you ask. Computers used to ship with complete schematic diagrams and enough documentation that you could know what every byte of system code did and where every I/O register was and what they did. These days, not so much -- before the massive, proprietary OS kernel even gets loaded there are many hardware and firmware interfaces to be navigated, many of them protected by patent IP laws and only available under NDA, if at all.

The intent of the STEPS paper is to explore possible answers to the question "how powerful a system can we build with modern tech, that is still completely comprehensible by a single person?"

I have kind of big issues with the results from the research. Sure they always say: ok its just research we don't mind if its not "finished".

But: where is the source? Some sub systems sources are available (Nile,Gezira,Cola, Ometa..). But the state of the projects does vary strongly.

Also for such a system you need something that works, you need continues integration.

You need reproducible science.

where is a reproducible build of the "frank" system that STEPS did create?

reproducible science and build should NOT be a big problem IMO.


This effort, and many previous ones lack of dramatic results, highlight the fact that reinventing programming is very difficult. The human mind is not very well equipped for computer programming. So it seems that the real programming revolution, will come when artificial intelligence becomes capable enough to do the programming by itself. Based on natural human language descriptions, or completely from the machine initiative. Probably that time is not too far off.

As an interesting note to this, my personal take on the matter is not to reinvent programming, that is too hard. But to reinforce it with a graphical user interface. A programming GUI will simplify programming in a similar way that an icon based file manager simplifies file manipulation. The main benefit is to free users from having to memorize textual command patterns. I haven't done a good job of explaining my vision of it, but here it is anyway: https://nzonbi.github.io/xoL/

> The human mind is not very well equipped for computer programming

That may be the case on average, but I know of at least one counterexample for certain.

I think you are probably correct in your first paragraph although I think it will take quite a while until we get to AI good enough that it could develop new systems autonomously.

Software development is a hard problem. Even a small system or ruleset easily explodes into incomprehensible complexity, a phenomenon called emergence.

There is also a certain fragility in how computers and computer programs work. Even the slightest error or failure can stop a system completely.

But then you lost me.

I do not think that graphical programming is the future. Next to nothing of the essential complexity of developing anything, from small algorithms to large systems, comes from the syntax, although it can contribute to the accidental complexity, together with the used tools, lack of time, and other factors.

Replacing a formal written language with symbols or flowchars have been tried and retried, and it never really took off. I believe there are good reason for this, and one of them is that you can not simplify a complex problem by using a tool that has less power - or expressiveness. These tools typically make simple problems simpler and harder problems next to impossible.

An other problem is that visual tools, and especially flow charts based tools, actually tends to be harder to comprehend when the graphs and visualisations are getting larger, compared to their equivalent textual representation.

Anyway, while selecting a good language is important and can improve or reduce the accidental complexity, the accidental complexity is just a small fraction compared to the essential complexity in larger systems, as argued by Fred Brooks in 1975.

But I agree that graphical symbols and drawings, pictograms and other visual elements could possibly enhance the readability and comprehension of written text, just as a small graph can help in natural language texts.

But then it is perhaps more along the lines of Knuths literate programming ideas, where the program is also the documentation. Knuth didn't quite made it right though as described here: http://akkartik.name/post/literate-programming . Not really his fault as he tries to build on top of existing languages, and just about all of them have have a rather backwards structure for technical reasons.

However, that link also quotes Fred Brooks and this nugget of wizdom from 1975. (or is it -85.)

    “Show me your flowcharts [code] and conceal your tables [data types],
    and I shall continue to be mystified.
    Show me your tables, and I won’t usually need your flowcharts;
    they’ll be obvious."
In other words the data types are the main characters in the narrative.

To sum up: The essential complexity is more or less impossible to get at, at least without AI (but then it just exists but we can spend more artificial brainpower on it while we are slacking off - and hope we are not killed and used as raw material for neural compute machines somewhere in the process.)

The accidental complexity on the other hand could possibly be reduced with better languages and editors that formats and displays the code in the most visual effective way for our poor minds, and I'm all for editors were the comments would be nicely typeset and where I could insert images and graphs, and also all other visual improvements that could enhance our awareness of the global structures.

I think there are two sound approaches to communicating complex systems between humans (which is the main goal here, a computer might be a bit slow compiling 200M LOC - but the real problem is that no human can read that much code, let alone understand it): 1) Write documentation that is also code. That is the idea of literate programming. I recently came across:

"Literate Programming in the Large": https://m.youtube.com/watch?v=Av0PQDVTP4A

which is a bit of a wandering talk, but well worth watching: it talks about real, huge comolex systems, and how lp can help bring them back under control.

2) The other approach is to shift your perspective, so you don't have a complex solution to a compkex problem; but rather a few small and lightly connected straight forward solutions to simple problems. Now I doesn't matter if you're bad at communicating, because the ideas you try to convey are simple ideas.

I think there are a few reason that STEPS appear to work: what we're doing with our complex software is simple stuff. If we know what we want to do (the hard part) doing so in a straightforward way becomes easy. If we can make hierarchies of abstraction and isolated sub-systems.

Note that simple doesn't mean trivial. These solution often require quite a lot of theoretical education; but not an unreasonable amount.

Another project that seem to argue for better abstractions, is clasp, and it's use for (among other things) refactoring c++:

"Clasp: Common Lisp using LLVM and C++ for Molecular Metaprogramming": https://www.youtube.com/watch?v=8X69_42Mj-g

"Using Common Lisp to refactor C++": https://www.youtube.com/watch?v=h31pURzgYX8

"Clasp — Bringing Common Lisp and C++ Together": https://github.com/drmeister/clasp

LOC correlates to complexity, and they reduced it by 1000x. Complexity kills progress. We made progress in physics when Maxwell's equations elegantly simplified enormously important phenomena. They're trying to find that simplification for software.

I think they are on the wrong track of simplification. In this industry, simplification does not come from elegant abstraction, technology or deep thinking, but obsoletion and concentration. When I first touched Internet, there were 6 protocols and now only 1 survived.

I think it is absurd to think that the paper is not impressive. The rendered output shows no sign of corners being cut - it is nicely laid out and has well made graphics. It's about as good as TeX output, and the system is doing far more work to get to the point where it can render. The same size team and schedule with a more conventional approach might make something like Word in a similar amount of time, but without the underlying flexibility.

ozten[2] wrote:

"Last week VPRI[1] published the final "STEPS Toward the Reinvention of Programming" paper[this submssion].

Although it is 2012, it had been unavailable publicly until now. A great way to catch up on how FONC ended. It was worked on by many individuals being cited as part of HARC.

[1] http://vpri.org/html/writings.php

[2] https://news.ycombinator.com/item?id=11680238

Sorry but its 2016, publishing a paper is not enough. Alan kay of all should now we need more , we need:

The three/four pillars of reproducible research

Often in the discussions around open and reproducible science we focus three main types of research products

1. the paper: the traditional narrative document, often 2. the data: increasingly appreciated as a first-class citizen of scientific record with data repositories providing DOIs 3. the code: recognized as a research product, but the last to be integrated into literature system and given DOI

4. the environment: a critical and under-appreciated ingredient for computational reproducibility

THAT should be the minimum for all science projects IMHO. What do you think?

I'd love to see full sources and build system that allowed everyone to play with Frank. I was sure I'd made a comment to that effect somewhere, but I can't find it now, perhaps it was eaten by my outdated smart phone.

On the other hand, I believe the paper(s) might very well be more important: exploring the ideas. I think it's a difference between a research project in computer science, and an engineering project. The first lambda calculus was just a project - they thought they'd need years to get the thing running. And then someone just coded up eval() in machine-code and they were bootstrapped.

I to want the implementation of eval(), but I'm not unhappy that they've shared their ideas.

For me, they ran before they could walk. Anything graphics-related could wait (although Nile is awesome, so they're forgiven). It feels like they were focused on trying to sell their findings rather than just focusing on research.

But I'm a huge fan of everyone involved in this, so that's not criticism -- just speculation.

I suggest people to walk the fonc mailing list, lots of old threads with smart people discussing interesting ideas.

I'm curious how much of the code base will be publicly available. It would be great to try this stuff out.

One portion, Nile, is available on github:


See also Ometa:




And Cola:


Some more links on the WP page for VPRI: https://en.wikipedia.org/wiki/Viewpoints_Research_Institute

And VPRI's own wiki:


As far as I've been able to gather, the most immediately useful stuff, is the ideas and concepts in OMeta, as well as the various implementations of OMeta.

Ometa is amazing. Ohm, the successor is even better.

I believe that's: https://github.com/cdglabs/ohm ? I see I've starred it at some point, but can't remember really looking at it. But if it's a refined/improved OMeta, it would indeed be interesting. Thanks for the reminder.

That's the one.

AFAIK the part I'm the most interested with the "word processor" (Frank) isn't available, which I find very annoying: this is a programming research project yet the programs aren't available!

A publicly funded one, no less.

They aren't terribly well organized and their stuff is mostly tinker toys but I think you might find some interesting things about Dynabook Jr (Frank) here http://tinlizzie.org/dbjr/

I hear APL is concise.

You know what else was concise for UI? HTML.

... but people wanted their rounded corners.

... so now it's not concise.

A relevant lecture from Alan Kay:


Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact