Hacker News new | comments | show | ask | jobs | submit | lukehutch's comments login

Favorite quote: "While that build runs, we have time to think."

-----


That reminds me of a story that I read ages ago. It happened in the 1980s.

This group of programmers had taken to exercising while waiting for compiles. They were all buff. Then Turbo Pascal came out and they all turned back into couch potatoes. :-)

-----


Exercise. That's what I'm supposed to be doing while Maven downloads the Internet.

-----


Then C become widespread and they became fit again! :)

I really miss Turbo Pascal compile times.

-----


Ah, I remember my first job, where I worked on a huge, legacy C++ project. My first day of work was spent building and fixing linker errors. After that, to test it, I rebuilt everything from scratch, and it took about that long, 30-45 minutes. While waiting for it to build, I wrote my own PHP time tracking system (click when I got in, click again when I went home). Ironically, wasting a day on compiling caused me to save hours worth of work keeping track of hours.

-----


Some good ideas -- have you looked at Dryad?

-----


This is only intended to be an optimal solution to the problem of building highly parallel data manipulation pipelines.

-----


Yes, I have come across now fewer than five programming languages called Flow since posting the Flow Manifesto. It already has a new name, but the new name and info about the new directions of the project haven't been posted publicly yet.

-----


Right, a loop is a morphism (or sub-lattice) from the state of loop variables at the beginning of a loop iteration to the state of loop variables in the next iteration. Iteration represents unrolling copies of the loop body sub-lattice in a linear string until termination. Recursion represents expanding sub-lattices inside sub-lattices until termination.

-----


Variable assignment is not strictly necessary, what is necessary is that one loop iteration can modify the initial state of variables in the next loop iteration. This is the second alternative to setting the current value of a variable presented in Flow (specifically, recurrence relations, e.g. x' = x + 1, which are syntactic sugar but allow "variable assignment" but only allow assignment to variables accessible in the next loop iteration). So the Flow Manifesto doesn't cover the hole in the Böhm-Jacopini theorem specifically, but that doesn't mean this computational model is not Turing complete.

As far as proofs or working implementation, sometimes life gets in the way of progress :-)

-----


What specifically is wrong with the definition of a lattice?

-----


You state that:

A lattice is a partial ordering with a single unique "top element" (least upper bound) and a single unique "bottom element" (greatest lower bound). Every node in the lattice is reachable by following some directed path from the single least upper bound, and there is a directed path from every node in the lattice to the single least lower bound.

A lattice is a poset where binary joins and meets exist. You define a bounded poset not a lattice. In general a lattice need not have either a top element or a bottom element, although all finite lattices are complete and thus do have top and bottom elements. The second sentence is also redundant, because for any element x of a lattice x ≤ ⊤, so why talk about paths?

-----


Cyaegha: Since we're talking about graphs generated from source code, they will always be finite. These are not abstract infinite mathematical objects. All finite lattices are posets, but not all finite posets are lattices, so I stand by the usage. And "Program lattice" sounds a heck of a lot better than "program bounded poset" :-)

The second sentence is intended to be redundant, it gives further explanation as to the implications of the first sentence. (This doc was never intended to be a tight mathematical definition, only to give a quick introduction to the concepts, with links to the strict mathematical definitions.)

The reality is that the lattice or bounded poset formulation is only needed to understand that the specific language constraints described ensure that the dependency graph of any valid program can be statically determined to be a partial ordering. The compiler doesn't even need to build a DAG internally, it just needs to ensure the specific language constraints described are in place, and as a result, the language will be able to be parallelized in any manner consistent with the partial ordering of data dependencies.

-----


All finite lattices are posets, but not all finite posets are lattices, so I stand by the usage.

Yes obviously, but nowhere is it clear that you actually have a lattice of any kind. Specifically, I see no reason why pruning DAGs of unused computations would yield a lattice, and this is a result you seem to rely on. Program lattice does indeed sound nicer than program bounded poset, but I would be more wary about misusing terminology than having a nice name! :)

-----


The least upper bound can be thought of as a virtual node consisting of the set of static constants (and the set of all inputs) fed into the rest of the lattice. The greatest lower bound is a virtual node consisting of the set of final output values that are "used" (written to an output file or database). If an intermediate value is computed but is not referenced anywhere, the data dependency DAG has a local lower bound node that is not connected to the greatest lower bound since the value is not written anywhere. If these unused nodes are pruned away, the result is a lattice.

-----


For that construction to work, these 'virtual' nodes need to exist in the poset. Your poset is just the vertex set of your DAG ordered by reachability, so they don't exist. I think your intuition is good, but the mathematics just doesn't add up. Perhaps you should look into things like trace monoids, pomsets and petri nets?

Please understand that I'm not trying to be mean here. You mention you've been applying for grants to work on this, but if you don't explain the mathematics adequately or demonstrate how it differs from existing formalisms then I imagine people are just going to reject you instantly. I would suggest seriously trying to formalise some of this stuff in a proof assistant like Coq. That'll quickly tell you if your theory works or not.

-----


I'm not the OP but I'm the blog owner. Whoever posted the link posted the mobile link, and blogger.com has re-formatted the image to maximum width... not sure how to fix it, but I'll take a look :-)

-----


Fair enough. I didn't mean to be a sour puss--I was just surprised by the situation.

-----


Applications are open for YC Summer 2016

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

Search: