Programming Languages (PSU CS558)

Learning the broad field of programming languages using this book (PSU CS558 Fall 2014).

Chapter 10: Control II – Procedures and Environments

  • An function should produce a value and produces no side effect (similar to expression)
  • A procedure is executed for its side effects and return no value (similar to statement).

10.1 Procedure Definition and Activation

  • Procedure is a mechanism in a programming language for abstracting a group of actions or computations.
    • The group of actions is called the body of procedure
    • The procedure is defined by providing a specification or interface and a body.
    • The specification gives the name, list of the types and names of its formal parameters
    • declaration (C++), prototype (C) are separate from its body.

10.2 Procedure Semantics

  • When a block is encountered during execution, it causes the allocation of local variables and other objects corresponding to the declarations of the block which called the activation record (or stack frame).
int x;
void B(void) {
  int i;
  i = x / 2;
  ...
} /* end B */
void A (void) {
  int x, y;
  ...
  x = y * 10;
  B();
} /* end A */
int main () {
  A();
  return 0;
}
  • The stack frame of global environment, block A and a procedure call of B
-----
| x |  global environment
=====
| x |
-----  Activation record of A
| y |
=====
| i |  Activation record of B
-----
  • parameters are sometimes called formal parameters and arguments are called actual parameters.

10.3 Parameter-Passing Mechanisms

 

pass by value

  • value parameter behave as constant values during the execution of the procedure
  • if the parameter has a pointer or reference type, then the value is an address and can be used to change memory outside the procedure. (array are implicitly pointer in C/C++).
int max (int x, int y) { return x > y ? x: y; }
max ( 10, 2 + 3); // replace the body of max as 10 > 5 ? 10: 5

pass by reference

  • passes the location of the variable
  • In C, operator & to indicate the location of a variable and the operator * to dereference a pointer.
void inc(int &x) { x++; } // pass by reference
inc(a);

/* is the same as */

void inc(int *x) { (*x)++; } // pass the pointer & deference the pointer
inc(&a); // pass the address of a
  • In C++, reference argument must be l-value, that is , they must have known addresses.
void inc(int &x) { x++; }
inc(2); // error for C++ because it is not an l-value.

pass by value-result

  • the value of the argument is copied and used in the procedure, and then the final value of the parameter is copied back out to the location of the argument when the procedure exits.
void p(int x, int y) { // v,t: x=1, y=1, a=1; r: x=a, y=a, a=1
  x++; // v: x=2, y=1, a=1; r: x=a, y=a, a=2; t: x=2, y=1, a=1
  y++; // v: x=2, y=2, a=1; r: x=a, y=a, a=3; t: x=2, y=2, a=1
}      // v: x=2, y=2, a=1; r: x=a, y=a, a=3; t: x=2, y=2, a=2
main () {
 int a = 1;
 p(a, a); 
 ...
}
/* at the end of main */
// v: pass by value, a = 1
// r: pass by reference, a = 3
// t: pass by value-result, a = 2

pass by name

  • The argument is not evaluated until its actual use as a parameter in the called procedure.
int i;
int a[10];

void inc(int x) { 
// v:x=1,i=1,a[1]=1,a[2]=2; r:x=a[1],  i=1,a[1]=1,a[2]=2 
// t:x=1,i=1,a[1]=1,a[2]=2; n:x=a[i],  i=1,a[1]=1,a[2]=2 
  i++; 
// v:x=1,i=2,a[1]=1,a[2]=2; r:x=a[1],  i=2,a[1]=1,a[2]=2 
// t:x=1,i=2,a[1]=1,a[2]=2; n:x=a[i],  i=2,a[1]=1,a[2]=2 
  x++; 
// v:x=2,i=2,a[1]=1,a[2]=2; r:x=a[1]+1,i=2,a[1]=2,a[2]=2 
// t:x=2,i=2,a[1]=2,a[2]=2; n:x=a[i]+1,i=2,a[1]=1,a[2]=3 
} 
// v:x=2,i=2,a[1]=1,a[2]=2; r:x=a[1]+1,i=2,a[1]=2,a[2]=2 
// t:x=2,i=2,a[1]=2,a[2]=2; n:x=a[i]+1,i=2,a[1]=1,a[2]=3 
main() { 
  i = 1; 
  a[1] = 1; 
  a[2] = 2; 
  inc(a[i]); 
  return 0; 
} 
/* at the end of main */ 
// v: pass by value       : i=1, a[1]=1, a[2]=2 
// r: pass by reference   : i=2, a[1]=2, a[2]=2 
// t: pass by value-result: i=2, a[1]=2, a[2]=2 
// n: pass by name        : i=2, a[1]=1, a[2]=3

