IP University - POPL - Unit 1 Notes

27 Jan 2020

This post gives a quick review on the first unit of the syllabus for the Principles of Progamming Languages (POPL) subject in the IP University syllabus.

Syntax, Semantics and Pragmatics

In linguistics of both natural and computer languages, syntax, semantics and pragmatics are used to categorize descriptions of language characteristics.

Syntax :

• describes structure, composition of allowable phrases and sentences of the language
• by itself devoid of meaning, simply tell us :
  • what strings are valid
  • how they may be parsed or decomposed

Semantics :

• provide the meaning of these syntactic elements
• we may think of providing syntactic elements as inputs to a semantic function, which in turn provides some representation of the meaning of the elements as output
• the semantic function of a programming language may be considered to be embedded in the logic of a compiler or intepreter which arranges for program execution
• an equivalent semantic function, albeit using a different representation, should also be found in the mind of the programmer

Pragmatics

• practical aspects of how constructs and features of a language may be used to achieve various objectives.
• aims to explain how and why people use languages in the way they do
• what we think of when we talk about programmers’ competence or “best practices” or patterns and anti-patterns

Example :

• consider the syntax, semantics and pragmatics of an assignment statement
• Syntax : it may consist of a variable and an expression (themselves syntactic constructs), separated by the token = as an assignment operator
• Semantics : the variable denotes a location in computer memory, while the expression denotes computation of a value based on the contents of memory. Overall, the semantics of assignment is to perform the expression evaluation based on current memory contents and then update the value stored in the particular location corresponding to the variable.
• Pragmatics : what assignment statements are useful for. There are many possibilities: to set up a temporary variable for the value of an expression that is needed more than once, to communicate values from one part of a program to another, to modify part of a data structure, or to set successive values of a variable used in some iterative computation.

Formal Translation Models

¯\_(ツ)_/¯

Variables, Expressions and Statements

Variables :

• a storage address paired with an associated symbolic name, which contains some known or unknown quantity of information referred to as a value
• way to reference the stored value, in addition to referring to the variable itself, depending on the context
• separation of name and content allows the name to be used independently of the exact information it represents
• variable’s storage address may be referenced by several different identifiers (aliasing)

Expressions :

• combination of one or more constants, variables, operators, and functions that the programming language interprets and computes to produce another value
• the resulting value is usually one of various primitive types, such as numerical, string, boolean, complex data type or many others

Statements :

• syntactic unit of an imperative programming language that expresses some action to be carried out
• program written in such a language is formed by a sequence of one or more statements
• statements contrast with expressions in that statements do not return results and are executed solely for their side effects, while expressions always return a result and often do not have side effects at all

Binding Time

• source file has many names whose properties need to be determined
• meaning of these properties might be determined at different phases of the life cycle of a program
• examples of such properties include:
  • set of values associated with a type
  • type of a variable
  • memory location of the compiled function
  • value stored in a variable
• binding is the act of associating properties with names.
• binding time - the time at which a binding takes place. It can take place at :
  • language design time
    • set of possible types for a variable
    • set of possible meanings for an operator symbol
  • language implementation time
    • A data type, such as int in C, is bound to a range of possible values
  • compile time
    • variable is bound to a particular data type.
  • link time
    • call to a library subprogram is bound to the subprogram code.
  • load time
    • static variable may be bound to a memory cell when the program is loaded into memory.
  • run time
    • bind a nonstatic local variable to a memory cell

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

Static vs. Dynamic binding

• sb happens at the compile-time and db happens at the runtime. Hence, called early and late binding
• in sb function definition and call are linked during the compile-time, whereas in db the function calls are not resolved until runtime
• sb happens when all information needed to call a function is available at the compile-time, db happens when all information needed for a function call cannot be determined at compile-time.
• sb can be achieved using the normal function calls, function overloading and operator overloading while db is achieved using the virtual functions.
• sb results in faster execution of a program
• db is flexible since a single function can handle different type of objects at runtime (reduces the size of the codebase, makes source code more readable)

Assignment

• an assignment statement sets and/or re-sets the value stored in the storage location(s) denoted by a variable name; in other words, it copies a value into the variable
• Some languages use the idea of l-values and r-values, deriving from the typical mode of evaluation on the left and right hand side of an assignment statement.
• An l-value refers to an object that persists beyond a single expression. Has requirement that the operand on the left side of the assignment operator is modifiable, usually a variable.
• An r-value is a temporary value that does not persist beyond the expression that uses it. Pulls or fetches the value stored in a variable or constant.

Environments and Stores

Languages differ on where activation records must go in the environment:

• (Old) Fortran is static: all data, including activation records, are statically allocated. Each function has only one activation record — no recursion!
• Functional languages (Scheme, ML) and some OO languages (Smalltalk) are heap-oriented: almost all data, including AR, allocated dynamically.
• Most languages are in between: data can go anywhere ARs go on the stack.

Activation Record

An Activation Record (AR) is created for each invocation of a procedure

Storage Allocation

Static storage allocation

• names bound to storage locations.
• if memory created at compile time then the memory will be created in static area and only once.
• memory is created only at compile time and deallocated after program completion.
• size and position of data objects should be known at compile time.
• recursion procedure is restricted.

Stack Storage Allocation

• storage is organized as a stack.
• activation record pushed into stack when activation begins and popped when the activation ends.
• activation record contains locals so that they are bound to fresh storage in each activation record
• value of locals is deleted when the activation ends.
• works on LIFO mechanism
• supports the recursion process.

Heap Storage Allocation

• most flexible allocation scheme.
• allocation and deallocation of memory can be done at any time and at any place depending on user’s requirement
• used to allocate memory to the variables dynamically and when the variables are no more used then claim it back.
• supports the recursion process.

Constants

• a value that cannot be altered by the program during normal execution, i.e., the value is constant.
• when associated with an identifier, a constant is said to be “named,” although the terms “constant” and “named constant” are often used interchangeably
• contrasted with a variable, which is an identifier with a value that can be changed during normal execution, i.e., the value is variable
• useful for both programmers and compilers
  • for programmers they are a form of self-documenting code and allow reasoning about correctness
  • for compilers they allow compile-time and run-time checks that verify that constancy assumptions are not violated, and allow or simplify some compiler optimizations.

Initialization

• assignment of an initial value for a data object or variable
• manner in which initialization is performed depends on programming language, as well as type, storage class, etc., of an object to be initialized
• constructs which perform initialization are typically called initializers and initializer lists.
• distinct from (and preceded by) declaration, although sometimes conflated in practice
• done either by statically embedding the value at compile time, or else by assignment at run time.

Statement level control structure

• At least two additional linguistic mechanisms are necessary to make the computations in programs flexible and powerful:
  • means of selecting among alternative control flow paths
  • means of causing the repeated execution of statements or sequences of statements

Statements that provide these kinds of capabilities are called control statements. A control structure is a control statement and the collection of statements whose execution it controls.

Control Statements:

• Selection statements
  • two-way (if-else)
  • n-way or multiple selection (if-elif-else / switch)
• Loop statements
  • counter controlled loops (for)
  • logically controlled loops (while / do-while)
  • user located control mechanisms (break / continue)
  • based on data structures (for)
  • unconditional branching (goto)