Programming Languages: Orthogonality and Semantics

Orthogonality

• Orthogonality is when a small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of a programming language.

Compiled vs. Interpreted Languages

• Compiled Language: A program is expressed in the instructions of the target machine after compilation, with the resulting machine code unreadable by humans.
• Interpreted Language: Instructions are not directly executed by the target machine. Instead, they are read and executed by another program.
• Java is technically both compiled and interpreted but is considered an interpreted language.

BNF

• Backus-Naur Form (BNF) is used to build derivations and parse trees.
• Grammar productions:
  • → =
  • → A | B | C
  • → +
  • | *
  • |()
  • |

Ambiguous Grammar

• Grammar is ambiguous if it generates a sentential form with two or more distinct parse trees.

Denotational Semantics

• Denotational semantics is used for formally defining the meaning of programming language constructs by assigning them mathematical objects.
• Strength includes accuracy with mathematical objects.
• Weakness includes making the program more complex and harder to execute.
• Denotational semantics is rigorous but complex.
• Chapter 3, slides 48 - 55

Axiomatic Semantics

• Axiomatic semantics defines the meaning of a programming language construct by describing its effect on logical assertions about the program state.
• Allows for formal verification, but is not easy to apply to a complex program.
• Axiomatic semantics is mainly used for verifying the correctness of a program.
• Chapter 3 slides 61-72
• Not easy to apply to a complex program.

Code Validity

• Example valid code:

  {a < 5}
   b=a-10
   c = 20 - 5* b {c > 5}

Lexical Analysis

• Lexical analysis is processing source code to convert a sequence of characters.
• The first phase of a compiler or interpreter.
• Lexeme: A basic lexical unit of a language, consisting of one or several words, considered as an abstract unit.
• Token: A categorized single unit of meaning, generated from a lexeme.
• Chapter 4

Syntax Analysis

• Syntax analysis: is the second phase of a compiler or interpreter.
• Takes a sequence of tokens and organizes them into a parse tree.

Pairwise Disjointness Tests

• Used in parsing to ensure that the grammar is not ambiguous.
• FIRST(aB) = {a}, FIRST(b) = {b}, FIRST(cBB) = {c}, Passes the test
• FIRST(aB) = {a}, FIRST(bA) = {b}, FIRST(aBb) = {a}, Fails the test
• FIRST(aaA) = {a}, FIRST(b) = {b}, FIRST(caB) = {c}, Passes the test

Binding and Binding Time

• Binding: An association between an entity and an attribute.
• The tradeoffs includes space and time.
• Chapter 5

Lifetime and Scope

• Lifetime: The duration for which a variable exists in memory during program execution.
• Scope: The visibility of a variable.

Array Types

• Static: Subscript ranges are statically bound, and storage allocation is static.
• Advantages: Static arrays has efficiency due to no dynamic allocation.
• Fixed stack-dynamic: Subscript ranges are statically bound, but allocation is done at declaration time.
• Advantages: Fixed stack-dynamic arrays have space efficiency
• Fixed heap-dynamic: Storage binding is dynamic but fixed after allocation. Storage is allocated from the heap, not the stack.
• Heap-dynamic: Binding of subscript ranges and storage allocation is dynamic and can change any number of times.
• Advantage: Heap-dynamic arrays have flexibility with arrays that can grow or shrink during program execution.
• Chapter 6, slides 36, 37, 38, 39

Type Errors

• A type error is the application of an operator to an operand of an inappropriate type.
• Type checking ensures that the operands of an operator are of compatible types.
• A compatible type is one that is either legal for the operator or can be implicitly converted to a legal type.
• Coercion: Automatic conversion by compiler-generated code to a legal type.
• Chapter 6

Arrays

• An array is a homogeneous aggregate of data elements where each element is identified by its position in the aggregate relative to the first element.
• Discuss array types, be able to explain row major vs row column order and how index location is computed for multidimensional arrays.
• Chapter 6

Garbage Collection

• Garbage collection (as in Java) provides ease of use and safety.
• Poses challenges for real-time systems due to non-deterministic pauses and overhead.
• C++'s explicit memory management allows greater control and predictability.
• Results in increased complexity and potential errors.

Matrices

• Jagged Matrices and Sparse Matrix Representation.
• Rectangular Matrices.
• Both should be included in a programming language due for efficacy and flexibility.

Static vs. Dynamic Type Checking

• Static type checking provides stronger guarantees about type correctness.
• Results in increased reliability, performance, and maintainability.

Coercion Rules

• Coercion rules can weaken the beneficial effect of strong typing by automatically converting data types without explicit instruction.

Operators

• Major groups of operators: arithmetic, relational, logical, assignment, bitwise, and sometimes string operators.
• Ternary operator: A conditional operator with three operands: a condition, an expression to execute if the condition is true, and an expression to execute if the condition is false.
• Prefix operators: Operators that appear before their operand.
• Perform an operation on their operand, return a value, and may modify the value of the operand or produce a new result.
• Associative operators: Defines how operators of the same precedence are grouped in the absence of parentheses.

Multiple Assignments

• Multiple assignments allow assigning values to multiple variables in a single statement or expression.
• Python and JavaScript support multiple assignments.