74

When a C program is running, the data is stored on the heap or the stack. The values are stored in RAM addresses. But what about the type indicators (e.g., int or char)? Are they also stored?

Consider the following code:

char a = 'A';
int x = 4;

I read that A and 4 are stored in RAM addresses here. But what about a and x? Most confusingly, how does the execution know that a is a char and x is an int? I mean, is the int and char mentioned somewhere in RAM?

Let's say a value is stored somewhere in RAM as 10011001; if I am the program which executes the code, how will I know whether this 10011001 is a char or an int?

What I don't understand is how the computer knows, when it reads a variable's value from an address such as 10001, whether it is an int or char. Imagine I click on a program called anyprog.exe. Immediately the code starts executing. Does this executable file include information on whether the variables stored are of the type int or char?

  • 24
    This information is totally lost at run-time. You (and your compiler) have to make sure in advance that the memory will be interpreted correctly. Is this the answer you were after? – 5gon12eder Aug 5 '15 at 19:59
  • 4
    It doesn't. Because it assumes that you know what you are doing, it takes whatever it finds at the memory address you provided, and writes it to stdout. If whatever was written corresponds to a readable character, it will eventually show up on someone's console as a readable character. If it doesn't so correspond, it will appear as gibberish, or possibly a random readable character. – Robert Harvey Aug 5 '15 at 20:21
  • 22
    @user16307 The short answer is that in statically typed languages, whenever you print out a char, the compiler will produce different code than it would for printing out an int. At runtime there is no longer any knowledge that x is a char, but it's the char-printing code that gets run, because that's what the compiler selected. – Ixrec Aug 5 '15 at 20:21
  • 13
    @user16307 It's always stored as the binary representation of the number 65. Whether it gets printed out as 65 or as A depends on the code that your compiler produced to print it out. There is no metadata next to the 65 that says it's actually a char or an int (at least, not in statically typed languages like C). – Ixrec Aug 5 '15 at 21:08
  • 2
    The fully understand the concepts you ask about here and implement them by yourself, you might want to take a compiler course, e.g. coursera's one – mucaho Aug 6 '15 at 3:12

14 Answers 14

122

To address the question you've posted in several comments(which I think you should edit into your post):

What I don't understand is how does the computer know lets when it reads a variable's value from and address such as 10001 if is an int or char. Imagine I click on a program called anyprog.exe. Immediately the code starts executing. Does this exe file include information about if the variables are stored as in or char?

So lets put some code to it. Let's say you write:

int x = 4;

And let's assume that it gets stored in RAM:

0x00010004: 0x00000004

The first part being the address, the second part being the value. When your program(which executes as machine code) runs, all it sees at 0x00010004 is the value 0x000000004. It doesn't 'know' the type of this data, and it doesn't know how it is 'supposed' to be used.

So, how does your program figure out the right thing to do? Consider this code:

int x = 4;
x = x + 5;

We have a read and a write here. When your program reads x from memory, it finds 0x00000004 there. And your program knows to add 0x00000005 to it. And the reason your program 'knows' this is a valid operation, is because the compiler ensures that the operation is valid through type-safety. Your compiler has already verified that you can add 4 and 5 together. So when your binary code runs(the exe), it doesn't have to make that verification. It just executes each step blindly, assuming everything is OK(bad things happen when they are in fact, not OK).

Another way to think of it is like this. I give you this information:

0x00000004: 0x12345678

Same format as before - address on the left, value on the right. What type is the value? At this point, you know just as much information about that value as your computer does when it's executing code. If I told you to add 12743 to that value, you could do it. You have no idea what the repercussions of that operation will be on the whole system, but adding two numbers is something you're really good at, so you could do it. Does that make the value an int? Not necessarily - All you see is two 32-bit values and the addition operator.

Perhaps some of the confusion is then getting the data back out. If we have:

char A = 'a';

How does the computer know to display a in the console? Well, there are a lot of steps to that. The first is to go to As location in memory and read it:

0x00000004: 0x00000061

The hex value for a in ASCII is 0x61, so the above might be something you'd see in memory. So now our machine code knows the integer value. How does it know to turn the integer value into a character to display it? Simply put, the compiler made sure to put in all of the necessary steps to make that transition. But your computer itself(or the program/exe) has no idea what the type of that data is. That 32-bit value could be anything - int, char, half of a double, a pointer, part of an array, part of a string, part of an instruction, etc.


Here's a brief interaction your program (exe) might have with the computer/operating system.

Program: I want to start up. I need 20 MB of memory.

Operating System: finds 20 free MB of memory that aren't in use and hands them over

