Esoteric programming paradigms

Could you clarify which algorithm you're referring to? Or name an example algorithm that works in the way you describe? What I find in academic literature seems to characterize Integer Programming as a search problem. See the following article that compares Constraint Programming with Integer Programming:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

> Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview of tree search as a technique for finding feasible solutions to mathematical models.

> Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. [...]

> One particularly well-developed solution technique, called branch and bound, was introduced by Land and Doig. Branch and bound is frequently used to find solutions to integer programming problems; it is a tree search procedure in which a bound on the optimal value to each subproblem is obtained by solving a relaxation. In this thesis we assume the use of a linear programming relaxation in the branch and bound tree.

> The last piece of a branch and bound algorithm is a search strategy specifying the order in which to explore nodes of the tree. Depth-first search can be used to save memory in a branch and bound tree, since we must only remember the difference in solution between two successive nodes of the search tree.

Chapter nine of Applied Mathematical Programming from MIT classifies integer program solvers into three major groups:

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

> Whereas the simplex method is effective for solving linear programs, there is no single technique for solving integer programs. Instead, a number of procedures have been developed, and the performance of any particular technique appears to be highly problem-dependent. Methods to date can be classified broadly as following one of three approaches:

> i) enumeration techniques, including the branch-and-bound procedure;

> ii) cutting-plane techniques; and

> iii) group-theoretic techniques. [...]

> Branch-and-bound is essentially a strategy of ‘‘divide and conquer.’’ The idea is to partition the feasible region into more manageable subdivisions and then, if required, to further partition the subdivisions. In general, there are a number of ways to divide the feasible region, and as a consequence there are a number of branch-and-bound algorithms.

> An integer linear program is a linear program further constrained by the integrality restrictions. Thus, in a maximization problem, the value of the objective function, at the linear-program optimum, will always be an upper bound on the optimal integer-programming objective. In addition, any integer feasible point is always a lower bound on the optimal linear-program objective value. The idea of branch-and-bound is to utilize these observations to systematically subdivide the linear programming feasible region and make assessments of the integer-programming problem based upon these subdivisions.

The book describes the "cutting-plane" approach, which does seem to work more like how you're describing (a series of transformations), but also says:

> In practice, the branch-and-bound procedures almost always outperform the cutting-plane algorithm. Nevertheless, the algorithm has been important to the evolution of integer programming. Historically, it was the first algorithm developed for integer programming that could be proved to converge in a finite number of steps. In addition, even though the algorithm generally is considered to be very inefficient, it has provided insights into integer programming that have led to other, more efficient, algorithms.

As I mentioned elsewhere, it has been ages since I took an actual formal exam on Linear Programming (and Integer Programming) - since then I always used dedicated sw to solve LP (there is for example a nice, self-contained LP solver in Numerical Recipes in C) and so I always focused more on how to describe the problems in terms of linear constraints.

"In my mind" it works like this: https://www.quora.com/What-is-the-difference-between-integer...

Having said this, while NP is guaranteed to terminate the actual computation time may take ages. Integer Programming may very well leverage the fact that the solution is restricted to integer values and apply different, faster algorithm to exploit this property - including search trees. But in the most general sense you do not need a search tree or backtracking for Linear Programming.

I'd agree that "persistent by default" is an unusual and interesting approach, that would be suitable for the list of paradigms that may "change the way you code".

It reminds me of a statement I read about managing application state, to treat the state (in this case a Redux store) as an "in-memory database". Add a layer to load/persist automatically - via LocalStorage, WebSocket, etc. - and it would be persistent by default. I suppose you wouldn't want everything persistent though, just a relevant slice of state.

Here's an article about "persistent languages", which includes discussion on related features. http://wiki.c2.com/?PersistentLanguage

I recently submitted a link about "Robust First Computing". It didn't get any response, but I'll repeat the link and description here, since it's certainly esoteric, but has some extremely important properties.

Robust-First Computing: Distributed City Generation https://www.youtube.com/watch?v=XkSXERxucPc

A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture.

The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters!

The paper "Local Routing in a new Indefinitely Scalable Architecture" [2] by Trent Small explains how those rules work, how the city streets adaptively learn how to route the cars to nearby buildings they desire to find, and illustrated the advantages of "Robust First" computing:

Abstract: Local routing is a problem which most of us face on a daily basis as we move around the cities we live in. This study proposes several routing methods based on road signs in a procedurally generated city which does not assume knowledge of global city structure and shows its overall efficiency in a variety of dense city environments. We show that techniques such as Intersection-Canalization allow for this method to be feasible for routing information arbitrarily on an architecture with limited resources.

This talk "Robust-first computing: Demon Horde Sort" [4] by Dave Ackley describes an inherently robust sorting machine, like "sorting gas", implemented with the open source Movable Feast Machine simulator, available on github [5].

A Movable Feast Machine is similar in many ways to traditional cellular automata, except for a few important differences that are necessary for infinitely scalable, robust first computing.

First, the rules are applied to cells in random order, instead of all at once sequentially (which requires double buffering). Many rule application events may execute in parallel, as long as their "light cones" or cells visible to the executing rules do not overlap.

Second, the "light cone" of a rules, aka the "neighborhood" in cellular automata terms, is larger than typical cellular automata, so the rule can see other cells several steps away.

Third, the rules have write access to all of the cells in the light cone, not just the one in the center like cellular automata rules. So they can swap cells around to enable mobile machines, which is quite difficult in cellular automata rules like John von Neumann's classic 29 state CA. [6] [7]

Forth, diffusion is built in. A rule may move the particle to another empty cell, or swap it with another particle in a different cell. And most rules automatically move the particle into a randomly chosen adjacent cell, by default. So the particles behave like gas moving with brownian motion, unless biased by "smart" rules like Maxwell's Demon, like the "sorting gas" described in the Demon Hoard Sort video.

In this video "Robust-first computing: Announcing ULAM at ECAL 2015" [8], David Ackley explains why "Robust First" computing and computing architectures like Movable Feast Machines are so incredibly important for scaling up incredibly parallel hardware.

I think this is incredibly important stuff in the long term, because we've hit the wall with determinism, and the demos are so mind blowing and visually breathtaking, that I want to try programming some of my own Movable Feast Machine systems!

[1] http://movablefeastmachine.org/

[2] https://www.youtube.com/watch?v=XkSXERxucPc

[3] http://www.cs.unm.edu/~ackley/papers/paper_tsmall1_11_24.pdf

[4] https://www.youtube.com/watch?v=helScS3coAE

[5] https://github.com/DaveAckley/MFM

[6] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton

[7] https://en.wikipedia.org/wiki/Von_Neumann_universal_construc...

[8] https://www.youtube.com/watch?v=aR7o8GPgSLk

What a sad world we live in when Adobe publishes a paper about PostScript in PDF (which is just PostScript without the programming language).

To help offset the irony and celebrate Turing completeness, here is a PostScript interpreter implemented in PostScript, and an explanation of why.

http://www.donhopkins.com/home/archive/cyber/litecyber/ps.ps...

http://www.donhopkins.com/home/archive/cyber/litecyber/ps.ps...

http://www.donhopkins.com/drupal/node/97