Esoteric programming paradigms

Esoteric programming paradigms(ybrikman.com)

397 points by SlyShy 9 years ago | 148 comments

zmonx 9 years ago |

I have two comments about the Prolog code:

First, the article claims: "the sudoku solver above does a brute force search", but that is specifically not the case. In fact, quite the opposite holds: The Prolog Sudoku formulation shown in the article uses a powerful technique known as Constraint Logic Programming over Finite Domains, which automatically performs pruning before and also during the search for solutions. This effectively eliminates large portions of the search space in practice, and degenerates to brute force only in those cases where almost nothing can be deduced from initial constraints. In the particular case of Sudoku, the pruning is especially effective and can in many cases eliminate the search entirely, since the initial constraints (hints) basically determine the whole solution.

Second, yes, it is easy to write an O(n!) search algorithm in Prolog. However, it is almost as easy to implement much more efficient search algorithms in Prolog. For example, here is Quicksort in Prolog:

    quicksort([])     --> [].
    quicksort([L|Ls]) -->
            { partition(Ls, L, Smalls, Bigs) },
            quicksort(Smalls), [L], quicksort(Bigs).

Note how natural the declarative description of "first the smaller elements, then the pivot element, then the bigger elements" is in Prolog. This only requires a suitable implementation of partition/4, which is very easy to implement in at most 7 lines of Prolog code.

chubot 9 years ago | |

Eh, I'm pretty sure that suffers from the problem noted here:

https://news.ycombinator.com/item?id=13375108

See the "genuine sieve of eratosthenes" paper, and also:

http://augustss.blogspot.com/2007/08/quicksort-in-haskell-qu...

zmonx 9 years ago | | |

I do not dispute your point. However, the main issue is that the worst case complexity of this Prolog quicksort, whether in place or not, is already only polynomial, in contrast to the O(n!) permutation sort given in the article, and only about equally hard to implement.

In Prolog, an arguably more natural sorting method is merge sort, and it can (also) be implemented with asymptotically optimal efficiency in Prolog as follows:

    mergesort(Ls0, Ls) :-
            length(Ls0, L),
            zcompare(C, L, 1),
            halving(C, L, Ls0, Ls).

    halving(<, _, Ls, Ls).
    halving(=, _, Ls, Ls).
    halving(>, L, Ls0, Ls) :-
            Half #= L // 2,
            length(Lefts0, Half),
            append(Lefts0, Rights0, Ls0),
            mergesort(Lefts0, Lefts),
            mergesort(Rights0, Rights),
            merge(Lefts, Rights, Ls).

merge/3 is a built-in in several Prolog systems, and if your system does not provide it, you can easily implement it in less than 10 lines of Prolog code.

Both quicksort and merge sort Prolog implementations are (even in their respective worst cases) vastly faster than the sorting algorithm given in the article (in its worst case, and also in its average case), and are at most marginally more complex to implement. For this reason, I think the article could be improved by simply showing one of these algorithms instead.

We cannot consider it a drawback of Prolog that computing all permutations takes O(n!) time in this language. It's the same for C, for example. If someone wants faster sorting, we can implement it also in a declarative language!

Somewhat strangely, the fact that you can easily write a Prolog program to generate all N! permutations of a list with N elements is more likely to be counted as a disadvantage than as an advantage, in my experience. If people looked at C and Prolog a bit more fairly in such overview documents, they could as well count it as a disadvantage of C that such a program is harder to write in C than in Prolog. Yet, I have never seen a C program implementing permutation sort in such articles, and never seen a comparable argument or suggestion about C as I routinely see it about Prolog.

Permutation sort is slow in C! Well, that's a well-known shortcoming of an imperative language such as C.

sriku 9 years ago | |

FD constraint programming is powerful. Mozart/Oz goes one step further by making the search strategies programmable within the language using the idea of computational spaces.

I think two of the OP's notes are covered in Mozart/Oz - concurrent programming using data floor variables (roughly equivalent to promises) and logic programming, including finite domain constraints.

zmonx 9 years ago | | |

I agree, with only one small additional remark: In general, a programmable search strategy sacrifices termination guarantees for more generality. That's a completely defensible approach of course, and not an argument against this path of development! Still, it comes at a price, and researchers working in termination analysis may prefer precisely the tighter reins and more stringent resulting properties we obtain when we eschew programmable strategies in specific parts of the language.

