Programming Language Concepts: Semantics, Bindings, Scoping, and More

Posted on Sep 3, 2024 in Computers

Programming Language Concepts

BNF and EBNF

Understand how to describe language features, such as loops, using BNF or EBNF. Be able to convert between these two notations.

BNF Example

+ | - | * | /

EBNF Example

} -> {

Semantic Languages

Learn about attribute grammars, operational semantics, denotational semantics, and axiomatic semantics. Understand their purpose and how they function.

Attribute Grammars: Contain semantic information on parse tree nodes. Used for static semantics specification and compiler design. A context-free grammar G = (S,N,T,P) where each grammar symbol x has a set A(x) of attribute values. Each rule defines attributes of nonterminals and includes predicates for attribute consistency.
Operational Semantics: Used in language manuals, textbooks, and for teaching programming. Two levels: natural (informal) and structural (formal). Can be complex for formal specifications.
Denotational Semantics: Recursive and the most abstract approach. Example: s = {, } VARMAP (ij,s) = vj
Axiomatic Semantics: Used for formal program verification and formal logic. Employs assertions to state relationships and constraints among variables at a specific execution point. The weakest precondition guarantees the postcondition. Example: a=b+1 {a>1} weakest precondition = b>0.

Bindings

Understand the mechanisms of static binding and dynamic binding rules.

Binding Time: The moment an entity is associated with its attribute (e.g., variable and value, operation and symbol).
Static Binding: Occurs before runtime and remains unchanged.
Dynamic Binding: Happens at runtime or can change during execution.

Scoping

Learn how static scoping and dynamic scoping rules work.

Static Scoping: Based on program text. Searches for declarations locally, then in larger enclosing scopes until found. Variables can be hidden by closer variables with the same name. Some languages, like Ada, allow access to hidden values (e.g., unit.name).
Dynamic Scoping: Based on the calling sequence. Subprogram calls determine variable linking.

Type Equivalence

Distinguish between structural equivalence and name equivalence.

Name Equivalence: Values have the same type based on the fully qualified name of their type. For example, a and b are name equivalent if both are declared as “int”.
Structural Equivalence: Values have the same type if their types are structurally identical, regardless of the name. Name equivalence implies structural equivalence.

Note that primitive types do have type names (e.g., “int”). C’s type system is primarily by name, meaning int* and short* are different types even with the same representation. Similarly, struct foo { int x;} and struct bar { int x;} are distinct types.

Data Types

Understand data structures like arrays and records, advantages and disadvantages of various data types, language-specific data type support, implementation details, type checking mechanisms, strongly typed languages, and data type evolution.

Primitive Data Types: Not defined in terms of other data types, often reflecting hardware.
Strings: Implementations vary across languages (e.g., char arrays in C/C++, primitive with operations in Python, string class in Java).
Arrays: Different languages use different syntax (e.g., () in Fortran and Ada, [] in most others) and have varying index types and range checking mechanisms.
Rectangular vs. Jagged Arrays: Rectangular arrays have the same number of elements in each row and column. Jagged arrays allow varying numbers of elements in rows.
Strongly Typed Languages: Detect type errors consistently. Ada, Java, and C# are examples, although coercion rules can impact strong typing.

Expressions and Assignment Statements

Understand various expressions, operator precedence, operator overloading, type conversions, coercions, short-circuit evaluations, and assignment statements.

Operator Overloading: Allows operators to have different meanings depending on the context. Can enhance readability but may also reduce compiler error detection and introduce ambiguity.
Type Conversions: Explicitly changing a value from one type to another. Narrowing conversions can lead to information loss.
Coercions: Implicit type conversions in mixed-mode expressions. Can weaken type error detection.
Short-Circuit Evaluation: Evaluating only the necessary parts of an expression. Improves efficiency but can alter program behavior if side effects are present.
Assignment Statements: Syntax varies across languages (e.g., = in Fortran, BASIC, C; := in Ada).

Control Structures

Explore selections, iterations, and other control structures in languages like Ada, Fortran, Python, and F#.

Ada Example

procedure Arr1 is
   A: array(1..5) of Integer;   
   I: Integer;
begin
   -- Read 'em in.
   for I in 1..5 loop
      Put("> ");
      Get(A(I));
   end loop;

   -- Put 'em out in reverse order.
   Put("[");
   for I in reverse A'Range loop
      Put(A(I));
      if I > A'First then
         Put(' ');
      end if;
   end loop;
   Put_Line("]");
end Arr1;

Fortran Example

real :: v1(3), v2(3), m(3,3)
integer :: i,j
v1(1) = 0.25
v1(2) = 1.2
v1(3) = 0.2

! to the unit matrix
do i=1,3
 do j=1,3
  m(j,i) = 0.0
 end do
 m(i,i) = 2.0

enddo

Python Example

for loop_variable in object:
    # loop body
[else:
    # else clause]
# current, next, reset

F# Example

let rec forLooop loopBody reps =
    if reps

Subprograms

Understand parameter passing mechanisms (in, out, inout), parameter passing methods (value, reference, name, value/result), language implementations (activation records, static and dynamic links, scoping), and other features like displays.

Parameter Passing: Different languages support different parameter passing mechanisms (e.g., in, out, inout) and methods (e.g., pass by value, pass by reference).
Activation Records: Data structures created for each subprogram call, containing information like return address, parameters, and local variables.
Static and Dynamic Links: Used to manage the call stack and access non-local variables in nested subprograms.
Scoping: Determines the visibility and lifetime of variables within subprograms.

Parameter Passing Examples

C: Pass by value, pass by reference
C++: Reference types for pass by reference
Java: All parameters passed by value, object parameters passed by reference
Ada: In, out, in out (in is default)
Fortran: In, out, inout
C#: Pass by value, reference
PHP: Similar to C#
Perl: Parameters placed in an array
Python, Ruby: Pass by assignment (all values are objects)

Activation Record Structure

Return Address -> (Dynamic Link) -> Parameters -> Local Variables

The dynamic link points to the beginning of the previous activation record on the call stack.

Static and Dynamic Chains

Static Chains: Used in statically scoped languages to access non-local variables in nested subprograms.
Dynamic Chains: Used in dynamically scoped languages, along with central variable tables, to manage variable access.

Chain Offset

of nesting depth of a nonlocal reference is the difference between the static depth of the reference, and where it was declared. (chainoffset, local_offset)

Programming Language Concepts: Semantics, Bindings, Scoping, and More