\section*{Background}

\begin{frame}
  \frametitle{Name Analysis}
  
  Concrete syntax:
  \begin{code}
  let  x = 1
       f = \x . x  in f x
  \end{code}
  
  Abstract syntax:
  \begin{code}
  Let  [Decl "x" (Val 1), Decl "f" (Lam "x" (Var "x"))]
       (App (Var "f") (Var "x")))
  \end{code}
  
  Questions:
  \begin{itemize}
  \item All identifiers defined?
  \item No duplicate definitions?
  \item What is the type of an identifier?
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Name Analysis applied - gather environment}
  
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=9mm, very thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\scriptsize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, very thick, draw=black!50, top color=white, bottom color=black!20,font=\scriptsize}
    , inh/.style={attr}
    , syn/.style={attr}
    , leftfirst/.style={xshift=-4mm}
    , rightfirst/.style={xshift=4mm}
    , arr/.style={->,dashed, very thick}
    ]
    \node[nd](n1){|let|}
      [sibling distance=60mm, level distance=12mm]
      child {
        node[nd](n2){|cons|}
        [sibling distance=32mm]
          child {
            node[nd](n4){|x=|}
              child {
                node[nd](n5){|val|}
              }
          }
          child {
            [sibling distance=32mm]
            node[nd](n6){|cons|}
              child {
                node[nd](n7){|f=|}
                  child {
                    node[nd](n8){|\x|}
                      child {
                        node[nd](n9){|x|}
                      }
                  }
              }
              child {
                node[nd](n10){|nil|}
              }
          }
      }
      child {
        [sibling distance=20mm]
        node[nd](n3){|app|}
          child {
            node[nd](n11){|f|}
          }
          child {
            node[nd](n12){|x|}
          }
      };
  
  \pause
  \node[right of=n4]{|(x,ty1)|};
  \pause
  \node[right of=n9]{|emptyset|};
  \pause
  \node[right of=n8](loc1){|emptyset|};
  \node[right of=loc1]{\tiny{|(x,ty2)|}};
  \pause
  \node[right of=n7]{|(f,ty3)|};
  \pause
  \node[right of=n10]{|emptyset|};  
  \node[right of=n6]{|(f,ty3)|};
  \pause
  \node[right of=n2,xshift=8mm]{|(x,ty1)(f,ty3)|};
  \pause
  \node[right of=n3]{|emptyset|};
  \node[right of=n1](loc2){|emptyset|};
  \node[right of=loc2]{\tiny{|(x,ty1)(f,ty3)|}};
  
  \comment{Observation! Already duplicate behavior for let/lam!}  
  \end{tikzpicture}
\end{frame}


\begin{frame}
  \frametitle{Name Analysis applied - distribute environment}
  
  \begin{tikzpicture}
    [ nd/.style={circle, minimum size=9mm, very thick, draw=blue!50!black!50, top color=white, bottom color=blue!50!black!20,font=\scriptsize}
    , nd2/.style={circle, minimum size=9mm, very thick, draw=red!50!black!50, top color=white, bottom color=red!50!black!20,font=\scriptsize}
    , attr/.style={rectangle, minimum size=4mm, node distance=6mm, very thick, draw=black!50, top color=white, bottom color=black!20,font=\scriptsize}
    , inh/.style={attr}
    , syn/.style={attr}
    , leftfirst/.style={xshift=-4mm}
    , rightfirst/.style={xshift=4mm}
    , arr/.style={->,dashed, very thick}
    ]
    \node[nd](n1){|let|}
      [sibling distance=60mm, level distance=12mm]
      child {
        node[nd](n2){|cons|}
        [sibling distance=32mm]
          child {
            node[nd](n4){|x=|}
              child {
                node[nd](n5){|val|}
              }
          }
          child {
            [sibling distance=32mm]
            node[nd](n6){|cons|}
              child {
                node[nd](n7){|f=|}
                  child {
                    node[nd](n8){|\x|}
                      child {
                        node[nd](n9){|x|}
                      }
                  }
              }
              child {
                node[nd](n10){|nil|}
              }
          }
      }
      child {
        [sibling distance=20mm]
        node[nd](n3){|app|}
          child {
            node[nd](n11){|f|}
          }
          child {
            node[nd](n12){|x|}
          }
      };
      
      \node[right of=n1](loc2){|emptyset|};
      \node[right of=loc2]{\tiny{|(x,ty1)(f,ty3)|}};
      \node[right of=n8](loc1){|emptyset|};
      \node[right of=loc1]{\tiny{|(x,ty2)|}};
      
      \pause
      \node[left of=n1]{|emptyset|};
      \node[left of=n2,xshift=-6mm]{|(x,ty1)(f,ty3)|};
      
      \pause
      \node[left of=n8,xshift=-6mm]{|(x,ty1)(f,ty3)|};
      \node[left of=n9,xshift=-6mm]{|(x,bf ty2)(f,ty3)|};
      
      \pause
      \node[left of=n3,xshift=-6mm]{|(x,ty1)(f,ty3)|};
      \node[left of=n11,xshift=-6mm]{|(x,ty1)(f,ty3)|};
      
      \pause
      \node[nd2,at=(n9)]{|x|};
      \node[nd2,at=(n11)]{|f|};
      \node[nd2,at=(n12)]{|x|};
      
      \pause
      \node[nd2,at=(n8)]{|\x|};
      \node[nd2,at=(n4)]{|x=|};
      \node[nd2,at=(n6)]{|f=|};
  \end{tikzpicture}