For finite domain constraints, such guarantees are a major attraction in the Prolog community: If setting up the constraints terminates, then setting up the constraints plus search also terminates. That's a rather valuable and strong guarantee (since it is the search that can take take infeasibly long more often than setting up the constraints), and it breaks down if the search itself is more generally programmable.

taeric 9 years ago | |

I think you are just using a different definition of brute force than the post is using. It doesn't try all permutations of the digits, but it does do a search over the tree to find the solutions.

Now, to your point, this is really the only way you can solve sudoku. There is an odd belief that you can make an algorithm that "never guesses." And folks think that that would be the definition of a non-brute force algorithm. In reality, you either have a solver that is ready to backtrack, or you have one that can't solve all puzzles.

Pamar 9 years ago | | |

I am not sure about your backtracking point. Sudoku can be solved by Integer Programming (i.e. a special subset of Linear Programming) and this does not require any kind of backtracking.

sfrank 9 years ago | | |

No, a domain-consistent all-different propagator such as the one desccribed in [1] is sufficient to determine a valuation domain for a Sudoku puzzle without any search.

Of course that does not hold in general, but in the special case of Sudokus and problem modelling by a domain-consistent all-different propagator, no search is required for a solution.

[1] A filtering algorithm for constraints of difference in CSPs, J-C. Régin, 1994

zmonx 9 years ago | | |

To see what I mean, please consider the Prolog program for solving Sudoku puzzles that is shown in this article, and try the following query:

    | ?- sudoku(X, Y).

