Unterprogramme

Ein Unterprogramm ist ein benannter Block mit einer Schnittstelle. Diese beschreibt den Datentransport zwischen Aufrufer und Unterprogramm.

Funktion
- liefert Wert
- Aufruf ist Ausdruck
Prozedur
- hat Wirkung, liefert keinen Wert (void)
- Aufruf ist Anweisung

Datenaustausch zw. Aufrufer (caller) und Aufgerufenem (callee): über globalen Speicher

#include <errno.h>
extern int errno;

oder über Parameter.

Datentransport (entspr. Schüsselwörtern in Ada)

in: (Argumente) vom Aufrufer zum Aufgerufenen
out: (Resultate) vom Aufgerufenen zum Aufrufer
in out: in beide Richtungen

pass-by-value (Wert)
copy in/copy out (Wert)
pass-by-reference (Verweis)
pass-by-name (textuelle Substitution)
selten ...Algol68, CPP-Macros ...Vorsicht!

häufig benutzte Implementierungen:

Pascal: by-value (default) oder by-reference (VAR)
C: by-value (Verweise ggf. selbst herstellen)
C++ unterscheidet zwischen Zeigern (*, wie in C) und Referenzen (&, verweisen immer auf die gleiche Stelle, werden automatisch dereferenziert)
Java: primitive Typen und Referenz-Typen (= Verweise auf Objekte) by-value
C#: primitive Typen und struct by-value, Objekte by-reference, Schlüsselwort ref
Scala: by-value oder by-name

by value:

static void u (int x) { x = x + 1; }
int y = 3 ; u (y); 
Console.WriteLine(y); // 3

by reference:

static void u (ref int x) { x = x + 1; }
int y = 3 ; u (ref y); 
Console.WriteLine(y); // 4

Übung: ref/kein ref; struct (Werttyp)/class (Verweistyp)

class C { public int foo }
static void u (ref C x) { x.foo=4; x=new C{foo=5};}
C y = new C {foo=3} ; C z = y; u (ref y);
Console.WriteLine(y.foo + " " + z.foo);

formaler Parameter wird durch Argument-Ausdruck ersetzt.

Algol(68): Jensen's device

sum (int i, int n; int f) { 
  int s = 0;
  for (i=0; i<n; i++) { s += f; }
  return s;
}
int [10][10] a; int i; sum (i, 10, a[i][i]);

#define thrice(x) 3*x // gefährlich
thrice (4+y)  ==>  3*4+y

``the need for a preprocessor shows omissions in the language''

fehlendes Modulsystem (Header-Includes)
fehlende generische Polymorphie
( ⇒ Templates in C+)

weitere Argumente:

mangelndes Vertrauen in optimierende Compiler (inlining)
bedingte Übersetzung

Parameter-Typ ist => T, entspr. „eine Aktion, die ein T liefert`` (in Haskell: IO T)

call-by-name

def F(b:Boolean,x: =>Int):Int = 
    { if (b) x*x else 0 }
F(false,{print ("foo "); 3})
//     res5: Int = 0
F(true,{print ("foo "); 3})
//    foo foo res6: Int = 9

Man benötigt call-by-name zur Definition von Abstraktionen über den Programmablauf.

Übung: If, While als Scala-Unterprogramm

andere Namen: (call-by-need, lazy evaluation)
Definition: das Argument wird bei seiner ersten Benutzung ausgewertet
wenn es nicht benutzt wird, dann nicht ausgewertet;
wenn mehrfach benutzt, dann nur einmal ausgewertet
das ist der Standard-Auswertungsmodus in Haskell:
alle Funktionen und Konstruktoren sind lazy
da es keine Nebenwirkungen gibt, bemerkt man das zunächst nicht ...
...und kann es ausnutzen beim Rechnen mit unendlichen Datenstrukturen (Streams)

[ error "foo" , 42 ] !! 0 
[ error "foo" , 42 ] !! 1 
length [ error "foo" , 42 ]
let xs = "bar" : xs
take 5 xs

Fibonacci-Folge

fib :: [ Integer ]
fib = 0 : 1 : zipWith (+) fib ( tail fib )

Primzahlen (Sieb des Eratosthenes)

Papier-Falt-Folge

let merge (x:xs) ys = x : merge ys xs
let updown = 0 : 1 : updown
let paper = merge updown paper
take 15 paper

vgl. http://mathworld.wolfram.com/DragonCurve.html

Bedarfsauswertung für eine lokale Konstante (Schlüsselwort lazy)

