An assignment questions asks the following:
Consider an array 'var a : array[1..10] of real'. Express the semantics of this array as a function, defining the domain and codomain (you might also be able to write the rule). In this programming language, the subrange '1..10' is viewed as a genuine type, so we can comfortably say that 'a[13]' is a type error.
I've come up with a semantic that works as a function, that is: f(a[$x$]) -> $y$ where $x$ is a type defined by the numbers $1$ to $10$ and $y$ is the set of all Real numbers. Does this seems correct?
Would there be any difference if I wrote the function in the opposite way, that is: f($y$) -> a[$x$] ?
Asked By : CodyBugstein
Answered By : Uday Reddy
First of all, an array is and has always been a function. It is a function from the set of indices (1..10 in your example) to memory locations that hold the array elements. When we write $a[i]$ in the programming language, we are just using stylized notation for saying $a(i)$, i.e., apply the function $a$ to $i$ and give me the location that it represents. When we write $$a[i] := a[i] + 1$$ we are using the memory location $a(i)$ both on the left and the right hand side of the assignment statement. On the left, it means the location itself (also called an L-value) and, on the right, it means the contents of the location (also called an R-value).
So, treating is an array as a function is no big deal. It is like calling a spade a spade.
However, what your professor wants you to do is to think of the array as a function from the set of indices to data values (like real numbers). No memory locations in the picture. That involves a bit more thinking and some rethinking.
In this view, $a$ is a variable whose value is an entire array value (which is now a function) and $a(i)$ is a real number. That represents the R-value of what we normally write as $a[i]$. What do we do about its L-value? Well, it doesn't exist, in this view. So, we think of an assignment to a subscripted variable, like the one I have shown as above, as really meaning an assignment to the array variable $a$, like this: $$ a := a[i: a(i)+1]$$ Here, the right hand side means "a function $a'$ that is just like $a$, except that the value of $a'(i)$ is going to be $a(i)+1$". So, we take the old function value of $a$, tweak it little to obtain a new function value, and assign it to $a$. Remarkably, with this little bit of rewriting, everything works!
It is quite remarkable that one of our most basic data structures should allow such radically different views. When we add procedures, things get a bit more complicated in the second view, because, as I said, there are no L-values for subscripted variables in this view. However, there are more abstract forms of L-values (called "acceptors") that can be used to deal with subscripted variables as procedure parameters. So, it all works fine.
For an introductory treatment of the two views, see J. C. Reynolds, Craft of Programming, Chapter 2. In particular, the introduction of the chapter, and the section 2.2.8, cover the two views.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9212
0 comments:
Post a Comment
Let us know your responses and feedback