This is called the most general query, since all arguments are fresh variables. Declaratively, we are asking Prolog: "Are there any solutions whatsoever?" In this case, the system answers with:

    X = [_#3(1..4),_#24(1..4),...etc.]
    Y = [_#3(1..4),_#24(1..4),...etc.]

This shows that the Prolog program did not perform any search at all: No concrete value is instantiated, and the system does not ask for alternatives. That's right! No search whatsoever, and no backtracking at all, is performed in this program. No matter which definition of brute force search you are applying, this definitely does not fall into "search" at all!

In the article, a more concrete query is also shown, as well as its solution. This solution is found via constraint propagation alone. This means that the system has deduced the unique solution purely by reasoning about the available constraints, which it does automatically every time a constraint is posted. This is one example of an algorithm that does not guess.

This also shows that even supposing you cannot make an algorithm that "never guesses", you can definitely make an algorithm that has to do much less guessing than searching over the whole tree. In Prolog, such algorithms are implemented and encapsulated in powerful combinatorial constraints like all_distinct/1, which are available in many Prolog systems and which you can use in your applications. Internally, the associated constraint propagators prune the search tree by applying various algorithms for you behind the scene. The ability to use such constraints and their strong pruning are major attractions of using Prolog for combinatorial tasks.

You are right that there may be cases where such propagation, albeit quite strong, may not suffice to fully solve a concrete combinatorial task. For this reason, you have to apply a concrete enumeration of remaining variables. In Constraint Logic Programming over Integers, this search is called labeling and provided by predicates like fd_labeling/2 or similar, depending on your Prolog system. The article does not use them though, and even if it did, the search could be guided by various heuristics by simply supplying a few options, which together with the pruning applied by constraints distinguish such a search from more uninformed search strategies.

Note also that the posted solution is quite hard to generalize elegantly. A shorter and equivalent Prolog program that describes 4x4 Sudoku puzzles is:

    sudoku(Rows) :-
            Rows = [Row1,Row2,Row3,Row4],
            maplist(same_length(Rows), Rows),
            blocks(Row1, Row2), blocks(Row3, Row4),
            append(Rows, Vs),
            fd_domain(Vs, 1, 4),
            maplist(fd_all_different, Rows),
            transpose(Rows, Cols),
            maplist(fd_all_different, Cols).

    blocks([], []).
    blocks([A1,A2|As], [B1,B2|Bs]) :-
            fd_all_different([A1,A2,B1,B2]),
            blocks(As, Bs).

This assumes the availability of append/2 and transpose/2, which are likely already provided by your Prolog system, and easy to implement if they aren't.

tomxor 9 years ago | |

Pruning is an optimisation though, not a computational reduction... the remaining computation is still brute force. While it may be effective with low n, the complexity will still grow in roughly the same way as n increases - for this reason I would still call it brute force.

Isn't this why sudoku is still considered NP hard? (unless there has been a recent breakthrough).

sixo 9 years ago |

'Concurrency-by-default' is similar to a notation I've been using to map out async service calls. It's just this: lines are terminated with "," or ";". A comma doesn't block and all comma-separated lines are executed in any order, while a semicolon blocks. Names are only usable when a semicolon is reached, and a semicolon unblocks flow when all preceding names are bound. Probably code is scoped into { } blocks. So a lambda is like "pyth_distance = {x, y; sqrt(x^2 + y^2)}". A series of async callbacks would be given by an inner block {x = call1(), y = call2(); pyth_distance(x,y)}, allowing you to do any manipulations you can do with normal code.

Might try making a toy language out of it eventually.

tannhaeuser 9 years ago |

I don't know if Prolog should be called esoteric. Prolog is an ISO-standardized language after all, and its syntax has been used for 4+ decades now in most papers on conceptual database system and query language design I've read. Which isn't surprising since Prolog syntax, being based on operator-precedence grammar concepts, is arguably as minimalistic as it gets. There's definitely also a lot of interest lately in Datalog, not just as a decidable logic fragment (which has been used for decades as well), but also as a practical non-SQL database query language and proper Prolog syntax subset.

fake-name 9 years ago | |

Considering they also mention SQL and Forth, I think this could probably equally be called "things that confuse someone who only knows C".

andybak 9 years ago | | |

I think both Forth and SQL are outliers in their strangeness. Most people only have to deal with SQL on a very shallow level and barely regard it as programming at all.

Forth is known by name and reputation but very few people have ever tried to write anything in it - let alone delve into it's strange bootstrapped nature.

charlieflowers 9 years ago | |

I think the point is, most people being paid to program don't know it, or don't know it very well. (EDIT: Granted, this may be more of a statement about the "mainstream" than it is about prolog).

kybernetikos 9 years ago | |

As far as I can tell, the author didn't call any of these languages esoteric (the word appears once, in reference to the list itself), it's editorial titling, presumably because the actual title of the article sounds horribly click-baity.

cmontella 9 years ago | |

> There's definitely also a lot of interest lately in Datalog

Incidentally, Aurora, mentioned in the article, evolved into Eve, which is inspired heavily by Datalog.

pron 9 years ago |

To this I would add synchronous programming[1], which is particularly suited for interactive or concurrent programs and formal reasoning, and has had success in industry in safety-critical realtime systems. Examples include Esterel[2] and SCADE, and outside realtime, Céu[3] and Eve[4] (the latter is based on Dedalus[5], which combines SP with logic programming).

As someone who loves formal methods and believes most mainstream software systems today are mostly interactive and/or synchronous, I think this paradigm has a lot of untapped potential, and I'm glad to see it slowly move out of safety-critical systems into the mainstream, in languages like Eve.

[1]: https://en.wikipedia.org/wiki/Synchronous_programming_langua...

[2]: https://en.wikipedia.org/wiki/Esterel

[3]: http://www.ceu-lang.org/

[4]: http://witheve.com/

[5]: https://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-...

ibdknox 9 years ago | |

Yeah, there are a lot of interesting benefits to synchronous programming that haven't been explored in a wider context and we're excited to be able to do so. Figuring out how to actually implement Eve's semantics has been quite a quest and unfortunately the implementations of most of those languages don't really fit us. Fortunately, we've put some really interesting things together lately that have produced some very surprising performance numbers for us, so hopefully that's finally resolved and we can move on to how GALS and the like apply in our world. :)

pron 9 years ago | | |

GALS is indeed the obvious next step. That's how I'd do it.

robmccoll 9 years ago |

ANI reminds me of HDLs [1] - I'm assuming that's the inspiration with terminology like "latch"?

Hardware is also concurrent by default. Coding some hardware logic will also change the way you approach coding. Anyone who's interested get an FPGA demo board and write some verilog or VHDL - I highly recommend it.

1. https://en.wikipedia.org/wiki/Hardware_description_language

verall 9 years ago | |

Yes, I can't really understand why he didn't mention HDLs. I had never seen ANI before but both the syntax and terminology reminded me of VHDL.

snerbles 9 years ago | | |

These layers of abstraction seem to lead software bloggers to re-discovering concepts known by hardware engineers for decades.

DeltaWhy 9 years ago | |

Can anyone recommend a good course/book/tutorial for learning Verilog/VHDL? I have a demo board from a course I took in college and would love to try doing some projects with it, but I've had a hard time finding any good learning material.

snerbles 9 years ago | | |

Writing test benches in Icarus Verilog was quite helpful for me, along with pretty much everything at asic-world[0]. I haven't looked for a VHDL equivalent of Icarus, unfortunately.

Of course, always remember that "can be compiled" != "can be synthesized".

[0] http://www.asic-world.com/verilog/index.html

mighty_atomic_c 9 years ago | |

I was thinking this while reading, too. Concurrency is everywhere in hardware by default, and explicitly statesd with fork...join!

richard_shelton 9 years ago |

Honestly, I don't think that "concatenative" is a good term here. I prefer to call it a special case of combinator-oriented programming. You may see examples of this approach in vector languages like APL, FP and in functional world too (see Henderson's book, SICP and so on). The author of Joy (the language which spawned the whole "concatenative" activity) clearly was inspired by Backus's FP. Here we have stack combinators and we can emulate them even in Python, thanks to closures.