10.4 Procedure Environments, Activations, and Allocation

10.5 Dynamic Memory Management

10.6 Exception Handling and Environments

10.7 Case Study: Processing Parameter Modes in TinyAda

Additional Notes

Exercise

Other Resources

Advertisements

Chapter 9: Control I – Expression and Statements

  • An expression returns a value and produces no side effect (in pure mathematical form)
  • A statement is executed for its side effects and return no value.

9.1 Expression

  • If the evaluation of an expression causes no side effects, then the expression will yield the same result, regardless of the order of evaluation of its subexpression. In the presence of side effects, the order of evaluation can make a difference.
  • short-circuit evaluation evaluate left-to-right up to the point where the truth value of the entire expression becomes known and then the evaluation stops.
  • referential transparency (substitution rule) is any two expressions in a program that have the same value may be substituted for each other anywhere in the program. Their values always remain equal, regardless of the context in which they are evaluated.
  • normal order evaluation of an expression means that each operation (or function) begins its evaluation before its operands are evaluated, and each operand is evaluated only if it is needed for the calculation of the value of the operation.
  • normal order evaluation is lazy evaluation in Haskell and pass by name in Algo160.

9.2 Conditional Statements and Guards

  • If-Statements
    • {if (e1) if (e2) S1 else S2} has a dangling-else ambiguity where the last else could be associate with either the first or second else.
    • Solution: diambiguating rule or bracketing keyword
  • Case- and Switch-Statements

9.3 Loops and Variations on WHILE

  • for loop vs while loop
for (e1; e2; e3) S;

e1;
while (e2) {
  S;
  e3;
}

9.4 The GOTO Controversy and Loop Exits

  • structured vs unstructured loop exist
int search(int array[], int target){
  boolean found = false;
  int index = 0;
  while (index < array.length && ! found) 
    if (array[index] == target)
      found = true;
    else
      index++;
  if (found)
    return index;
  else
    return -1;
}

int search(int array[], int target){
  for (int index = 0; index < array.length; index++) 
    if (array(index) == target)
      return index;
  return -1;
}

9.5 Exception Handling

  •  explicit control mechanism has a syntactic indication of the transfer at the point where a transfer control takes place. The opposite is implicit transfer of control where there is no indication.
  • exception handling is the control of error conditions or other unusual events during the execution of a program. It involves the declaration of both exceptions and exception handlers.
  • exception is any unexpected or infrequent event
  • exception handler is a procedure or code sequence that is designed to be executed when a particular exception is raised and that is supposed to make it possible for normal execution to continue in some way.
  • asynchronous exceptions occur at any moment and not just in response to the execution of program code.
  • synchronous exceptions occur in direct response to actions by the program.
  • resumption model of exception handling return to the point at which the exception was first raised and begin execution again.
  • termination model of exception handling continue execution with the code immediately following the block or expression in which the handler that is executed was found.

9.6 Case Study: Computing the Values of Static Expressions in TinyAda

Additional Notes

Exercise

Other Resources

Chapter 8: Data Types

  • Reasons to have strongly typed language (static type checking)
    • execution efficiency (memory allocation and machine code generation by compiler)
    • translation efficiency (reduce recompilation)
    • writability (catch programming error earlier)
    • security and reliability (reduce execution error)
    • readability
    • remove ambiguities
    • design tool (catch incorrect design descision)
    • interface consistency and correctness

8.1 Data Types and Type Information

  • data type is a set of values.
  • type checking determine whether the type information in a program is consistent.
  • type inference is the process of attaching a type to an expression.
  • type constructor uses to create complex types out of the basic types call user-defined types.
  • type declaration or definition gives name to the user-defined types.
  • untyped language (dynamically typed languages) are without static type systems and all type checking is performed at execution time.

