icarot
Though I fully agree with you -- We need a change (which change? I'm not sure!). Hilary Clinton definitely couldn't provide any positive change; also doubt Donald Trump can, thus I apathetically voted for a different candidate than either Clinton or Trump. Yet, I fully stand behind President Trump (feels weird to say that, eh.. I know..) as our president, with our country balanced in unity. I hope for the best with his leadership of the next four years!
Attempting to talk about "Linux", as if some single operating system - lack of pluralism between commenters to handle the differences notwithstanding - is a problem with this thread.
Or, converge onto interesting problems and fail gloriously; the only way to do anything of worth.
The post comparing this to dentistry is precisely what I was thinking, except nowhere near as hilarious. I wish I was intelligent enough to write a Markov algorithm for logic that paralleled reasoning in such a way automatically. Thank you for that.
Are you sure they make that optimization? How do you know? (I'm not familiar with either code base).
Are you absolutely sure that example is O(1)? It looks O(n) to me. I'm not experienced in Haskell, by the way: disclaimer.
Each call to 'fibs' constructs a list with its first argument and the recursive call. But for all of the recursions (aka, 2nd element and on) I think they'll have to build up deferred cons operations. I'm not sure about this at all. I sound suspicious, I know, but before you say anything, look here: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html...
don't they look suspiciously similiar? In that example, you'd have needed to store a function pointer and the argument'(s) type(s) for each call, on the stack, making space usage O(n). Each call pushes to the stack.
Does the Haskell example seem similar to you? I'm really uncertain.
I notice you said "half the problem" at the end of your third paragraph there. I'm assuming the other half is that it seems foolish to save the return address for a recurse. Only the first call should save a return. I think one problem with compiler writers is that oddly they don't separate how to treat a procedure and its recursions as different cases. They just fit every procedure into the same bucket-list algorithm of 1. allocate frames 2. allocate return address.
Hence the task, should ye choose to accept, is compute the Ackermann function as an iterative process (i.e, with state variables in the recursion keeping track of which step at the process you are at). The following is the easy, non-iterative process:
(define (A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1))))))
space is O(n) to record past results in one of the two subtrees of this tree recursion at any given time, which must both be evaluated separately, and at separate times if evaluation is deterministic (not concurrent). So if you were to recast it iteratively, you'd hold an immaculate benchmark of an abstrusely deep recursion which you could run on a register machine. I'm not sure if anyone has done this.
I don't think this can be computed on a register machine. What do you girls/guys think?
Now, he has actually iterated upon that post and did not write it from scratch, which I can tell because I recognize his writing style, and he posted a very similar comment sans the phonemics and phonetics on some of HN thread 2 years back on learning languages[1].
You'll notice trends in the structure, as he moves from his relevant story, rounds around some inline-defined concepts, and finally closes with a summarized forward outlook and pitfalls to avoid. As I said, it also helps that he already had the general idea behind this organized, combined with his experience in the area of learning a Sinnitic language.
And don't believe we're so high and mighty, if tempted. We make mistakes all the time, and as I pointed above, you may not have realized that tokenadult had an outline for this already in his head. You also may not realize that he made a mistake - the consonant cluster differentiating 'speak' and 'speaks' is not grammatical (i.e., describing relations between words) but, rather, lexical (i.e., referring to different ideas). This is an incredibly minor terminology kludge. Yet how often can that happen, escaping your notice, on a comment on L2 caching? On the exact algorithmic analysis of a bloom filter? On vague theoretical concepts such as referential transparency? Ad infinitum.
Don't overthink it too much (if you get me), just write as you did above. That is precisely how you will, eventually get to tokenadult's level.
As Alan Perlis: "What you know about computing other people will learn. What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more."
What others know of X you will learn, because what's in your hands is intelligence and openness.
Peace in your journey.