Introduction

• Programs in logic languages are expressed in a form of symbolic logic
• Use a logical inferencing process to produce results
• Declarative rather that procedural:

Only specification of results are stated (not detailed procedures for producing them)

Overview of Logic Programming

• Declarative semantics

There is a simple way to determine the meaning of each statement

Simpler than the semantics of imperative languages

• Programming is nonprocedural

Programs do not state now a result is to be computed, but rather the form of the result

Example: Sorting a List

• Describe the characteristics of a sorted list, not the process of rearranging a list

sort(old_list, new_list) Ì permute (old_list, new_list) Ç sorted (new_list)

sorted (list) Ì “j such that 1£ j < n, list(j) £ list (j+1)

The Origins of Prolog

• University of Aix-Marseille (Calmerauer & Roussel)

Natural language processing

• University of Edinburgh (Kowalski)

Automated theorem proving

Inferencing Process of Prolog

• Queries are called goals
• If a goal is a compound proposition, each of the facts is a subgoal
• To prove a goal is true, must find a chain of inference rules and/or facts. For goal Q:

P2 :- P1

P3 :- P2

…

Q :- Pn

• Process of proving a subgoal called matching, satisfying, or resolution

Approaches

• Matching is the process of proving a proposition
• Proving a subgoal is called satisfying the subgoal
• Bottom-up resolution, forward chaining
• Top-down resolution, backward chaining
• Prolog implementations use backward chaining

Subgoal Strategies

• When goal has more than one subgoal, can use either

Depth-first search:  find a complete proof for the first subgoal before working on others

Breadth-first search: work on all subgoals in parallel

• Prolog uses depth-first search

Can be done with fewer computer resources

Backtracking

• With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution: backtracking
• Begin search where previous search left off
• Can take lots of time and space because may find all possible proofs to every subgoal

Simple Arithmetic

• Prolog supports integer variables and integer arithmetic
• is operator: takes an arithmetic expression as right operand and variable as left operand

  A is B / 17 + C

• Not the same as an assignment statement!

The following is illegal:

Sum is Sum + Number.

Deficiencies of Prolog

• Resolution order control

In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

• The closed-world assumption

The only knowledge is what is in the database

• The negation problem

Anything not stated in the database is assumed to be false

• Intrinsic limitations

It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort

Applications of Logic Programming

• Relational database management systems
• Expert systems
• Natural language processing

Introduction

• The design of the imperative languages is based directly on the von Neumann architecture
• The design of the functional languages is based on mathematical functions

Mathematical Functions

• A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set
• A lambda expression specifies the parameter(s) and the mapping of a function in the following form

  l(x) x * x * x

for the function  cube(x) = x * x * x

Lambda Expressions

• Lambda expressions describe nameless functions
• Lambda expressions are applied to parameter(s) by placing the parameter(s) after the expression

  e.g.,   (l(x) x * x * x)(2)

which evaluates to 8

Functional Forms

• A higher-order function, or functional form, is one that either takes functions as parameters or yields a function as its result, or both

Function Composition

• A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second

  Form: h º f ° g

which means h (x) º f ( g ( x))

For f (x) º x + 2  and  g (x) º 3 * x,

h º f ° g yields (3 * x)+ 2

LISP Data Types and Structures

• Data object types: originally only atoms and lists
• List form: parenthesized collections of sublists and/or atoms

  e.g., (A B (C D) E)

• Originally, LISP was a typeless language
• LISP lists are stored internally as single-linked lists

LISP Interpretation

• Lambda notation is used to specify functions and function definitions. Function applications and data have the same form.

  e.g., If the list (A B C) is interpreted as data it is

a simple list of three atoms, A, B, and C

If it is interpreted as a function application,

it means that the function named A is

applied to the two parameters, B and C

• The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation

Output Functions

• Usually not needed, because the interpreter always displays the result of a function evaluated at the top level (not nested)
• Scheme has PRINTF, which is similar to the printf function of C
• Note: explicit input and output are not part of the pure functional programming model, because input operations change the state of the program and output operations are side effects

Numeric Predicate Functions

• #T (or #t) is true and #F (or #f) is false (sometimes () is used for false)
• =, <>, >, <, >=, <=
• EVEN?, ODD?, ZERO?, NEGATIVE?
• The NOT function inverts the logic of a Boolean expression

Control Flow

• Selection- the special form, IF

  (IF predicate then_exp else_exp)

    (IF (<> count 0)

(/ sum count)

)