(The important note is that this could return any 20 free MB of memory, they don't even have to be contiguous. At this point, the program can now operate within the memory it has without talking to the OS)

Program: I'm going to assume that the first spot in memory is a 32-bit integer variable x.

(The compiler makes sure that accesses to other variables will never touch this spot in memory. There's nothing on the system that says the first byte is variable x, or that variable x is an integer. An analogy: you have a bag. You tell people that you will only put yellow colored balls in this bag. When someone later pulls something out of the bag, then it would be shocking that they would pull out something blue or a cube - something has gone horribly wrong. The same goes for computers: your program is now assuming the first memory spot is variable x and that it is an integer. If something else is ever written over this byte of memory or it's assumed to be something else - something horrible has happened. The compiler ensures these kinds of things don't happen)

Program: I will now write 2 to the first four bytes where I'm assuming x is at.

Program: I want to add 5 to x.

  • Reads the value of X into a temporary register

  • Adds 5 to the temporary register

  • Stores the value of the temporary register back into the first byte, which is still assumed to be x.

Program: I'm going to assume the next available byte is the char variable y.

Program: I will write a to variable y.

  • A library is used to find the byte value for a

  • The byte is written to the address the program is assuming is y.

Program: I want to display the contents of y

  • Reads the value in the second memory spot

  • Uses a library to convert from the byte to a character

  • Uses graphics libraries to alter the console screen(setting pixels from black to white, scrolling one line, etc)

(And it goes on from here)

What you're probably getting hung up on is - what happens when the first spot in memory is no longer x? or the second is no longer y? What happens when someone reads x as a char or y as a pointer? In short, bad things happen. Some of these things have well-defined behavior, and some have undefined behavior. Undefined behavior is exactly that - anything can happen, from nothing at all, to crashing the program or the operating system. Even well-defined behavior can be malicious. If I can change x to a pointer to my program, and get your program to use it as a pointer, then I can get your program to start executing my program - which is exactly what hackers do. The compiler is there to help make sure we don't use int x as a string, and things of that nature. The machine code itself is not aware of types, and it will only do what the instructions tell it to do. There is also a large amount of information that's discovered at run-time: which bytes of memory is the program allowed to use? Does x start at the first byte or the 12th?

But you can imagine how horrible it would be to actually write programs like this(and you can, in the assembly language). You start off by 'declaring' your variables - you tell yourself that byte 1 is x, byte 2 is y, and as you write each line of code, loading and storing registers, you (as a human) have to remember which one is x and which one is y, because the system has no idea. And you (as a human) have to remember what types x and y are, because again - the system has no idea.

  • Amazing explanation. Only the part you wrote "How does it know to turn the integer value into a character to display it? Simply put, the compiler made sure to put in all of the necessary steps to make that transition." is still foggy for me. Lets say the CPU fetched 0x00000061 from the RAM register. From this point are you saying there are other instructions(in the exe file) which make that transition to what we see on the screen? – user16307 Aug 5 '15 at 22:00
  • 2
    @user16307 yes, there are additional instructions. Each line of code you write can potentially be turned into many instructions. There are instructions to figure out what character to use, there are instructions for which pixels to modify and what color they change to, etc. There's also code that you don't really see. For example, using std::cout means you're using a library. Your code to write to the console may only be one line, but the function(s) you call will be more lines, and each line can turn into many machine instructions. – Shaz Aug 5 '15 at 22:56
  • 8
    @user16307 Otherwise how can console or text file outputs a character instead of int Because there is a different sequence of instructions for outputting the contents of a memory location as an integer or as an alphanumeric characters. The compiler does know about the variables types, and chooses the appropriate sequence of instructions at compile time, and records it in the EXE. – Charles E. Grant Aug 6 '15 at 0:27
  • 2
    I would find a different phrase for "The byte code itself," as byte code (or bytecode) usually refers to an intermediate language (like Java Bytecode or MSIL), which might actually store of this data for the runtime to leverage. Plus it's not entirely clear what "byte code" is supposed to refer to in that context. Otherwise, nice answer. – jpmc26 Aug 6 '15 at 2:59
  • 6
    @user16307 Try not to worry about C++ and C#. What these people are saying is way above your current understanding of how computers and compilers work. For the purposes of what you're trying to understand, the hardware does NOT know anything about types, char or int or whatever. When you told the compiler some variable was an int, it generated executable code to handle a memory location AS IF it were an int. The memory location itself contains no info about types; it's just that your program decided to treat it as an int. Forget everything else you heard about runtime type information. – Andres F. Aug 7 '15 at 4:28
43

I think your main question seems to be: "If the type is erased at compile-time and not retained at runtime, then how does the computer know whether to execute code wich interprets it as an int or to execute code which interprets it as a char?"

And the answer is … the computer doesn't. However, the compiler does know, and it will have simply put the correct code in the binary in the first place. If the variable were typed as char, then the compiler wouldn't put the code for treating it as an int in the program, it would put the code to treat it is a char.

There are reasons to retain the type at runtime:

  • Dynamic Typing: in dynamic typing, type checking happens at runtime, so, obviously, the type has to be known at runtime. But C isn't dynamically typed, so the types can be safely erased. (Note that this is a very different scenario, though. Dynamic Types and Static Types aren't really the same thing, and in a mixed-typing language, you could still erase the static types and only keep the dynamic types.)
  • Dynamic Polymorphism: if you execute different code based on the runtime type, then you need to keep the runtime type around. C doesn't have dynamic polymorphism (it doesn't have any polymorphism at all, really, except in some special hard-coded cases, e.g. the + operator), so it doesn't need the runtime type for that reason. However, again, the runtime type is something different to the static type anyway, e.g. in Java, you could theoretically erase the static types and still keep the runtime type for polymorphism. Note also, that if you decentralize and specialize the type-lookup code and put it inside the object (or class), then you also don't necessarily need the runtime-type, e.g. C++ vtables.
  • Runtime Reflection: if you allow the program to reflect on its types at runtime, then you obviously need to keep the types at runtime. You can easily see this with Java, which keeps first-order types at runtime, but erases type arguments to generic types at compile time, so you can only reflect on the type constructor ("raw type") but not the type argument. Again, C doesn't have runtime reflection, so it doesn't need to keep the type at runtime.

