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 applicationsBusiness applicationsArtificial intelligenceSystems programmingWeb 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