# HG changeset patch # User Fahad Ausaf # Date 1415560463 0 # Node ID 10e7a90d8e7a043dad1545be4af6a6a27707dadf # Parent 6b8e3d232361798c33d8923a71fd89c6cd44ef15 test diff -r 6b8e3d232361 -r 10e7a90d8e7a Fahad/Scala/Chapter6.sc --- a/Fahad/Scala/Chapter6.sc Sat Nov 08 12:19:37 2014 +0000 +++ b/Fahad/Scala/Chapter6.sc Sun Nov 09 19:14:23 2014 +0000 @@ -1,8 +1,9 @@ package greeter - + + object Chapter6 { - println("Classes and Objects") //> Classes and Objects - + println("Classes and Objects") //> Classes and Objects + class Rational(n: Int, d: Int) { private def gcd(x: Int, y: Int): Int = { if (x == 0) y @@ -11,49 +12,49 @@ else gcd(y % x, x) } private val g = gcd(n, d) - + val numer: Int = n / g val denom: Int = d / g def +(that: Rational) = new Rational(numer * that.denom + that.numer * denom, denom * that.denom) def -(that: Rational) = new Rational(numer * that.denom - that.numer * denom, denom * that.denom) def *(that: Rational) = new Rational(numer * that.numer, denom * that.denom) def /(that: Rational) = new Rational(numer * that.denom, denom * that.numer) - + //Inheritance and Overriding override def toString = "" + numer + "/" + denom //Parameterless Methods def square = new Rational(numer * numer, denom * denom) } //Inheritance and Overriding - var i = 1 //> i : Int = 1 - var x = new Rational(0, 1) //> x : greeter.Chapter6.Rational = 0/1 + var i = 1 //> i : Int = 1 + var x = new Rational(0, 1) //> x : greeter.Chapter6.Rational = 0/1 while (i <= 10) { x += new Rational(1, i) i += 1 } - println("" + x.numer + "/" + x.denom) //> 7381/2520 + println("" + x.numer + "/" + x.denom) //> 7381/2520 //Parameterless Methods - val r = new Rational(3, 4) //> r : greeter.Chapter6.Rational = 3/4 - println(r.square) //> 9/16 - + val r = new Rational(3, 4) //> r : greeter.Chapter6.Rational = 3/4 + println(r.square) //> 9/16 + //Abstract Classes abstract class IntSet { def incl(x: Int): IntSet def contains(x: Int): Boolean } - + //Triats trait IntSett { def incl(x: Int): IntSet def contains(x: Int): Boolean } - + //Implementing abstract class class EmptySet extends IntSet { def contains(x: Int): Boolean = false def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet) } - + class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet { def contains(x: Int): Boolean = if (x < elem) left contains x @@ -64,5 +65,5 @@ else if (x > elem) new NonEmptySet(elem, left, right incl x) else this } - -} \ No newline at end of file + +} diff -r 6b8e3d232361 -r 10e7a90d8e7a Fahad/Scala/POSIX.sc --- a/Fahad/Scala/POSIX.sc Sat Nov 08 12:19:37 2014 +0000 +++ b/Fahad/Scala/POSIX.sc Sun Nov 09 19:14:23 2014 +0000 @@ -1,8 +1,9 @@ package greeter - + + object POSIX { - println("Posix Algorithm") //> Posix Algorithm - + println("Posix Algorithm") //> Posix Algorithm + abstract class Rexp case object NULL extends Rexp case object EMPTY extends Rexp @@ -11,7 +12,7 @@ case class SEQ(r1: Rexp, r2: Rexp) extends Rexp case class STAR(r: Rexp) extends Rexp case class RECD(x: String, r: Rexp) extends Rexp - + abstract class Val case object Void extends Val case class Chr(c: Char) extends Val @@ -20,23 +21,23 @@ case class Right(v: Val) extends Val case class Stars(vs: List[Val]) extends Val case class Rec(x: String, v: Val) extends Val - + def charlist2rexp(s: List[Char]): Rexp = s match { case Nil => EMPTY case c :: Nil => CHAR(c) case c :: s => SEQ(CHAR(c), charlist2rexp(s)) - } //> charlist2rexp: (s: List[Char])greeter.POSIX.Rexp + } //> charlist2rexp: (s: List[Char])greeter.POSIX.Rexp implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) - //> string2rexp: (s: String)greeter.POSIX.Rexp - + //> string2rexp: (s: String)greeter.POSIX.Rexp + implicit def RexpOps(r: Rexp) = new { def |(s: Rexp) = ALT(r, s) def % = STAR(r) def ~(s: Rexp) = SEQ(r, s) } //> RexpOps: (r: greeter.POSIX.Rexp)AnyRef{def |(s: greeter.POSIX.Rexp): greete //| r.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greet - //| er.POSIX.SEQ} - + //| er.POSIX.SEQ} + implicit def stringOps(s: String) = new { def |(r: Rexp) = ALT(s, r) def |(r: String) = ALT(s, r) @@ -47,8 +48,8 @@ } //> stringOps: (s: String)AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.AL //| T; def |(r: String): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r: //| greeter.POSIX.Rexp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SE - //| Q; def $(r: greeter.POSIX.Rexp): greeter.POSIX.RECD} - + //| Q; def $(r: greeter.POSIX.Rexp): greeter.POSIX.RECD} + // size of a regular expressions - for testing purposes def size(r: Rexp): Int = r match { case NULL => 1 @@ -58,8 +59,8 @@ case SEQ(r1, r2) => 1 + size(r1) + size(r2) case STAR(r) => 1 + size(r) case RECD(_, r) => 1 + size(r) - } //> size: (r: greeter.POSIX.Rexp)Int - + } //> size: (r: greeter.POSIX.Rexp)Int + // nullable function: tests whether the regular // expression can recognise the empty string def nullable(r: Rexp): Boolean = r match { @@ -70,8 +71,8 @@ case SEQ(r1, r2) => nullable(r1) && nullable(r2) case STAR(_) => true case RECD(_, r1) => nullable(r1) - } //> nullable: (r: greeter.POSIX.Rexp)Boolean - + } //> nullable: (r: greeter.POSIX.Rexp)Boolean + // derivative of a regular expression w.r.t. a character def der(c: Char, r: Rexp): Rexp = r match { case NULL => NULL @@ -83,14 +84,14 @@ else SEQ(der(c, r1), r2) case STAR(r) => SEQ(der(c, r), STAR(r)) case RECD(_, r1) => der(c, r1) - } //> der: (c: Char, r: greeter.POSIX.Rexp)greeter.POSIX.Rexp - + } //> der: (c: Char, r: greeter.POSIX.Rexp)greeter.POSIX.Rexp + // derivative w.r.t. a string (iterates der) def ders(s: List[Char], r: Rexp): Rexp = s match { case Nil => r case c :: s => ders(s, der(c, r)) - } //> ders: (s: List[Char], r: greeter.POSIX.Rexp)greeter.POSIX.Rexp - + } //> ders: (s: List[Char], r: greeter.POSIX.Rexp)greeter.POSIX.Rexp + // extracts a string from value def flatten(v: Val): String = v match { case Void => "" @@ -100,8 +101,8 @@ case Sequ(v1, v2) => flatten(v1) + flatten(v2) case Stars(vs) => vs.map(flatten).mkString case Rec(_, v) => flatten(v) - } //> flatten: (v: greeter.POSIX.Val)String - + } //> flatten: (v: greeter.POSIX.Val)String + // extracts an environment from a value def env(v: Val): List[(String, String)] = v match { case Void => Nil @@ -111,8 +112,8 @@ case Sequ(v1, v2) => env(v1) ::: env(v2) case Stars(vs) => vs.flatMap(env) case Rec(x, v) => (x, flatten(v)) :: env(v) - } //> env: (v: greeter.POSIX.Val)List[(String, String)] - + } //> env: (v: greeter.POSIX.Val)List[(String, String)] + def mkeps(r: Rexp): Val = r match { case EMPTY => Void case ALT(r1, r2) => @@ -120,8 +121,8 @@ case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) case STAR(r) => Stars(Nil) case RECD(x, r) => Rec(x, mkeps(r)) - } //> mkeps: (r: greeter.POSIX.Rexp)greeter.POSIX.Val - + } //> mkeps: (r: greeter.POSIX.Rexp)greeter.POSIX.Val + def inj(r: Rexp, c: Char, v: Val): Val = (r, v) match { case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1) :: vs) case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) @@ -132,38 +133,38 @@ case (CHAR(d), Void) => Chr(d) case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) } //> inj: (r: greeter.POSIX.Rexp, c: Char, v: greeter.POSIX.Val)greeter.POSIX.Va - //| l - + //| l + // main lexing function (produces a value) def lex(r: Rexp, s: List[Char]): Val = s match { case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") case c :: cs => inj(r, c, lex(der(c, r), cs)) - } //> lex: (r: greeter.POSIX.Rexp, s: List[Char])greeter.POSIX.Val - + } //> lex: (r: greeter.POSIX.Rexp, s: List[Char])greeter.POSIX.Val + def lexing(r: Rexp, s: String): Val = lex(r, s.toList) - //> lexing: (r: greeter.POSIX.Rexp, s: String)greeter.POSIX.Val - + //> lexing: (r: greeter.POSIX.Rexp, s: String)greeter.POSIX.Val + val r = (("1" $ "a") | (("2" $ "b") | ("3" $ "ab"))).% //> r : greeter.POSIX.STAR = STAR(ALT(RECD(1,CHAR(a)),ALT(RECD(2,CHAR(b)),RECD - //| (3,SEQ(CHAR(a),CHAR(b)))))) - env(lexing(r, "ba")) //> res0: List[(String, String)] = List((2,b), (1,a)) - - val r1 = "a" | "b" //> r1 : greeter.POSIX.ALT = ALT(CHAR(a),CHAR(b)) - lexing(r1, "a") //> res1: greeter.POSIX.Val = Left(Chr(a)) - + //| (3,SEQ(CHAR(a),CHAR(b)))))) + env(lexing(r, "ba")) //> res0: List[(String, String)] = List((2,b), (1,a)) + + val r1 = "a" | "b" //> r1 : greeter.POSIX.ALT = ALT(CHAR(a),CHAR(b)) + lexing(r1, "a") //> res1: greeter.POSIX.Val = Left(Chr(a)) + // Lexing Rules for a Small While Language - - def PLUS(r: Rexp) = r ~ r.% //> PLUS: (r: greeter.POSIX.Rexp)greeter.POSIX.SEQ + + def PLUS(r: Rexp) = r ~ r.% //> PLUS: (r: greeter.POSIX.Rexp)greeter.POSIX.SEQ val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" //> SYM : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT( //| ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHAR(c //| )),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k)), //| CHAR(l)),CHAR(m)),CHAR(n)),CHAR(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHA - //| R(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z)) + //| R(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z)) val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" //> DIGIT : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CH //| AR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR( - //| 9)) + //| 9)) val ID = SYM ~ (SYM | DIGIT).% //> ID : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A //| LT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHA //| R(c)),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k @@ -175,11 +176,11 @@ //| R(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w //| )),CHAR(x)),CHAR(y)),CHAR(z)),ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),C //| HAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR - //| (9))))) + //| (9))))) val NUM = PLUS(DIGIT) //> NUM : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0), //| CHAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHA //| R(9)),STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CHAR(1)),CHAR(2)),CH - //| AR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(9)))) + //| AR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(9)))) val KEYWORD: Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" //> KEYWORD : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHA //| R(s),SEQ(CHAR(k),SEQ(CHAR(i),CHAR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i) @@ -188,21 +189,21 @@ //| (s),CHAR(e))))),SEQ(CHAR(r),SEQ(CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w) //| ,SEQ(CHAR(r),SEQ(CHAR(i),SEQ(CHAR(t),CHAR(e)))))),SEQ(CHAR(t),SEQ(CHAR(r),S //| EQ(CHAR(u),CHAR(e))))),SEQ(CHAR(f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHAR - //| (e)))))) - val SEMI: Rexp = ";" //> SEMI : greeter.POSIX.Rexp = CHAR(;) + //| (e)))))) + val SEMI: Rexp = ";" //> SEMI : greeter.POSIX.Rexp = CHAR(;) val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" //> OP : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ( //| CHAR(:),CHAR(=)),SEQ(CHAR(=),CHAR(=))),CHAR(-)),CHAR(+)),CHAR(*)),SEQ(CHAR( //| !),CHAR(=))),CHAR(<)),CHAR(>)),SEQ(CHAR(<),CHAR(=))),SEQ(CHAR(>),CHAR(=))), - //| CHAR(%)),CHAR(/)) + //| CHAR(%)),CHAR(/)) val WHITESPACE = PLUS(" " | "\n" | "\t") //> WHITESPACE : greeter.POSIX.SEQ = SEQ(ALT(ALT(CHAR( ),CHAR( //| )),CHAR( )),STAR(ALT(ALT(CHAR( ),CHAR( - //| )),CHAR( )))) - val RPAREN: Rexp = ")" //> RPAREN : greeter.POSIX.Rexp = CHAR()) - val LPAREN: Rexp = "(" //> LPAREN : greeter.POSIX.Rexp = CHAR(() - val BEGIN: Rexp = "{" //> BEGIN : greeter.POSIX.Rexp = CHAR({) - val END: Rexp = "}" //> END : greeter.POSIX.Rexp = CHAR(}) - + //| )),CHAR( )))) + val RPAREN: Rexp = ")" //> RPAREN : greeter.POSIX.Rexp = CHAR()) + val LPAREN: Rexp = "(" //> LPAREN : greeter.POSIX.Rexp = CHAR(() + val BEGIN: Rexp = "{" //> BEGIN : greeter.POSIX.Rexp = CHAR({) + val END: Rexp = "}" //> END : greeter.POSIX.Rexp = CHAR(}) + /* * val WHILE_REGS = (("k" $ KEYWORD) | ("i" $ ID) | @@ -213,7 +214,7 @@ ("b" $ (BEGIN | END)) | ("w" $ WHITESPACE)).% */ - + val WHILE_REGS = (KEYWORD | ID | OP | @@ -235,48 +236,48 @@ //| CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHA //| R(y)),CHAR(z)),STAR(ALT //| Output exceeds cutoff limit. - + // Some Tests //============ - + def time[T](code: => T) = { val start = System.nanoTime() val result = code val end = System.nanoTime() println((end - start) / 1.0e9) result - } //> time: [T](code: => T)T - + } //> time: [T](code: => T)T + - val abc = List('a', 'b', 'c') //> abc : List[Char] = List(a, b, c) - val nullRexp = null //> nullRexp : Null = null - val myRexp = charlist2rexp(abc) //> myRexp : greeter.POSIX.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c))) + val abc = List('a', 'b', 'c') //> abc : List[Char] = List(a, b, c) + val nullRexp = null //> nullRexp : Null = null + val myRexp = charlist2rexp(abc) //> myRexp : greeter.POSIX.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c))) val myRexp2 = string2rexp("FahadAusaf") //> myRexp2 : greeter.POSIX.Rexp = SEQ(CHAR(F),SEQ(CHAR(a),SEQ(CHAR(h),SEQ(CHA //| R(a),SEQ(CHAR(d),SEQ(CHAR(A),SEQ(CHAR(u),SEQ(CHAR(s),SEQ(CHAR(a),CHAR(f)))) - //| )))))) + //| )))))) RexpOps(myRexp2) //> res2: AnyRef{def |(s: greeter.POSIX.Rexp): greeter.POSIX.ALT; def %: greete //| r.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greeter.POSIX.SEQ} = greeter.PO - //| SIX$$anonfun$main$1$$anon$1@37ecb28e + //| SIX$$anonfun$main$1$$anon$1@37ecb28e stringOps("Fahad") //> res3: AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.ALT; def |(r: Stri //| ng): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r: greeter.POSIX.R //| exp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SEQ; def $(r: gree //| ter.POSIX.Rexp): greeter.POSIX.RECD} = greeter.POSIX$$anonfun$main$1$$anon$ - //| 2@14bea551 + //| 2@14bea551 - size(myRexp2) //> res4: Int = 19 - nullable(nullRexp) //> scala.MatchError: null - //| at greeter.POSIX$$anonfun$main$1.nullable$1(greeter.POSIX.scala:59) - //| at greeter.POSIX$$anonfun$main$1.apply$mcV$sp(greeter.POSIX.scala:202) + size(myRexp2) //> res4: Int = 19 + nullable(nullRexp) //> scala.MatchError: null + //| at greeter.POSIX$$anonfun$main$1.nullable$1(greeter.POSIX.scala:59) + //| at greeter.POSIX$$anonfun$main$1.apply$mcV$sp(greeter.POSIX.scala:202) //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$$anonfun$$exe - //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76) + //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76) //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.redirected(W - //| orksheetSupport.scala:65) + //| orksheetSupport.scala:65) //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.$execute(Wor - //| ksheetSupport.scala:75) - //| at greeter.POSIX$.main(greeter.POSIX.scala:3) - //| at greeter.POSIX.main(greeter.POSIX.scala) + //| ksheetSupport.scala:75) + //| at greeter.POSIX$.main(greeter.POSIX.scala:3) + //| at greeter.POSIX.main(greeter.POSIX.scala) val newRexp = der('a',myRexp) @@ -301,4 +302,4 @@ //this is some crap -} \ No newline at end of file +}