def F(b:Boolean,x: =>Int):Int = 
    { lazy val y = x; if (b) y*y else 0 }
F(true,{print ("foo "); 3})
//   foo res8: Int = 9
F(false,{print ("foo "); 3})
//   res9: Int = 0

in der Deklaration benutzte Namen heißen (formale) Parameter,
bei Aufruf benutzte Ausdrücke heißen Argumente
(...nicht: aktuelle Parameter, denn engl. actual = dt. tatsächlich)

Designfragen bei Parameterzuordnung:

über Position oder Namen? gemischt?
defaults für fehlende Argumente?
beliebig lange Argumentlisten?

Üblich ist Zuordnung über Position

void p (int height, String name) { ... }
p (8, "foo");

in Ada: Zuordnung über Namen möglich

procedure Paint (height : Float; width : Float);
Paint (width => 30, height => 40);

nach erstem benannten Argument keine positionellen mehr erlaubt

code smell: lange Parameterliste,

refactoring: Parameterobjekt einführen

allerdings fehlt (in Java) benannte Notation für Record-Konstanten.

C++:

void p (int x, int y, int z = 8);
p (3, 4, 5); p (3, 4);

Default-Parameter müssen in Deklaration am Ende der Liste stehen

Ada:

procedure P
    (X : Integer; Y : Integer := 8; Z : Integer);
P (4, Z => 7);

Beim Aufruf nach weggelassenem Argument nur noch benannte Notation

wieso geht das eigentlich:

#include <stdio.h>
char * fmt = really_complicated();
printf (fmt, x, y, z);

Anzahl und Typ der weiteren Argumente werden überhaupt nicht geprüft:

extern int printf 
    (__const char *__restrict __format, ...);

static void check (String x, int ... ys) {
    for (int y : ys) { System.out.println (y); }
}

check ("foo",1,2); check ("bar",1,2,3,4);

letzter formaler Parameter kann für beliebig viele des gleichen Typs stehen.

tatsächlich gilt int [] ys,

das ergibt leider Probleme bei generischen Typen

Erklären Sie den Unterschied zwischen (Ada)

with Ada.Text_IO; use Ada.Text_IO;
procedure Check is
   procedure Sub (X: in out Integer;
                  Y: in out Integer;
                  Z: in out Integer) is
   begin
      Y := 8; Z := X;
   end;
   Foo: Integer := 9;   Bar: Integer := 7;
