1_Paradigms.tex

\section{Paradigms}

\begin{breakbox}
\textbf{Imperative:}
\begin{itemize}
	\item How program operates
	\item Statements, change a programs state
	\item Program = Seq. of statements
	\item Computation = Change of state
\end{itemize}
\textbf{Declarative:}
\begin{itemize}
	\item Logic of computation without describing its control flow
	\item No side effects
	\item Program = theories of formal logic
	\item Computation = deductions
\end{itemize}
\end{breakbox}

\begin{breakbox}
\textbf{Logic Programming:}
\begin{mdframed}
  \begin{center}
  	Computation: Proof of Predicate 
  \end{center}
\end{mdframed}

$mensch(sokrates)$ \\
$\forall mensch(x) \implies sterblich(x)$ \\
$sterblich(sokrates)$\\

\textbf{Prolog:}
\vspace{-5mm}
\begin{minted}[mathescape, numbersep=5pt, frame=lines,framesep=2mm, fontsize=\scriptsize]{prolog}
mensch(sokrates).
sterblich(X):-mensch(X).
?-sterblich(X) % X = sokrates
\end{minted}
\textbf{Prolog Syntax:}\\
\emph{Fakten:} \mintinline{prolog}{bhf(bern)}\\
\emph{Variable (X)}: \mintinline{prolog}{verb(X,Y)}\\
\emph{Regeln (Head:-Body):}\\ \mintinline{prolog}{verb(X,Y) :- bhf(X),bhf(Y)}\\
Head gilt, wenn \underline{alle} Bedingung des Body wahr sind\\
\emph{Lists:}\mintinline{prolog}{[a,b,c] [], [a|[b,c]]}\\

\textbf{Unifikation:}\\
$f(a,X,g(X)) \implies f(a,b,Y)$\\
$\text{with: } \{X/b, Y/g(b)\}$\\

%\textbf{Prolog Example:}\\
%\vspace{-5mm}
\begin{prologcode}
% LISTS
% [1,2,3] = [1,2,3].
% [1,2,3] = [1|[2,3]].
% [1,2,3] = [1,2,3|[]].

member(M,[M|_]).
member(M,[_|T]) :- member(M,T).
% member(a,[a,b,c,d]).
% member(X,[a,b,c,d]).
% member(a,X).

append([],Y,Y).
append([H|X],Y,[H|Z]) :- append(X,Y,Z).
% append([a,  b,  c],  [1,  2,  3],  _G518) 
% append([b,  c],  [1,  2,  3],  _G587) 
% append([c],  [1,  2,  3],  _G590) 
% append([],  [1,  2,  3],  _G593) 
% _G518 = [a|_G587] = [a|[b|_G590]] =[a|[b|[c|_G593]]]

perm([],[]).
perm(L,[H|T]) :- append(V,[H|U],L), append(V,U,W), perm(W,T).

% perm([1,2,3],X).

sorted([]).
sorted([_]).
sorted([H1,H2|T]) :- H1 =< H2, sorted([H2|T]).

% sorted([1,2,3,4]).
% sorted([1,2,30,4]).

n_sort(L,SL) :- perm(L,SL), sorted(SL).

% n_sort([2,1],X).
% n_sort([2,1,0,5,3,4],X).

% zuege
verbindung(StadtA, StadtZ, GAbfZ, Wie) :-
verbindung(StadtA, StadtZ, GAbfZ, [StadtA], Wie). %interface
verbindung(StadtA, StadtA, GAbfZ, S, []). % S rembers already visited
verbindung(StadtA, StadtZ, GAbfZ, S, [(Num,StadtT)|Wie]):-
zug(StadtA, StadtT, AbfZ, AnkZ, Num),
\+ member(StadtT, S),
AbfZ >= GAbfZ,
verbindung(StadtT, StadtZ, AnkZ, [StadtT|S], Wie).
\end{prologcode}
\end{breakbox}

\begin{breakbox}
\textbf{Functional Programming:}
\begin{mdframed}
  \begin{center}
  	Computation: Evaluation of mathematical Functions
  \end{center}
\end{mdframed}
\emph{Why declarative?}
\begin{itemize}
	\item Programming done with expression
	\item Foundation: lambda calculus
	\item no (or controlled) mutable state
\end{itemize}
\emph{Lambda calculus:} Formalisation of the concept of a math. function. Function as a Relation between 1 input and \underline{exactly} 1 output \\\\
\emph{No mutable state:}
\begin{itemize}
	\item \underline{Referential Transparency/Purity} $f(x)$ only depends on the definition of $f$ and the value $x$
	\item No mutable variables
	\item No assignements
	\item No imperative control structures
	\item All data structures are immutable\\
