I. Tools for working with Scala A. Downloading tools ------------------------------------------ DOWNLOADING THE TOOLS From scala.epfl.ch - Installation of command-line tools - Eclipse plugin ------------------------------------------ B. Eclipse Plugin ------------------------------------------ ECLIPSE PLUGIN Change your shortcut for starting eclipse to pass option: -vmargs -Xmx256M Set up Scala by following prompts To run, use external tools configuration with Location: Working Directory: ${project_loc} Arguments: -cp ${project_loc}/bin ${string_prompt} ------------------------------------------ C. Command line tools ------------------------------------------ COMMAND LINE TOOLS scala - the virtual machine (like java) scalaint - interactive interpreter (like hugs) scalac - the compiler scaladoc - documentation generator scala-info - tells about environment, etc. ------------------------------------------ D. Documentation ------------------------------------------ DOCUMENTATION From scala.epfl.ch About the language: - The Scala Language specification - Scala by Example About the APIs: - HTML browsable documents doc/api/index.html - also use the Java or .NET documents for base classes (Object, String...) ------------------------------------------ II. Overview of Scala A. Problems ------------------------------------------ PROBLEMS ADDRESSED BY SCALA - How to program Web Services? - How to support component-based systems? ------------------------------------------ 1. web service programming ------------------------------------------ WHY WEB SERVICES? RPC doesn't scale to large systems - delay - failures (of message delivery) Web service answers: - performance: - increase granularity of data (XML) - failures: - replication of servers ==> avoid server state ==> tree transformation ------------------------------------------ Why does increasing granularity of data help solve delay problems? Why does replication of servers lead to desire to avoid server state? Why does avoiding server state lead to viewing programs as tree transformations? 2. component-based programming ------------------------------------------ WHY COMPONENTS? - Programming is too expensive - Programming is too error-prone - Programmers don't generally have the necessary domain knowledge Idea: reusable components solve these problems ------------------------------------------ How do components help cut the costs of programming? How the components help reduce errors in programming? How do components help reduce the necessary domain knowledge? B. Approach ------------------------------------------ APPROACH TO SOLVING PROBLEMS For web services: - support XML tree transformations ==> functional programming idioms: - algebraic data types - pattern matching - list/sequence comprehensions - higher-order functions - lazy evaluation For component-based systems: - better composition mechanisms - better abstraction mechanisms want these to be scalable: ==> work same for small and large hypothesis: unify functional and OO programming type system innovation: - virtual types, path-dependent - symmetric mixin composition - external extensions using "views" ------------------------------------------ III. Primitives for computation in Scala A. Data Overview ------------------------------------------ TYPES IN SCALA Any (supertype of any type) - AnyVal (value classes) Double, Float, Long, Int, Short, Byte Char, Boolean, Unit - java.lang.Object = AnyRef (reference classes) java.lang.String, ... ScalaObject Iterable Seq List Symbol Ordered ... AllRef (a subtype of all reference classes) All (a subtype of all types) ------------------------------------------ ------------------------------------------ OPERATIONS IN ANY TYPE final def !=(v0: Any): Boolean final def ==(v0: Any): Boolean final def asInstanceOf[T0]: T0 def equals(v0: Any): Boolean def hashCode(): Int final def isInstanceOf[T0]: Boolean final def match[T0,T1](v0: (T0) => T1): T1 def toString(): String ------------------------------------------ 1. Value Classes (and their literals) ------------------------------------------ VALUE CLASSES All subtypes of scala.AnyVal Numbers - scala.Int (= int) ..., -1, 0, 1, ... - scala.Long (= long) ..., -1L, 0l, 1l, 2L, ... - scala.Short (= short) - scala.Byte (= byte) usual Java operators (+, -, *, %, /, ...) Characters - scala.Char (= char) 'x', '\n' Booleans - scala.Boolean (= boolean) true, false ------------------------------------------ 2. Reference Data ------------------------------------------ REFERENCE DATA Reference classes in general - java.lang.Object (= scala.AnyRef) (root/top reference class) - scala.AllRef (bottom reference class) null: AllRef Everything from the JDK, including: - java.lang.String "a str\n" all the Java String operations Several scala built-ins: scala package - scala.Object - Symbol 'sym, 'a_sym, scala.Symbol("foo") - scala.xml.Node (for XML) My phone book Janet 555-1212 ... - Predef (predefined stuff, varies between JDK and CLR) - Array[T] - Function (= (a) => b) - Unit () - Pair (= Tuple2), Triple (= Tuple3) Pair(3, 4) - ... ------------------------------------------ B. primitive expressions 1. designators ------------------------------------------ DESIGNATORS Sample names: x this super Selections: p.C.y E.f C.this super[M].y D.super[M].x ------------------------------------------ 2. calls ------------------------------------------ METHOD CALLS Basic primitives for computation: E.attr E1.f(1) E2.m(x,y) Sugar: If f is a method in `this' f ==> this.f g(E1, ..., En) ==> this.g(E1, ..., En) ------------------------------------------ ------------------------------------------ FUNCTION CALL SUGARS Application of objects: assuming that f is an object (i.e., that f is not a method) f(E1, ..., En) ==> f.apply(E1, ..., En) ------------------------------------------ ------------------------------------------ INFIX METHOD CALL SUGARS Left associative, for names not ending in a colon (:) w op z ==> e.g., 5 - 4 - 1 ==> (5 - 4) - 1 Right associative, for names ending in a colon (:) E3 --: E4 ==> e.g., 3 :: 4 :: Nil ==> 3 :: (4 :: Nil) ------------------------------------------ ------------------------------------------ POSTFIX AND PREFIX METHOD CALL SUGARS Postfix calls: E op ==> e.g., a length ==> a.length Prefix calls: - E ==> E.- + E ==> E.+ ! E ==> E.! ~ E ==> E.~ e.g., - sin(3) ==> sin(3).- ------------------------------------------ What would you guess the desugaring for a postfix op would be? 3. object creation ------------------------------------------ OBJECT CREATION Simple constructor calls: new C() new D(x, y) More complex forms later (templates) ------------------------------------------ 4. assignments ------------------------------------------ ASSIGNMENT Primitive - assignment x = E Sugars x = E ==> x.f = E ==> a(i,j) = E ==> ------------------------------------------ Can all assignments be interpreted as method calls, or must some be primitive? 5. pattern matching ------------------------------------------ PATTERN MATCHING Uses match method: xs match { case Nil => 0; case x :: xs if e == x => 1 + count(e, xs); case x :: xs => count(e, xs); } ls match { case List(x, y, xs @ _ *) ==> ...; case List(1, x@(('a'|'b')+),y,_) ==> ...; } ------------------------------------------ If match is a method, what argument type does it take? So what is the type of a block of case clauses? 6. exceptions ------------------------------------------ EXCEPTIONS (AS IN JAVA or C#) Creation: new IllegalArgumentException() Throwing: throw new IllegalArgumentException() Catching: try { S } catch E try { S } finally E Sugar: try { S } catch E1 finally E2 ==> try{ try { S } catch E1} finally E2 ------------------------------------------ 7. Return expressions ------------------------------------------ RETURN Returning: return E can only be used inside a method or function ------------------------------------------ IV. Means of Abstraction in Scala A. functional abstractions 1. function closures ------------------------------------------ ANONYMOUS FUNCTIONS x => x x: Int => x + 1 (y: Int) => { return y - 1 } (x: Int, y: Int) => (x + y /2) ------------------------------------------ What's the meaning of these? 2. method closures ------------------------------------------ METHOD CLOSURES Sugars: .head ==> (x => x.head) .drop(i) ==> (x => x.drop(i)) E.g., def column[T](xss: List[List[T]], n: int) : List[T] = xss.map(.drop(i)).map(.head) ------------------------------------------ Does this take methods out of an object and give up dynamic binding? B. Declarations and Definitions What's the difference between a declaration and a definition? 1. value ------------------------------------------ VALUES Declarations (val x:T) val half: Double; val quarter, eighth: Double; Value definitions (val x:T = E): val half = 1.0/2.0; val quarter: Double = 1.0/4.0; val one, uno = 1; With pattern matching: val x :: xs = mylist; ------------------------------------------ What's the value of "one" after the definition above? 2. variable ------------------------------------------ VARIABLES variable declarations (var x:T): var frac: Fraction; variable definitions (var x:T = E): var f = new Fraction(1,2); var i: Int = _; // default init. Client's view: var x: T; looks like: def x: T; // getter def x_= (y: T): Unit; ------------------------------------------ What's the advantage of having the client's view be two functions? 3. functions or methods ------------------------------------------ FUNCTIONS (METHODS) declarations: def ip2: Int; def inc(x: Int): Int; def update(i: Int, e: T): Unit; def append(elems: T*): List[T]; def ifFalse(tst: Boolean, body: => Unit): Unit; definitions def ip2 = i + 2; def inc(x: Int): Int = x + 1; def ifFalse(tst: Boolean, body: => Unit): Unit = { if (!tst) body } def sum(args: int*) = { var result = 0; for (val arg <- args.elements) result = result + arg; result } ------------------------------------------ ------------------------------------------ CURRYING Curried functions can be written: def cadd(x: Int)(y: Int): Int = x + y You can partially parameterize functions, even if not curried: (0 ==) But can't uncurry implicitly: cadd(3, 4) // error! ------------------------------------------ 4. type declarations and aliases ------------------------------------------ TYPE DECLARATIONS AND ALIAS DEFINTIONS declarations: type Elems; type IntList; type T <: Comparable[T]; type Two[a] = Tuple2[a,a]; type alias definitions: type void = Unit; type IntList = List[Int]; type Two[a] = Tuple2[a,a]; class and trait defintions class Counter(v: Int) { /* ... */ } trait Countable; ------------------------------------------ C. class, trait, and object definitions 1. class definitions ------------------------------------------ CLASS DEFINITIONS package misc; /** Simple counters. */ class Counter(v: Int) { /** Increment above the initial value.*/ private var incr: Int = 0; /** Return this counter's value. */ def value: Int = v + incr; /** Increment the counter. */ def inc: Unit = { incr = incr+1 } } ------------------------------------------ a. constructors ------------------------------------------ CONSTRUCTORS Additional ones named "this": this() = { this(0) } ------------------------------------------ b. members Which members are abstract? How would you add a toString override? c. Classes are types What declaration would you give to say that you want a nested class to be defined in a subclass, but aren't going to define it? d. abstract members and classes 2. object definitions ------------------------------------------ OBJECT DEFINITIONS I.e., singletons package misc; object CounterMain { def main(args: Array[String]): Unit = { val c = new Counter(3); Console.println(c); c.inc; c.inc; Console.println("c.value = " + c.value); } } ------------------------------------------ a. initialization ------------------------------------------ CLASS AND OBJECT INITIALIZATION Objects are initialized lazily, when the object is first dereferenced When a constructor called: 0. all val, var members set to _ (default) 1. constructor for superclass is executed, 2. statements in the class body executed, in order ------------------------------------------ 3. More examples (skip if not needed) V. Inheritance ------------------------------------------ A (SUPER)CLASS: STACK package misc; import scala.collection.mutable.ArrayBuffer; /** Stacks */ class Stack[T]() { /** The contents of the stack. */ private val elems = new ArrayBuffer[T](); /** Push v onto the top of this stack. */ def push(v: T): Unit = { elems+v } /** Pop the top of this stack off. */ def pop(): Unit = { elems.trimEnd(1) } /** Return the top of this stack. */ def top(): T = elems(elems.length); } ------------------------------------------ ------------------------------------------ A SUBCLASS, STACKWITHLENGTH package misc; /** Stacks */ class StackWithLength[T]() extends Stack[T]() { /** The length the stack. */ private var size = 0; /** The length of this stack. */ def length = size; } ------------------------------------------ How to define push, pop, and top? A. Inheriting data B. Inheriting operations Where does code execution start from? ------------------------------------------ STEPS IN MESSAGE SENDING let receiver = object that is sent message let static-class = class where code being executed is defined let rc = if receiver is not "super" then receiver's (dynamic) class else if receiver is "super" then superclass of static-class 1. [fetch] look for method in class rc (a) if found: (b) if not found and rc is not "Any": (c) if not found and rc is "Any": 2. [execute] bind this to bind formals to execute the code of the method ------------------------------------------ 1. dispatch examples without super ------------------------------------------ MESSAGE PASSING EXAMPLE package misc; object DynamicDispatch { class C { def m1() = m2(); def m2() = "C"; } class D extends C { override def m2() = "D"; } def main(args: Array[String]) = { Console.println("new C().m1() = " + new C().m1()); Console.println("new D().m1() = " + new D().m1()); var r = new java.util.Random(); val x: C = if (r.nextBoolean()) new C() else new D(); Console.println("x.m1() = " + x.m1()); } } ------------------------------------------ what is the result of new D().m1() ? What if we added another method to D... def m3 = super.m2(); and then ran new D().m3 ? What if m2's body was this.m2() instead? 2. dispatch examples with super ------------------------------------------ MESSAGE PASSING EXAMPLE WITH SUPER package misc; object DynamicDispatchSuper { class C { def m1() = m2(); def m2() = "C"; def m3() = "m3"; } class D extends C { override def m2() = super.m3(); override def m3() = "E"; } def main(args: Array[String]) = { Console.println("new C().m1() = " + new C().m1()); Console.println("new D().m1() = " + new D().m1()); } } ------------------------------------------ What is the result (if any) of the expression "new C().m1()"? What is the result (if any) of the expression "new D().m1()"? 3. Example: CachedStack ------------------------------------------ CACHED STACK package misc; /** Stacks with a Cache */ class StackWithCache[T <: AnyRef]() extends Stack[T] { /** The cache. */ private var cache: T = null; /** Push v onto the top of this stack. */ override def push(v: T): Unit = { if (cache != null) { super.push(cache); } cache = v; } } ------------------------------------------ How would you define pop and top? 4. How to define toString(), refactoring How to define toString() for StackWithCache? ------------------------------------------ INHERITANCE BY FACTORING OUT COMMON PARTS in class Stack[T]: class Stack[T]() { /* ... */ override def toString():String = { "Stack(" + elementsString + ")" } def elementsString = { val buf = new StringBuffer(); var first = true; for (val e: T <- elems.elements) { if (!first) { buf.append(", "); first = false; } buf.append(e.toString()); } buf.toString(); } } FOR YOU TO DO Define whatever methods are *needed* to have toString work for StackWithCache ------------------------------------------ C. traits and multiple inheritance 1. Design issue: Single vs. multiple inheritance ------------------------------------------ SINGLE VS. MULTIPLE INHERITANCE def: a language has *single inheritance* if each class has def: a language has *multiple inheritance* if each class may have Motivating problem: What if want StackWithCacheLength? ------------------------------------------ 2. traits ------------------------------------------ TRAITS Goal: multiple inheritance without the problems class C extends SuperOfC with Trait1 with Trait2 { ... } A kind of abstract class such that: - evaluation of its constructor is pure: i.e.: - no side effects - no allocation of storage So this leads to the restrictions: ------------------------------------------ ------------------------------------------ NOT ALLOWED IN TRAITS var definitions private var declarations val definitions that are not pure defs of secondary constructors ALLOWED IN A TRAIT val declarations (required values) val definitions that are pure var declarations (required fields) def declarations (abstract methods) def definitions (default methods) type declarations (required types) type definitions (provided types) object declarations imports packages ------------------------------------------ Why are object declarations ok? 3. Semantics of classes, traits, and objects a. sugars ------------------------------------------ SEMANTICS OF CLASSES AND OBJECTS Sugars for constructors class constructorName ... ==> class constructorName() ... class cn(..., val x: T, ...) ... { S1 ... Sn } ==> class cn(..., x': T, ...) ... { val x:T = x'; [x'/x]S1 ... [x'/x]Sn } Sugars for classes class id(args); ==> class id(args) {} class id(args) TemplateBody ==> class id(args) extends AnyRef with ScalaObject TemplateBody ------------------------------------------ b. semantics ------------------------------------------ SEMANTICS OF CLASS DEFINITIONS Environment = {types: [Id -> Type], values: [Id -> Value]} Type = {supers: SetOf(Id), valueArgs: Formal*} Value = Location M_C: ClassDef -> Environment -> Store -> Environment x Store M_C[[class id(x1:T1, ..., xn:Tn) extends scid(e1, ..., em) TemplateBody]] env s = (denv, s1) where denv.types(id) = { supers = { scid }, valueArgs = (x1:T1, ..., xn:Tn) } denv.values(id) = l where l not in dom(s) and s(l) = { class = env("metaclass"), super = env.values(scid), vtable = /* ... */, constr = let lsup = env(scid) in \(v1, ..., vn).\lnew.\s2. let env2 = { x1 = v1, ... xn = vn } (rands, s3) = M_E*[[e1,...,em]] (env2)s2 ((),s4) = lsup.constr(rands) (lnew)s3 s5 = s4.update(lnew, { x1 = v1, ..., xn = vn }) in M_E[[TemplateBody]] (env2) s5 } ------------------------------------------ What's the vtable? Why locations? What does the constructor do? c. Mixins and diamond inheritance ------------------------------------------ package misc; object Diamond { trait Top { def m1 = "Top's m1"; def m2 = "Top's m2"; def m3 = "Top's m3"; def m4 = "Top's m4"; def m5 = "Top's m5"; def m6: String; def m7: String; def m8: String; } trait Left extends Top { override def m2 = "Left's m2"; abstract override def m3: String; override def m4 = "Left's m4"; override def m5 = "Left's m5"; def m6 = "Left's m6"; def m9 = "Left's m9"; } trait Right extends Top { override def m3 = "Right's m3"; abstract override def m4: String; override def m5 = "Right's m5"; def m7 = "Right's m7"; def m9 = "Right's m9"; } class Bottom extends Top with Left with Right { // must override m5 to resolve conflict override def m5 = "Bottom's m5"; // must provide required method m8 def m8 = "Bottom's m8"; // must resolve conflict on m9 override def m9 = super[Left].m9 + " + " + super[Right].m9; } class Bottom2 extends Left with Right { // no conflict on m5! // must provide required method m8 def m8 = "Bottom2's m8"; // Right's m9 would need override // without the following override def m9 = "Bottom2's m9"; } class Bottom3 extends Right with Left { // no conflict on m5! // must provide required method m8 def m8 = "Bottom2's m8"; // Left's m9 would need override // without the following override def m9 = "Bottom2's m9"; } def main(args: Array[String]) = { val b: Bottom = new Bottom(); Console.println("b.m1 = " + b.m1); Console.println("b.m2 = " + b.m2); Console.println("b.m3 = " + b.m3); Console.println("b.m4 = " + b.m4); Console.println("b.m5 = " + b.m5); Console.println("b.m6 = " + b.m6); Console.println("b.m7 = " + b.m7); Console.println("b.m8 = " + b.m8); Console.println("b.m9 = " + b.m9); Console.println("-----------------"); val b2: Bottom2 = new Bottom2(); Console.println("b2.m1 = " + b2.m1); Console.println("b2.m2 = " + b2.m2); Console.println("b2.m3 = " + b2.m3); Console.println("b2.m4 = " + b2.m4); Console.println("b2.m5 = " + b2.m5 + " (1)"); Console.println("b2.m6 = " + b2.m6); Console.println("b2.m7 = " + b2.m7); Console.println("b2.m8 = " + b2.m8); Console.println("b2.m9 = " + b2.m9); Console.println("-----------------"); val b3: Bottom3 = new Bottom3(); Console.println("b3.m1 = " + b3.m1); Console.println("b3.m2 = " + b3.m2); Console.println("b3.m3 = " + b3.m3); Console.println("b3.m4 = " + b3.m4); Console.println("b3.m5 = " + b3.m5 + " (2)"); Console.println("b3.m6 = " + b3.m6); Console.println("b3.m7 = " + b3.m7); Console.println("b3.m8 = " + b3.m8); Console.println("b3.m9 = " + b3.m9); } } ------------------------------------------ Why are the given overrides needed in Bottom? What is the output? ----------------- b2.m1 = Top's m1 b2.m2 = Left's m2 b2.m3 = Right's m3 b2.m4 = Left's m4 b2.m5 = Right's m5 (1) b2.m6 = Left's m6 b2.m7 = Right's m7 b2.m8 = Bottom2's m8 b2.m9 = Bottom2's m9 ----------------- What's the effect of putting a trait in extends rather than with? So what's the rule? ------------------------------------------ RULES FOR OVERRIDES 1. Overrides in the body of the class win and can resolve conflicts 2. Unique definitions satisfy requirements 3. Overrides in mixins (with) have precedence over parents (extends) 4. Multiple overrides or definitions in mixins are have equal precedence and have to be resolved ------------------------------------------ d. Precedence and linearization Is linearization needed to resolve precedence of overriding? e. abstract overrides and layered traits ------------------------------------------ PROVIDING OVERRIDES AS MIXINS trait Iterator[T] { def hasNext: Boolean; def next: T; } class BufferIterator[T] extends Iterator[T] { def hasNext: Boolean = ...; def next: T = ...; } trait SynchronizedIterator[T] extends Iterator[T] { abstract override def next: T = synchronized { super.next } abstract override def hasNext: Boolean = synchronized { super.hasNext } } class SynchBufferIterator[T] extends BufferIterator[T] with SynchronizedIterator[T]; ------------------------------------------ VI. Other Means of Combination in Scala A. Programs B. Packages and compilation units ------------------------------------------ PACKAGES (AS IN JAVA, C#) Packages define: "a set of member classes, objects and packages" packages: cannot be used as values can be imported (import p.q;) can be selected (p.T) can have hidden (private) elements ------------------------------------------ ------------------------------------------ DIFFS FROM JAVA Multiple packages in a compilation unit: package p.q { /* ... */ } package p.r { /* ... */ } Imports ordered: later imports can names from earlier imports More implicit imports (ordered): 1. java.lang 2. scala 3. scala.Predef ------------------------------------------ C. Compound Data (skip) D. Compound Actions (skip) ------------------------------------------ COMPOUND ACTIONS Conditionals: if (E1) E2 if (E3) E4 else E5 Loops: while (Test) Body do B2 while (T2) for (Enums) yield EV for (Enums2) Body3 Blocks: { S1 ... Sn } ------------------------------------------ VII. XML and Scala A. XML construction ------------------------------------------ XML EMBEDDING XML in Scala is: - fragmentary (not whole documents) - represented by instances of scala.xml.Node - immutable ------------------------------------------ So how do you transform XML documents? 1. basic literals ------------------------------------------ import scala.xml._; /** Tests of Scala's XML facilities. */ object Hello { def main(args: Array[String]): Unit = { val pp = new PrettyPrinter(80,2); val doc: Node = Hello!

Hello!

; Console.println(XHTML.preamble); Console.println(pp.format(doc)); } } ------------------------------------------ 2. Using embedded Scala expressions ------------------------------------------ BACK TO SCALA Including { scala code } in XML: object XHTML { /* ... */ def xhtmlPage(title: String, body: Elem): Node = { title } { body } ; } Nesting: ------------------------------------------ What's the output of the XHTML.xhtmlPage function? How does the list work? 3. example ------------------------------------------ package scalaxml; import scala.xml._; import XHTML._; /** Tests of Scala's XML facilities. */ object FlagColors { def main(args: Array[String]): Unit = { val pp = new PrettyPrinter(80,2); val title = "Colors of the United States Flag"; val page: Node = xhtmlPage(title,

{ title }

The colors on the flag of the United States of America, like the colors of many flags from around the world, are as follows.

); Console.println(preamble); Console.println(pp.format(page)); } } ------------------------------------------ B. queries 1. Loading XML ------------------------------------------ LOADING XML FROM FILES import scala.xml._; object CopyXML with Application { val pp = new PrettyPrinter(100, 2); val doc = XML.loadFile( "d:/WWW/ComS541/index.shtml"); Console.println(XHTML.preamble); Console.println(pp.format(doc)); } ------------------------------------------ ------------------------------------------ LOADING FROM A URL import scala.xml._; import java.net.URL; object CopyXMLFromURL { def main(args: Array[String]): Unit = { assert (args.length == 1); val pp = new PrettyPrinter(100, 2); val ios: java.io.InputStream = new URL(args(0)).openStream(); val doc = XML.load(ios); Console.println(XHTML.preamble); Console.println(pp.format(doc)); } } ------------------------------------------ 2. pattern matching (for one match) ------------------------------------------ PATTERN MATCHING NODES tbl match { case { rows @ _* }
=> { rows }{ newRow }
} ------------------------------------------ What does this match? Why escape back to XML, why not write { cs newEntry } ? 3. queries ------------------------------------------ QUERIES VIA XPATH-LIKE OPERATORS XPath operators: n \ "str" sequence of elements of n in nodes named "str" val d1 = 1 with inner 2 3 d1 \ "b" --> 1 3 0 \ "b" --> Nil n \\ "str" all descendents "str" including self d1 \\ "b" --> 1 2 3 0 \\ "b" --> 0 ------------------------------------------ ------------------------------------------ CAN USE IN FOR COMPREHENSIONS From "Scala by Example": for (val a <- labAddrBook \\ "entry"; val p <- labPhoneBook \\ "entry"; a \ "name" == p \ "name") yield { a.child } { p \ "phone"} ------------------------------------------ C. other features VIII. The Scala Type System A. Basic concepts 1. type and type error ------------------------------------------ BASIC CONCEPTS OF TYPE AND CLASS Def: A *protocol* is a set of messages (method names and arguments) that can be sent to an object Def: A *signature* is a set of method names and argument types Some questions: - Who decides what set of objects that obeys a protocol is a type? - What is a type error? ------------------------------------------ 2. behavioral reasoning aided by type checker can we make even stronger behavioral guarantees? ------------------------------------------ REASONING ABOUT ADTs Data type induction argument example: Sets represented by lists To prove: every Set's list has no duplicates How to prove this? ------------------------------------------ What part of the program has to be examined for this to work? 3. Seals (Morris 1973) ------------------------------------------ SEAL GOALS Only by using the ADTs ops can a client: alter = Clients cannot: discover = impersonate = SEALS MECHANISM createSeal -> (seal_t, unseal_t) gives unique seal and unseal functions Properties: unseal_t(seal_t(x)) = x unseal_t(anything else) is an error ------------------------------------------ How could these cause problems for a program that kept a table in sorted order? Does Scala prevent impersonation? How does this allow for data type induction? How could we use seals to define what a "type error" means? How does this relate to security in Scala or Java? 4. static and conservative nature of type systems ------------------------------------------ TYPE SYSTEMS AS STATIC APPROXIMATIONS Does this code have a type error? var i: int = 0; var f: Foo = _; if (myReader.read_bool()) { i = i + 1; } else { f = i; } ------------------------------------------ Why are all elements of an array assumed to have the same type? ------------------------------------------ BASIC STRATEGY OF STATIC TYPE SYSTEMS Variables have a statically declared type Expresssions are assigned a type based on Examples: ------------------------------------------ 5. soundness and completeness ------------------------------------------ SOUNDNESS AND COMPLETENESS A type system is *sound* iff A type system is *complete* iff ------------------------------------------ How to prove this? How is this affected by subtyping? B. types in Scala 1. security and types in network programming ------------------------------------------ WHY TYPE SOUNDNESS MATTERS OR HOW THEORETICIAL WORK CAN MAKE YOU FAMOUS class T { var x: SecurityManager; ... } class U { var x: MyObject; ... } var t: T; var u: U; // ...somehow make u and t aliases... t.x = System.getSecurity(); var m: MyObject = u.x; ------------------------------------------ 2. subtyping a. definitions ------------------------------------------ SUBTYPING Def: S is a subtype of T, written S <: T, iff Properties of subtypes: ------------------------------------------ What does this mean? b. behavioral subtyping ------------------------------------------ AN ASIDE: BEHAVIORAL SUBTYPES Def: S is a behavioral subtype of T iff Properties of behavioral subtypes: ------------------------------------------ c. inheritance and requirements on method typing ------------------------------------------ INHERITANCE AND METHOD TYPES class Int extends AnyVal; class Cell(xc: AnyVal) { private var xv = xc; def x: AnyVal = xv; def x_=(xc: AnyVal): Unit = { xv = xc; } } class PickyCell(xc: Int) extends Cell(xc) { override def x: = { ... } override def x_=(xc: ) = { ... } } val myC: Cell = new ...; val y = myC.x; myP.x = true; ------------------------------------------ What can the return type of the PickyCell's x method be? What can the argument type of PickyCell's x_= method be? Why? What about exceptions? If they were recorded in method type (as in Java) could you allow more or less in the subclass? ------------------------------------------ STATIC OVERLOADING vs. DYNAMIC OVERRIDES (MESSAGE PASSING) class Foo { def f(x: Float): Int = 1; } class Bar extends Foo { def f(s: String): Int = 2; } // client code var x: Foo = new Foo(); x.f (3.14); x.f ("a string"); // static type error ------------------------------------------ 3. names matter: classes and traits are types ------------------------------------------ CLASSES AND TYPES Every class and trait name ------------------------------------------ What does that mean for subtyping? ------------------------------------------ SUBCLASS ==> SUBTYPE class T {...} class S extends T {...} var x: T = new S(); ------------------------------------------ Why doesn't Scala infer when a class implements a type or a subtype? 4. casting ------------------------------------------ CHECKED CASTING E.g., var y : S = (S) randomExp; casting to a (reference) type generates ------------------------------------------ C. generics, variance annotations, and arrays ------------------------------------------ GENERIC POLYMORPHISM class GStack[T] { var elems: List[T] = Nil; def push(e: T): Unit = { elems = e :: elems; } def pop: Unit = { elems = elems.tail; } def top: T = elems.head; } ------------------------------------------ What's the advantage of this? 1. An example ------------------------------------------ ARRAYS IN SCALA Suppose PickyCell <: Cell. Consider class Array[T] Is Array[PickyCell] <: Array[Cell]? ------------------------------------------ 2. variance annotations How would you declare the relationships that might exist? ------------------------------------------ VARIANCE ANNOTATIONS trait VA[+D, -R, I] { val p: D; def save(r: R): Unit; var x: I; } D is covariant (read-only) R is contravariant (write-only) I is invariant (read-write) So VA[PickyCell, Cell, String] <: VA[Cell, PickyCell, String] E.g., case class Tuple2[+T1,+T2](_1:T1, _2:T2) trait Function1[-T0,+R] ------------------------------------------ Why the annotation on the above examples? When is a => b a subtype of c => d? ------------------------------------------ CHECKING VARIANCE ANNOTATIONS Is this okay? trait MyFunction1[+T0,-R] extends Function1[T0, R]; Covariant (+) positions: + types of val members + return types of methods + type parameters that are covariant Contravariant (-) positions: - argument types of methods - upper bounds on type parameters - type parameters that are contravariant Invariant ( ) positions: . types of var members . type parameters that are invariant . types used in both co- and contravariant positions ------------------------------------------ ------------------------------------------ FOR YOU TO DO Which of the declarations are consistent? abstract class VarAnnotaions[+D, -R, I] { var x: D; var y: R; var z: I; val a: D; val b: R; val c: I; def f(i: R): D; def g(j: D): R; def h(k: I): I; } ------------------------------------------ ------------------------------------------ FOR YOU TO DO Which type parameters can be co- or contravariant? abstract class InferVariances[ A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P] { var x: A; val y: B; def f(z: C): D; def g: (E => F); def h(o: G): (H => I) => (J => K); def iterate(f: L => L, n: Int): L => L; def remember(e: => M): Unit; def hmm(h: => ((N => O) => P)): Unit; } ------------------------------------------ Can all of these be invariant? ------------------------------------------ FOR YOU TO DO Is the following right? trait Super[+T] { def compare(x:Super[T]): Boolean; } trait Sub[+T] extends Super[T] { override def compare(x: Sub[T]): Boolean; } ------------------------------------------ How could this be fixed? 3. parameter bounds a. upper bounds GStack[T] works for all types T. What if you need more than the standard methods for the type parameter? ------------------------------------------ BOUNDED POLYMORPHISM trait Displayable { def display: Unit; } def displayAll[T <: Displayable] (elems: Seq[T]) = { for (val e <- elems) e.display } ------------------------------------------ Why won't this type check without the bound on T? ------------------------------------------ F-BOUNDED POLYMORPHISM trait Ordered[T] { def < (x:T): Boolean; } def max[T <: Ordered[T]](x: T, y: T) = { if (x < y) y else x } ------------------------------------------ b. lower bounds ------------------------------------------ COVARIANT TYPES AND IMMUTABLE OBJECTS trait GenList[+T] { def isEmpty: Boolean; def head: T; def tail: GenList[T]; def prepend(x: T): GenList[T]; // ok? } ------------------------------------------ Is the definition of prepend legal? Can you create an example that shows why? ------------------------------------------ FIX USING LOWER BOUNDS trait GenList[+T] { def isEmpty: Boolean; def head: T; def tail: GenList[T]; def prepend[S >: T](x: S): GenList[S]; } ------------------------------------------ What does this say? What happens if you use prepend with a subtype parameter? With a supertype parameter? How can these be used to solve the problem with Super and Sub above? D. type members and virtual types 1. advantages ------------------------------------------ ADVANTAGES OF TYPE MEMBERS Dependent products: abstract class Cell { type T; var value: T; } class IntCell extends Cell { type T = Int; var value = 0; } Family polymorphism: - type member that vary together, covariantly E.g., parsers, FSEntityProblem, ... ------------------------------------------ How is Cell like a generic type? Why is family polymorphism useful? 2. problems ------------------------------------------ PROBLEMS WITH OVERRIDING TYPE MEMBERS abstract class Cell { type T; var value: T; } class IntCell extends Cell { type T = Int; var value = 0; } // Is this okay? class StringCell extends IntCell { override type T = String; } ------------------------------------------ Scala doesn't allow StringCell, why? ------------------------------------------ PROBLEMS WITH TYPES FOUND THROUGH VARS object TypeInVarProblems with Application { trait TaggedValue { type T <: AnyRef; val value: T; } class Extractor { var v: TaggedValue = null; def extract: v.T = v.value; } val e = new Extractor(); e.v = new TaggedValue { type T = File; val value = new File("fn"); } val f: e.v.T = new File("fn2"); e.v = new TaggedValue { type T = String; val value = "hmmm"; } Console.println(f concat (e.extract)); } ------------------------------------------ What's wrong with this? 3. solution in Scala What approaches are there to preventing these problems? ------------------------------------------ HOW TO AVOID PROBLEMS WITH TYPE MEMBERS 1. Don't allow overriding 2. Require type names to be ------------------------------------------ ------------------------------------------ STABLE IDENTIFIERS FOR TYPES object StableIds { abstract class B { val y = 3; object BO { type Smell = U; type Odor = V; } type U; type V = Float; class B2 { object o; } } class C extends B { type U = Double; object O { type OT = Int; val z : this.OT = 1; var x : C.this.U = 3.14; var w : C.super.V = 2.73f; var hmm : C.super.BO.Odor = 1.0f; } val q: O.OT = 7; val r: O.type#OT = 14; val s: C.super[B].BO.type#Odor = 5.41f; val t: super.B2 = new super.B2(); val u: t.o.type = t.o; } } ------------------------------------------ What can't you use as a type? ------------------------------------------ STABLE IDS AND PATHS Def: a *path* is one of: - \epsilon, the empty path - C.this, where C names a class (or trait) - this, which means C.this, where C is the enclosing class - C.super.x, where C names a class, and x is a stable member of its superclass - C.super[M].x, where M is a mixin of class C, and x is stable - super.x, which means C.super.x, where C is the enclosing class - p.x, where p is a path, and x a stable member of p Def: a *stable member* is either: - a package, - a val definition, - a class definition, - a type definition, or - an object definition Def: a *stable identifier* is a path, that ends in an identifier ------------------------------------------ ------------------------------------------ TYPES FORMED FROM PATHS AND STABLEIDS Singleton types: syntax: p.type, where p is a path, p denotes a value, p conforms to AnyRef meaning: the set {p, null} examples: O.type t.o.type C.super[B].BO.type Type projections: syntax: T # x, where T is either a: - singleton type - a non-abstract class - a Java class and x is a type member of T meaning: the set of types defined by x in T examples: O.type#OT C.super[B].BO.type#Odor Type designators (names): syntax: sid, where sid is a stable identifier meaning: the type of values named desugaring: t ==> C.this.type#t, if t bound in C t ==> \epsilon.type#t, otherwise p.t ==> p.type#t Examples Float ==> scala.type#Float U ==> C.this.type#U this.OT ==> this.type#OT ------------------------------------------ E. typing mixin composition 1. definitions ------------------------------------------ TEMPLATES Def: a *template* is what follows "extends" in a class or object definition. Def: A template, of form sc with mc1 with ... with mcn { ... } has *superclass* sc, *mixin classes* mc1, ..., and mcn Def: The *parent classes* of a template are the superclass and the mixin classes. ------------------------------------------ 2. subtyping of mixins ------------------------------------------ SUBTYPING Subyping is declared. Given: class C sc with mc1 ... with mcn { ... } this produces: C <: sc C <: mc1 ... C <: mcn ------------------------------------------ 3. defaults for parent classes ------------------------------------------ DEFAULT PARENT CLASSES Default superclass extends AnyRef Default mixin: with ScalaObject ------------------------------------------ 4. problems from linearization ------------------------------------------ TYPING RESTRICTIONS ON TEMPLATES sc with mc1 with ... with mcn { ... } "The superclass of a template", sc, "must be a subtype of the superclass of each mixin class", mc1, ..., mcn. Why? trait Mixin1Super { def x = true } class Super { def x = 541 } trait Mixin1 extends Mixin1Super; class Sub extends Super with Mixin1; !(new Sub().x) // ok? ------------------------------------------ 5. self types ------------------------------------------ SELF TYPES In a class or object declaration, can declare the type of "this": class C : s extends sc with mc1 with ... with mcn { ... } Def: s is the *self type* of C. Default: C Restrictions: 1. The self type s must satisfy: s <: sc's self type s <: mc1's self type ... s <: mcn's self type 2. Each expression of form new D(...) must be such that D's self type is a supertype of (or equal to) D. ------------------------------------------ Why these restrictions? What could go wrong? ------------------------------------------ EXAMPLE WITH SELF TYPES trait SubjectObserver { type S <: Subject; type O <: Observer; abstract class Subject: S { private var observers: List[O] = List(); def subscribe(obs: O) = observers = obs :: observers; def publish = for (val obs <- observers) obs.notify(this); } trait Observer { def notify(sub: S): unit; } } ------------------------------------------ ------------------------------------------ USING SubjectObserver object SensorReader extends SubjectObserver { type S = Sensor; type O = Display; abstract class Sensor extends Subject { val label: String; var value: double = 0.0; def changeValue(v: double) = { value = v; publish; } } abstract class Display extends Observer { def println(s: String) = ... def notify(sub: Sensor) = println(sub.label + " has value " + sub.value); } } ------------------------------------------ IX. Summary and Evaluation of Scala A. vs. goals ------------------------------------------ HOW WELL DOES SCALA ACCOMPLISH ITS GOALS? - Programming web services - Supporting component-based systems ------------------------------------------ How well does it handle XML? How well does it handle the expression problem? B. vs. Haskell ------------------------------------------ HOW WELL DOES SCALA COMPARE TO HASKELL? ------------------------------------------ ------------------------------------------ HOW WELL DOES SCALA INTEGRATE OO AND FUNCTIONAL ------------------------------------------