Kamis, 28 Desember 2017

Names, Bindings, and Scopes

Names

•Length
–If too short, they cannot be connotative
–Language examples:
•FORTRAN 95: maximum of 31
•C99: no limit but only the first 63 are significant; also, external names are limited to a maximum of 31
•C#, Ada, and Java: no limit, and all are significant
•C++: no limit, but implementers often impose one

•Special character
–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
•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)

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

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     

 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
•Variables can be hidden from a unit by having a "closer" variable with the same name
•Ada allows access to these "hidden" variables
–E.g.,  unit.name


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
•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


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;
                   }
–Static scoping
•Reference to x in sub2 is to big's x
–Dynamic scoping
•Reference to x in sub2 is to sub1's x
                


Reference
•Robert W. Sebesta - Concept of Programming Languages (Tenth Edition), Chapter 5






Describing Syntax and Semantics

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
•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 Rules

•An abstraction (or nonterminal symbol) can have more than one RHS
     <stmt> ® <single_stmt>
             | begin <stmt_list> end

Describing Lists

Syntactic lists are described using recursion

    <ident_list> ® ident
                | ident, <ident_list>
A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)

     An Example Grammar

 <program> ® <stmts>
   <stmts> ® <stmt> | <stmt> ; <stmts>
   <stmt> ® <var> = <expr>
   <var> ® a | b | c | d
   <expr> ® <term> + <term> | <term> - <term>
   <term> ® <var> | const

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)


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



Denotational Semantics


•Based on recursive function theory
•The most abstract semantics description method
•Originally developed by Scott and Strachey (1970)
•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


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.
•Pre-, post form:  {P} statement {Q}
•An example
–a = b + 1  {a > 1}
–One possible precondition: {b > 10}
–Weakest precondition:        {b > 0}


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



Reference
Robert W. Sebesta - Concept of Programming Languages (Tenth Edition), Chapter 3







Introduction to Programming Language Concept

Programming Domains

•Scientific applications•Business applications•Artificial intelligence•Systems programming•Web Software


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

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


The von Neumann Architecture



Programming Methodologies Influences


•1950's and early 1960's: Simple applications; worry about machine efficiency
•Late 1960's: People efficiency became important; readability, better control structures
–structured programming
–top-down design and step-wise refinement
•Late 1970's: Process-oriented to data-oriented
–data abstraction
•Middle 1980's: Object-oriented programming
–Data abstraction + inheritance + polymorph


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


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

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)




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)









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
•The major methods of implementing programming languages are: compilation, pure interpretation, and hybrid implementation



Reference

Robert W. Sebesta - Concept of Programming Languages (Tenth Edition), Chapter 1