square = code(dup, op("*"))

Add a bit of syntactic sugar and you'll get "concatenative", or, better stack combinator-oriented language.

As for Prolog, I really appreciate that the author is calling it "declarative" not a "logic" language. It's more important to learn about backtracking and unification (powerful variant of pattern matching) than about something like Horn clauses. For anyone who wants to learn Prolog better (and it's worth it, Prolog is one of most beautiful PLs around!) I recommend this article: http://www.amzi.com/articles/prolog_under_the_hood.htm

asavinov 9 years ago |

Would like to mention concept-oriented programming [1] which is work in progress but has highly ambitious goals of changing the way we think of programming. The initial idea is to make references active and customized elements of the program which can intercept all accesses to the represented objects. A new programming construct, called concept (hence the name of the approach), describes both behavior of references and behavior of objects. Objects exist in a hierarchy modeled by the concept hierarchy. IS-IN relation is used instead of the traditional IS-A. Also, concept-oriented programming distinguishes between incoming and outgoing methods, that is, every method has two versions: for external access and for internal access. More papers in [2].

[1] https://arxiv.org/abs/1501.00720 [2] https://www.researchgate.net/profile/Alexandr_Savinov

Disclaimer: I am the author of concept-oriented programming and data model

DonbunEf7 9 years ago | |

How does your research interact with object-capability models of computation, as in the E programming language?

asavinov 9 years ago | | |

(I can be wrong but) as far as I understand E is based on objects and messages as primary mechanisms, that is, we do not know where objects exist, how they are managed and how messages are transferred. Concept-oriented programming (COP) is a references-first approach while objects are defined as being functions of references, that is, object is a derived (secondary) element of the model and the goal is to be able to have full control over this mechanism (custom heap, custom garbage collection, custom access control and security model etc.)

What I see similar in object-capability model and COP is that they both try to treat object access as a highly important part of a system behavior. In COP, I used to write that it is more important what happens during access rather than in the object itself. Hence, being able to make these intermediate actions integral part of the program (and develop good PL for that purpose) is very important.

anotheryou 9 years ago |

Will Eve ever take off? I like the thoughts behind it.

https://youtu.be/VZQoAKJPbh8 very good talk about the background of eve. When he finally talks about eve you might want to switch to a more recent talk about it.

ibdknox 9 years ago | |

Eve[1] is in the process of becoming a lot more real than it has been up to this point. We've found a great model and discovered a way to build a high performance implementation of it, which means much of the foundational research is finally in place. Over the next couple of weeks, we'll be revamping our website, docs, etc to help people get started building real things with it. :)

There's going to be a lot of really exciting stuff coming over the next few months. We've gathered a set of ideas, evidence, and implementations that have certainly blown us away - we hope others will find it valuable too.

