3 ms·

The example given with acceleration, velocity, and position? How is a compiler going to deal with that? With an Euler integrator, you say? (every frame, p=p+ti

The example given with acceleration, velocity, and position? How is a compiler going to deal with that? With an Euler integrator, you say? (every frame, p=p+time_scaled(v), v=v+time_scaled(a) ). Note there's an implied time, as well as frames per second, in there, but a compiler can know about time. Unless when you're saying "acceleration" you're not talking about real time, but calculating where something will be at a future time...but I digress. What about a Verlet integrator? [1] Maybe you'll also want to add springs, and Verlet works better for springs. Or maybe a Runge-Kutta [2] integrator? You can get more accuracy out of one of those. Though some people claim that a higher frequency Euler integrator can do as good of a job, possibly with more stability. And how many times per frame should the system run the integrator? Because the stability of a system can depend a lot on the interval size. In fact, you might want to experiment with different integrators, and different time intervals, to get the result that's best for your application. These are all choices that a PROGRAMMER typically needs to make, and they can be different for every problem. More than that, unless your compiler can DERIVE all of the above equations and more, at least one and probably several would need to be built in to the compiler. This "problem" hasn't been solved because, short of creating strong AI, it's not solvable. This can only work when you're writing something like a "game builder" app: A domain-specific problem solver that is designed to deal with a very specific problem -- and which is coded using a traditional approach. [1] http://en.wikipedia.org/wiki/Verlet_integration http://en.wikipedia.org/wiki/Verlet_integration [2] http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods http://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods

shasta 15y ago
This is exactly right, and why people like languages that support DSL building. You do want to let programmers encode their concerns in a natural way as outlined in the article. But then assuming that the implementation of these all of these concerns is going to handled by some super language strikes me as unrealistic. The hard problem is picking good abstractions for encoding the concerns that are amenable to efficient implementation.
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.

shasta 15y ago

This is exactly right, and why people like languages that support DSL building. You do want to let programmers encode their concerns in a natural way as outlined in the article. But then assuming that the implementation of these all of these concerns is going to handled by some super language strikes me as unrealistic. The hard problem is picking good abstractions for encoding the concerns that are amenable to efficient implementation.

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.