Organization of Programming Languages

Tests should be ready by Tuesday
Discuss topics from Chapter 16

• classes
• prototypes
• inheritance
• encapsulation
• polymorphism

Another view, from Wikipedia entry fro Object Oriented, http://en.wikipedia.org/wiki/Object_oriented#Fundamental_features_and_concepts

“Benjamin C. Pierce and some other researchers view as futile any attempt to distill OOP to a minimal set of features. He nonetheless identifies fundamental features that support the OOP programming style in most object-oriented languages:^[14]

• Dynamic dispatch – when a method is invoked on an object, the object itself determines what code gets executed by looking up the method at run time in a table associated with the object. This feature distinguishes an object from an abstract data type (or module), which has a fixed (static) implementation of the operations for all instances. It is a programming methodology that gives modular component development while at the same time being very efficient.
• Encapsulation (or multi-methods, in which case the state is kept separate)
• Subtype polymorphism
• Object inheritance (or delegation)
• Open recursion – a special variable (syntactically it may be a keyword), usually called this or self, that allows a method body to invoke another method body of the same object. This variable is late-bound; it allows a method defined in one class to invoke another method that is defined later, in some subclass thereof.”

Two examples  of dynamic dispatch

• 5.24.5.Dynamic Method Dispatch
• Polymorphism in Object-Oriented Languages

What are desirable characteristics of a programming language?

Java Tutorial on Exceptions.

Videos:

• Need for Exception Handling in Java

• Java Tutorial – 21 – Exception Handling

A few examples of exception handling

• Excep13.java
• Excep14.java
• ExceptionTest0.java
• ExceptionTest2.java

Handout with exception examples.

For next class:

• Read Chapter 17 of the text,
• Read “Lisp: Good News, Bad News, How to Win Big“,  Richard P. Gabriel, 1991

Chapter 14. Memory management

• Webber’s PowerPoint
• Chapter 14: Memory Management  (Start with Slide 34)
• Source code for this chapter
• A Java stack manager: StackManager.java
• A Java heap manager with no coalescing: HeapManager.java
• A Java heap manager with coalescing: HeapManager.java (Go through this as an example.)
• Fragments of a Java heap manager with quick lists: allocate, deallocate, and QuickHeapManager

A programming assignment – Due March 22.

Do exercises 1 and 2 on pages 265-267 of the text.

Chapter 15

Consider two related techniques in Java

• using interfaces
  • involves only polymorphism
  • Java tutorial: interfaces
• extending classes
  • involves polymorphism and inheritance
  • Java tutorial: inheritance

Chapter 12 – Memory Locations for Variables

Activation records – see pages 186, 188-193 (PowerPoint starting with Slide 24)

Now consider dealing with nested functions.

Take a look at how this is handled in Quicksort,

See diagram on page 196 (PowerPoint starting with Slide 32)

Rules on page 196

1. When calling a top-level function, set the nesting link for the called function to NULL
2. When calling from a top-level function to a nested function, set the nesting link to the address of the caller’s activation record.
3. When calling from a nested function to a nested function, set the nesting link for the called activation the same as the caller’s nesting link.

Need to consider functions as parameters.

fun addXToALL (x, theList) =
   let
      fun addX y =
           y + x;
      in
          map addX theList
    end;

we can’t use rule 2 above when we make the call map addX theList, because x is not resolved that way.
We need to view a function value as the implementation along with the nesting link. See pages 199 and 200. (PowerPoint slides 41 – 45)

Long-lived functions

Consider

fun fonToAddX x =
   let
      fun addX y =
           y + x;
      in
         addX
    end;

fun test () =
  let
     val f = funToAddX 3;
  in
     f 5
end;

How do we handle this? See page 201 and 202. (PowerPoint Slide 47 – 53)

If time try exercises 2,3 page 203

We now move the object-oriented paradigm for programming languages. Weber uses Java as an exemplar.

Object-Oriented Programming, defined in Wikipedia

Object-oriented programming (OOP) is a programming paradigm using “objects” – data structures consisting of data fields andmethods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction, encapsulation, messaging, modularity, polymorphism, and inheritance. Many modern programming languages now support OOP.

Since you all now Java we will jump to Chatper 14, Memory Management to get you ready for a programming assignment – Due March 22, 10 days from today.

Do exercises 1 and 2 on pages 265-267 of the text.

For next time, read Can Your Programming Language Do This?
by Joel Spolsky so that you can discuss it in class. Think of two or three questions you have while reading it, write them down, and post them as comments to this blog post.

Notes via power point.

