10
$\begingroup$

I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of.

An example given to me, that illustrated it further, by User @chi was:

E.g. consider the task: given $(i,x_1 ,…,x_n )$ return $x_i$ . In RAM this can be solved in $O(1)$ since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$

This makes me wonder about functional languages; From my understanding, "Functional languages are intimately related to the lambda calculus" (from a comment by Yuval Filmus on here). So, if functional languages are based on lambda calculus, but they run on RAM based machines, what is the proper way to perform complexity analysis on algorithms implemented using purely functional data structures and languages?

I have not had the opportunity to read Purely Functional Data Structures but I have looked at the Wikipedia page for the subject, and it seems that some of the data structures do replace traditional arrays with:

"Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic."

In that case, the computational model would be different, correct?

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ I am definitely not an expert on this topic, but I believe I heard that 1) a lisp-like machine (with its own cost model) can simulate RAM programs with a $O(\log n)$ additional factor (this looks easy to prove), and 2) whether this factor is really needed is still an open problem. Further, it can be argued that assigning a O(1) cost to array access in the RAM model is too generous. In hardware, memory access has to traverse $O(\log n)$ gates where $n$ is the size physical memory. $\endgroup$
    – chi
    Sep 26, 2016 at 13:26
  • 1
    $\begingroup$ Also keep in mind that virtually all real-world FP languages have arrays in some form, with a guaranteed $O(1)$ access time (as in imperative languages). This is typically solved adding them as a language primitive. $\endgroup$
    – chi
    Sep 26, 2016 at 13:30
  • 1
    $\begingroup$ An example of a different computational model would be the number of beta reductions done on a lambda calculus term. In FP we are more so using a ram model dressed up as a lambda calculus, if that makes sense $\endgroup$
    – Kurt Mueller
    Sep 26, 2016 at 13:47
  • 1
    $\begingroup$ @KurtMueller Note that we can get a lambda term of size $O(2^n)$ after only $O(n)$ bete reductions. This makes the cost model of counting the number of beta unrealistic. An arguably better one could be to weigh each step by the size of the terms at hand. Yet, this is not the only possible model: optimal evaluation of lambda terms does not apply beta in the naive way, preferring some more sophisticated graph reduction machines. In such case, counting the betas would probably be not appropriate. $\endgroup$
    – chi
    Sep 26, 2016 at 15:01
  • 1
    $\begingroup$ Note that you also need to know whether your functional language is eager or lazy / strict or non-strict. I recently encountered a situation where a real-world algorithm was polynomial in Haskell (non-strict) but the naive translation to OCaml (strict) was exponential. $\endgroup$
    – Eric Lippert
    Sep 26, 2016 at 20:01

1 Answer 1

Reset to default
6
$\begingroup$

It depends on the semantics of your functional language. You can't do algorithm analysis on programming languages in isolation, because you don't know what the statements actually mean. The specification for your language needs to provide sufficiently detailed semantics. If your language specifies everything in terms of lambda calculus you need some cost measure for reductions (are they O(1) or do they depend on the size of the term you reduce?).

I think that most functional languages don't do it that way and instead provide more useful statements like "function calls are O(1), appending to the head of a list is O(1)", things like that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I believe I kind of understand your answer (the misunderstanding is most likely due to my lack of understanding in lambda calculus): You're saying you basically have to do the analysis on case by case (case being language) basis, rather than a general way, because certain operations have different meanings per language. Is my understanding correct? $\endgroup$
    – Honinbo Shusaku
    Sep 26, 2016 at 14:16
  • $\begingroup$ Yes. Your language designer needs to tell you what the things you can write in the language actually mean before you can analyze the runtime of an algorithm. $\endgroup$
    – adrianN
    Sep 26, 2016 at 14:50
  • $\begingroup$ "You can't do algorithm analysis on programming languages in isolation" - was this referring to FP languages or languages in general? If it was referring to the earlier, then how do we algorithm analysis in school in such a general manner i.e. do analysis across Java, C/C++, Python problems? Is it because they're all very similar? Or is it because the underlying data structures & ADTs are all the same and implemented in the same manner as well? Or lastly, is it because these courses are simply for the sake of education, and don't necessarily need to strictly accurate? $\endgroup$
    – Honinbo Shusaku
    Sep 27, 2016 at 15:54
  • 1
    $\begingroup$ It's true for all programming languages. To be strictly correct you first need to fix a machine model, say the RAM and (a small handful) of instructions it supports. You can only do analysis on programs using only those instructions. Then you can think of a mapping of your programming language to that machine model. Then you can analyze programs in the programming language. For a very rigorous treatment check how Knuth does it in The Art of Computer Programming. A lot of this can be simplified because of big-O hiding constants. $\endgroup$
    – adrianN
    Sep 28, 2016 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.