8.2 Simple Types

  • ordinal types has a discrete order that exist on the set.

8.3 Type Constructors

  • Cartesian Product is an ordered pairs of element from multiple sets. (e.g. struct, tuple)
  • Union is discriminated if a tag or discriminator is added to the union to distinghish which type the element is.
  • Undiscriminated union is similar to disjoint union. (e.g. union in c)
  • array on row-major form vs column-major form. (e.g. a[][20] as an argument in function because row size must be known in row-major form so compiler know how to store a).
  • recursive type define a set by taking the smallest solution (least fixed point)

8.4 Type Nomenclature in Sample Languages

8.5 Type Equivalence

  • structural equivalence is when two type have the same structure or built in exactly the same way using the same type constructors from the same simple types.
  • name equivalence is when two type is the same only if they have the same name.
  • declaration equivalence is when new names for existing type names are equivalent to the original types.

8.6 Type Checking

  • Type compatibility (e.g. assignment compatibility, where l-value and r-value are the same type)
  • Implicit type (e.g. constant)

8.7 Type Conversion

  • implicit conversion (or coercions)
  • widening conversion is where the target data type can hold all of the information being converted without loss of data. narrowing conversion is the opposite.
  • explicit conversion (or cast)

8.8 Polymorphic Type Checking

  • overloaded function is ad hoc polymorphism.
  • parametric polymorphism (array of α where α is a type parameter for the array)
  • implicit vs explicit parametric polymorphism
  • subtype or pure polymorphism when objects that share a common ancestor can also either share or redefine the operations that exist for that ancestor.
  • monomorphic is no polymorphism.
  • without knowing the type, a translator cannot determin the size of the values, which much be known in order to make copies from location to location by the code.
    • Expansion generate a copy of the code for each different type used in the function call. Result in code bloat.
    • Boxing or tagging by fix a size for all data that contain any scalar value and add a tag bit to note if its a scalar or not. Result in indirection.

8.9 Explicit Polymorphism

  • mechanism for explicit polymorphism is the template.
  • implicitly constrained parametric polymorphism implicitly applies a constraint to the type parameter with a specific operator (e.g. >) defined for its values.
  • an explicit type parameter example in C++
template <typename T>
struct StackNode{
  T data;
  StrackNode<T> * next;
};

template <typename T>
struct Stack{
  StackNode<T> * theStack;
};

template <typename T>
T top (Stack<T> s) {
  return s.theStack->data;
}

Stack<int> s;
s.theStack = new StackNode<int>;
s.theStack->data = 3;
s.theStack->next = 0;

int t = top(s); // t is now 3

8.10 Case Study: Type Checking in TinyAda

Additional Notes

Exercise

Other Resources

Chapter 7: Basic Semantics

  • Syntax of a programming language tells us what the language constructs looks like.
  • Semantic of a programming language tells us what the language constructs actually do.

7.1 Attributes, Binding, and Semantic Functions

  • Values are any storable quantities.
  • Locations are like addresses in the memory
  • Meaning of name is determined by the properties, or attributes, associated with the name.
  • The process of associating an attribute with a name is called binding.
  • Binding time of the attribute classified according to the time during the translation/execution process when it is computed and bound to a name.
    • Static binding occurs prior to execution.
      • A static attribute can be bound during parsing or semantic analysis (translation time),
      • during the linking of the program with libraries (link time),
      • during the loading of the program for execution (load time).
      • language definition time, predefine identifiers or the language.
    • Dynamic binding occurs during execution
      • A dynamic attribute can be bound on entry or exit from a procedure, or
      • on entry or exit from the entire program
  • symbol table is a data structure that maintain the appropriate meanings given to names (names → attributes).
  • parsing phase of translation
    • lexical analysis determines whether a string of characters represents a token in the vocabulary of the language
    • syntax analysis determines whether a sequence of tokens represents a phrase in the CFG of the language.
    • static semantic analysis is concerned with establishing the attributes of names in declarations and ensuring that the use of these name in references conforms to their declared attributes.
  • Environment is to maintain the binding of names to storage location (names → location).
  • Memory is to maintain the binding of storage location to values. (locations → values).

