Tree Oriented Programming [pdf] | Hacker News Reader

Tree Oriented Programming [pdf]

foswiki.cs.uu.nl

118 pointsbreck26 comments

This slide deck is incredible. Slide 8 "Language evolution" compares LISP vs Haskell to a rotary telephone vs a cell phone, then the next 80 code-packed slides are spent re-inventing s-expressions, but more verbose and harder to use.

I have never seen a gloriously snarky, incredibly accurate, incredibly concise synopsis of something before. This comment should be chiseled in stone and buried for future post-nuke earthlings, so they will know just how capable we used to be.

Thank you

On the slides for quick-sort, the author asks:

> Why don’t they teach it like that in the algorithms course?)

I'm sure they do sometimes. However, it is incorrect because quick-sort is an O(nlogn) in-place sort. This is a best-case O(n^2) sort (due to the linked-list appending) and is not in-place. If you got taught this as quick-sort ask for a refund... ;)

---

Honestly, there's isn't anything very interesting in these slides assuming you already know basic functional programming. The dissing of Lisp was odd given the functionality of Haskell that was used was approximately the intersection of Haskell and whichever-Lisp, plus basic static typing (which you can get in various Lisps as well: https://docs.racket-lang.org/ts-guide/ )

Quicksort is actually O(n^2) in degenerate cases but as you note its expected to operate in-place. Proper in-place algos written in Haskell read like the imperative versions. This sort code made it into FP lore as a quicksort equivalent which it isn't. It's just neat.

In this case it is not clear the author intended to claim their code has quicksort properties. The "why don't they" question at the bottom could be read as "Or is it quick-sort?" Hey I'm being generous because reading just the slides is bound to miss subtext.

Yeah, I wasn't being very generous. However, naming the function "qsort" is pretty dishonest. I agree that the proper quick-sort implementation is going to look pretty imperative (and involve mutation) which is why I get a bit annoyed at fake-quick-sort being used to demo how pretty FP makes your code...

(I agree that this implementation is neat. I think it's a great way to explain sorting.)

(naive qsort is O(n^2) in the worst case (with pivot selection it is Theta(nlogn), though,) but the functional-linked-list-sort is O(n^2) in all cases... :))

This is still an expected O(nlogn) sort though not in-place as appending only need O(n) time.

It isn't. Perhaps you're missing the recursion (which, at each step, does two of those list appends.)

Write this algorithm in an imperative language and it'll pretty clear that this is best/expected case O(n^2).

It doesn't matter that it's two list appends, 2*O(n) is still O(n).

Suppose the length of (qsort (filter (<x) xs)) is k. Then the time to do the two appends in (qsort (filter (<x) xs)) ++ [x] ++ (qsort (filter (>=x) xs)) is k + (k+1), which is linear in k.

At the same time any quicksort (even an in-place one) will scan through the entire array once in order to partition it, which also takes linear time. (It will take time proportional to the length of the entire array, not just the first half.) The extra work from the appends only changes the constant factors, not the asymptotics.

Anyone interested in this might also look into "term-rewriting" languages used similarly. Long line of research exists in that.

https://en.wikipedia.org/wiki/Refal

https://en.wikipedia.org/wiki/TXL_(programming_language)

http://strategoxt.org/

https://en.wikipedia.org/wiki/DMS_Software_Reengineering_Too...

And my all time fave -- https://en.wikipedia.org/wiki/L-system

I remember running into that studying Artificial Life. It was neat how the simple rules let drawings of plants emerge. Really mind-blowing.

https://en.wikipedia.org/wiki/Artificial_life

OMeta can also be used to define tree transformers, and may be of interest too.

http://www.tinlizzie.org/ometa/

I am quite interested to hear if anybody has any thoughts on the work of Valentin Turchin, the author of Refal.

In an interview [1] conducted by Joe Armstrong, Alan Kay traced some of the key ideas of Erlang and Smalltalk to early papers by John McCarthy (Advice Taker), Carl Hewitt (Planner), Simula, and other work (including META 2, which apparently inspired OMeta). The theme here seems to be a favorite of Kay's: "late binding of meaning" used to build systems that scale just as well as biology.

In his interview, Kay mentions Minsky's Computation: Finite and Infinite Machines, which discusses various models of computation.

Now, Alan Kay has long looked to biology for hints on how to scale. (For example, in the interview I mentioned, he says that a computer is a "universal atom of meaning".)

I mention all this because what I am reading of Valentin Turchin [2] is making me very tempted to add (English) expositions of his work alongside my reading of Minksy's Computation. Specifically, Turchin's work on Supercompilation [3,4], which seems to draw upon a tradition of cybernetics [5], seems to me to be in somewhat of the same spirit as that of Kay's, at least when you consider that the influence of cybernetics largely means that we take cues from biology and attach meaning to existing patterns in nature and technology alike in our endeavors to replicate its success (and of course couple our constructions with them in feedback loops, as in the elecrical engineering that largely inspired cybernetics). Turchin appears to be a key figure [6] in the Principia Cybernetica project. (Whereas Kay appears to be more influenced by North American McLuhan and the Pragmatist traditions in philosophy and psychology, Turchin seems to come from a more European tradition of cybernetics. Both traditions seem to be scratching the same itch, though, especially when it comes to biologically inspired notions of computation and meaning.)

Seeing that so much of Turchin's work took place in Russia, and was only understood in the West many years later, I would be interested to hear what people make of it. Simon-Peyton Jones is quoted in [4] as surmising Supercompilation to be a "ball of mud", in which understanding anything at all required understanding the entire thing.

(Ben Goertzel, listed as a co-author of the 2002 paper on supercompilation [3], has made further remarks about Principia Cybernetica web on his website [7].)

[1] https://www.youtube.com/watch?v=fhOHn9TClXY

[2] http://pespmc1.vub.ac.be/TURCHIN.html

[3] http://goertzel.org/papers/SupercompilingJavaMay2002.htm

[4] https://themonadreader.files.wordpress.com/2014/04/super-fin...

[5] http://pespmc1.vub.ac.be/DEFAULT.html

[6] http://pespmc1.vub.ac.be/BOARD.html

[7] http://www.goertzel.org/benzine/PrincipiaCybernetica.htm

To generalize this beyond programming languages parsing. That's basically what Model-Driven Engineering boils down to.

You take a model, transform to another model (if you need to), then use it to generate stuff (basically reports and/or code).

A model is just a tree that respects a set of structural properties (the metamodel), just like a program is a text file that respects a grammar.

This should be nice and clean, but it's been just a few months since I started meddling with MDE (because academia) and it seems bloated beyond salvation. Maybe we could take the good parts and rehash them in a functional setting.

I came up with a pretty simple way of doing what I believe is the same thing that you're describing. The approach I take is to represent 'program models' as paths through the 'metamodel', which is a graph of 'program constructs'. So program models just end up being nested lists of numbered graph edges. http://westoncb.blogspot.com/2015/06/how-to-make-view-indepe...

I haven't tried an implementation yet, but probably will at some point this year. Would be curious if you had any comments!

I just read a good chunk of your article.

Could you give an idea of what the graph and interface would look like if the language we want to write in is Lisp?

It is indeed very string that we've settled on character based editors for making programs.

That was an interesting read :)

