%\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<T> {
    None,
    Some(T),
}

enum Result<T, E> {
    Ok(T),
    Err(E),
}

fn foo(...) -> Result<String, io::Error> {
  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<String, io::Error> {
  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<T>}: 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<T: std::cmp::PartialOrd>(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<usize,()> {
    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<T>}: heap-allocated, owned, usual borrowing restrictions
  \item \code{Rc<T>} (reference-counted): multiple owners of data
  \item \code{RefCell<T>}: mutability checked at run-time
  \item \code{Rc<RefCell<T>}: multiple owners of mutable data
  \item \code{Weak<T>}: can avoid leaking pointer cycles
  \end{myitemize}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
  \slidetitle{\code{Box<T>}: 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<T>}: Linked list}\nointerlineskip
%  \begin{minipage}[t]{17cm}
\begin{verbatim}
enum List {
    Cons(i32, Box<List>),
    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<T> Deref for MyBox<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.0
    }
}
struct MyBox<T>(T);
impl<T> MyBox<T> {
    fn new(x: T) -> MyBox<T> {
        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<T>}: multiple owners}\nointerlineskip
%  \begin{minipage}[t]{17cm}
\begin{verbatim}
enum List {
    Cons(i32, Rc<List>),
    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<RefCell<T>}: multiple owners of mutable data}\nointerlineskip
%  \begin{minipage}[t]{17cm}
\begin{verbatim}
#[derive(Debug)]
enum List {
    Cons(Rc<RefCell<i32>>, Rc<List>),
    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<Rc<List>>),
    Nil,
}
impl List {
    fn tail(&self) ->
           Option<&RefCell<Rc<List>>> {
        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<T>}: 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<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}
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<Box<dyn Draw>>=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<Box<dyn Draw>>} 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<Box<dyn DrawBla>>=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::<Enum0>());
    let s = "bla".to_string();
    println!("&*s: {}",size_of_val(&*s));
    println!("&s: {}",size_of_val(&s));
    struct Node {
        value: isize,
        parent: RefCell<Weak<Node>>,
        children: RefCell<Vec<Rc<Node>>>,
    }
    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<List3>), Nil3 }
16 enum List0 { Cons0(isize, Rc<List0>), Nil0 }
16 enum List1 { Cons1(Rc<RefCell<i32>>, Rc<List1>), Nil1 }
24 enum List2 { Cons2(i32, RefCell<Rc<List2>>), Nil2 }
56 struct Node { value: isize, parent: RefCell<Weak<Node>>,
        children: RefCell<Vec<Rc<Node>>> }
   offsets: value: 48, parent: 32, children: 0
 8 Rc<Node>
24 Vec<Rc<Node>>
32 RefCell<Vec<Rc<Node>>>
16 Box<dyn Draw>
 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<T>},\code{Arc<T>}
  \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<T> { head: Link<T> }
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
    elem: T,
    next: Link<T>,
}
impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }
    pub fn pop(&mut self) -> Option<T> {
        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<T> {
        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<T> {
    head: Link<T>,
    tail: *mut Node<T> }
type Link<T> = *mut Node<T>;
struct Node<T> {
    elem: T,
    next: Link<T> }
impl<T> List<T> {
  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<T> {
    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<List>),
    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<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

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<String, io::Error> {
    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<String, io::Error> {
    let mut username = String::new();

    File::open("hello.txt")?.read_to_string(&mut username)?;

    Ok(username)
}
}

Error handling: exceptions vs. panic/Result


fn largest<T: std::cmp::PartialOrd>(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 <unistd.h>
\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}