EDIT: I realized I didn't address your initial question. Fwiw, we just recently crossed a really big milestone in terms of usage - more than 40,000 people have now played around with Eve on http://play.witheve.com and we've learned a ton from that experience. Part of the website revamp will be making that workflow simpler and nicer. We have a surprisingly high conversion rate (> 30%), so hopefully we can help smooth out that experience and begin to grow the community more and more.

[1]: http://witheve.com

throwaway7645 9 years ago | | |

I can't load the site on my phone. Mind pointing out what makes Eve so special? I'm suspicious of us figuring out anything mind boggling new at this point and assumed Eve was all a gimmick (I hope to be proved wrong :)). Something like Red makes a lot of sense to me as that ahhh language as it is tiny with no install, can be used for high/low level coding, has excellent DSLs such as GUI builders, and can compile to a native binary to name a few things that kind of shocked me. Eve seems to be more like an online Smalltalk? It's always fascinating to hear new ideas and I wish the best for your project!

chrisdone 9 years ago | |

I believe that Aurora (covered in the article) was some kind of pre-cursor to Eve, by the same Chris Granger.

ibdknox 9 years ago | | |

It was indeed, though Eve is a much more grown up idea than Aurora ever was. It's amazing how little we really understood back then and how far we've come. :)

nialv7 9 years ago |

Array oriented programming languages are also pretty interesting:

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

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

protomyth 9 years ago | |

F-Script was a very interesting array programming / objects hybrid. Smalltalk meets APL is not far off.

nickpsecurity 9 years ago | |

Especially in something like kdb.

throwaway7645 9 years ago | | |

I hear this a lot, but am confused in that I can't find hardly any examples anywhere. It'd be nice if kx systems put some videos of people querying data and building charts...etc.

dkersten 9 years ago |

A few random comments:

Forth is a great concatenative language, since its the pioneer in that area (I think), but Factor is definitely worth mentioning too as a "modern" take on the paradigm. It essentially tries to be a concatenative Lisp.

ANI was dead even in 2014 when this article was written (which the author acknowledges: "the language seems dead, but the concepts are pretty interesting"). It has some really interesting ideas, but since it never got implemented, I'm not sure how much use there is in discussing it here amongst real languages. It would be useful as a discussion for possible future languages for sure, but its currently still just a concept, so I'm not sure what practical thing you can learn from it right now.

oolongtea 9 years ago |

ANI/Plaid reminded me of the LabVIEW visual dataflow language, which is quite widely used in the branch of physics I used to work in, for data acquisition and instrument control. While I've often longed for a text-based alternative that plays better with modern version control and my favorite text editors, I have to say that having everything laid out for you in a visual way does make it easier to reason about the execution flow. That is, after a few years of working with it --- initially, this paradigm shift was rather a painful stretch of the nerves.

If every language has its own specific dark patterns and bottlenecks, LabVIEW's is definitely the "brightly-colored spaghetti" structural breakdown of an advanced beginner's code :-)

Incidentally, why do we, as programmers, tend to focus on a language's bottlenecks so much, in such an emotionally charged way? Any psychology-of-programming people out here? You might consider LabVIEW an excellent case study in getting on people's nerves...

mcguire 9 years ago |

For some extra dependently typed fun, check out ATS and Dafny.

ATS is aimed at system programming, and if you think Idris has a steep learning curve, you'll need belaying for ATS. And, the language is horrible. But it's really mind expanding to see it in action.

Dafny is a really basic language with support for Hoare/Dijkstra verification. It's completely unlike the type system model.

_pmf_ 9 years ago |

I'd recommend to everybody (but especially those involved in either embedded systems or a lot of concurrent state) to try out HSM / state chart programming (note: this has basically nothing to do with "flat" FSMs). It's as close to a silver bullet as you'll ever get for these kinds of systems.

Stateflow or QP/QM, all other systems suck.

petra 9 years ago | |

Is it useful in writing drivers ? or mostly for application code ?

And what are the drawbacks? Why aren't everybody using it?

_pmf_ 9 years ago | | |

It's used heavily in application code for automotive ECUs. It has code generators that generate output with a really, really, small footprint and zero runtime overhead; due to optimization at very high levels, this is on the level of really good LTO optimization.

