CMSC 330: Organization of Programming Languages Type Systems, Names & Binding CMSC 330 2 Topics Covered Thus Far ! " Programming languages •" Ruby •" OCaml ! " Syntax specification •" Regular expressions •" Context free grammars ! " Implementation •" Finite automata (scanners) •" Recursive descent parsers CMSC 330 3 Language Features Covered Thus Far ! " Ruby •" Implicit declarations { x = 1 } •" Dynamic typing { x = 1 ; x = “foo” } ! " OCaml •" Functional programming add 1 (add 2 3) •" Type inference let x = x+1 ( x : int ) •" Higher-order functions let rec x = fun y -> x y •" Static (lexical) scoping let x = let x = … •" Parametric polymorphism let x y = y ( ‘a -> ‘a ) •" Modules module foo struct … end CMSC 330 4 Programming Languages Revisited ! " Characteristics •" Artificial language for precisely describing algorithms •" Used to control behavior of machine / computer •" Defined by its syntax & semantics ! " Syntax •" Combination of meaningful text symbols !" Examples: if, while, let, =, ==, &&, + ! " Semantics •" Meaning associated with syntactic construct !" Examples: x = 1 vs. x == 1CMSC 330 5 Comparing Programming Languages ! " Syntax •" Differences usually superficial !" C / Java if (x == 1) { … } else { … } !" Ruby if x == 1 … else … end !" OCaml if (x = 1) then … else … •" Can cope with differences easily with experience !" Though may be annoying initially •" You should be able to learn new syntax quickly !" Just keep language manual / examples handy CMSC 330 6 Comparing Prog. Languages (cont.) ! " Semantics •" Differences may be major / minor / subtle •" Explaining these differences a major goal for 330 •" Will be covering different features in upcoming lectures Physical Equality Structural Equality Java a == b a.equals(b) C a == b *a == *b Ruby a.equal?(b) a == b OCaml a == b a = b Programming Language Paradigms ! " Imperative programming •" Assignment statements heavily used ! " Functional programming •" Function calls, higher-order functions ! " Object-oriented ! " You can do any of these in most languages •" But, some languages may make this easier/harder CMSC 330 7 CMSC 330 8 Explicit vs. Implicit Declarations ! " Explicit declarations •" Variables must be declared before used •" Examples !" C, C++, Java, OCaml ! " Implicit declarations •" Variables do not need to be declared •" Examples !" RubyCMSC 330 9 Type vs. Untyped Languages ! " Typed language •" Operations are only valid for specified types !" 2 * 3 = 6 !" “foo” * “bar” = undefined •" Helps catch program errors !" Either at compile or run time ! " Untyped language •" All operations are valid for all values •" Treat all values as sequences of 0’s and 1’s •" Example !" Assembly languages, FORTH CMSC 330 10 Static vs. Dynamic Types ! " Static types •" Before program is run !" Type of all expressions are determined •" Usually by compiler !" Disallowed operations cause compile-time error ! " Static types may be manifest or inferred •" Manifest – specified in text (at variable declaration) !" C, C++, Java, C# •" Inferred – compiler determines type based on usage !" ML, OCaml CMSC 330 11 Static vs. Dynamic Types (cont.) ! " Dynamic types •" While program is running !" Type of all expressions determined •" Values maintain tag indicating type !" Disallowed operations cause run-time exception ! " Dynamic types are not manifest (obviously) •" Examples !" Ruby, Python, Javascript, Lisp, Scheme ! " Most static type systems have some dynamic aspects •" Null pointers, array bounds, downcasts, etc CMSC 330 12 Weak vs. Strong Typing ! " Weak typing •" Allows one type to be treated as another •" …or provides (many) implicit casts !" C int i = 0xdeadbeef ; int *p = (int *) i; *p = 42; /* write to absolute address */ •" Main examples: C, C++ !" Helps make certain kinds of low-level systems programming easier !" But, pervades language, makes it easy to make mistakes even in code that doesn’t need this abilityCMSC 330 13 Weak vs. Strong Typing (cont.) ! " Strong typing •" Prevents one type to be treated as another !" Either statically, dynamically, or both •" Also known as type-safe •" Examples !" Java, OCaml, Ruby, Perl, Javascript, etc ! " Consensus: Strong typing is good •" Most languages have an “escape hatch” for those instances where you need weak typing !" In OCaml, Obj.magic : ’a -> ’b CMSC 330 14 Weak/Strong vs. Static/Dynamic Types ! " How do these properties interact? •" Weak/strong & static/dynamic are orthogonal •" Some literature confuse strong & static type ! " Strong / static types •" More work for programmer •" Catches more errors at compile time ! " Weak / dynamic types •" Less work for programmer •" More errors occur at run time Polymorphism ! " We’ve seen three kinds of polymorphism •" A feature of type systems in which one value can have many different types ! " Ad-hoc polymorphism (overloading) •" Ex: + in C, method overloading in Java ! " Subtype polymorphism •" Ex: subclassing in Java ! " Parametric polymorphism •" Ex: OCaml ’a, Java generics CMSC 330 15 More Language Features Coming Up ! " Names and binding •" Namespaces, scoping ! " Parameter passing mechanisms •" Call-by-{value, reference, name} ! " Parallelism support •" Thread creation •" Shared-memory concurrency •" Message passing CMSC 330 16CMSC 330 17 Names and Binding ! " Programs use names to refer to things •" E.g., in x = x + 1, x refers to a variable ! " A binding is an association between a name and what it refers to •" int x; /* x is bound to a stack location containing an int */ •" int f (int) { ... } /* f is bound to a function */ •" class C { ... } /* C is bound to a class */ •" let x = e1 in e2 (* x is bound to e1 *) CMSC 330 18 Name Restrictions ! " Languages often have various restrictions on names to make lexing and parsing easier •" Names cannot be the same as keywords in the language •" OCaml function names must be lowercase •" OCaml type constructor and module names must be uppercase •" Names cannot include special characters like ; , : etc !" Usually names are upper- and lowercase letters, digits, and _ (where the first character can’t be a digit) !" Some languages also allow more
View Full Document
Unlocking...