%\documentclass[a4paper,titlepage]{slides} \documentclass[a4paper,landscape,titlepage]{slides} \usepackage[latin1]{inputenc} %\usepackage[T1]{fontenc} %\usepackage[german]{babel} %\usepackage{portland} \usepackage{lscape} %\usepackage[dvips]{color} \usepackage{alltt} \usepackage{array} \usepackage{dcolumn} \usepackage{epsfig} \input{epsf} \usepackage{fancyvrb} \usepackage[usenames,dvipsnames]{xcolor} \usepackage[normalem]{ulem} \usepackage{url} \newcommand{\slidetitle}[1]{\vspace{4ex}{\large\centerline{#1}}\vspace{1ex}} %\newcommand{\epsline}[1]{\vspace{1ex}\centerline{\epsffile{#1.eps}}} \newcommand{\epsline}[2]{\vspace{1ex}\centerline{\epsfig{file=#1.eps}}} %\wepsbox{file,width} \newcommand{\wepsbox}[2]{\includegraphics[width=#2]{#1.eps}} %\sepsbox{file,scale} \newcommand{\sepsbox}[2]{\includegraphics[scale=#2]{#1.eps}} %\wepsline{file,width} \newcommand{\wepsline}[2]{\vspace{1ex}\centerline{\epsfig{file=#1.eps,width=#2}}} \newcommand{\white}[1]{\textcolor{white}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\code}[1]{\texttt{#1}} \newcommand{\rep}[1]{{\Large$\downarrow$}\makebox[0pt][l]{#1}} \newcommand{\comment}[1]{} %\pass{arrow}{components} \newcommand{\pass}[2]{\(\left.\mbox{\fbox{\begin{tabular}{l}#2\end{tabular}}}\right#1\)} \newenvironment{portrait}{}{} \newenvironment{myitemize}{\begin{list}{$\bullet$}{\setlength{\itemsep}{0ex}\setlength{\topsep}{0ex}}}{\end{list}} \newcolumntype{.}{D{.}{.}{2}} \setlength\paperwidth{32cm} %16:9 aspect ratio \setlength\paperheight{18cm} \setlength\textheight{\paperheight} \addtolength\textheight{-1cm} \setlength\topmargin{\paperheight} \addtolength\topmargin{-2in} \addtolength\topmargin{-\headheight} \addtolength\topmargin{-\headsep} \addtolength\topmargin{-\textheight} \addtolength\topmargin{-\footskip} % this might be wrong! \addtolength\topmargin{-.5\topmargin} \addtolength\topmargin{-1.6ex} %\addtolength\evensidemargin{-2cm} \addtolength\oddsidemargin{-1cm} \addtolength\textwidth{4cm} %\setlength\textheight{\paperheight} %\addtolength\textheight{-1cm} % \setlength\topmargin{\paperheight} % \addtolength\topmargin{-2in} % \addtolength\topmargin{-\headheight} % \addtolength\topmargin{-\headsep} % \addtolength\topmargin{-\textheight} % \addtolength\topmargin{-\footskip} % this might be wrong! % \addtolength\topmargin{-.5\topmargin} %%\addtolength\evensidemargin{-2cm} %%\addtolength\oddsidemargin{-2cm} %%\addtolength\textwidth{4cm} \title{Low-Level Programming} \author{ M. Anton Ertl\\TU Wien } \date{} \begin{document} %\begin{landscape} \maketitle %\end{landscape} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{High-level vs. low-level programming language} \begin{minipage}[t]{15cm} \begin{myitemize} \item Prevents some bugs\\ \sout{arbitrary overwrites}\\ \sout{dangling references} \item Prevents some exploits\\ \sout{Buffer overflow} \item More convenient\\ automatic memory reclamation\\ arbitrary integers \item Limitations \end{myitemize} \end{minipage} \begin{minipage}[t]{15cm} \begin{myitemize} \item Access to bits and bytes\\ across abstraction boundaries \item Systems programming\\ run-time systems of HLLs\\ Libraries \item Efficiency\\ possible, not guaranteed\\ knowledge useful for HLLs \item Less convenient\\ fixed buffers or\\ manual memory reclamation \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Low-level programming languages} \begin{myitemize} \item Assembly language: machine-dependent, full power \item Forth: interactive, no type checking \item C \item C++ \item Rust: elaborate type system\\ tries to combine safety and low-level featurs \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Debugging} \begin{myitemize} \item interactive testing\\ use small words \item Stepping Debugger\\ \code{dbg \emph{word}}\\ Only works with \code{gforth-itc} \item Tracer (\code{printf} debugging)\\ \verb|~~| \item Backtrace \item insert \code{assert( ... )} \item insert conditional tracers \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{IDE features} \begin{myitemize} \item \code{locate \emph{word}}\\ \code{edit \emph{word}} \item \code{help \emph{word}} \item \code{where \emph{word}}\\ \code{nw bw ( u ) ww}\\ \item after a Backtrace\\ \code{nt bt ( u ) tt} \item Decompiler\\ \code{see \emph{word}}\\ \code{simple-see \emph{word}}\\ \code{see-code \emph{word}} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Memory} \wepsbox{memory}{30cm} \begin{myitemize} \item Address space (per-process) \item Accessible (mapped) memory (\code{pmap \emph{pid}})\\ \textbf{R}eadable \textbf{W}ritable e\textbf{X}ecutable \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Example: linked list} \begin{minipage}[t]{17cm} \begin{verbatim} public class ListQueueSimple { private ListNode head; public void add(String v) { if (head == null) { head = new ListNode(v, null); } else { ListNode last = head; while (last.next() != null) { last = last.next(); } last.setNext(new ListNode(v, null)); } } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{verbatim} public String poll() { if (head != null) { String result = head.value(); head = head.next(); return result; } return null; } } \end{verbatim} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Example: linked list (cont.)} \begin{minipage}[t]{16cm} \begin{verbatim} public class ListNode { private String value; private ListNode next; public ListNode(String v, ListNode n) { value = v; next = n; } public String value() { return value; } \end{verbatim} \end{minipage} \begin{minipage}[t]{14cm} \begin{verbatim} public ListNode next() { return next; } public void setNext(ListNode n) { next = n; } } \end{verbatim} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Example: linked list (cont.)} \begin{minipage}[t]{15cm} \begin{verbatim} 0 field: list-next 2field: list-value constant listnode : list-add {: c-addr u list-addr -- :} list-addr begin {: list-addr1 :} list-addr1 @ dup while list-next repeat drop listnode allocate throw {: node :} 0 node list-next ! c-addr u node list-value 2! node list-addr1 ! ; \end{verbatim} \hspace*{23cm}\raisebox{0cm}[0mm][0mm]{\wepsbox{listqueue}{3cm}} \end{minipage} \begin{minipage}[t]{15cm} \begin{verbatim} : list-poll {: list-addr -- c-addr u :} list-addr @ {: node :} node if node list-next @ list-addr ! node list-value 2@ node free throw else 0 0 then ; \ Example variable q 0 q ! "abc" q list-add "def" q list-add q list-poll type \end{verbatim} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Storage management} \begin{myitemize} \item Static allocation\\ \code{create allot}\\ Small systems ($<64$KB) \item Dynamic allocation with explicit deallocation\\ \code{allocate free} regions/arenas\\ Keep track of allocations: Memory leaks and double \code{free}\\ Medium systems % !! regions % !! $trings \item Dynamic allocation with automatic deallocation\\ \code{allocate} and garbage collection\\ Large systems ($>16$MB) \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Storage management and APIs} \begin{verbatim} read-line ( c-addr u1 fid -- u2 flag wior ) \end{verbatim} Reads a line from fid into the buffer at c-addr u1. Gforth supports all three common line terminators: LF, CR and CRLF. A non-zero wior indicates an error. A false flag indicates that 'read-line' has been invoked at the end of the file. u2 indicates the line length (without terminator): u2$<$u1 indicates that the line is u2 chars long; u2=u1 indicates that the line is at least u1 chars long, the u1 chars of the buffer have been filled with chars from the line, and the next slice of the line with be read with the next 'read-line'. If the line is u1 chars long, the first 'read-line' returns u2=u1 and the next read-line returns u2=0. \begin{verbatim} slurp-fid ( fid -- c-addr u ) \end{verbatim} c-addr u is the content of the file fid \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Types} \centerline{Who knows the type of data?} \vspace{1ex} \centerline{ \begin{tabular}{rr|c|c} &&\multicolumn{2}{c}{run-time system}\\ &&no&yes\\\hline \raisebox{-1ex}{compiler}&no&Forth&Python, Lisp\\ &yes&C, Pascal&C++, Java, Rust\\ \end{tabular}} \begin{myitemize} \item Type knowledge of the programmer (e.g., sorted array) \item uniformity (Lisp) vs.\ specialization (Java) \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Types: Checking} \begin{verbatim} 'a' 5 * \end{verbatim} \begin{myitemize} \item How do you find type errors in Forth? Testing! \item With a little experience type errors are easy to find.\\ experience in interpreting program output\\ experience in writing test cases\\ experience in writing programs for easy testability \item More intensive testing $\Rightarrow$ you also find other errors \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Types: Checking} \begin{quote} As programmers learned C with Classes or C++, they lost the ability to quickly find the ``silly errors'' that creep into C programs through the lack of checking. Further, they failed to take the precautions against such silly errors that good C programmers take as a matter of course. After all, ``such errors don't happen in C with Classes.'' Thus, as the frequency of run-time errors caused by uncaught argument type errors goes down, their seriousness and the time needed to find them goes up. \emph{Bjarne Stroustroup} \end{quote} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Types: Overloading} \begin{verbatim} int n; n*3 n @ 3 * float r; r*3.0 r f@ 3.0e f* int n; n<3 n @ 3 < unsigned u; u<3 u @ 3 u< \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Types: Advantages and disadvantages of Forth} \begin{myitemize} \item[$+$] More uniformity: Better reusability \item[$+$] Extensions as libraries that would need type system extension in other languages (OOP, meta-programming) \item[$+$] Less complexity, e.g., for containers \item[$-$] No type knowledge for garbage collection, marshalling etc. \item[$-$] For changes affecting many lines static type checking would be useful\\ Poor man's checking: Use new names for changed interfaces\\ New names allow gradual changes \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Object-oriented extension: features} \begin{myitemize} \item Dynamic Dispatch (virtual functions/methods) \item Instance Variables \item Single inheritance \item Static binding (C++: \code{A::m}) \item Basic class \code{object} \item \code{new} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Object-oriented extension: Usage (1)} \begin{verbatim} object class cell var text cell var len cell var x cell var y method init method draw end-class button :noname ( o -- ) >r r@ x @ r@ y @ at-xy r@ text @ r> len @ type ; button defines draw :noname ( addr u o -- ) >r 0 r@ x ! 0 r@ y ! r@ len ! r> text ! ; button defines init \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Object-oriented extension: Usage (2)} \begin{verbatim} button class end-class bold-button : bold 27 emit ." [1m" ; : normal 27 emit ." [0m" ; :noname bold [ button :: draw ] normal ; bold-button defines draw button new Constant foo s" thin foo" foo init page foo draw bold-button new Constant bar s" fat bar" bar init 1 bar y ! bar draw \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Object-oriented extension: source code} \begin{verbatim} : method ( m v -- m' v ) Create over , swap cell+ swap DOES> ( ... o -- ... ) @ over @ + @ execute ; : var ( m v size -- m v' ) Create over , + DOES> ( o -- addr ) @ + ; : class ( class -- class methods vars ) dup 2@ ; : end-class ( class methods vars -- ) Create here >r , dup , 2 cells ?DO ['] noop , 1 cells +LOOP cell+ dup cell+ r> rot @ 2 cells /string move ; : defines ( xt class -- ) ' >body @ + ! ; : new ( class -- o ) here over @ allot swap over ! ; : :: ( class "name" -- ) ' >body @ + @ compile, ; Create object 1 cells , 2 cells , \end{verbatim} Explanation: \code{https://bernd-paysan.de/mini-oof.html} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Object-oriented extension: explanation} \begin{minipage}[b]{12cm} \begin{verbatim} object class cell var text cell var len cell var x cell var y method init method draw end-class button button new Constant foo button class end-class bold-button bold-button new Constant bar \end{verbatim} \end{minipage}% \wepsbox{mini-oof}{14cm}\hfil \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Stateless control structures} \begin{verbatim} ... IF ... THEN ... IF ... ELSE ... THEN BEGIN ... WHILE ... REPEAT BEGIN ... UNTIL CASE ... OF ... ENDOF ... OF ... ENDOF ... ENDCASE ?DO ... LOOP \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Control structures: foundation} \centerline{ \begin{tabular}{r|r|r} & forwards & backwards \\\hline Unconditional branch& \code{AHEAD ( -- orig )} & \code{AGAIN ( dest -- )}\\ Conditional branch & \code{IF ( -- orig )} & \code{UNTIL ( dest -- )}\\ branch target & \code{THEN ( orig -- )} & \code{BEGIN ( -- dest )}\\ \end{tabular}} \begin{verbatim} : foo BEGIN ( C: dest ) ... IF ( C: dest orig ) ... THEN ( C: dest ) ... UNTIL ( C: ) ; \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Control Structures: ground floor} \begin{verbatim} : ELSE ( compilation: orig1 -- orig2 ; run-time: -- ) \ core POSTPONE ahead 1 cs-roll POSTPONE then ; immediate restrict : WHILE ( compilation: dest -- orig dest ; run-time: f -- ) \ core POSTPONE if 1 cs-roll ; immediate restrict : REPEAT ( compilation: orig dest -- ; run-time: -- ) \ core POSTPONE again POSTPONE then ; immediate restrict \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Control structures: Usage} \begin{verbatim} : foo ... if ( C: orig1 ) ... else ( C: orig2 ) ... begin ( C: orig2 dest ) ... while ( C: orig2 orig3 dest ) ... repeat ( C: orig2 ) then ; \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Macros} \begin{verbatim} : endif POSTPONE then ; immediate : foo ... if ... endif ... ; : (map) ( a n -- a a') cells over + swap ; : map< postpone (map) postpone ?do postpone i postpone @ ; immediate : >map 1 cells postpone literal postpone +loop ; immediate : step 0 array 1000 map< + >map drop ; \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Code generation: \texttt{LITERAL COMPILE,}} \begin{verbatim} : foo [ 5 cells ] literal ; : ]cells ] cells POSTPONE literal ; : foo [ 5 ]cells ; : twice ( xt -- ) dup compile, compile, ; : 2+ [ ' 1+ twice ] ; : 4* [ ' 2* twice ] ; \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Code generation: Gray} \begin{verbatim} : compile-test \ set -- ) postpone literal test-vector @ compile, ; : generate-alternative1 \ -- ) operand1 get-first compile-test postpone if operand1 generate postpone else operand2 generate postpone endif ; \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Implementation} \wepsbox{new-direct}{11cm}\hspace{1cm}\wepsbox{new-super}{17cm} \begin{myitemize} \item \code{see \emph{word}} \item \code{simple-see \emph{word}} \item \code{see-code \emph{word}} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Correctness and checking (one language)} \wepsline{checking}{20cm} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Correctness and checking (across languages)} \wepsline{checking-across}{20cm} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Reliability and security: common problems} \begin{itemize} \item Buffer overflow\\ \code{create buf 3 allot s" too long" buf swap move}\\ Countermeasure: bounds check \item Dangling reference, use-after-free, double-free\\ \verb|1 cells allocate throw dup value p value q|\\ \verb|p free throw 5 q ! \ use after free|\\ \verb|q free throw \ double free| \end{itemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Rust: Building} \begin{verbatim} cargo init myproject cd myproject emacsclient src/main.rs # edit cargo run # executable in target/debug/myproject \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Rust: Generalities} \begin{myitemize} \item Syntax: \verb|{}|, but many differences from C/C++/Java\\ \verb|let x = if a<0 { 5 } else { 6 };| % ";" is separator % expression-oriented, () if none; no ";" at end of block; ";" after "}" \item variables are immutable by default\\ \verb|let x = ...;| vs. \verb|let mut x = ...;|\\ Redefinition shadows without warning \item type inference, except at function boundary \item integer types: \code{i8}...\code{i128}, \code{isize}, \code{u8} ... \code{u128}, \code{usize}\\ no implicit conversion\\ default: \code{i32}, if type inference does not produce a type\\ \red{\code{let x=5\_000\_000\_000; // error}}\\ \code{let x=5\_000\_000\_000; let y:i64 = x; // ok} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Values on the Stack} \begin{myitemize} \item Values of fixed-size types can be on the stack \item Values on the stack can be \emph{copied}. \end{myitemize} \begin{verbatim} fn main() { let s = [3; 5]; let t = s; // copy let x = s[2]; println!("{x}"); } \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Stack and Heap} \centerline{\sepsbox{rust-string}{2}} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Heap and Ownership} \begin{myitemize} \item Each value on the heap has an owner. \item There can only be one owner at a time.\\ Values on the heap cannot be copied, assignment \emph{moves}.\\ Values on the heap can be explicitly cloned \item When the owner goes out of scope, the value will be dropped. \item Compiler complains only on usage. \end{myitemize} \begin{minipage}{15cm} \begin{verbatim} fn main() { let s1 = "hello".to_string(); let s2 = s1; // move println!("{s1}"); // Error } \end{verbatim} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Moving and Cloning} \centerline{\sepsbox{move-clone}{2}} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{References and Slices} \centerline{\sepsbox{rust-ref}{2}} \begin{myitemize} \item Reference lives only as long as the referenced value \item References important for parameter passing \item \emph{Borrowing} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Mutable References} \begin{myitemize} \item There can only be one! \item No unmutable references allowed to live simultaneously \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Last use ends liveness} \begin{verbatim} fn main() { let mut s = String::from("hello"); let r1 = &s; // no problem let r2 = &s; // no problem println!("{r1} and {r2}"); // Variables r1 and r2 will not be used after this point. let r3 = &mut s; // no problem println!("{r3}"); } \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Last use ends liveness} \begin{verbatim} fn first_word(s: &str) -> &str { let bytes = s.as_bytes(); for (i, &item) in bytes.iter().enumerate() { if item == b' ' { return &s[0..i]; } } &s[..] } fn main() { let my_string = String::from("hello world"); let word = first_word(&my_string[..]); println!("the first word is: {word}"); } \end{verbatim} %fn main() { % let my_string = String::from("hello world"); % % // `first_word` works on slices of `String`s, whether partial or whole. % let word = first_word(&my_string[0..6]); % let word = first_word(&my_string[..]); % // `first_word` also works on references to `String`s, which are equivalent % // to whole slices of `String`s. % let word = first_word(&my_string); % % let my_string_literal = "hello world"; % % // `first_word` works on slices of string literals, whether partial or % // whole. % let word = first_word(&my_string_literal[0..6]); % let word = first_word(&my_string_literal[..]); % % // Because string literals *are* string slices already, % // this works too, without the slice syntax! % let word = first_word(my_string_literal); %} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Related: Gforth \$trings} \begin{minipage}[b]{10cm} \begin{verbatim} variable s s $init s" hello" s $! s $@ type \end{verbatim} \end{minipage} \sepsbox{gforth-strings}{2} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Borrow checker} \begin{verbatim} fn main() { let r; { let x = 5; r = &x; // borrowed value does not live long enough } println!("r: {r}"); } \end{verbatim} \begin{myitemize} \item reference lives at most as long as its value \item variables must be initialized before use\\ but not necessarily at definition \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Borrow checker}\nointerlineskip \begin{minipage}{20cm} \begin{verbatim} fn main() { let string1 = String::from("abcd"); let result; // not mut; initialized in if if longest(&string1,"foo")=="abcd" { let string2 = "xyzab".to_string(); result = longest(string1.as_str(), &string2); // borrowed value does not live long enough } else { result = "baz"; } println!("The longest string is {result}"); } fn longest<'a>(x: &'a str, y: &'a str) -> &'a str { if x.len() > y.len() { x } else { y } } \end{verbatim} \end{minipage} \begin{minipage}{10cm} \begin{myitemize} \item Lifetime annotation \verb|'a|\\ for functions \item lifetime relations \item sometimes automatic:\\ per reference parameter \\ one input $\Rightarrow$ outputs\\ self $\Rightarrow$ outputs \item Initialization in \verb|if| \item \verb|'static| lifetime \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} struct Rectangle { width: u32, height: u32, } fn area(rectangle: &Rectangle) -> u32 { rectangle.width * rectangle.height } fn main() { let mut rect1 = Rectangle { height: 50, width: 30, }; println!( "The area of the rectangle is {}.", area(&rect1)); } \end{verbatim} \end{minipage} \begin{minipage}[t]{12cm} \begin{myitemize} \item Fields not mutable \item Struct vars may be mutable \item automatic dereferencing \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Struct methods}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} struct Rectangle { width: u32, height: u32, } impl Rectangle { // <------ fn area(&self) -> u32 { // <------ self.width * self.height // <------ } } fn main() { let rect1 = Rectangle { ... }; println!( "The area of the rectangle is {}.", rect1.area()); // <--------------- } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \verb|&self| is \verb|self: &Self| \item different syntax \item namespace organisation \item no dynamic dispatch\\ for now \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} struct ImportantExcerpt<'a> { part: &'a str, } fn main() { let novel = String::from("Call me Ishmael. Some years ago..."); let first_sentence = novel.split('.').next().unwrap(); let i = ImportantExcerpt { part: first_senence, }; println!("{}",i.part); } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item References in fields need lifetime \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Enumerations and pattern matching}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} enum Message { Quit, // no data Move { x: i32, y: i32 }, // struct Write(String), // tuple ChangeColor(i32, i32, i32), // tuple } fn main() { let m = Message::Write(String::from("hello")); let m = Message::Move{x:1, y:2}; match m { Message::Quit => println!("quit"), Message::Move { y:a, x } => println!("{a},{x}"), Message::Write(s) => println!("{s}"), Message::ChangeColor(_r, _g, _b) => return, } } \end{verbatim} \end{minipage} \vspace*{-2ex} \begin{minipage}[t]{13cm} \begin{myitemize} \item not just variables in patterns \item \code{match} requires all cases \item syntax for matching one case \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Option and Result}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} enum Option { None, Some(T), } enum Result { Ok(T), Err(E), } fn foo(...) -> Result { let file = File::open("foo.txt")?; let file_contents = ...; return Ok(file_contents); } \end{verbatim} \end{minipage} \begin{minipage}[t]{15cm} \begin{myitemize} \item No \code{NULL} \item No exceptions \item Conveniences for these types \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Panic! instead of Err Result}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} fn foo(...) -> Result { let file = File::open("foo.txt")?; let file_contents = ...; return Ok(file_contents); } fn foo(...) -> String { let file = File::open("foo.txt") .expect("foo.txt not found"); let file_contents = ...; return file_contents; } \end{verbatim} \end{minipage} % \begin{minipage}[t]{15cm} % \begin{myitemize} % \item % \item % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Vec}: growable arrays}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} fn main() { let mut v = vec![1, 2, 3, 4, 5]; let first = v[0]; v.push(6); println!("The first element is: {first}"); } fn main() { let mut v = vec![100, 32, 57]; for i in &mut v { *i += 50; } } \end{verbatim} \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Genericity}\nointerlineskip \begin{minipage}{20cm} \begin{verbatim} fn largest(list: &[T]) -> &T { let mut largest = &list[0]; for item in list { if item > largest { largest = item; } } largest } \end{verbatim} \end{minipage} \begin{minipage}{10cm} \begin{myitemize} \item Monomorphization \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Traits}\nointerlineskip \begin{minipage}{20cm} \begin{verbatim} pub trait Summary { fn summarize(&self) -> String; } pub struct NewsArticle { ... } impl Summary for NewsArticle { fn summarize(&self) -> String { ... } } \end{verbatim} \end{minipage} \begin{minipage}{10cm} \begin{myitemize} \item similar to interfaces \item no dynamic dispatch\\ for now \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Cost of Result vs. panic}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} fn fibr(n:usize) -> Result { match n { 0 => Ok(0), 1 => Ok(1), _ => { let s=fibr(n-2)?; let t=fibr(n-1)?; match s.overflowing_add(t) { (r,false) => Ok(r), (_,true) => Err(()) } } } } \end{verbatim} \end{minipage} \begin{minipage}[t]{15cm} \begin{verbatim} fn fibv(n:usize) -> usize { if n<2 { n } else { let s=fibv(n-2); let t=fibv(n-1); s.checked_add(t).unwrap() // s.wrapping_add(t) // s+t } } \end{verbatim} \nointerlineskip \vspace{1ex} \hspace*{-3cm}\begin{tabular}{rrr|l} % Rocketlake rust 1.89 --release, see fib cyc & inst. & br. & per return\\\hline %: num parse-name evaluate s>f 331160281e f/ 7 1 1 f.rdp ." & "; %: % cr num num num space parse-name type ; %% 2229316046 6165819460 1592609816 return %% 1579679750 4802090344 1159115416 panic %% 1775061079 4802090566 1159115492 match_strict %% 1531484093 4802090342 1159115409 if_strict %% 1208286288 3438360945 764709097 if_wrapping %% 1210923755 3438361472 764709272 if_default %% 1017339379 3296938109 662374761 count 6.7 & 18.6 & 4.8 & Result\\ 4.6 & 14.5 & 3.5 & \verb|s.checked_add(t).unwrap()|\\ 3.6 & 10.4 & 2.3 & \verb|s.wrapping_add(t)|, \code{s+t} \end{tabular} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Result vs. exceptions}\nointerlineskip \begin{myitemize} \item Result: additional per-return cost \item Exceptions: cost per (\code{try}...)\code{catch}? Forth: yes, JVM: no\\ With many cleanup blocks Forth's \code{catch} may cost more \item Exceptions: cost per not-taken \code{throw}: one branch \item Exceptions: cost per taken \code{throw}\\ Does it matter? It's an exception\\ Forth: a few cycles; JVM: more expensive (search for \code{catch}) \item Cost of exceptions in Forth\\ Setting up catch frame\\ checking on not-taken \code{throw} \item Cost of exceptions in Java\\ no catch frame\\ checking on not-taken \code{throw}\\ search for try block on taken \code{throw} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Cost of reference vs. owned}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} fn longestref<'a>(x: &'a str, y: &'a str) -> &'a str { if x.len() > y.len() { x } else { y } } fn longeststring(x: &str, y: &str) -> String { let r = if x.len() > y.len() { x } else { y }; r.to_string() } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} \begin{myitemize} \item average string length 128 bytes\\ not cheaper with 32 bytes\\ owned 25\% more expensive with 512 bytes \item \begin{tabular}{rr|l} %on Rocketlake with Rust 1.89 --release, see own_cost cyc & inst & per call (includes benchmarking overhead)\\\hline %: num parse-name evaluate parse-name evaluate + 10240000 / 6 .r ." & "; %: % cr num num parse-name 2drop space parse-name type ; % 61510933 1643623 184710480 1231662 27491 ref % 440559354 1030272 1926393388 998946 17528 string % 438373870 1025050 1912750330 983717 17145 string_samesize 6 & 18 & reference\\ 43 & 188 & owned \end{tabular} \item possibly more complex data structures in your program \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{(Smart) pointers (single-threaded)}\nointerlineskip \begin{myitemize} \item implement \code{Deref} (\code{deref()}) and \code{Drop} (\code{drop()}) \item you can implement your own smart pointers \item \code{Box}: heap-allocated, owned, usual borrowing restrictions \item \code{Rc} (reference-counted): multiple owners of data \item \code{RefCell}: mutability checked at run-time \item \code{Rc}: multiple owners of mutable data \item \code{Weak}: can avoid leaking pointer cycles \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Box}: Dereference}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} fn main() { let x = 5; let y = Box::new(x); assert_eq!(5, x); assert_eq!(5, *y); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Box}: Linked list}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} enum List { Cons(i32, Box), Nil, } use crate::List::{Cons, Nil}; fn main() { let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Define your own smart pointer: \code{Deref}}\nointerlineskip \begin{minipage}[t]{13cm} \begin{verbatim} use std::ops::Deref; impl Deref for MyBox { type Target = T; fn deref(&self) -> &T { &self.0 } } struct MyBox(T); impl MyBox { fn new(x: T) -> MyBox { MyBox(x) } } \end{verbatim} \end{minipage} \begin{minipage}[t]{17cm} \begin{verbatim} fn hello(name: &str) { println!("Hello, {name}!"); } fn main() { let m = MyBox::new(String::from("Rust")); hello(&m); } \end{verbatim} \end{minipage} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Rc}: multiple owners}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} enum List { Cons(i32, Rc), Nil, } use crate::List::{Cons, Nil}; use std::rc::Rc; fn main() { let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); let b = Cons(3, Rc::clone(&a)); let c = Cons(4, Rc::clone(&a)); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Rc}: multiple owners of mutable data}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} #[derive(Debug)] enum List { Cons(Rc>, Rc), Nil, } use crate::List::{Cons, Nil}; use std::cell::RefCell; use std::rc::Rc; fn main() { let value = Rc::new(RefCell::new(5)); let a = Rc::new(Cons(Rc::clone(&value), Rc::new(Nil))); let b = Cons(Rc::new(RefCell::new(3)), Rc::clone(&a)); let c = Cons(Rc::new(RefCell::new(4)), Rc::clone(&a)); *value.borrow_mut() += 10; println!("a: {a:?}, b: {b:?}, c: {c:?}"); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Cycles in pointered structures}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} use crate::List::{Cons, Nil}; use std::cell::RefCell; use std::rc::Rc; enum List { Cons(i32, RefCell>), Nil, } impl List { fn tail(&self) -> Option<&RefCell>> { match self { Cons(_, item) => Some(item), Nil => None, } } } \end{verbatim} \end{minipage}\vspace*{-1cm} \begin{minipage}[t]{15cm} \begin{verbatim} fn main() { let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil)))); let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a)))); if let Some(link) = a.tail() { *link.borrow_mut() = Rc::clone(&b); } } \end{verbatim} \end{minipage} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{\code{Weak}: to avoid memory leak}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} use std::cell::RefCell; use std::rc::{Rc, Weak}; #[derive(Debug)] struct Node { value: i32, parent: RefCell>, children: RefCell>>, } fn main() { let leaf = Rc::new(Node { value: 3, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]), }); \end{verbatim} \end{minipage} \begin{minipage}[t]{15cm} \begin{verbatim} println!("leaf parent = {:?}", leaf.parent.borrow().upgrade()); let branch = Rc::new(Node { value: 5, parent: RefCell::new(Weak::new()), children: RefCell::new( vec![Rc::clone(&leaf)]), }); *leaf.parent.borrow_mut() = Rc::downgrade(&branch); println!("leaf parent = {:?}", leaf.parent.borrow().upgrade()); } \end{verbatim} \end{minipage} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{trait objects}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} pub trait Draw { fn draw(&self); } pub struct Button0 { } impl Draw for Button0 { fn draw(&self) { println!("Button0"); } } // Button1 and Button2 similar fn main() { let mut v:Vec>=vec![]; v.push(Box::new(Button0{})); v.push(Box::new(Button2{})); v.push(Box::new(Button1{})); for i in v { i.draw(); } } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \code{draw()} of run-time struct called\\ dynamic dispatch (OOP) \item \code{:Vec>} necessary \item \code{Box} necessary \item \code{dyn} necessary \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Multiple traits and dynamic dispatch}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} pub trait Draw { fn draw(&self);} pub trait Bla { fn bla(&self); } trait DrawBla: Draw + Bla {} // Draw and Bla for Button0 impl DrawBla for Button0 {} // likewise for Button1 and Button2 fn main() { let mut v:Vec>=vec![]; v.push(Box::new(Button0{})); // ... for i in v { i.draw(); i.bla(); } } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \code{Draw} and \code{Bla} are\\supertraits of \code{DrawBla} \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Data representations and sizes}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} fn main() { use std::mem::{size_of,size_of_val, offset_of}; enum Enum0 { E0a(u8) } println!("Enum0: {}",size_of::()); let s = "bla".to_string(); println!("&*s: {}",size_of_val(&*s)); println!("&s: {}",size_of_val(&s)); struct Node { value: isize, parent: RefCell>, children: RefCell>>, } println!("{}",offset_of!(Node,value)); } \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item pointer only when necessary \item default: representation not\\defined\\ order of fields can vary\\ NULL optimization \item specific representations\\ C\\ others \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Data sizes}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} 1 enum Enum0 { E0a(u8) } 2 enum Enum1 { E1a(u8), E1b } 16 enum Enum2 { E2a(u64), E2b } 8 enum Enum3<'a> { E3a(&'a u8), E3b } 16 enum Enum4<'a> { E4a(&'a u8), E4b, E4c } 16 enum List3 {Cons(isize, Box), Nil3 } 16 enum List0 { Cons0(isize, Rc), Nil0 } 16 enum List1 { Cons1(Rc>, Rc), Nil1 } 24 enum List2 { Cons2(i32, RefCell>), Nil2 } 56 struct Node { value: isize, parent: RefCell>, children: RefCell>> } offsets: value: 48, parent: 32, children: 0 8 Rc 24 Vec> 32 RefCell>> 16 Box 3 &*s // let s = "bla".to_string(); \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Unsafe Rust}\nointerlineskip % \begin{minipage}[t]{17cm} %\begin{verbatim} %\end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} \begin{myitemize} \item Promise from programmer that invariants are kept \item Safe abstraction over unsafe code \item ``Unsafe superpowers'' \begin{myitemize} \item Dereference a raw pointer \item Call an unsafe function or method \item Access or modify a mutable static variable \item Implement an unsafe trait \item Access fields of unions \end{myitemize} \item Run-time checking with Miri \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Example: \code{unsafe}}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} use std::slice; fn split_at_mut(values: &mut [i32], mid: usize) -> (&mut [i32], &mut [i32]) { let len = values.len(); let ptr = values.as_mut_ptr(); assert!(mid <= len); unsafe { ( slice::from_raw_parts_mut(ptr, mid), slice::from_raw_parts_mut(ptr.add(mid), len - mid) ) } } fn main() { let mut vector = vec![1, 2, 3, 4, 5, 6]; let (left, right) = split_at_mut(&mut vector, 3); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Example: \code{unsafe}}\nointerlineskip % \begin{minipage}[t]{17cm} \begin{verbatim} unsafe extern "C" { safe fn abs(input: i32) -> i32; } fn main() { println!("Absolute value of -3 according to C: {}", abs(-3)); } \end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Concurrent programming}\nointerlineskip % \begin{minipage}[t]{17cm} %\begin{verbatim} %\end{verbatim} % \end{minipage} % \begin{minipage}[t]{13cm} \begin{myitemize} \item parallel: two CPUs work on different data \item concurrent: two threads work on the same data\\ dining philosophers \item race conditions \item deadlocks \end{myitemize} \slidetitle{... in Rust}\nointerlineskip \begin{myitemize} \item high level: channels \code{std::sync::mpsc} \item medium level: \code{Mutex},\code{Arc} \item low level: \code{std::sync::atomic} memory accesses \item \code{async}/\code{await}: concurrency within a thread \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Multiple threads with channels}\nointerlineskip \begin{minipage}[t]{19cm} \begin{verbatim} use std::sync::mpsc; use std::thread; use std::time::Duration; fn main() { let (tx, rx) = mpsc::channel(); thread::spawn(move || { let vals = vec!["hi","from","the","thread"]; for val in vals { tx.send(val.to_string()).unwrap(); thread::sleep(Duration::from_secs(1)); } }); for received in rx { println!("Got: {received}"); } } \end{verbatim} \end{minipage}\vspace*{-0.8cm} \begin{minipage}[t]{11cm} \begin{myitemize} \item \code{spawn} starts thread\\ \code{move} data to thread \item \code{join} waits for finish \item \code{recv} (not here) \item receiver as iterator \item multiple producers\\ with \code{tx.clone()} \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{threads vs. async}\nointerlineskip \begin{minipage}[t]{18cm} \begin{verbatim} use std::sync::mpsc; use std::thread; fn main() { let (tx, rx) = mpsc::channel(); let mut handles = vec![]; for i in 0..100000 { let tx1 = tx.clone(); let handle = thread::spawn(move || { tx1.send(i.to_string()).unwrap(); }); handles.push(handle); } for handle in handles { handle.join().unwrap(); } drop(tx); for received in rx { println!("Got: {received}"); } } \end{verbatim} \vspace*{-1cm} \end{minipage} \begin{minipage}[t]{12cm} \begin{myitemize} \item 2.5s elapsed \item 4.66s CPU time \item 1.84 CPUs used \item thread spawn overhead \item not efficient for short tasks \item limit active threads \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{threads vs. async}\nointerlineskip \begin{minipage}[t]{19cm} \begin{verbatim} fn main() { trpl::run(async { let (tx, mut rx) = trpl::channel(); let mut futures = vec![]; for i in 0..100000 { let tx1 = tx.clone(); let tx1_fut = async move { tx1.send(i.to_string()).unwrap(); }; futures.push(tx1_fut); } trpl::join_all(futures).await; drop(tx); while let Some(value) = rx.recv().await { println!("Got: {value}"); } }); } \end{verbatim} \end{minipage} \begin{minipage}[t]{11cm} \begin{myitemize} \item 0.04s elapsed \item 0.04s CPU time \item 1.00 CPUs used \item use for short tasks \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Linked list queue}\nointerlineskip \begin{minipage}[t]{15cm} \begin{verbatim} pub struct List { head: Link } type Link = Option>>; struct Node { elem: T, next: Link, } impl List { pub fn new() -> Self { List { head: None } } pub fn pop(&mut self) -> Option { self.head.take().map(|node| { self.head = node.next; node.elem }) } \end{verbatim} \vspace*{-0.5cm} \end{minipage} \begin{minipage}[t]{15cm} \begin{verbatim} fn getp(&mut self) -> &mut Link { let mut l = &mut self.head; while let Some(s)=l { l = &mut s.next; }; l } pub fn add(&mut self, elem: T) { *self.getp() = Some(Box::new( Node {elem, next: None})); } } \end{verbatim} \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} % \slidetitle{Proper linked list queue}\nointerlineskip \begin{minipage}[t]{14cm} \begin{verbatim} use std::ptr; pub struct List { head: Link, tail: *mut Node } type Link = *mut Node; struct Node { elem: T, next: Link } impl List { pub fn new() -> Self { List { head: ptr::null_mut(), tail: ptr::null_mut() } } pub fn add(&mut self, elem: T) { unsafe { let new_tail = Box::into_raw(Box::new(Node { elem: elem, \end{verbatim} \vspace*{-1cm} \end{minipage} \begin{minipage}[t]{16cm} \begin{verbatim} next: ptr::null_mut() })); if !self.tail.is_null() { (*self.tail).next = new_tail; } else { self.head = new_tail; } self.tail = new_tail; } } pub fn pop(&mut self) -> Option { unsafe { if self.head.is_null() { None } else { let head = Box::from_raw(self.head); self.head = head.next; if self.head.is_null() { self.tail = ptr::null_mut(); } Some(head.elem) } } } } \end{verbatim} \vspace*{-1cm} \end{minipage} % \begin{minipage}[t]{13cm} % \begin{myitemize} % \item % \end{myitemize} % \end{minipage} \end{slide} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document} Learning outcomes After successful completion of the course, students are able to design, write and debug programs in low-level programming languages. to know when developing such programs is appropriate. to understand the security challenges of low-level programs. Subject of course The role of low-level programming in the software ecosystem Limits of high-level programming: operating systems, drivers, run-time systems, efficiency. Various forms of memory allocation (static, explicit deallocation, automatic deallocation). Security and reliability problems of low-level programming Programming in Forth (interactive low-level programming) Programming in Rust (mostly-safe low-level programming) Methods and tools, in particular for debugging Teaching methods Lectures on the contents of the course. Programming exercises in Forth. Programming exercises in Rust. A group of students develops a small project in a low-level language and presents it. Concurrent vs. parallel programming errors: race conditions, deadlocks, livelocks Rust approach spawn moving data join channels send recv receiver as iterator multiple producers with tx.clone() Mutex use std::sync::mpsc; use std::thread; use std::time::Duration; fn main() { let (tx, rx) = mpsc::channel(); thread::spawn(move || { let vals = vec!["hi","from","the","thread"]; for val in vals { tx.send(val.to_string()).unwrap(); thread::sleep(Duration::from_secs(1)); } }); for received in rx { println!("Got: {received}"); } } enum List { Cons(i32, Rc), Nil, } use crate::List::{Cons, Nil}; use std::rc::Rc; // --snip-- fn main() { let a = Rc::new(Cons(5, Rc::new(Cons(10, Rc::new(Nil))))); println!("count after creating a = {}", Rc::strong_count(&a)); let b = Cons(3, Rc::clone(&a)); println!("count after creating b = {}", Rc::strong_count(&a)); { let c = Cons(4, Rc::clone(&a)); println!("count after creating c = {}", Rc::strong_count(&a)); } println!("count after c goes out of scope = {}", Rc::strong_count(&a)); } Weak references: use std::cell::RefCell; use std::rc::{Rc, Weak}; #[derive(Debug)] struct Node { value: i32, parent: RefCell>, children: RefCell>>, } fn main() { let leaf = Rc::new(Node { value: 3, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]), }); println!("leaf parent = {:?}", leaf.parent.borrow().upgrade()); let branch = Rc::new(Node { value: 5, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![Rc::clone(&leaf)]), }); *leaf.parent.borrow_mut() = Rc::downgrade(&branch); println!("leaf parent = {:?}", leaf.parent.borrow().upgrade()); } #[derive(Debug)] debug! fn main() { let mut v = vec![1, 2, 3, 4, 5]; let first = v[0]; v.push(6); println!("The first element is: {first}"); } fn main() { let mut v = vec![100, 32, 57]; for i in &mut v { *i += 50; } } fn main() { use std::collections::HashMap; let mut scores = HashMap::new(); scores.insert("Blue", 10); scores.insert("Yellow", 50); for (key, value) in &scores { println!("{key}: {value}"); } } fn main() { use std::collections::HashMap; let mut scores = HashMap::new(); scores.insert(String::from("Blue"), 10); scores.entry(String::from("Yellow")).or_insert(50); scores.entry(String::from("Blue")).or_insert(50); println!("{scores:?}"); } use std::fs::File; fn main() { let greeting_file = File::open("hello.txt").unwrap(); } no exceptions #![allow(unused)] fn main() { use std::fs::File; use std::io::{self, Read}; fn read_username_from_file() -> Result { let mut username_file = File::open("hello.txt")?; let mut username = String::new(); username_file.read_to_string(&mut username)?; Ok(username) } } #![allow(unused)] fn main() { use std::fs::File; use std::io::{self, Read}; fn read_username_from_file() -> Result { let mut username = String::new(); File::open("hello.txt")?.read_to_string(&mut username)?; Ok(username) } } Error handling: exceptions vs. panic/Result fn largest(list: &[T]) -> &T { let mut largest = &list[0]; for item in list { if item > largest { largest = item; } } largest } fn main() { let number_list = vec![34, 50, 25, 100, 65]; let result = largest(&number_list); println!("The largest number is {result}"); let char_list = vec!['y', 'm', 'a', 'q']; let result = largest(&char_list); println!("The largest char is {result}"); } Monomorphization struct Rectangle { width: u32, height: u32, } fn main() { let mut rect1 = Rectangle { width: 30, height: 50, }; let mut v: u32 = 3; setfield(& mut rect1.height,40); setfield(& mut v, 5); println!( "The area of the rectangle is {} square pixels and v has value {v}.", area(&rect1) ); } fn area(rectangle: &Rectangle) -> u32 { rectangle.width * rectangle.height } fn setfield(field: & mut u32, v: u32) { *field = v; } enumerations vs. dynamic dispatch %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \end{myitemize} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Structs}\nointerlineskip \begin{minipage}[t]{17cm} \begin{verbatim} \end{verbatim} \end{minipage} \begin{minipage}[t]{13cm} \begin{myitemize} \item \end{myitemize} \end{minipage} \end{slide} \begin{slide} \slidetitle{} \begin{myitemize} \item \item \item \end{myitemize} \end{slide} \begin{slide} \slidetitle{} \begin{myitemize} \item \item \item \end{myitemize} \end{slide} \begin{slide} \slidetitle{} \begin{myitemize} \item \item \item \end{myitemize} \end{slide} \begin{slide} \slidetitle{} \begin{myitemize} \item \item \item \end{myitemize} \end{slide} \begin{slide} \slidetitle{} \begin{myitemize} \item \item \item \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Interpretation, Compilation, and Execution} \begin{verbatim} \ Compilation : hello ( -- ) ." hello, world" ; \ Interpretation .( hello, world) \ Interpretation and execution hello \end{verbatim} Interpretation \begin{myitemize} \item exists in Forth, Postscript, Lisp, Prolog, Python, ... \item does not exist in Fortran, C, C++, Java, Rust, ... \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{No hard boundary between compile time and run time} ... in the languge; there may be one in the head of the programmer.\\ No executable file; many systems have an image file. \begin{myitemize} \item Initialize data structures \item Macros: Execution during compilation \item Run-time code generation: optimization or simplification \end{myitemize} C++ has a separate programming language for macros (template language) \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Initialization} \begin{verbatim} /* C */ int a[] = {235,1857}; /* C, alternative */ int a[2]; a[0]=foo(2); a[1]=bar(3); \ Forth create a 2 foo , 3 bar , \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Quines} Programs that print themselves; the shorter the better. \begin{verbatim} source type \end{verbatim} By avoiding the use of certain Forth features, we get a variety of quines:\\ \texttt{http://www.complang.tuwien.ac.at/forth/quines.html} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Name Binding} \begin{myitemize} \item What happens if a name is redefined? \item Algol (C, Java, ...): Compilation error \item Lisp, Postscript: Dynamic Name Binding\\ The new definition replaces the old one completely \item Forth: Static name binding\\ The old definition still exists\\ Old uses use the old definition\\ New uses use the new definition \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Name binding: Collision} \begin{myitemize} \item Frequent case: programmer defines name $x$, library is extended by $x$: \begin{verbatim} ( in main ) require lib1.fs ( in lib1.fs ) require lib2.fs ( in lib2.fs ) : x ." x1" ; ( in lib1.fs ) : y x ; ( in main ) : x ." x2" ; ( in main ) x \ outputs "x2" ( in main ) y \ outputs "x1" \end{verbatim} \item Algol: Compile-time error \item Lisp: Library 1 executes the wrong function $x$; run-time error or worse \item Forth: Warning at compile time, program works \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Namensbindung: problems and solutions} \begin{myitemize} \item Collisions: conventions (C), namespaces (C++) \begin{verbatim} #define _POSIX_C_SOURCE 199506L #include \end{verbatim} \item Collisions: dictionaries (Postscript) \item Forward declarations: \code{defer} (Forth) \begin{verbatim} defer foo : bar ... foo ... ; :noname ... bar ... ; is foo \end{verbatim} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Gforth: generalized guarded commands} \begin{minipage}{12cm} \begin{verbatim} case ... ?of ... endof ... ?of ... contof ... next-case \ or "0 endcase" \end{verbatim} \end{minipage} \begin{minipage}{15cm} \begin{verbatim} : gcd ( n1 n2 -- n ) case 2dup > ?of tuck - contof 2dup < ?of over - contof ( n n' ) endcase ; : collatz ( u -- ) case dup . 1 of endof dup 1 and ?of 3 * 1+ contof 2/ next-case ; \end{verbatim} \end{minipage} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Forth-philosophy} \begin{myitemize} \item actually Chuck Moore's philosophy \item \emph{Keep it simple!} \item \emph{Do not speculate!}\\ do not generalize\\ do not design for reuse\\ only take steps when necessary \item \emph{Do it yourself!}\\ no libraries \item \emph{Do not bury your tools!} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Postscript} \begin{myitemize} \item Syntax \begin{myitemize} \item \verb|( ) < > [ ] { } / %| are delimiters \item \verb|<< >>| are lexemes \item \verb|( )| surround strings; balance parentheses, or use \verb|\) \(| \end{myitemize} \item Types \begin{myitemize} \item Types known at run-time \item Operators work on several types \item Type checking at run-time \item Limited non-static stack depth when building an array \end{myitemize} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Postscript: types} \centerline{ \begin{tabular}{c|>{\tt}c} Typ &{\rm Beispiel-Literal} \\\hline integer &1 \\ real &1.0 \\ boolean &true \\ name &/name \\ mark &[ \\ null &null \\ operator &/add load \\ fontID & \\ save & \\\hline array &[1 2] \\ string &(string) \\ dictionary &<< index1 wert1 index2 wert2 ... >>\\ file & \\ \end{tabular}} \begin{myitemize} \item simple types: value semantics \item composite types: reference semantics (shallow copying) \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Attributes: literal und executable objects} \hspace{1ex} \centerline{ \begin{tabular}{c|>{\tt}c|>{\tt}c} Typ&{\rm executable example}&{\rm executable literal}\\\hline Name &name &/name\\ Operator &//add &/add load\\ Array &\{dup mul\} &[ 1 2 ]\\ \end{tabular} } \begin{myitemize} \item Attribute of object in addition to type \item Executing a literal object pushes it on the stack \item Executing an executable object has a type-specific effect \item Difference between direct and indirect execution \item Attributes are ignored when the object is treated as data (most operations) \item Further attribute: access \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Procedures and arrays} \begin{myitemize} \item Procedures are executable arrays \item Syntactically different\\ \verb|{ 1 2 add }|\\ \verb|[ 1 2 add ]| \item Binding a procedure to a name\\ and executing the name executes the procedure indirectly\\ Also with \code{exec}, \code{if} etc. \item Indirect execution of a procedure:\\ Elements of the procedure are executed \emph{directly} \item Direct execution of a procedure:\\ push it on the stack \end{myitemize} \begin{verbatim} /x { { 1 2 add } } def x exec \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Control Structures} Operators that take (usually) procedures as parameters \begin{verbatim} a 0 lt { 1 == } if a 0 lt { 1 == } { 2 == } ifelse 5 1 10 { == } for 5 2 10 { == } for [ 1 7 3 ] { == } forall << /c 1 /a 2 /b 3 >> { == == } forall 4 { (abc) = } repeat 5 { dup 0 lt { exit } if dup = 1 sub } loop pop \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Names and dictionaries} \begin{myitemize} \item \verb|/squared {dup mul} def| \item By executing \code{squared}, the procedure is executed indirectly\\ $\Rightarrow$ its elements are executed directly \item Definition is stored in current dictionary \item dictionary corresponds to Forth's wordlist \item Dictionary stack corresponds to Forth's search order \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Name binding} \begin{myitemize} \item name binding at run-time\\ \verb|/foo {bar} def /bar {1} def| \item Usage for local variables\\ \verb|/foo { << /a rot >> begin ... a ... end } def| \item Dynamic scoping\\ \verb|<< /a 5 >> begin { a } end exec | gives an error\\ Most languages support static scoping only \item Similar to environment-variables in Unix \begin{verbatim} /foo { ... conf ... } def << /conf { 5 } >> begin foo end << /conf { x } >> begin foo end \end{verbatim} \end{myitemize} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Comparison} \begin{verbatim} /v [ 0 1 999 {} for ] def /step {0 v { add } forall} def 100000 {step pop} repeat : (map) ( a n - a a') cells over + swap ; : map[ postpone (map) postpone ?do postpone I postpone @ ; immediate : ]map 1 cells postpone literal postpone +loop ; immediate create array 1000 cells allot : init 1000 0 DO I array I cells + ! LOOP ; init : step 0 array 1000 map[ + ]map drop ; : bench 100000 0 DO step LOOP ; bench \end{verbatim} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Document Structuring Conventions} \begin{verbatim} %!PS-Adobe-2.0 %%Creator: dvips(k) 5.95a Copyright 2005 Radical Eye Software %%Title: slides.dvi %%Pages: 4 0 %%PageOrder: Ascend %%Orientation: Landscape %%BoundingBox: 0 0 595 842 %%DocumentFonts: LCMSS8 CMTT8 CMSY8 CMMI8 LCMSSI8 LCMSSB8 CMSY10 %%DocumentPaperSizes: a4 %%EndComments ... ProcSets ... ... Fonts ... ... Setup ... %%Page: (0,1,2,3,4,5,6,7) 1 ... Postscript Code ... %%Page: (8,9,10,11,12,13,14,15) 2 ... unabhängig von anderen Seiten %%Trailer ... %%EOF \end{verbatim} Example:\\ Source: \url{https://www.complang.tuwien.ac.at/anton/lvas/ertl%26pirker97.txt}\\ Result: \url{https://www.complang.tuwien.ac.at/papers/ertl%26pirker97.ps.gz} \end{slide} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{slide} \slidetitle{Encapsulated Postscript} \begin{myitemize} \item Usually for graphics \item Is included in other documents \item Examples: \url{https://www.complang.tuwien.ac.at/anton/eps-gallery} \end{myitemize} \begin{verbatim} %!PS-Adobe-3.0 EPSF-3.0 %%BoundingBox: 90 651 387 709 ... Prolog ... %%Page: 1 1 ... Nur eine Seite, meist ohne showpage ... \end{verbatim} \end{slide} \end{document}