luo.box

Programming Languages Concepts

Published:

https://www.sci.brooklyn.cuny.edu/~chuang/books/sebesta.pdf

Motivaiton

Here I’m choosing 4 languages, Nix, a dynamic functional language, JavaScript, a dynamic object-orenited

General concepts

Syntax and Semantics

The study of programming languages, like the study of natural languages, can be divided into examinations of syntax and semantics. The syntax of a programming language is the form of its expressions, statements, and program units. Its semantics is the meaning of those expressions, statements, and program units.

In short, syntax means how to write it, semantics means how it type-checks and evaluates.

Describing Syntax

A language, whether natural (such as English) or artificial (such as Java), is a set of strings of characters from some alphabet. The strings of a langauge are called sentences or statements. The lowest-level syntactic units are called lexemes, programs are strings of lexemes. They are partitioned into groups represented by a token. Specifically, the names of variables, methods, classes form a group represented by a token called identifier.

Consider the following Java statement:

index = 2 * count;

The lexems and tokens of this statement are

LexemesTokens
indexidentifier
=equal_sign
2int_literal
*mult_op
countidentifier
;semicolon

Backus-Naur Form

A metalanguage is a language that is used to describe another language. BNF(Backus-Naur Form) is a metalanguage for programming languages. It uses abstractions for syntactic structures. A simple Java assignment statement, for example might be represented by the abstraction <assign>:

<assign> -> <var> = <expression>

The text on the left side of the arrow, which is aptly called the left-hand side(LHS), the right called the right-hand side(RHS). Altoghter, the definition is called a rule, or production.

The abstractions in a BNF description, or grammar, are often called nonterminal symbols, or simply nonterminals, and the lexemes and tokens of the rules are called terminal symbols, or simply terminals. A BNF description, or grammar, is a collection of rules.

A grammar for a small language:

<program> → begin <stmt_list> end

<stmt_list> → <stmt>
              | <stmt> ; <stmt_list>
<stmt> → <var> = <expression>
<var> → A | B | C
<expression> → <var> + <var>
              | <var> – <var>
              | <var>

grammars describes the hierarchical syntactic structure called parse trees of the sentences they define, a sentence generates more than one distinct parse trees is said to be ambiguous.

Names, bindings, and scopes

A name is a string of characters used to identify some entity in a program. In most languages, names are case sensitive. A keyword is a word that is special only in certain contexts. A reserved word is a special word that cannot be used as a name.

Variable

A variable is an abstraction of a computer memory cell or collection of cells. The move from machine languages to assembly languages was largely one of replacing absolute numeric memory addresses for data with names, it makes programs far more readable and escapes from manual absolute addressing. A variable can be characterized as a sextuple of attributes: (name, address, value, type, lifetime, and scope).

Address

The address of a variable is the machine memory address with which it is associated. In many langauges, it is possible for the same variable to be associated with different addresses at different times in the program. These are in a sense different instantiations of the same variable.

The address of a variable is sometimes called its l-value, because the address is what is required when the name of a variable appears in the left side of an assignment.

It is possible to have multiple variables that have the same address, the variables are called aliases. Aliases can be created in programs in several different ways, one common way in C and C++ is with their union types.

Two pointer variables are aliases when they point to the same memory location. The same is true for reference variables. This kind of aliasing is simply a side effect of the nature of pointers and references. When a C++ pointer is set to point at a named variable, the pointer, when dereferenced, and the variable’s name are aliases.

Type

The type of a variable determines the range of values the variable can store and the set of operations that are defined for values of the type.

Value

The value of a variable is the contents of the memory cell or cells associated with the variable. The physical cells of most modern computer memories are byte-size, which is too small for most program variable, hence the tern memory cell means abstract memory cell.

A variable’s value is sometimes called its r-value since it is required when the name of the variable appears in the right side of an assignment statement. To access the r-value, the l-value must be determined first.

Binding

A binding is an association between an attribute and an entity, such as between a variable and its type or value, or between an operation and a symbol. The time at which a binding takes place is called binding time. Bindings can take place at language design time, language implementation time, compile time, load time, link time, or run time.

count = count + 5;

Binding of attributes to variables

A binding is static if it first occurs before run time begins and remains unchanged throughout program execution. If the binding first occurs during run time or can change in the course of program execution, it is called dynamic.

The physical binding of a variable to a storage cell in a virtual memory environment is complex, because the page or segment of the address space in which the cell resides may be moved in and out of memory many times during program execution. In a sense, such variables are bound and unbound repeatedly. These bindings, however, are maintained by computer hardware, and the changes are invisible to the program and the user.

Type bindings

Before a variable can be referenced in a program, it must be bound to a data type. The two important aspects of this binding are how the type is specified and when the binding takes place. Types can be specified statically through some form of explicit or implicit declaration.

Static Type Binding

An explicit declaration is a statement that lists variable names and specifies that they are particular type. An implicit declaration is a means of associating variables with types through default conventions, rather than declaration statements. In this case, the first appearance of a variable name constitutes its implicit declaration. Both explicit and implicit declarations create static bindings to types.

There are several different bases for implicit variable type bindings. The simplest of these is naming conventions. Another kind of implicit type declarations uses context. This is sometimes called type inference.

Dynamic Type Binding

With dynamic type binding, the type of a varaible is not specified by a declaration statement, nor can it be determined by the splling of its name. Instead, the variable is bound to a type when it is assigned a value in an assignment statement. In reality, the names of variables are never bound to types. Name can be bound to variables and variables can be bound to types.

Storage Bindings and Lifetime

The memory cell to which a variable is bound somehow must be taken from a pool of available memory. This process is called allocation. Deallocation is the process of placing a memory cell that has been unbound from a variable back into the pool of available memory.

The lifetime of a variable is the time during which the variable is bound to a specific memory location. So, the lifetime of a variable begins when it is bound to a specific cell and ends when it is unbound from that cell.

It is convenient ot separate scalar(unstructured) variable into four categories, according to their lifetimes: static, stack-dynamic, explicit heap-dynamic, and implicit heap-dynamic.

Static Variables

Static variables are those that are bound to memory cells before program execution begins and remain bound to those same memory cells until program execution terminates. Globally accessible variables are often used throughout the execution of a program, thus making it necessary to have them bound to the same storage during that execution.

One advantage of static variables is efficiency:

One disadvantage of static binding to storage is reduced flexibility;

Rust, C++, Java allows programmers to include the static specifier on a variable definition in a function, making the variables it defines static.

static N: i32 = 5;
Stack-Dynamic Variables

Stack-dynamic variables are those whose storage bindings are created when their decalration statements are elaborated, but whose types are staticlly bound. Elaboration of such a declaration refers to the storage allocation and binding process indicated by the declaration, which takes place when execution reaches the code to which declaration is attached. Therefore, elaboration occurs during run time.

As the their name indicates, stack-dynamic variables are allocated from the run-time stack.

Some languages, for examples, C++ and Java, allow variable declarations to occur anywhere a statement can appear. In some implementations of these languages, all of the stack-dynamic variables declared in a funciton or method(not inlcuding those declared in nested blocks) may be bound to storage the beginning of ececution of the funciton of method, even though the declarations of some of these variables do not appear at the beginning. In such cases, the variable becomes visible at the declaration, but the storage binding (and initialization, if it is specified in the declaration) occurs when the function or method begins execution. The fact that storage binding of a variable takes place before it becomes visible does not affect the semantics of the langauge.

