IP University - POPL - Unit 2 Notes

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

Primitive Data Types

In computer science, primitive data type is either of the following:

• a basic type is a data type provided by a programming language as a basic building block. Most languages allow more complicated composite types to be recursively constructed starting from basic types.
• a built-in type is a data type for which the programming language provides built-in support.

Classic basic primitive types may include:

• Character (character, char);
• Integer (integer, int, short, long, byte) with a variety of precisions;
• Floating-point number (float, double, real, double precision);
• Fixed-point number (fixed) with a variety of precisions and a programmer-selected scale.
• Boolean, logical values true and false.
• Reference (also called a pointer or handle or descriptor), a value referring to another object.

Pointers

• a programming language object that stores a memory address
• can be that of another value located in computer memory, or in some cases, that of memory mapped computer hardware
• references a location in memory, and obtaining the value stored at that location is known as dereferencing the pointer
• using them improves performance for repetitive operations like traversing iterable data structures
• cheaper in time and space to copy and dereference pointers than it is to copy and access the data to which the pointers point
• also used to hold the addresses of entry points for called subroutines in procedural programming and for run-time linking to dynamic link libraries (DLLs)
• in OOP, pointers to functions are used for binding methods, often using what are called virtual method tables

int a = 5;
int *ptr = NULL;
ptr = &a;

Structured type

• compound data type which falls under user-defined category
• used for grouping simple data types or other compound data types
• contains a sequence of member variable names along with their type/attributes

struct <struct name> {
    <type> <member>;
};

• members inside a structure are placed sequentially next to next in the memory layout
• minimum size of a structure is the sum total of all sizes of members, considering padding

Coercion

• coercion : implicit conversion of a value into another of a different data type (it is automatically done)
• casting : explicit conversion performed by code instructions
• treats a variable of one data type as if it belongs to a different data type
• languages that support implicit conversion define the rules that will be automatically applied when primitive compatible values are involved

double x, y;
x = 3;            // implicitly coercion (coercion)
y = (double) 5;   // explicitly coercion (casting)

• function/operator considered polymorphic one when it is permited to perform implicit or explicit parameter/operand coercion

#include <iostream>
void f(double x) {     // polymorphic function
  std::cout << x << std::endl;
}

int main() {
  double a = 5 + 6.3;  // polymorphic operator
  std::cout << a << std::endl;
  f(5);
  f((double) 6);
}

Type Equivalence

• Type is a property of program constructs such as expressions
• defines a set of values (range of variables) and a set of operations on those values
• classes are one instantiation of the modern notion of the type

Type Systems

• a collection of rules that assign types to program constructs (more constraints added to checking the validity of the programs, violation of such constraints indicate errors)
• languages type system specifies which operations are valid for which types
• type systems provide a concise formalization of the semantic checking rules
• type rules are defined on the structure of expressions
• type rules are language specific

Type Checking

• is the process of verifying fully typed programs
• type checking rules usually have the form:
  • if two type expressions are equivalent
  • then return a given type
  • else return type_error
• to define when two given type expressions are equivalent.
• modern languages allow the naming of user-defined types.
• two possibilities.
  • Name equivalence : treat named types as basic types, two type expressions are name equivalent if and only if they are identical, that is if they can be represented by the same syntax tree, with the same labels.
  • Structural equivalence : replace the named types by their definitions and recursively check the substituted trees.

Static and Dynamic Type Checking

• Statically typed languages: all or almost all type checking occurs at compilation time. (C, Java)
• Dynamically typed languages: almost all checking of types is done as part of program execution (Scheme)
• Untyped languages: no type checking (assembly, machine code)

Tradeoffs

• static type system :
  • does not have knowledge of input values or execution behaviors
  • disallows some correct programs, cannot predict precisely all the behaviors (some program runs correctly will be rejected)
  • catches many programming errors at compile time
  • avoids overhead of runtime type checking
  • are more restrictive; can require more work to do reasonable things
• rapid prototyping easier in a dynamic type system.

Object Oriented Concepts

• programming paradigm based on the concept of objects, which can contain:
  • data, in the form of fields (often known as attributes or properties)
  • code, in the form of procedures/methods.
