patternModerate
Applicative-order languages don't support constant time array writes? If not, why not?
Viewed 0 times
whyorderwritesconstantlanguagesarraytimeapplicativenotdon
Problem
I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:
Efficiency is a great challenge in Mathematica, due to its applicative
model of computation (it does not support constant-time write
operations to arrays) and the overhead of interpretation (as opposed to compilation).
I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called). But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes. I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.
If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time? Why would the order of evaluation matter in determining array write time?
I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.
Efficiency is a great challenge in Mathematica, due to its applicative
model of computation (it does not support constant-time write
operations to arrays) and the overhead of interpretation (as opposed to compilation).
I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called). But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes. I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.
If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time? Why would the order of evaluation matter in determining array write time?
I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.
Solution
Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a purely functional style of programming.
In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.
There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates to all versions. You can make (externally) pure data structures that provide constant time lookup and update for the latest versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.
While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.
In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.
There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates to all versions. You can make (externally) pure data structures that provide constant time lookup and update for the latest versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.
While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.
Context
StackExchange Computer Science Q#95876, answer score: 12
Revisions (0)
No revisions yet.