As CPU excess increases, I guess I've always thought that eventually code blocks could be grown using genetics inspired algorithmic processes that could just try everything possible until something works well.
To some extent this is already done in a process called "Superoptimization"[1]. In that case, though, correct code is used as a rigorous functional specification, and the Superoptimization process will replace segments with shorter or faster opcode sequences with identical side effects.
You are underestimating the rate at which the number of possibilities to be searched explodes exponentially. Read the paper on Denali, an optimizer that conceptually tries all possible instruction sequences to compile a piece of a program optimally. Even though they used sophisticated pruning techniques and state of the art combinatorial solvers it didn't work for anything beyond a couple of instructions (less than 10), and AFAIK nothing practical ever came of it. Say you can currently successfully synthesize instruction sequences of length 6. The thing with exponential growth is that even if computers became a million times faster, then you might be able to achieve instruction sequences of length 9, not of length 6 million.
I don't think there's any existing programming language that does what OP wants.
But Prolog is far from the last word on the subject. For one, it is basically untyped. There are dependently-typed programming languages that can express non-trivial properties via types, which the compiler can check (see ezyang's example).
I'll help what I can. I had a very similar idea, sparked by a conversation in college with a fellow CS major. He was saying how much he liked to program and I said that I hate it. My reasoning was exactly the same as yours, but perhaps broader.
I'd like it if we could get to the point where you say very plainly what you want in your native language (English for me), and then that is interpreted and perhaps more questions are asked by the program until it can implement what you meant. Obviously the problem of NLP is a massive one that will likely never have a perfect solution. There are also the problems of logical inference (if you think this is easy, look up the CyC project). I don't think we should let the current constraints of technology hold us back from designing something better, however.
What you have is fabulous and immediately useful: You are describing a language for describing constraints on the results of computer programs.
In other words, you can express the correctness of a computer program and check whether a program is, in fact, correct.
It’s true that IF a sufficiently smart compiler could infer a working program from the definition of correctness, no further “programming” would be required. However, we don’t have that yet, and in fact I’m not urging you to write it.
Instead, consider the benefits of your language just the way it is. You can use it to write test suites. You can embed it in other languages to express design-by-contract.
Sure, sorry, didn't mention on the article, Prolog is the closest thing that exists, although I think Prolog commits at least one cardinal sin that breaks the really great properties (/cut/) and it just doesn't get deep enough.
Prolog is a kind of declarative programming, but the two concepts are not the same. From the link: "declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow." This can be implemented in any way one desires.
You probably already know this but you should really save yourself a million comments and put an update in the article that shows you already know about Prolog. :)
Possum would allow you to directly execute a program that was formally defined using the Sum formal specification language. While it was not able to handle every possibility, I found using it to be a really magical experience.
However, in practical terms, the idea of declarative programming has just as many difficulties as ordinary programming: how do you know your specification is correct? how do you debug a logical expression? how do you know your specification matches what you want it to do?
I will look at the project, sounds interesting. If it's like that, I can only
I know declarative doesn't solve the problem of correctness. It's really difficult to define correctness per se! But what such an approach really gains is that you can forget about off-by-one errors, unforeseen cross-conditions in stupid details, so much repetitive code, etc... you will still have the higher-level problems of programming, the efficiency problems, the spec-correctness problems, etc... but nowadays you have those, plus the nitty-gritty details of programming in our paleolitic languages!
I know there are a few initiatives in this area, I really want to have an everyday tool that allows using that kind of approach for everyday problems. It will just make everything so much better for us programmers!
They say that the only essential complexity is the one inherent to the problem the program is trying to solve. Everything else is just here because we haven't yet found the methodology or invented the tools to battle it.
They also describe an ideal world, where all the programming is done in way of declarative programming - what you want the code to do, and not how to do it.
So I am relatively naive when it comes to declarative programming in general and have not yet read this paper (I will after commenting here), but that said...
Don't you have to (at the very least) tell the compiler how to do things? To reuse the example from the article: when you tell your friend to get you a beer, at some point your friend has learned HOW to get you a beer. Similarly the compiler will need to know HOW to do things that you declare. Sure it will be great when we can just tell the compiler that we need this list sorted in reverse alphabetical order but at some point someone is going to have to program the sorting algorithm on the back end.
Am I way off or are we just talking about a hypothetical future when compilers are (even more) black boxed and we don't have to think about them anymore?
Declarative languages are defined by the fact that in them, you don't tell the compiler how to do things. You just describe the result you want, and it's the compilers job to get there. Yes, this makes the compiler rather hard to write.
SQL is probably the primary example. Prolog is also well-known.
For anyone who may not know, Prolog does this in a pretty interesting way. You have some declarations that make up your program, Prolog takes these and then uses them to conduct a logical proof (like in discrete math). You negate the premise (proof by contradiction), and then try to show that this will cause a contradiction (line 5 says Bob is Human, but line 42 says Bob is not Human). If you can find such a contradiction, your premise was true.
It does this by using backtracking, which is really interesting in itself if you're not familiar with it.
Great paper. I'm familiar with it, and I think it's one of the initiatives out there pointing in the right direction. Same as Prolog and SQL. But we still have to work a long way in that direction for it to pay off nicely in our day to day!
this paper has a lot to say about the cause of programming complexity, Out of The Tarpit
This paper is highly regarded by some smart people, but every time I've tried to read it I've seen nothing of much value - only some obvious platitudes about complexity (including the bit about complexity being intrinsic to the problem vs. just the implementation), a lot of architectural gobbledygook (complete with boxes-and-lines diagrams), and some hand-waving about combining the functional and relational models. Has anything ever come of this? Specifically, any working systems?
That seems like a huge stretch. Lisp has nothing to do with that paper, and minimizing state and complexity could hardly be more obvious design concerns. The concurrency aspect I can't comment on, but it's not a major theme there either.
Perhaps I just don't get it, but I'm a little miffed at having tried several times to absorb the gems of wisdom in that paper and come up with nothing that isn't obvious (even the idea of functional programming over relational data is obvious) and that couldn't have been said less pretentiously in easily a tenth of the space - ironically, for a paper about minimizing complexity.
1) accidental complexity is the source of a large number of bugs
2) implicit, unnecessary, tightly-coupled state is the cause of a significant number of bugs.
3) mostly-functional programming reduces the amount of state in 2
4) RDMS databases, with transactions and triggers, are a good way of reducing state as well
Clojure applies all of these lessons. lisp reduces accidental complexity in the language. FP reduces accidental complexity wrt to state. the STM and agents are close analogues to DB transactions and triggers.
"even the idea of functional programming over relational data is obvious". Yes, but where else has that been tried?
This doesn't look much simpler to me, and I suspect the problem with this approach will wind up being incomplete or overconstrained specifications, rather than incorrect programs.
To use the language of the op, it will be composed of many discrete simple assertions that excruciatingly specify the output.
What something starts like this it usually translates to: "I don't understand pragmatic hardware/complexity/market etc constaints and engineering compromises".
Might be. Hopefully not. I have done a huge amount of programming though, so it's not like the reflection comes from ignorance.
Under the mess of spaghetti code that anything out there is now, I see a clean structure of code trying to come out. I want to help it come out to the surface.
Generally, what I've found is the reason for the big pile of mess is not that the methodology is wrong, but quite frankly the programmer didn't know what needed to be done until the program was completed. Even with a complete set of requirements, if you are writing anything of any complexity then by definition it hasn't been done before. But you can usually take an existing program, re-define the specification, and re-write the code in a much cleaner and correct fashion (assuming you avoid the temptation to add new features at the same time).
The most common declarative programming language used in SQL. In theory the optimizer takes my declaration and builds an optimum (or at least decent) set of step in the database engine to accomplish what I have declared. With all the work in this limited area, database optimizers get it really wrong quite a lot (Sybase 12.5 was bad enough on big data that forcing order of joins and indexes was needed).
I am not sure we are at the stage where the computer can be trusted with the "what". Most new learners need to be told step by step the "how" and computers seem to be at that stage. Prolog is a nice counter-example, but even it can get itself into some real trouble.
I agree programming is broken, and I agree the whole program knowledge is just painful, but I am think there are some steps before full declarative. As much as I dislike the old VB, it did have a very vibrant component market. That concept didn't seem to evolve or make it to the server. I look at Mongrel2 and wonder if the component approach could be applied. Regardless, I think the biggest problem is lack of ability to separate the pieces of a big project effectively no matter the eventual solution.
although I respect Philip Greenspun greatly, most spreadsheets I have seen are pretty procedural. People tend to think in steps on those types of calculations.
I'm not convinced this is possible for anything but a small subset of programs. Such a compiler reasoning about a Turing-complete program would certainly be 'AI-hard', as it would have to essentially be a programmer itself.
What I'm interested in is making proof assistants easier to use by improving their inference capabilities, so programmers can verify the correctness of their programs without having to put in orders of magnitude more work...
So long as the problem you are trying to solve is constrained by the ease with which you can express the problem, this will help.
But it will not help when the constraints are elsewhere: memory, network, CPU, heterogeneous interoperability; all still relevant in these times of mobile and distributed computing. When you are operating to these other constraints, you need control - or rather, consistency and predictability - over the consumption of those other resources. It's no good having a magic compiler that can turn your specification into an implementation, if you don't know whether the implementation will run in O(1) or O(n) space or time, what kind of constant factors are involved, and how easily you can tweak the tradeoffs when you hit one constraint or another.
I concur with raganwald's comment: this is more useful for proving, static analysis, testing, etc.
Furthermore, I'm pessimistic that you'll see substantial improvements in expressibility using your approach, particularly when you try to scale it above simple functional (by which I mean stateless input to output) problems. The reason is that programming is an exercise in attention to detail while simultaneously keeping the large in mind; and your focus won't change this fundamental nature. Writing a complete specification for a program rivals writing an imperative implementation in complexity (soup to nuts, I'm not talking about high-level DSLs here, which is an approach equally applicable to the imperative route). I expect a good compiler will swamp you with the inconsistencies of your hidden, unstated assumptions.
For example, I note that your sorting specification doesn't specify whether or not the sort is stable; I think that makes it incomplete, and also it's a tricky constraint to encode.
You are right, and I think you've found one of the weak spots. But I do think that can be treated, and the advantages of the programming-ease will be a good trade-off in many cases with the lost control for efficiency.
It's like the switch from assembly to C, or from manual memory management to automatic memory management. You lose something. You gain something else. The new approach is not valid for everything, but for some/many cases, it's much better.
Yes, the spec of a complete program will still be a great amount of work. The default resulting code will probably be slow. But you will be able to "describe" the program (in many cases), and you will be able to optimize it later without risking the correctness. Hopefully that can be a great aid and tool in many cases. We'll see, and I hope to have a lot of help along the way doing it publicly!
BTW, if what comes out is just a good new approach to static code analysis / formal specification / etc... it will have been worth it. But I do hope to find a usable tool at the end of this quest :)
He doesn't have to specify whether or not the sort is stable -- the compiler should only have to satisfy the constraints he imposes. So if he doesn't specify that it must be a stable sort, the sort might be unstable, just as with many sort routines that don't specify whether they're stable.
This is what I mean by hidden / unstated assumptions. So on one version / implementation of the compiler, a program may produce correct output, where on another, it produces incorrect output, because of a hidden assumption about the stability of the produced sort. The problem may not be found in testing due to this; and what will debugging the program look like?
If this is the kind of issue that can come up in a really simple task, what kind of issues will emerge as things scale up?
> Writing a complete specification for a program rivals writing an imperative implementation in complexity
> I expect a good compiler will swamp you with the inconsistencies of your hidden, unstated assumptions.
Thank you, this is exactly what I came here to say.
The entire practice of programming is formally defining how everything works, and the devil is always in the details. The effort of going through those details thoroughly and defining exactly what you want to the program to do in all situations is, simply, the act of programming itself.
The best you can do is create languages, libraries, frameworks to help you do it more efficiently.
i came here to upvote this comment. it touches on the real problems concisely without just sneering about reinventing declarative programming. metaprogramming is worth pursuing, but the considerations hinted at above point to why it is so difficult to realize.
one thing everyone who is hating on the idea is missing is that if one compiler somewhere finds a solution on the Pareto front, for a sub-problem, that pattern can be uploaded to the cloud and re-used by other compilers. this would over time tend to help with the practical problem of how to conserve resources in the face of such a hard overall problem.
I'm curious about how a compiler can infer the algorithm for sorting. I've played with machine learning algorithms like neural networks and genetic algorithms which might be able to do some of this, but what other things are out there?
My vision of the future for programming is a room with 3d virtual reality goggles. Monitors are nowhere to be found, lines of code in files are presented to you on virtual monitors around you in a 760 degree panoramic view, above, below, and THROUGH. Our brains are evolved for a 3d world, not the lines-of-code on printed page world.
Commands like "instantiate new object", "add items to object", "do an sql query", "run sql query", "sum the integers", suck. These commands will be represented in 3d space like a flow chart with general directives. When you want to "zoom in" on one of the boxes, you can see the particulars of how it takes place. Zooming out shows you a perfect representation of the general directives, zooming in takes you to the nitty gritty commands, and zooming in further shows you the bits being shifted around on the hardware.
that's actually not that far from what programming with well-designed libraries and abstractions is like now. at least, I know I have a more-or-less 3d visualization of my program in my head as I'm working on it... but that could be just me.
> There was recently a very interesting post by John Carmack about static code checking, where he cited a great tweet by Dave Revell on code checking: "The more I push code through static analysis, the more I’m amazed that computers boot at all."
Wrong attribution. That tweet was originally by Ryan Gordon (@icculus).
Jon, you're looking for haskell. But there's a catch -- programming in haskell is HARD, and expert haskellers are the best of the best, thus EXPENSIVE.
many customers don't want correct programs, they want cheap programs. Some people in finance care about correctness, maybe you should check them out.
Dusting, thanks for the suggestion, but I'm not looking for Haskell. It's not what I'm looking for. What I want is declarative, not functional. There is an inherent limitation in the functional approach, I hope to cover why that is in a further article in the series.
I am not after correctness per-se. I am actually more after "cheapness" at least in programmer time. But I do think a lot of the programmer time is spent in things that a solution-describing approach removes, and correctness gets a ride.
I have often heard Haskell called declarative, it all just depends on how you go about writing your Haskell code.
Theoretically Haskell is "time cheap" it just requires more time upfront. That is not to say Haskell is exactly what you are looking for however, I think it is at this point, the closest useful language to what you are looking for.
Not to discourage you from trying anything but it looks like you've ignored the complexity issues with this (I won't pick at the fact that you described an O(n^2) algorithm for sorting).
I understand that you don't want to specify the steps to achieving the goal but the steps directly impacts running time.
In your particular example, a compiler could produce a program with the correct output but runs extremely slowly even for small arrays (by simply trying all permutations until it finds one satisfying your constraints, or even worse, randomizes the entries until the constants are satisfied ("bogo sort")).
Furthermore, there are undecidable problem for which the output is easy to specify but no program could exist. For example, deciding if an input piece of code will loop indefinitely.
In your article, you've mixed needless overhead (the dummy/local swapped variable comes to mind) and the steps needed to specify an algorithm.
If you only want to remove the overhead (and thus, some source of mistakes you've pointed out), you could aim for a language where the algorithms are easier to specify.
In the bubble sort case, the code would look something like.
def bubble_sort( array ):
while there is an i such that array[i]<array[i+1]:
swap( array[i], array[i+1] )
(You can almost do this in Python already which seems to be where the syntax is inspired from. I can elaborate if interested.)
Ultimately, I have to agree with other comments saying this will be more useful for checking than specifying a program.
Here is another way of defining something is sorted, taken straight from a real language:
Inductive StronglySorted : list A -> Prop :=
| SSorted_nil : StronglySorted []
| SSorted_cons a l : StronglySorted l -> Forall (R a) l -> StronglySorted (a :: l).
What this says is that an empty list is sorted (SSorted_nil), and that given some sorted list l, if a is less than all of the elements in l (well, we generalize to some relation R), then a prepended to the whole list is sorted. (SSorted_cons)
But it turns out, there is another way we can say this property, if our relation is transitive: all we need to say is that the element is less than or equal to the first element of the list.
And for any non-trivial specification, there are literally dozens of ways of specifying it, all of which happen to be identical. Which one do you pick? Which one is easier to use? Hard to say, in general.
also, i didn't completely follow the final example, but you might find that category theory is relevant. related, it's not completely clear to me why you're not happy with functional programming. in a sense what academic functional programmers are doing is what you want your software to do. they're just not smart enough to put it in a compiler yet. i think. for example http://www.fing.edu.uy/inco/cursos/proggen/Articulos/sorting... (isn't that kinda what you want?)
I once read a programming book on Elliptic Curve Cryptography, which was invented by Dr. Neal Koblitz. So the book said - whatever is in the next 200 pages is considered trivial by mathematicians working in number theory. If you write it in the form of equations, this entire book will occupy less than half a page. It is basically a lemma and a few theorems. But this book is 200 pages long. Why ? Because it tells you how to implement that lemma and those theorems using C++.
So that's how that is.
Just yesterday I described to an intern how to generate the nth term of a Halton sequence in base k. So if you want the 17th term in base 3, well, decimal 17 = ternary 122, reflect 122 to get 221, then ternary 0.221 = decimal 0.926. So the answer is 0.926. Its very, very simple. High school math. The nth halton term is in fact given by a 1-line equation in mathematics.
Now he came back with scala code to do the same thing.
Look at this monster:
def Halton( n:Int, b:Int):Seq[Double] = {(1 to n).map( x=>Integer.toString(x,b).reverse.zipWithIndex.map(y=>(y._1-'0')*pow(b, -(y._2+1))).sum)}
Now it works & its functional programming & computes a million Halton terms in any base in 5 seconds and so on, but still, look at it. Is it anywhere close to the one line equation ? If I express what I want declaratively, will it be any simpler ? Not really. Why not ? Because a declaration like "1..n" means an imperative loop, a declaration like "convert 17 in decimal to ternary" means a whole bunch of divisons and remainders and aggregation, then a reflect means reversing a string, which implicitly means iterating over a character array and allocating new space for the reversed result, then a reconvert ternary to decimal means an iteration with powers of 10, where a power means other iteration over multiplication....jesus! This simple 1-line equation in math becomes hundreds of thousands of loops in practice. There's no getting around that. If you've gotten around it, you've just invented math!
I imagine that the book might as well have used another (simpler) language. Now, as I see it, to understand the math, you need quite a lot of domain knowledge. A formula doesn't make sense out of context. Most statements written in programming languages do that, in a much higher degree.
Therefore, to actually do the ECC, I think it's quicker just to read the language specification of your (simple) language, than actually understand all of the math being the formulas. Granted, you wouldn't understand WHY it works. And that's my point. Comparing math to programming languages is like comparing apples to oranges.
They talk about "active" or "runnable" maths. The programming languages they create aim to basically mirror mathematical expressions. This in turn makes the programming stack much smaller and easier to comprehend.
That function definition is a monstrosity because it is poorly factored. Assuming pre-existing fromBase and toBase functions, here is a definition that in my opinion is easily readable and matches your verbal description:
halton b n = fromBase b (reverse digits) / b^(length digits)
where digits = toBase b n
Just to show there's nothing up my sleeve, here are the fromBase and toBase definitions:
toBase b 0 = []
toBase b n = (n `mod` b) : toBase b (n `div` b)
fromBase b [] = 0
fromBase b (n:ns) = n + b * fromBase b ns
They too read like how a mathematician would define them. (I abstained from use of foldr/unfoldr to make this clear.)
Edit: On second thought, it's easy to implement it as a direct recursion. I'll demonstrate it in C so I'm not accused of language chauvinism:
double halton(int b, int n)
{
return (n == 0) ? 0.0 : (n % b + halton(b, n / b)) / b;
}
Here the digit reversal is implicit in the recursion (the oldest programmer trick in the book).
This C code is self-contained and compiles to a tiny handful of machine code instructions, so it's hard to see how your statement that "this simple 1-line equation in math becomes hundreds of thousands of loops in practice" holds much water.
The only reason it's one line in math is that the rest of math is implicitly hiding in your brainstate. If you could extract that out it would be much bigger and uglier much like your expansion of this code into loops and memory manipulation, etc.
But what's your point? Code can do more wide ranging things and does so with fewer available symbols (no superscript for pow() operations), so it's wordier, but really it's not so far different. It may take a computer 200 pages of explained C++ but it takes a child months and years of schooling.
“Computer generate for me the sequence of all possible steps I could take; highlight moves that results in high economic and emotional payoff. Feel free to use alpha beta pruning and dynamic programming to reduce the time taken to polynomial time. Also, constrain possible moves to reflect my personal proclivities. Also, highlight a path were I'm dating Alicia Keys and Drake is with Nicki Minaj.. hate to see him beg on a music video.” [1]
My dream programming language should be able to run this. Good luck.
So, over the years I've played with many things that claim to be "declarative", and here's why I now shy away from them like the plague. There's no such thing as "declarative". No matter what you type into the computer, at some point it's going to turn into instructions that do the thing you want done. Trying to create a declarative language is a way of making it extraordinarily opaque as to what the machine is actually going to do. It looks great in four lines, it crashes and burn on any real sized problem, because you inevitably hit the following sequence:
1. I encounter a problem; a performance issue or a bug.
2. I can not practically proceed past this point because everything I might need to figure out what is going on has been "helpfully" obscured from me.
Yes, you can still thrash and flail but this hardly constitutes a "fix" to programming. You simply can not help but create an abstraction that not only leaks like a sieve, but is actually multiple leaky sieves layered on top of each other in opaque ways. (And letting us see in is in its own way a failure case too, with these goals.)
Part of what I like about Haskell is that it helps bridge the gap, but doesn't actually go too far. A map call is still ultimately an instruction to the machine. It's not quite the same type of instruction you give in C or C++, what with it being deferred until called for (lazy) etc, but it's still an instruction and it can be followed down to the machine if you really need to without only marginally more work than any other "normal" language. (It may be a bit bizarre to follow it down all the way, but hardly more so than C++ in its own way.)
Contrast this to SQL, which is declarative, and you never have to worry about what the database is doing to answer your question. Except it never works that way and you inevitably must actually sit there and learn how indexes work and how queries are parsed and how the optimizer works to a fairly deep level and then sit there on every interesting query and work out which synonymous query will tickle the optimizer into working properly except that you actually can't do that and you end up having to turn to weird annotated comments in the query specific to your database and then you still end up having to break the query into three pieces and manually gluing them together in the client code.
And I don't even care to guess how many man-millenia have been poured into that declarative language trying to make it go zoom on a subproblem much simpler than general purpose computing. (Well, except isasmuch as they've more or less grown to encompass that over the years, but it's still at least meant to be a query language.)
So, if you think you can fix that problem, have fun and I wish you the very best of luck, no sarcasm. This is the problem I've seen with the previous attempts to go down this route before, and I feed this back in the spirit of helping you refine your thoughts rather than yelling at you to stop.
What if you created a declarative language which allows you to override the algorithms in a functional/imperative? You could create a public algorithm repo that auto-pulls into your local machine on setup. Could search for algorithms by declarations. That would be a lot of reuse.
The issue here is that function definition doesn't tell what the function does. So you may have hundred implementations of sorting algorithms in different libraries, and neither compiler nor the IDE know that they all do the same thing. So when you write
sort(myCollection)
you are still referring to one particular set of instructions. The system parent poster envisions (the way I understand it) would be along those lines:
* User gives SPECIFICATION of sort, along the lines OP writes about in his blog.
* Other contributors provide various implementations which satisfy the specification. Such system would either have to auto-prove that implementation meets specification or just trust contributors that it does.
* Then in your code you can write sort(myCollection) and the system would pick the best implementation.
I think to have a truly declarative language that doesn't just dissolve into obscure commands at some point requires the language to have a true understanding of human language. Which to currently do well even just for answering questions requires Watson levels of computing power.
I think human language sucks at giving commands. Yes human language is very expressive but its very easy to misunderstand each other. With code its always your fault if it dosn't do what you want, you exprest it wrongly. With human language you the error can be on both ends.
> Trying to create a declarative language is a way of making it extraordinarily opaque as to what the machine is actually going to do. It looks great in four lines, it crashes and burn on any real sized problem,
Erlang, Haskell and Ocaml are examples of declarative languages, and they all have been used to solve very real-sized problems: telecommunication switches, compilers, trading systems, a window manager, etc.
It amazes me how the argument above is still repeated (often followed by "but those systems don't count, give me an example of X".)
I love OCaml, but I would hardly call it a declarative language. You still describe the steps to perform an algorithm, rather than the result of the algorithm. The article poster references Haskell and explicitly says "The functional approach brings indeed several improvements over regular imperative or object-oriented programming. But still it’s not the solution."
The argument forwarded for considering them declarative is that their compilers perform transforms on the source code, and that there are no side-effects.
I certainly agree with your interpretation more. Typical functional programming isn't really declarative (though, yes, moreso than imperative programs are) and those waters shouldn't be muddied.
I don't think there's any inherent problem with stuff being declarative. We just need the software to be smart enough to handle it well. We might have a long way to go till we can do this effectively.
I'd suggest looking at 'declarative' from the point of view of delegation (not in the technical sense, but the usual sense of getting someone else to do a task for you). Ideally you want to specify what you want to be done and you shouldn't care about how it's done. Software is meant to be a labor saving device.
I assume you're ok with the idea of delegating tasks to people. If the software was smart enough I think it'd reasonable to delegate to it as well.
SQL is declarative, and that's it's strength. The optimization, indexing, and other tweaking of the implementation is separated from the code that declares the result needed.
I'm not convinced you can really separate those things in a practical context. Inevitably you end up with a leaky abstraction and the opaqueness of what's actually going on makes it harder to diagnose.
I think declarative is the right default, since it shows the intent over the mechanics, but I deeply distrust any system that won't let me be very specific about the mechanics if I need to be.
The problem is not that SQL is slow, the problem is people push the system until it becomes slow.
It's just as easy to write 'JOIN this billion row table with that billion row table' as it is to forget how hard that is. We may complain that creating indexes is painful, but take some huge complex and slow query and try recreating it in C++ correctly and at least as fast and you quickly enter a world of pain.
PS: It's awesome to be able to write something and then optimize it without worrying that you are going to break something. When it comes to efficiency being able to select performance trade-offs even in an arcane fashion beats testing everything from scratch by a huge margin.
The problem is that most SQL engines have commands for fine-tuning. Things like 'ignore index', for instance. That is a leaky abstraction - knowing the details of the system lets the programmer do better than the query analyzer. Similarly, sometimes a left join + null check performs better than a "where not exists ()" subquery, despite them serving identical purposes.
If you can change how you phrase a query and get different performance, while keeping the same semantic meaning, your language isn't just leaking, it's hemorrhaging. It may still be useful, perhaps world-changingly so, but it's a perfect example of the dangers of declarative programming.
As to 'try making it in C++': with a library for doing so with as much maturity as SQL? Sure. It'd probably be reasonably simple, if more verbose. And when it inevitably runs slowly, you can infer the reason for why A runs faster than B relatively simply, because it's doing precisely what you told it to do.
You have a point, declarative approaches almost never delivers as promised, which is "you don't have to worry about implementation".
In reality, as you say, you end up with edge cases where you still need to dive into the implementation in order to find out what's happening.
I don't think it's a good enough argument to dismiss the whole paradigm though. Im prefectly happy with my declarative regular expressions that work 90% of the time, and rather take the hit debugging those hairy 10% that end up not working well, than writing my own imperative parser every time and repeatedly deal with those off by one errors etc..
When you say "it never works" I suspect you really mean "it never works in 100% on the cases".
Jerf, thanks so much for sharing your thoughts. I think I agree with all your views. They are taken from the real experience of trying those approaches. And I am grateful that you provide the feedback. I and anyone tackling this steep mountain need all the help we can get.
I am sure that inspectability/debuggability are two of the big issues with such an approach. When things fail, the more magic there is, the more difficult it is to fix it. It's even difficult to understand what's happening!
I do think that there is a gap there. You can specify things and have the environment apply your spec. If it's totally naive, like Prolog's "slowsort", it will take exponential time and be impractical for real-world cases. But if strategies can be found and/or devised, and applied, which get some efficiency, it can be practical for many things. When things fall apart, it's clear that powerful debuggers will be needed. A lot of work will be needed on the tools, similar to SQL Query Strategy Inspectors, etc... maybe even professionals specializing just in this. But I think that it will finally allow us to write code in a sane way. Even if armies of professionals have to come after the fact to tweak it so that it's usable, the same as for SQL.
I totally understand what you see as adavantageous in Haskell. I think that same "it's turtles all the way down", where you can inspect and debug every step, is the reason that Haskell cannot gain the power that I am after. Prolog can't either, for other reasons.
I believe a fundamentally different approach is needed. And that's what I'm trying to sketch out.
And thanks to you and many other people hopefully we can learn whether there is something there or there isn't, and if there is, hopefully reach some useful result!
161 comments
[ 4.2 ms ] story [ 203 ms ] thread[1] http://en.wikipedia.org/wiki/Superoptimization
At the very least, a constraint programming language would be a good basis to start with here.
http://en.wikipedia.org/wiki/Constraint_programming
But Prolog is far from the last word on the subject. For one, it is basically untyped. There are dependently-typed programming languages that can express non-trivial properties via types, which the compiler can check (see ezyang's example).
See also:
http://stackoverflow.com/questions/2829347/a-question-about-...
(More detailed thoughts left as a comment on the post itself.)
I'd like it if we could get to the point where you say very plainly what you want in your native language (English for me), and then that is interpreted and perhaps more questions are asked by the program until it can implement what you meant. Obviously the problem of NLP is a massive one that will likely never have a perfect solution. There are also the problems of logical inference (if you think this is easy, look up the CyC project). I don't think we should let the current constraints of technology hold us back from designing something better, however.
The future isn't going to be programming digital machines anyhow. Its going to be programming living matter.
But that's another story.
What you have is fabulous and immediately useful: You are describing a language for describing constraints on the results of computer programs.
In other words, you can express the correctness of a computer program and check whether a program is, in fact, correct.
It’s true that IF a sufficiently smart compiler could infer a working program from the definition of correctness, no further “programming” would be required. However, we don’t have that yet, and in fact I’m not urging you to write it.
Instead, consider the benefits of your language just the way it is. You can use it to write test suites. You can embed it in other languages to express design-by-contract.
It looks valuable in its current form.
http://www.haskell.org/haskellwiki/Introduction_to_QuickChec...
The system was an "animator" for formal specifications called Possum: http://ww2.cs.mu.oz.au/~tmill/tgf/index.html
Possum would allow you to directly execute a program that was formally defined using the Sum formal specification language. While it was not able to handle every possibility, I found using it to be a really magical experience.
However, in practical terms, the idea of declarative programming has just as many difficulties as ordinary programming: how do you know your specification is correct? how do you debug a logical expression? how do you know your specification matches what you want it to do?
I know declarative doesn't solve the problem of correctness. It's really difficult to define correctness per se! But what such an approach really gains is that you can forget about off-by-one errors, unforeseen cross-conditions in stupid details, so much repetitive code, etc... you will still have the higher-level problems of programming, the efficiency problems, the spec-correctness problems, etc... but nowadays you have those, plus the nitty-gritty details of programming in our paleolitic languages!
I know there are a few initiatives in this area, I really want to have an everyday tool that allows using that kind of approach for everyday problems. It will just make everything so much better for us programmers!
http://web.mac.com/ben_moseley/frp/paper-v1_01.pdf
They say that the only essential complexity is the one inherent to the problem the program is trying to solve. Everything else is just here because we haven't yet found the methodology or invented the tools to battle it.
They also describe an ideal world, where all the programming is done in way of declarative programming - what you want the code to do, and not how to do it.
Don't you have to (at the very least) tell the compiler how to do things? To reuse the example from the article: when you tell your friend to get you a beer, at some point your friend has learned HOW to get you a beer. Similarly the compiler will need to know HOW to do things that you declare. Sure it will be great when we can just tell the compiler that we need this list sorted in reverse alphabetical order but at some point someone is going to have to program the sorting algorithm on the back end.
Am I way off or are we just talking about a hypothetical future when compilers are (even more) black boxed and we don't have to think about them anymore?
SQL is probably the primary example. Prolog is also well-known.
It does this by using backtracking, which is really interesting in itself if you're not familiar with it.
See: http://wambook.sourceforge.net/
This paper is highly regarded by some smart people, but every time I've tried to read it I've seen nothing of much value - only some obvious platitudes about complexity (including the bit about complexity being intrinsic to the problem vs. just the implementation), a lot of architectural gobbledygook (complete with boxes-and-lines diagrams), and some hand-waving about combining the functional and relational models. Has anything ever come of this? Specifically, any working systems?
Clojure's lispy (simple implementation, syntax), FP (reduced state), easier concurrency, agents + stm are all influenced by this paper.
Perhaps I just don't get it, but I'm a little miffed at having tried several times to absorb the gems of wisdom in that paper and come up with nothing that isn't obvious (even the idea of functional programming over relational data is obvious) and that couldn't have been said less pretentiously in easily a tenth of the space - ironically, for a paper about minimizing complexity.
1) accidental complexity is the source of a large number of bugs 2) implicit, unnecessary, tightly-coupled state is the cause of a significant number of bugs. 3) mostly-functional programming reduces the amount of state in 2 4) RDMS databases, with transactions and triggers, are a good way of reducing state as well
Clojure applies all of these lessons. lisp reduces accidental complexity in the language. FP reduces accidental complexity wrt to state. the STM and agents are close analogues to DB transactions and triggers.
"even the idea of functional programming over relational data is obvious". Yes, but where else has that been tried?
To use the language of the op, it will be composed of many discrete simple assertions that excruciatingly specify the output.
What something starts like this it usually translates to: "I don't understand pragmatic hardware/complexity/market etc constaints and engineering compromises".
Under the mess of spaghetti code that anything out there is now, I see a clean structure of code trying to come out. I want to help it come out to the surface.
I am not sure we are at the stage where the computer can be trusted with the "what". Most new learners need to be told step by step the "how" and computers seem to be at that stage. Prolog is a nice counter-example, but even it can get itself into some real trouble.
I agree programming is broken, and I agree the whole program knowledge is just painful, but I am think there are some steps before full declarative. As much as I dislike the old VB, it did have a very vibrant component market. That concept didn't seem to evolve or make it to the server. I look at Mongrel2 and wonder if the component approach could be applied. Regardless, I think the biggest problem is lack of ability to separate the pieces of a big project effectively no matter the eventual solution.
Or maybe a spreadsheet (http://philip.greenspun.com/panda/databases-choosing).
What I'm interested in is making proof assistants easier to use by improving their inference capabilities, so programmers can verify the correctness of their programs without having to put in orders of magnitude more work...
But it will not help when the constraints are elsewhere: memory, network, CPU, heterogeneous interoperability; all still relevant in these times of mobile and distributed computing. When you are operating to these other constraints, you need control - or rather, consistency and predictability - over the consumption of those other resources. It's no good having a magic compiler that can turn your specification into an implementation, if you don't know whether the implementation will run in O(1) or O(n) space or time, what kind of constant factors are involved, and how easily you can tweak the tradeoffs when you hit one constraint or another.
I concur with raganwald's comment: this is more useful for proving, static analysis, testing, etc.
Furthermore, I'm pessimistic that you'll see substantial improvements in expressibility using your approach, particularly when you try to scale it above simple functional (by which I mean stateless input to output) problems. The reason is that programming is an exercise in attention to detail while simultaneously keeping the large in mind; and your focus won't change this fundamental nature. Writing a complete specification for a program rivals writing an imperative implementation in complexity (soup to nuts, I'm not talking about high-level DSLs here, which is an approach equally applicable to the imperative route). I expect a good compiler will swamp you with the inconsistencies of your hidden, unstated assumptions.
For example, I note that your sorting specification doesn't specify whether or not the sort is stable; I think that makes it incomplete, and also it's a tricky constraint to encode.
It's like the switch from assembly to C, or from manual memory management to automatic memory management. You lose something. You gain something else. The new approach is not valid for everything, but for some/many cases, it's much better.
Yes, the spec of a complete program will still be a great amount of work. The default resulting code will probably be slow. But you will be able to "describe" the program (in many cases), and you will be able to optimize it later without risking the correctness. Hopefully that can be a great aid and tool in many cases. We'll see, and I hope to have a lot of help along the way doing it publicly!
BTW, if what comes out is just a good new approach to static code analysis / formal specification / etc... it will have been worth it. But I do hope to find a usable tool at the end of this quest :)
If this is the kind of issue that can come up in a really simple task, what kind of issues will emerge as things scale up?
> I expect a good compiler will swamp you with the inconsistencies of your hidden, unstated assumptions.
Thank you, this is exactly what I came here to say.
The entire practice of programming is formally defining how everything works, and the devil is always in the details. The effort of going through those details thoroughly and defining exactly what you want to the program to do in all situations is, simply, the act of programming itself.
The best you can do is create languages, libraries, frameworks to help you do it more efficiently.
one thing everyone who is hating on the idea is missing is that if one compiler somewhere finds a solution on the Pareto front, for a sub-problem, that pattern can be uploaded to the cloud and re-used by other compilers. this would over time tend to help with the practical problem of how to conserve resources in the face of such a hard overall problem.
Commands like "instantiate new object", "add items to object", "do an sql query", "run sql query", "sum the integers", suck. These commands will be represented in 3d space like a flow chart with general directives. When you want to "zoom in" on one of the boxes, you can see the particulars of how it takes place. Zooming out shows you a perfect representation of the general directives, zooming in takes you to the nitty gritty commands, and zooming in further shows you the bits being shifted around on the hardware.
Wrong attribution. That tweet was originally by Ryan Gordon (@icculus).
many customers don't want correct programs, they want cheap programs. Some people in finance care about correctness, maybe you should check them out.
I am not after correctness per-se. I am actually more after "cheapness" at least in programmer time. But I do think a lot of the programmer time is spent in things that a solution-describing approach removes, and correctness gets a ride.
Hopefully I am in a right path in that direction!
You repeat yourself like this several times in your article, and I find it tedious.
I understand that you don't want to specify the steps to achieving the goal but the steps directly impacts running time.
In your particular example, a compiler could produce a program with the correct output but runs extremely slowly even for small arrays (by simply trying all permutations until it finds one satisfying your constraints, or even worse, randomizes the entries until the constants are satisfied ("bogo sort")).
Furthermore, there are undecidable problem for which the output is easy to specify but no program could exist. For example, deciding if an input piece of code will loop indefinitely.
In your article, you've mixed needless overhead (the dummy/local swapped variable comes to mind) and the steps needed to specify an algorithm.
If you only want to remove the overhead (and thus, some source of mistakes you've pointed out), you could aim for a language where the algorithms are easier to specify.
In the bubble sort case, the code would look something like.
(You can almost do this in Python already which seems to be where the syntax is inspired from. I can elaborate if interested.)Ultimately, I have to agree with other comments saying this will be more useful for checking than specifying a program.
[EDIT: fixed code formatting]
But it turns out, there is another way we can say this property, if our relation is transitive: all we need to say is that the element is less than or equal to the first element of the list.
And for any non-trivial specification, there are literally dozens of ways of specifying it, all of which happen to be identical. Which one do you pick? Which one is easier to use? Hard to say, in general.
Source: http://coq.inria.fr/stdlib/Coq.Sorting.Sorted.html
also, i didn't completely follow the final example, but you might find that category theory is relevant. related, it's not completely clear to me why you're not happy with functional programming. in a sense what academic functional programmers are doing is what you want your software to do. they're just not smart enough to put it in a compiler yet. i think. for example http://www.fing.edu.uy/inco/cursos/proggen/Articulos/sorting... (isn't that kinda what you want?)
So that's how that is.
Just yesterday I described to an intern how to generate the nth term of a Halton sequence in base k. So if you want the 17th term in base 3, well, decimal 17 = ternary 122, reflect 122 to get 221, then ternary 0.221 = decimal 0.926. So the answer is 0.926. Its very, very simple. High school math. The nth halton term is in fact given by a 1-line equation in mathematics.
Now he came back with scala code to do the same thing. Look at this monster:
def Halton( n:Int, b:Int):Seq[Double] = {(1 to n).map( x=>Integer.toString(x,b).reverse.zipWithIndex.map(y=>(y._1-'0')*pow(b, -(y._2+1))).sum)}
Now it works & its functional programming & computes a million Halton terms in any base in 5 seconds and so on, but still, look at it. Is it anywhere close to the one line equation ? If I express what I want declaratively, will it be any simpler ? Not really. Why not ? Because a declaration like "1..n" means an imperative loop, a declaration like "convert 17 in decimal to ternary" means a whole bunch of divisons and remainders and aggregation, then a reflect means reversing a string, which implicitly means iterating over a character array and allocating new space for the reversed result, then a reconvert ternary to decimal means an iteration with powers of 10, where a power means other iteration over multiplication....jesus! This simple 1-line equation in math becomes hundreds of thousands of loops in practice. There's no getting around that. If you've gotten around it, you've just invented math!
Therefore, to actually do the ECC, I think it's quicker just to read the language specification of your (simple) language, than actually understand all of the math being the formulas. Granted, you wouldn't understand WHY it works. And that's my point. Comparing math to programming languages is like comparing apples to oranges.
Also, the STEPS project in general (read the progress reports): http://www.vpri.org/html/writings.php
They talk about "active" or "runnable" maths. The programming languages they create aim to basically mirror mathematical expressions. This in turn makes the programming stack much smaller and easier to comprehend.
Edit: On second thought, it's easy to implement it as a direct recursion. I'll demonstrate it in C so I'm not accused of language chauvinism:
Here the digit reversal is implicit in the recursion (the oldest programmer trick in the book).This C code is self-contained and compiles to a tiny handful of machine code instructions, so it's hard to see how your statement that "this simple 1-line equation in math becomes hundreds of thousands of loops in practice" holds much water.
But what's your point? Code can do more wide ranging things and does so with fewer available symbols (no superscript for pow() operations), so it's wordier, but really it's not so far different. It may take a computer 200 pages of explained C++ but it takes a child months and years of schooling.
My dream programming language should be able to run this. Good luck.
[1] http://chestergrant.posterous.com/your-favorite-programmer-d...
1. I encounter a problem; a performance issue or a bug.
2. I can not practically proceed past this point because everything I might need to figure out what is going on has been "helpfully" obscured from me.
Yes, you can still thrash and flail but this hardly constitutes a "fix" to programming. You simply can not help but create an abstraction that not only leaks like a sieve, but is actually multiple leaky sieves layered on top of each other in opaque ways. (And letting us see in is in its own way a failure case too, with these goals.)
Part of what I like about Haskell is that it helps bridge the gap, but doesn't actually go too far. A map call is still ultimately an instruction to the machine. It's not quite the same type of instruction you give in C or C++, what with it being deferred until called for (lazy) etc, but it's still an instruction and it can be followed down to the machine if you really need to without only marginally more work than any other "normal" language. (It may be a bit bizarre to follow it down all the way, but hardly more so than C++ in its own way.)
Contrast this to SQL, which is declarative, and you never have to worry about what the database is doing to answer your question. Except it never works that way and you inevitably must actually sit there and learn how indexes work and how queries are parsed and how the optimizer works to a fairly deep level and then sit there on every interesting query and work out which synonymous query will tickle the optimizer into working properly except that you actually can't do that and you end up having to turn to weird annotated comments in the query specific to your database and then you still end up having to break the query into three pieces and manually gluing them together in the client code.
And I don't even care to guess how many man-millenia have been poured into that declarative language trying to make it go zoom on a subproblem much simpler than general purpose computing. (Well, except isasmuch as they've more or less grown to encompass that over the years, but it's still at least meant to be a query language.)
So, if you think you can fix that problem, have fun and I wish you the very best of luck, no sarcasm. This is the problem I've seen with the previous attempts to go down this route before, and I feed this back in the spirit of helping you refine your thoughts rather than yelling at you to stop.
We have that. They're called libraries. If I need to sort a collection, I don't write an imperative chunk of code, I just do:
Looks pretty declarative to me.sort(myCollection)
you are still referring to one particular set of instructions. The system parent poster envisions (the way I understand it) would be along those lines:
* User gives SPECIFICATION of sort, along the lines OP writes about in his blog.
* Other contributors provide various implementations which satisfy the specification. Such system would either have to auto-prove that implementation meets specification or just trust contributors that it does.
* Then in your code you can write sort(myCollection) and the system would pick the best implementation.
Erlang, Haskell and Ocaml are examples of declarative languages, and they all have been used to solve very real-sized problems: telecommunication switches, compilers, trading systems, a window manager, etc.
It amazes me how the argument above is still repeated (often followed by "but those systems don't count, give me an example of X".)
I certainly agree with your interpretation more. Typical functional programming isn't really declarative (though, yes, moreso than imperative programs are) and those waters shouldn't be muddied.
I'd suggest looking at 'declarative' from the point of view of delegation (not in the technical sense, but the usual sense of getting someone else to do a task for you). Ideally you want to specify what you want to be done and you shouldn't care about how it's done. Software is meant to be a labor saving device.
I assume you're ok with the idea of delegating tasks to people. If the software was smart enough I think it'd reasonable to delegate to it as well.
You just shifted the complexity with one sentence, it doesn't make it any easier.
I was pointing out that it's a worthwhile longterm goal, but one that requires sophisticated software to achieve.
I think declarative is the right default, since it shows the intent over the mechanics, but I deeply distrust any system that won't let me be very specific about the mechanics if I need to be.
It's just as easy to write 'JOIN this billion row table with that billion row table' as it is to forget how hard that is. We may complain that creating indexes is painful, but take some huge complex and slow query and try recreating it in C++ correctly and at least as fast and you quickly enter a world of pain.
PS: It's awesome to be able to write something and then optimize it without worrying that you are going to break something. When it comes to efficiency being able to select performance trade-offs even in an arcane fashion beats testing everything from scratch by a huge margin.
If you can change how you phrase a query and get different performance, while keeping the same semantic meaning, your language isn't just leaking, it's hemorrhaging. It may still be useful, perhaps world-changingly so, but it's a perfect example of the dangers of declarative programming.
As to 'try making it in C++': with a library for doing so with as much maturity as SQL? Sure. It'd probably be reasonably simple, if more verbose. And when it inevitably runs slowly, you can infer the reason for why A runs faster than B relatively simply, because it's doing precisely what you told it to do.
In reality, as you say, you end up with edge cases where you still need to dive into the implementation in order to find out what's happening.
I don't think it's a good enough argument to dismiss the whole paradigm though. Im prefectly happy with my declarative regular expressions that work 90% of the time, and rather take the hit debugging those hairy 10% that end up not working well, than writing my own imperative parser every time and repeatedly deal with those off by one errors etc..
When you say "it never works" I suspect you really mean "it never works in 100% on the cases".
I am sure that inspectability/debuggability are two of the big issues with such an approach. When things fail, the more magic there is, the more difficult it is to fix it. It's even difficult to understand what's happening!
I do think that there is a gap there. You can specify things and have the environment apply your spec. If it's totally naive, like Prolog's "slowsort", it will take exponential time and be impractical for real-world cases. But if strategies can be found and/or devised, and applied, which get some efficiency, it can be practical for many things. When things fall apart, it's clear that powerful debuggers will be needed. A lot of work will be needed on the tools, similar to SQL Query Strategy Inspectors, etc... maybe even professionals specializing just in this. But I think that it will finally allow us to write code in a sane way. Even if armies of professionals have to come after the fact to tweak it so that it's usable, the same as for SQL.
I totally understand what you see as adavantageous in Haskell. I think that same "it's turtles all the way down", where you can inspect and debug every step, is the reason that Haskell cannot gain the power that I am after. Prolog can't either, for other reasons.
I believe a fundamentally different approach is needed. And that's what I'm trying to sketch out.
And thanks to you and many other people hopefully we can learn whether there is something there or there isn't, and if there is, hopefully reach some useful result!