The only reason to keep the type at runtime in C would be for debugging, however, debugging is usually done with the source available, and then you can simply look up the type in the source file.

Type Erasure is quite normal. It doesn't impact type safety: the types are checked at compile time, once the compiler is satisfied that the program is type-safe, the types are no longer needed (for that reason). It doesn't impact static polymorphism (aka overloading): once overload resolution is complete, and the compiler has picked the right overload, it doesn't need the types anymore. Types can also guide optimization, but again, once the optimizer has picked its optimizations based on the types, it doesn't need them anymore.

Retaining types at runtime is only required when you want to do something with the types at runtime.

Haskell is one of the most strict, most rigorous, type-safe statically typed languages, and Haskell compilers usually erase all types. (The exception being the passing of method dictionaries for type classes, I believe.)

  • 3
    No! Why? What would that information be needed for? The compiler outputs the code for reading a char into the compiled binary. It doesn't output the code for an int, it doesn't output the code for a byte, it doesn't output the code for a pointer, it simply outputs only the code for a char. There are no runtime decisions being made based on the type. You don't need the type. It is completely and utterly irrelevant. All relevant decisions have already been made at compile time. – Jörg W Mittag Aug 5 '15 at 22:14
  • 2
    There isn't. The compiler simply puts code for printing a char in the binary. Period. The compiler knows that at that memory address, there is char, therefore it puts the code for printing a char in the binary. If the value at that memory address for some strange reason happens to not be a char, then, well, all hell breaks loose. That's basically how a whole class of security exploits work. – Jörg W Mittag Aug 5 '15 at 22:51
  • 2
    Think about it: if the CPU somehow knew about the data types of programs, then everybody on the planet would have to buy a new CPU everytime someone invents a new type. public class JoergsAwesomeNewType {}; See? I just invented a new type! You need to buy a new CPU! – Jörg W Mittag Aug 5 '15 at 22:54
  • 9
    No. It doesn't. The compiler knows what code it has to put in the binary. There is no point in keeping this information around. If you are printing an int, the compiler will put the code for printing an int. If you are printing a char, the compiler will put the code for printing a char. Period. But it's just a bit pattern. The code for printing a char will interpret the bit pattern in a certain way, the code for printing an int will interpret the bit in a different way, but there is no way to distinguish a bit pattern which is an int from a bit pattern which is a char, it's a string of bits. – Jörg W Mittag Aug 5 '15 at 23:00
  • 2
    @user16307: "Doesnt exe file include information about what address is what type of data?" Maybe. If you compile with debug data, the debug data will include information on variable names, addresses, and types. And sometimes that debug data is stored within the .exe file (as a binary stream). But it is not part of the executable code, and it is not used by the application itself, only by a debugger. – Ben Voigt Aug 6 '15 at 21:24
12

The computer doesn't "know" what addresses are what, but the knowledge of what's what is baked into the instructions of your program.

When you write a C program that writes and reads a char variable, the compiler creates assembly code that writes that piece of data somewhere as a char, and there is some other code somewhere else that reads a memory address and interprets it as a char. The only thing tying these two operations together is the location of that memory address.

When it comes time to read, the instructions don't say "see what data type is there", it just says something like "load that memory as a float". If the address to be read from has been changed, or something has overwritten that memory with something other than a float, the CPU will just happily load that memory as a float anyway, and all kinds of weird stuff can happen as a result.

