What does "run-time representation" means in programming languages"?

808 views Asked by At

I'm taking a "Programming Languages: Design and Implementation" course and want to know what "run-time representation" means in programming languages?

1

There are 1 answers

0
Ingo On

To understand it, you need to remember that (contemporary) computers only know integral numbers (in various lengths: 1, 2, 4 or 8 bytes), IEEE floating point numbers (4 or 8 bytes) and memory addresses (pointers, 4 or 8 bytes).

Thus when you want to have a list, for example, you (or, at least the compiler writer of the language you are using) need to think about how lists will be represented (!) in memory at runtime.

One possible representation for elements of singly linked lists:

|________|________|
DataPtr   NextPtr

The list node takes two adjacent pointer sized memory words, the first one points to the actual data, the second word points to the next list node.

There are two things to note here:

  1. The representation is quite arbitrary. For example, we could switch the data and the next pointer, and this would be another representation that is as good as the former one.

  2. Consider the run-time representation of a tuple or pair. It could be:

    |________|________|

    PtrFirst PtrSecond

    that is, two memory words that hold pointers to the first and second component, respectively. Sounds familiar?

    Well, how can we tell whether two subsequent words that hold pointers represent a pair or a list element? We can't! Many of our data abstraction will end up using the same run-time representation.