201–210 of 216 posts
Earlier quoted context omitted.
Both, the obvious example is the fibinatchi sequence f(x) = f(x-1) + f(x-2). There are lots of efficient ways of coding it but the most obvious O(n^2) approch is n depth and it can't be tail-call optimized. Granted, you can write much more efficient code that can be tail call optimized, but there complex and less obvious. There are also languages which cache previous results so the native approch becomes O(n) with fa…
> Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
PS: Feel free to look for any counter example.
Earlier quoted context omitted.
You see, i am arguing from practice and you from theory. In theory you are absolutely correct. In practice the vast majority of code is NOT written in total languages. A more likely scenario is one where somebody is using language X and, in the middle of a project they decide there's this recursion thing they read about or learned in school. And off they go. In that context. In the context of a practical world where…
> You see, i am arguing from practice and you from theory. ??? My "theory" is being extremely widely used in practice. Take a look at the Intel FDIV bug history and its consequences for example. They've been formally certifying critical parts of the hardware ever since then. Or take a look at the widely used seL4 kernel: http://ssrg.nicta.com.au/projects/seL4/ > In practice the vast majority of code is NOT written in…
The world you paint isn't the real world. The world I am considering is this one:
In other words, one where your total languages are virtually nowhere to be found. Not by a small margin, by a landslide.
So, as they say in the movies, in a world where the top 5 most used languages are C and and C derivatives and total languages are almost nowhere to be found or a thing of academia, then, yes, what I am saying is very relevant and, dare I say, true and appropriate.
And, BTW, even experienced programmers screw up recursion because it just isn't used that often. I don't want to blame newbies.
So I look at this world, as evidenced by the charts on that site and a data I am sure could be dug up on a bunch of other sites I can very easily conclude that total languages are still mostly in academia and so is safe recursion. In a world dominated by C and derivatives, recursion can be really dangerous. Bad recursion hidden inside a library can be really bad news.
Anyhow, I am done with the back and forth. I understand where you want to come from. I am just asking that you understand that the frame of reference you have constructed is not one that matches our current reality. Which means one can't say that recursion is safe because when total languages when virtually nobody, in relative terms, uses them. And then, when they do use them, you have to ask what they are using them for. Is it Academia or real world application?
Enough said. Thanks for a good discussion. I wish people were not so nasty with down-votes on HN as it detracts from trying to have a discussion based on ideas contrary to the underlying HN culture. That's just the way it is.
Earlier quoted context omitted.
> Anyway, tail call optimization only works when you can rewrite the code as a loop You cannot turn a virtual tail call into a static jump.
Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
Ok, create a loop equivalent for `(define (f g x) (g x))`.
Earlier quoted context omitted.
> You see, i am arguing from practice and you from theory. ??? My "theory" is being extremely widely used in practice. Take a look at the Intel FDIV bug history and its consequences for example. They've been formally certifying critical parts of the hardware ever since then. Or take a look at the widely used seL4 kernel: http://ssrg.nicta.com.au/projects/seL4/ > In practice the vast majority of code is NOT written in…
I think you are at a point where you just want to argue to argue because. I'll give one more spin and I am out. The world you paint isn't the real world. The world I am considering is this one: http://langpop.com/ In other words, one where your total languages are virtually nowhere to be found. Not by a small margin, by a landslide. So, as they say in the movies, in a world where the top 5 most used languages are C a…
My world is this one:
http://www.prover.com/company/press/view/?id=47
http://www.cl.cam.ac.uk/~jrh13/slides/nasa-14apr10/slides.pd...
... and so on.
And, honestly, I don't want to have anything in common with your "real world", where graduate larvae with IQ > In other words, one where your total languages are virtually nowhere to be found.
We're speaking about mission critical stuff, which is already a virtually nonexistent thing dwarfed by CRUD and all such crap.
> And, BTW, even experienced programmers screw up recursion because it just isn't used that often. I don't want to blame newbies.
I see. You did not get a single word from what I said. Pity.
Let me repeat my point again: humans are brainless scumbags. They should never be trusted with anything important. If anything can be screwed up, it will be screwed up in an epic scale. The only way to avoid an epic screwup is to exclude this brainless scum from the process, and let the immaculate formal systems do the job.
> I am just asking that you understand that the frame of reference you have constructed is not one that matches our current reality.
I'd prefer to stay away as far as possible from your reality. Mine is much better. In my reality, a code without multiple layers of formal proof would not ever be signed off for anything mission critical (although I admit that the most deadly stuff I worked with were anti-aircraft systems, nothing fancy like nuclear plants and such).
Earlier quoted context omitted.
Are you saying that if the word problem was "2 consecutive numbers and a third number that was five higher than the second number" you'd be unable to solve it? "Tricks" work for simple cases. Algebra works for all cases.
Yeah, I would be unable to solve it, given that I'm pretty sure there is no solution if we assume that "consecutive" implies integers (and I'd be curious what 'consecutive' means if we don't). If instead we made it "2 consecutive numbers and a third number that was five higher than the second number add up to 70" (i.e., 21 + 22 + 27), that's easily solved using 'tricks'. Really, the trick mention (which is what I did…
The thing is that your solution is the algebraic solution. You're simplifying an equation by balancing both sides, when you subtract four. Just from our perspective, you simplify to a still difficult state, instead of the easiest possible state.
Algebra is just a way of formally stating what you did, and then offering some simplifications that speed up the process. Or offering more powerful methods that making solving more difficult problems easier.
Earlier quoted context omitted.
Yeah, I would be unable to solve it, given that I'm pretty sure there is no solution if we assume that "consecutive" implies integers (and I'd be curious what 'consecutive' means if we don't). If instead we made it "2 consecutive numbers and a third number that was five higher than the second number add up to 70" (i.e., 21 + 22 + 27), that's easily solved using 'tricks'. Really, the trick mention (which is what I did…
You're right, my mistake. That "five higher" should have been "four higher". The thing is that your solution is the algebraic solution. You're simplifying an equation by balancing both sides, when you subtract four. Just from our perspective, you simplify to a still difficult state, instead of the easiest possible state. Algebra is just a way of formally stating what you did, and then offering some simplifications th…
I agree. That's why I said
'Really, the trick mention(ed) ... is just a rephrasing of the algebra'
Just because you do number juggling in your head rather than write it formulaically doesn't make it an inferior technique, or make it not algebra, which was my point.
Earlier quoted context omitted.
F(x) = F(x) + F(x) Eventually you hit OOM or some death limit even on a stackless language.
This is a memory leak now, not a stack overflow.
Put another way, allocating 1GB of stack space on a machine with 2GB of RAM is at worst the equivelent of using a stackless lanugage on a machine limited 1 GB of RAM.
PS: It's actually worse as stackless languages are stricly slower than actually having the equivelent stack space pre alocated and you need to put an pointer for each stack call pluss overhead for alocating memory.
Earlier quoted context omitted.
Sure, it needs bookkeeping but it's still trivial to create a loop equivalent of any tail call optimizable code that your compiler recognizes. PS: Feel free to look for any counter example.
> PS: Feel free to look for any counter example. Ok, create a loop equivalent for `(define (f g x) (g x))`.
Though the mechanical equivalent would be something like:
huge(input)
{
output, continue, current_function = f;
do{
if (current_function == f)
{input = x ; continue = true; current_function=g}
if (current_function == g)
{ output = input; continue = false;}
}while(continue);
return output;
}