Pages 144 – 147.  Each of these can be done as a one-line solution using  map, foldr, and foldl.

Do as many as you like from exercises 1- 13

Do as many as you like from exercises 14- 25

Understand
fun cubelist L = map (fn x => x*x*x) L;

fun cubesum L = foldr (fn (x,y) => x*x*x + y) 0 L;

Comments about namespaces and scope

fun insertsort [] = []
 | insertsort (x::xs) =
 let fun insert (x, []) = [x]
 | insert (x, y::ys) =
 if x<=y then x::y::ys
 else y::insert(x, ys)
 in insert(x, insertsort xs)
 end;

Trace the program for

val urList = [ 3.0, 5.0,12.78, 1.89, 2.0 + 6.0, 2.0 * hd(urList),  9.0/10.0];

Any polymorphism going on here?

fun appendString(x:'a,s: string, toString:'a-> string) : string
= (toString x) ^ " "^ s;

some examples:

appendString(401, "class", Int.toString)

appendString("three", "twelve", fn(s:string) => s)

Now consider the type IntList defined as

datatype IntList = Nil | Cons of int * IntList;

not bad for a ‘wrapper’ type but we can make this more general

datatype ‘a List = Nil | Cons of   ‘a * ‘a List;

Is this what the author  calls parametric  polymorphism?

Future of Programming Languages. Part I – stop when Tate starts talking about his love affair.

Chapter 9 –  More ML

For next time, read Can Your Programming Language Do This?
by Joel Spolsky so that you can discuss it in class. Think of two or three questions you have while reading it, write them down, and post them as comments to this blog post.

Notes via power point.

Pages 144 – 147.  Each of these can be done as a one-line solution using  map, foldr, and foldl.

Do as many as you like from exercises 1- 13

Do as many as you like from exercises 14- 25

Understand
fun cubelist L = map (fn x => x*x*x) L;

fun cubesum L = foldr (fn (x,y) => x*x*x + y) 0 L;

Comments about namespaces and scope

Chapter 7 topics.

Pattern Matching

• See section 7.5 for  a summary of ML patterns (so far)
• Pattern Matching used in function definitions. Rewrite the functions from the last quiz.

Local Variable definitions
Use let expression

<let-exp> ::= let <definitions> in <expression> end

fun days2ms days =
let
   val hours = days * 24.0
   val minutes = hours * 60.0
   val seconds = minutes * 60.0
in
    seconds * 1000
end;

Take a look at fun halve on page 111

fun halve nil = (nil, nil)
|   halve [a] = ([a], nil)
|   halve (a :: b :: cs) =
      let
        val (x, y) = halve cs
      in
        (a :: x, b :: y)
      end;

Examine halve [42];
halve[41,43];
halve[ 1,45,23,13];

Now look at merge

fun merge (nil, ys) = ys
|   merge (xs, nil) = xs
|   merge (x :: xs, y :: ys) =
      if (x < y) then x :: merge(xs, y :: ys)
else y :: merge(x :: xs, ys);

merge ([13,56], [14, 18, 66])

Finally lets look at mergesort
Chapter 8 Topics
Polymorphism

In computer science, polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions. A function that can evaluate to or be applied to values of different types is known as a polymorphic function. A data type that can appear to be of a generalized type (e.g., a list with elements of arbitrary type) is designated polymorphic data type like the generalized type from which such specializations are made. – from Type Polymorphism,

A function or operator is polymorphic if it has at least two types.

Overloading

For example + in ML, C++, Java

Here’s another

float perimeter( float width, float height ) { return 2*(width + height);}
float perimeter (float  sidea, float sideb, float sidec){ return sidea+sideb+sidec;}

Coercion int i = 23.8 +2; // implicit coercion
explicit coercion.
What coercions are allowed by the language? See pages 122 123.
Ad Hoc Polymorphism

• A function or operator exhibits ad hoc polymorphism if it has at least two but only finitely any types
• Overloading
• Parameter Coercion

Universal polymorphism
A function or operator exhibits universal polymorphism if it has infinitely many types
Parametric Polymorphism
Subtype Polymorphism

Quiz on Chapters 5 and 6.

Answer these questions:

• What is purpose of  type checking?
• When are two types equivalent?
• What does the author mean when he says that a key question for type systems is how much of the representation is exposed?
• Are the types bool and list primitive types in SML?

A few other lectures about types you may want to look at:

• Introduction to the study of Types
  University of Galsgow
• Strong Typing
• Lecture 4: Functional Programming Languages (SML) From Virginia Tech

Pattern matching in ML