Advantages:

Disadvantages:

In Java, C++, and C#, variables defined in methods are by default stack dynamic. All attributes other than storage are statically bound to stack-dynamic scalar variables. That is not the case for some structured types.

let x: i32 = 5;
Explicit Heap-Dynamic Variables

Explicit heap-dynamic variables are nameless(abstract) memory cells that are allocated and deallocated by explicit run-time instructions written by the programmer. These variables, which are allocated from and deallocated to the heap, can only be referenced through pointer or reference variables. The heap is collection of storage cells whose organization is highly disorganized because of the unpredicatability of its use. The pointer or reference variable that is used to access an explicit heap-dynamic variable is created as any other scalar variable. An explicit heap-dynamic variable is created by either an operator(for example, in C++) or a call to system subprogram provided for that purpose(for example, in C).

In C++, the allocation operator, named new, uses a type name as its operand. When executed, an explicit heap-dynamic variable of the operand type is created and its address is returned. Because an explicit heap-dynamic variable is bound to a tyep at compile time, that binding is static. However, such variables are bound to storage at the time they are created, which is during run time.

In addition, some languages include a subprogram or operator for explicitly destroying them. C++ has a explicitly deallocation operator delete, Java uses implicit garbage collection.

Explicit heap-dynamic variables are often used to construct dynamic structures, such as linked lists and trees, that need to grow and/or shrink during execution.

The disadvantages of explicit heap-dynamic variables are the difficulty of using pointer and reference variables correctly, the cost of references to the variables, and the complexity of the required storage management implementation. This is essentially the problem of heap management.

let x = Box::new(5);
Implicit Heap-Dynamic Variables

Implicit heap-dynamic variables are bound to heap storage only when they are assigned values. In fact, all their attributes are bound every time they are assigned. For example, consider the following JavaScript assignment statement:

highs = [74, 84, 86, 90, 71];

Regardless of whether the variable named highs was previously used in the program or what it was used for, it is now an array of five numeric values.

The advantage of such variables is that they have the highest degree of flexibility, allowing highly generic code to be written.

One disadvantage of implicit heap-dynamic variables is the run-time overhead of maintaining all the dynamic attributes, which could include array subscript types and ranges, among others. Another disadvantage is the loss of some error detection by the compiler.

Scope

Scoping is necessary if you want to reuse names.

The scope of a variable is the range of statements in which the variable is visible. A variable is visible in a statement if it can be referenced in that statement.

A variable is local in a program unit or block if it is declared there. The nonlocal variables are those that are visible within but are not declared there.

Static Scope

The method of binding names to nonlocal variables is called static scoping. It is so named because the scope of a variable can be statically determined, that is, prior to execution.

In static scopeing, definition of a variable is resolved by searching its containing block or function. If that fails, then searching the outer containing block and so on.

There are two categories of static-scoped languages:

Block

Many languages allow new static scopes to be defined in the midst of executable code. Such variables are typically stack dynamic, so their storage is allocated when the section is entered and deallocated when the section is exited. Such a section of code is called a block. Blocks provide the origin of the phrase block-structured language.

The C-based languages allow any compound statement (a statement sequence surrounded by matched braces) to have declarations and thereby define a new scope.

void sub() [
  int count;
  // ...
  while (...) {
    int count;       
    count ++;
    // ...
  }
  // ...
]

In general, a declaration for a variable effectively hides any declaration of a variable with the same name in a larger enclosing scope. Note that this code is legal in C and C++ but illegal in Java and C# because they believed that the reuse of names in nested blocks was too error prone to be allowed.

Although JavaScript uses static scopeing for its nested functions, non-function blocks cannot be defined in the language.

Most funcitonal programming languages include a construct that is related to the blocks of the imperative langauges, ususally named let. These constructs have two parts, the first of which is to bind names to values, usually specified as expressions. The second part is an expression that uses the names defined in the first part. Programs in functional langauges are comprised of expressions, rather than statements. Therefore, the final part of let construct is an expression, rather than a statement.

(LET (
  (name_1 expression_1)
  ...
  (name_n expression_n))
  expression
)

This differs from a block in an imperative langauge in that the names are of values; they are not variables in the imperative sense. Once set, they cannot be changed. The names in the first part are like the named constants of imperative languages.

let n1 = 
    let n2 = 7
    let n3 = n2 + 3
    n3;;
let n4 = n3 + n1;;

Declaration Order

In some languages(C89), all data declarations in a function except those in nested blocks must apper at the beginning of the funciton. In others(C99, C++, Java, JavaScript, etc.) allow variable declarations to appear anywhere a statement can appear in a program unit.

Declarations may create scopes that are not associsted with compound statements or subprograms. For example, in C99, C++, and Java, the scope of all local variables is from their declarations to the ends of the blocks. However, in C#, the scope of any variable declared in a block is the whole block, regardless of the position of the declaration in the block.

In JavaScript, local variables can be declared anywhere in a funciton, but the scope of such a variable is always the entire function. If used before its declarration in the function, such a variable has the value undefined.

Global Scope

Many languages allow variable definitions appear outside functions. Definitions outside funcitons in a file create global variables.

C and C++ have both declarations and definitions of global data. Declarations specify types and other attributes but do not cause allocation of storage. Definitions specify attributes and cause storage allocation.

A declaration of a variable outside function definitions specifies that the variable is defined in a different file. A global variable in C is implicitly visible in all subsequent functions in the file, except those that include a declaration of a local variable with the same name. A global variable that is defined after a function can be made visible in the funciton by declaring it to be external, as in the following:

extern int sum;

In C99, definitions of global variables usually have initial values. Declarations of global variables never have initial values. If the declaration is outside function definitions, it need not include the extern qualifier.

JavaScript statements can be interspersed with funciton definitions. Variables in JavaScript are implicitly declared when they appear in statements. Any variable that is implicitly delcared outside any funciton is a global variable; variables implicitly declared in function s are local variables. The scope of global variables extends from their declarations so the end of the program but skips over any subsequent function definitions. So global variables are not implicitly visible in any funciton. There is no way to access a global variable in a function that has declared a local variable with the same name.

Dynamic Scope

The scope of variable in APL, SNOBOL4, and the early versions of LISP is dynamic. Dynamic scoping is based on the calling sequence of subprograms, not on their spatial relationship to each other. Thus, the scope can be determined only at run time.

In dynamic scoping, definition of a variable is resolved by searching its containing block and if not found, then searching its calling function and if still not found then the function which called that calling function will be searched and so on.

Scope and Lifetime

Scope is a textual, or spatial, concept whereas lifetime is a temporal concept, but they appear to be related in some cases. For example, consider a variable that is declared in a Java method that contains no method calls. The scope of such a variable is from its declaration to the end of the method. The lifetime of that variable is the period of time beginning when the method is entered and ending when execution of the method terminates.

This apparent relationship between scope and lifetime does not hold in other situations. In C and C++, for example, a variable that is declared in a function using the specifier static is statically bound to the scope of that function and its also statically bound to storage. So, its scope is static and local to the function, but its lifetime extends over the entire execution of the program of which it is a part.

Scope and lifetime are also unrelated when subprogram calls are involved. Consider the following Rust functions:

fn printheader() {
    //...
} // end of printheader