Bad analogy time: imagine a complicated shipping warehouse, where the warehouse is memory and people picking things is the CPU. One part of the warehouse 'program' places various items on the shelf. Another program goes and grabs items off the warehouse and puts them into boxes. When they are pulled off, they are not checked, they just go into the bin. The whole warehouse functions by everything working in sync, with the right items always being in the right place at the right time, otherwise everything crashes, just like in an actual program.

  • how would you explain if the CPU finds 0x00000061 at a register and fetches it; and imagine the console program supposed to output this as a character not int. do you mean that in that exe file there are some instruction codes which knows the address of 0x00000061 is a char and converts to a character by using ASCII table? – user16307 Aug 5 '15 at 22:15
  • 7
    Note that "everything crashes" is actually the best-case scenario. "Weird things happen" is the second-best scenario, "subtly-weird things happen" is even worse, and the worst-case is "things happen behind your back that someone intentionally manipulated to happen just the way they want them to", aka a security exploit. – Jörg W Mittag Aug 5 '15 at 23:04
  • @user16307: The code in the program will tell the computer to fetch that address then to display it according to whatever encoding is being used. Whether that data in the memory location is an ASCII character or complete garbage, the computer is not concerned about. Something else was responsible for setting up that memory address to have the expected values in it. I think it might benefit you to try some assembly programming. – whatsisname Aug 6 '15 at 1:08
  • 1
    @JörgWMittag: indeed. I thought about mentioning a buffer overflow as an example but decided it would just make things more confusing. – whatsisname Aug 6 '15 at 1:09
  • @user16307: The thing that displays data to screen is a program. On traditional unixen it's a terminal (a piece of software that emulates the DEC VT100 serial terminal - a hardware device with a monitor and keyboard that displays whatever that comes into its modem to the monitor and sends whatever typed on its keyboard to its modem). On DOS it's DOS (actually the text mode of your VGA card but lets ignore that) and on Windows it's command.com. Your program doesn't know that it's actually printing out strings, it's just printing out a sequence of bytes (numbers). – slebetman Aug 6 '15 at 5:31
8

It doesn't. Once C is compiled to machine code, the machine just sees a bunch of bits. How those bits are interpreted depends on what operations are being performed on them as opposed to some additional metadata.

The types you enter in your source code are just for the compiler. It takes what type you say the data is supposed to be and, to the best of its ability, tries to make sure that that data is only used in ways that make sense. Once the compiler has done as good a job as it can in checking the logic of your source code, it converts it to machine code, and discards the type data, because machine code has no way of representing that (at least on most machines).

  • What I don't understand is how does the computer know lets when it reads a variable's value from and address such as 10001 if is an int or char. Imagine I click on a program called anyprog.exe. Immediately the code starts executing. Does this exe file include information about if the variables are stored as in or char? – – user16307 Aug 5 '15 at 20:06
  • @user16307 No, there's no extra information about if something is an int or a char. I'll add some example stuff later, assuming nobody else beats me to it. – 8bittree Aug 5 '15 at 20:09
  • 1
    @user16307: The exe file contains that information indirectly. The processor executing the program doesn't care about the types used when writing the program, but much of it can be deduced from the instructions used to access the various memory locations. – Bart van Ingen Schenau Aug 5 '15 at 20:23
  • @user16307 there is actually a little extra information. The exe files knows that an integer is 4 bytes so when you write "int a" the compiler reservers 4 bytes for the a variable and can thus calculate the address of a and the other variables after. – Esben Skov Pedersen Aug 5 '15 at 20:26
  • 1
    @user16307 there is no practical difference (beside the size of the type) difference between int a = 65 and char b = 'A' once the code is compiled. – user40980 Aug 5 '15 at 21:06
6

Most processors provide different instructions for working with data of different types, so type information is usually "baked in" to the generated machine code. There's no need to store additional type metadata.

Some concrete examples might help. The machine code below was generated using gcc 4.1.2 on an x86_64 system running SuSE Linux Enterprise Server (SLES) 10.

Assume the following source code:

int main( void )
{
  int x, y, z;

  x = 1;
  y = 2;

  z = x + y;

  return 0;
}

Here's the meat of the generated assembly code corresponding to the above source (using gcc -S), with comments added by me:

main:
.LFB2:
        pushq   %rbp               ;; save the current frame pointer value
.LCFI0:
        movq    %rsp, %rbp         ;; make the current stack pointer value the new frame pointer value
.LCFI1:                            
        movl    $1, -12(%rbp)      ;; x = 1
        movl    $2, -8(%rbp)       ;; y = 2
        movl    -8(%rbp), %eax     ;; copy the value of y to the eax register
        addl    -12(%rbp), %eax    ;; add the value of x to the eax register
        movl    %eax, -4(%rbp)     ;; copy the value in eax to z
        movl    $0, %eax           ;; eax gets the return value of the function
        leave                      ;; exit and restore the stack
        ret

There's some extra stuff that follows ret, but it isn't relevant to the discussion.

%eax is a 32-bit general purpose data register. %rsp is a 64-bit register reserved for saving the stack pointer, which contains the address of the last thing pushed onto the stack. %rbp is a 64-bit register reserved for saving the frame pointer, which contains the address of the current stack frame. A stack frame is created on the stack when you enter a function, and it reserves space for the function's arguments and local variables. Arguments and variables are accessed by using offsets from the frame pointer. In this case, the memory for the variable x is 12 bytes "below" the address stored in %rbp.

In the above code, we copy the integer value of x (1, stored at -12(%rbp)) to the register %eax using the movl instruction, which is used to copy 32-bit words from one location to another. We then call addl, which adds the integer value of y (stored at -8(%rbp)) to the value already in %eax. We then save the result to -4(%rbp), which is z.