\end{itemize}
\emph{Functions as first-class citizen:}
\begin{itemize}
	\item Funcs can be anonymous ($\lambda x.x+1$)
	\item Funcs can be the input/output to other \emph{higher-order} Functions
	\item Funcs can be composed ($f \circ g$)
\end{itemize}
\end{breakbox}

\begin{breakbox}
\textbf{Expression Evaluation Stategies:}
\emph{Call by Value}
\begin{itemize}
	\pro Params evaluated only once
	\con All Params evaluated (even unused)
	\con May not terminate\\
\end{itemize}
\emph{Call by Name}
\begin{itemize}
	\con Params evaluated multiple times
	\pro Unused Params not evaluated
	\pro Terminates if there is a terminating strategy (e.g. base case)\\
\end{itemize}
\emph{Never-terminating-strategy:} recursion without base case \\
\emph{Terminates-by-name:} \mintinline{haskell}{if true then o else infloop}\\
\emph{Haskell's evaluation strategy:}\\\underline{Lazy Evaluation}, call-by-name and rember past evaluations
\end{breakbox}

\begin{breakbox}
\textbf{Haskell ADTs:}\\
\emph{With type parameters}
\vspace{-5mm}
\begin{minted}[mathescape, numbersep=5pt, frame=lines,framesep=2mm, fontsize=\scriptsize]{haskell}
data Lst a = Nil | Cons a (Lst a)
Lst :: * -> * 		-- type ctor
Nil :: Lst a 		 -- term
Cons :: a -> Lst a -> Lst a   -- term

data Maybe a = Nothing | Just a
Maybe :: * -> *
Nothing :: Maybe a
Just :: a -> Maybe a
\end{minted}
\emph{Without type parameters}
\vspace{-5mm}
\begin{minted}[mathescape, numbersep=5pt, frame=lines,framesep=2mm, fontsize=\scriptsize]{haskell}
data Bool = True | False --type
True :: Bool  -- term
False :: Bool -- term
\end{minted}
\end{breakbox}

\begin{breakbox}
\textbf{Polymorphism:}\\
\emph{Variants}
\begin{itemize}
	\item Ad-hoc: function with the same name denotes different implementations (function overloading)
	\item Parametric: Code written to work with many possible types (OO:generics)
	\item Subtype: one type (subtype) can be substituted for another (supertype)
\end{itemize}
\emph{Haskell's Polymorphism}
\begin{itemize}
	\item Implemented with type classes
	\item Parametric: \mintinline{haskell}{id :: a -> a} works with all types
	\item Ad-hoc: \mintinline{haskell}{Eq Bool, Eq Int} type classes: different instances of type clases denote different implementations
\end{itemize}
\begin{haskellcode}
-- type class Eq instance for Lst and Tree
--
data Lst a = Nil | Cons a (Lst a)
data Tree a = EmptyTree | Node a (Tree a) (Tree a)

-- lstEq :: Eq a => Lst a -> Lst a -> Bool
lstEq Nil Nil = True
lstEq (Cons x xs) (Cons y ys) = (x == y) && (lstEq xs ys)

instance Eq a => Eq (Lst a) where
	xs == ys  =  lstEq xs ys

-- treeEq :: Eq a => Tree a -> Tree a -> Bool
treeEq EmptyTree EmptyTree = True
treeEq (Node x xl xr) (Node y yl yr) = (x == y) 
			&& (treeEq xl yl) && (treeEq xr yr)

instance Eq a => Eq (Tree a) where
	(==)  =  treeEq
\end{haskellcode}
\end{breakbox}

\begin{breakbox}
\textbf{Haskell ADT Examples}
\begin{haskellcode}
data Lst a = Nil | Cons a (Lst a) deriving (Show, Eq)

--len :: Num a => Lst t -> a
len Nil = 0
len (Cons hd tl) = 1 + len tl
--mem :: Eq a => a -> Lst a -> Bool
mem e Nil = False
mem e (Cons hd tl) = (e == hd) || (mem e tl)
--appd
appd e Nil = Cons e Nil
appd e (Cons hd tl) = Cons hd (appd e tl)
--nth
nth :: Int -> Lst a -> Maybe a
nth n Nil = Nothing
nth n (Cons xs x) | n == 1 = (Just xs)
                  | otherwise = nth (n-1) x
--prod
prod :: Num a => Lst a -> a
prod Nil = 1
prod (Cons hd tl) = hd * prod tl
--disj --conj: replace || with &&
disj :: Lst Bool -> Bool
disj Nil = False
disj (Cons hd tl) = hd || (disj tl)
--mapp
mapp :: (a -> b) -> Lst a -> Lst b
mapp f Nil = Nil
mapp f (Cons hd tl) = Cons (f hd) (mapp f tl)
--filter
fltr :: (a -> Bool) -> Lst a -> Lst a
fltr f Nil = Nil
fltr f (Cons hd tl) = if (f hd) then 
			(Cons hd (fltr f tl)) else (fltr f tl)
--reduce :: (t -> t1 -> t1) -> t1 -> Lst t -> t1
reduce f i Nil = i
reduce f i (Cons hd tl) = f hd (reduce f i tl)
--redtotal
redTotal :: Num a => Lst a -> a
redTotal lst = reduce (\x y -> x + y) 0 lst
--redDisj
redDisj :: Lst Bool -> Bool
redDisj lst = reduce (\x y -> x || y) False lst
--redApp
redApp :: Lst a -> Lst a -> Lst a
redApp lst1 lst2 = reduce (\ x y -> Cons x y) lst2 lst1
--insert
insert :: Ord a => a -> Lst a -> Lst a
insert x Nil = Cons x Nil
insert x (Cons hd tl) | x < hd = (Cons x (Cons hd tl))
                      | otherwise = (Cons hd (insert x tl))
--insertionsort
isort :: Ord a => Lst a -> Lst a -> Lst a
isort lst Nil = lst
isort sorted (Cons hd tl) = isort (insert hd sorted) tl
--quicksort
partition :: (a -> Bool) -> Lst a -> (Lst a, Lst a)
partition f ls = (fltr f ls, fltr (\x -> not (f x)) ls)
app Nil ls = ls
app (Cons hd tl) ls = Cons hd (app tl ls)

quicksort Nil = Nil
quicksort (Cons hd tl) = app (quicksort smaller) 
			(Cons hd (quicksort larger))
  where
    (smaller, larger) = (partition (\x -> x < hd) tl)
\end{haskellcode}
\end{breakbox}

\begin{breakbox}
\textbf{Haskell Lists and Functions:}\\
\begin{haskellcode}
-- Lists
l1 = [1..20]
l2 = [3,4]
head (hd:tl) = hd --ambigous
tail (hd:tl) = tl --ambigous
l3 = l1 ++ l2 -- concat lists: [1,2,3,4]
l4 = 1:l3 -- add elemnt: [1,1,2,3,4]
v = l4 !! 4 -- get element: 4
	
-- List Comprehensions
[ x*y | x <- [2,5,10], y <- [8,10,11], x*y > 50]  -- [55,80,100,110]
-- delete :: Eq t => t -> [t] -> [t]
delete x xs = [a | a <- xs, a /= x]
 
-- quicksort :: Ord t => [t] -> [t]
quicksort [] = []  
quicksort (x:xs) = smallerSorted ++ [x] ++ smallerSorted
	where
		smallerSorted = quicksort [a | a <- xs, a <= x]
		biggerSorted = quicksort [a | a <- xs, a > x]

-- perm :: Eq t => [t] -> [[t]]
perm [] = [[]]
perm xs = [x:ys | x <- xs, ys <- perm (delFst x xs)]
\end{haskellcode}
\end{breakbox}

\begin{breakbox}
\textbf{Haskell Tree ADT:}\\
\begin{haskellcode}
data Tree a = Nil | Node a (Tree a) (Tree a) 
			deriving(Show, Read, Eq)

--treeMap
treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f Nil = Nil
treeMap f (Node v l r) = Node (f v) (treeMap f l) (treeMap f r)
--repTree
repTree :: (Ord a, Num a) => a1 -> a -> Tree a1
repTree e depth 
    | depth <= 0 = Nil
    | otherwise  = Node e (repTree e (depth-1)) 
    			(repTree e (depth-1))

--inOrder, for preorder/postoder change place of [v]
inOrder :: Tree a -> [a]
inOrder Nil = []
inOrder (Node v l r) = (inOrder l) ++ [v] ++ (inOrder r)

--treeInsert
treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert x Nil = Node x Nil Nil
treeInsert x (Node v l r) | x <= v = Node v (treeInsert x l) (r) 
                          | otherwise = Node v l (treeInsert x r)
--treeSearch                          
treeSearch :: (Ord a) => a -> Tree a -> Bool  
treeSearch x Nil = False  
treeSearch x (Node a left right)  
    | x == a = True  
    | x < a  = treeSearch x left  
    | x > a  = treeSearch x right
--treeSort
treeSort ls = inOrder (foldr treeInsert Nil ls)
\end{haskellcode}
\end{breakbox}