fn compute() {
    let sum: i32;
    //...
    printheader();
}

The scope of the variable sum is completely contained within the compute function. It does not extend to the body of the function printheader, although printheader executes in the midst of the execution of compute. However, the lifetime of sum extends over the time during which printheader executes. Whatever storage location sum is bound to before the call to printheader, that binding will continue during and after the execution of printheader.

Referencing Environments

The referencing environment of a statement is the collection of all variables that are visible in the statement. The referencing environment of a statement in a static-scoped language is the variables declared in its local scope plus the collection of all variables of its ancestor scopes that are visible. In such a language, the referencing environment of a statement is needed while that statement is being compiled, so code and data structures can be created to allow references to variables from other scopes during run time.

Named Constants

A named constant is a variable that is bound to a value only once.

Data Types

Primitive Data Types

Data types that are not defined in terms of other types are called primitive data types.

Numeric Types

Integer

Many computers support several sizes of integers. Most integer types are supported directly by the hardware.

Floating-Point

Most languages include two floating-point types, often called float and double.

The float type is the standard size, usually being stored in four bytes of memory. The double type is provided for situations where larger fractional parts and/or a larger range of exponents is needed. Double-precision variables usually occupy twice as much storage as float variables and provide at least twice the number of bits of fraction.

Complex

Some programming languages(Fortran, Python) support a complex data type. In Python, the imaginary part of a complex literal is specified by following it with a j or J.

(7 + 3j)
Decimal

Most larger computers that are designed to support business systems applications have hardware support for decimal data types. Decimal data types store a fixed number of decimal digits, with the decimal point at a fixed position in the value. These are the primary data types for business data processing and are therefore essential to COBOL. C# and F# also have decimal data types.

Decimal types have the advantage of being able to precisely store decimal values, at least those within a restricted range, which cannot be done with floating-point. For example, the number 0.1 (in decimal) can be exactly represented in a decimal type, but not in a floating-point type, as we saw in Section 6.2.1.2. The disadvantages of decimal types are that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful, for reasons discussed in the following paragraph.

Decimal types are stored very much like character strings, using binary codes for the decimal digits. These representations are called binary coded decimal (BCD). In some cases, they are stored one digit per byte, but in others, they are packed two digits per byte. Either way, they take more storage than binary representations. It takes at least four bits to code a decimal digit. Therefore, to store a six-digit coded decimal number requires 24 bits of memory

However, it takes only 20 bits to store the same number in binary. The operations on decimal values are done in hardware on machines that have such capabilities; otherwise, they are simulated in software.

Boolean Types

Boolean types are perhaps the simplest of all types. Their range of values has only two elements: one for true and one for false.

A Boolean value could be represented by a single bit, but because a single bit of memory cannot be accessed efficiently on many machines, they are often stored in the smallest efficiently addressable cell of memory, typically a byte.

Character Types

Character data are stored in computers as numeric codings. Traditionally, the most commonly used coding was the 8-bit code ASCII (American Standard Code for Information Interchange), which uses the values 0 to 127 to code 128 different characters.

Because of the globalization of business and the need for computers to communicate with other computers around the world, the ASCII character set became inadequate. In response, in 1991, the Unicode Consortium published the UCS-2 standard, a 16-bit character set. This character code is often called Unicode. Unicode includes the characters from most of the world’s natural languages. For example, Unicode includes the Cyrillic alphabet, as used in Serbia, and the Thai digits. The first 128 characters of Unicode are identical to those of ASCII. Java was the first widely used language to use the Unicode character set. Since then, it has found its way into JavaScript, Python, Perl, C#, and F#.

Character String Types

A character string type is one in which the values consist of sequences of characters.

The most common string operations are assignment, catenation, substring reference, comparison, and pattern matching.

A substring reference is a reference to a substring of a given string. Substring references are discussed in the more general context of arrays, where the substring references are called slices.

In general, both assignment and comparison operations on character strings are complicated by the possibility of string operands of different lengths.

Pattern matching is another fundamental character string operation. In some languages, pattern matching is supported directly in the language. In others, it is provided by a function or class library.

If strings are not defined as a primitive type, string data is usually stored in arrays of single characters and referenced as such in the language. This is the approach taken by C and C++.

In Java, strings are supported by the String class, whose values are constant strings, and the StringBuffer class, whose values are changeable and are more like arrays of single characters. These values are specified with methods of the StringBuffer class. C# and Ruby include string classes that are similar to those of Java.

Python includes strings as a primitive type and has operations for substring reference, catenation, indexing to access individual characters, as well as methods for searching and replacement. There is also an operation for character membership in a string. So, even though Python’s strings are primitive types, for character and substring references, they act very much like arrays of characters. However, Python strings are immutable, similar to the String class objects of Java.

In ML, string is a primitive immutable type. It uses ^ for its catenation operator and includes functions for substring referencing and getting the size of a string.

Perl, JavaScript, Ruby, and PHP include built-in pattern-matching operations. In these languages, the pattern-matching expressions are somewhat loosely based on mathematical regular expressions. In fact, they are often called regular expressions.

the length can be static and set when the string is created. Such a string is called a static length string. This is the choice for the strings of Python, the immutable objects of Java’s String class, as well as similar classes in the C++ standard class library, Ruby’s built-in String class, and the .NET class library available to C# and F#

The second option is to allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition, as exemplified by the strings in C and the C-style strings of C++. These are called limited dynamic length strings. Such string variables can store any number of characters between zero and the maximum. Recall that strings in C use a special character to indicate the end of the string’s characters, rather than maintaining the string length.

The third option is to allow strings to have varying length with no maximum, as in JavaScript, Perl, and the standard C++ library. These are called dynamic length strings. This option requires the overhead of dynamic storage allocation and deallocation but provides maximum flexibility.

User-Defined Ordinal Types

An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers. In Java, for example, the primitive ordinal types are integer, char, and boolean. There are two user-defined ordinal types that have been supported by programming languages: enumeration and subrange.

Enumeration Types

An enumeration type is one in which all of the possible values, which are named constants, are provided, or enumerated, in the definition. Enumeration types provide a way of defining and grouping collections of named constants, which are called enumeration constants. The definition of a typical enumeration type is shown in the following C# example:

enum days {Mon, Tue, Wed, Thu, Fri, Sat, Sun}

The enumeration constants are typically implicitly assigned the integer values, 0, 1, . . . but can be explicitly assigned any integer literal in the type’s definition. In C/C++, they are coerced to integer.

All enumeration types in Java are implicitly subclasses of the predefined class Enum, so they can have instance data fields, constructores, and methods.

In Haskell, enumeration types are defined as new types with data declarations:

data weekdays = Monday | Tuesday | Wednesday | Thursday | Friday

Interestingly, none of the relatively recent scripting kinds of langauges include enumeration types, including Perl, JavaScript, PHP, Python, Ruby, Lua, and Nix.

Subrange Types

A subrange type is a contiguous subsequence of an ordinal type. For example, 12..14 is a subrange of integer type.

Array Types

An array is a homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element. The individual data elements of an array are of the same type. References to individual array elements are specified using subscript expressions.

