Binaer-Codes --> Maschinensprache --> Assembler --> Hochsprachen
Bildung immer größerer Programmteile
function I ( FP1, ..., FPn ): T; B
B Ausdruck mit Wert
Formale Parameter FP1, ..., FPn
B == I:=E return( E )
In := I ( AP1, ..., APn )
AP1, ..., APn
(lambda ( FP1, ..., FPn ) B )
( (lambda ( FP1, ..., FPn ) B ) ( AP1, ..., APn ) )
procedure I ( FP1, ..., FPn ); B
B Kommando/Statement/Block
I ( AP1, ..., APn )
int potenz ( int b, int n ) { ...; return( p ); }
void printString ( String s ) { ...; return; }
FPi:=Wert(APi) FPi darf lokal geändert werden
Ergebnisparameter (Variable): APi:=Wert(FPi) FPi muß geändert werden
Wert-Ergebnisparameter (Variable): FPi:=APi; ...; APi:=Wert(FPi)
FPi == Wert(APi)
Referenzparameter (Variable): FPI == Referenz(APi)
Kopiermechanismen:
void add ( in int a, in int b, out int sum ) { sum = a + b; }
void normalize ( in-out int v ) { v = v/norm(v); }
Definitions Mechanismen:
void add ( const int a, const int b, var int sum ) { sum = a + b; }
void normalize ( var int v ) { v = v/norm(v); }
Was kommt raus ?
void confuse ( var int a, var int b ) { a = 1; a = b + a; }
int i = 4; int j = confuse( i, i );
j ist 2 oder 5 ?
int sqr ( int a ) { return(a*a); }
int p = 2; int q = 5;
int r = sqr( p+q );
1: a=Wert(p+q); d.h. a=Wert(2+5); d.h. a=7; also return(7*7);
2: a='p+q'; d.h. return('p+q'*'p+q'); d.h. return('2+5'*'2+5');
d.h. return(7*7)
Aus Church-Rosser Property folgt 1 entspricht 2. zB Lambda-Kalkül
Bei normalen Programmiersprachen meist nicht erfüllt.
boolean cand ( boolean a, boolean b ) {
if (a) { return(b); } else { return(false); } }
int n = 2; int t = 10;
cand(n>0,t/n>6) -->
strikt: false :: cand(true,false)
normal: false :: if (true) { return(10/2>6); }
else { return(false); }
int n = 0; int t = 10;
cand(n>0,t/n>6) -->
strikt: nicht aufgerufen :: cand(false,error)
normal: false :: if (false) { return(10/2>6); }
else { return(false); }
package I is D end I package body I is body B end I
C++: class I { D } I::F1() B1; ...; I::Fn() Bn;
DEFINITION MODULE sema;
(* Semaphore Definition Module. *)
FROM pthread IMPORT pthread_mutex_t, pthread_cond_t;
CONST rcsid = "$Id: sema.md,v 1.1 1994/10/06 14:15:24 kredel Exp $";
CONST copyright = "Copyright (c) 1993 - 1994 Universitaet Mannheim";
TYPE semaphore = RECORD
s : INTEGER; (* Counter *)
del : INTEGER; (* No. of delayed Pthreads *)
mux : pthread_mutex_t;
pos : pthread_cond_t;
END;
PROCEDURE seminit( VAR sem: semaphore; s: INTEGER );
(*Semaphore initialization. *)
PROCEDURE P( VAR sem: semaphore );
(*Semaphore operation P. *)
PROCEDURE V( VAR sem: semaphore );
(*Semaphore operation V. *)
END sema.
IMPLEMENTATION MODULE sema;
(* Semaphore Implementation Module. *)
FROM pthread IMPORT pthread_mutex_t, pthread_cond_t,
mutexattr_default, condattr_default,
pthread_cond_init, pthread_cond_wait, pthread_cond_broadcast,
pthread_cond_signal,
pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock;
FROM MASERR IMPORT ERROR, severe, fatal;
PROCEDURE seminit( VAR sem: semaphore; s: INTEGER );
(*Semaphore initialization. *)
BEGIN
(*1*) (*initialization of mutex*)
IF pthread_mutex_init(sem.mux,mutexattr_default) < 0 THEN
ERROR(fatal,"seminit: Cannot initialize sem.mux"); END;
(*2*) (*initialization of condition and counters*)
IF pthread_cond_init(sem.pos,condattr_default) < 0 THEN
ERROR(fatal,"seminit: Cannot initialize sem.pos"); END;
IF s >= 0 THEN sem.s:=s ELSE sem.s:=0 END;
sem.del:=0;
(*9*) END seminit;
PROCEDURE P( VAR sem: semaphore );
(*Semaphore operation P. *)
BEGIN
(*1*) (*lock access to sem *)
IF pthread_mutex_lock(sem.mux) < 0 THEN
ERROR(fatal,"P: Cannot lock sem.mux"); END;
(*2*) (*wait until sem.s > 0, then decrement *)
WHILE sem.s <= 0 DO
INC(sem.del);
IF pthread_cond_wait(sem.pos,sem.mux) < 0 THEN
ERROR(fatal,"P: Cannot wait on sem.pos"); END;
DEC(sem.del) END;
DEC(sem.s);
(*3*) (*unlock*)
IF pthread_mutex_unlock(sem.mux) < 0 THEN
ERROR(fatal,"seminit: Cannot unlock sem.mux"); END;
(*9*) END P;
PROCEDURE V( VAR sem: semaphore );
(*Semaphore operation V. *)
BEGIN
(*1*) (*lock access to sem *)
IF pthread_mutex_lock(sem.mux) < 0 THEN
ERROR(fatal,"P: Cannot lock sem.mux"); END;
(*2*) (*increment, then signal sem.s > 0 *) INC(sem.s);
IF sem.del > 0 THEN
IF pthread_cond_signal(sem.pos) < 0 THEN
ERROR(fatal,"P: Cannot signal sem.pos"); END;
END;
(*3*) (*unlock*)
IF pthread_mutex_unlock(sem.mux) < 0 THEN
ERROR(fatal,"seminit: Cannot unlock sem.mux"); END;
(*9*) END V;
END sema.
package tel-buch is
procedure insert ( .. );
procedure lookup ( .. );
end tel-buch;
package body tel-buch is
buch: BuchTyp;
procedure insert ( .. ) is
...
procedure lookup ( .. ) is
...
end tel-buch;
tel-buch.insert(.);
tel-buch.lookup(.);
generic package tel-buch is
procedure insert ( .. );
procedure lookup ( .. );
end tel-buch;
package body tel-buch is
buch: BuchTyp;
procedure insert ( .. ) is
...
procedure lookup ( .. ) is
...
end tel-buch;
package heidelberg is new tel-buch;
package mannheim is new tel-buch;
heidelberg.insert(.);
mannheim.lookup(.);
// semaphore class
#include
#include "TYPES.h"
#include "ERROR.h"
//////////////////////////////////////////////////////////
/// Interface class sema
//////////////////////////////////////////////////////////
class sema {
private:
INTEGER init;
INTEGER s;
INTEGER del;
pthread_mutex_t mux;
pthread_cond_t pos;
public:
sema();
sema(INTEGER);
~sema();
void P();
void V();
};
//////////////////////////////////////////////////////////
/// Implementierung der Methoden class sema
//////////////////////////////////////////////////////////
sema::sema(INTEGER i = 0)
{
if (pthread_mutex_init(&mux, pthread_mutexattr_default) < 0)
{
ERROR(fatal, "sema init: Cannot initialize sem.mux");
}
if (pthread_cond_init(&pos, pthread_condattr_default) < 0)
{
ERROR(fatal, "sema init: Cannot initialize sem.pos");
}
if (i >= 0) {
s = i;
} else {
s = 0;
}
init = s;
del = 0;
}
sema::~sema()
{
if (s != init) { GWRITE( s-init );
ERROR(fatal, "sema destruction: pending operations ");
}
}
void
sema::P()
{
if (pthread_mutex_lock(&mux) < 0) {
ERROR(fatal, "P: Cannot lock sem.mux");
}
while (s <= 0) {
del++;
if (pthread_cond_wait(&pos, &mux) < 0) {
ERROR(fatal, "P: Cannot wait on sem.pos");
}
del--
}
s--;
if (pthread_mutex_unlock(&mux) < 0) {
ERROR(fatal, "seminit: Cannot unlock sem.mux");
}
}
void
sema::V()
{
if (pthread_mutex_lock(&mux) < 0) {
ERROR(fatal, "P: Cannot lock sem.mux");
}
s++;
if (del > 0) {
if (pthread_cond_signal(&pos) < 0) {
ERROR(fatal, "P: Cannot signal sem.pos");
}
}
if (pthread_mutex_unlock(&mux) < 0) {
ERROR(fatal, "seminit: Cannot unlock sem.mux");
}
}
public class sema {
private int init;
private int s;
private int del;
public sema() {
this(0);
}
public sema(int i) {
if (i >=0) { init = i; } else { init = 0; }
s = init; del = 0;
}
protected void finalize() throws Throwable {
if (init != s) { int x = s - init;
System.out.println("sema: " + x +
" pending operations.");
}
super.finalize();
}
public synchronized void P() {
while (s <= 0) {
del++;
try {
this.wait();
} catch (InterruptedException e) {}
del--;
}
s--;
}
public synchronized void V() {
s++;
if (del > 0) { this.notify(); } // Bem *
}
}
Abstrakter Datentyp Definition durch Konstanten, Funktionen und Prozeduren. Mathematische Wertemenge wird indirekt (algorithmisch oder per Gleichungen) definiert.
Beispiel mit ASL (Abstract Specification Language):
data type NAT // natürliche Zahlen
constructors
0: NAT
succ: NAT --> NAT
operations
plus: NAT x NAT --> NAT
times: NAT x NAT --> NAT
equations a,b : NAT
plus(0,a) = a
plus(succ(a),b) = succ(plus(a,b))
times(0,a) = 0
times(succ(0),a) = a
times(succ(a),b) = plus(times(plus(a,b),b)
end NAT
Definition/Spezifikation von NAT
durch eine Menge von Operationen/Funktionen und Gleichungen.
Bedeutung ist die Menge (Klasse) von mathematischen Modellen (Sigma-Algebren), die diese Funktionen und Gleichungen erfüllt.
Beispiel Rationale Zahlen als Paare ganzer Zahlen:{ rat(p,q) : p, q sind Integer }oder richtig
{ rat(p,q) : p, q sind Integer, q > 0, ggt(p,q)=1 }
data type RAT // rationale Zahlen
constructors p, q: INT
0: RAT
1: RAT
rat(p,q): RAT "when (q > 0) and (gcd(p,q) = 1)"
destructors
num: RAT --> INT
senum: RAT --> INT
operations
plus: RAT x RAT --> RAT
times: RAT x RAT --> RAT
equal: RAT x RAT --> BOOL
equations a,b : RAT, p, q: INT
num(rat(p,q)) = p
denum(rat(p,q)) = q
plus(rat(p1,q1),rat(p2,q2)) = rat(p1*q2+p2*q1,q1*q2)
times(rat(p1,q1),rat(p2,q2)) = rat(p1*p2,q1*q2)
equal(rat(p1,q1),rat(p2,q2)) = (p1*q2 == p2*q1)
end RAT
Beispiel rat1 mit zu einfachem Ansatz
public class rat1 extends Object {
private int p, q;
public rat1(int ps, int qs) {
p = ps; q = qs;
}
public int zähler() {
return(p);
}
public int nenner() {
return(q);
}
public static rat1 zero() {
return( new rat1(0,1) );
}
public static rat1 one() {
return( new rat1(1,1) );
}
public String toString() {
return( "rat1("+ p + "," + q + ")" );
}
public boolean equals(rat1 r) {
// strukturelle Gleichheit
return( (p == r.zähler()) && (q == r.nenner()) );
}
public void plus(rat1 r) {
p = p*r.zähler() + r.nenner()*q;
q = q*r.nenner();
}
public void times(rat1 r) {
p = p*r.nenner();
q = q*r.nenner();
}
}
Test Programm
public class rt {
public static void main( String args[] ) {
{
rat1 einz = rat1.one();
rat1 eh = new rat1(1,2);
rat1 dh = new rat1(6,4);
System.out.println(" einz = " + einz);
System.out.println(" eh = " + eh);
System.out.println(" dh = " + dh);
rat1 pl = einz; pl.plus( eh );
System.out.println(" pl = " + pl);
if ( pl.equals(dh) ) {
System.out.println(" 1+1/2 == 6/4 ");
} else {
System.out.println(" 1+1/2 != 6/4 ");
}
}
}
Ausgabe
einz = rat1(1,1) eh = rat1(1,2) dh = rat1(6,4) pl = rat1(3,2) 1+1/2 != 6/4
Aufbau von neuen Datentypen - per Typdefinition in gegebenen Programmiersprachen - nur aus Prädikaten (Logik 1.Stufe) führt zu Problemen.
Typdefinition von neuen Datentypen aus vorhandenen Datentypen bieten nur die Möglichkeiten der Prädikaten Logik. Benötigt werden aber Datentypen, die mathematischen Objekten einsprechen.
Konstruktion per Typdefinition <-->Beispiel rat2
Konstruktion per Implementierung
public class rat2 extends Object {
private int p, q;
private int ggt(int a, int b) {
if (b == 0) { return(a); }
else { return( ggt( b, a % b ) ); }
}
public rat2(int ps, int qs) throws Exception {
if (qs == 0) { throw new Exception(); }
if (qs < 0) { qs=-qs; ps=-ps; }
int g = ggt(ps,qs);
p = ps/g; q = qs/g;
}
public rat2(int ps) {
p = ps; q = 1;
}
public int zähler() {
return(p);
}
public int nenner() {
return(q);
}
public static rat2 zero() {
return( new rat2(0) );
}
public static rat2 one() {
return( new rat2(1) );
}
public String toString() {
return( "rat2("+ p + "," + q + ")" );
}
public boolean equals(rat2 r) {
// mathematische Gleichheit, strukturelle würde reichen
return( (p*r.nenner() == r.zähler()*q) );
}
public void plus(rat2 r) {
int pp = p*r.zähler() + r.nenner()*q;
int qq = q*r.nenner(); // warum ist qq > 0 ?
int g = ggt(pp,qq);
p = pp/g; q = qq/g;
}
public void times(rat2 r) {
int pp = p*r.nenner();
int qq = q*r.nenner();
int g = ggt(pp,qq);
p = pp/g; q = qq/g;
}
}
Test Programm
public class rt {
public static void main( String args[] ) {
{
rat1 einz = rat1.one();
rat1 eh = new rat1(1,2);
rat1 dh = new rat1(6,4);
System.out.println(" einz = " + einz);
System.out.println(" eh = " + eh);
System.out.println(" dh = " + dh);
rat1 pl = einz; pl.plus( eh );
System.out.println(" pl = " + pl);
if ( pl.equals(dh) ) {
System.out.println(" 1+1/2 == 6/4 ");
} else {
System.out.println(" 1+1/2 != 6/4 ");
}
}
System.out.println("\n jetzt mit rat2 \n ");
{
rat2 einz = rat2.one();
rat2 eh =null;
rat2 dh =null;
try {
eh = new rat2(1,2);
dh = new rat2(6,4);
} catch (Exception e) { }
System.out.println(" einz = " + einz);
System.out.println(" eh = " + eh);
System.out.println(" dh = " + dh);
rat2 pl = einz; pl.plus( eh );
System.out.println(" pl = " + pl);
if ( pl.equals(dh) ) {
System.out.println(" 1+1/2 == 6/4 ");
} else {
System.out.println(" 1+1/2 != 6/4 ");
}
}
try {
System.out.println("\n 10/5 = " + new rat2(10,5) + "\n");
System.out.println("\n 10/6 = " + new rat2(10,6) + "\n");
} catch (Exception e) { }
}
}
Ausgabe
einz = rat1(1,1) eh = rat1(1,2) dh = rat1(6,4) pl = rat1(3,2) 1+1/2 != 6/4 jetzt mit rat2 einz = rat2(1,1) eh = rat2(1,2) dh = rat2(3,2) pl = rat2(3,2) 1+1/2 == 6/4 10/5 = rat2(2,1) 10/6 = rat2(5,3)
generic
size: in Integer;
package tel-buch is
procedure insert ( .. );
procedure lookup ( .. );
end tel-buch;
package heidelberg is new tel-buch (100000);
package mannheim is new tel-buch (200000);
oder mit Typen
generic
size: in Integer;
type Art ist private;
type Key ist private;
package verzeichnis is
procedure insert ( n: in Art );
procedure lookup ( k: in Key, e out Art );
end tel-buch;
package heidelberg is new verzeichnis (100000, Adressen, String);
package sammlung is new verzeichnis (200, CD-Beschreibung, Nummer);
template<class T> class channel {
private:
T buffer[asyncmsg_maxbuf];
INTEGER front, rear;
pthread_mutex_t s_mux, r_mux;
sema *empty;
sema *full;
public:
channel();
~channel();
void send(T);
void receive(T*);
};
template<class T> channel<T>::channel()
{
if (pthread_mutex_init(&s_mux,
pthread_mutexattr_default) < 0)
{
ERROR(severe, "Cannot initialize s_mux.");
}
if (pthread_mutex_init(&r_mux,
pthread_mutexattr_default) < 0)
{
ERROR(severe, "Cannot initialize r_mux.");
}
front = 0; rear = 0;
empty = new sema((INTEGER)asyncmsg_maxbuf);
full = new sema((INTEGER)0);
}
template<class T> void channel<T>::send(T v)
{
empty->P();
if (pthread_mutex_lock(&s_mux) < 0) {
ERROR(severe, "send: Cannot lock s_mux.");
}
buffer[rear] = v;
rear++;
if (rear >= asyncmsg_maxbuf) {
rear = 0;
}
if (pthread_mutex_unlock(&s_mux) < 0) {
ERROR(severe, "send: Cannot unlock s_mux.");
}
full->V();
}
template<class T> void channel<T>::receive(T* v)
{
(*full).P();
if (pthread_mutex_lock(&r_mux) < 0) {
ERROR(severe, "receive: Cannot lock r_mux.");
}
*v = buffer[front];
buffer[front] = 0;
front++;
if (front >= asyncmsg_maxbuf) {
front = 0;
}
if (pthread_mutex_unlock(&r_mux) < 0) {
ERROR(severe, "receive: Cannot unlock r_mux.");
}
(*empty).V();
}
Verwendung:
channel<LONGINT> work;
public class Channel extends Object {
private Object[] buffer;
private int size;
private int front;
private int rear;
private sema empty;
private sema full;
private Object snd;
private Object rcv;
public Channel(int init) {
buffer = new Object[init];
size = init;
front = 0;
rear = 0;
empty = new sema(init);
full = new sema(0);
snd = new Object();
rcv = new Object();
}
public void send(Object v) {
empty.P();
synchronized (snd) {
buffer[ rear ] = v;
rear++; if (rear >= size) rear -= size;
}
full.V();
}
public Object receive() {
Object v;
full.P();
synchronized (rcv) {
v = buffer[ front ];
front++; if (front >= size) front -= size;
}
empty.V();
return v;
}
}
Deklaration:
public Channel chan = new Channel(100);
Verwendung von send:
BigInteger v, z;
v = new BigInteger("1");
z = new BigInteger("10");
for(int i=0; i<l; i++) {
v = v.multiply(z);
chan.send(v);
}
Verwendung von recieve:
BigInteger v = new BigInteger("0");
for(int i=0; i<l; i++) {
x = chan.receive();
if (x instanceof BigInteger) {
v = (BigInteger)x;
} else {
System.out.println(
"Non BigInteger received."
+ x);
}
}
manchmal auch "ad-hoc" Polymorphie
Zum Beispiel sind arithmetische Operatoren meist überladen.
int operator "-" (int)
int operator "-" (int,int)
float operator "-" (float)
float operator "-" (float,float)
Problem falls nicht eindeutig
int operator "/" (int,int) 7/2 = 3
float operator "/" (float,float) 7.0/2.0 = 3.5
float operator "/" (int,int) 7/2 = 3.5
Lösung durch weglassen von 3. und expliziter Typanpassung
((float)7)/((float)2) = 3.5
Betrachte:
T1 operator I (S1) f1: S1 --> T1
T2 operator I (S2) f2: S2 --> T2
Kontext-unabhängiges Überladen: nicht erlaubt, falls S1 gleich S2
Kontext-abhängiges Überladen: erlaubt, falls S1 gleich S2, aber T1 ungleich T2
ist problematisch
T id(T x) { return(x); }
T2 second(T1 x, T2 y) { return(y); }
Identitätsfunktion 'id' funktioniert für alle Typen, ebenso wie 'second'.
oder auch
T power(T x, int n) {
if (n=1) { return(x); }
else { return( times(x,power(x,n-1)) ); }
}
Funktioniert für alle Datentypen T, die eine Muliplikation
T times(T,T) haben und für alle n >= 1.
Ist in Reinform nur in Funktionalen Programmiersprachen zu finden.
In Java existieren sogenannte 'Abstrakte Klassen' die solche Teilimplementierungen enthalten dürfen.
Zum Beispiel
public abstract class WP {
WP val;
public WP power(int n) {
if (n=1) { return(val); }
else { return( times(val,power(val,n-1)) ); }
}
public abstract WP times(WP x);
}
Benutzung (für extends siehe nächsten Abschnitt)
public class WT extends WP {
public WT times(WT a) {
// implementierung
}
}
Instanzierung
WT b = new WT(.);
WT p = b.power(7);
dabei wird die Implementierung von WP benutzt.
Schnittstellen
public interface Rank {
public int compare(Rank other);
}
Verwendung
public class Ranked extends xy implements Rank {
public int compare(Rank other) {
// implementierung
}
}
subtype Natural is Integer range 0..Integer'last;
subtype Digit is Natural range 0..9;
subtype Small is Integer range -3..3;
public class Shape {
point x, y; // origin
public Shape(point a, point b) { x=a; y=b; }
public point getx() { return(x); }
public point gety() { return(y); }
public void moveto(point a, point b) { x=a; y=b; }
}
public class Circle extends Shape {
length r; // radius
public Circle(point a, point b, length c) {
super(a,b); r=c;
}
public void area() { return( Pi*r*r ); }
}
public class Rectangle extends Shape {
length h, w; // heigth, width
public Rectangle(point a, point b, length c, length d) {
super(a,b); h=c; w=d;
}
public void area() { return( h*w ); }
}
Typcasts:
Shape s = new Shape(3,4);
Circle c = new Circle(4,5,9);
Rectangle r = new Rectangle(2,3,5,9);
s = (Shape)c; // erlaubt
r = (Shape)c; // nicht erlaubt
s = (Shape)c;
Circle cc = (Circle)s; // erlaubt
s = (Shape)r;
Circle cc = (Circle)s; // nicht erlaubt
Eine als public deklarierte Klasse ist in allen Packages zugreifbar. Auf eine nicht public Klasse kann nur innerhalb des selben Package zugegriffen werden.
Zur Verdeutlichung der Konzepte betrachten wir folgende Beispiele.
public class A {
public int pb;
protected int pt;
private int pv;
/*default*/ int df;
}
public class B extends A {
A a = new A(); /* 1 */
}
public class C {
A a = new A(); /* 2 */
}
An der Stelle 1 gilt folgendes:
pb, pt, df sowie a.pb, a.pt, a.df
sichtbar
pb, pt und a.pb
sichtbar
a.pb, a.pt, a.df
sichtbar
a.pb
sichtbar
Auf public Felder (Variablen oder Methoden) kann in allen Packages und Subklassen zugegriffen werden, solange die Klasse selbst zugreifbar ist. Auf protected Felder kann in Subklassen der Klasse und in allen Klassen im gleichen Package zugegriffen werden. private Felder sind dagegen nur in derselben Klasse zugreifbar.