Now let's change that up so we're dealing with double values instead of int values:

int main( void )
{
  double x, y, z;

  x = 1;
  y = 2;

  z = x + y;

  return 0;
}

Running gcc -S again gives us:

main:
.LFB2:
        pushq   %rbp                              
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movabsq $4607182418800017408, %rax ;; copy literal 64-bit floating-point representation of 1.00 to rax
        movq    %rax, -24(%rbp)            ;; save rax to x
        movabsq $4611686018427387904, %rax ;; copy literal 64-bit floating-point representation of 2.00 to rax
        movq    %rax, -16(%rbp)            ;; save rax to y
        movsd   -24(%rbp), %xmm0           ;; copy value of x to xmm0 register
        addsd   -16(%rbp), %xmm0           ;; add value of y to xmm0 register
        movsd   %xmm0, -8(%rbp)            ;; save result to z
        movl    $0, %eax                   ;; eax gets return value of function
        leave                              ;; exit and restore the stack
        ret

Several differences. Instead of movl and addl, we use movsd and addsd (assign and add double-precision floats). Instead of storing interim values in %eax, we use %xmm0.

This is what I mean when I say that the type is "baked in" to the machine code. The compiler simply generates the right machine code to handle that particular type.

4

Historically, C regarded memory as consisting of a number of groups of numbered slots of type unsigned char (also called "byte", though it need not always be 8 bits). Any code which used anything stored in memory would need to know which slot or slots the information was stored in, and know what should be done with the information there [e.g. "interpret the four bytes starting at address 123:456 as a 32-bit floating-point value" or "store the lower 16 bits of the most recently computed quantity into two bytes starting at address 345:678]. The memory itself would neither know nor care what the values stored in the memory slots "meant". If code tried to write memory using one type and read it as another, the bit patterns stored by the write would be interpreted according to the rules of the second type, with whatever consequences might result.

For example, if code were to store 0x12345678 to a 32-bit unsigned int, and then attempt to read two consecutive 16-bit unsigned int values from its address and the one above, then depending upon which half of the unsigned int was stored where, the code might read the values 0x1234 and 0x5678, or 0x5678 and 0x1234.

The C99 Standard, however, no longer requires that memory behave as a bunch of numbered slots that know nothing about what their bit patterns represent. A compiler is allowed to behave as though memory slots are aware of the types of data that are stored into them, and will only allow data which is written using any type other than unsigned char to be read using either type unsigned char or the same type as it was written with; compilers are further allowed to behave as though memory slots have the power and inclination to arbitrarily corrupt the behavior of any program which tries to access memory in a fashion contrary to those rules.

Given:

unsigned int a = 0x12345678;
unsigned short p = (unsigned short *)&a;
printf("0x%04X",*p);

some implementations might print 0x1234, and others might print 0x5678, but under the C99 Standard it would be legal for an implementation to print "FRINK RULES!" or do anything else, on the theory that it would be legal for the memory locations holding a to include hardware that records what type was used to write them, and for such hardware to respond to an invalid read attempt in any fashion whatsoever, including by causing "FRINK RULES!" to be output.

Note that it doesn't matter if any such hardware actually exists--the fact that such hardware could legally exist makes it legal for compilers to generate code which behaves as though it's running on such a system. If the compiler can determine that a particular memory location will be written as one type and read as another, it can pretend that it's running on a system whose hardware could make such determination, and could respond with whatever degree of capriciousness the compiler author sees fit.

The purpose of this rule was to allow compilers which knew that a group of bytes holding a value of some type held a particular value at some point in time, and that no value of that same type had been written since, to infer that that group of bytes would still hold that value. For example, a processor had read a group of bytes into a register, and then later on wanted to use the same information again while it was still in the register, the compiler could use the register contents without having to reread the value from memory. A useful optimization. For about the first ten years of the rule, violating it would generally mean that if a variable is written with a type other than one which is used to read it, the write may or may not affect the value read. Such behavior may in some cases be disastrous, but in other cases may be harmless, especially if the code which is reading the value would be equally happy with the value written or the value held before the write, or even more so if the value written happened to match the value already held.

Around 2009, however, the authors of some compilers like CLANG have determined that since the Standard allows compilers to do anything they like in cases where memory is written using one type and read as another, compilers should infer that programs will never receive input that could cause such a thing to occur. Since the Standard says the compiler is allowed to do anything it likes when such invalid input is received, code which would only have an effect in cases where the Standard imposes no requirements may (and in the view of some compiler authors, should) be omitted as irrelevant. This changes the behavior of aliasing violations from being like memory that which, given a read request, may arbitrarily return the last value written using the same type as a read request or any more recent value written using some other type, to being like memory which will capriciously alter program behavior any time the Standard would allow it to do so.

  • 1
    Mentioning undefined behavior when type pruning to someone who doesn't understand how there is no RTTI seems counter-intuitive – Cole Johnson Aug 8 '15 at 7:17
  • @ColeJohnson: It's too bad there's no formal name or standard for the dialect of C supported by 99% of pre-2009 compilers, since from both a teaching perspective and a practical one they should be considered fundamentally different languages. Since the same name is given to both the dialect that evolved a number of predictable and optimizable behaviors over 35 years, dialect that throws out such behaviors for the supposed purpose of optimization, it's hard to avoid confusion when talking about things that work differently in them. – supercat Aug 8 '15 at 17:43
  • Historically C ran on the Lisp machines that didn't permit such loose playing with types. I'm pretty sure that many of the "predictable and optimizable behaviors" seen 30 years ago simply didn't work anywhere but BSD Unix on the VAX. – prosfilaes Aug 10 '15 at 9:20
  • @prosfilaes: Perhaps "99% of the compilers that were used from 1999 to 2009" would be more accurate? Even when compilers had options for some rather aggressive integer optimizations, they were just that--options. I don't know that I've ever seen a compiler before 1999 which didn't have a mode that didn't guarantee that given int x,y,z; the expression x*y > z would never do anything other than return 1 or 0, or where aliasing violations would have any effect other than to let the compiler arbitrarily return either an old or new value. – supercat Aug 10 '15 at 15:45
  • 1
    ...where the unsigned char values that are used to construct a type "came from". If a program were to decompose a pointer into an unsigned char[], show its hex contents briefly on the screen, and then erase the pointer, the unsigned char[], and later accept some hex numbers from the keyboard, copy them back to a pointer, and then dereference that pointer, behavior would be well-defined in the case where the number that was typed in matched the number that was displayed. – supercat Aug 10 '15 at 16:05
3

In C, it is not. Other languages (e.g., Lisp, Python) have dynamic types but C is statically-typed. That means that your program must know what type the data is to properly interpret is as a character, an integer, etc.

Usually the compiler takes care of this for you, and if you do something wrong, you'll get a compile-time error (or warning).

  • What I don't understand is how does the computer know lets when it reads a variable's value from and address such as 10001 if is an int or char. Imagine I click on a program called anyprog.exe. Immediately the code starts executing. Does this exe file include information about if the variables are stored as in or char? – – user16307 Aug 5 '15 at 20:06
  • 1
    @user16307 Essentially no, all that information is completely lost. It's up to the machine code to be designed well enough to do its job right even without that information. All the computer cares about is that there are eight bits in a row at address 10001. It is either your job or the compiler's job, case depending, to keep up with stuff like that manually while writing machine or assembly code. – Panzercrisis Aug 5 '15 at 20:15
  • 1
    Note that dynamic typing is not the only reason to retain types. Java is statically typed, but it still must retain the types, because it allows to dynamically reflect on the type. Plus, it has runtime polymorphism, i.e. method dispatch based on the runtime type, for which it also needs the type. C++ puts the method dispatch code into the object (or rather class) itself, so, it doesn't need the type in some sense (although of course the vtable is in some sense part of the type, so, really at least part of the type is retained), but in Java, the method dispatch code is centralized. – Jörg W Mittag Aug 5 '15 at 22:18
  • look at my question I wrote "when a C program executes?" arent they indirectly stored in exe file among instruction codes and eventually take places in memory? I write this for you again: If the CPU finds 0x00000061 at a register and fetches it; and imagine the console program supposed to output this as a character not int. are there in that exe file(machine/binary code) some instruction codes which knows the address of 0x00000061 is a char and converts to a character by using ASCII table? If so it means char int identifiers are indirectly in the binary??? – user16307 Aug 5 '15 at 22:53
  • If the value is 0x61 and is declared as a char (i.e., 'a') and you call a routine to display it, there will [eventually] be a system call to display that character. If you've declared it as an int and call the display routine, the compiler will know to generate code to convert 0x61 (decimal 97) to the ASCII sequence 0x39, 0x37 ('9', '7'). Bottom line: the code that is generated is different because the compiler knows to treat them differently. – Mike Harris Aug 6 '15 at 15:00
3

You have to distinguish between compiletime and runtime on the one hand and code and data on the other hand.

From a machine perspective it is no difference between what you call code or instructions and what you call data. It all comes down to numbers. But some sequences - what we would call code - do something what we find usefull, others would simply crash the machine.

The work which is done by the CPU is a simple 4 step loop:

  • Fetch "data" from a given address
  • Decode the instruction (i.e. "interpret" the number as an instruction)
  • Read an effective address
  • Execute and store results

This is called the instruction cycle.

I read that A and 4 are stored in RAM addresses here. But what about a and x?

a and x are variables, which are placeholders for the addresses, where the program could find the "content" of the variables. So, anytime the variable a is used, there is effectively the address of the content of a used.

Most confusingly, how does the execution know that a is a char and x is an int?

The execution doesn't know anyting. From what was said in the introduction, the CPU only fetches data and interprets this data as instructions.

The printf-function is designed to "know", what kind of input you are putting into it, i.e. its resulting code gives the right instructions how to deal with a special memory segment. Of course, it is possible to gnerate nonsense output: using an address, where no string is stored along with "%s" in printf() will result in nonsense output stopped only by a random memory location, where a 0 (\0) is.

The same goes for the entry-point of a programm. Under the C64 it was possible to put your programs in (nearly) every known address. Assembly-Programs were started with an instruction called sys followed by an address: sys 49152 was a common place to put your assembler code. But nothing prevented you from loading e.g. graphical data into 49152, resulting in a machine crash after "starting" from this point. In this case, the instruction cycle started with reading "graphical data" and trying to interpret it as "code" (which of course made no sense); the effects were sometmes astounding ;)

