When I first started working with the Go language, my impression was that it was a better version of C. A C with strings, with better enums, and most importantly a C without a preprocessor.
All of those aspects are true, but I'm not sure that the "origin language" of Go was C.
I say this after reading Kernighan's 1981 paper "Why Pascal is not my Favorite Programming Language". In it, he lists the major deficiencies of Pascal, including types, fixed-length arrays (or the absence of variable-length arrays), lack of static variables and initialization, lack of separate compilation (units), breaks from loops, order of evaluation in expressions, the detection of end-of-line and end-of-file, the use of 'begin' and 'end' instead of braces, and the use of semicolons as separators (required in some places, forbidden in others).
All of these criticisms are addressed in the Go language. It is as if Kernighan had sent these thoughts telepathically to Griesemer, Pike, and Thompson (the credited creators of Go).
Now, I don't believe that Kernighan used mind control on the creators of Go. What I do believe is somewhat more mundane: Kernighan, working with Pike and Kernighan on earlier projects, shared his ideas on programming languages with them. And since the principal players enjoyed long and fruitful careers together, they were receptive to those ideas. (It may be that Kernighan adopted some ideas from the others, too.)
My conclusion is that the ideas that became the Go language were present much earlier than the introduction of Go, or even the start of the Go project. They were present in the 1980s, and stimulated by the failings of Pascal. Go is, as I see it, a "better Pascal", not a "better C".
If that doesn't convince you, consider this: The assignment operator in C is '=' and in Pascal it is ':='. In Go, the assignment operators (there are two) are ':=' and '='. (Go uses the first form to declare new variables and the second form to assign to existing variables.)
In the end, which language (C or Pascal) was the predecessor of Go matters little. What matters is that we have the Go language and that it is a usable language.
Showing posts with label language design. Show all posts
Showing posts with label language design. Show all posts
Wednesday, November 8, 2017
Tuesday, April 15, 2014
Integer Arithmetic Considered Harmful
The general trend of programming has been one of increasing safety in our tools. From machine language to assembly language, from FORTRAN to BASIC, from C to C++ to Java, our languages have relieved programmers from tedious chores and prevented them from doing the wrong thing.
Assembly language was better than machine language. It allowed the use of mnemonics for opcodes and symbols for memory locations. Programmers could more easily remember "ADD B" than "0x80" and "JMP ENDLOOP" instead of "0xC3 0x3F2A" -- especially when revisions moved ENDLOOP's location from 0x3F2A to 0x3F35.
Structured programming languages (Algol, Pascal, C, and others) improved on the GOTO statement in FORTRAN and BASIC. Loops built of while and for were much easier to read (and maintain) than loops built with GOTO.
Through it all, the one element that has remained unchanged is integer arithmetic. Integer arithmetic has been available since before COBOL and FORTRAN, and has remained unchanged up to Java, C#, and even Python (well, Python 2). It is the shark of the computing world, something that evolved to an efficient form and has not changed.
Integer arithmetic provides fast operations for addition, subtraction, multiplication, and division. They operate over a domain specific to the underlying hardware; most modern PCs and servers use 64-bit integers while recent hardware used 32-bit integers. (Really old hardware like the original IBM PC used 16-bit integers.)
Integer arithmetic on computers is not quite the same as the mathematician's integer arithmetic. Mathematicians have an infinite supply of integers which allows them to perform lots of calculations that are not available to computers. Mathematicians can work with integers of arbitrarily large values, where computers are limited to a hardware-specific domain. For 16-bit processors, that domain is 0 to 65535; for 32-bit processors it is 0 to 4,294,967,295.
The domain limits are important. They constrain your calculations; any value larger than the maximum "wraps around" and starts at zero. For a 16-bit processor, the sum of 65530 and 10 is not 65540 (a number outside the range) but 5.
Similarly, subtraction wraps at zero "back" to the high end. On a 32-bit processor, the value 5 subtracted from 3 is not -2 (again, outside the range) but 4,294,967,293.
Some languages have signed integers which allow for negative values. This is a mere sleight-of-hand, shifting the domain. For 16-bit integers, signed integers operate over the range -32768 to 32767; for 32-bit processors the range is from −2,147,483,648 to 2,147,483,647. The starting and ending ranges change but the number of numbers, the number of different values, remains the same. The "wrap" effect is still present; it simply happens at different points. An unsigned integer can compute "3 minus 5" and provide the result -2, but on a 16-bit processor the sum of 32760 and 10 is -32766.
This wrapping often happens silently. While processors have built-in hardware to indicate an overflow (usually a status flag than can be checked with an additional operation) our compilers generally ignore such overflows. They generate code that silently wraps values past the minimum and maximum values.
Compilers also allow for the conversion of signed integers to unsigned integers, and also for the reverse. For many values this conversion is harmless, but for others it can cause problems. Converting a signed integer 5 to an unsigned integer provides the desired result of 5. Converting signed integer -5 to an unsigned integer provides the result -65534 on a 16-bit processor and −2,147,483,643 on a 32-bit processor. Are these the desired values? The answer is not always clear.
Integer arithmetic is dangerous because values wrap silently at the end of the range of values.
Compounding the problem is our use of integers for indexes into arrays. Access operations for arrays occurs in one of three typical cases: We are iterating over the entire array, iterating over a subset, or we are accessing one specific element in the array. In each case, we manipulate an index value (an integer) to "point" to the desired element or elements. Correct execution depends on the index value; an incorrect index value will yield incorrect results.
Which brings me back to the general trend in programming languages, the trend towards safety. Integer arithmetic is inherently dangerous. Values can overflow (or underflow) with no warning. Programmers have been taught to "program defensively" and "guard against errors" when writing integer operations, but not all of them do. The result is that many of our programs have defects, some more harmful than others, some more subtle than others.
We have long avoided changes to integer arithmetic in our languages. The reasons are several. The current (unsafe) operations are fast, and there is no call for slower operations. The current (unsafe) compiler outputs are correct, and adding checks may introduce other changes. Changing the compilers now would break lots of existing code. These are all good reasons.
Despite those reasons, I see changes to integer arithmetic.
Run-time checks for integer operations Pascal and Ada have such checks; I expect other languages to adopt them. Integer operations that result in overflow or underflow will throw exceptions (for languages that have exceptions).
Checked conversions Conversions from signed to unsigned (or unsigned to signed) will be checked at run-time. Errors will throw an exception.
Hard-to-code conversions Conversions from signed to unsigned (or unsigned to signed) will be harder to code, probably required a specific cast.
Implementations of integers than allow for arbitrarily large values Python 3 handles this now. Python 3 uses "normal" integers for values that fit within an integer range, and a custom integer for values outside of that range. This design eliminates the problems of "wrapping".
New types to implement a limited-range integer for indexing Arrays will allow indexing with only a specific type of index, not a plain "int". This type might be constructed at run-time, since the size of the array may be known only at run-time.
Not all of these changes need be implemented in any one language. The run-time checks for integer operations and the use of arbitrarily large values may "overlap" in that they both solve the problem of exceeding a range.
These changes will meet with some resistance. Changes for safety often do; many decry the performance of the safe operations. Despite the nay-sayers, changes for safety often do work their way into languages. I expect these changes to become part of the standard for our popular languages.
Assembly language was better than machine language. It allowed the use of mnemonics for opcodes and symbols for memory locations. Programmers could more easily remember "ADD B" than "0x80" and "JMP ENDLOOP" instead of "0xC3 0x3F2A" -- especially when revisions moved ENDLOOP's location from 0x3F2A to 0x3F35.
Structured programming languages (Algol, Pascal, C, and others) improved on the GOTO statement in FORTRAN and BASIC. Loops built of while and for were much easier to read (and maintain) than loops built with GOTO.
Through it all, the one element that has remained unchanged is integer arithmetic. Integer arithmetic has been available since before COBOL and FORTRAN, and has remained unchanged up to Java, C#, and even Python (well, Python 2). It is the shark of the computing world, something that evolved to an efficient form and has not changed.
Integer arithmetic provides fast operations for addition, subtraction, multiplication, and division. They operate over a domain specific to the underlying hardware; most modern PCs and servers use 64-bit integers while recent hardware used 32-bit integers. (Really old hardware like the original IBM PC used 16-bit integers.)
Integer arithmetic on computers is not quite the same as the mathematician's integer arithmetic. Mathematicians have an infinite supply of integers which allows them to perform lots of calculations that are not available to computers. Mathematicians can work with integers of arbitrarily large values, where computers are limited to a hardware-specific domain. For 16-bit processors, that domain is 0 to 65535; for 32-bit processors it is 0 to 4,294,967,295.
The domain limits are important. They constrain your calculations; any value larger than the maximum "wraps around" and starts at zero. For a 16-bit processor, the sum of 65530 and 10 is not 65540 (a number outside the range) but 5.
Similarly, subtraction wraps at zero "back" to the high end. On a 32-bit processor, the value 5 subtracted from 3 is not -2 (again, outside the range) but 4,294,967,293.
Some languages have signed integers which allow for negative values. This is a mere sleight-of-hand, shifting the domain. For 16-bit integers, signed integers operate over the range -32768 to 32767; for 32-bit processors the range is from −2,147,483,648 to 2,147,483,647. The starting and ending ranges change but the number of numbers, the number of different values, remains the same. The "wrap" effect is still present; it simply happens at different points. An unsigned integer can compute "3 minus 5" and provide the result -2, but on a 16-bit processor the sum of 32760 and 10 is -32766.
This wrapping often happens silently. While processors have built-in hardware to indicate an overflow (usually a status flag than can be checked with an additional operation) our compilers generally ignore such overflows. They generate code that silently wraps values past the minimum and maximum values.
Compilers also allow for the conversion of signed integers to unsigned integers, and also for the reverse. For many values this conversion is harmless, but for others it can cause problems. Converting a signed integer 5 to an unsigned integer provides the desired result of 5. Converting signed integer -5 to an unsigned integer provides the result -65534 on a 16-bit processor and −2,147,483,643 on a 32-bit processor. Are these the desired values? The answer is not always clear.
Integer arithmetic is dangerous because values wrap silently at the end of the range of values.
Compounding the problem is our use of integers for indexes into arrays. Access operations for arrays occurs in one of three typical cases: We are iterating over the entire array, iterating over a subset, or we are accessing one specific element in the array. In each case, we manipulate an index value (an integer) to "point" to the desired element or elements. Correct execution depends on the index value; an incorrect index value will yield incorrect results.
Which brings me back to the general trend in programming languages, the trend towards safety. Integer arithmetic is inherently dangerous. Values can overflow (or underflow) with no warning. Programmers have been taught to "program defensively" and "guard against errors" when writing integer operations, but not all of them do. The result is that many of our programs have defects, some more harmful than others, some more subtle than others.
We have long avoided changes to integer arithmetic in our languages. The reasons are several. The current (unsafe) operations are fast, and there is no call for slower operations. The current (unsafe) compiler outputs are correct, and adding checks may introduce other changes. Changing the compilers now would break lots of existing code. These are all good reasons.
Despite those reasons, I see changes to integer arithmetic.
Run-time checks for integer operations Pascal and Ada have such checks; I expect other languages to adopt them. Integer operations that result in overflow or underflow will throw exceptions (for languages that have exceptions).
Checked conversions Conversions from signed to unsigned (or unsigned to signed) will be checked at run-time. Errors will throw an exception.
Hard-to-code conversions Conversions from signed to unsigned (or unsigned to signed) will be harder to code, probably required a specific cast.
Implementations of integers than allow for arbitrarily large values Python 3 handles this now. Python 3 uses "normal" integers for values that fit within an integer range, and a custom integer for values outside of that range. This design eliminates the problems of "wrapping".
New types to implement a limited-range integer for indexing Arrays will allow indexing with only a specific type of index, not a plain "int". This type might be constructed at run-time, since the size of the array may be known only at run-time.
Not all of these changes need be implemented in any one language. The run-time checks for integer operations and the use of arbitrarily large values may "overlap" in that they both solve the problem of exceeding a range.
These changes will meet with some resistance. Changes for safety often do; many decry the performance of the safe operations. Despite the nay-sayers, changes for safety often do work their way into languages. I expect these changes to become part of the standard for our popular languages.
Tuesday, April 8, 2014
Java and C# really derive from Pascal
In the history of programming, the "C versus Pascal" debate was a heated and sometimes unpleasant discussion on language design. It was fought over the capabilities of programming languages.
The Pascal side advocated restrictive code, what we today call "type safe" code. Pascal was designed as a teaching language, a replacement for BASIC that contained the ideas of structured programming.
The C side advocated liberal code, what we today call "unsafe code". C was designed not to teach but to get the job done, specifically systems programming jobs that required access to the hardware.
The terms "type safe" and "unsafe code" are telling, and they give away the eventual resolution. C won over Pascal in the beginning, at kept its lead for many years, but Pascal (or rather the ideas in Pascal) have been gaining ground. Even the C and C++ standards have been moving towards the restrictive design of Pascal.
Notable ideas in Pascal included:
Notable ideas in K&R C:
It's hard to define a clear victor in the C/Pascal war. Pascal got a boost with the UCSD p-System and a large boost with the Turbo Pascal IDE. C was big in the Unix world and also big for programming Windows. Today, Pascal is viewed as a legacy language while C and its derivatives C++, Java, and C# enjoy popularity.
But if C won in name, Pascal won in spirit. The early, liberal K&R C has been "improved" with later standards that limit the ability to implicitly convert data types. K&R C was also enhanced with the 'const' keyword for variables. C++ introduced classes which allow programmers to build their own data types. So do Java and C#, and they eliminate pointers, check array indexes, and standardize operations across platforms. Java and C# are closer to the spirit of Pascal than C.
Yes, there are differences. Java and C# use braces to define blocks, where Pascal used 'BEGIN' and 'END'. Pascal declares variables with the name-and-then-type sequence, while C, Java, and C# use the type-and-then-name sequence. But if you look at the features, especially those Pascal features criticized as reducing performance, you see them in Java and C#.
We had many debates about the C and Pascal programming languages. In the end, it was not the "elegance" of a language or the capabilities of the IDE that solved the argument. Advances in technology neutralized many of our objections. Faster processors and improvements in compilers eliminated the need for speed tricks and allowed for the "performance killing" features in Pascal. And without realizing it, we adopted them, slowly, quietly, and with new names. We didn't adopt the name Pascal, we didn't adopt the syntax of Pascal, but we did adopt the features of Pascal.
The Pascal side advocated restrictive code, what we today call "type safe" code. Pascal was designed as a teaching language, a replacement for BASIC that contained the ideas of structured programming.
The C side advocated liberal code, what we today call "unsafe code". C was designed not to teach but to get the job done, specifically systems programming jobs that required access to the hardware.
The terms "type safe" and "unsafe code" are telling, and they give away the eventual resolution. C won over Pascal in the beginning, at kept its lead for many years, but Pascal (or rather the ideas in Pascal) have been gaining ground. Even the C and C++ standards have been moving towards the restrictive design of Pascal.
Notable ideas in Pascal included:
- Structured programming (blocks, 'while' and 'repeat' loops, 'switch/case' flows, limited goto)
- Array data type
- Array index checking at run-time
- Pointer data type
- Strong typing, including pointers
- Overflow checking on arithmetic operations
- Controlled conversions from one type to another
- A constant qualifier for variables
- Standard features across implementations
Notable ideas in K&R C:
- Structured programming (blocks, 'while' and 'repeat' loops, 'switch/case' flows, limited goto)
- Array data type (sort of -- really a syntactic trick involving pointers)
- No checking of array index (at compile-time or run-time)
- Pointer data type
- Strong typing, but not for pointers
- No overflow checking
- Free conversions from one type to another
- No 'const' qualifier
- Many features were implementation-dependent
For programmers coming from BASIC (or FORTRAN) the structured programming concepts, common in C and Pascal, were appealing. Yet the other aspects of the C and Pascal programming languages were polar opposites.
It's hard to define a clear victor in the C/Pascal war. Pascal got a boost with the UCSD p-System and a large boost with the Turbo Pascal IDE. C was big in the Unix world and also big for programming Windows. Today, Pascal is viewed as a legacy language while C and its derivatives C++, Java, and C# enjoy popularity.
But if C won in name, Pascal won in spirit. The early, liberal K&R C has been "improved" with later standards that limit the ability to implicitly convert data types. K&R C was also enhanced with the 'const' keyword for variables. C++ introduced classes which allow programmers to build their own data types. So do Java and C#, and they eliminate pointers, check array indexes, and standardize operations across platforms. Java and C# are closer to the spirit of Pascal than C.
Yes, there are differences. Java and C# use braces to define blocks, where Pascal used 'BEGIN' and 'END'. Pascal declares variables with the name-and-then-type sequence, while C, Java, and C# use the type-and-then-name sequence. But if you look at the features, especially those Pascal features criticized as reducing performance, you see them in Java and C#.
We had many debates about the C and Pascal programming languages. In the end, it was not the "elegance" of a language or the capabilities of the IDE that solved the argument. Advances in technology neutralized many of our objections. Faster processors and improvements in compilers eliminated the need for speed tricks and allowed for the "performance killing" features in Pascal. And without realizing it, we adopted them, slowly, quietly, and with new names. We didn't adopt the name Pascal, we didn't adopt the syntax of Pascal, but we did adopt the features of Pascal.
Wednesday, March 7, 2012
The C preprocessor is a thing of beauty
Converting programs from one language to another can be easy or difficult, depending on the languages. More specifically, the ease of conversion depends on the commonality of language features.
For example: converting a program from FORTRAN IV to C. Converting a FORTRAN program to C is easy, converting a C program to FORTRAN IV is hard. The FORTRAN constructs of subroutines and functions are easily handled in C, as are the data types of integer, real, and character. C has constructs that are unavailable in FORTRAN: pointers, dynamic memory, and recursion. The FORTRAN language elements of IF/THEN and DO are available in C, but the C elements of 'while' and 'longjmp' are not. (We have to shoe-horn the non-FORTRAN aspects of C into FORTRAN.)
When converting a program from one language to another, the difficulties of conversion are the language-specific features of the 'origin' language -- the things that the 'destination' language cannot handle.
In the past, I have considered the C preprocessor to be a hideous thing, an orc-like programming language that has no manners. But I have been wrong.
The C preprocessor (which is the same as the C++ preprocessor), has some very interesting constructs. It is a language with concepts found only in advanced programming languages. It has access to the caller's scope, something that exists in the lambdas of LISP. It can use a parameter as a substitution token, or it can substitute the text value of the token name into the program ("stringification").
These features of the C preprocessor make conversion to other languages difficult. We think of the C preprocessor as an ugly beast not because it is ugly, but because we cannot easily convert its code to another language. The preprocessor language is beautiful -- simple, elegant, and powerful. We hate it because we cannot think of it in the terms of languages that we know and love.
It may be some time before mainstream languages have the features of the C preprocessor. (I'm considering LISP outside of the mainstream, at least for now.) Until such a time, the advanced language of the preprocessor will pose conversion challenges to programmers.
For example: converting a program from FORTRAN IV to C. Converting a FORTRAN program to C is easy, converting a C program to FORTRAN IV is hard. The FORTRAN constructs of subroutines and functions are easily handled in C, as are the data types of integer, real, and character. C has constructs that are unavailable in FORTRAN: pointers, dynamic memory, and recursion. The FORTRAN language elements of IF/THEN and DO are available in C, but the C elements of 'while' and 'longjmp' are not. (We have to shoe-horn the non-FORTRAN aspects of C into FORTRAN.)
When converting a program from one language to another, the difficulties of conversion are the language-specific features of the 'origin' language -- the things that the 'destination' language cannot handle.
In the past, I have considered the C preprocessor to be a hideous thing, an orc-like programming language that has no manners. But I have been wrong.
The C preprocessor (which is the same as the C++ preprocessor), has some very interesting constructs. It is a language with concepts found only in advanced programming languages. It has access to the caller's scope, something that exists in the lambdas of LISP. It can use a parameter as a substitution token, or it can substitute the text value of the token name into the program ("stringification").
These features of the C preprocessor make conversion to other languages difficult. We think of the C preprocessor as an ugly beast not because it is ugly, but because we cannot easily convert its code to another language. The preprocessor language is beautiful -- simple, elegant, and powerful. We hate it because we cannot think of it in the terms of languages that we know and love.
It may be some time before mainstream languages have the features of the C preprocessor. (I'm considering LISP outside of the mainstream, at least for now.) Until such a time, the advanced language of the preprocessor will pose conversion challenges to programmers.
Subscribe to:
Posts (Atom)