Drawbacks: it's very un-agile; you really have to think the system through completely. (The magic being that if you do this, it is very likely correct by design.) It's not really feasible to specify a part of the system now and leave other parts open for later refinement. The other drawback being that no good non-commercial options exist.

lioeters 9 years ago |

Thought-provoking. The examples are all programming languages, but the paradigms themselves can apply on a smaller scale, i.e., for application features, as design patterns or inspiration.

The section on "symbolic programming" has me pondering still about potential implications. It makes me imagine something like a "visual" WYSIWYG editor, but a "conceptual" editor.. Looking forward to digging deeper via provided references.

ramchip 9 years ago |

It's strange to see ANI mentioned as if it were a real, working language. AFAIK it was never able to compile even the samples: https://code.google.com/archive/p/anic/issues/7

dkarapetyan 9 years ago |

Wait. What exactly is esoteric about these paradigms? All the books I've read simply call them regular paradigms.

virgil_disgr4ce 9 years ago | |

I guess "uncommon" is increasingly used as one of the meanings of "esoteric"

throwaway7645 9 years ago | |

You're correct that I'd not consider these esoteric, just not procedural or OO. Esoteric would be something like Brainf*, the music programming language, or that art language (forget the name). Unusual but still commercial and useful paradigms are logic, array, functional, and concatenative to name a few.

jfoutz 9 years ago | | |

Piet. The Mondrian language I'm guessing

minxomat 9 years ago |

Curious. ANI seems to me like an abstract form of graph-parallel programming, where the language itself is the scheduler.

There are some production-ready schedulers for GPP, like Intel's TBB[1] (C++), but learning to be effective with this requires a major shift in thinking about code - essentially thinking in graphs.

[1] - https://www.threadingbuildingblocks.org/tutorial-intel-tbb-f...

edparcell 9 years ago | |

My team has been working on a Python library called Loman that represents computations as graphs. We've open-sourced it [1][2]. One of our aims is to make it as natural as possible to use graph-based programming, and within an already-familiar programming language. Be interested to know what you think.

[1] https://github.com/janusassetallocation/loman [2] http://loman.readthedocs.io/en/latest/user/intro.html

minxomat 9 years ago | | |

Can you demo your library with a more complex example, e.g. the Dining Philosophers Problem. Here[1] is the solution using TBB, and here[2] a more recent version - using a multioutput function node to optimize the flow.

[1] - https://software.intel.com/en-us/blogs/2011/01/10/using-the-...

[2] - https://software.intel.com/en-us/blogs/2011/09/13/using-inte...

protomyth 9 years ago |

Agent oriented-programming http://robotics.stanford.edu/~shoham/www%20papers/AgentOrien... [PDF]

romaniv 9 years ago | |

Alan Kay talking about agent-oriented computing in 1990:

https://youtu.be/275FQ9koAw8?t=7647

Very interesting view, especially considering how long ago that was and how relevant they still are.

vram22 9 years ago | | |

Some time after Java first came out, there was a product called Voyager from a Java products company called Objectspace [1]. Voyager was a product for creating and using mobile agents. I had downloaded the trial and tried it out a bit. It was quite cool. IIRC, Graham Glass, who was involved in ObjectSpace, was also the creator of Electric XML, an XML library, and was later CTO of WebObjects. Recently he had/has been working on EDU 2.0 (EDU20.org), an e-learning product company.

[1] They were also the creators of JGL, the Java Generics Library, which was like a Java version of the C++ STL, and done before Java got generics natively.

protomyth 9 years ago | | |

That's pretty good, hadn't seen that clip. I think the pervasive networking mentioned has enabled the paradigm but wasn't quite the driver Kay thought it would be. RPCs (of some type) over HTTP have won over having mobile code. On the other hand, I still see a big upside in using agents for their deployment and component (in the divisible whole sense) organization of software.

nickpsecurity 9 years ago | |

Telescript and Obliq come to mind.

protomyth 9 years ago | | |

The Telescript reference I understand since that was General Magic's goal with Magic Cap, but I'm not sure I see how Obliq is an agent oriented programming language. It seems to be a object oriented one.

