Programming Languages: Design, Specification, and ImplementationAdministrativeReview: BNF, Concrete and Abstract Syntax TreesUse of typesTypesFortran ExampleFortran: Name SpacesFortran: Static and Runtime Naming; ScopeReferences: Invisible but SignificantControl flowEverything staticWhat can go wrongAlgol 60: Static and Runtime Naming; ScopeNew features in Algol 60Beyond: Algol 68; PL/I; CNew things that can go wrongProgramming Languages:Design, Specification, and ImplementationG22.2210-001Rob StromSeptember 14, 2006AdministrativeAlternative mailing address for me: [email protected]Everyone should subscribe to the class mailing list: http://www.cs.nyu.edu/mailman/listinfo/g22_2110_001_fa06Readings: Remainder of chapter 3 of Gelernter and Jagannathan; chapter 7; MIT Scheme documentationGelernter textbook: we will notify about availability of photocopied notesHomework due end of class 4 (Scheme):•Convert list of atoms to concrete tree according to the simple grammar•Convert concrete tree to abstract treeReview: BNF, Concrete and Abstract Syntax Trees( A + B * C ) * D A B C Dftfftettfeeft*+*expr ::= expr “+” term | expr “–” term | termterm ::= term “*” factor | term “/” factor | factorfactor ::= number | identifier | “(“ expr “)”Use of typesOperator overloadingPolymorphismConversionImplementation choicesError checkingDifferences: •What’s typed? The value, the container, or the name•If the name can refer to different containers must they all be the same type?TypesIntegerFloat(In COBOL: Decimal)Second-class: “Hollerith”Fortran ExampleFortran: Name SpacesGlobal•Procedures and Functions•Common BlocksStatically Scoped•VariablesName Spaces•One global name space•One per procedure/functionDynamically Scoped•NoneFortran: Static and Runtime Naming; ScopePROGRAM MAIN…COMMON/ FOO/A,B,I/ BAR/C, D/ BAZ/E, F, JDIMENSION Z(999)…CALL SWAP(W, Z(200))…SUBROUTINE SWAP(X,Y)COMMON/ FOO/OLDX /GORP/KTEMPX = XX = YY = TEMPXOLDX = TEMPX…FUNCTION N (I)COMMON/ BAZ/X/GORP/LNTEMP = I**2 – 3*I + 2N = NTEMP * L…References: Invisible but SignificantEQUIVALENCE COMMONBindingControl flow“Spaghetti” codeGOTO and assigned GOTOCan jump anywhere except:•To another procedure•Inside a DO loop from outside the loopIF tests and jumps, not blocksDO loops and jumpsEverything staticDimensions of arrays (although not necessarily visible to subroutines)Number of instances of storage blocksAll programs both static and global (except statement functions)All I/O devices static and globalWhat can go wrongSyntax problems•DO I = 1.3Passing a constant•CALL SWAP(2, 3)Unchecked BoundsUninitialized VariablesAlgol 60: Static and Runtime Naming; ScopePROCEDURE MAIN;…x := read();BEGIN INTEGER ARRAY FOO[1:X]; … j := 20; blat(j, FOO(j)); …PROCEDURE blat(x,y); BEGIN x := 1000; y:= 1000 END…INTEGER PROCEDURE random; BEGIN OWN INTEGER seed; random := seed := some new value … END…New features in Algol 60Call by nameDynamic array boundsRecursive creation of local stack variablesOwn variablesNested declarations, scopesInner proceduresBeyond: Algol 68; PL/I; CFully dynamic storage – e.g. PL/I’s storage classes:•STATIC – like FORTRAN (local & external)•AUTOMATIC – like Algol 60 non-own•CONTROLLED – dynamically allocated•X BASED(Y) – dynamically allocated with pointerNew things that can go wrongUnbounded memoryDangling references via pointersDangling