In many languages, such as C, C++, Java, Ada, and C#, all of the elements of an array are required to be of the same type. In these languages, pointers and references are restricted to point to or reference a single type. So the objects or data values being pointed to or referenced are also of a single type. In some other languages, such as JavaScript, Python, and Ruby, variables are typeless references to objects or data values. In these cases, arrays still consist of elements of a single type, but the elements can reference objects or data values of different types. Such arrays are still homogeneous, because the array elements are of the same type.

Specific elements of an array are referenced by means of a two-level syntactic mechanism, where the first part is the aggregate name, and the second part is a possibly dynamic selector consisting of one or more items known as subscripts or indices. If all of the subscripts in a reference are constants, the selector is static; otherwise, it is dynamic. The selection operation can be thought of as a mapping from the array name and the set of subscript values to an element in the aggregate. Indeed, arrays are sometimes called finite mappings.

Array Categories

The binding of the subscript type to an array variable is usually static, but the subscript value ranges are sometimes dynamically bound.

There are five categories of arrays, based on the binding to subscript ranges, the binding to storage, and from where the storage is allocated. The category names indicate the design choices of these three. In the first four of these categories, once the subscript ranges are bound and the storage is allocated, they remain fixed for the lifetime of the variable.

static array

the subscript ranges are statically bound and storage allocation is static (done before run time). The advantage of static arrays is efficiency: No dynamic allocation or deallocation is required. The disadvantage is that the storage for the array is fixed for the entire execution time of the program.

fixed stack-dynamic array

the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution. The advantage of fixed stack-dynamic arrays over static arrays is space efficiency.

stack-dynamic array

both the subscript ranges and the storage allocation are dynamically bound at elaboration time. Once the subscript ranges are bound and the storage is allocated, however, they remain fixed during the lifetime of the variable. The advantage of stack-dynamic arrays over static and fixed stack-dynamic arrays is flexibility.

fixed heap-dynamic array

similar to a fixed stack-dynamic array, in that the subscript ranges and the storage binding are both fixed after storage is allocated. The differences are that both the subscript ranges and storage bindings are done when the user program requests them during execution, and the storage is allocated from the heap, rather than the stack. The advantage of fixed heap-dynamic arrays is flexibility—the array’s size always fits the problem. The disadvantage is allocation time from the heap, which is longer than allocation time from the stack.

heap-dynamic array

h the binding of subscript ranges and storage allocation is dynamic and can change any number of times during the array’s lifetime. The advantage of heap-dynamic arrays over the others is flexibility: Arrays can grow and shrink during program execution as the need for space changes. The disadvantage is that allocation and deallocation take longer and may happen many times during execution of the program.

Rectangular and Jagged Arrays

A rectangular array is a multidimensioned array in which all of the rows have the same number of elements and all of the columns have the same number of elements. Rectangular arrays model rectangular tables exactly.

A jagged array is one in which the lengths of the rows need not be the same.

C, C++, and Java support jagged arrays but not rectangular arrays.

Slice

A slice of an array is some substructure of that array. n. It is important to realize that a slice is not a new data type. Rather, it is a mechanism for referencing part of an array as a unit.

Associative Arrays

An associative array is an unordered collection of data elements that are indexed by an equal number of values called keys. In the case of non-associative arrays, the indices never need to be stored (because of their regularity). In an associative array, however, the user-defined keys must be stored in the structure.

Record Types

A record is an aggregate of data elements in which the individual elements are identified by names and accessed through offsets from the beginning of the structure.

In C, C++, and C#, records are supported with the struct data type. C# structs are stack-allocated value types, as opposed to class objects, which are heap-allocated reference types.

The fundamental difference between a record and an array is that record elements, or fields, are not referenced by indices. Instead, the fields are named with identifiers, and references to the fields are made using these identifiers.

Most of the other languages use dot notation for field references, where the components of the reference are connected with periods.

Tuple Types

A tuple is a data type that is similar to a record, except that the elements are not named. Tuples are used in Python, ML, and F# to allow functions to return multiple values.

List Types

Python includes a list data type, which also serves as Python’s arrays. Unlike the lists of Scheme, Common LISP, ML, and F#, the lists of Python are mutable. They can contain any data value or object. A Python list is created with an assignment of a list value to a name.

Python includes a powerful mechanism for creating arrays called list comprehensions. A list comprehension is an idea derived from set notation. It first appeared in the functional programming language Haskell.

Union Types

A union is a type whose variables may store different type values at different times during program execution.

C and C++ provide union constructs in which there is no language support for type checking. In C and C++, the union construct is used to specify union structures. The unions in these languages are called free unions, because programmers are allowed complete freedom from type checking in their use.

Type checking of unions requires that each union construct include a type indicator. Such an indicator is called a tag, or discriminant, and a union with a discriminant is called a discriminated union or tagged union.

Unions are potentially unsafe constructs in some languages. They are one of the reasons why C and C++ are not strongly typed: These languages do not allow type checking of references to their unions. On the other hand, unions can be safely used, as in their design in Ada, ML, Haskell, and F#.

Pointer and Reference Types

A pointer type is one in which the variables have a range of values that consists of memory addresses and a special value, nil. The value nil is not a valid address and is used to indicate that a pointer cannot currently be used to reference a memory cell.

Pointer are designed for two distinct kinds of uses. First, pointers provide some of the power of indirect addressing, which is frequently used in assembly language programming. Second, pointers provide a way to manage dynamic storage. A pointer can be used to access a location in an area where storage is dynamically allocated called a heap.

Variables that are dynamically allocated from the heap are called heap-dynamic variables. They often do not have identifiers associated with them and thus can be referenced only by pointer or reference type variables. Variables without names are called anonymous variables. It is in this latter application area of pointers that the most important design issues arise.

Pointers, unlike arrays and records, are not structured types, although they are defined using a type operator. Furthermore, they are also different from scalar variables because they are used to reference some other variable, rather than being used to store data. These two categories of variables are called reference types and value types, respectively.

Languages that provide a pointer type usually include two fundamental pointer operations: assignment and dereferencing. The first operation sets a pointer variable’s value to some useful address. If pointer variables are used only to manage dynamic storage, then the allocation mechanism, whether by operator or built-in subprogram, serves to initialize the pointer variable. If pointers are used for indirect addressing to variables that are not heap dynamic, then there must be an explicit operator or built-in subprogram for fetching the address of a variable, which can then be assigned to the pointer variable.

Dereferencing of pointers can be either explicit or implicit. In C++, it is explicitly specified with the asterisk (*) as a prefix unary operator.

Languages that provide pointers for the management of a heap must include an explicit allocation operation. Allocation is sometimes specified with a subprogram, such as malloc in C. In languages that support object-oriented programming, allocation of heap objects is often specified with the new operator. C++, which does not provide implicit deallocation, uses delete as its deallocation operator.

Pointer Problems

Pointers were highly flexible, but their use could lead to several kinds of programming errors. Some recent languages, such as Java, have replaced pointers completely with reference types, which, along with implicit deallocation, minimize the primary problems with pointers. A reference type is really only a pointer with restricted operations

Dangling Pointers

A dangling pointer, or dangling reference, is a pointer that contains the address of a heap-dynamic variable that has been deallocated.

Previous solutions to this are tombstones(Lomet, 1975), and locks-and-keys approach(Fischer and LeBlanc, 1977). Of course, the best solution to the dangling-pointer problem is to take deallocation of heap-dynamic variables out of the hands of programmers. If programs cannot explicitly deallocate heap-dynamic variables, there will be no dangling pointers. To do this, the run-time system must implicitly deallocate heap-dynamic variables when they are no longer useful. LISP systems have always done this. Both Java and C# also use this approach for their reference variables. Recall that C#’s pointers do not include implicit deallocation.