Let's say a value is stored somewhere in RAM as 10011001; if I am the program which executes the code, how will I know whether this 10011001 is a char or an int?

As said: The "context" - i.e. the previous and next instructions - help treating the data in the way we want it. From a machine perspective, there is no difference in any memory location. int and char is only vocabulary, which makes sense in compiletime; during runtime (on a assembly level), there is no char or int.

What I don't understand is how the computer knows, when it reads a variable's value from an address such as 10001, whether it is an int or char.

The computer knows nothing. The programmer does. The compiled code generates the context, which is necessary to generate meaningful results for humans.

Does this executable file include information on whether the variables stored are of the type int or char

Yes and No. The information, whether it is an int or a char is lost. But on the other hand, the context (the instructions which tell, how to deal with memory locations, where data is stored) is preserved; so implicitely yes, the "information" is implicitely available.

  • Nice distinction between compile time & runtime. – Michael Blackburn Sep 3 '15 at 15:15
2

Let us keep this discussion to the C language only.

The program you are referring to is written in a high level language like C. The computer understand machine language only. Higher level languages gives the programmer the ability to express logic in a more human friendly way which is then translated into machine code which the microprocessor can decode and execute. Now let us discuss the code you mentioned:

char a = 'A';
int x = 4;

Let us try to analyse each part:

