% FILE. . . . . /home/hak/hlt/doc/hak/design/slides.tex
% EDIT BY . . . Hassan Ait-Kaci
% ON MACHINE. . Hp-Dv7
% STARTED ON. . Thu Apr 26 15:24:49 2012

% Last modified on Thu Apr 26 15:25:15 2012 by hak
%      modified on Mon Apr 07 19:44:51 2003 by Administrators

\documentclass[12pt]{article}

\input{slides.mac}
\usepackage{fleqn}

\newcommand{\HAK}{Hassan A\"{\i}t-Kaci}

\setlength{\textheight}{.6\textheight}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\landscape

\title{\begin{tabular}{c}
An Abstract and Reusable \\[1.5ex]
Programming Language Architecture 
\end{tabular}}
\speaker{\Green \HAK}
\affiliation{\begin{tabular}{c}
\textbf{ILOG}
\end{tabular}}

\titlepage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Outline]

\begin{items}

\Item Motivation

\Item Overview

\Item Syntax

\Item Kernel

\Item Types

\Item Backend

\Item Conclusion

\end{items}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Motivation]

\begin{itemize}

\Item Synthesis of language front-ends to dedicated engines

\Item Syntactic interface between several application domains

\Item Scripting tools

\Item Rapid prototyping, academic experimentation, \etc, ...

\end{itemize}

\textbf{\Blue Basic idea:} Factoring out {\Blue \ldots}

\begin{itemize}

\item[] {\Blue \dots} syntax analysis,

\item[] {\Blue \dots} type checking,

\item[] {\Blue \dots} code generation.

\end{itemize}

Seeking an {\Red open} design---\ie, easily {\Green adaptable} and
{\Green extensible}.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Overview]

The design consists in Java {\Red packages} and {\Red classes} that
offer a basic service.

One can thus {\Green import} (some of) these packages and {\Green
derive} (some of) of these classes and (possibly) complete them with
specific features to:
\begin{Itemize}

\Item Specify a grammar for a surface syntax;

\Item Possibly augment the basic design with {\Green new}:
  \begin{Itemize}
    \item kernel expressions;
    \item built-in types;
    \item built-in instructions;
    \item runtime objects and structures.
\end{Itemize}

\Item Translate AST's into kernel language expressions.
\end{Itemize}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Processing diagram]

\rput(.5\textwidth,-.35\textheight){
\begin{tabular}{c@{\hskip5cm}c}
\Bnode{b1}{parsing}         & \Bnode{b2}{name resolution} \\ [3cm]
\Bnode{b4}{boxing analysis} & \Bnode{b3}{type checking} \\ [3cm]
\Bnode{b5}{code generation} & \Bnode{b6}{execution} 
\end{tabular}
\LINK{b1}{b2}\LINK{b2}{b3}\LINK{b3}{b4}\LINK{b4}{b5}\LINK{b5}{b6}
}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Syntax front-end]

{\Red JACC} - {\Red J}ust {\Red A}nother {\Red C}ompiler {\Red C}ompiler:

\begin{items}