Lost Heap-Dynamic Variables

A lost heap-dynamic variable is an allocated heap-dynamic variable that is no longer accessible to the user program. Such variables are often called garbage, because they are not useful for their original purpose, and they also cannot be reallocated for some new use in the program.

This is sometimes called memory leakage.

There are several different approaches to garbage collection. The two most common traditional techniques are in some ways opposite processes. These are named reference counters, in which reclamation is incremental and is done when inaccessible cells are created, and mark-sweep, in which reclamation occurs only when the list of available space becomes empty. These two methods are sometimes called the eager approach and the lazy approach, respectively.

Reference Types

A reference type variable is similar to a pointer, with one important and fundamental difference: A pointer refers to an address in memory, while a reference refers to an object or a value in memory. As a result, although it is natural to perform arithmetic on addresses, it is not sensible to do arithmetic on references.

All variables in the object-oriented languages Smalltalk, Python, Ruby, and Lua are references. They are always implicitly dereferenced. Furthermore, the direct values of these variables cannot be accessed.

Type Checking

Type checking is the activity of ensuring that the operands of an operator are of compatible types. A compatible type is one that either is legal for the operator or is allowed under language rules to be implicitly converted by compiler-generated code (or the interpreter) to a legal type. This automatic conversion is called a coercion. For example, if an int variable and a float. Variable are added in Java, the value of the int variable is coerced to floatand a floating-point add is done.

A type error is the application of an operator to an operand of an inappropriate type.

If all bindings of variables to types are static in a language, then type checking can nearly always be done statically. Dynamic type binding requires type checking at run time, which is called dynamic type checking.

Type checking is complicated when a language allows a memory cell to store values of different types at different times during execution. Such memory cells can be created with Ada variant records, C and C++ unions, and the discriminated unions of ML, Haskell, and F#. In these cases, type checking, if done, must be dynamic and requires the run-time system to maintain the type of the current value of such memory cells. So, even though all variables are statically bound to types in languages such as C++, not all type errors can be detected by static type checking.

Strong Typing

One of the ideas in language design that became prominent in the so-called structured-programming revolution of the 1970s was strong typing. A programming language is strongly typed if type errors are always detected. This requires that the types of all operands can be determined, either at compile time or at run time.

C and C++ are not strongly typed languages because both include union types, which are not type checked.

ML is strongly typed, even though the types of some function parameters may not be known at compile time. F# is strongly typed.

Java and C#, although they are based on C++, are strongly typed. Types can be explicitly cast, which could result in a type error. However, there are no implicit ways type errors can go undetected.

Languages with a great deal of coercion, like C, and C++, are less reliable than those with little coercion, such as Ada, and those with no coercion, such as ML and F#.

Type Equivalence

The type compatibility rules dictate the types of operands that are acceptable for each of the operators and thereby specify the possible type errors of the language. The rules are called compatibility because in some cases the type of an operand can be implicitly converted by the compiler or run-time system to make it acceptable to the operator.

The type compatibility rules are simple and rigid for the predefined scalar types. However, coercion of structured types is rare, so the issue is not type compatibility, but type equivalence. That is, two types are equivalent if an operand of one type in an expression is substituted for one of the other type, without coercion. Type equivalence is a strict form of type compatibility—compatibility without coercion. The central issue here is how type equivalence is defined.

There are two approaches to defining type equivalence: name type equivalence and structure type equivalence. Name type equivalence means that two variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name. Structure type equivalence means that two variables have equivalent types if their types have identical structures. There are some variations of these two approaches, and many languages use combinations of them.

Another difficulty with structure type equivalence is that it disallows differentiating between types with the same structure:

type Celsius = f64;
type Fahrenheit = f64;

The types of variables of these two types are considered equivalent under structure type equivalence, allowing them to be mixed in expressions, which is surely undesirable in this case, considering the difference indicated by the type’s names. In general, types with different names are likely to be abstractions of different categories of problem values and should not be considered equivalent.

Ada uses a restrictive form of name type equivalence but provides two type constructs, subtypes and derived types, that avoid the problems associated with name type equivalence. A derived type is a new type that is based on some previously defined type with which it is not equivalent, although it may have identical structure. Derived types inherit all the properties of their parent types.

struct Celsius(f64);
struct Fahrenheit(f64);

An Ada subtype is a possibly range-constrained version of an existing type. A subtype is type equivalent with its parent type.

subtype Small_type is Integer range 0..99;

C uses both name and structure type equivalence. Every struct, enum, and union declaration creates a new type that is not equivalent to any other type. So, name type equivalence is used for structure, enumeration, and union types. Other nonscalar types use structure type equivalence. Array types are equivalent if they have the same type components. Also, if an array type has a constant size, it is equivalent either to other arrays with the same constant size or to with those without a constant size. Note that typedef in C and C++ does not introduce a new type; it simply defines a new name for an existing type. So, any type defined with typedef is type equivalent to its parent type. One exception to C using name type equivalence for structures, enumerations, and unions is if two structures, enumerations, or unions are defined in different files, in which case structural type equivalence is used. This is a loophole in the name type equivalence rule to allow equivalence of structures, enumerations, and unions that are defined in different files.

Object-oriented languages such as Java and C++ bring another kind of type compatibility issue with them. The issue is object compatibility and its relationship to the inheritance hierarchy.

Subprograms

The first programmable computer, Babbage’s Analytical Engine, built in the 1840s, had the capability of reusing collections of instruction cards at several different places in a program. In a modern programming language, such a collection of statements is written as a subprogram. This reuse results in several different kinds of savings, primarily memory space and coding time. Such reuse is also an abstraction, for the details of the subprogram’s computation are replaced in a program by a statement that calls the subprogram

Basic Definitions

All subprograms except coroutines have the following characteristics:

A subprogram definition describes the interface to and the actions of the subprogram abstraction. A subprogram call is the explicit request that a specific subprogram be executed. A subprogram is active if it has begun execution but has not yet completed.

A subprogram header as the first part of the definition serves several purposes:

The header of a JavaScript subprogram begins with function.

The body of subprograms defines its actions. In the C-based languages (and some others—for example, JavaScript) the body of a subprogram is delimited by braces.

The parameter profile of a subprogram contains the number, order, and types of its formal parameters. The protocol of a subprogram is its parameter profile plus, if it is a function, its return type. In languages in which subprograms have types, those types are defined by the subprogram’s protocol.

Subprograms can have declarations as well as definitions. This form parallels the variable declarations and definitions in C, in which the declarations can be used to provide type information but not to define variables. Subprogram declarations provide the subprogram’s protocol but do not include their bodies. They are necessary in languages that do not allow forward references to subprograms. In both the cases of variables and subprograms, declarations are needed for static type checking. In the case of subprograms, it is the type of the parameters that must be checked. Function declarations are common in C and C++ programs, where they are called prototypes. Such declarations are often placed in header files.

In most other languages (other than C and C++), subprograms do not need declarations, because there is no requirement that subprograms be defined before they are called.

Parameters

There are two ways that a non-method subprogram can gain access to the data that it is to process:

Although methods also access external data through nonlocal references and parameters, the primary data to be processed by a method is the object through which the method is called.

Pure functional programming languages like Haskell do not have mutable data, so functions written in them are unable to change memory in any way. They simply perform calculations and return a resulting value.

In some situations, it is convenient to be able to transmit computations, rather than data, as parameters to subprograms. In these cases, the name of the subprogram that implements that computation may be used as a parameter.

The parameters in the subprogram header are called formal parameters(or just parameters). They are sometimes thought of as dummy variables because they are not variables in the usual sense: In most cases, they are bound to storage only when the subprogram is called, and that binding is often through some other program variables.

Subprogram call statements must include the name of the subprogram and a list of parameters to be bound to the formal parameters of the subprogram. These parameters are called actual parameters(or arguments).

In nearly all programming languages, the correspondence between actual and formal parameters—or the binding of actual parameters to formal parameters—is done by position: The first actual parameter is bound to the first formal parameter and so forth. Such parameters are called positional parameters. When lists are long, however, it is easy for a programmer to make mistakes in the order of actual parameters in the list. One solution to this problem is to provide keyword parameters, in which the name of the formal parameter to which an actual parameter is to be bound is specified with the actual parameter in a call(Python).

Procedures and functions

There are two distinct categories of subprograms, procedures and functions, both of which can be viewed as approaches to extending the langauges. All subprograms are collections of statements that define parameterized computations. Functions return values and procedures do not. In most languages that do not include procedures as a separate form of subprogram, functions can be defined not to return values and they can be used as procedures. For example, if a particular language does not have a sort statement, a user can build a procedure to sort arrays of data and use a call to that procedure in place of the unavailable sort statement.

Functions define new user-defined operators.

An overloaded subprogram is one tha thas the same name as another subprogram in the same referencing environment. A generic subprogram is one whose computation can be done on data of different types inn different calls. A closure is a nested subprogram and its referencing environment, which together allow the subprogram to be called from anywhere in a program.

Local Referencing Environments

Variables that are defined inside subprograms are called local variables, because their scope is usually the body of the subprogram in which they are defined.

The idea of nesting subprograms is to be able to create a hierarchy of both logic and scopes. If a subprogram is needed only whithin another subprogram, why not place it here and hide it froom the rest of the program? Many languages including all of the direct descendants of C do not allow subprogram nesting. Recently some new languages including JavaScript, Python, Ruby, Lua allow it. Also, most functional programming languages allow it.

Parameter-Passing Methods

Parameter-passing methods are the ways in which parameters are transmitted to and/or from called subprograms.

Formal parameters are characterized by one of three distinct semantics models:

There are two conceptual models of how data transfers take place in parameter transmission: Either an actual value is copied (to the caller, to the called, or both ways), or an access path is transmitted. Most commonly, the access path is a simple pointer or reference.

Pass-by-Value

When a parameter is passed by value, the value of the actual parameter is used to initialize the corresponding formal parameter, which then acts as a local variable in the subprogram, thus implementing in-mode semantics.

Pass-by-value is normally implemented by copy, because accesses often are more efficient with this approach. It cloud be implemented by transmitting an access path to the value be in a write-protected cell. But enforcing the write protection is not always a simple matter.

The advantage of pass-by-value is that for scalars it is fast, in both linkage cost and access time. The disadvantage of the method if copies are used is that additional storage is required for the formal parameter. The storage and the copy operations can be costly if the parameter is large, such as an array with many elements.

When a parameter is passed by value, the caller and callee have two independent variables with the same value. If the callee modifies the parameter variable, the effect is not visible to the caller. i.e, call by value means that you pass values as function arguments, it’s where I write down something on a piece of paper and hand it to you, and so now it is effectively your piece of paper.

Pass-by-Result

Pass-by-result is an implementation model for out-mode parameters. When a parameter is passed by result, no value is transmitted to the subprogram. The corresponding formal parameter acts as a local variable, but just before control is transferred back to the caller, its value is transmitted back to the caller’s actual parameter, which obviously must be a variable. (How would the caller reference the computed result if it were a literal or an expression?)

If values are returned by copy (as opposed to access paths), as they typically are, pass-by-result also requires the extra storage and the copy operations that are required by pass-by-value. As with pass-by-value, the difficulty of implementing pass-by-result by transmitting an access path usually results in it being implemented by copy. In this case, the problem is in ensuring that the initial value of the actual parameter is not used in the called subprogram.

One additional problem with the pass-by-result model is that there can be an actual parameter collision.

Another problem that can occur with pass-by-result is that the implementor may be able to choose between two different times to evaluate the addresses of the actual parameters: at the time of the call or at the time of the return.

Pass-by-Value-Result

Pass-by-value-result is an implementation model for inout-mode parameters in which actual values are copied. It is in effect a combination of pass-by-value and pass-by-result. The value of the actual parameter is used to initialize the corresponding formal parameter, which then acts as a local variable. In fact, pass-by-value-result formal parameters must have local storage associated with the called subprogram. At subprogram termination, the value of the formal parameter is transmitted back to the actual parameter.

Pass-by-value-result is sometimes called pass-by-copy, because the actual parameter is copied to the formal parameter at subprogram entry and then copied back at subprogram termination.

Pass-by-value-result shares with pass-by-value and pass-by-result the disadvantages of requiring multiple storage for parameters and time for copying values. It shares with pass-by-result the problems associated with the order in which actual parameters are assigned.

Pass-by-Reference

Pass-by-reference is a second implementation model for inout-mode parameters. Rather than copying data values back and forth, however, as in pass-byvalue-result, the pass-by-reference method transmits an access path, usually just an address, to the called subprogram. This provides the access path to the cell storing the actual parameter. Thus, the called subprogram is allowed to access the actual parameter in the calling program unit. In effect, the actual parameter is shared with the called subprogram.The advantage of pass-by-reference is that the passing process itself is efficient, in terms of both time and space. Duplicate space is not required, nor is any copying required.

There are, however, several disadvantages to the pass-by-reference method. First, access to the formal parameters will be slower than pass-by-value parameters, because of the additional level of indirect addressing that is required. Second, if only one-way communication to the called subprogram is required, inadvertent and erroneous changes may be made to the actual parameter.

Another problem of pass-by-reference is that aliases can be created. The problem with these kinds of aliasing is the same as in other circumstances: It is harmful to readability and thus to reliability. It also makes program verification more difficult.

The “passing by reference” method has an important limitation. If a parameter is declared as passed by reference (so it is preceded by the & sign) its corresponding actual parameter must be a variable.

When a parameter is passed by reference, the caller and the callee use the same variable for the parameter. If the callee modifies the parameter variable, the effect is visible to the caller’s variable. i.e., call by reference means that you pass variables as function arguments, it’s when I give you my notebook which has something written down in it.

“Variable” here means the caller’s (local or global) variable itself – i.e. if I pass a local variable by reference and assign to it, I’ll change the caller’s variable itself, not e.g. whatever it is pointing to if it’s a pointer.

This is now considered bad practice (as an implicit dependency). As such, virtually all newer languages are exclusively, or almost exclusively pass-by-value. Pass-by-reference is now chiefly used in the form of “output/input arguments” in languages where a function cannot return more than one value.