begin
   Sub (Foo,Foo,Bar);
   Put_Line (Integer'Image(Foo));
   Put_Line (Integer'Image(Bar));
end Check;

(in Datei Check.adb schreiben, kompilieren mit gnatmake Check.adb)

und (C++)

#include <iostream>

void sub (int & x, int & y, int & z) {
  y = 8;
  z = x;
}

int main () {
   int foo = 9;
   int bar = 7;

   sub (foo,foo,bar);
   std::cout << foo << std::endl;
   std::cout << bar << std::endl;
}

Durch welchen Aufruf kann man diese beiden Unterprogramme semantisch voneinander unterscheiden:

Funktion (C++): (call by reference)

void swap (int & x, int & y) 
   { int h = x; x = y; y = h; }

Makro (C): (call by name)

#define swap(x, y) \ 
   { int h = x; x = y; y = h; }

Kann man jedes der beiden von copy-in/copy-out unterscheiden?

Unterprogramme sind wichtiges Mittel zur Abstraktion, das möchte man überall einsetzen
also sind auch lokale Unterprogramme wünschenswert
(Konzepte Block und Unterprogramm sollen orthogonal sein)

int f (int x) {
  int g (int y) { return y + 1; }
  return g (g (x));
}

Zugriff auf nichtlokale Variablen? (Bsp: Zugriff auf X in F)

with Ada.Text_Io; use Ada.Text_Io;
procedure Nest is
   X : Integer := 4;
   function F (Y: Integer) return Integer is
   begin return X + Y; end F;
   function G (X : Integer) return Integer is
   begin return F(3 * X); end G;
begin Put_Line (Integer'Image (G(5)));
end Nest;

statische Sichtbarkeit: textuell umgebender Block
(Pascal, Ada, Scheme-LISP, Haskell ...)
dynamische Sichtbarkeit: Aufruf-Reihenfolge
((Common-LISP), (Perl))

Während ein Unterprogramm rechnet, stehen seine lokalen Daten in einem Aktivationsverbund (Frame).

Jeder Frame hat zwei Vorgänger:

dynamischer Vorgänger:
(Frame des aufrufenden UP) benutzt zum Rückkehren
statischer Vorgänger
(Frame des textuell umgebenden UP)
benutzt zum Zugriff auf ``fremde'' lokale Variablen

Jeder Variablenzugriff hat Index-Paar (i, j) :

im i -ten statischen Vorgänger der Eintrag Nr. j

lokale Variablen des aktuellen UP: Index (0, j)

with Ada.Text_Io; use Ada.Text_Io;
procedure Nested is
 function F (X: Integer; Y: Integer) 
 return Integer is
  function G (Y: Integer) return Integer is
  begin
   if (Y > 0) then return 1 + G(Y-1);
   else return X; end if;
  end G;
 begin return G (Y); end F;
begin
 Put_Line (Integer'Image (F(3,2)));
end Nested;

Entwurfs-Entscheidung für C:

jedes Unterprogramm ist global

Folgerung:

leichte Implementierung:
- dynamischer Vorgänger = der vorige Frame (auf dem Stack)
- statischer Vorgänger: gibt es nicht
softwaretechnische Nachteile:
globale Abstraktionen machen Programm unübersichtlich.

in C# gibt es lokale Unterprogramme:

int x = 3;
Func <int,int> f = y => x + y;
Console.WriteLine (f(4));

in Java gibt es keine lokalen Unterprogramme, aber innere Klassen, dabei ähnliche Fragen

class C { class D { .. } }

static int d ( Func<int,int> g ) { 
    return g(g(1));              }
static int p (int x) {
    Func<int,int> f = y => x + y;
    return d (f);                }

Betrachte Aufruf p(3) .

Das innere Unterprogramm f muß auf den p -Frame zugreifen, um den richtigen Wert des x zu finden.

Dazu Closure konstruieren: f mit statischem Vorgänger.

Wenn Unterprogramme als Argumente übergeben werden, steht der statische Vorgänger im Stack.

(ansonsten muß man den Vorgänger-Frame auf andere Weise retten, siehe später)

static int x = 3;	
static Func<int,int> s (int y) {
    return z => x + y + z;     
}
static void Main () {
    Func<int,int> p = s(4);
    Console.WriteLine (p(3));  
}

Wenn die von s(4) konstruierte Funktion p aufgerufen wird, dann wird der s -Frame benötigt, steht aber nicht mehr im Stack.

⇒ Die (Frames in den) Closures müssen im Heap verwaltet werden.

int [] x = { 1,0,0,1,0 };
Console.WriteLine 
   (x.Aggregate (0, (a, b) => 2*a + b));

http://code.msdn.microsoft.com/LINQ-Aggregate-Operators-c51b3869

foldl ( \ a b -> 2*a + b) 0 [1,0,0,1,0]

Haskell (http://haskell.org/)

historische Schreibweise: λab.2a + b

(Alonzo Church: The Calculi of Lambda Conversion, 1941)

vgl. Henk Barendregt: The Impact of the Lambda Calculus, 1997, ftp://ftp.cs.ru.nl/pub/CompMath.Found/church.ps

static nested class: dient lediglich zur Gruppierung
```
class C { static class D { .. } .. }
```
nested inner class:
```
class C { class D { .. } .. }
```
jedes D-Objekt hat einen Verweis auf ein C-Objekt ( $\approx$ statische Kette) (bezeichnet durch C.this)
local inner class: ( Zugriff auf lokale Variablen in m
nur, wenn diese final sind. Warum? )
```
class C { void m () { class D { .. } .. } }
```

interface Function<T,R> { R apply(T t); }

bisher (Java ≤ 7):

Function<Integer,Integer> f =
    new Function<Integer,Integer> () { 
        public Integer apply (Integer x) { 
            return x*x; 
    } } ;
System.out.println (f.apply(4));

jetzt (Java 8): verkürzte Notation (Lambda-Ausdruck) für Implementierung funktionaler Interfaces

Function<Integer,Integer> g = x -> x*x;
System.out.println (g.apply(4));

Anwendung u.a. in java.util.stream.Stream<T>

in prozeduralen Sprachen:

falls alle UP global: dynamische Kette reicht
lokale UP: benötigt auch statische Kette
lokale UP as Daten: benötigt Closures
= (Code, statischer Link)
UP als Argumente: Closures auf Stack
UP als Resultate: Closures im Heap

in objektorientierten Sprachen: ähnliche Überlegungen bei lokalen (inner, nested) Klassen.

2015-08-17