There are lots of similarities between what you describe and the Model-Driven approach I was talking about, except that the latter aims to be much more generic.

Indeed, if you go ahead with the implementation, my suggestion is: take a look at what you've found about the program graph, and see what you could generalize to _any_ graph of that kind.

And by the way, you could even be able to describe the structure of all such graphs (made of entities, atoms and edges with cardinalities) as a graph.

If you want to check previous work in the Model-Driven field, look for:

* Eclipse Modeling Framework (EMF); * Ecore, a language to describe metamodels; * OCL, a different language that can be used to add constraints to an EMF metamodel.

While I was writing this, I came up with a question re:your graph structure. Java and Python allow for inner classes (ie. a class definition inside another class), and Python also allows for nested functions. Can a graph such as those in your article describe self-containing constructs?

I'm detained for now, but if you check back tomorrow I'll reply to this.

First off, thanks for taking the time to read and reply—I appreciate it.

> take a look at what you've found about the program graph, and see what you could generalize to _any_ graph of that kind.

This sounds interesting to me, but I may be missing something. I've taken a brief look at EMF and Ecore, and it sounds like Ecore has done this generalization you speak of.

The counterpart to this shows up in a somewhat odd way in my project: if I've been correct so far on the role of Ecore, the analog in my system would sort of be the definition of EBNF grammars (since grammars are analogs of metamodels and EBNF defines what valid grammars are).

This was a somewhat arbitrary choice on my part, and to be honest I haven't thought very much about what should constitute this meta-metamodel (i.e. the Ecore analog). What I do at the moment is parse EBNF grammars and use knowledge of their semantics to form a graph representing relationships between rules which refer to one another. The nice thing about this is I can take any existing EBNF grammar (in the ANTRL format), automatically parse it and get one of these graphs (because when I was originally doing this it was just to make a new kind of general purpose program editor; not new kinds of languages).

I believe this implies an answer to your question also:

> Can a graph such as those in your article describe self-containing constructs?

Yes. I have actually generated a graph for the Java language and wrote a little program that automatically walks around it, following the restrictions of these operators * , ?, and + to determine when it must follow an edge, or only optionally etc. —and since Java has nested classes, there's a kind of construction proof here.

Back to "see what you could generalize to _any_ graph of that kind." —thanks for the suggestion. This does seem like an interesting thing to consider, rather than borrowing my somewhat ad hoc carryover choice of parsed EBNF grammars ;)

> you could even be able to describe the structure of all such graphs (made of entities, atoms and edges with cardinalities) as a graph.

I have a suspicion that's somewhat on the lines of what I would do. My guess at the meta-metamodel is: any graph with edges having cardinalities, and optionally having associated ?, * , and + operators.

Also, to clarify about the self-containing constructs: they just end up being cyclic sections in the graph. For instance, in Java we start with a node for classDeclaration, and the path to an inner class looks like classBody -> classBodyDeclaration -> memberDeclaration -> classDeclaration. (That's using this grammar for java: https://github.com/antlr/grammars-v4/blob/master/java/Java.g...)

We created and successfully use http://nianiolang.org for this type of tasks. Higher order functions intoduced more problems in the transform phase for our use cases (transforming complex application state of https://instadb.com). Imperative syntax works well with strict value passing semantics.

AST-based editor: https://medium.com/cirru-project/stack-editor-programming-by...

From the title I thought it might have been

http://strlen.com/aardappel-language "which computes by concurrently reducing trees (using a form of tree-rewriting) which sit together in tree-spaces (bags) and communicate amongst eachother (exchanging parts of themselves, in Linda-like fashion"

Many problems in the real world aren't like that, but like this:

[ messy input data with no formal grammar ] --process--> [ output text ]

That was a big part of the original motivation for TXR.

That flip phone makes me think this is about 15 years old? No date on it though, anyone have any more information?

2006.

http://foswiki.cs.uu.nl/foswiki/Swierstra/ResearchTalks

Reply on news.ycombinator.com