\end{frame}

\begin{frame}
  \frametitle{Implementation - parser}
  
  \footnotesize{
  \begin{code}
  pExpr :: Parser Token T_Expr

  pExpr =    sem_Expr_Let <$> pKey "let" <*> pDecls <*> pKey "in" <*> pExpr
        <|>  sem_Expr_Lam <$> pKey "\\" <*> pIdent <*> pKey "." <*> pExpr
        <|>  pExprApps
  
  pExprApps = pChainl sem_Expr_App pExprBase

  pExprBase =  sem_Expr_Var <$> pIdent
            <|> sem_Expr_Val <$> pValue
            <|> pParens pExpr
  
  pDecls = pFoldr (sem_Decls_Cons,sem_Decls_Nil) pDecl
  pDecl = sem_Decl_Decl <$> pIdent <*> pKey "=" <*> pExpr
  \end{code}
  }
\end{frame}

\begin{frame}
  \frametitle{Implementation - constructors (1)}
  
  \begin{code}
  sem_Expr_Var nm      = sem :: Expr  ...
  sem_Expr_Val val     = sem :: Expr  ...
  sem_Expr_App l r     = sem :: Expr  ...
  sem_Expr_Lam nm b    = sem :: Expr  ...
  sem_Expr_Let ds b    = sem :: Expr  ...
  sem_Decls_Cons d ds  = sem :: Decls ...
  sem_Decls_Nil        = sem :: Decls ...
  sem_Decl_Decl nm e   = sem :: Decl  ...
  \end{code}
  \pause
  \scriptsize{
  \begin{code}
  sem_Expr_Lam :: String -> T_Expr -> T_Expr
  sem_Expr_Let :: T_Decls -> T_Expr -> T_Expr
  \end{code}}
\end{frame}

\begin{frame}
  \frametitle{Implementation - interfaces}
  
  \begin{code}
  itf Expr Decls Decl
    visit gather      syn  gathEnv :: [(String, Ty)]
    visit distribute  inh  finEnv  :: [(String, Ty)]
                      syn  errors  :: [String]
    order gather < distribute
  \end{code}
  \pause
  \scriptsize{
  \begin{code}
  newtype T_Expr st = ...

  data Inh_Expr = Inh_Expr
    { finEnv_Inh_Expr   :: [(String,Ty)] }

  data Syn_Expr = Syn_Expr
    { gathEnv_Syn_Expr  :: [(String,Ty)]
    , errors_Syn_Expr   :: [String]
    }

  eval_Expr :: (forall st . T_Expr st) -> Inh_Expr -> Syn_Expr
  \end{code}}
\end{frame}

\begin{frame}
  \frametitle{Implementation - Constructors (2)}
  
  \footnotesize{
  \begin{code}
  sem_Expr_Var nm =
    sem :: Expr
      loc.mbVal    = lookup nm lhs.finEnv
      lhs.errors   = maybe ["missing: " ++ nm] (const []) loc.mbVal
      lhs.gathEnv  = emptyset
  \end{code}
  \pause
  \begin{code}
  sem_Expr_Lam nm b =
    sem :: Expr
      child body :: Expr = b
      
      loc.(envWith,envWithout) = partition ((== nm) . fst) lhs.finEnv
      loc.dupErrs  = if length loc.envWith > 1 then ["dup: " ++ nm]
      lhs.errors   = loc.dupErrs ++ body.errors

      loc.binding  = [(nm, loc.argType)]
      body.finEnv  = loc.binding ++ loc.envWithout
      lhs.gathEnv  = filter ((/=nm) . fst) body.gathEnv
  \end{code}
  }
\end{frame}

\begin{frame}
  \frametitle{Implementation - Constructors (2)}

  \footnotesize{
  \begin{code}
    sem_Expr_App l r =
      sem :: Expr
        child left   :: Expr = l
        child right  :: Expr = r

        left.finEnv   = lhs.finEnv
        right.finEnv  = lhs.finEnv

        lhs.gathEnv   = left.gathEnv ++ right.gathEnv
        lhs.errors    = left.errors ++ right.errors
  \end{code}
  }
  
  \pause
  Other cases: similar..........
\end{frame}

\begin{frame}
  \frametitle{Name Analysis in UHC}
  
  \begin{itemize}
  \item |EH| AST has 39 constructors that deal with names
  \item |Core| AST about 16 constructors
  \item Lost the count in the |HS| AST
  \item Many more ASTs in UHC
  \item ... think of all other compilers
  \end{itemize}

  Code duplication!
\end{frame}