Serialisierung
Proseminar Programmiersysteme
Betreuer: Guido Tack
Benedict Fehringer
Übersicht
• Einführung
• Datengraphen und abstrakter Speicher
• Pickles (Unpickling, Pickling)
• Bsp. in Java und Alice
Einführung
Was meint Serialisierung?
Serialisierung bedeutet, dass ein Datengraph in eine eindimensionale (lineare)-Form gebracht wird, so dass diese eindeutig in den Ursprungs-Datengraph umgewandelt werden kann.
Wozu benötigt man Serialisierung?
• Speichern
• Transferieren
• Compilieren
Umsetzung der Serialisierung in verschiedenen Sprachen
• CLU (eine Sprache, die von Pascal abstammt); (B. Liskov and St. Zilles, 1974)
• JAVA (Roger Riggs, Jim Waldo, Ann Wollrath Sun Microsystems, Inc., 1996), Microsoft`s.NET Framework
• Ruby oder Python
• SML/NJ (A. W. Appel and D. B. MacQueen, 1994), OCaml, Alice
• Mozart/Oz
Datengraphen und abstrakter
Speicher
Bsp. für einen Datengraph
class A
{
public string s;
public int i;
public B b;
}
class B
{
public int j;
public A a;
}
A x = new A ();
B y = new B ();
x.s = „aaa“;
x.i = 24;
x.b = y;
y.j = 45;
y.a = x;
Bsp. für einen Datengraph
Inhalt LabelAdresse
0
1
2
3
4
object x
int
string
object y
int
object x
object y
int „24“
int „45“
string „aaa“
1 | 2 | 3
„24“
„aaa“
0 | 4
„45“
Datengraph (formal)
Ein Datengraph ist eine endliche Funktion g, so dass gilt:
Ran(g) Lab x (Str Dom(g)*)
Abstrakter Speicher
• Spezielle Datenstrukturen benötigen eine spezielle Repräsentation (Zahlen, Strings, Arrays,...) (kann zur Optimierung implementiert werden)
Pickles
Definitionen
Pickle:
- linear - external - „Platform-unabhängige“
Pickling
- Umwandlung eines Datengraphen in einen Pickle
Unpickling
- Umkehrvorgang zum Pickling
Konstruktion/Unpickling von Datengraphen
• Baum
• azyklischer Graph
• zyklischer Graph
Baum
a
bc
dc
Instruktion # Nachfolger
d
c
b
a 2
c
0
0
0
2
Baum
a
bc
dc
Instruktion # Nachfolger
d
c
b
a 2
c
0
0
0
2
Azyklischer Graph
Instruktion
a
b
dc
# Nachfolger
c
0
0
2
2
-
-
b
a
d
STORE 0
LOAD 0
Azyklischer Graph
Instruktion
a
b
dc
# Nachfolger
c
0
0
2
2
-
-
b
a
d
STORE 0
LOAD 0
Zyklischer Graph
Instruktion a
b
dc
# Nachfolger
PROMISE 0 a
STORE 1
c 1
-
LOAD 1
2
FULFIL 0
-
2
0
b
d
2
Zyklischer Graph
Instruktion a
b
dc
# Nachfolger
PROMISE 0 a
STORE 1
c 1
-
LOAD 1
2
FULFIL 0
-
2
0
b
d
2
Pickling
• Schritt 1: Datengraph Pickle-Baum
• Schritt 2: Pickle-Baum Postorder-Linearisierung
• Schritt 3: Postorder-Linearisierung Pickle
Schritt 1
a
b
dc
0: a
b
-> 1 d
1: c
-> 0
Datengraph Pickle-Baum
Schritt 2
0: a
b
-> 1 d
1: c
-> 0
Knoten # Nachfolger
1:c
-> 0
d
-> 1
b
0:a
-
1
-
0
2
2
Pickle-Baum Postorder-Linearisierung
Schritt 3
Knoten # Nachfolger
-> 0
1:c
-> 1
d
b
0:a
-
1
-
0
2
2
Knoten # Nachfolger
PROMISE 0 a
c
STORE 1
LOAD 1
d
b
FULFIL 0
2
1
-
-
0
2
2
Postorder-Linearisierung Bottom-up-Pickle
Top-Down-Pickles
• Präorder statt Postorder Top-Down Pickle
• Kein Promise/Fulfill nötig
Verschiedene Darstellungen eines Pickle-Bäume
0: a
b
-> 1d
1: c
-> 0
0: a
b-> 1
d1: c
-> 0
=
Implementier-Details
• Depth First Search (Graph Pickle-Baum Pickle)
• Bestimmung der maximalen Stack-Höhe
Realisierung in JAVA und Alice
JAVA-Objekt-Modell
• Klassen
• Objekte
• Felder
• Methoden
• ...
Pickling in Java
• Objekte können serialisiert werden
• Top-Down-Mechanismus
• Pruning
Bsp. für Pickling in Java
import java.io.Serializable;public class A implements Serializable{public int i;public string s; }
Bsp. für Pickling in Java
10 public class FlattenA20 {30 public static void main(String [] args)40 {50 A a = new A();60 FileOutputStream fos = new FileOutputStream(“aa.ser");70 ObjectOutputStream out = new ObjectOutputStream(fos);80 out.writeObject(a);90 out.close();100 }110 }
Bsp. für Pickling in Java10 public class InflateA20 {30 public static void main(String [] args)40 {50 A a = null;60 FileInputStream fis = null;70 ObjectInputStream in = null;80 try90 {100 fis = new FileInputStream(“aa.ser");110 in = new ObjectInputStream(fis);120 a = (A)in.readObject();130 in.close();140 }150 catch(IOException ex) { ERROR!!!}160 catch(ClassNotFoundException ex) { ERROR!!! }170 }180 }
Pruning
• der Programmierer kann selbst entscheiden, welcher Teil gepickelt werden soll und welcher nicht.
• Die nicht zu Pickelndeln Teile müssen markiert werden
Bsp. für Pickling in Java
import java.io.Serializable;public class A implements Serializable{transient public int i;public string s; }
Pickling in Alice
• Pickling beliebiger Daten
• Typsicherheit
• Anwendung: z.B. Komponentensystem / Compiler
Bsp. für Pickling in Alicesignature NUM =sig type t fun fromInt : int -> t fun toInt : t -> int fun add : t * t -> tendstructure Num :> NUM =struct type t = int fun toInt n = n fun fromInt n = n val add = op+end
Bsp. für Pickling in Alice
Pickling:
Pickle.save: string * package -> unit
Pickle.save ("Num." ^ Pickle.extension, pack Num :> NUM)
Unpickling:
Pickle.load: string -> package
structure Num' = unpack Pickle.load ("Num." ^ Pickle.extension) : NUM
Bsp. für Pickling in Alice
Achtung!
Num'.add (Num.fromInt 4, Num.fromInt 5)1.0-1.39: argument type mismatch: t * tdoes not match argument type Num'.t * Num'.tbecause type Num.tdoes not unify with Num'.t
Literaturverzeichnis
• Guido Tack, Linearisation, Minimisation and Transformation of Data Graphs with Transients. Diplomarbeit, Saarbrücken, Mai 2003
• Roger Riggs, Jim Waldo, Ann Wollrath Sun Microsystems, Inc., Pickling State in the Java™ System, Toronto, Ontario, Canada, June 1996
• Java Object Serialization Specification. Available from http://java.sun.com/j2se/1.4/docs/guide/serialization/, 2001.
• The Alice Project. Available from http://www.ps.uni-sb.de/alice, 2003. Homepage at the Programming Systems Lab, Universität des Saarlandes, Saarbrücken.