combatentropy 9 years ago |

  > Dependent types
  > 
  > Example languages: Idris, Agda, Coq
  > 
  > You’re probably used to type systems in languages like C and Java,
  > where the compiler can check that a variable is an integer, list, or string.
  > But what if your compiler could check that a variable is “a positive integer”,
  > “a list of length 2”, or “a string that is a palindrome”?

This is what I love about SQL. You can even define your own types, like "email", at least in PostgreSQL:

  create table contacts (
    name text not null,
    age int check (age >= 0),
    email email
  );

It already has a few of these special types built in, like for IP and MAC addresses (https://www.postgresql.org/docs/current/static/datatype.html).

tathougies 9 years ago | |

The author got the gist of dependent types wrong. It's not simply about checks. Dependently typed languages allow the result type to explicitly depend on the input data.

Thus, a dependently typed database would allow one columns type to depend on the value of another column.

It would be like saying

  Create table dep ( name text, fieldType int not null, fieldValue (if fieldType = 1 then int else varchar))

Notice the 'if' in the type of fieldValue

kornish 9 years ago | |

Out of interest, how is common ORM support for custom Postgres types?

siddboots 9 years ago | | |

GeoAlchemy for PostGIS/SQLAlchemy is a good example of explicit support. But typically, you can always "deal" with custom types in your ORM, even if that means falling back to binary data.

afdsadf 9 years ago |

Shame not to see factor in the concatenative list, it addresses some of the pain points there with locals

protomyth 9 years ago | |

Postscript would also have been a fine addition and has its own methods of dealing with locals. https://www.adobe.com/products/postscript/pdfs/PLRM.pdf [PDF]

DonHopkins 9 years ago | | |

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/drupal/node/97

toolslive 9 years ago |

I have also seen _persistent by default_ where every variable is by default store in a database and automatically initialized when you come back to that piece of code. Useful for web development. (Sorry, forgot the name of the programming language)

lioeters 9 years ago | |

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

leovonl 9 years ago |

This classification of "paradigms" is a bit off.

First, declarative programming is a generic name which includes a broad range of paradigms - from functional to logic programming. Logic programming is something that deserves a special mention and discussion, because there are a number of interesting and unique concepts that deserve a more in-depth explanation.

Second, "dependent types" is better understood as a feature of a language (or better yet, of a type system) than a paradigm by itself.

Some of the other "paradigms" also seem more like characteristics of languages, and not really something that structures the way solutions are expressed/understood.

mmalone 9 years ago | |

This. There are three (and arguably only three) common programming paradigms: imperative programming, functional programming, and logic programming with lineages back to Turing machines, lambda calculus, and formal logic / proof search, respectively. Languages can be broken down along other dimensions, but usually the term "paradigm" is reserved for the sort of irreducible foundation of a language, and these seem to be the three useful ones.

Edit: to put a slightly finer point on it, this irreducible foundation mostly has to do with how the language "computes." Imperative languages compute via statements that modify program state. Functional languages compute via proof reduction to normal form. Logic languages compute via proof search.

adwn 9 years ago | | |

There's no reason why you couldn't integrate functional programming and imperative programming into a single language – for example, an imperative layer (for I/O) around a functional, lambda-calculus based core (for computations). Now what is the "irreducible foundation of [this] language"?

devrandomguy 9 years ago |

There should be a category for analogy based languages. Rail or the Billiard Ball Machine, which looks like Feynman diagrams on a pool table, are examples of this.

https://esolangs.org/wiki/Rail https://esolangs.org/wiki/Billiard_ball_machine

dragonwriter 9 years ago |

I'm kind of uncomfortable calling "declarative" a paradigm; it's a broad (and not binary) feature. Prolog and SQL are, respectively, the leading examplars of the logic and relational paradigms. They are both fairly declarative (but then, in the age of optimizing compilers, even C is somewhat declarative: your code constrains the result but it doesn't dictate the how as much as it seems to.)

rmidthun 9 years ago |

I would add pictorial programming languages, such as ProGraph if you want a really unusual way to program. Object oriented, but inherently dataflow. Loops were very weird though.

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

tjalfi 9 years ago |

ParaSail[0] is another implicitly parallel language. It has similar goals to Rust and Spark Ada.

[0] https://forge.open-do.org/plugins/moinmoin/parasail/

a_c 9 years ago |

On concatenative languages, I would like to add Piet[1] as a contender. Plus Piet program could look like 8-bit art (to me).

[1] http://www.dangermouse.net/esoteric/piet.html

a_c 9 years ago | |

I once read about Pieter Hintjens' model oriented programming [1] which the idea I have yet to understand. Hope someone can provide more insight on this subject. HN discussion [2]

[1] https://github.com/imatix/gsl [2] https://news.ycombinator.com/item?id=11558007

westurner 9 years ago |

Re: "Dependent Types"

In Python, PyContracts supports runtime type-checking and value constraints/assertions (as @contract decorators, annotations, and docstrings).

https://andreacensi.github.io/contracts/

Unfortunately, there's yet no unifying syntax between PyContracts and the newer python type annotations which MyPy checks at compile-type.

https://github.com/python/typeshed

What does it mean for types to be "a first class member of" a programming language?

Blackthorn 9 years ago |

Concurrency by default feels a bit like the underlying processor of the machine, what with superscalar architectures and all.

snerbles 9 years ago | |

Hardware Description Languages tend to be concurrent by default, with specific syntax for sequential logic.

A parallel pair of AND gates is physically concurrent, let alone anything with a clock.

garyclarke27 9 years ago |

Great thought provoking article. Good explanation of Dependent Types, Title is misleading though, should be called - Particular or Specfic Types. Postgres has the same capability - Domains - always surprised that other db's such as sql server have never adopted this useful feature.

oddmunds 9 years ago |

There seems to be and old discussion over here https://news.ycombinator.com/item?id=7565153

Chris2048 9 years ago |

Aurora looks interesting, but it seems to be .Net/windows only?

ibdknox 9 years ago | |

That must be a different Aurora. The one mentioned here was never really released, only demo'd at Strange Loop. We subsequently went on to turn that into Eve[1].

[1]: http://witheve.com

rmbeard 9 years ago | | |

Thanks for confirming that. This looks very interesting. How active is development of the mathematical side of things? Also have graphics capabilities been developed yet or are they far away? The HN article indicated Aurora now Eve would have these capabilities. I'm interested because of the similarities I see between Eve and other literate programming approaches such as the Jupyter project, Mathematica, Sage notebooks, R motebooks. Eve looks like it will soon be joining that group.

hchasestevens 9 years ago | | |

Is there any chance that you'd ever open-source the original Aurora demo? Seems like it would be a great foundation for further exploration in this space.

DonHopkins 9 years ago |

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

bryanrasmussen 9 years ago |

Isn't Lua supposed to be an example of a concatenative language?

beagle3 9 years ago | |

Not at all.

The definition I like to use of concatenative language is:

If "X Y" is a legal program, then "X" is a list of tokens and a legal program and "Y" is a list of tokens and a legal program, and semantically, executing "X Y" is equivalent to executing "X" and then executing "Y".

practical implementations often deviate a little from this ideal.

bryanrasmussen 9 years ago | | |

Not sure where I had it from, probably some other language and I got it mixed up with Lua in my head.

vvanders 9 years ago | |

Not really, the C API is stack based but it's concatenative to the degree that a C program uses a stack + heap.

_pmf_ 9 years ago | |

Do you mean Tcl?

pitaj 9 years ago |

I believe HN title convention is to remove the number of list items ex. this title should be just "Programming paradigms that will change how you think about coding".

sctb 9 years ago | |

You're right, and “... that will change how you think about coding” is clickbait. Luckily the article contains an adjective for that, which we've used in the title. Thanks!

dasmoth 9 years ago | | |

I realise moderation is tough an never pleases everyone, but have to say I'm disappointed here: in some circles, "esoteric" carries some quite strong negative connotations, which I think are unwarranted here.

Some of these languages are definitely suitable for "serious" usage. And I'm not sure I'd count SQL (or Prolog, for that matter) as esoteric at all!

fenomas 9 years ago | | |

> "... that will change how you think about coding” is clickbait

Nonsense. The article's premise is explicitly that the listed paradigms will change how you think about coding. The author may or may not be correct about that, but the original title was not random hyperbole to entice a click - it was an accurate description of the article's premise and content.