• Recall from Chapter 8 the COND function:

(DEFINE (leap? year)

(COND

((ZERO? (MODULO year 400)) #T)

((ZERO? (MODULO year 100)) #F)

(ELSE (ZERO? (MODULO year 4)))

))

List Functions

• QUOTE – takes one parameter; returns the parameter without evaluation

QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function.  QUOTE is used to avoid parameter evaluation when it is not appropriate

QUOTE can be abbreviated with the apostrophe prefix operator

‘(A B) is equivalent to (QUOTE (A B))

• Examples:

  (CAR ′((A B) C D)) returns (A B)

(CAR ′A) is an error

(CDR ′((A B) C D)) returns (C D)

(CDR ′A) is an error

(CDR ′(A)) returns ()

(CONS ′() ′(A B)) returns (() A B)

(CONS ′(A B) ′(C D)) returns ((A B) C D)

(CONS ′A ′B) returns (A . B)  (a dotted pair)

• LIST is a function for building a list from any number of parameters

   (LIST ′apple ′orange ′grape) returns

(apple orange grape)

Predicate Function: EQ?

• EQ? takes two expressions as parameters (usually two atoms); it returns #T if both parameters have the same pointer value; otherwise #F

  (EQ? ‘A ‘A) yields #T

(EQ? ‘A ‘B) yields #F

(EQ? ‘A ‘(A B)) yields #F

(EQ? ‘(A B) ‘(A B)) yields #T or #F

(EQ? 3.4 (+ 3 0.4))) yields #T or #F

• EQV? is like EQ?, except that it works for both symbolic and numeric atoms; it is a value comparison, not a pointer comparison

   (EQV? 3 3) yields #T

(EQV? ‘A 3) yields #F

(EQV 3.4 (+ 3 0.4)) yields #T

(EQV? 3.0 3) yields #F  (floats and integers are different)

Introduction to Exception Handling

• In a language without exception handling

–When an exception occurs, control goes to the operating system, where a message is displayed and the program is terminated

• In a language with exception handling

–Programs are allowed to trap some exceptions, thereby providing the possibility of fixing the problem and continuing

Exception Handling in C++

• Added to C++ in 1990
• Design is based on that of CLU, Ada, and ML

C++ Exception Handlers

• Exception Handlers Form:

  try {

— code that is expected to raise an exception

}

catch (formal parameter) {

— handler code

}

…

catch (formal parameter) {

— handler code

}

Introduction to Event Handling

• An event is a notification that something specific has occurred, such as a mouse click on a graphical button
• The event handler is a segment of code that is executed in response to an event

Event Handling in C#

• Event handling in C# (and the other .NET languages) is similar to that in Java
• .NET has two approaches, Windows Forms and Windows Presentation Foundation—we cover only the former (which is the original approach)
• An application subclasses the Form predefined class (defined in System.Windows.Forms)
• There is no need to create a frame or panel in which to place the GUI components
• Label objects are used to place text in the window
• Radio buttons are objects of the RadioButton class
• Components are positioned by assigning a new Point object to the Location property of the component  private RadioButton plain = new RadioButton();

  plain.Location = new Point(100, 300);

  plain.Text = ″Plain″;

  controls.Add(plain);

• All C# event handlers have the same protocol, the return type is void and the two parameters are of types object and EventArgs
• An event handler can have any name
• A radio button is tested with the Boolean Checked property of the button

    private void rb_CheckedChanged (object o,

  EventArgs e) {

  if (plain.Checked) …

  …

  }

• To register an event, a new EventHandler object must be created and added to the predefined delegate for the event

• When a radio button changes from unchecked to checked, the CheckedChanged event is raised
• The associated delegate is referenced by the name of the event
• If the handler was named rb_CheckedChanged, we could register it on the radio button named plain with:

plain.CheckedChanged +=

new EventHandler (rb_CheckedChanged);

Introduction

• Concurrency can occur at four levels:

–Machine instruction level

–High-level language statement level

–Unit level

–Program level

• Because there are no language issues in instruction- and program-level concurrency, they are not addressed here

Introduction to Subprogram-Level Concurrency

• A task or process or thread is a program unit that can be in concurrent execution with other program units
• Tasks differ from ordinary subprograms in that:

–A task may be implicitly started

–When a program unit starts the execution of a task, it is not necessarily suspended

–When a task’s execution is completed, control may not return to the caller

• Tasks usually work together

Semaphores

• Dijkstra – 1965
• A semaphore is a data structure consisting of a counter and a queue for storing task descriptors

–A task descriptor is a data structure that stores all of the relevant information about the execution state of the task

• Semaphores can be used to implement guards on the code that accesses shared data structures
• Semaphores have only two operations, wait and release (originally called P and V by Dijkstra)
• Semaphores can be used to provide both competition and cooperation synchronization

Cooperation Synchronization with Semaphores

• Example: A shared buffer
• The buffer is implemented as an ADT with the operations DEPOSIT and FETCH as the only ways to access the buffer
• Use two semaphores for cooperation: emptyspots and fullspots
• The semaphore counters are used to store the numbers of empty spots and full spots in the buffer
• DEPOSIT must first check emptyspots to see if there is room in the buffer
• If there is room, the counter of emptyspots is decremented and the value is inserted
• If there is no room, the caller is stored in the queue of emptyspots
• When DEPOSIT is finished, it must increment the counter of fullspots
• FETCH must first check fullspots to see if there is a value–If there is a full spot, the counter of fullspots is decremented and the value is removed

  –If there are no values in the buffer, the caller must be placed in the queue of fullspots

  –When FETCH is finished, it increments the counter of emptyspots

• The operations of FETCH and DEPOSIT on the semaphores are accomplished through two semaphore operations named wait and release

Monitors

• Ada, Java, C#
• The idea: encapsulate the shared data and its operations to restrict access
• A monitor is an abstract data type for shared data

Message Passing

• Message passing is a general model for concurrency

–It can model both semaphores and monitors

–It is not just for competition synchronization

• Central idea: task communication is like seeing a doctor–most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous

Message Passing: Server/Actor Tasks

• A task that has accept clauses, but no other code is called a server task (the example above is a server task)
• A task without accept clauses is called an actor task

–An actor task can send messages to other tasks

–Note: A sender must know the entry name of the receiver, but not vice versa (asymmetric)

Message Passing Priorities

• The priority of any task can be set with the pragma Priority

pragma Priority (static expression);

• The priority of a task applies to it only when it is in the task ready queue

Introduction

• Many object-oriented programming (OOP) languages

–Some support procedural and data-oriented programming (e.g., Ada 95+ and C++)

–Some support functional program (e.g., CLOS)

–Newer languages do not support other paradigms but use their imperative structures (e.g., Java and C#)

–Some are pure OOP language (e.g., Smalltalk & Ruby)

–Some functional languages support OOP, but they are not discussed in this chapter

Object-Oriented Programming

• Three major language features:

–Abstract data types (Chapter 11)

–Inheritance

• Inheritance is the central theme in OOP and languages that support it

–Polymorphism

Design Issues for OOP Languages

• The Exclusivity of Objects
• Are Subclasses Subtypes?
• Single and Multiple Inheritance
• Object Allocation and Deallocation
• Dynamic and Static Binding
• Nested Classes
• Initialization of Objects

Support for OOP in C++

• General Characteristics:

–Evolved from C and SIMULA 67

–Among the most widely used OOP languages

–Mixed typing system

–Constructors and destructors

–Elaborate access controls to class entities

• Inheritance

–A class need not be the subclass of any class

–Access controls for members are

–Private (visible only in the class and friends) (disallows subclasses from being subtypes)

–Public (visible in subclasses and clients)

–Protected (visible in the class and in subclasses, but not clients)

• Multiple inheritance is supported

–If there are two inherited members with the same name, they can both be referenced using the scope resolution operator (::)

class Thread { … }

class Drawing { … }

class DrawThread : public Thread, public Drawing { … }

Implementing OO Constructs

• Two interesting and challenging parts

–Storage structures for instance variables

–Dynamic binding of messages to methods

The Concept of Abstraction

• An abstraction is a view or representation of an entity that includes only the most significant attributes
• The concept of abstraction is fundamental in programming (and computer science)
• Nearly all programming languages support process abstraction with subprograms
• Nearly all programming languages designed since 1980 support data abstraction

Introduction to Data Abstraction

• An abstract data type is a user-defined data type that satisfies the following two conditions:

–The representation of objects of the type is hidden from the program units that use these objects, so the only operations possible are those provided in the type’s definition

–The declarations of the type and the protocols of the operations on objects of the type are contained in a single syntactic unit. Other program units are allowed to create variables of the defined type.

Language Examples: C++

• Based on C struct type and Simula 67 classes
• The class is the encapsulation device
• A class is a type
• All of the class instances of a class share a single copy of the member functions
• Each instance of a class has its own copy of the class data members
• Instances can be static, stack dynamic, or heap dynamic
• Information Hiding–Private clause for hidden entities

  –Public clause for interface entities

  –Protected clause for inheritance

• Constructors:

  –Functions to initialize the data members of instances (they do not create the objects)

  –May also allocate storage if part of the object is heap-dynamic

  –Can include parameters to provide parameterization of the objects

  –Implicitly called when an instance is created

  –Can be explicitly called

  –Name is the same as the class name

• Destructors

–Functions to cleanup after an instance is destroyed; usually just to reclaim heap storage

–Implicitly called when the object’s lifetime ends

–Can be explicitly called

–Name is the class name, preceded by a tilde (~)

Encapsulation Constructs

• Large programs have two special needs:

–Some means of organization, other than simply division into subprograms

–Some means of partial compilation (compilation units that are smaller than the whole program)

• Obvious solution: a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units)
• Such collections are called encapsulation

Naming Encapsulations

• Large programs define many global names; need a way to divide into logical groupings
• A naming encapsulation is used to create a new scope for names
• C++ Namespaces

–Can place each library in its own namespace and qualify names used outside with the namespace

–C# also includes namespaces

• Java Packages

–Packages can contain more than one class definition; classes in a package are partial friends

–Clients of a package can use fully qualified name or use the import declaration

• Ruby classes are name encapsulations, but Ruby also has modules
• Typically encapsulate collections of constants and methods
• Modules cannot be instantiated or subclassed, and they cannot define variables
• Methods defined in a module must include the module’s name
• Access to the contents of a module is requested with the require method

Introduction

• Two fundamental abstraction facilities

Process abstraction

• Emphasized from early days
• Discussed in this chapter

Data abstraction

• Emphasized in the1980s
• Discussed at length in Chapter 11

Fundamentals of Subprograms

• Each subprogram has a single entry point
• The calling program is suspended during execution of the called subprogram
• Control always returns to the caller when the called subprogram’s execution terminates

Local Referencing Environments

• Local variables can be stack-dynamic

Advantages

• Support for recursion
• Storage for locals is shared among some subprograms

Disadvantages

• Allocation/de-allocation, initialization time
• Indirect addressing
• Subprograms cannot be history sensitive
• Local variables can be static

Advantages and disadvantages are the opposite of those for stack-dynamic local variables

Implementing Parameter-Passing Methods

• In most languages parameter communication takes place thru the run-time stack
• Pass-by-reference are the simplest to implement; only an address is placed in the stack

 

Function header:  void sub(int a, int b, int c, int d)

Function call in main: sub(w, x, y, z)

(pass w by value, x by result, y by value-result, z by reference

Parameters that are Subprogram Names

• It is sometimes convenient to pass subprogram names as parameters
• Issues:

1. Are parameter types checked?
2. What is the correct referencing environment for a subprogram that was sent as a parameter?

Calling Subprograms Indirectly

• Usually when there are several possible subprograms to be called and the correct one on a particular run of the program is not know until execution (e.g., event handling and GUIs)
• In C and C++, such calls are made through function pointers

• In C#, method pointers are implemented as objects called delegates

A delegate declaration:

public delegate int Change(int x);

This delegate type, named Change, can be instantiated with any method that takes an int parameter and returns an int value

A method:  static int fun1(int x) { … }

  Instantiate: Change chgfun1 = new Change(fun1);

Can be called with: chgfun1(12);

A delegate can store more than one address, which is called a multicast delegate

Overloaded Subprograms

• An overloaded subprogram is one that has the same name as another subprogram in the same referencing environment

Every version of an overloaded subprogram has a unique protocol

• C++, Java, C#, and Ada include predefined overloaded subprograms
• In Ada, the return type of an overloaded function can be used to disambiguate calls (thus two overloaded functions can have the same parameters)
• Ada, Java, C++, and C# allow users to write multiple versions of subprograms with the same name

User-Defined Overloaded Operators

• Operators can be overloaded in Ada, C++, Python, and Ruby
• A Python example

def __add__ (self, second) :

  return Complex(self.real + second.real,

self.imag + second.imag)

Use: To compute x + y, x.__add__(y)

Closures

• A closure is a subprogram and the referencing environment where it was defined

1. The referencing environment is needed if the subprogram can be called from any arbitrary place in the program
2. A static-scoped language that does not permit nested subprograms doesn’t need closures
3. Closures are only needed if a subprogram can access variables in nesting scopes and it can be called from anywhere
4. To support closures, an implementation may need to provide unlimited extent to some variables (because a subprogram may access a nonlocal variable that is normally no longer alive)

Coroutines

• A coroutine is a subprogram that has multiple entries and controls them itself – supported directly in Lua
• Also called symmetric control: caller and called coroutines are on a more equal basis
• A coroutine call is named a resume
• The first resume of a coroutine is to its beginning, but subsequent calls enter at the point just after the last executed statement in the coroutine
• Coroutines repeatedly resume each other, possibly forever
• Coroutines provide quasi-concurrent execution of program units (the coroutines); their execution is interleaved, but not overlapped

Selection Statements

• A selection statement provides the means of choosing between two or more paths of execution
• Two general categories:

1. Two-way selectors
2. Multiple-way selectors

Two-Way Selection Statements

• General form:

if control_expression

then clause

else clause

• Design Issues:

1. What is the form and type of the control expression?
2. How are the then and else clauses specified?
3. How should the meaning of nested selectors be specified?

Iterative Statements

• The repeated execution of a statement or compound statement is accomplished either by iteration or recursion
• General design issues for iteration control statements:

1. How is iteration controlled?
2. Where is the control mechanism in the loop?

Iteration Based on Data Structures

• The number of elements in a data structure controls loop iteration
• Control mechanism is a call to an iterator function that returns the next element in some chosen order, if there is one; else loop is terminate
• C’s for can be used to build a user-defined iterator:

  for (p=root; p==NULL; traverse(p)){

…

}

• PHP

1.   current points at one element of the array
2.   next moves current to the next element
3.   reset moves current to the first element

• Java 5.0 (uses for, although it is called foreach)

For arrays and any other class that implements the Iterable interface, e.g., ArrayList

for (String myElement : myList) { … }

Introduction

• Expressions are the fundamental means of specifying computations in a programming language
• To understand expression evaluation, need to be familiar with the orders of operator and operand evaluation
• Essence of imperative languages is dominant role of assignment statements

Arithmetic Expressions

• Arithmetic evaluation was one of the motivations for the development of the first programming languages
• Arithmetic expressions consist of operators, operands, parentheses, and function calls

Overloaded Operators

• Use of an operator for more than one purpose is called operator overloading
• Some are common (e.g., + for int and float)
• Some are potential trouble (e.g., * in C and C++)

1. Loss of compiler error detection (omission of an operand should be a detectable error)
2. Some loss of readability

• C++, C#, and F# allow user-defined overloaded operators

1. When sensibly used, such operators can be an aid to readability (avoid method calls, expressions appear natural)
2. Potential problems:

• Users can define nonsense operations
• Readability may suffer, even when the operators make sense

Type Conversions

• A narrowing conversion is one that converts an object to a type that cannot include all of the values of the original type e.g., float to int
• A widening conversion is one in which an object is converted to a type that can include at least approximations to all of the values of the original type e.g., int to float

Relational and Boolean Expressions

• Relational Expressions

1. Use relational operators and operands of various types
2. Evaluate to some Boolean representation
3. Operator symbols used vary somewhat among languages (!=, /=, ~=, .NE., <>, #)

• JavaScript and PHP have two additional relational operator, === and !==

1. Similar to their cousins, == and !=, except that they do not coerce their operands
2. Ruby uses == for equality relation operator that uses coercions and eql? for those that do not

• Boolean Expressions

1. Operands are Boolean and the result is Boolean
2. Example operators

• C89 has no Boolean type–it uses int type with 0 for false and nonzero for true
• One odd characteristic of C’s expressions: a < b < c is a legal expression, but the result is not what you might expect:

1. Left operator is evaluated, producing 0 or 1
2. The evaluation result is then compared with the third operand (i.e., c)

Short Circuit Evaluation

• An expression in which the result is determined without evaluating all of the operands and/or operators
• Example: (13 * a) * (b / 13 – 1)

If a is zero, there is no need to evaluate (b  /13 – 1)

• Problem with non-short-circuit evaluation

index = 0;

while (index <= length) && (LIST[index] != value)

index++;

When index=length, LIST[index] will cause an indexing problem (assuming LIST is length – 1 long)

• C, C++, and Java: use short-circuit evaluation for the usual Boolean operators (&& and ||), but also provide bitwise Boolean operators that are not short circuit (& and |)
• All logic operators in Ruby, Perl, ML, F#, and Python are short-circuit evaluated
• Ada: programmer can specify either (short-circuit is specified with and then and or else)
• Short-circuit evaluation exposes the potential problem of side effects in expressions
  e.g. (a > b) || (b++ / 3)

Assignment Statements

• The general syntax

<target_var> <assign_operator> <expression>

• The assignment operator

=   Fortran, BASIC, the C-based languages

:=  Ada

• = can be bad when it is overloaded for the relational operator for equality (that’s why the C-based languages use == as the relational operator)

Mixed-Mode Assignment

• Assignment statements can also be mixed-mode
• In Fortran, C, Perl, and C++, any numeric type value can be assigned to any numeric type variable
• In Java and C#, only widening assignment coercions are done
• In Ada, there is no assignment coercion

This session is GSLC

Introduction

• A data type defines a collection of data objects and a set of predefined operations on those objects
• A descriptor is the collection of the attributes of a variable
• An object represents an instance of a user-defined (abstract data) type
• One design issue for all data types: What operations are defined and how are they specified?

Primitive Data Types

• Almost all programming languages provide a set of primitive data types
• Primitive data types: Those not defined in terms of other data types
• Some primitive data types are merely reflections of the hardware
• Others require only a little non-hardware support for their implementation
• Integer
• Floating Point
• Complex
• Decimal
• Boolean
• Character

Character String Types

• Values are sequences of characters
• Design issues:

1. Is it a primitive type or just a special kind of array?
2. Should the length of strings be static or dynamic?

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
• Examples of primitive ordinal types in Java

1. integer
2. char
3. boolean

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.

Associative Arrays

• An associative array is an unordered collection of data elements that are indexed by an equal number of values called keys

User-defined keys must be stored

• Built-in type in Perl, Python, Ruby, and Lua

In Lua, they are supported by tables

Record Types

• A record is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by names
• Design issues:

1. What is the syntactic form of references to the field?
2. Are elliptical references allowed

Tuple Types

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

Python

• Closely related to its lists, but immutable
• Create with a tuple literal

   myTuple = (3, 5.8, ′apple′)

Referenced with subscripts (begin at 1)

Catenation with + and deleted with del

• ML

val myTuple = (3, 5.8, ′apple′);

Access as follows:

#1(myTuple) is the first element

A new tuple type can be defined:

  type intReal = int * real;

• F#

let tup = (3, 5, 7)

let a, b, c = tup  This assigns a tuple to a tuple pattern (a, b, c)

List Types

• Lists in LISP and Scheme are delimited by parentheses and use no commas(A B C D) and (A (B C) D)

• Data and code have the same form

As data, (A B C) is literally what it is

As code, (A B C) is the function A applied to the parameters B and C

• The interpreter needs to know which a list is, so if it is data, we quote it with an apostrophe′(A B C) is data

• List Operations in Scheme

1. CAR returns the first element of its list parameter

(CAR ′(A B C)) returns A

2. CDR returns the remainder of its list parameter after the first element has been removed

(CDR ′(A B C)) returns (B C)

3. CONS puts its first parameter into its second parameter, a list, to make a new list

(CONS ′A (B C)) returns (A B C)

4. LIST returns a new list of its parameters

(LIST ′A ′B ′(C D)) returns (A B (C D))

Unions Types

• A union is a type whose variables are allowed to store different type values at different times during execution
• Design issues

1. Should type checking be required?
2. Should unions be embedded in records?

Pointer and Reference Types

• A pointer type variable has a range of values that consists of memory addresses and a special value, nil
• Provide the power of indirect addressing
• Provide a way to manage dynamic memory
• A pointer can be used to access a location in the area where storage is dynamically created (usually called a heap)

Type Checking

• Generalize the concept of operands and operators to include subprograms and assignments
• Type checking is the activity of ensuring that the operands of an operator are of compatible types
• A compatible type is one that is either legal for the operator, or is allowed under language rules to be implicitly converted, by compiler- generated code, to a legal type

This automatic conversion is called a coercion.

• A type error is the application of an operator to an operand of an inappropriate type
• If all type bindings are static, nearly all type checking can be static
• If type bindings are dynamic, type checking must be dynamic
• A programming language is strongly typed if type errors are always detected
• Advantage of strong typing: allows the detection of the misuses of variables that result in type errors