• an object’s procedures can access and often modify the data fields of the object with which they are associated (objects have a notion of this or self)
• programs are designed by making them out of objects that interact with one another

Objects and classes

• languages that support OOP use inheritance for code reuse and extensibility in the form of classes
• classes – the definitions for the data format and available procedures for a given type or class of object; may also contain data and procedures
• objects – instances of classes
• leads to the following terms:
  • class variables – belong to the class as a whole; there is only one copy of each one
  • attributes – data that belongs to individual objects; every object has its own copy
  • member variables – refers to both the class and instance variables that are defined by a particular class
  • class methods – belong to the class as a whole and have access only to class variables and inputs from the procedure call
  • instance methods – belong to individual objects, and have access to instance variables for the specific object they are called on, inputs, and class variables
• objects are accessed like variables with complex internal structure
• in many languages are effectively pointers, serving as actual references to a single instance of said object in memory within a heap or stack
• provide a layer of abstraction which can be used to separate internal from external code

Information Hiding

• the principle of segregation of the design decisions in a computer program that are most likely to change
• protecting other parts of the program from extensive modification if the design decision is changed
• providing a stable interface which protects the remainder of the program from the implementation (the details that are most likely to change)
• think of information hiding as being the principle and encapsulation being the technique

Encapsulation

• the bundling of data with the methods that operate on that data
• restricting of direct access to some of an object’s components
• to hide the values or state of a structured data object inside a class, preventing unauthorized parties’ direct access to them
• using “getters” and “setters” to access the values, and other client classes call these methods to retrieve and modify the values within the object.

Abstraction

• the process of removing details or attributes in the study of objects or systems to focus attention on details of greater importance
• the creation of abstract concept-objects by mirroring common features or attributes of various non-abstract objects
• Abstract Data type (ADT) is a type (or class) for objects whose
  • behaviour is defined by a set of value and a set of operations
  • only mentions what operations are to be performed but not how these operations will be implemented
  • does not specify how data will be organized in memory and what algorithms will be used for implementing the operations
  • called “abstract” because it gives an implementation-independent view.

Inheritance

• mechanism of basing an object or class upon another object (prototype-based inheritance) or class (class-based inheritance), retaining similar implementation
• deriving new classes (sub classes) from existing ones (super class or base class) and forming them into a hierarchy of classes
• in most class-based object-oriented languages, an object created through inheritance (a “child object”) acquires all the properties and behaviors of the parent object (except: constructors, destructor, overloaded operators and friend functions of the base class)
• it allows :
  • programmers to create classes that are built upon existing classes
  • to specify a new implementation while maintaining the same behaviors
  • to reuse code and to independently extend original software via public classes and interfaces.

Type Parameterization

• type parameterization is a frequently used mechanism used in templates to reference an unknown data type, data structure, or class
• Templates are most frequently used in Java and C++
• part of generic programming, in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters.

Polymorphism

• the provision of a single interface to entities of different types or the use of a single symbol to represent multiple different types
• classes of polymorphism are:
  • Ad hoc polymorphism: defines a common interface for an arbitrary set of individually specified types (includes function and operator overloading).
  • Parametric polymorphism: when one or more types are not specified by name but by abstract symbols that can represent any type.
  • Subtyping: when a name denotes instances of many different classes related by some common superclass.

Function Overloading vs. Function Overriding

• inheritance: overriding of functions occurs when one class is inherited from another class. overloading can occur without inheritance.
• signature: overloaded functions must differ in function signature ie either number of parameters or type of parameters should differ. In overriding, function signatures must be same.
• scope of functions: overridden functions are in different scopes; whereas overloaded functions are in same scope.
• Behavior of functions:
  • overriding is needed when derived class function has to do some added or different job than the base class function
  • overloading is used to have same name functions which behave differently depending upon parameters passed to them.

Python modules vs packages

A module is a single file (or files) that are imported under one import and used. e.g.

import my_module

A package is a collection of modules in directories that give a package hierarchy.

from my_package.timing.danger.internets import function_yo