3 ms·

I have to say, I don't know his actual response, but he gives a hint within the article that perhaps, when one wants to get performance in algorithms, one will

by drostie 15y ago

I have to say, I don't know his actual response, but he gives a hint within the article that perhaps, when one wants to get performance in algorithms, one will start to look at the way the constraints are phrased. So when you've got to write a sort, you probably start in our hypothetical dream language by saying: "sort permutes a list so that a < b implies list[a] < list[b]." Now "permute", with predicates, is probably built into the system and the constraint solver probably turns this into a variant of bubble sort, O(n^2). [That is, when you now query list[0] it does a reverse bubble-sort by looking for the least element rather than the greatest element, moving that to the lowest position.] Now you come into this and say "hey, I've got a huge list, I need O(n log n) power." What do you use? Perhaps merge sort. "sort zips together, least-element first, the sorted first half of input and the sorted second half of input -- unless len(input) < 2, in which case it just returns the input." Zipping together on predicate p may or may not be a fundamental design element of the language. If you can establish a consistent syntax for these sorts of claims which a constraint solver can follow, then the simplicity of the constraint solver, and your ability to guess what it will do, will allow you to determine which algorithm you use to perform the same task. So it doesn't require strong AI and the programmer is still making the choice -- that's what I'm trying to say. The programmer is merely making the choice in a different framework: rather than making the choice in some wrapper for blocks of assembly language, you are making the choice in some wrapper for a constraint solver. Now let me turn from where I think you're wrong to where I think you're right: I have the feeling that you're going to see something less revolutionary than claimed, because it will be like C's inline assembler support; in this hypothetical language you can probably "drop back down" to the pre-constraint-solver level when you can't figure out how to articulate the problem with constraints. (Something like "The constraint is, it has to come from applying this function to those lists!")

SomeCallMeTim 15y ago
> "sort zips together, least-element first, the sorted first half of input and the sorted second half of input -- unless len(input) < 2, in which case it just returns the input." If you're defining the algorithm to that level of detail, then I submit that you're writing the algorithm. What you just described looked almost exactly like how it would be written in one of the more advanced current functional languages, and the OP and previous OP that he was responding to both considered functional languages to be Not Good Enough. What they're asking for is pretty much just Sufficiently Advanced Technology to Do What They Want (i.e., Magic, or strong AI). Aside from that, sort IS something that's so common that it tends to be implemented in every high level programming environment in one way or another. Baking several sorts into a language isn't odd, so I don't think "sort" is a good example, because I ALREADY can say "take this list and sort it" in any language I use. An Euler integrator isn't built in to anything but a DSL for animations or games, though. And it's one of THOUSANDS (millions?) of algorithms that a program might need -- most of which are more easily described (by the programmer) in a traditional language than by trying to jump through hoops to describe what you want in a way that you'll actually get what you want. So yes, the trivial problems could be solved by such a language -- but they're already solved by CURRENT languages. It's the hard problems where it would be hard to know how to even start to create a "describe the results" language. I think all you'd end up with is a DSL for each of the cases you thought to describe -- which, depending on the domain, could be useful for that domain. DSLs are great when they're well designed. But as someone else pointed out, you don't write a game in SQL.

by drostie 15y ago

SomeCallMeTim 15y ago

> "sort zips together, least-element first, the sorted first half of input and the sorted second half of input -- unless len(input) < 2, in which case it just returns the input." If you're defining the algorithm to that level of detail, then I submit that you're writing the algorithm. What you just described looked almost exactly like how it would be written in one of the more advanced current functional languages, and the OP and previous OP that he was responding to both considered functional languages to be Not Good Enough. What they're asking for is pretty much just Sufficiently Advanced Technology to Do What They Want (i.e., Magic, or strong AI). Aside from that, sort IS something that's so common that it tends to be implemented in every high level programming environment in one way or another. Baking several sorts into a language isn't odd, so I don't think "sort" is a good example, because I ALREADY can say "take this list and sort it" in any language I use. An Euler integrator isn't built in to anything but a DSL for animations or games, though. And it's one of THOUSANDS (millions?) of algorithms that a program might need -- most of which are more easily described (by the programmer) in a traditional language than by trying to jump through hoops to describe what you want in a way that you'll actually get what you want. So yes, the trivial problems could be solved by such a language -- but they're already solved by CURRENT languages. It's the hard problems where it would be hard to know how to even start to create a "describe the results" language. I think all you'd end up with is a DSL for each of the cases you thought to describe -- which, depending on the domain, could be useful for that domain. DSLs are great when they're well designed. But as someone else pointed out, you don't write a game in SQL.