7.2 Declarations, Blocks, and Scope

  • explicit binding (int x; bind x to integer) vs implicit binding (int x; location of x)
  • definition bind all potential attributes.
  • declaration partially specify attributes (e.g. function prototype)
  • declarations associate with a specific block are called local
  • declarations in surrounding blocks (or global) are nonlocal
  • block structure associate each declared name a level number and offset to call lexical address
    • The level number increase as we move into each nested block
    • The offset of the names declared within each nested block
  • The scope of a binding is the region of the program over which the binding is maintained.
int x;

void p() {
  char x;
  ...
}

void q() {
  char x;
  ::x = 42;
  ...
}
  • x in p() takes precedence over the global declaration of x
  • scope resolution operator :: (in C++) is to access hidden declaration (::x in q()).
  • extern is use to access global variable declaration across files in C.

7.3 The Symbol Table

  • scope analysis
    • the maintenance of scope information in a lexically scoped language with block structure requires that declarations be processed like a stack
      • on entry into a block, all declaration of that block are processed and the corresponding bindings added to the symbol table
      • on exit from the block, the bindings provided by the declaration are removed and restoring any previous bindings that may have existed.
  • dynamic vs static scoping.
  • problem with dynamic scoping
    • when a nonlocal name is used in an expression or statement, the appropriate declaration that applies to that name must obtain from executions. The semantics of the program changes during execution.
    • nonlocal variable references cannot predicted prior to execution, neither can the data types of the variable.

7.4 Name Resolution and Overloading

  • A translator disambiguate two uses of the same symbol by looking at the data types of the operands.
  • Overload resolution
    • The basic method for allowing overloaded functions is to expand the operation of the lookup operation in the symbol table to perform lookups based not only on the name of a function but also on the number of its parameters and their data types.
  • There is no semantic difference between operator and functions, only syntactic difference that operators are written in infix form while function calls are always written in prefix form.

7.5 Allocation, Lifetimes, and the Environment

  • The lifetime of an object is the duration of its allocation in the environment
  • heap allow arbitrary allocation and deallocation (dynamic allocation)
  • stack-based/automatic allocation refer to allocation of local variable.
  • static allocation refer to allocation of global variable.
int f() {
  static int x;
}
  • x is allocated only once and it has the same meaning (and value) across all calls to f. This combination of local scope with global lifetime can be used to preserve local state across calls to f, while at the same time preventing code outside the function from changing this state.

7.6 Variables and Constants

  • Variables is an object whose stored value can change during execution
    • principle attributes are name, location and value.
    • r-value is value stored in the location of a variable
    • l-value is the location of a variable
    • assignment by sharing result in binding the location instead of its value (pointer or reference semantics).
    • assignment by cloning result in binding to a new allocation location with the copy of the value (storage or value semantics).
  • Constants is a language entity that has a fixed value for the duration of its existence in a program.
    • no location attribute, only value.
    • constant has value semantics.
    • symbolic constant is essentially a name for a value
    • compile time vs load time constant

7.7 Aliases, Dangling References, and Garbage

  • Alias occurs when the same object is bound to two different names at the same time.
    • occur during procedure call, through the use of pointer variable and through assignment by sharing.
    • side effect of a statement is any change in the value of a variable that persists beyond the execution of the statement.
    • potential harmful side effect is changes to variables whose names do not directly appear in the statement because the effect cannot determined from the written code.
  • Dangling references is a location that has been deallocated from the environment but that can still be accessed by a program.
    • occur when global pointer reference local object, return a pointer to a local object in a function, and two pointers reference to the same object while one of the pointer free that object.
  • Garbage is memory that has been allocated in the environment but inaccessible to the program.
    • occur when pointer to a memory when reassign to another object before call free.

7.8 Case Study: Initial Static Semantic Analysis of TinyAda

Additional Notes

Exercise

Other Resources

Chapter 6: Syntax

