Language DesignCOMS W4115Katsushika Hokusai, In the Hollow of a Wave off the Coast at Kanagawa, 1827Prof. Stephen A. EdwardsFall 2003Columbia UniversityDepartment of Computer ScienceLanguage Design IssuesSyntax: how programs look•Names and reserved words•Instruction formats•GroupingSemantics: what programs mean•Model of computation: sequential, concurrent•Control and data flow•Types and data representationC HistoryDeveloped between 1969 and 1973 alongwith UnixDue mostly to Dennis RitchieDesigned for systems programming•Operating systems•Utility programs•Compilers•FiltersEvolved from B, which evolved from BCPLBCPLMartin Richards, Cambridge, 1967Typeless•Everything a machine word (n-bit integer)•Pointers (addresses) and integers identicalMemory: undifferentiated array of wordsNatural model for word-addressed machinesLocal variables depend on frame-pointer-relativeaddressing: no dynamically-sized automatic objectsStrings awkward: Routines expand and pack bytes to/fromword arraysC HistoryOriginal machine (DECPDP-11) was very small:24K bytes of memory, 12Kused for operating systemWritten when computerswere big, capital equipmentGroup would get one,develop new language, OSC HistoryMany language features designed to reduce memory•Forward declarations required for everything•Designed to work in one pass: must know everything•No function nestingPDP-11 was byte-addressed•Now standard•Meant BCPL’s word-based model was insufficientEuclid’s Algorithm in Cint gcd(int m, int n ){int r;while ((r = m % n) != 0) {m = n;n = r;}return n;}“New syle” functiondeclaration listsnumber and type ofarguments.Originally onlylisted return type.Generated code didnot care how manyarguments wereactually passed,and everything wasa word.Arguments arecall-by-valueEuclid’s Algorithm in Cint gcd(int m, int n ){int r;while ((r = m % n) != 0) {m = n;n = r;}return n;}Automatic variableAllocated on stackwhen functionentered, releasedon returnParameters &automatic variablesaccessed via framepointerOther temporariesalso stacked← IgnorednmFP → PCr → SPEuclid on the PDP-11.globl _gcd GPRs: r0–r7.text r7=PC, r6=SP, r5=FP_gcd:jsr r5, rsave Save SP in FPL2: mov 4(r5), r1 r1 = nsxt r0 sign extenddiv 6(r5), r0 r0, r1 = m ÷ nmov r1, -10(r5) r = r1 (m % n)jeq L3 if r == 0 goto L3mov 6(r5), 4(r5) m = nmov -10(r5), 6(r5) n = rjbr L2L3: mov 6(r5), r0 r0 = njbr L1 non-optimizing compilerL1: jmp rretrn return r0 (n)Euclid on the PDP-11.globl _gcd.text_gcd:jsr r5, rsaveL2: mov 4(r5), r1sxt r0div 6(r5), r0mov r1, -10(r5)jeq L3mov 6(r5), 4(r5)mov -10(r5), 6(r5)jbr L2L3: mov 6(r5), r0jbr L1L1: jmp rretrnVery naturalmapping fromC into PDP-11instructions.Complex addressing modesmake frame-pointer-relativeaccesses easy.Another idiosyncrasy:registers werememory-mapped, so takingaddress of a variable in aregister is straightforward.The Design of CTaken from Dennis Ritchie’s C Reference Manual(Appendix A of Kernighan & Ritchie)Lexical ConventionsIdentifiers (words, e.g., foo, printf)Sequence of letters, digits, and underscores, starting witha letter or underscoreKeywords (special words, e.g., if, return)C has fairly few: only 23 keywords. Deliberate: leavesmore room for users’ namesComments (between /* and */)Most fall into two basic styles: start/end sequences as inC, or until end-of-line as in Java’s //Lexical ConventionsC is a free-form language where whitespace mostlyserves to separate tokens. Which of these are the same?1+21 + 2foo barfoobarreturn thisreturnthisSpace is significant in some language. Python usesindentation for grouping, thus these are different:if x < 3:y = 2z = 3if x < 3:y = 2z = 3Constants/LiteralsIntegers (e.g., 10)Should a leading - be part of an integer or not?Characters (e.g., ’a’)How do you represent non-printable or ’ characters?Floating-point numbers (e.g., 3.5e-10)Usually fairly complex syntax, easy to get wrong.Strings (e.g., "Hello")How do you include a " in a string?What’s in a Name?In C, each name has a storage class (where it is) and atype (what it is).Storage classes:1. automatic2. static3. external4. registerFundamental types:1. char2. int3. float4. doubleDerived types:1. arrays2. functions3. pointers4. structuresObjects and lvaluesObject: area of memorylvalue: refers to an objectAn lvalue may appear on the left side of an assignmenta = 3; /* OK: a is an lvalue */3 = a; /* 3 is not an lvalue */ConversionsC defines certain automatic conversions:•A char can be used as an int•Floating-point arithmetic is always done withdoubles; floats are automatically promoted•int and char may be converted to float or doubleand back. Result is undefined if it could overflow.•Adding an integer to a pointer gives a pointer•Subtracting two pointers to objects of the same typeproduces an integerExpressionsExpressions are built from identifiers (foo), constants (3),parenthesis, and unary and binary operators.Each operator has a precedence and an associativityPrecedence tells us1 * 2 + 3 * 4 means(1 * 2) + (3 * 4)Associativity tells us1 + 2 + 3 + 4 means((1 + 2) + 3) + 4C’s Operators in Precedence Orderf(r,r,...) a[i] p->m s.m!b ˜i -i++l --l l++ l--*p &l (type) r sizeof(t)n * o n / o i % jn + o n - oi << j i >> jn < o n > o n <= o n >= or == r r != ri & ji ˆ ji | jb && cb || cb ? r : rl = r l += n l -= n l *= nl /= n l %= i l &= i l ˆ= il |= i l <<= i l >>= ir1 , r2DeclaratorsDeclaration: string of specifiers followed by a declaratorstatic unsignedbasic typez}|{int| {z }specifiers(*f[10])(int, char*)[10];| {z }declaratorDeclarator’s notation matches that of an expression: use itto return the basic type.Largely regarded as the worst syntactic aspect of C: bothpre- (pointers) and post-fix operators (arrays, functions).Storage-Class Specifiersauto Automatic (stacked), defaultstatic Statically allocatedextern Look for a declaration elsewhereregister Kept in a register, not memoryC trivia: Originally, a function could only have at mostthree register variables, may only be int or char,can’t use address-of operator &.Today, register simply ignored. Compilers try to putmost automatic variables in registers.Type Specifiersintcharfloatdoublestruct { declarations }struct identifier { declarations }struct identifierDeclaratorsidentifier( declarator ) Groupingdeclarator () Functiondeclarator [ optional-constant ] Array* declarator PointerC trivia: Originally, number and type of arguments to afunction wasn’t part of its type, thus declarator justcontained
View Full Document
Unlocking...