The meaning of “reference” in “pass by reference”. The difference with the general “reference” term is that this “reference” is temporary and implicit. What the callee gets is a “variable” that is somehow “the same” as the original one. How specifically this effect is achieved is irrelevant (e.g. the language may also expose some implementation details – addresses, pointers, dereferencing – this is all irrelevant; if the net effect is this, it’s pass-by-reference).

Pass-by-Name

Pass-by-name is an inout-mode parameter transmission method that does not correspond to a single implementation model. When parameters are passed by name, the actual parameter is, in effect, textually substituted for the corresponding formal parameter in all its occurrences in the subprogram. This method is quite different from those discussed thus far; in which case, formal parameters are bound to actual values or addresses at the time of the subprogram call. A pass-by-name formal parameter is bound to an access method at the time of the subprogram call, but the actual binding to a value or an address is delayed until the formal parameter is assigned or referenced. Implementing a pass-by-name parameter requires a subprogram to be passed to the called subprogram to evaluate the address or value of the formal parameter. The referencing environment of the passed subprogram must also be passed. This subprogram/referencing environment is a closure. Pass-by-name parameters are both complex to implement and inefficient. They also add significant complexity to the program, thereby lowering its readability and reliability.

Because pass-by-name is not part of any widely used language, it is not discussed further here. However, it is used at compile time by the macros in assembly languages and for the generic parameters of the generic subprograms in C++, Java 5.0, and C# 2005.

Confusions

source: https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value

First and foremost, the “pass-by-value vs. pass-by-reference” distinction as defined in the CS theory is now obsolete because the technique originally defined as “pass-by-reference” has since fallen out of favor and is seldom used now.

Newer languages tend to use a different (but similar) pair of techniques to achieve the same effects(see below) which is the primary source of confusion.

A secondary source of confusion if the fact that in “pass-by-reference”, “reference” has a narrower meaning than the general term “reference”(because the phrase predates it).

Now, in modern languages, variables tend to be of “reference types” (another concept invented later than “pass by reference” and inspired by it), i.e. the actual object data is stored separately somewhere (usually, on the heap), and only “references” to it are ever held in variables and passed as parameters.

Passing such a reference falls under pass-by-value because a variable’s value is technically the reference itself, not the referred object. However, the net effect on the program can be the same as either pass-by-value or pass-by-reference:

As you may see, this pair of techniques is almost the same as those in the definition, only with a level of indirection: just replace “variable” with “referenced object”.

There’s no agreed-upon name for them, which leads to contorted explanations like “call by value where the value is a reference”. In 1975, Barbara Liskov suggested the term “call-by-object-sharing” (or sometimes just “call-by-sharing”) though it never quite caught on. Moreover, neither of these phrases draws a parallel with the original pair. No wonder the old terms ended up being reused in the absence of anything better, leading to confusion.

(I would use the terms “new” or “indirect” pass-by-value/pass-by-reference for the new techniques.)

Implementing Parameter-Passing Methods

In most contemporary languages, parameter communication takes place through the run-time stack. The run-time stack is initialized and maintained by the run-time system, which manages the execution of programs. The runtime stack is used extensively for subprogram control linkage and parameter passing.

Pass-by-value parameters have their values copied into stack locations. The stack locations then serve as storage for the corresponding formal parameters. Pass-by-result parameters are implemented as the opposite of pass-byvalue. The values assigned to the pass-by-result actual parameters are placed in the stack, where they can be retrieved by the calling program unit upon termination of the called subprogram. Pass-by-value-result parameters can be implemented directly from their semantics as a combination of pass-by-value and pass-by-result. The stack location for such a parameter is initialized by the call and is then used like a local variable in the called subprogram.

Pass-by-reference parameters are perhaps the simplest to implement. Regardless of the type of the actual parameter, only its address must be placed in the stack. In the case of literals, the address of the literal is put in the stack. In the case of an expression, the compiler must build code to evaluate the expresion just before the transfer of control to the called subprogram. The address of the memory cell in which the code places the result of its evaluation is then put in the stack. The compiler must be sure to prevent the called subprogram from changing parameters that are literals or expressions.

Parameter-Passing Methods of Some Common Languages

C uses pass-by-value. Pass-by-reference (inout mode) semantics is achieved by using pointers as parameters. The value of the pointer is made available to the called function and nothing is copied back. However, because what was passed is an access path to the data of the caller, the called function can change the caller’s data. In both C and C++, formal parameters can be typed as pointers to constants. The corresponding actual parameters need not be constants, for in such cases they are coerced to constants. This allows pointer parameters to provide the efficiency of pass-by-reference with the one-way semantics of pass-by-value. Write protection of those parameters in the called function is implicitly specified.

C++ includes a special pointer type, called reference type, which is often used for parameters. Reference parameters are implicitly dereferenced in the function or method, and their semantics is pass-by-reference. C++ also allows reference parameters to be defined to be constants. For example, we could have