char/int are known as data types. These tell the compiler to allocate memory. In the case of char it will be 1 byte and int 2 bytes. ( Please note this memory size is again depend upon microprocessor ).

a/x are known as identifiers. Now these are you can say "user friendly" names given to memory locations in RAM.

= tells the compiler to store 'A' at the memory location of a and 4 at memory location x.

So int/char data type identifiers are only used by the compiler and not by the microprocessor during program execution. Hence they are not stored in memory.

  • ok int/char data type identifiers are not directly stored in memory as variables, but arent they indirectly stored in exe file among instruction codes and eventually take places in memory? I write this for you again: If the CPU finds 0x00000061 at a register and fetches it; and imagine the console program supposed to output this as a character not int. are there in that exe file(machine/binary code) some instruction codes which knows the address of 0x00000061 is a char and converts to a character by using ASCII table? If so it means char int identifiers are indirectly in the binary??? – user16307 Aug 5 '15 at 22:36
  • No for CPU its all numbers. For your specific example printing on console is does not depend upon if variable is char or int. I will update my answer with detail flow of how high level program is converted into machine language till execution of program. – prasad Aug 6 '15 at 4:12
2

My answer here is somewhat simplified and will refer only to C.

No, type information does not get stored in the program.

int or char are not type indicators to the CPU; only to the compiler.

The exe created by the compiler will have instructions to manipulate ints if the variable was declared as an int. Likewise, if the variable was declared as a char, the exe will contain instructions to manipulate a char.

In C:

int main()
{
    int a = 65;
    char b = 'A';
    if(a == b)
    {
        printf("Well, what do you know. A char can equal an int.\n");
    }
    return 0;
}

This program will print its message, since the char and the int have the same values in RAM.

Now, if you are wondering how printf manages to output 65 for an int and A for a char, that is because you have to specify in the "format string" how printf should treat the value.
(For example, %c means to treat the value as a char, and %d means to treat the value as an integer; same value either way, though.)

  • 2
    I was hoping someone would use an example using printf. @OP: int a = 65; printf("%c", a) will output 'A'. Why? Because the processor doesn't care. To it, all it sees are bits. Your program told the processor to store 65 (coincidentally the value of 'A' in ASCII) at a and then output a character, which is gladly does. Why? Because it doesn't care. – Cole Johnson Aug 8 '15 at 7:21
  • but why some says here in C# case, it is not the story? i read some others comments and they say in C# and C++ the story(info on data types) is different and even CPU does not do the computing. Any ideas about that? – user16307 Aug 10 '15 at 10:27
  • @user16307 If the CPU doesn't do the computing, the program isn't running. :) As for C#, I don't know, but I think my answer applies there too. As for C++, I know my answer applies there. – BenjiWiebe Aug 10 '15 at 12:38
0

At the lowest level, in the actual physical CPU there are no types at all (ignoring the floating point units). Just patterns of bits. A computer works by manipulating patterns of bits, very, very fast.

That's all the CPU ever does, all it ever can do. There's no such thing as an int, or a char.

x = 4 + 5

Will execute as:

  1. Load 00000100 into register 1
  2. Load 00000101 into register 2
  3. IAdd register 1 to register 2, and store in register 1

