Programming Languages PragmaticsSimple typesIntegerFloating Point (FP)Binary Coded DecimalCharacterBooleanUser-defined typesSlide 9Slide 10When Should Two Types Be Considered Equivalent?ExampleMemory management introStringsStrings - examplesStrings - representationsCompound (1) ArraysArrays – design decisionsSlide 19Arrays – operationsArrays – storageArrays – element accessArrays - multidimensionalJagged arrays(2) Associative Arrays - mapsAssociative Arrays - implementation(3) RecordsRecords - implementation(4) Pascal variant records (unions)Other unions(5) Sets (Pascal)(6) Pointers and referencesPointers (and references)Dereferencing examplePointers hold addressesPointer arithmeticBasic dynamic memory management model:Problems with pointers and dynamic memory:1Problems with pointers and dynamic memory: 2Cause of reference problemsUser management of memoryGarbage CollectionReference counting:Why Does This Fail?Garbage Collection: (mark-sweep)A sloppy java exampleManaging heap of variable-sized cellsReferencesProgramming Languages PragmaticsData TypesData TypesSimple typesSimple typesinteger floating point binary-coded decimalcharacter boolean user-defined typesusually in hardwareusually in softwarenot composed of other typeshardware or software implemented2IntegerInteger2’s complementunsignedoperations exact within rangerange depends on size of virtual cell- typical size: 1, 2, 4, 8 bytes3Floating Point (FP)Floating Point (FP)Approximate real numbers but not dense, not even “equally sparse”Languages may support at least two FP types: float and double May follow the IEEE FP-754 Standard (Java)representations and operations are approximaterange and precision depend on size of virtual cell (usually 4 or 8 bytes)1 11 52 bitsmantissaexponentsign4See excellent detailed explanation of floating pointrepresentation in the following video: http://www.youtube.com/watch?v=t-8fMtUNX1ABinary Coded DecimalBinary Coded Decimal‘exact’ decimal arithmetic, space costlydecimal digits in 4 bit coderange and precision depend on size of virtual cell – 2 digits per byte445 9 0 51 87 8defined decimal pointBytes5CharacterCharacterASCII – 128 character set – 1 byteUnicode – 2 byte extensionusually coded as unsigned integer6BooleanBoolean1 bit is sufficient but...no bit-wise addressability in hardwarestore in a byte – space inefficientstore 8 per byte – execution inefficientc: 0=false, non-zero=true7User-defined typesUser-defined typesimplemented (like character and boolean usually are) as a coding of unsigned integerenumerated type: (Pascal example)type suit = (club, diamond, heart, spade);var lead: suit;lead := heart; internally represented as { 0, 1, 2, 3 } operations: 8User-defined typesUser-defined typesimplemented as a restricted range of integersubrange type: (Ada example)subtype CENTURY20 is INTEGER range 1900..1999;BIRTHYEAR: CENTURY20;BIRTHYEAR := 1981;9User-defined typesUser-defined typesType compatibility issues:-can two enumerated types contain same constant?-can defined types be coerced with integer, with each other?10When Should Two Types Be When Should Two Types Be Considered Equivalent?Considered Equivalent?Type equivalenceTwo principal formsStructuralStructuralTwo types are equivalent if they consist of the same componentsName equivalence Name equivalence Every type declaration defines a new type so two types are the same if they have the same nameMore popular in more modern languages11ExampleExampletypedef struct {int a;int b;} Point; typedef struct {int a;int b;} Pair; Java uses name equivalence ML is more-or-less structural  C hybrid (structural except for structs)Point x;Pair y;X = y;Legal?12Memory management introMemory management introThe parser creates a symbol table of identifiers including variables:Some information, name plus more, is bound at this time and as the program is compiled by storage in symbol table:e.g. int x;--> x type: intaddr: offsetnamenametypetypeaddressaddress13StringsStringsFirst use: output formatting onlyQuasi-primitive type in most languages (not just arrays of character)- operations: initialization, substring, catenation, comparisonThe length problem: fixed or varying?No standard string model14cchar *s = “abc”;int len = strlen(s); array of char with terminal: extended syntaxlibrary of methodsStrings - examplesStrings - examplesJAVAString s = “abc”+x;s = s.substring(0,2);fixed length arrayextended syntaxclass with 70 methodsa b c 015Strings - representationsStrings - representationsfixed length and content (static)fixed length and varying content (FORTRAN)varying length and content by reallocation (java String)varying length and content by extension (java StringBuffer)Varying length and content(C)Static strLengthAddressDynamic strMaxLengthCurrLengthAddresschar*AddressIn symbol table16Compound (1)Compound (1) Arrays Arrayscollection of elements of one typeaccess to individual elements is computed at execution time by position, O(1), or O(dim)17Arrays – design decisionsArrays – design decisionsindexing:dimensions – limit? recursive?types – int, other, user defined?first index: 0, 1, variablerange checking – no(C), yes(java)syntax for subscript operator (),[]?18Arrays – design decisionsArrays – design decisionsbinding timestype, index typeindex range(ie array size), spacestaticfixed stack-dynamicstack-dynamicheap-dynamicinitial values of elementsat storage allocation? e.g. int[] x = {1,2,3};19Arrays – operationsArrays – operationson elements – based on typeon entire array as variables -- vector and matrix operations e.g.,APL- sub array (~ substring)subarray dimensions(slices)20Arrays – storageArrays – storage<array>element type, sizeindex typeindex lower boundindex upper boundaddressaddresslower boundupper bound21Arrays – element accessArrays – element access<array>element type, sizeindex typeindex lower boundindex upper boundaddressaddresslower boundiaddress of a[i] =address + (i-lower bound)*size22Arrays - multidimensionalArrays - multidimensionalcontiguous or notrow major, column major ordercomputed location of element23Jagged arraysJagged arraysImplemented as arrays of arrays<array><array>, 4index typeindex lower boundindex upper boundaddressaddress<array><array><array>, 3<array>, 3index typeindex typeindex