I think it is correct to say that, in the functional paradigm, you effect change by making something new (and forgetting some older things.) Regardless of the paradigm (other than self-modifying code, perhaps) programs just are, but they must be evaluated if they are to do something useful.
I will leave that last sentence as I wrote it, but it immediately leads me to wonder if functions that write functions have wandered into the self-modifying code realm?
I really agree with you. Think that there's a tension between how a computer works and how a functions operate on data.
Immutability and Referential Transparency help reduce that friction, but in the end we still have not found a real solution. That's why languages like Haskell require a bunch of gymnastics just to allow IO to be seen as pure functions.
I will leave that last sentence as I wrote it, but it immediately leads me to wonder if functions that write functions have wandered into the self-modifying code realm?