CS363 Midterm Slides .pdf

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Bachelor of Science in Computer Science CS363 Principles of Programming Languages Week 2 Describing Syntax and Semantics Contents 1.Programming Domains 2. Language Evaluation Criteria 3. Influences on Language Design 4. Language Categories 5. Language Design Trade-Offs 6. Implementation Methods 7. Programming Environments 8. Define the terms syntax and semantics 9. Discuss the most common method of describing syntax, context-free grammars (BNF) Weekly Learning Outcomes 1. Explain reasons why software developers should study general approaches to language design and evaluation 2. Describe the major programming domains 3. Discuss the two major influences on language design: machine architecture and program design methodologies 4. Introduce the major categories of programming languages 5. Describe a few of the most important trade-offs that must be - considered during language design 6. Define the terms syntax and semantics 7. Discuss the most common method of describing syntax, contextfree grammars (BNF) 5 Required Reading Chapter 1 + Chapter 3 (3.1 – 3.3) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Reasons for Studying Concepts of Programming Languages Increased ability to express ideas Improved background for choosing appropriate languages Increased ability to learn new languages Better understanding of significance of implementation Better use of languages that are already known Overall advancement of computing Evaluation Criteria: Writability Simplicity and orthogonality Few constructs, a small number of primitives, a small set of rules for combining them Support for abstraction The ability to define and use complex structures or operations in ways that allow details to be ignored Expressivity A set of relatively convenient ways of specifying operations Strength and number of operators and predefined functions 1-8 Evaluation Criteria: Reliability Type checking Testing for type errors Exception handling Intercept run-time errors and take corrective measures Aliasing Presence of two or more distinct referencing methods for the same memory location Readability and writability A language that does not support “natural” ways of expressing an algorithm will require the use of “unnatural” approaches, and hence reduced reliability 1-9 Programming Domains Scientific applications Large numbers of floating point computations; use of arrays Fortran Business applications Produce reports, use decimal numbers and characters COBOL Artificial intelligence Symbols rather than numbers manipulated; use of linked lists LISP Systems programming Need efficiency because of continuous use C Web Software Eclectic collection of languages: markup (e.g., HTML), scripting (e.g., PHP), general-purpose (e.g., Java) Language Evaluation Criteria Readability: the ease with which programs can be read and understood Writability: the ease with which a language can be used to create programs Reliability: conformance to specifications (i.e., performs to its specifications) Cost: the ultimate total cost Evaluation Criteria: Readability Overall simplicity A manageable set of features and constructs Minimal feature multiplicity Minimal operator overloading Orthogonality A relatively small set of primitive constructs can be combined in a relatively small number of ways Every possible combination is legal Data types Adequate predefined data types Syntax considerations Identifier forms: flexible composition Special words and methods of forming compound statements Form and meaning: self-descriptive constructs, meaningful keywords Evaluation Criteria: Cost Training programmers to use the language Writing programs (closeness to particular applications) Executing programs Reliability: poor reliability leads to high costs Maintaining programs Evaluation Criteria: Others Portability The ease with which programs can be moved from one implementation to another Generality The applicability to a wide range of applications Well-definedness The completeness and precision of the language’s official definition Influences on Language Design Computer Architecture Languages are developed around the prevalent computer architecture, known as the von Neumann architecture Program Design Methodologies New software development methodologies (e.g., object-oriented software development) led to new programming paradigms and by extension, new programming languages Computer Architecture Influence Well-known computer architecture: Von Neumann Imperative languages, most dominant, because of von Neumann computers Data and programs stored in memory Memory is separate from CPU Instructions and data are piped from memory to CPU Basis for imperative languages Variables model memory cells Assignment statements model piping Iteration is efficient Copyright © 2018 Pearson. All rights reserved. 1-16 The von Neumann Architecture The von Neumann Architecture Fetch-execute-cycle (on a von Neumann architecture computer) initialize the program counter repeat forever fetch the instruction pointed by the counter increment the counter decode the instruction execute the instruction end repeat Programming Methodologies Influences 1950s and early 1960s: Simple applications; worry about machine efficiency Late 1960s: People efficiency became important; readability, better control structures structured programming top-down design and step-wise refinement Late 1970s: Process-oriented to data-oriented data abstraction Middle 1980s: Object-oriented programming Data abstraction + inheritance + polymorphism Language Categories Imperative Central features are variables, assignment statements, and iteration Include languages that support object-oriented programming Include scripting languages Include the visual languages Examples: C, Java, Perl, JavaScript, Visual BASIC.NET, C++ Functional Main means of making computations is by applying functions to given parameters Examples: LISP, Scheme, ML, F# Logic Rule-based (rules are specified in no particular order) Example: Prolog Markup/programming hybrid Markup languages extended to support some programming Examples: JSTL, XSLT Language Design Trade-Offs Reliability vs. cost of execution Example: Java demands all references to array elements be checked for proper indexing, which leads to increased execution costs Readability vs. writability Example: APL provides many powerful operators (and a large number of new symbols), allowing complex computations to be written in a compact program but at the cost of poor readability Writability (flexibility) vs. reliability Example: C++ pointers are powerful and very flexible but are unreliable Implementation Methods Compilation Programs are translated into machine language; includes JIT systems Use: Large commercial applications Pure Interpretation Programs are interpreted by another program known as an interpreter Use: Small programs or when efficiency is not an issue Hybrid Implementation Systems A compromise between compilers and pure interpreters Use: Small and medium systems when efficiency is not the first concern Layered View of Computer The operating system and language implementation are layered over machine interface of a computer Compilation Translate high-level program (source language) into machine code (machine language) Slow translation, fast execution Compilation process has several phases: lexical analysis: converts characters in the source program into lexical units syntax analysis: transforms lexical units into parse trees which represent the syntactic structure of program Semantics analysis: generate intermediate code code generation: machine code is generated The Compilation Process Additional Compilation Terminologies Load module (executable image): the user and system code together Linking and loading: the process of collecting system program units and linking them to a user program Von Neumann Bottleneck Connection speed between a computer’s memory and its processor determines the speed of a computer Program instructions often can be executed much faster than the speed of the connection; the connection speed thus results in a bottleneck Known as the von Neumann bottleneck; it is the primary limiting factor in the speed of computers Pure Interpretation No translation Easier implementation of programs (run-time errors can easily and immediately be displayed) Slower execution (10 to 100 times slower than compiled programs) Often requires more space Now rare for traditional high-level languages Significant comeback with some Web scripting languages (e.g., JavaScript, PHP) Pure Interpretation Process Hybrid Implementation Systems A compromise between compilers and pure interpreters A high-level language program is translated to an intermediate language that allows easy interpretation Faster than pure interpretation Examples Perl programs are partially compiled to detect errors before interpretation Initial implementations of Java were hybrid; the intermediate form, byte code, provides portability to any machine that has a byte code interpreter and a run-time system (together, these are called Java Virtual Machine) Hybrid Implementation Process Just-in-Time Implementation Systems Initially translate programs to an intermediate language Then compile the intermediate language of the subprograms into machine code when they are called Machine code version is kept for subsequent calls JIT systems are widely used for Java programs.NET languages are implemented with a JIT system In essence, JIT systems are delayed compilers Preprocessors Preprocessor macros (instructions) are commonly used to specify that code from another file is to be included A preprocessor processes a program immediately before the program is compiled to expand embedded preprocessor macros A well-known example: C preprocessor expands #include, #define, and similar macros Programming Environments A collection of tools used in software development UNIX An older operating system and tool collection Nowadays often used through a GUI (e.g., CDE, KDE, or GNOME) that runs on top of UNIX Microsoft Visual Studio.NET A large, complex visual environment Used to build Web applications and non-Web applications in any.NET language NetBeans Related to Visual Studio.NET, except for applications in Java Syntax and Semantics of Programming Languages Syntax: the form or structure of the expressions, statements, and program units Semantics: the meaning of the expressions, statements, and program units Syntax and semantics provide a language’s definition Users of a language definition Other language designers Implementers Programmers (the users of the language) The General Problem of Describing Syntax: Terminology A sentence is a string of characters over some alphabet A language is a set of sentences A lexeme is the lowest level syntactic unit of a language (e.g., *, sum, begin) A token is a category of lexemes (e.g., identifier) Formal Definition of Languages Recognizers A recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language Example: syntax analysis part of a compiler Generators A device that generates sentences of a language One can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator BNF and Context-Free Grammars Context-Free Grammars Developed by Noam Chomsky in the mid-1950s Language generators, meant to describe the syntax of natural languages Define a class of languages called context-free languages Backus-Naur Form (1959) Invented by John Backus to describe the syntax of Algol 58 BNF is equivalent to context-free grammars BNF Fundamentals In BNF, abstractions are used to represent classes of syntactic structures--they act like syntactic variables (also called nonterminal symbols, or just terminals) Terminals are lexemes or tokens A rule has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminals BNF Fundamentals (continued) Nonterminals are often enclosed in angle brackets Examples of BNF rules: → identifier | identifier, → if then Grammar: a finite non-empty set of rules A start symbol is a special element of the nonterminals of a grammar BNF Rules An abstraction (or nonterminal symbol) can have more than one RHS | begin end Describing Lists Syntactic lists are described using recursion ident | ident, A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols) An Example Grammar | ; = a | b | c | d + | - | const An Example Derivation => => => = => a = => a = + => a = + => a = b + => a = b + const Derivations Every string of symbols in a derivation is a sentential form A sentence is a sentential form that has only terminal symbols A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded A derivation may be neither leftmost nor rightmost Parse Tree A hierarchical representation of a derivation a = + const b Ambiguity in Grammars A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees An Ambiguous Expression Grammar / | | const const - const / const const - const / const An Unambiguous Expression Grammar If we use the parse tree to indicate precedence levels of the operators, we cannot have ambiguity - | / const| const const - / const const Associativity of Operators Operator associativity can also be indicated by a grammar -> + | const (ambiguous) -> + const const (unambiguous) | const + + const const Extended BNF Optional parts are placed in brackets [ ] -> ident [()] Alternative parts of RHSs are placed inside parentheses and separated via vertical bars → (+|-) const Repetitions (0 or more) are placed inside braces { } → letter {letter|digit} BNF and EBNF BNF + | - | * | / | EBNF {(+ | -) } {(* | /) } Recent Variations in EBNF Alternative RHSs are put on separate lines Use of a colon instead of => Use of opt for optional parts Use of oneof for choices Static Semantics Nothing to do with meaning Context-free grammars (CFGs) cannot describe all of the syntax of programming languages Categories of constructs that are trouble: - Context-free, but cumbersome (e.g., types of operands in expressions) - Non-context-free (e.g., variables must be declared before they are used) Summary The study of programming languages is valuable for a number of reasons: Increase our capacity to use different constructs Enable us to choose languages more intelligently Makes learning new languages easier Most important criteria for evaluating programming languages include: Readability, writability, reliability, cost Major influences on language design have been machine architecture and software development methodologies The major methods of implementing programming languages are: compilation, pure interpretation, and hybrid implementation Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Bachelor of Science in Computer Science CS363 Principles of Programming Languages Week 3 Describing Syntax and Semantics Names, Bindings, and Scopes Contents 1.Attribute Grammars 2. Describing the Meanings of Programs: Dynamic Semantics 3. Names 4. Variables 5. The Concept of Binding Weekly Learning Outcomes 1. Discuss attribute grammars, which can be used to describe both the syntax and static semantics of programming languages. 2. Introduce three formal methods of describing semantics—operational, axiomatic, and denotational semantics. 3. Describe the nature of names and special words in programming languages. 4. Discuss the attributes of variables, including type, address, value, and the issue of aliases. 5. Introduce the important concepts of binding and binding 61 Required Reading Chapter 3 (3.1 – 3.3) + Chapter 5 (5.1 – 5.4) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 6 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Attribute Grammars Attribute grammars (AGs) have additions to CFGs to carry some semantic info on parse tree nodes Primary value of AGs: Static semantics specification Compiler design (static semantics checking) Attribute Grammars : Definition Def: An attribute grammar is a context-free grammar G = (S, N, T, P) with the following additions: For each grammar symbol x there is a set A(x) of attribute values Each rule has a set of functions that define certain attributes of the nonterminals in the rule Each rule has a (possibly empty) set of predicates to check for attribute consistency Attribute Grammars: Definition Let X0 X1... Xn be a rule Functions of the form S(X0) = f(A(X1),... , A(Xn)) define synthesized attributes Functions of the form I(Xj) = f(A(X0),... , A(Xn)), for i + | A | B | C actual_type: synthesized for and expected_type: inherited for Attribute Grammar (continued) Syntax rule: + Semantic rules:.actual_type .actual_type Predicate:.actual_type ==.actual_type.expected_type ==.actual_type Syntax rule: id Semantic rule:.actual_type  lookup (.string) Attribute Grammars (continued) How are attribute values computed? If all attributes were inherited, the tree could be decorated in topdown order. If all attributes were synthesized, the tree could be decorated in bottom-up order. In many cases, both kinds of attributes are used, and it is some combination of top-down and bottom-up that must be used. Attribute Grammars (continued).expected_type  inherited from parent.actual_type  lookup (A).actual_type  lookup (B).actual_type =?.actual_type.actual_type .actual_type.actual_type =?.expected_type Semantics There is no single widely acceptable notation or formalism for describing semantics Several needs for a methodology and notation for semantics: Programmers need to know what statements mean Compiler writers must know exactly what language constructs do Correctness proofs would be possible Compiler generators would be possible Designers could detect ambiguities and inconsistencies Operational Semantics Operational Semantics Describe the meaning of a program by executing its statements on a machine, either simulated or actual. The change in the state of the machine (memory, registers, etc.) defines the meaning of the statement To use operational semantics for a high-level language, a virtual machine is needed Operational Semantics A hardware pure interpreter would be too expensive A software pure interpreter also has problems The detailed characteristics of the particular computer would make actions difficult to understand Such a semantic definition would be machine- dependent Operational Semantics (continued) A better alternative: A complete computer simulation The process: Build a translator (translates source code to the machine code of an idealized computer) Build a simulator for the idealized computer Evaluation of operational semantics: Good if used informally (language manuals, etc.) Extremely complex if used formally (e.g., VDL), it was used for describing semantics of PL/I. Operational Semantics (continued) Uses of operational semantics: - Language manuals and textbooks - Teaching programming languages Two different levels of uses of operational semantics: - Natural operational semantics - Structural operational semantics Evaluation: - Good if used informally (language manuals, etc.) - Extremely complex if used formally (e.g.,VDL) Denotational Semantics Based on recursive function theory The most abstract semantics description method Originally developed by Scott and Strachey (1970) Denotational Semantics - continued The process of building a denotational specification for a language: - Define a mathematical object for each language entity Define a function that maps instances of the language entities onto instances of the corresponding mathematical objects The meaning of language constructs are defined by only the values of the program's variables Denotational Semantics: program state The state of a program is the values of all its current variables s = {, , …, } Let VARMAP be a function that, when given a variable name and a state, returns the current value of the variable VARMAP(ij, s) = vj Decimal Numbers '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | ('0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9') Mdec('0') = 0, Mdec ('1') = 1, …, Mdec ('9') = 9 Mdec ( '0') = 10 * Mdec () Mdec ( '1’) = 10 * Mdec () + 1 … Mdec ( '9') = 10 * Mdec () + 9 Expressions Map expressions onto Z  {error} We assume expressions are decimal numbers, variables, or binary expressions having one arithmetic operator and two operands, each of which can be an expression Expressions Me(, s) = case of => Mdec(, s) => if VARMAP(, s) == undef then error else VARMAP(, s) => if (Me(., s) == undef OR Me(., s) = undef) then error else if (. == '+' then Me(., s) + Me(., s) else Me(., s) * Me(., s)... Assignment Statements Maps state sets to state sets U {error} Ma(x := E, s) = if Me(E, s) == error then error else s’ = {,,...,}, where for j = 1, 2,..., n, if ij == x then vj’ = Me(E, s) else vj’ = VARMAP(ij, s) Logical Pretest Loops Maps state sets to state sets U {error} Ml(while B do L, s) = if Mb(B, s) == undef then error else if Mb(B, s) == false then s else if Msl(L, s) == error then error else Ml(while B do L, Msl(L, s)) Loop Meaning The meaning of the loop is the value of the program variables after the statements in the loop have been executed the prescribed number of times, assuming there have been no errors In essence, the loop has been converted from iteration to recursion, where the recursive control is mathematically defined by other recursive state mapping functions - Recursion, when compared to iteration, is easier to describe with mathematical rigor Evaluation of Denotational Semantics Can be used to prove the correctness of programs Provides a rigorous way to think about programs Can be an aid to language design Has been used in compiler generation systems Because of its complexity, it are of little use to language users Axiomatic Semantics Based on formal logic (predicate calculus) Original purpose: formal program verification Axioms or inference rules are defined for each statement type in the language (to allow transformations of logic expressions into more formal logic expressions) The logic expressions are called assertions Axiomatic Semantics (continued) An assertion before a statement (a precondition) states the relationships and constraints among variables that are true at that point in execution An assertion following a statement is a postcondition A weakest precondition is the least restrictive precondition that will guarantee the postcondition Axiomatic Semantics Form Pre-, post form: {P} statement {Q} An example a = b + 1 {a > 1} One possible precondition: {b > 10} Weakest precondition: {b > 0} Program Proof Process The postcondition for the entire program is the desired result Work back through the program to the first statement. If the precondition on the first statement is the same as the program specification, the program is correct. Axiomatic Semantics: Assignment An axiom for assignment statements (x = E): {Qx->E} x = E {Q} The Rule of Consequence: {P} S {Q}, P'  P, Q  Q' {P' } S {Q' } Axiomatic Semantics: Sequences An inference rule for sequences of the form S1; S2 {P1} S1 {P2} {P2} S2 {P3} {P1} S1{P2}, {P2} S2 {P3} {P1} S1; S2 {P3} Axiomatic Semantics: Selection An inference rules for selection - if B then S1 else S2 {B and P} S1 {Q}, {(not B) and P} S2 {Q} {P} if B then S1 else S2 {Q} Axiomatic Semantics: Loops An inference rule for logical pretest loops {P} while B do S end {Q} (I and B) S {I} {I} while B do S {I and (not B)} where I is the loop invariant (the inductive hypothesis) Axiomatic Semantics: Axioms Characteristics of the loop invariant: I must meet the following conditions: P => I -- the loop invariant must be true initially {I} B {I} -- evaluation of the Boolean must not change the validity of I {I and B} S {I} -- I is not changed by executing the body of the loop (I and (not B)) => Q -- if I is true and B is false, Q is implied The loop terminates -- can be difficult to prove Loop Invariant The loop invariant I is a weakened version of the loop postcondition, and it is also a precondition. I must be weak enough to be satisfied prior to the beginning of the loop, but when combined with the loop exit condition, it must be strong enough to force the truth of the postcondition Evaluation of Axiomatic Semantics Developing axioms or inference rules for all of the statements in a language is difficult It is a good tool for correctness proofs, and an excellent framework for reasoning about programs, but it is not as useful for language users and compiler writers Its usefulness in describing the meaning of a programming language is limited for language users or compiler writers Denotation Semantics vs Operational Semantics In operational semantics, the state changes are defined by coded algorithms In denotational semantics, the state changes are defined by rigorous mathematical functions Names Design issues for names: Are names case sensitive? Are special words reserved words or keywords? Names (continued) Length If too short, they cannot be connotative Language examples: C99: no limit but only the first 63 are significant; also, external names are limited to a maximum of 31 C# and Java: no limit, and all are significant C++: no limit, but implementers often impose one Names (continued) Special characters PHP: all variable names must begin with dollar signs Perl: all variable names begin with special characters, which specify the variable’s type Ruby: variable names that begin with @ are instance variables; those that begin with @@ are class variables Names (continued) Case sensitivity Disadvantage: readability (names that look alike are different) Names in the C-based languages are case sensitive Names in others are not Worse in C++, Java, and C# because predefined names are mixed case (e.g. IndexOutOfBoundsException) Names (continued) Special words An aid to readability; used to delimit or separate statement clauses - A keyword is a word that is special only in certain contexts A reserved word is a special word that cannot be used as a userdefined name Potential problem with reserved words: If there are too many, many collisions occur (e.g., COBOL has 300 reserved words!) Variables A variable is an abstraction of a memory cell Variables can be characterized as a sextuple of attributes: Name Address Value Type Lifetime Scope Variables Attributes Name - not all variables have them Address - the memory address with which it is associated A variable may have different addresses at different times during execution A variable may have different addresses at different places in a program If two variable names can be used to access the same memory location, they are called aliases Aliases are created via pointers, reference variables, C and C++ unions Aliases are harmful to readability (program readers must remember all of them) Variables Attributes (continued) Type - determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision Value - the contents of the location with which the variable is associated - The l-value of a variable is its address - The r-value of a variable is its value Abstract memory cell - the physical cell or collection of cells associated with a variable The Concept of Binding A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol Binding time is the time at which a binding takes place. Possible Binding Times Language design time -- bind operator symbols to operations Language implementation time-- bind floating point type to a representation Compile time -- bind a variable to a type in C or Java Load time -- bind a C or C++ static variable to a memory cell) Runtime -- bind a nonstatic local variable to a memory cell Static and Dynamic Binding A binding is static if it first occurs before run time and remains unchanged throughout program execution. A binding is dynamic if it first occurs during execution or can change during execution of the program Type Binding How is a type specified? When does the binding take place? If static, the type may be specified by either an explicit or an implicit declaration Explicit/Implicit Declaration An explicit declaration is a program statement used for declaring the types of variables An implicit declaration is a default mechanism for specifying types of variables through default conventions, rather than declaration statements Basic, Perl, Ruby, JavaScript, and PHP provide implicit declarations Advantage: writability (a minor convenience) Disadvantage: reliability (less trouble with Perl) Explicit/Implicit Declaration (continued) Some languages use type inferencing to determine types of variables (context) C# - a variable can be declared with var and an initial value. The initial value sets the type Visual Basic 9.0+, ML, Haskell, and F# use type inferencing. The context of the appearance of a variable determines its type Dynamic Type Binding Dynamic Type Binding (JavaScript, Python, Ruby, PHP, and C# (limited)) Specified through an assignment statement e.g., JavaScript list = [2, 4.33, 6, 8]; list = 17.3; Advantage: flexibility (generic program units) Disadvantages: High cost (dynamic type checking and interpretation) Type error detection by the compiler is difficult Variable Attributes (continued) Storage Bindings & Lifetime Allocation - getting a cell from some pool of available cells Deallocation - putting a cell back into the pool The lifetime of a variable is the time during which it is bound to a particular memory cell Categories of Variables by Lifetimes Static--bound to memory cells before execution begins and remains bound to the same memory cell throughout execution, e.g., C and C++ static variables in functions Advantages: efficiency (direct addressing), history-sensitive subprogram support Disadvantage: lack of flexibility (no recursion) Categories of Variables by Lifetimes Stack-dynamic--Storage bindings are created for variables when their declaration statements are elaborated. (A declaration is elaborated when the executable code associated with it is executed) If scalar, all attributes except address are statically bound local variables in C subprograms (not declared static) and Java methods Advantage: allows recursion; conserves storage Disadvantages: Overhead of allocation and deallocation Subprograms cannot be history sensitive Inefficient references (indirect addressing) Categories of Variables by Lifetimes Explicit heap-dynamic -- Allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution Referenced only through pointers or references, e.g. dynamic objects in C++ (via new and delete), all objects in Java Advantage: provides for dynamic storage management Disadvantage: inefficient and unreliable Categories of Variables by Lifetimes Implicit heap-dynamic--Allocation and deallocation caused by assignment statements all variables in APL; all strings and arrays in Perl, JavaScript, and PHP Advantage: flexibility (generic code) Disadvantages: Inefficient, because all attributes are dynamic Loss of error detection Summary BNF and context-free grammars are equivalent meta-languages Well-suited for describing the syntax of programming languages An attribute grammar is a descriptive formalism that can describe both the syntax and the semantics of a language Three primary methods of semantics description Operation, axiomatic, denotational Case sensitivity and the relationship of names to special words represent design issues of names Variables are characterized by the sextuples: name, address, value, type, lifetime, scope Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Bachelor of Science in Computer Science CS363 Principles of Programming Languages Week 4 Names, Bindings, and Scopes Data Types Contents 1. Scope and Lifetime 2. Referencing Environments 3. Named Constants 4. Primitive Data Types 5. Character String Types 6. Enumeration Types Weekly Learning Outcomes 1. Describe two very different scoping rules for names, static and dynamic. 2. Describe the concept of a referencing environment of a statement. 3. Discuss named constants and variable initialization. 4. Introduce the concept of a data type and the characteristics of the common primitive data types. 5. Discuss the designs of enumeration and subrange types. 123 Required Reading Chapter 5 (5.4 – 5.8) + Chapter 6 (6.1 – 6.4) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 8 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Variable Attributes: Scope The scope of a variable is the range of statements over which it is visible The local variables of a program unit are those that are declared in that unit The nonlocal variables of a program unit are those that are visible in the unit but not declared there Global variables are a special category of nonlocal variables The scope rules of a language determine how references to names are associated with variables Static Scope Based on program text To connect a name reference to a variable, you (or the compiler) must find the declaration Search process: search declarations, first locally, then in increasingly larger enclosing scopes, until one is found for the given name Enclosing static scopes (to a specific scope) are called its static ancestors; the nearest static ancestor is called a static parent Some languages allow nested subprogram definitions, which create nested static scopes (e.g., Ada, JavaScript, Common Lisp, Scheme, Fortran 2003+, F#, and Python) Scope (continued) Variables can be hidden from a unit by having a "closer" variable with the same name Blocks A method of creating static scopes inside program units--from ALGOL 60 Example in C: void sub() { int count; while (...) { int count; count++;... } … } - Note: legal in C and C++, but not in Java and C# - too error-prone The LET Construct Most functional languages include some form of let construct A let construct has two parts The first part binds names to values The second part uses the names defined in the first part In Scheme: (LET ( (name1 expression1) … (namen expressionn) ) The LET Construct (continued) In ML: let val name1 = expression1 … val namen = expressionn in expression end; In F#: First part: let left_side = expression (left_side is either a name or a tuple pattern) All that follows is the second part Declaration Order C99, C++, Java, and C# allow variable declarations to appear anywhere a statement can appear In C99, C++, and Java, the scope of all local variables is from the declaration to the end of the block In the official documentation of C#, the scope of any variable declared in a block is the whole block, regardless of the position of the declaration in the block However, that is misleading, because a variable still must be declared before it can be used Declaration Order (continued) In C++, Java, and C#, variables can be declared in for statements The scope of such variables is restricted to the for construct Global Scope C, C++, PHP, and Python support a program structure that consists of a sequence of function definitions in a file These languages allow variable declarations to appear outside function definitions C and C++have both declarations (just attributes) and definitions (attributes and storage) A declaration outside a function definition specifies that it is defined in another file Global Scope (continued) PHP Programs are embedded in HTML markup documents, in any number of fragments, some statements and some function definitions The scope of a variable (implicitly) declared in a function is local to the function The scope of a variable implicitly declared outside functions is from the declaration to the end of the program, but skips over any intervening functions Global variables can be accessed in a function through the $GLOBALS array or by declaring it global Global Scope (continued) Python A global variable can be referenced in functions, but can be assigned in a function only if it has been declared to be global in the function Evaluation of Static Scoping Works well in many situations Problems: In most cases, too much access is possible As a program evolves, the initial structure is destroyed and local variables often become global; subprograms also gravitate toward become global, rather than nested Dynamic Scope Based on calling sequences of program units, not their textual layout (temporal versus spatial) References to variables are connected to declarations by searching back through the chain of subprogram calls that forced execution to this point Scope Example function big() { function sub1() var x = 7; function sub2() { var y = x; } var x = 3; } big calls sub1 sub1 calls sub2 sub2 uses x Static scoping Reference to x in sub2 is to big's x Dynamic scoping Reference to x in sub2 is to sub1's x Scope Example Evaluation of Dynamic Scoping: Advantage: convenience Disadvantages: 1. While a subprogram is executing, its variables are visible to all subprograms it calls 2. Impossible to statically type check 3. Poor readability- it is not possible to statically determine the type of a variable Scope and Lifetime Scope and lifetime are sometimes closely related, but are different concepts Consider a static variable in a C or C++ function Referencing Environments The referencing environment of a statement is the collection of all names that are visible in the statement In a static-scoped language, it is the local variables plus all of the visible variables in all of the enclosing scopes A subprogram is active if its execution has begun but has not yet terminated In a dynamic-scoped language, the referencing environment is the local variables plus all visible variables in all active subprograms Named Constants A named constant is a variable that is bound to a value only when it is bound to storage Advantages: readability and modifiability Used to parameterize programs The binding of values to named constants can be either static (called manifest constants) or dynamic Languages: C++ and Java: expressions of any kind, dynamically bound C# has two kinds, readonly and const - the values of const named constants are bound at compile time - The values of readonly named constants are dynamically bound Data Types A data type defines a collection of data objects and a set of predefined operations on those objects A descriptor is the collection of the attributes of a variable An object represents an instance of a user-defined (abstract data) type One design issue for all data types: What operations are defined and how are they specified? Primitive Data Types Almost all programming languages provide a set of primitive data types Primitive data types: Those not defined in terms of other data types Some primitive data types are merely reflections of the hardware Others require only a little non-hardware support for their implementation Primitive Data Types: Integer Almost always an exact reflection of the hardware so the mapping is trivial There may be as many as eight different integer types in a language Java’s signed integer sizes: byte, short, int, long Primitive Data Types: Floating Point Model real numbers, but only as approximations Languages for scientific use support at least two floating-point types (e.g., float and double; sometimes more Usually exactly like the hardware, but not always IEEE Floating-Point Standard 754 Primitive Data Types: Complex Some languages support a complex type, e.g., C99, Fortran, and Python Each value consists of two floats, the real part and the imaginary part Literal form (in Python): (7 + 3j), where 7 is the real part and 3 is the imaginary part Primitive Data Types: Decimal For business applications (money) Essential to COBOL C# offers a decimal data type Store a fixed number of decimal digits, in coded form (BCD) Advantage: accuracy Disadvantages: limited range, wastes memory Primitive Data Types: Boolean Simplest of all Range of values: two elements, one for “true” and one for “false” Could be implemented as bits, but often as bytes Advantage: readability Primitive Data Types: Character Stored as numeric codings Most commonly used coding: ASCII An alternative, 16-bit coding: Unicode (UCS-2) Includes characters from most natural languages Originally used in Java Now supported by many languages 32-bit Unicode (UCS-4) Supported by Fortran, starting with 2003 Character String Types Values are sequences of characters Design issues: Is it a primitive type or just a special kind of array? Should the length of strings be static or dynamic? Character String Types Operations Typical operations: Assignment and copying Comparison (=, >, etc.) Catenation Substring reference Pattern matching Character String Type in Certain Languages C and C++ Not primitive Use char arrays and a library of functions that provide operations SNOBOL4 (a string manipulation language) Primitive Many operations, including elaborate pattern matching Fortran and Python Primitive type with assignment and several operations Java (and C#, Ruby, and Swift) Primitive via the String class Perl, JavaScript, Ruby, and PHP - Provide built-in pattern matching, using regular expressions Character String Length Options Static: COBOL, Java’s String class Limited Dynamic Length: C and C++ In these languages, a special character is used to indicate the end of a string’s characters, rather than maintaining the length Dynamic (no maximum): SNOBOL4, Perl, JavaScript Character String Type Evaluation Aid to writability As a primitive type with static length, they are inexpensive to provide-why not have them? Dynamic length is nice, but is it worth the expense? Character String Implementation Static length: compile-time descriptor Limited dynamic length: may need a run-time descriptor for length (but not in C and C++) Dynamic length: need run-time descriptor; allocation/deallocation is the biggest implementation problem Compile- and Run-Time Descriptors Compile-time descriptor for static strings Run-time descriptor for limited dynamic strings User-Defined Ordinal Types An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers Examples of primitive ordinal types in Java integer char boolean Enumeration Types All possible values, which are named constants, are provided in the definition C# example enum days {mon, tue, wed, thu, fri, sat, sun}; Design issues Is an enumeration constant allowed to appear in more than one type definition, and if so, how is the type of an occurrence of that constant checked? Are enumeration values coerced to integer? Any other type coerced to an enumeration type? Evaluation of Enumerated Type Aid to readability, e.g., no need to code a color as a number Aid to reliability, e.g., compiler can check: operations (don’t allow colors to be added) No enumeration variable can be assigned a value outside its defined range C#, F#, Swift, and Java 5.0 provide better support for enumeration than C++ because enumeration type variables in these languages are not coerced into integer types Summary BNF and context-free grammars are equivalent meta-languages Well-suited for describing the syntax of programming languages An attribute grammar is a descriptive formalism that can describe both the syntax and the semantics of a language Three primary methods of semantics description Operation, axiomatic, denotational Case sensitivity and the relationship of names to special words represent design issues of names Variables are characterized by the sextuples: name, address, value, type, lifetime, scope Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Bachelor of Science in Computer Science CS363 Principles of Programming Languages Week 5 Data Types Contents 1. Array Types, Associative Arrays, Record Types, Tuples, Lists, and Unions 2. Pointer and Reference Types 3. Optional Types 4. Type Checking 5. Strong Typing 6. Type Equivalence Weekly Learning Outcomes 1. Discuss the details of structured data types— specifically, arrays, associative arrays, records, tuples, lists, and unions. 2. Discuss pointers, references, and the optional types. 3. Describe and evaluate the design issues and the design choices made by the designers of some common languages. 4. Discuss the fundamentals of the theory of data types including type checking, strong typing, and type equivalence rules. 5. Ability to implement various data types. 167 Required Reading Chapter 6 (6.5 – 6.15) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 8 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Array Types An array is a homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element. Copyright © 2018 Pearson. All rights reserved. 1-169 Array Design Issues What types are legal for subscripts? Are subscripting expressions in element references range checked? When are subscript ranges bound? When does allocation take place? Are ragged or rectangular multidimensional arrays allowed, or both? What is the maximum number of subscripts? Can array objects be initialized? Are any kind of slices supported? Array Indexing Indexing (or subscripting) is a mapping from indices to elements array_name (index_value_list) an element Index Syntax Fortran and Ada use parentheses Ada explicitly uses parentheses to show uniformity between array references and function calls because both are mappings Most other languages use brackets Arrays Index (Subscript) Types FORTRAN, C: integer only Java: integer types only Index range checking - C, C++, Perl, and Fortran do not specify range checking - Java, ML, C# specify range checking Subscript Binding and Array Categories Static: subscript ranges are statically bound and storage allocation is static (before run-time) Advantage: efficiency (no dynamic allocation) Fixed stack-dynamic: subscript ranges are statically bound, but the allocation is done at declaration time Advantage: space efficiency Subscript Binding and Array Categories (continued) Fixed heap-dynamic: similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation (i.e., binding is done when requested and storage is allocated from heap, not stack) Subscript Binding and Array Categories (continued) Heap-dynamic: binding of subscript ranges and storage allocation is dynamic and can change any number of times Advantage: flexibility (arrays can grow or shrink during program execution) Subscript Binding and Array Categories (continued) C and C++ arrays that include static modifier are static C and C++ arrays without static modifier are fixed stackdynamic C and C++ provide fixed heap-dynamic arrays C# includes a second array class ArrayList that provides fixed heap-dynamic Perl, JavaScript, Python, and Ruby support heap-dynamic arrays Array Initialization Some language allow initialization at the time of storage allocation C, C++, Java, Swift, and C# C# example: int list [] = {4, 5, 7, 83} Character strings in C and C++ char name [] = ″freddie″; Arrays of strings in C and C++ char *names [] = {″Bob″, ″Jake″, ″Joe″]; Java initialization of String objects String[] names = {″Bob″, ″Jake″, ″Joe″}; Heterogeneous Arrays A heterogeneous array is one in which the elements need not be of the same type Supported by Perl, Python, JavaScript, and Ruby Array Initialization C-based languages int list [] = {1, 3, 5, 7} char *names [] = {″Mike″, ″Fred″, ″Mary Lou″}; Python List comprehensions list = [x ** 2 for x in range(12) if x % 3 == 0] puts [0, 9, 36, 81] in list Arrays Operations APL provides the most powerful array processing operations for vectors and matrixes as well as unary operators (for example, to reverse column elements) Python’s array assignments, but they are only reference changes. Python also supports array catenation and element membership operations Ruby also provides array catenation Rectangular and Jagged Arrays A rectangular array is a multi-dimensioned array in which all of the rows have the same number of elements and all columns have the same number of elements A jagged matrix has rows with varying number of elements Possible when multi-dimensioned arrays actually appear as arrays of arrays C, C++, and Java support jagged arrays F# and C# support rectangular arrays and jagged arrays Slices A slice is some substructure of an array; nothing more than a referencing mechanism Slices are only useful in languages that have array operations Slice Examples Python vector = [2, 4, 6, 8, 10, 12, 14, 16] mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] vector (3:6) is a three-element array mat[0:2] is the first and second element of the first row of mat Ruby supports slices with the slice method list.slice(2, 2) returns the third and fourth elements of list Implementation of Arrays Access function maps subscript expressions to an address in the array Access function for single-dimensioned arrays: address(list[k]) = address (list[lower_bound]) + ((k-lower_bound) * element_size) Accessing Multi-dimensioned Arrays Two common ways: Row major order (by rows) – used in most languages Column major order (by columns) – used in Fortran A compile-time descriptor for a multidimensional array Locating an Element in a Multi-dimensioned Array General format Location (a[I,j]) = address of a [row_lb,col_lb] + (((I row_lb) * n) + (j - col_lb)) * element_size Compile-Time Descriptors Single-dimensioned array Multidimensional array Associative Arrays An associative array is an unordered collection of data elements that are indexed by an equal number of values called keys User-defined keys must be stored Design issues: - What is the form of references to elements? - Is the size static or dynamic? Built-in type in Perl, Python, Ruby, and Swift Associative Arrays in Perl Names begin with %; literals are delimited by parentheses %hi_temps = ("Mon" => 77, "Tue" => 79, "Wed" => 65, …); Subscripting is done using braces and keys $hi_temps{"Wed"} = 83; Elements can be removed with delete delete $hi_temps{"Tue"}; Record Types A record is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by names Design issues: What is the syntactic form of references to the field? Are elliptical references allowed Definition of Records in COBOL COBOL uses level numbers to show nested records; others use recursive definition 01 EMP-REC. 02 EMP-NAME. 05 FIRST PIC X(20). 05 MID PIC X(10). 05 LAST PIC X(20). 02 HOURLY-RATE PIC 99V99. References to Records Record field references 1. COBOL field_name OF record_name_1 OF... OF record_name_n 2. Others (dot notation) record_name_1.record_name_2.... record_name_n.field_name Fully qualified references must include all record names Elliptical references allow leaving out record names as long as the reference is unambiguous, for example in COBOL FIRST, FIRST OF EMP-NAME, and FIRST of EMP-REC are elliptical references to the employee’s first name Evaluation and Comparison to Arrays Records are used when collection of data values is heterogeneous Access to array elements is much slower than access to record fields, because subscripts are dynamic (field names are static) Dynamic subscripts could be used with record field access, but it would disallow type checking and it would be much slower Implementation of Record Type Offset address relative to the beginning of the records is associated with each field Tuple Types A tuple is a data type that is similar to a record, except that the elements are not named Used in Python, ML, and F# to allow functions to return multiple values Python Closely related to its lists, but immutable Create with a tuple literal myTuple = (3, 5.8, ′apple′) Referenced with subscripts (begin at 1) Catenation with + and deleted with del Tuple Types (continued) ML val myTuple = (3, 5.8, ′apple′); - Access as follows: #1(myTuple) is the first element - A new tuple type can be defined type intReal = int * real; (The asterisk is just a separator) F# let tup = (3, 5, 7) let a, b, c = tup This assigns a tuple to a tuple pattern (a, b, c) List Types Lists in Lisp and Scheme are delimited by parentheses and use no commas (A B C D) and (A (B C) D) Data and code have the same form As data, (A B C) is literally what it is As code, (A B C) is the function A applied to the parameters B and C The interpreter needs to know which a list is, so if it is data, we quote it with an apostrophe ′(A B C) is data List Types (continued) List Operations in Scheme CAR returns the first element of its list parameter (CAR ′(A B C)) returns A CDR returns the remainder of its list parameter after the first element has been removed (CDR ′(A B C)) returns (B C) - CONS puts its first parameter into its second parameter, a list, to make a new list (CONS ′A (B C)) returns (A B C) - LIST returns a new list of its parameters (LIST ′A ′B ′(C D)) returns (A B (C D)) List Types (continued) List Operations in ML Lists are written in brackets and the elements are separated by commas List elements must be of the same type The Scheme CONS function is a binary operator in ML, :: 3 :: [5, 7, 9] evaluates to [3, 5, 7, 9] The Scheme CAR and CDR functions are named hd and tl, respectively List Types (continued) F# Lists Like those of ML, except elements are separated by semicolons and hd and tl are methods of the List class Python Lists The list data type also serves as Python’s arrays Unlike Scheme, Common Lisp, ML, and F#, Python’s lists are mutable Elements can be of any type Create a list with an assignment myList = [3, 5.8, "grape"] List Types (continued) Python Lists (continued) List elements are referenced with subscripting, with indices beginning at zero x = myList Sets x to 5.8 List elements can be deleted with del del myList List Comprehensions – derived from set notation [x * x for x in range(6) if x % 3 == 0] creates [0, 1, 2, Constructed list: [0, 9, 36] range(12) 3, 4, 5, 6] List Types (continued) Haskell’s List Comprehensions The original [n * n | n [i * i) |] Both C# and Java supports lists through their generic heap-dynamic collection classes, List and ArrayList, respectively Summary The data types of a language are a large part of what determines that language’s style and usefulness. The primitive data types of most imperative languages include numeric, character, and Boolean types. The user-defined enumeration and subrange types are convenient and add to the readability and reliability of programs. Arrays and records are included in most languages. Pointers are used for addressing flexibility and to control dynamic storage management. Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Principles of Programming Languages Data Types Contents 1. Array Types, Associative Arrays, Record Types, Tuples, Lists, and Unions 2. Pointer and Reference Types 3. Optional Types 4. Type Checking 5. Strong Typing 6. Type Equivalence Weekly Learning Outcomes 1. Discuss the details of structured data types— specifically, arrays, associative arrays, records, tuples, lists, and unions. 2. Discuss pointers, references, and the optional types. 3. Describe and evaluate the design issues and the design choices made by the designers of some common languages. 4. Discuss the fundamentals of the theory of data types including type checking, strong typing, and type equivalence rules. 5. Ability to implement various data types. 209 Required Reading Chapter 6 (6.5 – 6.15) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 8 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Unions Types A union is a type whose variables are allowed to store different type values at different times during execution Design issue Should type checking be required? Discriminated vs. Free Unions C and C++ provide union constructs in which there is no language support for type checking; the union in these languages is called free union Type checking of unions require that each union include a type indicator called a discriminant Supported by ML, Haskell, and F# Unions in F# Defined with a type statement using OR type intReal = | IntValue of int | RealValue of float;; is the new type IntValue and RealValue are constructors intReal To create a value of type intReal: let ir1 = IntValue 17;; let ir2 = RealValue 3.4;; Unions in F# (continued) Accessing the value of a union is done with pattern matching match pattern with | expression_list1 -> expression1 |… | expression_listn -> expressionn - Pattern can be any data type - The expression list can have wild cards (_) Unions in F# (continued) Example: let a = 7;; let b = ″grape″;; let x = match (a, b) with | 4, ″apple″ -> apple | _, ″grape″ -> grape | _ -> fruit;; Unions in F# (continued) To display the type of the intReal union: let printType value = match value with | IntVale value -> printfn ″int″ | RealValue value -> printfn ″float″;; If ir1 and ir2 are defined as previously, printType ir1 returns int printType ir2 returns float Evaluation of Unions Free unions are unsafe Do not allow type checking Java and C# do not support unions Reflective of growing concerns for safety in programming language Pointer and Reference Types A pointer type variable has a range of values that consists of memory addresses and a special value, nil Provide the power of indirect addressing Provide a way to manage dynamic memory A pointer can be used to access a location in the area where storage is dynamically created (usually called a heap) Design Issues of Pointers What are the scope of and lifetime of a pointer variable? What is the lifetime of a heap-dynamic variable? Are pointers restricted as to the type of value to which they can point? Are pointers used for dynamic storage management, indirect addressing, or both? Should the language support pointer types, reference types, or both? Pointer Operations Two fundamental operations: assignment and dereferencing Assignment is used to set a pointer variable’s value to some useful address Dereferencing yields the value stored at the location represented by the pointer’s value Dereferencing can be explicit or implicit C++ uses an explicit operation via * j = *ptr sets j to the value located at ptr Pointer Assignment Illustrated The assignment operation j = *ptr Problems with Pointers Dangling pointers (dangerous) A pointer points to a heap-dynamic variable that has been deallocated Lost heap-dynamic variable An allocated heap-dynamic variable that is no longer accessible to the user program (often called garbage) Pointer p1 is set to point to a newly created heap-dynamic variable Pointer p1 is later set to point to another newly created heap-dynamic variable The process of losing heap-dynamic variables is called memory leakage Pointers in C and C++ Extremely flexible but must be used with care Pointers can point at any variable regardless of when or where it was allocated Used for dynamic storage management and addressing Pointer arithmetic is possible Explicit dereferencing and address-of operators Domain type need not be fixed (void *) void * can point to any type and can be type checked (cannot be de-referenced) Pointer Arithmetic in C and C++ float stuff; float *p; p = stuff; *(p+5) is equivalent to *(p+i) is equivalent to and stuff[i] and stuff p p[i] Reference Types C++ includes a special kind of pointer type called a reference type that is used primarily for formal parameters Advantages of both pass-by-reference and pass-by-value Java extends C++’s reference variables and allows them to replace pointers entirely References are references to objects, rather than being addresses C# includes both the references of Java and the pointers of C++ Evaluation of Pointers Dangling pointers and dangling objects are problems as is heap management Pointers are like goto's--they widen the range of cells that can be accessed by a variable Pointers or references are necessary for dynamic data structures--so we can't design a language without them Representations of Pointers Large computers use single values Intel microprocessors use segment and offset Dangling Pointer Problem Tombstone: extra heap cell that is a pointer to the heap-dynamic variable The actual pointer variable points only at tombstones When heap-dynamic variable de-allocated, tombstone remains but set to nil Costly in time and space. Locks-and-keys: Pointer values are represented as (key, address) pairs Heap-dynamic variables are represented as variable plus cell for integer lock value When heap-dynamic variable allocated, lock value is created and placed in lock cell and key cell of pointer Heap Management A very complex run-time process Single-size cells vs. variable-size cells Two approaches to reclaim garbage Reference counters (eager approach): reclamation is gradual Mark-sweep (lazy approach): reclamation occurs when the list of variable space becomes empty Reference Counter Reference counters: maintain a counter in every cell that store the number of pointers currently pointing at the cell Disadvantages: space required, execution time required, complications for cells connected circularly Advantage: it is intrinsically incremental, so significant delays in the application execution are avoided Mark-Sweep The run-time system allocates storage cells as requested and disconnects pointers from cells as necessary; mark-sweep then begins Every heap cell has an extra bit used by collection algorithm All cells initially set to garbage All pointers traced into heap, and reachable cells marked as not garbage All garbage cells returned to list of available cells Disadvantages: in its original form, it was done too infrequently. When done, it caused significant delays in application execution. Contemporary mark-sweep algorithms avoid this by doing it more often—called incremental mark-sweep Marking Algorithm Variable-Size Cells All the difficulties of single-size cells plus more Required by most programming languages If mark-sweep is used, additional problems occur The initial setting of the indicators of all cells in the heap is difficult The marking process in nontrivial Maintaining the list of available space is another source of overhead Optional Types - Optional types are useful when there is a need for a variable to indicate that it currently has no value - C#, F#, and Swift, among others, have optional types - Reference types in C# are already optional types (use null for no value) - Value types in C# (struct types) can be declared to be optional by attaching a question mark to the type name in their declaration int? x; - The no-value is null, which can be assigned to x and x can be tested for it - In Swift, nil is used instead of null Type Checking Generalize the concept of operands and operators to include subprograms and assignments Type checking is the activity of ensuring that the operands of an operator are of compatible types A compatible type is one that is either legal for the operator, or is allowed under language rules to be implicitly converted, by compiler- generated code, to a legal type This automatic conversion is called a coercion. A type error is the application of an operator to an operand of an inappropriate type Type Checking (continued) If all type bindings are static, nearly all type checking can be static If type bindings are dynamic, type checking must be dynamic A programming language is strongly typed if type errors are always detected Advantage of strong typing: allows the detection of the misuses of variables that result in type errors Strong Typing Language examples: C and C++ are not: parameter type checking can be avoided; unions are not type checked Java and C# are, almost (because of explicit type casting) - ML and F# are Strong Typing (continued) Coercion rules strongly affect strong typing--they can weaken it considerably (C++ versus ML and F#) Although Java has just half the assignment coercions of C++, its strong typing is still far less effective than that of Ada Name Type Equivalence Name type equivalence means the two variables have equivalent types if they are in either the same declaration or in declarations that use the same type name Easy to implement but highly restrictive: Subranges of integer types are not equivalent with integer types Formal parameters must be the same type as their corresponding actual parameters Structure Type Equivalence Structure type equivalence means that two variables have equivalent types if their types have identical structures More flexible, but harder to implement Type Equivalence (continued) Consider the problem of two structured types: Are two record types equivalent if they are structurally the same but use different field names? Are two array types equivalent if they are the same except that the subscripts are different? (e.g. [1..10] and [0..9]) Are two enumeration types equivalent if their components are spelled differently? With structural type equivalence, you cannot differentiate between types of the same structure (e.g. different units of speed, both float) Summary The data types of a language are a large part of what determines that language’s style and usefulness. The primitive data types of most imperative languages include numeric, character, and Boolean types. The user-defined enumeration and subrange types are convenient and add to the readability and reliability of programs. Arrays and records are included in most languages. Pointers are used for addressing flexibility and to control dynamic storage management. Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics CS363 Principles of Programming Languages Week 6 Expressions and Assignment Statements Contents 1. Arithmetic Expressions 2. Overloaded Operators 3. Type Conversions 4. Relational and Boolean Expressions 5. Short Circuit Evaluation 6. Assignment Statements 7. Mixed-Mode Assignment Weekly Learning Outcomes 1. Discuss the semantics rules that determine the order of evaluation of operators in expressions. 2. Discuss overloaded operators, both predefined and user defined and evaluate mixed-mode expressions. 3. Define and evaluate widening and narrowing type conversions, both implicit and explicit. 4. Discuss relational and Boolean expressions including the process of short-circuit evaluation. 5. Describe the assignment statement, from its simplest form to all of its variations, including assignments as expressions and mixedmode assignments. 248 Required Reading Chapter 7 Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 7 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Introduction Expressions are the fundamental means of specifying computations in a programming language To understand expression evaluation, need to be familiar with the orders of operator and operand evaluation Essence of imperative languages is dominant role of assignment statements Arithmetic Expressions Arithmetic evaluation was one of the motivations for the development of the first programming languages Arithmetic expressions consist of operators, operands, parentheses, and function calls In most languages, binary operators are infix, except in Scheme and LISP, in which they are prefix; Perl also has some prefix binary operators Most unary operators are prefix, but the ++ and –- operators in C-based languages can be either prefix or postfix Arithmetic Expressions: Design Issues Design issues for arithmetic expressions Operator precedence rules? Operator associativity rules? Order of operand evaluation? Operand evaluation side effects? Operator overloading? Type mixing in expressions? Arithmetic Expressions: Operators A unary operator has one operand A binary operator has two operands A ternary operator has three operands Arithmetic Expressions: Operator Precedence Rules The operator precedence rules for expression evaluation define the order in which “adjacent” operators of different precedence levels are evaluated Typical precedence levels parentheses unary operators ** (if the language supports it) *, / +, - Arithmetic Expressions: Operator Associativity Rule The operator associativity rules for expression evaluation define the order in which adjacent operators with the same precedence level are evaluated Typical associativity rules Left to right, except **, which is right to left Sometimes unary operators associate right to left (e.g., in FORTRAN) APL is different; all operators have equal precedence and all operators associate right to left Precedence and associativity rules can be overriden with parentheses Expressions in Ruby and Scheme Ruby All arithmetic, relational, and assignment operators, as well as array indexing, shifts, and bit-wise logic operators, are implemented as methods - One result of this is that these operators can all be overriden by application programs Scheme (and Common Lisp) - All arithmetic and logic operations are by explicitly called subprograms - a + b * c is coded as (+ a (* b c)) Arithmetic Expressions: Conditional Expressions Conditional Expressions C-based languages (e.g., C, C++) An example: average = (count == 0)? 0 : sum / count Evaluates as if written as follows: if (count == 0) average = 0 else average = sum /count Arithmetic Expressions: Operand Evaluation Order Operand evaluation order 1. Variables: fetch the value from memory 2. Constants: sometimes a fetch from memory; sometimes the constant is in the machine language instruction 3. Parenthesized expressions: evaluate all operands and operators first 4. The most interesting case is when an operand is a function call Arithmetic Expressions: Potentials for Side Effects Functional side effects: when a function changes a two-way parameter or a non-local variable Problem with functional side effects: When a function referenced in an expression alters another operand of the expression; e.g., for a parameter change: a = 10; b = a + fun(&a); Functional Side Effects Two possible solutions to the problem 1. Write the language definition to disallow functional side effects No two-way parameters in functions No non-local references in functions Advantage: it works! Disadvantage: inflexibility of one-way parameters and lack of non-local references 2. Write the language definition to demand that operand evaluation order be fixed Disadvantage: limits some compiler optimizations Java requires that operands appear to be evaluated in left-to-right order Referential Transparency A program has the property of referential transparency if any two expressions in the program that have the same value can be substituted for one another anywhere in the program, without affecting the action of the program result1 = (fun(a) + b) / (fun(a) – c); temp = fun(a); result2 = (temp + b) / (temp – c); If fun has no side effects, result1 = result2 Otherwise, not, and referential transparency is violated Referential Transparency (continued) Advantage of referential transparency Semantics of a program is much easier to understand if it has referential transparency Because they do not have variables, programs in pure functional languages are referentially transparent Functions cannot have state, which would be stored in local variables If a function uses an outside value, it must be a constant (there are no variables). So, the value of a function depends only on its parameters Overloaded Operators Use of an operator for more than one purpose is called operator overloading Some are common (e.g., + for int and float) Some are potential trouble (e.g., * in C and C++) Loss of compiler error detection (omission of an operand should be a detectable error) Some loss of readability Overloaded Operators (continued) C++, C#, and F# allow user-defined overloaded operators When sensibly used, such operators can be an aid to readability (avoid method calls, expressions appear natural) Potential problems: Users can define nonsense operations Readability may suffer, even when the operators make sense Type Conversions A narrowing conversion is one that converts an object to a type that cannot include all of the values of the original type e.g., float to int A widening conversion is one in which an object is converted to a type that can include at least approximations to all of the values of the original type e.g., int to float Type Conversions: Mixed Mode A mixed-mode expression is one that has operands of different types A coercion is an implicit type conversion Disadvantage of coercions: They decrease in the type error detection ability of the compiler In most languages, all numeric types are coerced in expressions, using widening conversions In ML and F#, there are no coercions in expressions Explicit Type Conversions Called casting in C-based languages Examples C: (int)angle F#: float(sum) Note that F#’s syntax is similar to that of function calls Errors in Expressions Causes Inherent limitations of arithmetic zero Limitations of computer arithmetic Often ignored by the run-time system e.g., division by e.g. overflow Relational and Boolean Expressions Relational Expressions Use relational operators and operands of various types Evaluate to some Boolean representation Operator symbols used vary somewhat among languages (!=, /=, ~=,.NE., , #) JavaScript and PHP have two additional relational operator, === and !== - Similar to their cousins, == and !=, except that they do not coerce their operands Ruby uses == for equality relation operator that uses coercions and eql? for those that do not Relational and Boolean Expressions Boolean Expressions Operands are Boolean and the result is Boolean Example operators C89 has no Boolean type--it uses int type with 0 for false and nonzero for true One odd characteristic of C’s expressions: a < b < c is a legal expression, but the result is not what you might expect: Left operator is evaluated, producing 0 or 1 The evaluation result is then compared with the third operand (i.e., c) Short Circuit Evaluation An expression in which the result is determined without evaluating all of the operands and/or operators Example: (13 * a) * (b / 13 – 1) If a is zero, there is no need to evaluate (b /13 - 1) Problem with non-short-circuit evaluation index = 0; while (index b) || (b++ / 3) Assignment Statements The general syntax The assignment operator = Fortran, BASIC, the C-based languages := Ada = can be bad when it is overloaded for the relational operator for equality (that’s why the C-based languages use == as the relational operator) Assignment Statements: Conditional Targets Conditional targets (Perl) ($flag ? $total : $subtotal) = 0 Which is equivalent to if ($flag){ $total = 0 } else { $subtotal = 0 } Assignment Statements: Compound Assignment Operators A shorthand method of specifying a commonly needed form of assignment Introduced in ALGOL; adopted by C and the C-based languaes Example a = a + b can be written as a += b Assignment Statements: Unary Assignment Operators Unary assignment operators in C-based languages combine increment and decrement operations with assignment Examples sum = ++count (count incremented, then assigned to sum) sum = count++ (count assigned to sum, then incremented count++ (count incremented) -count++ (count incremented then negated) Assignment as an Expression In the C-based languages, Perl, and JavaScript, the assignment statement produces a result and can be used as an operand while ((ch = getchar())!= EOF){…} is carried out; the result (assigned to ch) is used as a conditional value for the while statement Disadvantage: another kind of expression side effect ch = getchar() Multiple Assignments Perl and Ruby allow multiple-target multiple-source assignments ($first, $second, $third) = (20, 30, 40); Also, the following is legal and performs an interchange: ($first, $second) = ($second, $first); Assignment in Functional Languages Identifiers in functional languages are only names of values ML Names are bound to values with val val fruit = apples + oranges; - If another val for fruit follows, it is a new and different name F# F#’s let is like ML’s val, except let also creates a new scope Mixed-Mode Assignment Assignment statements can also be mixed-mode In Fortran, C, Perl, and C++, any numeric type value can be assigned to any numeric type variable In Java and C#, only widening assignment coercions are done In Ada, there is no assignment coercion Summary Expressions Operator precedence and associativity Operator overloading Mixed-type expressions Various forms of assignment Thank You ‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Bachelor of Science in Computer Science CS363 Principles of Programming Languages Week 8 Statement-Level Control Structures Subprograms Contents 1. Selection and Iterative Statements 2. Unconditional Branching 3. Guarded Commands 4. Fundamentals and Design Issues of Subprograms 5. Local Referencing Environments Weekly Learning Outcomes 1. Describe selection statements, for both two-way and multiple selection. 2. Discuss the variety of looping statements that have been developed and used in programming languages. 3. Discuss the problems associated with unconditional branch statements. 4. Describe the guarded command control statements. 5. Discuss the design of subprograms, including parameter-passing methods, local referencing environments. 287 Required Reading Chapter 8 + Chapter 9 (9.1-9.4) Concepts of Programming Languages, Robert W. Sebesta, 12th Edition, Pearson, 2019 ISBN-13: 978-0-13499718-6 Recommended Reading Chapter 5 Louden, K.C. and Lambert, K.A., 2011. Programming languages: principles and practices. Cengage Learning Levels of Control Flow – Within expressions (Chapter 7) – Among program units (Chapter 9) – Among program statements (this chapter) Control Statements: Evolution FORTRAN I control statements were based directly on IBM 704 hardware Much research and argument in the 1960s about the issue One important result: It was proven that all algorithms represented by flowcharts can be coded with only two-way selection and pretest logical loops Control Structure A control structure is a control statement and the statements whose execution it controls Design question Should a control structure have multiple entries? Selection Statements A selection statement provides the means of choosing between two or more paths of execution Two general categories: Two-way selectors Multiple-way selectors Two-Way Selection Statements General form: if control_expression then clause else clause Design Issues: What is the form and type of the control expression? How are the then and else clauses specified? How should the meaning of nested selectors be specified? The Control Expression If the then reserved word or some other syntactic marker is not used to introduce the then clause, the control expression is placed in parentheses In C89, C99, Python, and C++, the control expression can be arithmetic In most other languages, the control expression must be Boolean Clause Form In many contemporary languages, the then and else clauses can be single statements or compound statements In Perl, all clauses must be delimited by braces (they must be compound) In Python and Ruby, clauses are statement sequences Python uses indentation to define clauses if x > y : x = y print " x was greater than y" Nesting Selectors Java example if (sum == 0) if (count == 0) result = 0; else result = 1; Which if gets the else? Java's static semantics rule: else matches with the nearest previous if Nesting Selectors (continued) To force an alternative semantics, compound statements may be used: if (sum == 0) { if (count == 0) result = 0; } else result = 1; The above solution is used in C, C++, and C# Nesting Selectors (continued) Statement sequences as clauses: Ruby if sum == 0 then if count == 0 then result = 0 else result = 1 end end Nesting Selectors (continued) Python if sum == 0 : if count == 0 : result = 0 else : result = 1 Selector Expressions In ML, F#, and Lisp, the selector is an expression; in F#: let y = if x > 0 then x else 2 * x - If the if expression returns a value, there must be an else clause (the expression could produce a unit type, which has no value). The types of the values returned by then and else clauses must be the same. Multiple-Way Selection Statements Allow the selection of one of any number of statements or statement groups Design Issues: 1. What is the form and type of the control expression? 2. How are the selectable segments specified? 3. Is execution flow through the structure restricted to include just a single selectable segment? 4. How are case values specified? 5. What is done about unrepresented expression values? Multiple-Way Selection: Examples C, C++, Java, and JavaScript switch (expression) { case const_expr1: stmt1; … case const_exprn: stmtn; [default: stmtn+1] } Multiple-Way Selection: Examples Design choices for C’s switch statement 1. Control expression can be only an integer type 2. Selectable segments can be statement sequences, blocks, or compound statements 3. Any number of segments can be executed in one execution of the construct (there is no implicit branch at the end of selectable segments) 4. default clause is for unrepresented values (if there is no default, the whole statement does nothing) Multiple-Way Selection: Examples C# Differs from C in that it has a static semantics rule that disallows the implicit execution of more than one segment Each selectable segment must end with an unconditional branch (goto or break) Also, in C# the control expression and the case constants can be strings Multiple-Way Selection: Examples Ruby has two forms of leap = case when year when year else year end case statements-we’ll cover only one % 400 == 0 then true % 100 == 0 then false % 4 == 0 Implementing Multiple Selectors Approaches: Multiple conditional branches Store case values in a table and use a linear search of the table When there are more than ten cases, a hash table of case values can be used If the number of cases is small and more than half of the whole range of case values are represented, an array whose indices are the case values and whose values are the case labels can be used Multiple-Way Selection Using if Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses, for example in Python: if count < 10 : bag1 = True elif count < 100 : bag2 = True elif count < 1000 : bag3 = True Multiple-Way Selection Using if The Python example can be written as a Ruby case case when count < 10 then bag1 = true when count < 100 then bag2 = true when count < 1000 then bag3 = true end Scheme’s Multiple Selector General form of a call to COND: (COND (predicate1 expression1) … (predicaten expressionn) [(ELSE expressionn+1)] ) - The ELSE clause is optional; ELSE is a synonym for true - Each predicate-expression pair is a parameter - Semantics: The value of the evaluation of COND is the value of the expression associated with the first predicate expression that is true Iterative Statements The repeated execution of a statement or compound statement is accomplished either by iteration or recursion General design issues for iteration control statements: 1. How is iteration controlled? 2. Where is the control mechanism in the loop? Counter-Controlled Loops A counting iterative statement has a loop variable, and a means of specifying the initial and terminal, and stepsize values Design Issues: 1. What are the type and scope of the loop variable? 2. Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control? 3. Should the loop parameters be evaluated only once, or once for every iteration? 4. What is the value of the loop variable after loop termination? Counter-Controlled Loops: Examples C-based languages for ([expr_1] ; [expr_2] ; [expr_3]) statement - The expressions can be whole statements, or even statement sequences, with the statements separated by commas The value of a multiple-statement expression is the value of the last statement in the expression If the second expression is absent, it is an infinite loop Design choices: - There is no explicit loop variable - Everything can be changed in the loop - The first expression is evaluated once, but the other two are evaluated with each iteration - It is legal to branch into the body of a for loop in C Counter-Controlled Loops: Examples C++ differs from C in two ways: 1. The control expression can also be Boolean 2. The initial expression can include variable definitions (scope is from the definition to the end of the loop body) Java and C# Differs from C++ in that the control expression must be Boolean Counter-Controlled Loops: Examples Python for loop_variable in object: - loop body [else: - else clause] The object is often a range, which is either a list of values in brackets ([2, 4, 6]), or a call to the range function, as in range(5), which returns 0, 1, 2, 3, 4 The loop variable takes on the values specified in the given range, one for each iteration At loop termination, the loop variable has the last value that was assigned to it The else clause, which is optional, is executed if the loop terminates normally Counter-Controlled Loops: Examples F# Because counters require variables, and functional languages do not have variables, counter-controlled loops must be simulated with recursive functions let rec forLoop loopBody reps = if reps

CS363 Midterm Slides .pdf

Document Details

Tags

Related

Full Transcript

Upgrade to continue