The iadd instruction triggers hardware which behaves as if registers 1 and 2 are integers. If they don't actually represent integers, all kinds of things can go wrong later. The best outcome is usually crashing.

It's on the compiler to chose the correct instruction based on the types given in source, but in the actual machine code executed by the CPU, there are no types, anywhere.

edit: Note that the actual machine code does not in fact mention 4, or 5, or integer anywhere. it's just two patterns of bits, and an instruction that takes two bit patterns, assumes they're ints, and adds them together.

0

Short answer, the type is encoded in the CPU instructions the compiler generates.

Although the information about the type or size of the information is not directly stored, the compiler does keep track of this information when accessing, modifying and storing values in these variables.

how does the execution know that a is a char and x is an int?

It doesn't, but when the compiler produces the machine code it knows. An int and a char can be of different sizes. In an architecture where where a char is the size of a byte and an int is 4 bytes, then variable x is not in address 10001, but also in 10002, 10003 and 10004. When code needs to load the value of x into a CPU register, it uses the instruction for loading 4 bytes. When loading a char, it uses the instruction to load 1 byte.

How to choose which of the two instructions? The compiler decides during the compilation, it's not done at runtime after inspecting the values in memory.

Note as well that registers can be of different sizes. On Intel x86 CPUs the EAX is 32 bits wide, half of it is AX, which is 16, and AX is split into AH and AL, both 8 bits.

So if you want to load an integer (on x86 CPUs), you use the MOV instruction for integers, to load a char you use the MOV instruction for chars. They are both called MOV, but they have different op codes. Effectively being two different instructions. The type of the variable is encoded in the instruction to use.

The same thing happens with other operations. There are many instructions for performing addition, depending on the size of operands, and even if they are signed or unsigned. See https://en.wikipedia.org/wiki/ADD_(x86_instruction) which list different possible additions.

Let's say a value is stored somewhere in RAM as 10011001; if I am the program which executes the code, how will I know whether this 10011001 is a char or an int

First, a char would be 10011001, but an int would be 00000000 00000000 00000000 10011001, because they are different sizes (on a computer with the same sizes as mentioned above). But lets consider the case for signed char vs unsigned char.

What is stored in a memory location can be interpreted anyway you want. Part of the responsibilities of the C compiler is to ensure that what is stored and read from a variable is done in a consistent manner. So it's not that the program knows what's stored in a memory location, but that it agrees before hand that it will always read and write the same kind of things there. (not counting things like casting types).

  • but why some says here in C# case, it is not the story? i read some others comments and they say in C# and C++ the story(info on data types) is different and even CPU does not do the computing. Any ideas about that? – user16307 Aug 10 '15 at 10:29
0

but why some says here in C# case, it is not the story? i read some others comments and they say in C# and C++ the story(info on data types) is different and even CPU does not do the computing. Any ideas about that?

In type-checked languages like C#, the type-checking is done by the compiler. The code benji wrote:

int main()
{
    int a = 65;
    char b = 'A';
    if(a == b)
    {
        printf("Well, what do you know. A char can equal an int.\n");
    }
    return 0;
}

Would simply refuse to compile. Similarly if you tried to multiply a string and an integer (I was going to say add, but the operator '+' is overloaded with string concatenation and it might just work).

int a = 42;
string b = "Compilers are awesome.";
double[] c = a * b;

The compiler would simply refuse to generate machine code from this C#, no matter how much your string kissed up to it.

-4

The other answers are correct in that essentially every consumer device you will encounter doesn't store type information. However, there have been several hardware designs in the past (and the present day, in a research context) that use a tagged architecture -- they store both the data and the type (and possibly other information as well). These would most prominently include the Lisp machines.

I vaguely recall hearing about a hardware architecture designed for object-oriented programming that had something similar, but I can't find it now.

  • 3
    The question specifically states it is referring to the C language (not Lisp), and the C language does not store variable metadata. While it is certainly possible for a C implementation to do this, as the standard does not forbid it, in practice it never happens. If you have examples relevant to the question, please provide specific citations and provide references that relate to the C language. – user22815 Aug 6 '15 at 20:20
  • Well, you could write a C compiler for a Lisp machine, but nobody uses Lisp machines in this day and age in general. The object-oriented architecture was Rekursiv, by the way. – Nathan Ringo Aug 6 '15 at 20:31
  • 2
    I think this answer isn't helpful. It complicates things way beyond the current level of understanding of the OP. It's clear the OP doesn't understand the basic execution model of a CPU + RAM, and how a compiler translates symbolic high-level source to an executable binary. Tagged memory, RTTI, Lisp, etc, is way beyond what the asker needs to know in my opinion, and will only confuse him/her more. – Andres F. Aug 7 '15 at 4:32
  • but why some says here in C# case, it is not the story? i read some others comments and they say in C# and C++ the story(info on data types) is different and even CPU does not do the computing. Any ideas about that? – user16307 Aug 10 '15 at 10:29

protected by Community Aug 6 '15 at 19:56

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.