\Item ``100\% Pure Java'' LALR(1) parser generator \textit{\`a la} yacc

\Item AST construction and manipulation

\Item partial parsing

\Item dynamically (re-)definable operators \textit{\`a la} Prolog

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Jacc dynamic operators]

\begin{verbatim}
  %token '!'

  %dynamic op1
  %op1 '!' yf 200

  %dynamic op2
  %op2 '!' yfx 500

  %%
  expression : expression1 _op1_ expression1 
             | expression2 _op2
             | '!' expression
             ;
\end{verbatim}


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions]

\begin{Itemize}

\ritem{constants}
\ritem{names}
\ritem{functions}
\ritem{control}
\ritem{indexed structures}
\ritem{tuples}
\ritem{objects}
\ritem{collections}
\ritem{updates}
\ritem{nonstandard constructs}
\ritem{monoids}

\end{Itemize}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{constants}

\begin{Itemize}
\sitem{Char}{}
\sitem{Int}{}
\sitem{Real}{}
\sitem{StringConstant}{}
\sitem{BuiltinObjectConstant}{}
\end{Itemize}

\ritem{names}

\begin{Itemize}
\sitem{Unresolved}{}
\sitem{Global}{}
\sitem{Local}{}
\sitem{Parameter}{}
\end{Itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{functions}

\begin{Itemize}
\sitem{Abstraction}{\Abstraction{x_1,\ldots,x_n}{e}}
\sitem{Application}{\Application{f}{e_1,\ldots,e_n}}
\sitem{Let}{\Let{x_1}{e_1}{x_n}{e_n}{e}}
\end{Itemize}

\ritem{control}

\begin{Itemize}
\sitem{Sequence}{\Sequence{e_1}{e_n}}
\sitem{IfThenElse}{\IfThenElse{e_1}{e_2}{e_3}}
\sitem{And}{\AND{e_1}{e_2}}
\sitem{Or}{\OR{e_1}{e_2}}
\sitem{Loop}{\Loop{e_1}{e_2}}
\end{Itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{indexed structures}

\begin{Itemize}
\sitem{NewArray}{\NewArray{type}{indexer}{indexer}}
\sitem{ArraySlot}{\ArraySlot{e}{e_1}{e_n}}
\sitem{ArrayExtension}{\ArrayExtension{e_1}{e_n} or \MapExtension{i_1}{e_1}{i_n}{e_n}}
\sitem{ArrayInitializer}{\texttt{NewArray} \KRNL{=} \texttt{ArrayExtension}}
\sitem{ArrayToMap}{\ArrayToMap{e}{indexer}}
\end{Itemize}

\ritem{tuples}

\begin{Itemize}
\sitem{Tuple}{\Tuple{e_1}{e_n}}
\sitem{NamedTuple}{\NamedTuple{p_1}{e_1}{p_n}{e_n}}
\sitem{TupleProjection}{\TupleProjection{e}{p}}
\end{Itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{objects}

\begin{Itemize}
\sitem{NewObject}
      {\New\; \TYPE{C} \ \ or \ \  \New\; \TYPE{C(T_1,\ldots,T_n)}}
\end{Itemize}

\ritem{collections}

\begin{Itemize}
\sitem{NewSet}{\New\; \TYPE{\{T\}} \ \ or \ \  \KRNL{\set \{ e_1, \ldots, e_n \}}}
\sitem{NewList}{\New\; \TYPE{\g{list}\{T\}} \ \ or \ \  \KRNL{\lst \{ e_1, \ldots, e_n \}}}
\sitem{NewBag}{\New\; \TYPE{\g{bag}\{T\}} \ \ or \ \  \KRNL{\bag \{ e_1, \ldots, e_n \}}}
\end{Itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{updates}

\begin{Itemize}
\sitem{Definition}{\Def\;\Assign{id}{e} \ \ or \ \ \Def\;\Assign{id(v_1,\ldots,v_n)}{e}}
\sitem{Assignment}{\Assign{l}{e}}
\sitem{UnresolvedAssignment}{}
\sitem{GlobalAssignment}{}
\sitem{LocalAssignment}{}
\sitem{ArraySlotUpdate}{\ArraySlotUpdate{e}{e_1}{e_n}{e'}}
\sitem{TupleUpdate}{\Assign{\TupleProjection{t}{p}}{e}}
\sitem{FieldUpdate}{\Assign{o.f}{e}}
\end{Itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Kernel Expressions (ctd.)]

\begin{items}

\ritem{nonstandard constructs}

\begin{Itemize}
\sitem{ExitWithValue}{\KRNL{\g{return}\;e}}
\sitem{UndecidedExpression}{\KRNL{e_1 \; ? \; e_2}}
\sitem{HideType}{\KRNL{e \; \g{as} \; \TYPE{T}}}
\sitem{OpenType}{\KRNL{\$e}}
\end{Itemize}

\ritem{monoids}

\begin{Itemize}
\sitem{Homomorphism}{}
\sitem{Comprehension}{}
\sitem{FilterHomomorphism}{}
\end{Itemize}
\end{items}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Functions]

\[
\typerule{\judgment{\Gamma\tsubst{x_1}{T_1}\cdots\tsubst{x_n}{T_n}}{e}{T}}
         {\gammajudgment{\Abstraction{x_1,\ldots,x_n}{e}}{\funtype{T_1,\ldots,T_n}{T}}}
\]

\[
\typerule{\gammajudgment{e_1}{T_1}, \cdots,
          \gammajudgment{e_n}{T_n},
          \gammajudgment{f}{\funtype{T_1,\ldots,T_n}{T}}}
         {\gammajudgment{\Application{f}{e_1,\ldots,e_n}}{{T}}}
\]

\bigskip
Implicit currying:
\[
\dfrac{\unif{S_1}{T_1},\;\ldots,\;\unif{S_n}{T_n},\;\unif{S}{\funtype{T_{n+1},\ldots,T_{n+k}}{T}}}
      {\unif{\funtype{S_1,\ldots,S_n}{S}}{\funtype{T_1,\ldots,T_n,T_{n+1},\ldots,T_{n+k}}{T}}}
\]

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Let]

\[
\typerule{\gammajudgment{e_1}{T_1}, \cdots, \gammajudgment{e_n}{T_n},
	  \judgment{\Gamma\tsubst{x_1}{T_1}\cdots\tsubst{x_n}{T_n}}{e}{T}}          
         {\gammajudgment{\Let{x_1}{e_1}{x_n}{e_n}{e}}{T}}
\]

\bigskip

\textbf{NB:} this \KRNL{\g{let}} is \textit{not} polymorphic and amounts to:

\[
\begin{array}{c}
\Let{x_1}{e_1}{x_n}{e_n}{e} \\[2ex]
\Green \eqd \\[2ex]
\Application{\bigl(\Abstraction{x_1,\ldots,x_n}{e}\bigr)}{e_1,\ldots,e_n}
\end{array}
\]

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Control expressions]

\[
\begin{array}{l}
      \typerule{\gammajudgment{e_1}{\TYPE{T_1}}, \ldots, \gammajudgment{e_n}{\TYPE{T_n}}}
	       {\gammajudgment{\Sequence{e_1}{e_n}}{\TYPE{T_n}}}
\\[4ex]
      \typerule{\gammajudgment{c}{\BOOL}, \gammajudgment{e_1}{T}, \gammajudgment{e_2}{T}}
               {\gammajudgment{\IfThenElse{c}{e_1}{e_2}}{T}}
\\[4ex]
      \typerule{\gammajudgment{e_1}{\BOOL}, \gammajudgment{e_2}{\BOOL}}
               {\gammajudgment{\AndOr{e_1}{e_2}}{\BOOL}}
\\[4ex]
      \typerule{\gammajudgment{c}{\BOOL}, \gammajudgment{e}{T}}
               {\gammajudgment{\Loop{c}{e}}{\VOID}}
\end{array}
\]

\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Monoid homomorphisms]

{\Green Monoid}: data type with associative binary operation and
identity
\begin{center}
\begin{tabular}{ccc}
\makebox[6em][c]{Type}  & \makebox[6em][c]{Operation}  & \makebox[6em][c]{Identity}
\\ \hline
\INT           & \KRNL{+}       & \KRNL{0}
\\
\INT           & \KRNL{*}       & \KRNL{1}
\\
\REAL          & \KRNL{+}       & \KRNL{0.0}
\\
\REAL          &  \KRNL{*}      & \KRNL{1.0}
\\
\INT           & \KRNL{\MaxOp}  & \KRNL{-\infty}
\\
\INT           & \KRNL{\MinOp}  & \KRNL{+\infty}
\\
\BOOL          & \KRNL{\OrOp}   & \KRNL{\false}
\\
\BOOL          & \KRNL{\AndOp}  & \KRNL{\true}
\\
\SET           & \KRNL{\g{union}}    & \KRNL{\{\}}
\\
\LIST          & \KRNL{\g{append}}   & \KRNL{[]}
\\
$\vdots$ & $\vdots$ & $\vdots$ 
\end{tabular}
\end{center}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Monoid homomorphism]

A monoid homomorphism expresses an {\Green\em declarative iteration}.

Example (list):

\[
\begin{array}{l@{\;=\;}l}
{\Blue\g{hom}_\star^{\Ide} \bigl(f\bigr)} ([]) & \Ide \\[2ex]
{\Blue\g{hom}_\star^{\Ide} \bigl(f\bigr)} ([H|T]) & f(H) \star
{\Blue \g{hom}_\star^{\Ide}\bigl(f\bigr)} (T)
\end{array}
\]

\vskip2cm

Clearly, this scheme extends a function $f$ to a homomorphism of monoids,
from the monoid of lists to the monoid defined by \Mon{\star}{\Ide}.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Primitive homomorphisms]

A {\Green\em primitive homomorphism} computing a value of type \TYPE{T} consists of:

\begin{items}
\Item  a collection iterated over---of type \TYPE{coll(T')};
\Item  a function applied to each element---of type \FUNTYPE{T'}{T};
\Item  a monoid operation---of type \FUNTYPE{T,T}{T};
\Item  an identity---of type \TYPE{T}.
\end{items}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Collection homomorphisms]

A {\Green\em collection homomorphism} expression constructing a collection
of type \TYPE{coll(T)} consists of:

\begin{items}
\Item  a collection iterated over---of type  \TYPE{coll'(T')};
\Item  a function applied to each element---of type
       \FUNTYPE{T'}{coll(T)};
\Item  an operation ``adding'' an element to a collection---of
       type\\
       \FUNTYPE{T,coll(T)}{coll(T)}
\Item  an identity---of type \TYPE{coll(T)}.
\end{items}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Monoid comprehension]

\[
\KRNL{\Monoid{\oplus} \COMP{e}{q_1, \ldots, q_n}} 
\]

\begin{itemize}
\Item \KRNL{\Monoid{\oplus}} is a monoid,
\Item \KRNL{e} is an expression,
\Item \KRNL{q\_i} is a {\em qualifier}:
      \begin{itemize}
      \item an expression \KRNL{e}, or
      \item a pair \KRNL{\IN{x}{e}}, where \KRNL{x} is a variable and
	    \KRNL{e} is an expression.
      \end{itemize}
\end{itemize}

{\Red\LARGE\begin{verbatim}
[+,set{}] { <x,y> | x <- 1..5, y <- x..6, (x+y)%2 == 0 };
\end{verbatim}}
{\Green\Large\begin{verbatim}
{<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<2,6>,<3,3>,<3,5>,<4,4>,<4,6>,<5,5>} : {<int,int>}
\end{verbatim}}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Monoid comprehension]

A monoid comprehension is defined in terms of homomorphisms:

[Fegaras-Maier: TODS-1996]

\[
\begin{array}{l@{\;\eqd\;}l}
\KRNL{\Monoid{\oplus} \COMP{e}{}} & \KRNL{e \oplus \Ide} \\ [2.5ex]
\KRNL{\Monoid{\oplus} \COMP{e} {\IN{x}{e}', Q }} &
\KRNL{\Hom{e'}{\lambda x.\Comprehension{\oplus}{e}{Q}}{\oplus}} \\ [2.5ex]
\KRNL{\Monoid{\oplus} \COMP{e} {c, Q }} &
\KRNL{\ite{c}{\Monoid{\oplus} \COMP{e} { Q }}{\Ide}}
\end{array}
\]

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Monoid comprehensions]

Monoid comprehensions (based on homomorphisms) allow to express a complete
formal {\Red\em Object Query Calculus} [Fegaras-Maier: TODS-1996].


Monoid comprehensions
\begin{items}
\Item facilitate optimization through expression normalization

\Item complete naturally the $\lambda$-calculus

\Item enable efficient declarative iteration using RDB techniques
\end{items}

We adapted the comprehension calculus to work in a language setting.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Types]

\begin{items}

\Item polymorphism

\Item overloading

\Item currying

\Item boxing/unboxing

\Item dynamic types

\Item classes

\Item type definitions

\end{items}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Polymorphism]

ML-polymorphism (\ie, $2${\em nd}-order universal)---\eg:

\textrm{\huge\begin{BNFLIST}
\BNFRULE{Type}{SimpleType \BAR TypeScheme}
\BNFRULE{SimpleType}{BasicType \BAR FunctionType \BAR TypeParameter}
\BNFRULE{BasicType}{\INT\ \BAR \REAL\ \BAR \BOOL\ \BAR \ldots }
\BNFRULE{FunctionType}{\funtype{\textit{SimpleType}}{\textit{SimpleType}}}
\BNFRULE{TypeParameter}{\TYPE{\alpha} \BAR \TYPE{\alpha'} \BAR \ldots \BAR
                        \TYPE{\beta} \BAR \TYPE{\beta'} \BAR \ldots}
\BNFRULE{TypeScheme}{\TYPE{\forall} TypeParameter \TYPE{.} Type}
\end{BNFLIST}}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue The Type System]

\rput(.5\textwidth,-.35\textheight){
\begin{minipage}{\textwidth}

\hfill
\Acnode{Type}
\HFILL

\vskip1.5cm

\hfill
\Acnode{Static}
\hfill
\Acnode{Dynamic}
\HFILL

\vskip2.5cm

\hfill
\Acnode{Named}
\hfill
\Cnode{Parameter}
\hfill
\Acnode{Constructed}
\hfill
\Acnode{Extensional}
\hfill
\Acnode{Intensional}
\HFILL

\vskip2.5cm

\hfill
\Cnode{Constant}
\hfill
\Acnode{Term}
\hfill
\Cnode{Boxable}
\hfill
\Cnode{Function}
\hfill
\Cnode{Tuple}
\hfill
\Cnode{Array}
\hfill
\Acnode{Collection}
\HFILL

\vskip2.5cm

\hfill
\Cnode{CollectionConstant}
\hfill
\Cnode{Class}
\hfill
\Cnode{Defined}
\hfill
\Cnode{NamedTuple}
\hfill
\Cnode{Set}
\hfill
\Cnode{Bag}
\hfill
\Cnode{List}
\HFILL

\end{minipage}

\Extends{Static}{Type}
\Extends{Dynamic}{Type}

\Extends{Named}{Static}
\Extends{Constructed}{Static}
\Extends{Parameter}{Static}

\Extends{Extensional}{Dynamic}
\Extends{Intensional}{Dynamic}

\Extends{Array}{Constructed}
\Extends{Boxable}{Constructed}
\Extends{Collection}{Constructed}
\Extends{Function}{Constructed}
\Extends{Tuple}{Constructed}

\Extends{Set}{Collection}
\Extends{Bag}{Collection}
\Extends{List}{Collection}

\Extends{Constant}{Named}
\Extends{Term}{Named}

\Extends{NamedTuple}{Tuple}

\Extends{CollectionConstant}{Constant}

\Extends{Class}{Term}
\Extends{Defined}{Term}
%}
}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Class type]

Declaring a class type and defining its implementation causes the
following:

\begin{items}
 
\Item the name of the class is entered with a new type for it in the
      type symbol table;

\Item each field of a distinct type is assigned an offset in an
      array of slots (per sort);

\Item each method and field expression is name-resolved, type-checked,
      after closing it into an abstraction taking \This\ as first argument;

\end{items}
     
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Class type]

\begin{items}
 
\Item each method definition is compiled into a global definition,
      and each field is compiled into a global function corresponding
      to accessing its value from the appropriate offset;

\Item finally, each field's initialization expression is compiled and
      recorded to be used at object creation time.

\end{items}

An object may be created at run-time (using the \New\ operator followed by a class name).
     
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Class type]

\[
\KRNL{\Class\;\id{classname}
\;\{\;\meta{interface}\;\}\;}\meta{[}\KRNL{\;\{\;\meta{implementation}\}\;}\meta{]}
\]

The {\em interface} block specifies the type signatures of the {\em
members} ({\em fields} and {\em methods}) of the class \, and possibly
initial values for fields.

The {\em implementation} block is optional and gives the definition of
(some or all of) the methods.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Class type]

\[
\KRNL{\begin{array}{rl}
\Class \; \id{Counter}  \{ & \id{val} : \INT = 1; \\
                           & \Method\; \id{set} : \FUNTYPE{\INT}{\id{Counter}}; \\
                 \}          & \\
                 \{          & \id{set} (\id{val} : \INT) : \id{Counter}  =
                                       (\This.\id{val} = \id{val}); \\
                 \} & 
\end{array}}
\]
\[
\KRNL{
\Def\; \qid{Counter}{set} (\id{x} : \id{Counter}, \id{n} : \INT) : \id{Counter}
= (\id{x}.\id{val} = \id{n});
}
\]
\[
\KRNL{\id{c} = \New\ \id{Counter};}
\]
\[
\KRNL{\begin{array}{l}
\id{c}.\id{set}(\id{c}.\id{val}+2);	\\
     \id{write}(\id{c}.\id{val});
\end{array}}
\]
\[
\KRNL{\begin{array}{l}
     \qid{Counter}{set}(\id{c},\qid{Counter}{val}(\qid{Counter}{c})+2);	\\
     \id{write}(\qid{Counter}{val}(\qid{Counter}{c}));
\end{array}}
\]

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue The Type Checker]

\begin{items}

\Item Backtracking prover that establishes {\Green goal} objects.


\Item \eg: a {\Red \texttt{TypingGoal}} consists of an expression and a
      type:

\bigskip

      proving a \texttt{TypingGoal} amounts to unifying its expression
      component's type with its type component.

\Item Such goals are spawned in the typechecker by the type checking
      method of expressions as per their type checking rules.

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue The Type Checker (ctd.)]

\begin{items}

\Item Some globally defined symbols may have multiple types:

      keep choices and backtrack to alternative types upon failure.

\Item the typechecker maintains all the necessary structures for
undoing:
\begin{itemize}
\item type variable binding,
\item function type currying,
\item application expression currying.
\end{itemize}

\end{items}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Some typing goals]

\begin{center}
\begin{tabular}{ll}

\begin{minipage}[t]{.45\textwidth}
\begin{itemize}
\Item \texttt{EmptyGoal}
\Item \texttt{TypingGoal}
\Item \texttt{UnifyGoal}
\Item \texttt{GlobalTypingGoal}
\Item \texttt{SubTypeGoal}
\Item \texttt{BaseTypeGoal}
\Item \texttt{ArrayIndexTypeGoal}
\end{itemize}
\end{minipage}

&

\begin{minipage}[t]{.45\textwidth}
\begin{itemize}
\Item \texttt{PruningGoal}
\Item \texttt{PushExitableGoal}
\Item \texttt{PopExitableGoal}
\Item \texttt{CheckExitableGoal}
\Item \texttt{ResiduatedGoal}
\Item \texttt{ShadowUnifyGoal}
\Item \texttt{UnifyBaseTypeGoal}
\Item \texttt{NoVoidTypeGoal}
\end{itemize}
\end{minipage}

\end{tabular}
\end{center}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\blue Boxing/Unboxing]

Polymorphic code must work for either:
\begin{Itemize}
\item primitive unboxed types (\eg, \INT, \REAL, \etc)

\item boxed types
\end{Itemize}


\textbf{\Blue Problem:} how to compile a polymorphic function into code that
knows the actual runtime sorts of the function's runtime arguments and
returned value, {\Green\em before the function type is actually instantiated}?

The problem was addressed by Xavier Leroy 11 years [POPL'92].

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\blue Boxing/Unboxing]

{\Green Leroy's method:}
\begin{Itemize}
\Item type annotation enabling a source-to-source transformation;

\Item source transformation: generate of {\Red\em wrappers} and {\Red\em
unwrappers} for boxing and unboxing expressions whenever necessary;

\Item compile the transformed source as usual.
\end{Itemize}

{\Green We adapt and improve the main idea from Leroy's method:}
\begin{Itemize}
\Item type annotation and rules are greatly simplified;
\Item no source-to-source transformation is needed;
\Item un/wrappers generation is done at code-generation time.
\end{Itemize}

{\Green This saves a great amount of space and time.}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Backend system]

Intermediate code is executed in the context of {\Red\em Runtime}.

A runtime state (encapsulated by an object in this class) is that of a
stack automaton supporting the computations of a higher-order functional
language with lexical closures.

This may be viewed as an optimized variant of Peter Landin's SECD machine
in the same spirit as Luca Cardelli's Functional Abstract Machine (FAM).

The backend system also defines runtime objects for tuples, maps, sets,
\etc, ... 

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}[\Blue Conclusion]

This architecture offers a compromise between formal executable
specification systems and pragmatic language definition (a {\em poor
man's language kit?...}).

It enables low-cost development of programming languages with basic and
advanced features.

Importantly, it is {\Green\em open} and favors {\Green ease of
extension} and {\Green interoperability}.

Much more remains to be done (\eg, namespaces, access management, rule-based
programming, logic programming, type logics, \etc, ...)

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}

\vfill
\hfill\Bnode{thanks}{\textbf{\Red \ \ Thank \ \ You \ \ Very \ \ Much !\ \ }}\HFILL
\VFILL

\end{slide}

\end{document}

