On OrthogonalityALGOL68ALGOL68: Goals & HistoryKey Ideas in ALGOL68More Key IdeasALGOL68 StructureALGOL68: OrganizationData types (primitive modes)More Primitive ModesNon-primitive ("non-plain”) modesReferencesSlide 12ConsiderALGOL68 ReferencesStructuring PrimitivesMore Structured TypesContinue Structuring PrimitivesStructures:UnionsMore UnionsProceduresCoercionMore CoercionCASE ClausesContinue Cons of CASE StatementA68 Summary...A68 Summary (cont)...Slide 28Slide 29PascalPascal HistoryPascal: First ImpressionDiscriminated & Free Union Variant RecordsVariant Record ExamplesName vs Structure EquivalencePascal Scope Rules...Binding to Outer LevelCEvaluate COn Orthogonality•What makes orthogonality work?–by remembering only m + n things, we get m * n capabilities.•Orthogonality says that no point should be definable by more than one XY pair.•Orthogonality advantageous only if: m+n + e < m*n - e***mnALGOL68ALGOL68: Goals & HistoryThesis: It is good practice in programming language design to abstain from exceptions.•Design goals:–gen purpose, rigorously-defined language–Clear up trouble spots in ALGOL60• (but, Pascal more like A60 than A68 is)–orthogonality, extensibility•ALGOL68 - development started in mid-60's.–Revised report (SIGPLAN Notices, May 1977) cleared up many ambiguities.Key Ideas in ALGOL68•User type declarations (modes)•Orthogonal design (modes, structures, ops)•Reference mode (pointers of a sort)•United modes (predecessor to variant records)•Auto declaration of FOR LOOP index•User-specified operator overloading•Notion of "elaboration" on context entryMore Key Ideas• Mode requirement for formals• Casting: user-spec'd mode conversion• Redefinition of operator precedence• Collateral actions• Semaphores• W-grammars - two-level grammar• Contexts (strong, firm, meek, weak, soft)– WRT coercionALGOL68 Structure•ALGOL68 is block structured w/ static scope rules–Monolithic programming, as in ALGOL60 (and later in Pascal)•ALGOL68's model of computation:– static– stack: block/procedure AR's; local data objects– heap: “heap” -- dynamic-- data objects•ALGOL68 is an expression-oriented language–(note influence on C/C++)ALGOL68: Organization•Declarations:–Must be given (FOR LOOP index only exception)–Can name new types (modes)•Imperatives (units)–15 major unit types–Assignment is allowable side-effect of units•c.f. CData types (primitive modes)• Int }• Real }• Char } primitives• Bool }• Void }•Modes created from primitives --defined in "prelude"–String–Compl–Bits - Word full of bitsMore Primitive Modes–Bytes - Word full of chars–Sema - Semaphore–Format- I/O–File - I/O•User defined modes allowed: Mode largeint = long INT• and its attendant advantagesNon-primitive ("non-plain”) modes• references *• multiples (arrays, rows)• structures• unions *• procedures * * - unusual--can be applied to primitives or other constucted modesReferences•Variable X has two attributes of concern:–its value–reference to storage where value is kept•Most languages don't distinguish•e.g. x := x + 2 "value of x” "ref to place where value is stored"•"The type of x is integer" and "The type of values assigned to x is integer" get combined in this case.–ALGOL68 made the distinction (as do e.g. C & C++).References•INT x -- means x is a ref to objects of type INT•In general, a variable stands for reference to data object so, for: x := x + 2 "dereferenced" to yield int, so + operation is meaningful•In general, for V := E• type of V should be ref (type of E)•Thus, if we declare: REF INT PNTTOX– mode of PNTTOX is REF REF INT and PNTTOX:= X -- assigns X's address to PNTTOX• action not obvious from syntaxConsider INT x,y; -- x&y are REFs to objects of type INT REF INT r; -- r is REF to REF INTs x:= 2; r:= x; y:= r; x:= 3; y:= r; -- no deref necessary-- ditto - pointer assignment-- assigns 2 as value of y --two derefs required-- no deref necessary;-- assigns 3 to y. Two derefs req'dNo visual clue that y’s value could be affectedby assignment to x.ALGOL68 References•Note: can't do: r:= 3; -- r is REF REF INT and 3 is INT -- no coercion possible (ref int) r:= 3 -- will work. It assigns 3 to the last variable r referred to (i.e. x).•Note: can create REF REF REF ... INT, etc if so inclined.Syntactic consistency? Manifest interface?Structuring Primitives •ARRAYs (rows) -- 1D: ROW; 2D: ROW ROW;•STRUCTURES–e.g. [1:12] INT MONTH -- vector of 12 integers•On equivalence of arrays:–Objects of different dimensions -> different modes–Bounds are not part of the mode (c.f. Pascal) [1:10, 1:n] REAL time } equivalent [1:100, 7:11] REAL thing } modes.More Structured Types•Aggregate Assignmentmonth:= (31,28,31,30,31,30,31,31,30,31,30,31) --adopted in Ada and later languages•Dynamic arrays: [m:n] INT obj -- When encountered, array with n-m+1 locations created.Continue Structuring Primitives• FLEX ARRAYs -- change size on the fly.–e.g. FLEX [1:0] INT obj -- a row with no integers. obj:= (5,5,5) -- changes bounds to 1:3 on the fly. --bounds change only by assignment to whole array•Aside on strings: mode string = FLEX[1:0] CHAR -- done in prelude declaration string greetings; greetings:= "Greetings and salutations" -- creates vector exact length of string.Structures:• e.g. mode bin_tree = struct( INT data, REF bin_tree l_child, r_child ) ^ note recursive definition ( illegal definition w/o REF) -- Why?•Other standard modes built up from structs:–e.g. mode compl = struct ( REAL re, im ) mode bits = struct ( [1:bits_width] BOOL x ) mode bytes = struct ( [1:bytes_width] CHAR x ) mode sema = struct ( REF INT x ) -- all in ALGOL68 preludeUnions• e.g. mode combine = UNION ( INT, BOOL ) . . . combine x -- x can take on INT or BOOL values but-- only under controlled conditions.• assignment is OK: x:= 5 x:= TRUEMore Unions•Using x in an expression requires: CASE x IN -- "conformity clause" (INT x1): ... <use x1> (BOOL x2): ... <use x2> ESAC•Note: UNION (t1, t2, ..., tn) -- ti can be any mode. -- Only limitation: can't have ti