Binary file handouts/ho01.pdf has changed
Binary file handouts/ho02.pdf has changed
--- 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}
--- 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
+}
+*/
--- 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))
--- 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)))
}
--- 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()
--- 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"))
--- 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)
}
Binary file slides/slides01.pdf has changed
--- 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)