6.1 Lexical Structure of Programming Languages

  • Token categories
    • reserved words (keywords)
    • literals or constants
    • special symbols
    • identifiers
  • principle of longest substring takes the longest possible substring of nonblank characters as a single token.
  • Regular expression
    • + mean one or more
    • ? mean one or none
    • * mean none or more

6.2 Context-Free Grammars and BNF’s

  • Elements of CFG
    • start symbol is nonterminal that stands for the entire, top-level phrase being defined.
    • nonterminals are broken down into further phrase structures
    • terminals cannot be broken down into further phrase structures
    • productions are rules use for the derivation.
  • CFG defines a language.

6.3 Parse Trees and Abstract Syntax Trees

  • A Parse Tree is labeled by nonterminal at interior nodes and terminals at leaves. The structure of a parse tree is completely specified by the grammar rules of the language and a derivation of a particular sequence of terminals.
  • Abstract syntax tree abstract the essential structure of the parse tree.
Example: arithmetic expression grammar
expr   → expr + expr | expr * expr | (expr) | number
number → number digit | digit
digit  → 0 | 1 | 2 | 3 | 4| 5 | 6 | 7 | 8 | 9

Example: parse tree for 234
         number
        /     \
    number    digit
   /     \      |
number  digit   4
  |       |
digit     3
  |
  2

Example: abstract syntax tree for 234
    4
   /
  3
 /
2

6.4 Ambiguity, Associativity, and Precedence

  • A grammar which two distinct parse trees are possible for the same string is ambiguous.
  • left-recursive rule for an operation causes it to left-associate, right-recursive causes right-associate.
3 + 4 + 5

left-recursive/associate
expr → expr + term

          expr
         / | \
     expr  +  term
    / | \      |
expr  +  term  5
 |        |
 3        4

right-recursive/associate
expr → term + expr

     expr
    / | \
term  +  expr
 |       / | \      
 3   term  +  expr
      |        |
      4        5

6.5 EBNFs and Syntax Diagrams

  • EBNF
    • {} stands for “zero or more repetition of”
    • [] indicate optional part of the structure

6.6 Parsing Techniques and Tools

  • Bottom-up parser match an input with the right-hand sides of the grammar rules, when match occurs, the right-hand side is replaced by, or reduced to, the nonterminal on the left.
  • Top-down parsers expand the nonterminal to match incoming tokens and directly construct a derivation.
  • Recursive-decent parser turns the nonterminals into a group of mutually recursive procedures whose actions are based on the right-hand sides of the BNF’s.
  • predictive parser requirement
    • able to distinguish between choices in a grammar rule in term of First sets or the First sets of any two choices must not have any token in common (where First(\alpha) to be the set of tokens that can begin the string \alpha).
    • for any optional part, no token beginning the optional part an also come after the optional part.

6.7 Lexics vs. Syntax vs. Semantics

6.8 Case Study: Building a Syntax Analyzer for TinyAda

Additional Notes

Exercise

Other Resources

Chapter 5: Object-Oriented Programming

5.1 Software Reuse and Independence

  • Four basic way that a software component can be modified for reuse
    • extension of the data or operations
    • redefinition of one or more of the operations
    • abstraction
    • polymorphism

5.2 Smalltalk

5.3 Java

  • Some of the Java feature include garbage collection and use of references instead of explicit pointers.
  • Basic Elements of Java: Classes, Objects and Methods.
    • Constructor chaining is when one constructor call another constructor with argument.
  • The Java Collection Framework: Interfaces, Inheritance, and Polymorphism
    • An interfaces is a set of operations on objects of a given type. Interfaces serve as the glue that connects components in software systems.
    • If a class implements an interface, any of its subclasses also (implicitly) implement that interface.
    • Abstract class implement common properties and behavior for their subclasses. Concrete classes can be instantiated.
    • listOfStrings and listOfChars above are just List. Same methods can be called on the two List variable even though the two lists they reference have different implementations and different element types. The variable queueOfFloats has been declared Queue<Float> and so the LinkedList that it refers to are using the methods specified in the Queue interface.
