Martin Sulzmann
// Woche 3
package main
import "fmt"
func hello3(x int) func() {
return func() { fmt.Printf("Hello %d \n", x) }
}
func testHello() {
// Verschiedenen Anwendungsformen
// 1. Partielle Funktionsanwendung
var f func()
f = hello3(3)
f()
// 2.
h := hello3(3)
h()
// 3.
(hello3(2))()
// ^^^^^^^^^^
// ist eine Funktion welche direkt aufgerufen wird
// 4. Funktionsanwendung ist links-assoziativ
hello3(2)()
}
// Addieren
func add(x int) func(int) int {
return func(y int) int { return x + y }
}
func plus(x int, y int) int {
return x + y
}
func testAdd() {
fmt.Printf("%d", plus(3, 4))
fmt.Printf("%d", add(3)(4))
inc := add(1)
fmt.Printf("%d", inc(4))
g := add
fmt.Printf("%d", g(3)(2))
var f func(int) func(int) int
f = add
fmt.Printf("%d", f(3)(2))
}
func main() {
// testHello()
testAdd()
}
/*
Frage aus der Vorlesung.
Wäre folgende Syntax gültig: curry(f func(int, int) int) func(int)(int) int
Nein!
func(int)(int) int
ist syntaktisch nicht legal.
es fehlt "func"
func(int)( func(int) int )
*/package main
import "fmt"
// Example
type rectangle struct {
length int
width int
}
type square struct {
length int
}
func (r rectangle) area() int { // R-area
return r.length * r.width
}
func (s square) area() int { // S-area
return s.length * s.length
}
type shape interface {
area() int
// foo() bool
}
func sumArea(x shape, y shape) int {
return x.area() + y.area()
}
func test() {
var r rectangle = rectangle{1, 2}
var s square = square{3}
x2 := sumArea(r, s) // applied on (rectangle, square)
// sumArea expects arguments of type shape!
// rectangle <= shape because rectangle implements the area method
// see R-area
// (implicit) structural subtyping
x2b := sumArea(r, r) // applied on (rectangle, rectangle)
fmt.Printf("%d %d \n", x2, x2b)
}
func main() {
test()
}package main
// Aussage: ((int => bool) /\ int) => bool
// Dargestellt als Go Typ.
// func (func(int) bool, int) bool
//
func mp(f func(int) bool, x int) bool {
return f(x)
}
// Was waere wenn ...
/*
Wir betrachten hier dependent types.
Typen sind "dependent" von Werten.
Dadurch koennen wir schaerfere/genauere Aussagen treffen (= Typen spezifizieren).
forall n, m != 0. func g(x int(n), y int(m)) int(n/m) {
return x / y
}
*/
func g(x int, y int) int {
return x / y
}
type pair struct {
left interface{}
right interface{}
}
// Interpretiert als:
// Forall T <= any, Forall S <= any.
// any = interface{}
type pairG[T any, S any] struct {
left T
right S
}
// (any,any) => any
// Schwache Aussage, keine Garantie, dass der "linke" Wert zurueckgeliefert wird.
func first(x pair) interface{} {
return 1 // x.left
}
// Forall T, S. (T,S) => T
// Starke Aussage:
// Garantiert, dass wir den linken Wert zurueckliefern.
func firstG[T any, S any](x pairG[T, S]) T {
return x.left
}
type Show interface {
show() string
}
// x und y sind vom Typ Show,
// aber z.B. number <= Show und auch boolean <= Show
// deshalb ist showTwice1 anwender auf (number, boolean),
// sprich Werte vom Typ number und boolean.
func showTwice1(x Show, y Show) {
}
// x und y muessen vom gleichen Typ T sein.
// T ist ein Typparameter wobei T <= Show.
// Deshalb ist showTice2 angewandt auf (number, boolean) nicht Typkorrekt.
// Weil T = number und T = boolean, aber number != boolean.
func showTwice2[T Show](x T, y T) {
}
// Effektiv das gleiche (gleiche Aussage) wie showTwice1.
func showTwice3[T Show, S Show](x T, y S) {
}
func main() {
// g(1,0)
}package main
type Show interface {
show() string
}
type pair[T Show, S Show] struct {
left T
right S
}
func (this pair[T,S]) show() string {
return "(" + this.left.show() + "," + this.right.show() + ")"
}
type ppair[T any, S any] struct {
left T
right S
}
/*
// Not OK.
func (this ppair[T Show,S Show]) show() string {
return "(" + this.left.show() + "," + this.right.show() + ")"
}
*/
// OK
func showFunc[T Show,S Show](this ppair[T,S]) string {
return "(" + this.left.show() + "," + this.right.show() + ")"
}
func main() {
}///////////////////////////////
// Ownership + Borrowing
fn example1(x : i32) -> i32 {
let y = x; // Local type inference.
// y = 1; // Variables are immutable by default.
return x+y;
}
fn example2(x : i32) -> i32 {
let mut y = x; // Mutable variables must be declared explicitly.
let z = y;
y = 1;
return x+y+z;
}
/*
fn example3a(x : String) -> String {
// 1. x : String_Owner
let y = x;
// 2. y : String_Owner
// 3. x : String_No_longer_the_owner
// Rust verwendet ein "lineares" Typsystem.
// Ein "move" hat stattgefunden, die Besitzrechte ("ownership") haben sich geaendert.
println!("{}",y); // Zugriff auf y okay, weil "owner"
return x; // Zugriff auf x "not okay", weil "no longer the owner"
}
*/
fn example3(x : String) -> String {
// 1. x : String_Owner
let y = x.clone();
// 2. y : String_Owner
// 3. x : String_Owner
// weil wir einen "clone" angelegt haben
println!("{}",y);
return x;
}
/*
Recap C++.
Wir koennen "=" (Zuweisung) ueberladen und dadurch die Copy Semantik "verstecken".
*/
/*
// Folgendes Beispiel liefert einen Typfehler
struct Rectangle {
x : i32,
y : i32
}
fn example4() {
let p = Rectangle{x : 1, y : 2};
// 1. p : Rectangle_Owner
let q = p;
// 2. q : Rectangle_Owner
// 3. p : Rectangle_No_longer_the_owner
println!("{} {}",q.x, p.x);
}
*/
#[derive(Clone)]
// Magie, wir koennen automatisch die Instanz der "clone" Methode definieren.
struct Rectangle4a {
x : i32,
y : i32
}
fn example4a() {
let p = Rectangle4a{x : 1, y : 2};
// 1. p : Rectangle_Owner
let q = p.clone();
// 2. q : Rectangle_Owner
// 3. p : Rectangle_Owner, jetzt passt es!
// Jeder "owner" besitzt einen verschiedenen Speicherbereich.
println!("{} {}",q.x, p.x);
}
#[derive(Clone,Copy)]
// Magie, wir koennen automatisch die Instanz der "clone" Methode definieren.
// Zusaetzlich, generien wir eine automatisch "copy" Methode, entspricht dem Zuweisungsoperator.
struct Rectangle {
x : i32,
y : i32
}
fn example4() {
let p = Rectangle{x : 1, y : 2};
// 1. p : Rectangle_Owner
let q = p; // entspricht effektiv p.clone(), wir ueberladen die Zuweisungsoperation.
// 2. q : Rectangle_Owner
// 3. p : Rectangle_Onwer, jetzt passt es!
println!("{} {}",q.x, p.x);
}
struct Square {
x : i32
}
fn example5() {
let p = Square{x : 1};
let q = &p;
println!("{} {}",q.x, p.x);
}
fn example6() {
let p = Square{x : 1};
let q = &p;
println!("{} {}",q.x, p.x);
}
/*
fn example7() {
let mut p = Square{x : 1};
// 1. p Square_Owner
let q = &p;
// 2. q Square_Borrowed
// 3. p Square_Owner_Borrowed
p.x = 2; // Typfehler, cannot overwrite a borrowed value!
println!("{} {}",q.x, p.x);
}
*/
fn example8() {
let mut p = Square{x : 1};
// 1. p Square_Owner
{
let q = &p;
// 2. q Square_Borrowed
// 3. p Square_Owner_Borrowed
println!("{} {}",q.x, p.x);
// read access is okay
}
// Ab hier gilt
// 4. p Square_Owner
p.x = 2; // okay, can change the value we are the exclusive owner!
println!("{}",p.x);
}
fn main() {
println!("Hello {} {}", 5, "World!"); // Type of placeholders inferred.
println!("{}", example1(5));
println!("{}", example2(5));
println!("{}", example3(String::from("Hallo")));
example4();
example5();
example6();
example8();
}Rust traits (are predicates to support user-controllable overloading)
Rust dyn traits (are abstract types)
Rust uses the dictionary-translation method for traits
// Traits are not types!
// Traits are predicates!
// Each trait as an (implicit) argument.
// Arguments are types!
// Traits constraint types!
// In Rust, "Self" is the implicit argument for each trait.
/*
it would be much nicer to write
trait Shape(Self) {
fn area(s : &Self) -> i32;
}
We can treat "Self" as a type parameter.
So, it would also be okay to write the following using "Java" notation.
trait Shape(T) {
fn area(s : &T) -> i32;
}
*/
trait Shape {
fn area(s : &Self) -> i32;
}
// For which instances is the Shape predicate valid?
// The user can "implement" a specifc instance.
struct Rectangle {
x : i32,
y : i32
}
// In essence, we specify that Shape(Rectangle) holds!
// "Shape for Rectangle" => we set Self=Rectangle and assume that Shape(Rectangle) holds.
/*
Assuming some alternative syntax. The below corresponds to the following.
impl Shape(Rectangle) {
fn area(s : &Rectangle) -> i32 {
return r.x * r.y;
}
}
*/
// IMPL-RECTANGLE
impl Shape for Rectangle {
fn area(r : &Rectangle) -> i32 {
return r.x * r.y;
}
}
struct Square {
x : i32
}
impl Shape for Square {
fn area(s : &Square) -> i32 {
return s.x * s.x;
}
}
/*
In some alternative Syntax, the below corresponds to the following.
forall A, B. // universelle Typparameter
Shape(A) and Shape(B) // wobei aber gelten muss
=> // dann folgt
fn sum_area(x : &A, y : &B) -> i32
*/
fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
return Shape::area(x) + Shape::area(y);
// ^^^^^^^^^^^^^^
// x is of type &A where Shape(A) holds
// Implies that we have available the
// "area" method.
// Access via "Shape::area",
// cause the same method name may appear
// in different traits.
// In detail, the following is happing at compile-time when
// type checking Shape::area(x)
// 1. Shape::area ==> look up the type declaration
// we find fn area(s : &T) -> i32 where Shape(T) must hold
// 2. Given x : &A where Shape(A) holds.
// 3. We can set T=A and type check
// Shape::area(x) => is of type i32
// 4. The same applies to Shape::area(y).
// Observation.
// We can overload "functions". They are called methods in Rust.
// Overloaded functions are tied to traits.
}
/*
Why is <<A:Shape> "confusing"?
Might look like a type bound.
For instance, in Java notation "<A Shape>".
Makes no sense, cause traits are not types.
In Rust, we need to interpret
<A:Shape>
as the predicate
Shape(A)
*/
fn example9() {
let r = Rectangle{x : 1, y : 2};
let s = Square{x : 3};
println!("{}",sum_area(&r,&s));
// Compiler checks that the function call is type correct.
// 1. r is of type Rectangle.
// 2. Based on sum_area function we must prove:
// Shape(Rectangle) holds.
// 3. This holds because of IMPL-RECTANGLE
// 4. The same applies to "s".
// 5. For each trait instance, we have an implementation.
// For example, for Shape(Rectangle) we have some concrete function area_rec
// 6. Static resolution of "overloaded" method calls.
// 7. area_rec becomes an (implicit) argument of the suma_area function.
// This is nothing else than a variant of the "dictionary-passing translation scheme".
}
fn main() {
example9();
}dyn traits
(are abstract types)struct Square {
x : i32
}
struct Rectangle {
x : i32,
y : i32
}
// Syntactic sugar for "OO" method calls.
// Our to be overloaded "self" parameters occurs in leading position.
// So, instead of "area(arg)" we can write "arg.area()".
trait Shape2 {
fn area2(&self) -> i32;
}
impl Shape2 for Rectangle {
fn area2(&self) -> i32 {
return self.x * self.y;
}
}
impl Shape2 for Square {
fn area2(&self) -> i32 {
return self.x * self.x;
}
}
fn sum_area2<A:Shape2,B:Shape2>(x : &A, y : &B) -> i32 {
return x.area2() + y.area2();
}
fn example10() {
let r = Rectangle{x : 1, y : 2};
let s = Square{x : 3};
println!("{}",sum_area2(&r,&s));
}
// dyn Shape2 refers to an abstract (=existential) type.
// In logic notation:
// dyn Shape2 = exists T. Shape2(T) => T
//
// 1. "exists T" means some type T
// 2. "Shape2(T) =>" means must satisfy the predicate Shape2(T)
//
// For example, Rectangle can also be of type "dyn Shape2",
// but also Square can be of that.
//
// Hence, we do not know the size of "dyn Shape2".
// Must manage such values on the heap.
// In Rust, this means we must "Box" them.
//
fn sum_area3(x : Box<dyn Shape2>, y : Box<dyn Shape2>) -> i32 {
return x.area2() + y.area2();
}
fn example11() {
let r = Box::new(Rectangle{x : 1, y : 2});
let s = Box::new(Square{x : 3});
// Box<Rectangle> is turned into Box<dyn Shape2>.
// 1. We build the dictionary for "Shape2(Rectangle).
// We put the dictionary into the "black box" = abstract value of type "dyn Shape2".
println!("{}",sum_area3(r,s));
}
fn main() {
example10();
}// Dictionary-translation
trait Shape {
fn area(s : &Self) -> i32;
}
struct Rectangle {
x : i32,
y : i32
}
impl Shape for Rectangle {
fn area(r : &Rectangle) -> i32 {
return r.x * r.y;
}
}
// Above implies the following "function" definition.
fn area_rec(r : &Rectangle) -> i32 {
return r.x * r.y;
}
struct Square {
x : i32
}
impl Shape for Square {
fn area(s : &Square) -> i32 {
return s.x * s.x;
}
}
// Above implies the following "function" definition.
fn area_sq(s : &Square) -> i32 {
return s.x * s.x;
}
fn sum_area<A:Shape,B:Shape>(x : &A, y : &B) -> i32 {
return Shape::area(x) + Shape::area(y);
}
// How to translate "sum_area"?
//
// We make "dictionaries" explicit!
// 1. Each predicate is turned into a dictionary.
// 2. Shape(A) represented by m1 : fn(&A) -> i32.
fn sum_area_dict<A,B>(m1 : fn(&A) -> i32, m2 : fn(&B) -> i32, x : &A, y : &B) -> i32 {
return m1(x) + m2(y);
}
fn example9() {
let r = Rectangle{x : 1, y : 2};
let s = Square{x : 3};
println!("{}",sum_area(&r,&s));
// The call
// sum_area(&r,&s)
// translates to
println!("{}",sum_area_dict(area_rec, area_sq, &r, &s));
}
fn main() {
example9();
}// Datentypen
// Primitive, i32, ...
// Arrays, Sequenzen von Werten der gleichen Groesse.
// Benutzer-definierte Strukturen.
// Effektiv Tupel von Werten, assoziiert mit einem Attribut (Feldnamen).
struct Rectangle {
x : i32,
y : i32
}
// In Rust gibt es auch "algebraische" Datentypen (auch Summentypen genannt).
// In Rust genannt "enums".
// Enumerationen aka Aufzaehlungstypen.
// Quasi eine Menge von Werte welchen durch einen Enum Tag identifiziert werden koennen.
// In C++ sind enums nicht's anderes wie eine symbolische Darstellung einer endlichen Menge
// von Integer Werten.
// Enum Tags koennen jetzt auch Argumente haben.
// Deshalben sollten wir diese Art von Enum Tags als "Konstruktoren" bezeichnen.
// In mathematischer Notation.
// data Exp = Int { val : i32 }
// | Bool { val : bool }
// | Plus { left : Exp, right : Exp }
// Das ganze aehnelt Kontext-freien Grammtik Regeln!
// Exp -> int
// Exp -> bool
// Exp -> plus Exp Exp
// D.h. mit einer endlichen Anzahl von Regeln,
// koennen wir eine unendliche Menge von Werten beschreiben.
// Wieso "Box<Exp>"?
// Weil die Speichergroesse eines "enum" Wertes muss statisch (zur Compilezeit) berechenbar sein.
// Beachte.
// 1. Wertemenge Exp ist fix!
// 2. Aber wir koennen beliebig viele Funktionen schreiben welche Exp verwenden, z.B. eval, ...
// Vergleich zu OO in Java.
// 1. Offene Wertemenge, da Klassen erweiterbar (z.B. Int erbt von Exp, ...)
// 2. Aber die Funktionalitaeten sind fixiert in der Basisklasse.
pub enum Exp {
Int {
val: i32
},
/*
// Weiterer Konstruktor.
Bool {
val : bool
},
*/
Plus {
left: Box<Exp>,
right: Box<Exp>
},
Mult{
left: Box<Exp>,
right: Box<Exp>
},
}
fn eval(e : &Exp) -> i32 {
match e {
Exp::Int { val } => return *val,
Exp::Int { val : 0 } => return 0, // this case never applies, warning!!!
Exp::Plus { left, right } => return eval(left) + eval(right),
Exp::Mult { left, right } => return eval(left) * eval(right),
}
}
fn eval2(e : &Exp) -> i32 {
match e {
Exp::Int { val } => return *val,
Exp::Plus { left, right } => return eval(left) + eval(right),
Exp::Mult { left, right } =>
match **left {
Exp::Int{val : 0} => return 0,
-- "nested pattern", erst matchen wir gegen "Int" und dann gegen "0".
_ => return eval(left) * eval(right)
}
}
}
fn main() {
}{-
*Main> :t example1
example1 :: Num a => a -> a
-}
example1 :: Num a => a -> a
example1 x = let y = x
in x + y
{-
Haskell hat maechtiges Ueberladungskonzept.
Arithemtische Operatoren sind ueberladen!
"Num a" ist eine Typklassen (siehe traits in Rust).
Betrachte: example1 :: Num a => a -> a
example1 ist vom Funktionstyp
a -> a
fuer ein belieges a, solange der Typ a den Typconstraint "Num a" erfuellt.
-}
example3 :: String -> String
example3 x = let y = x ++ "Hallo"
in y
example4 :: String -> IO String
example4 x = do let y = x ++ "Hallo"
z <- getLine
print (y++z)
return y
example4_1 :: String -> IO String
example4_1 x =
do let y = x ++ "Hallo"
let z = "C"
print (y++z)
return y
{-
Beachte. Typen beschreiben, ob Funktionen einen Seiteneffekt haben oder nicht!
Betrachte.
example3 :: String -> String
Ist eine "pure" Funktion.
Eingabe vom Typ String, liefert einen Wert vom Typ String.
example4 :: String -> IO String
Funktion mit Seiteneffekt.
Betrachte
IO String
Muss man wie folgt interpretieren.
- Der eigentliche Rueckgabewert ist vom Typ String.
- Dieser Wert wurde berechnet, wobei Seiteneffekt auftreten koennen.
- "IO" beschreibt alle Seiteneffekte die alle etwas mit
Input, Output, Zustand, ... zu tun.
IO ist ein Typkonstruktor.
Argumente sind Type (welche die eigentliche Berechung beschreiben).
-}
example4b :: String -> IO String
example4b x =
let y = x ++ "Hallo"
in do { z <- getLine;
print (y++z);
return z }
plus3 = \x -> \y -> x + y
{-
In Go Notation.
plus3 := func(x int) func(int) int {
return func(y int) int {
return x + y
}
}
Wir eliminieren all Go Typen
plus3 := func(x) {
return func(y) {
return x + y
}
}
Entspricht in Haskell dem folgenden Ausdruck
\x -> (
\y -> (
x + y
)
)
-}
data Maybe a = Just a | Nothing
data List a = Nil | Cons a (List a) deriving Show
{-
Der Compiler verwandelt obiges in eine verkette Lists.
Mit zwei "enums".
1. Fall, leere Liste
2. Fall, nicht-leere Liste, mit einem Element und einer "Referenz" auf eine weitere Liste!
-}
{-
"Show a" is eine Typklasse mit folgender show :: a -> String Methode
show konvertierte die interne Darstellung in einen String
mit Hilfe von "deriving" wird die Instanz "Show (List a)" automatisch generiert.
-}
{-
Oder eine "custom-specific" Instanz selber gebaut.
instance Show a => Show (List a) where
show Nil = "[]"
show (Cons x xs) = go ("[" ++ show x) xs
where
go s Nil = s ++ "]"
go s (Cons x xs) = go (s ++ "," ++ show x) xs
-}
list1 = Cons 1 (Cons (1+1) Nil)
-- hd (tl list1) liefert 2
{-
aber
list1
<interactive>:39:1: error:
• No instance for (Show (List Integer))
arising from a use of ‘print’
• In a stmt of an interactive GHCi command: print it
Interpretation der Fehlermeldung.
Zur Darstellung des Ergebniswertes,
muss dieser Wert in einen String konvertiert.
D.h. die interne Maschinendarstellung muss in einen String konvertiert werden.
Fuer primitive Datentypen (Int, Bool, ...) ist dies schon vordefiniert.
-}
hd :: List a -> a
hd (Cons x _) = x
tl :: List a -> List a
tl (Cons _ xs) = xs