This is a distinction often passed over or confused. Even Alan Kay and Gregor Kiczales did not make it clear:
But it is valuable to be clear about this; it helps us understand software engineering better.
Deciding on a structuring arrangement – how to design some software into classes, functions, macros, modules, etc. – is like deciding on a paper filing system.
With a different paper filing system, all the same information is there, but accessible in different ways. Different kinds of information will be suited by different filing systems. And the main part of what makes one arrangement suitable is the human manipulation: what is visible where, how many sheets to move.
This is what we are really considering when weighing up and choosing program structure. The algorithm does not change, but the convenience of human manipulation can be adjusted.
It is half of what programming is. One half – the ‘functional’ – is the more solid engineering: designing a system able to serve x web-pages per second with y storage. The other half – this ‘representational’ side – is designing a ‘paper filing system’ for us to handle all the algorithm and program pieces.
Representation is not really totally separate from function/algorithm. To have a different representation the software must have some actual difference, and that difference is going to affect execution in some way.
How separate? There does not seem to be a proof of a particular degree, because the concepts seem to be defined by that very thing. O(1) or less is what we would expect as the performance effect of representation on function – because representation changes only the algorithm itself as a static thing, it just makes certain operations etc. slower. But this really assumes the changes are not to the deeper structure of the algorithm, i.e. that the O() character is unchanged – which was what a proof would be seeking.
The exemplars are programming languages. Interpretation has an O(1) effect – although the factor is between the orders of 10 and 1000. Compilation has O(0) effect by translating-out the difference before execution – or at least it aims to, often without achieving it.
In the end this is a ‘good’ kind of separation (because it is basically linear?). Representation cost is either negligable, or easily tradeable: if it is n times slower, compensate with n times more power. And if you just wait long enough for hardware to get faster, it all just improves by itself.
It is the functional side – algorithmic performance (speed, storage, (and energy?)) – that corresponds to the products of other physical engineerings – material structures with particular weight, strength, etc. properties. The representational side – the ‘paper filing system’, i.e. what is not algorithmic performance – corresponds more to the drawing/diagram/design formats of physical engineering.
But such diagram-formats are rather more important in software. Because the manipulation of them is much enlarged: even more use, re-use, modification, and communication depends on it. A building is just used. But software can be re-used as part of many other pieces of software.
The primary point of the distinction is: separating the two helps understanding (because each side can be addressed without concern of the other). The secondary point of the distinction is: you cannot properly understand software representation by looking at other engineering's function (which is what seemed troubling with the examples from Kay and Kiczales).