List<String> listOfStrings = new LinkedList<String>();
Queue<Float> queueOfFloats = new LinkedList<Float>();
List<Character> listOfChars = new ArrayList<Character>();
  • Dynamic Binding and Static Binding
    • Dynamic binding is when method being called upon an object is looked up by name at runtime.
    • Java complier statically determines which implementation of a method to use when the receiver object’s actual class can be determined at compile time. However, it will not actually generate code for static binding unless the method has been defined as final or static.
      • final method cannot be overridden in a subclass
      • static method call on a class rather than an instance.

5.4 C++

  • Basic Element of C++: Classes, Data Members, and Member Functions
    • Instance variables and methods are both members of the class (data member and member function, respectively).
    • public, protected, or private member are accessible by client code and derived class, only derived class, or none, respectively.
  • Static Binding, Dynamic Binding and Virtual Functions
    • All member functions are statically bound at compile time. Only function defined using the keyword virtual are candidates for dynamic binding.
    • pure virtual declaration in an abstract class by use the keyword virtual along with the function = 0.
    • Example of repeated inheritance (two separate copies of object of class A) vs shared inheritance (using virtual keyword).
class A {...};
class B : public A {...};
class C : public A {...};
class D : public B, public C {...};

A     A
|     |
B     C
 \   /
   D
class A {...};
class B : virtual public A {...};
class C : virtual public A {...};
class D : public B, public C {...};

   A
 /   \
B     C
 \   /
   D

5.5 Design Issues in Object-Oriented Languages

  • Classes vs Types
    • Possible incorporation of classes into the type system.
      • As typeless entities and exclude from type checking (Objective-C).
      • As type constructors and must be incorporated into type checking (C++). Compatibility of objects of descendent classes to objects of ancestor classes complicates type checking (e.g. x is descendent of y, so y = x but flag x = y.)
      • As a type system itself (Smalltalk, Java).
  • Classes vs Modules
    • Code that uses a class becomes dependent on the particular implementation of the class even if it cannot make use of the details of that implementation.
  • Inheritance vs Polymorphism
    • Four basic kinds of polymorphism
      • parametric polymorphism in which type parameters may remain unspecified in declaration (e.g. C++ template).
      • Overloading in which different function or method declarations share the same name and are disambiguated through the use of the types of the parameters in each declaration.
      • Subtype polymorphism in which all the operations of one type can be applied to another type.
      • Inheritance in which is a kind of subtype polymorphism and overloading.

5.6 Implementation Issues in Object-Oriented Languages

  • Implementation of Objects and Methods
    • The allocation of instance variable of super class precede those variable from derived class in the object instance so that the allocation of the variable within the object instance stay the same.
  • Inheritance and Dynamic Binding
    • Allocation of methods as pointer in the allocation of the object instance.

Additional Notes

Exercise

Other Resources

Chapter 3: Functional Programming

3.1 Programs as Functions

  • In mathematics, variables always stand for actual values, while in imperative programming languages, variable refer to memory locations that store values. Therefore, x = x + 1 make no sense in mathematics.
  • In functional programming, once a variable is bound to a value, the variable cannot be change. Thus, there is no assignment.
  • Lack of assignment mean no notion of the internal state of a function.
  • Referential transparency mean the value of the function is not depend on the order of evaluation of its arguments. Thus, function must be view as value as well.

