# HG changeset patch # User Christian Urban # Date 1726757253 -3600 # Node ID 791f4d9f53e15eaf02950fcb4c4247987af84bbb # Parent 787ef75ec006628124aba85b2f4fc4b7ccea50e4 updated diff -r 787ef75ec006 -r 791f4d9f53e1 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 787ef75ec006 -r 791f4d9f53e1 handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 787ef75ec006 -r 791f4d9f53e1 handouts/ho02.tex --- a/handouts/ho02.tex Wed May 29 13:25:30 2024 +0100 +++ b/handouts/ho02.tex Thu Sep 19 15:47:33 2024 +0100 @@ -8,7 +8,7 @@ \begin{document} \fnote{\copyright{} Christian Urban, King's College London, - 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023} + 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024} \section*{Handout 2 (Regular Expression Matching)} @@ -389,10 +389,10 @@ construct the regular expression for $s$ by calling $\textit{der}$ with $r_1$ and ``appending'' $r_2$. There is however one exception to this simple rule: if $r_1$ can match the empty string, then -all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is +all of $c\!::\!s$ is matched by $r_2$. Therefore in case $r_1$ is nullable (that is can match the empty string) we have to allow the choice $\textit{der}\,c\,r_2$ for calculating the regular -expression that can match $s$. Therefore we have to add the +expression that can match $s$. This means we have to add the regular expression $\textit{der}\,c\,r_2$ in the result. The $*$-case is again simple: if $r^*$ matches a string of the form $c\!::\!s$, then the first part must be ``matched'' by a @@ -788,7 +788,7 @@ (23/Aug/2016) I found another place where this algorithm can be sped up (this idea is not integrated with what is coming next, but I present it nonetheless). The idea is to not define \texttt{ders} -that it iterates the derivative character-by-character, but in bigger +so that it iterates the derivative character-by-character, but in bigger chunks. The resulting code for \texttt{ders2} looks as follows: \lstinputlisting[numbers=none]{../progs/app52.scala} diff -r 787ef75ec006 -r 791f4d9f53e1 progs/fun/fun_llvm.sc --- a/progs/fun/fun_llvm.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/fun/fun_llvm.sc Thu Sep 19 15:47:33 2024 +0100 @@ -41,8 +41,12 @@ // ./a.out -import $file.fun_tokens, fun_tokens._ -import $file.fun_parser, fun_parser._ +//> using toolkit 0.5.0 +// > using file fun_tokens.scala +// > using file fun_parser.scala + +//import $file.fun_tokens, fun_tokens._ +//import $file.fun_parser, fun_parser._ // for generating new labels @@ -267,7 +271,6 @@ } } -print("%d\n", i) val prelude = """ @.str = private constant [4 x i8] c"%d\0A\00" @@ -360,6 +363,7 @@ */ +/* factC(6, x => x) factC(6, x => {println(s"The final Result is $x") ; 0}) factC(6, _ + 1) @@ -373,4 +377,5 @@ def fibC(n: Int, ret: Int => Int) : Int = { if (n == 0 || n == 1) ret(1) else fibC(n - 1, x => fibC(n - 2, y => ret(x + y))) -} \ No newline at end of file +} +*/ diff -r 787ef75ec006 -r 791f4d9f53e1 progs/fun/fun_parser.sc --- a/progs/fun/fun_parser.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/fun/fun_parser.sc Thu Sep 19 15:47:33 2024 +0100 @@ -10,16 +10,21 @@ // this will generate a parse-tree from a list // of tokens +//> using toolkit 0.5.0 +// > using file fun_tokens.scala + + import scala.language.implicitConversions import scala.language.reflectiveCalls -import $file.fun_tokens, fun_tokens._ + +//import $file.fun_tokens, fun_tokens._ // Parser combinators // type parameter I needs to be of Seq-type // -type IsSeq[I] = I => Seq[_] +type IsSeq[I] = I => Seq[?] /* abstract class Parser[I, T](using is: I => Seq[_]) { @@ -32,7 +37,7 @@ */ -abstract class Parser[I, T](using is: I => Seq[_]) { +abstract class Parser[I, T](using is: I => Seq[?]) { def parse(ts: I): Set[(T, I)] def parse_single(ts: I) : T = @@ -76,7 +81,7 @@ def map[S](f: => T => S) = new MapParser[I, T, S](p, f) } -def ListParser[I, T, S](p: => Parser[I, T], q: => Parser[I, S])(using is: I => Seq[_]): Parser[I, List[T]] = { +def ListParser[I, T, S](p: => Parser[I, T], q: => Parser[I, S])(using is: I => Seq[?]): Parser[I, List[T]] = { (p ~ q ~ ListParser(p, q)).map{ case (x:T) ~ (y:S) ~ (z:List[T]) => x :: z } || (p.map[List[T]]{s => List(s)}) } @@ -184,7 +189,7 @@ Prog.parse_single(tks) //@doc("Parses a file.") -@main +//@main def main(fname: String) : Unit = { val tks = tokenise(os.read(os.pwd / fname)) println(parse_tks(tks)) diff -r 787ef75ec006 -r 791f4d9f53e1 progs/fun/fun_tokens.sc --- a/progs/fun/fun_tokens.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/fun/fun_tokens.sc Thu Sep 19 15:47:33 2024 +0100 @@ -8,6 +8,7 @@ // amm fun_tokens.sc defs.fun // +//> using toolkit 0.5.0 import scala.language.implicitConversions @@ -41,7 +42,7 @@ charlist2rexp(s.toList) extension (s: String) { - def $ (r: Rexp) = RECD(s, r) + infix def $ (r: Rexp) = RECD(s, r) } extension (r: Rexp) { @@ -252,7 +253,7 @@ // import os._ //@doc("Tokenising a file.") -@main +//@main def main(fname: String) = { println(tokenise(os.read(os.pwd / fname))) } diff -r 787ef75ec006 -r 791f4d9f53e1 progs/matcher/re1.sc --- a/progs/matcher/re1.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/matcher/re1.sc Thu Sep 19 15:47:33 2024 +0100 @@ -100,8 +100,6 @@ // test: (a?{n}) (a{n}) -@arg(doc = "Test (a?{n}) (a{n})") -@main def test1() = { println("Test (a?{n}) (a{n})") @@ -111,8 +109,6 @@ } // test: (a*)* b -@arg(doc = "Test (a*)* b") -@main def test2() = { println("Test (a*)* b") @@ -165,7 +161,7 @@ size(ders(("a" * 30).toList, BIG)) // 31010539 -@main + def test3() = { println("Test (a + aa)*") @@ -174,7 +170,7 @@ } } - -@arg(doc = "All tests.") @main def all() = { test1(); test2() ; test3() } + +//all() diff -r 787ef75ec006 -r 791f4d9f53e1 progs/parser-combinators/comb1.sc --- a/progs/parser-combinators/comb1.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/parser-combinators/comb1.sc Thu Sep 19 15:47:33 2024 +0100 @@ -7,22 +7,30 @@ // Note, in the lectures I did not show the type bound -// using is: I => Seq[_], which means that the input -// type 'I' needs to be a sequence. +// I : IsSeq, which means that the input type 'I' needs +// to be a sequence that can be tested to be empty. + +trait IsSeq[I] { + extension (i: I) def isEmpty: Boolean +} -type IsSeq[I] = I => Seq[?] +given IsSeq[String] = _.isEmpty +given [I]: IsSeq[Seq[I]] = _.isEmpty + -abstract class Parser[I: IsSeq, T](using is: IsSeq[I]) { +// parser class +//============== + +abstract class Parser[I : IsSeq, T] { def parse(in: I): Set[(T, I)] def parse_all(in: I) : Set[T] = for ((hd, tl) <- parse(in); - if is(tl).isEmpty) yield hd + if tl.isEmpty) yield hd } - // parser combinators - +//==================== // alternative parser class AltParser[I : IsSeq, T](p: => Parser[I, T], @@ -169,14 +177,18 @@ println(E.parse_all("1+2+3")) -// with parser combinators (and other parsing algorithms) -// no left-recursion is allowed, otherwise the will loop +// with parser combinators (and many other parsing algorithms) +// no left-recursion is allowed, otherwise the will loop; +// newer versions of Scala (3.5) will actually give a warning +// about this +/* lazy val EL: Parser[String, Int] = ((EL ~ p"+" ~ EL).map{ case ((x, y), z) => x + z} || (EL ~ p"*" ~ EL).map{ case ((x, y), z) => x * z} || (p"(" ~ EL ~ p")").map{ case ((x, y), z) => y} || NumParserInt) +*/ // this will run forever: //println(EL.parse_all("1+2+3")) diff -r 787ef75ec006 -r 791f4d9f53e1 progs/while/compile.sc --- a/progs/while/compile.sc Wed May 29 13:25:30 2024 +0100 +++ b/progs/while/compile.sc Thu Sep 19 15:47:33 2024 +0100 @@ -81,7 +81,7 @@ extension (sc: StringContext) { def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" - def l(args: Any*): String = sc.s(args:_*) ++ ":\n" + def l(args: Any*): String = sc.s(args:_*) ++ ":" } // this allows us to write things like @@ -131,22 +131,22 @@ val if_end = Fresh("If_end") val (instrs1, env1) = compile_block(bl1, env) val (instrs2, env2) = compile_block(bl2, env1) - (compile_bexp(b, env, if_else) ++ - instrs1 ++ - i"goto $if_end" ++ - l"$if_else" ++ - instrs2 ++ - l"$if_end", env2) + (s"""|${compile_bexp(b, env, if_else)} + |${instrs1} + |${i"goto $if_end"} + |${l"$if_else"} + |${instrs2} + |${l"$if_end"}""".stripMargin, env2) } case While(b, bl) => { val loop_begin = Fresh("Loop_begin") val loop_end = Fresh("Loop_end") val (instrs1, env1) = compile_block(bl, env) - (l"$loop_begin" ++ - compile_bexp(b, env, loop_end) ++ - instrs1 ++ - i"goto $loop_begin" ++ - l"$loop_end", env1) + (s"""|${l"$loop_begin"} + |${compile_bexp(b, env, loop_end)} + |$instrs1 + |${i"goto $loop_begin"} + |${l"$loop_end"}""".stripMargin, env1) } case Write(x) => (i"iload ${env(x)} \t\t; $x" ++ @@ -166,7 +166,7 @@ // main compilation function for blocks def compile(bl: Block, class_name: String) : String = { val instructions = compile_block(bl, Map.empty)._1 - (beginning ++ instructions ++ ending).replaceAllLiterally("XXX", class_name) + (beginning ++ instructions ++ ending).replace("XXX", class_name) } diff -r 787ef75ec006 -r 791f4d9f53e1 slides/slides01.pdf Binary file slides/slides01.pdf has changed diff -r 787ef75ec006 -r 791f4d9f53e1 slides/slides01.tex --- a/slides/slides01.tex Wed May 29 13:25:30 2024 +0100 +++ b/slides/slides01.tex Thu Sep 19 15:47:33 2024 +0100 @@ -254,7 +254,7 @@ \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office Hour: & Thurdays 15 -- 16\\ + Office Hour: & Fridays 12 -- 14\\ Location: & N7.07 (North Wing, Bush House)\\ Slides \& Progs: & KEATS\\ Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ @@ -513,7 +513,7 @@ \textbf{Boeing 777's}: First flight in 1994. They want to achieve triple redundancy for potential hardware faults. -\here{http://www.citemaster.net/get/db3a81c6-548e-11e5-9d2e-00163e009cc7/R8.pdf}\bigskip +\here{https://ieeexplore.ieee.org/document/495891}\bigskip They compile 1 Ada program to\medskip @@ -627,7 +627,6 @@ \footnotesize\textcolor{gray}{Grace Hopper}\smallskip\\ {\small\textcolor{gray}{(she made it to David Letterman's Tonight Show - \here{https://youtu.be/3N_ywhx6_K0?t=31} / \here{https://www.youtube.com/watch?v=oE2uls6iIEU})}} \end{flushright} \end{textblock} @@ -643,13 +642,13 @@ \begin{itemize} \item final exam in January (35\%) -\item five CWs (65\%) +\item four CWs (65\% - first CW is optional) \end{itemize}\bigskip\bigskip\pause \textbf{Weekly Homework (optional):} \begin{itemize} -\item uploaded on KEATS, send answers via email, (try to!) respond individually +\item uploaded on KEATS - solutions will be discussed during the SGTs \item \alert{\bf all} questions in the exam will be from the HWs!! \end{itemize} @@ -664,8 +663,8 @@ \begin{center} \begin{tikzpicture} - \begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023}, - width = \textwidth, + \begin{axis}[symbolic x coords={2016,2017,2018,2019,2020,2021,2022,2023,2024}, + width = 1.1\textwidth, height = 5cm, bar width=8mm, nodes near coords, @@ -679,8 +678,9 @@ ] \addplot[ybar,style={rred,fill=rred!75,mark=none},text=black] coordinates { -(2023,183) -(2022,112) +(2024,136) +(2023,169) +(2022,111) (2021,98) (2020,59) (2019,38)