Lecture No.3 - PLD

Lecture No.3 - PLD

Structuring the Data

Definition of DT, ADT

Built-in / primitive types

Structured / composite types - aggregates

Homogeneous / heterogeneous types

Type constructor

Accessing the elements / components of an aggregate

Categories of aggregates

1.Finite mappings / arrays

2.Structures / Cartesian product

3.Sequence, Recursive structures

4.Unions and discriminated unions

UNIONS

C

typedef union {short int offset;

long unsigned int absolute; } address;

typedef enum {abs, rel} descriptor ;

typedef struct

{address location;

descriptor kind;} safe_address;

DISCRIMINATED UNIONS

Scheme

(define-datatype bintree bintree?

(leaf(datumnumber?))

(node(key symbol?)

(left bintree?)

(right bintree?)))

(define tree_a (node a (leaf 2) (leaf 3))

(define tree_b (node b (leaf –5) tree_a))

VERSION 1

typedef struct {char key;

union tree * left, * right;} intnode;

typedef union {int leaf_node;

intnode int_node; } tree;

VERSION 2 – not identical but probably more natural

typedef union {int leaf;

char intnode;} node_type;

typedef struct {node_type key;

struct tree1 *left, *right;} tree1;

Abstract Data Types

C

class Stack {

public:

Stack(int sz) {top=s=new int [size=sz];}

~Stack(){delete[] s;}

void push(int el){*top++=el;}

int pop(){return *--top;}

int length(){return top - s;}

private:

int size;

int *top;

int *s;

};

void foo() {

Stack int_stack(30);

………

int_stack.push(9);

}

Generic ADTs

template <class T> class Stack {

public:

Stack(int sz) {top=s=new T [size=sz];}

~Stack(){delete[] s;}

void push(T el){*top++=el;}

T pop(){return *--top;}

int length(){return top - s;}

private:

int size;

T *top;

T *s;

};

void foo() {

Stack<int> int_stack(30);

……

int_stack.push(9);

}

ADT in Lisp – is generic?

(defun resetstack (stack)

(setf stack nil))

(defun emptystack (stack)

(null stack))

(defun push (x list)

(setf list (cons x list)))

(defun pop (stack)

(if (null stack) (error “Empty stack)

(let ((result (first list)))

(setf list (rest list))

result)))

ADT queue inScheme

(define create-queue

(lambda ()

(let ((q-in '())

(q-out '()))

(letrec

((reset-queue

(lambda ()

(set! q-in '())

(set! q-out '())))

(empty-queue?

(lambda ()

(and (null? q-in)

(null? q-out))))

(enqueue

(lambda (x)

(set! q-in (cons x q-in))))

(dequeue

(lambda ()

(if (empty-queue?)

(eopl:error 'dequeue

"Not on an empty queue")

(begin

(if (null? q-out)

(begin

(set! q-out (reverse q-in))

(set! q-in '())))

(let ((ans (car q-out)))

(set! q-out (cdr q-out))

ans))))))

(vector reset-queue empty-queue? enqueue dequeue)))))

(define queue-get-reset-operation

(lambda (q) (vector-ref q 0)))

(define queue-get-empty?-operation

(lambda (q) (vector-ref q 1)))

(define queue-get-enqueue-operation

(lambda (q) (vector-ref q 2)))

(define queue-get-dequeue-operation

(lambda (q) (vector-ref q 3)))

Type Systems

What is a type system?

What is a type safe program (or type secure program)?

Static versus dynamic program checking

Strong typing versus weak typing languages

Type compatibility

type s1 is struct { int y; int w;};

type s2 is struct { int y; int w;};

type s3 is struct {int y;};

s3 func(s1 z) {…}

s1 a, x;s3 c;a = b; x = a; c = func (b); d = func (a);

s2 b;int d;

Type conversions

Coercion = any allowed type conversion applied automatically by the compiler

int x; float z;

x = x + z;x = x + (int) z;

Subtypes

type Int_Vec is array (Integer range >) of integer;

subtypeis Int_Vec (0..99);

Overloading

Generic types

Generic ADTs

Generic routines

C++

template <class T> void swap(&T a, T& b)

{ T temp = a;

a = b;

b = temp;

}

int i,j;float f,g;

swap(i,j);swap(f,g);

Monomorphic versus Polymorphic Systems

Polymorphic features found in most languages:

type compatibility
coercion
overloading

parametric

universal

inclusion

polymorphism

overloading

ad-hoc

coercion