3.2 Scheme: A Dialect of Lisp

  • Syntax
    • expression → atom | ‘(‘ {expression} ‘)’
    • atom → number | string | symbol | character | boolean
  • Expression
    • #T mean true
    • #\a mean the character ‘a’
    • (2.1 2.2 2.3) is a list of numbers
    • (+ 2 3) is 2 + 3
  • Evaluation rule
    • atomic literal evaluate to themselves
    • symbol are treat as identifier.
    • parenthesized expression or list is evaluated as follow:
      • if first term is keyword, special rule applied.
      • otherwise, first term must evaluate to a function.
    • Scheme uses prefix form (+ 2 3) is 2 + 3.
    • quote will return the expression without evaluation. (quote (2.1 2.2 2.3)) or ‘(2.1 2.2 2.3) return (2.1 2.2 2.3)
    • (if exp1 exp2 exp3) evaluate exp2 if exp1 is true, otherwise exp3 is evaluated. (similar to if-then statement)
    • (cond exp1 … expn) where each expi is a pair (first second) where second expression will be evaluated if first is true. (similar to switch statement)
    • (let ((a 2) (b 3)) (+ a b)) will allows variable names to be bound to values within an expression. Result is 5 for this expression.
    • (lambda param-list body) create a function without name to reference it. Use let to bind the function to a name but let cannot use to define recursive function, which letrec will. However let and letrec only introduce variables that are visible within the scope and for the lifetime of the let or letrec.
    • To make a new, global binding of a variable visible in the top-level environment, use define.
  • Dynamic or latent type checking means two things:
    • only values, not variables, have data types.
    • types of values are not checked until it is absolutely necessary to do so at runtime.
  • Tail and Non-Tail Recursion
    • To avoid inefficiency with recursion, make any recursive steps the last steps in any functions (or tail recursive).
  • Data Structures in Scheme
    • a list representation of binary tree could be (“horse” (“cow” () (“dog” () ())) where a node in this tree is a list of three items (name left right).
    • If L is (1, 2, 3), then (car L) give the head element 1 and (cdr L) give a list without its head element, (2, 3). (cons 4 L) will add the element 4 at the head of list L, (4, 1, 2, 3).
    • (car (cdr L))) equals to (cadr L), (cdr (cdr L)) equals to (cddr L) and (car (cdr (cdr L))) equals to (caddr L).
    • null? return true if its list argument is empty
    • (list a) is equal to (cons a ‘())
  • Programming Techniques in Scheme
    • Use recursion to perform loops
    • Use accumulating parameter to turn a non-tail-recursive procedure into a tail-recursive procedure
  • HIgher-Order Functions
    • using lambda to define a function. f is a function with two parameters. We can define new function that uses make-double
      • (define make-double (lambda f) (lambda (x) (f x x)))
      • (define square (make-double *))
  • Static (Lexical) Scoping
    • In static scoping, the meaning or value of a given variable can be determined just by reading the text of the program.
    • In dynamic scoping, the meaning of a variable depends on the runtime context.
  • Symbolic Information Processing and Metalinguistic Power

3.3 ML: Functional Programming with Static Typing

3.4 Delayed Evaluation

  • Pass by name delayed evaluation is helpful in that it allows parameters to remain uncomputed if not needed and permits special forms similar to if and cond to be defined as ordinary functions.
  • Lazy Evaluation
    • All arguments to user defined functions are delayed
    • All bindings of local names in let and letrec expressions are delayed
    • All arguments to constructor functions (such as cons) are delayed
    • All arguments to other predefined functions, such as the arithmetic functions “1”, “*”, and so on, are forced
    • All function-valued arguments are forced
    • All conditions in selection forms such as if and cond are forced

3.5 Haskell – A Fully Curried Lazy Language with Overloading

  • Elements of Haskell
    • ++ operator for list concatenation
    • plus2 = (2 +) define a function that add 2 to its argument
    • (\X -> X * X) 3 is an anonymous function or lambda.
    • [1, 2, 3] is a list of 1, 2 and 3. The type must match for all elements.
    • (1, 2, 3) is a tuple of 1, 2 and 3.  The type does not have to match for all elements.
    • : corresponding to concatenating an element to the front of a list
  • HIgher-Order Functions and List Comprehensions
    • function composition operator (.)
    • ((*3) . (2+)) 5 gives 21 by doing function composition of 2+5 and then times 3.
    • List comprehensions
      • square_list lis = [x * x| x <- lis] is the same as (\x -> x * x)
  • Lazy Evaluation and Infinite Lists
    • [n..] stands for the list of integers beginning with n.
    • [2,4..] for even list of integer
    • take x will take x number of elements from the beginning of the list
    • drop x will drop x number of elements from the beginning of the list
  • Type Classes and Overloaded Functions
    • square x = x* x where square 2 will give 4 but square 3.5 will give 12.25. Thus, the function overloaded using type class Num. Int, Float and Double are instance of Num.
    • Class Eq requires for == and /=.
    • Class Ord requires for < or > …
    • Class Integral requires for div and mod operations.

3.6 The Mathematics of Functional Programming: Lambda Calculus

Additional Notes

Exercise

Other Resources