Reusing memory of immutable state in eager evaluation?

I'm studying purely functional language and currently thinking about some immutable data implementation.

Here is a pseudo code.

List a = [1 .. 10000]
List b = NewListWithoutLastElement a
b

When evaluating b, b must be copied in eager/strict implementation of immutable data. But in this case, a is not used anymore in any place, so memory of 'a' can be re-used safely to avoid copying cost.

Furthermore, programmer can force compiler always do this by marking the type List with some keyword meaning must-be-dispose开发者_如何转开发d-after-using. Which makes compile time error on logic cannot avoid copying cost.

This can gain huge performance. Because it can be applied to huge object graph too.

How do you think? Any implementations?

This would be possible, but severely limited in scope. Keep in mind that the vast majority of complex values in a functional program will be passed to many functions to extract various properties from them - and, most of the time, those functions are themselves arguments to other functions, which means you cannot make any assumptions about them.

For example:

let map2 f g x = f x, g x 

let apply f = 
  let a = [1 .. 10000]
  f a 

// in another file :

apply (map2 NewListWithoutLastElement NewListWithoutFirstElement)

This is fairly standard in functional code, and there is no way to place a must-be-disposed-after-using attribute on a because no specific location has enough knowledge about the rest of the program. Of course, you could try adding that information to the type system, but type inference on this is decidedly non-trivial (not to mention that types would grow quite large).

Things get even worse when you have compound objects, such as trees, that might share sub-elements between values. Consider this:

let a = binary_tree [ 1; 2; 5; 7; 9 ]
let result_1 = complex_computation_1 (insert a 6)
let result_2 = complex_computation_2 (remove a 5)

In order to allow memory reuse within complex_computation_2, you would need to prove that complex_computation_1 does not alter a, does not store any part of a within result_1 and is done using a by the time complex_computation_2 starts working. While the two first requirements might seem the hardest, keep in mind that this is a pure functional language: the third requirement actually causes a massive performance drop because complex_computation_1 and complex_computation_2 cannot be run on different threads anymore!

In practice, this is not an issue in the vast majority of functional languages, for three reasons:

• They have a garbage collector built specifically for this. It is faster for them to just allocate new memory and reclaim the abandoned one, rather than try to reuse existing memory. In the vast majority of cases, this will be fast enough.
• They have data structures that already implement data sharing. For instance, NewListWithoutFirstElement already provides full reuse of the memory of the transformed list without any effort. It's fairly common for functional programmers (and any kind of programmers, really) to determine their use of data structures based on performance considerations, and rewriting a "remove last" algorithm as a "remove first" algorithm is kind of easy.
• Lazy evaluation already does something equivalent: a lazy list's tail is initially just a closure that can evaluate the tail if you need to—so there's no memory to be reused. On the other hand, this means that reading an element from b in your example would read one element from a, determine if it's the last, and return it without really requiring storage (a cons cell would probably be allocated somewhere in there, but this happens all the time in functional programming languages and short-lived small objects are perfectly fine with the GC).