void fun(const int &p1, int p2, int &p3) { //... }

where p1 is pass-by-reference but cannot be changed in the function, p2 is pass-by-value, and p3 is pass-by-reference. Neither p1 nor p3 need be explicitly dereferenced in fun.

Constant parameters and in-mode parameters are not exactly alike. Constant parameters clearly implement in mode. However, in all of the common imperative languages except Ada, in-mode parameters can be assigned in the subprogram even though those changes are never reflected in the values of the corresponding actual parameters. Constant parameters can never be assigned.

As with C and C++, all Java parameters are passed by value. However, because objects can be accessed only through reference variables, object parameters are in effect passed by reference. Although an object reference passed as a parameter cannot itself be changed in the called subprogram, the referenced object can be changed if a method is available to cause the change. Because reference variables cannot point to scalar variables directly and Java does not have pointers, scalars cannot be passed by reference in Java (although a reference to an object that contains a scalar can).

The default parameter-passing method of C# is pass-byvalue. Pass-by-reference can be specified by preceding both a formal parameter and its corresponding actual parameter with ref. C# also supports out-mode parameters, which are pass-by-reference parameters that do not need initial values. Such parameters are specified in the formal parameter list with the out modifier

The parameter-passing method of Python and Ruby is called pass-by-assignment. Because all data values are objects, every variable is a reference to an object. In pass-by-assignment, the actual parameter value is assigned to the formal parameter. Therefore, pass-by-assignment is in effect pass-by-reference, because the value of all actual parameters are references. However, only in certain cases does this result in pass-by-reference parameter-passing semantics. For example, many objects are essentially immutable. In a pure object-oriented language, the process of changing the value of a variable with an assignment statement, as in

x = x + 1

oes not change the object referenced by x. Rather, it takes the object referenced by x, increments it by 1, thereby creating a new object (with the value x + 1), and then changes x to reference the new object. So, when a reference to a scalar object is passed to a subprogram, the object being referenced cannot be changed in place. Because the reference is passed by value, even though the formal parameter is changed in the subprogram, that change has no effect on the actual parameter in the caller.

Conclusion

Two important considerations are involved in choosing parameter-passing methods: efficiency and whether one-way or two-way data transfer is needed.

Contemporary software-engineering principles dictate that access by subprogram code to data outside the subprogram should be minimized. With this goal in mind, in-mode parameters should be used whenever no data are to be returned through parameters to the caller. Out-mode parameters should be used when no data are transferred to the called subprogram but the subprogram must transmit data back to the caller. Finally, inout-mode parameters should be used only when data must move in both directions between the caller and the called subprogram.

There is a practical consideration that is in conflict with this principle. Sometimes it is justifiable to pass access paths for one-way parameter transmission. For example, when a large array is to be passed to a subprogram that does not modify it, a one-way method may be preferred. However, pass-by-value would require that the entire array be moved to a local storage area of the subprogram. This would be costly in both time and space. Because of this, large arrays are often passed by reference.

The choice of a parameter-passing method for functions is related to another design issue: functional side effects.

Examples

Parameters That Are Subprograms

Although the idea is natural and seemingly simple, the details of how it works can be confusing. If only the transmission of the subprogram code was necessary, it could be done by passing a single pointer. However, two complications arise

First, there is the matter of type checking the parameters of the activations of the subprogram that was passed as a parameter. In C and C++, functions cannot be passed as parameters, but pointers to functions can. The type of a pointer to a function includes the function’s protocol. Because the protocol includes all parameter types, such parameters can be completely type checked.

The second complication with parameters that are subprograms appears only with languages that allow nested subprograms. The issue is what referencing environment for executing the passed subprogram should be used. There are three choices:

Examples

Conclusion

Calling Subprograms Indirectly

There are situations in which subprograms must be called indirectly. These most often occur when the specific subprogram to be called is not known until run time. The call to the subprogram is made through a pointer or reference to the subprogram, which has been set during execution before the call is made. The two most common applications of indirect subprogram calls are for event handling in graphical user interfaces, which are now part of nearly all Web applications, as well as many non-Web applications, and for callbacks, in which a subprogram is called and instructed to notify the caller when the called subprogram has completed its work.

Examples

Conclusion

Overloaded Subprograms

An overloaded operator is one that has multiple meanings. The meaning of a particular instance of an overloaded operator is determined by the types of its operands. For example, if the * operator has two floating-point operands in a Java program, it specifies floating-point multiplication. But if the same operator has two integer operands, it specifies integer multiplication.

An overloaded subprogram is a subprogram that has the same name as another subprogram in the same referencing environment. Every version of an overloaded subprogram must have a unique protocol; that is, it must be different from the others in the number, order, or types of its parameters, and possibly in its return type if it is a function. The meaning of a call to an overloaded subprogram is determined by the actual parameter list (and/or possibly the type of the returned value, in the case of a function). Although it is not necessary, overloaded subprograms usually implement the same process.

Examples

Conclusion

Generic Subprograms

A polymorphic subprogram takes parameters of different types on different activations. Overloaded subprograms provide a particular kind of polymorphism called ad hoc polymorphism. Overloaded subprograms need not behave similarly.

Languages that support object-oriented programming usually support subtype polymorphism. Subtype polymorphism means that a variable of type T can access any object of type T or any type derived from T.

A more general kind of polymorphism is provided by the methods of Python and Ruby. Recall that variables in these languages do not have types, so formal parameters do not have types. Therefore, a method will work for any type of actual parameter, as long as the operators used on the formal parameters in the method are defined.

Parametric polymorphism is provided by a subprogram that takes generic parameters that are used in type expressions that describe the types of the parameters of the subprogram. Different instantiations of such subprograms can be given different generic parameters, producing subprograms that take different types of parameters. Parametric definitions of subprograms all behave the same. Parametrically polymorphic subprograms are often called generic subprograms. Ada, C++, Java 5.0+, C# 2005+, and F# provide a kind of compile-time parametric polymorphism.

Examples

Conclusion

User-Defined Overloaded Operators

Operators can be overloaded by the user in Ada, C++, Python, and Ruby.

Closures

efining a closure is a simple matter; a closure is a subprogram and the referencing environment where it was defined. The referencing environment is needed if the subprogram can be called from any arbitrary place in the program. Explaining a closure is not so simple.

If a static-scoped programming language does not allow nested subprograms, closures are not useful, so such languages do not support them. All of the variables in the referencing environment of a subprogram in such a language (its local variables and the global variables) are accessible, regardless of the place in the program where the subprogram is called.

For the subprogram to be callable from anywhere in the program, its referencing environment must be available wherever it might be called. Therefore, the variables defined in nesting subprograms may need lifetimes that are of the entire program, rather than just the time during which the subprogram in which they were defined is active. A variable whose lifetime is that of the whole program is said to have unlimited extent. This usually means they mustbe heap-dynamic, rather than stack-dynamic.

Nearly all functional programming languages, most scripting languages, and at least one primarily imperative language, C#, support closures. These languages are static-scoped, allow nested subprograms,12 and allow subprograms to be passed as parameters.

Coroutines

A coroutine is a special kind of subprogram. Rather than the master-slave relationship between a caller and a called subprogram that exists with conventional subprograms, caller and called coroutines are more equitable. In fact, the coroutine control mechanism is often called the symmetric unit control model.

Coroutines can have multiple entry points, which are controlled by the coroutines themselves. They also have the means to maintain their status between activations. This means that coroutines must be history sensitive and thus have static local variables. Secondary executions of a coroutine often begin at points other than its beginning. Because of this, the invocation of a coroutine is called a resume rather than a call.

One of the usual characteristics of subprograms is maintained in coroutines: Only one coroutine is actually in execution at a given time. Rather than executing to its end, a coroutine often partially executes and then transfers control to some other coroutine, and when restarted, a coroutine resumes execution just after the statement it used to transfer control elsewhere. This sort of interleaved execution sequence is related to the way multiprogramming operating systems work. Although there may be only one processor, all of the executing programs in such a system appear to run concurrently while sharing the processor. In the case of coroutines, this is sometimes called quasi-concurrency.

Typically, coroutines are created in an application by a program unit called the master unit, which is not a coroutine. When created, coroutines execute their initialization code and then return control to that master unit. When the entire family of coroutines is constructed, the master program resumes one of the coroutines, and the members of the family of coroutines then resume each other in some order until their work is completed, if in fact it can be completed. If the execution of a coroutine reaches the end of its code section, control is transferred to the master unit that created it. This is the mechanism for ending execution of the collection of coroutines, when that is desirable. In some programs, the coroutines run whenever the computer is running.

ML Expressions and Variable Bindings

An ML program is a sequence of bindings. Each binding gets type-checked and then evaluated. What type a binding has depends on a static environment, how a binding is evaluated depends on a dynamic environment.

TypeContainsBuild TimeSynonym
Static EnvironmentTypes of preceding bindingsEarlier passContext
Dynamic EnvironmentValues of the preceding bindingsLater passEnvironment

Syntax

Syntax means how to write it.

val x = e;

Here, e can be any expression. The semicolon is opitonal in a file but necessary in the REPL.

Bindings are immutable, there is no assignment statement in ML. But a binding can be shadowed. For example:

val x = 17;
val x = 19;

The later val x = 19; creates a different environment that shadows the earlier one.

Semantics

Semantics means how it type-checks and evaluates.

To type-check a variable binding, we use the “current static environment” to type-check e and produce a “new static environment”

Evaluation is analogous: To evaluate a variable binding, we use the “current dynamic environment” to evaluate e and produce a “new dynamic environment” that is the current environment except with x having the value v where v is the result of evaluating e.

Value

A value is an expression that, “has no more computation to do”. 17 is a value, but 8+9 is not. All values are expressions. Not all expressions are values.

statically-typed functional paradigm

dynamically-typed functional paradigm

dynamically-typed object-oriented paradigm

#programming-languages