\documentclass{article}
\usepackage{geometry}
\usepackage{xcolor}
\usepackage{xspace}
\usepackage{amsmath}
\usepackage{tabularx}
\usepackage{longtable}
\usepackage[spanish]{babel}
\begin{document}
\colorlet{darkgreen}{green!60!black}
\newcommand{\chr}[1]{\texttt{'}\textcolor{blue}{\texttt{#1}}\texttt{'}}
\newcommand{\str}[1]{\texttt{"}\textcolor{blue}{\texttt{#1}}\texttt{"}}
\newcommand{\token}[1]{\textcolor{red}{\texttt{#1}}}
\newcommand{\nonterminal}[1]{\textcolor{blue}{{\it$\langle$#1$\rangle$}}}
\newcommand{\nonEmpty}[1]{#1$_{1}$}
\newcommand{\production}[2]{
  \noindent
  \begin{tabular}{lrp{10cm}}
  #1 & $\xrightarrow{\hspace{.5cm}}$ & #2
  \end{tabular}\\
}
\newcommand{\EMPTY}{$\epsilon$}
\newcommand{\ALT}{
  \\ & $\mid$ &
}
\newcommand{\ALTA}{
  $\mid$
}
\newcommand{\TODO}[1]{\textcolor{red}{****#1****}}

\newcommand{\type}[1]{\textcolor{blue}{\texttt{#1}}}
\renewcommand{\ast}[1]{\textcolor{darkgreen}{\texttt{\underline{#1}}}}
\newcommand{\instruction}[1]{\textcolor{darkgreen}{\texttt{\underline{#1}}}}
\newcommand{\typedecl}[2]{\noindent
  \begin{tabularx}{\textwidth}{lrlr}
  #1 & $=$ & #2
  \end{tabularx}\\
}
\newcommand{\datadecl}[2]{\noindent
  \begin{tabularx}{\textwidth}{lrp{13cm}r}
  #1 & $::=$ & #2
  \end{tabularx}\\
}

\newcommand{\PUEDE}{{\bf PUEDE}\xspace}
\newcommand{\PUEDEN}{{\bf PUEDEN}\xspace}
\newcommand{\NOPUEDE}{{\bf NO PUEDE}\xspace}
\newcommand{\NOPUEDEN}{{\bf NO PUEDEN}\xspace}
\newcommand{\DEBE}{{\bf DEBE}\xspace}
\newcommand{\DEBEN}{{\bf DEBEN}\xspace}

\newcommand{\typename}[1]{\textcolor{blue}{\texttt{#1}}}
\newcommand{\constructorname}[1]{\textcolor{red}{\texttt{#1}}}
\newcommand{\fieldname}[1]{\textcolor{darkgreen}{\textit{#1}}}

\tableofcontents

\section{Gram\'atica}

\subsection{Sintaxis l\'exica}

\begin{itemize}
\item Se ignoran:
\chr{\textbackslash t} (\texttt{TAB}, chr 9),
\chr{\textbackslash n} (\texttt{LF}, chr 10),
\chr{\textbackslash r} (\texttt{CR}, chr 13),
\chr{\,} (\texttt{SPACE}, chr 32).
\item Se admiten comentarios comenzados por \str{//} (estilo C++), por \str{--} (estilo Haskell) y por \str{\#} (estilo shell) que se extienden hasta el fin de l\'inea (\texttt{LF}).
\item Se admiten comentarios delimitados por \str{/*} \str{*/} y por \str{\{-} \str{-\}} que pueden anidarse.
\item El tokenizador reconoce directivas {\em pragma} de la forma \str{/*@parte$_1$@parte$_2$@...@parte$_n$@*/}. La idea es que esto pueda ser un mecanismo extensible de directivas. Ver m\'as abajo las directivas soportadas.
\end{itemize}

\subsection{Lista de s\'imbolos terminales}

Todos los s\'imbolos terminales se acompa\~nan de su nombre \token{EN\_MAYUSCULAS}.\bigskip

\begin{itemize}

\item {\bf Constantes num\'ericas.}
  Son una secuencia de d\'igitos decimales que representan enteros positivos.
  No pueden tener ceros innecesarios a la izquierda.
  \begin{center}
    \token{NUM} ::= \texttt{0|[1-9][0-9]*}
  \end{center}

\item {\bf Identificadores.}
  Comienzan por un caracter alfab\'etico y
  est\'an seguidos por cero o m\'as caracteres,
  ya sea alfab\'eticos, num\'ericos, gui\'on bajo (\texttt{\_}) o comilla simple (\texttt{'}).
  Se aceptan caracteres Unicode arbitrarios. Decimos que un caracter $c$ es {\bf alfab\'etico}
  cuando tiene dos variantes, una min\'uscula y una may\'uscula, es decir cuando:
  \[
  \texttt{$c$.toUpperCase() != $c$.toLowerCase()}
  \]
  Los identificadores \token{LOWERID} comienzan por un caracter en min\'usculas
  (y sirven para identificar \'indices, par\'ametros, funciones, variables, campos).
  Los identificadores \token{UPPERID} comienzan por un caracter en may\'usculas
  (y sirven para identificador constructores, procedimientos, tipos).
  \begin{center}
    \token{LOWERID} ::= \texttt{[:lower:]([:alpha:]|[0-9]|\_|')*}
  \end{center}
  \begin{center}
    \token{UPPERID} ::= \texttt{[:upper:]([:alpha:]|[0-9]|\_|')*}
  \end{center}

\item {\bf Constantes de cadena.}
  Las cadenas est\'an delimitadas por comillas dobles (\chr{"}).
  Todos los caracteres desde la comilla que abre hasta la que cierra se
  toman literalmente salvo la contrabarra (\chr{\textbackslash}) que se
  interpreta como un caracter de escape.
  Los escapes admitidos son:
  \begin{itemize}
  \item \texttt{\textbackslash\textbackslash} -- contrabarra (\textbackslash)
  \item \texttt{\textbackslash"} -- comilla doble (")
  \item \texttt{\textbackslash{a}} -- \texttt{BEL}, chr 7
  \item \texttt{\textbackslash{b}} -- \texttt{BS}, chr 8
  \item \texttt{\textbackslash{f}} -- \texttt{FF}, chr 12
  \item \texttt{\textbackslash{n}} -- \texttt{LF}, chr 10
  \item \texttt{\textbackslash{r}} -- \texttt{CR}, chr 13
  \item \texttt{\textbackslash{t}} -- \texttt{TAB}, chr 9
  \item \texttt{\textbackslash{v}} -- \texttt{VT}, chr 11
  \end{itemize}
  \begin{center}
    \token{STRING} ::= \texttt{"(\textbackslash{a}|\textbackslash{b}|\textbackslash{f}|\textbackslash{n}|\textbackslash{r}|\textbackslash{t}|\textbackslash{v}|\textbackslash\textbackslash|\textbackslash"|[\^{}\textbackslash"])*"}
  \end{center}

\item {\bf Lista completa de tokens.}
  \begin{longtable}{llp{.6\textwidth}}
  % El siguiente tex se genera a partir de 01-tokens.json usando gendoc.py.
  \input{01-tokens.tex}
  \end{longtable}
\end{itemize}

\subsection{Pragmas}

\subsubsection{Pragmas \texttt{BEGIN\_REGION} y \texttt{END\_REGION}}

Las directivas \texttt{BEGIN\_REGION} y \texttt{END\_REGION} sirven para
mantener registro de ``regiones''. Una regi\'on es una cadena de texto que
sirve para identificar o {\em taggear} un fragmento del programa.
Las regiones no tienen ning\'un significado
especial para el int\'erprete de Gobstones, pero todas las excepciones que
eleva el int\'erprete vienen acompa\~nadas de una posici\'on que incluye
el nombre de la regi\'on actual. Las regiones pueden anidarse.
Este comportamiento se implementa por medio de dos directivas.
\begin{itemize}
\item \str{/*@BEGIN\_REGION@\textit{nombre\_de\_la\_regi\'on}@*/} ---
       mete el nombre de una regi\'on en la pila de regiones.
\item \str{/*@END\_REGION@*/} --- saca la regi\'on del tope de la pila de regiones.
\end{itemize}
Por ejemplo ante el siguiente programa:
\begin{verbatim}
/*@BEGIN_REGION@A@*/
procedure P() {
  /*@BEGIN_REGION@B@*/
  x := f(
  /*@END_REGION@*/
}
/*@END_REGION@*/
\end{verbatim}
El parser idealmente deber\'ia reportar que hay un error de sintaxis en la regi\'on \texttt{B}.

\subsubsection{Pragma \texttt{ATTRIBUTE}}

La directiva \texttt{ATTRIBUTE} sirve para decorar definiciones de
tipos, programas, procedimientos y funciones con atributos clave/valor.
La directiva \texttt{ATTRIBUTE} debe {\bf preceder} inmediatamente la definici\'on
de un tipo, programa, procedimiento o funci\'on, y su sintaxis es la siguiente:
\begin{itemize}
\item \str{/*@ATTRIBUTE@clave@valor@*/} --- asocia el valor indicado a la clave indicada.
      Las claves y valores son {\em strings}.
\end{itemize}
Una definici\'on de tipo, programa, procedimiento o funci\'on puede estar precedida
de varias directivas \texttt{ATTRIBUTE}, asociando a dicha definici\'on un diccionario
de atributos. Por ejemplo en el siguiente programa:
\begin{verbatim}
/*@ATTRIBUTE@descripcion@Poner una piedra en la casilla actual.@*/
/*@ATTRIBUTE@esAtomico@SI@*/
procedure PonerPiedra() {
  ...
}

/*@ATTRIBUTE@esAtomico@NO@*/
function f() {
  ...
}

/*@ATTRIBUTE@descripcion@Programa principal.@*/
program {
  ...
}
\end{verbatim}
El procedimiento \texttt{PonerPiedra} tiene asociado el siguiente diccionario de atributos
(en formato JSON):
\begin{verbatim}
  {
    descripcion: "Poner una piedra en la casilla actual.",
    esAtomico: "SI"
  }
\end{verbatim}
y la funci\'on \texttt{f} tiene asociado el siguiente diccionario de atributos:
\begin{verbatim}
  {
    esAtomico: "NO"
  }
\end{verbatim}
El int\'erprete no otorga ning\'un significado ni funcionalidad especial a los atributos.
Son un mecanismo abierto cuya finalidad es dependiente de la implementaci\'on.

\subsubsection{Pragma \texttt{LANGUAGE}}

Establece opciones del lenguaje.
El objetivo de esta directiva es habilitar extensiones y funcionalidades experimentales.
La etapa de an\'alisis sint\'actico no se ve afectada por la directiva \texttt{LANGUAGE}.
La directiva \texttt{LANGUAGE} puede potencialmente
afectar las etapas de an\'alisis est\'atico ({\em linter}),
compilaci\'on y el comportamiento en tiempo de ejecuci\'on.

La sintaxis de la directiva es:
\begin{itemize}
\item \str{/*@LANGUAGE@nombre-de-la-opcion@*/} ---
      habilita la opci\'on indicada.
\end{itemize}

Por el momento hay una \'unica directiva \texttt{LANGUAGE} implementada:
\begin{itemize}
\item \str{/*@LANGUAGE@DestructuringForeach@*/} ---
      habilita la posibilidad de usar patrones complejos
      como \'indice del \texttt{foreach}
      (en lugar de permitir solamente variables).
\end{itemize}

\subsection{Producciones de la gram\'atica}

Los s\'imbolos no terminales se describen con su nombre \nonterminal{enCursiva}.
Las producciones se escriben siguiendo las convenciones usuales de EBNF.
La gram\'atica es liberal en algunos sentidos. En particular:
\begin{itemize}
\item El \texttt{return}
se considera un {\em statement} que puede aparecer en la posici\'on en la que
podr\'ia aparecer cualquier otra instrucci\'on. La restricci\'on de que
el \texttt{return} \'unicamente aparezca como \'ultima instrucci\'on del bloque, y
\'unicamente al final de las declaraciones de funciones y del programa principal,
es una restricci\'on que se posterga para la etapa de chequeo sem\'antico
({\em lint}).
\item Se admite el gui\'on bajo (\chr{\_}) como un posible patr\'on en el lado
izquierdo de las ramas de un \texttt{switch} y en el lado izquierdo de las ramas de un
\texttt{interactive program}.
En una lista de ramas deber\'ia haber un \'unico gui\'on bajo, y deber\'ia ser el \'ultimo
patr\'on de la lista pero esto, de nuevo, se relega a la etapa de lint.
\item Los patrones del interactive program (\texttt{TIMEOUT}, \texttt{K\_ENTER}, etc.) se
admiten como patrones en cualquier switch.
\end{itemize}

Las convenciones de asociatividad y precedencia de operadores no se reflejan
en las producciones, sino en la tabla de precedencia.
(Para expresar esto en la gram\'atica ser\'ia necesario estratificar las expresiones
en t\'erminos, factores, \'atomos, etc., tal como se hace en la gram\'atica oficial).
\bigskip

% El siguiente tex se genera a partir de 02-grammar.json usando gendoc.py.
\input{02-grammar.tex}

\subsection{Precedencia de operadores}

Los operadores se organizan seg\'un la siguiente tabla.
Cada fila corresponde a un nivel de precedencia, ordenados de menor a mayor precedencia.
Las {\em fixities} posibles son:
operador binario asociativo a derecha ({\bf InfixR}),
operador binario asociativo a izquierda ({\bf InfixL}),
operador binario no asociativo ({\bf Infix}),
operador unario prefijo ({\bf Prefix}).

\begin{itemize}
\item {\bf InfixR:} \token{OR} (\texttt{||})
\item {\bf InfixR:} \token{AND} (\texttt{\&\&})
\item {\bf Prefix:} \token{NOT} (\texttt{not})
\item {\bf Infix:}
  \token{EQ} (\texttt{==})
  \token{NE} (\texttt{/=})
  \token{LE} (\texttt{<=})
  \token{GE} (\texttt{>=})
  \token{LT} (\texttt{<})
  \token{GT} (\texttt{>})
\item {\bf InfixL:}
  \token{CONCAT} (\texttt{++})
\item {\bf InfixL:}
  \token{PLUS} (\texttt{+})
  \token{MINUS} (\texttt{-})
\item {\bf InfixL:}
  \token{TIMES} (\texttt{*})
\item {\bf InfixL:}
  \token{DIV} (\texttt{div})
  \token{MOD} (\texttt{mod})
\item {\bf InfixR:}
  \token{POW} (\texttt{\^})
\item {\bf Prefix:}
  \token{MINUS} (\texttt{-}, menos unario)
\end{itemize}

\subsection{\'Arbol de sintaxis abstracta}

El resultado de analizar sint\'acticamente un programa es un objeto.
El objeto representa un \'arbol sint\'actico y est\'a construido
recursivamente de la siguiente manera:
\begin{itemize}
\item Las hojas del \'arbol son instancias de la clase \texttt{Token}
      cuyo atributo 
      \texttt{tag} representa el tipo de token (por ejemplo,
      \texttt{T\_UPPERID})
      y cuyo atributo \texttt{value} representa el valor le\'ido
      (por ejemplo, ``\texttt{PonerN}'').
\item Los nodos internos del \'arbol son instancias de la clase
      \texttt{ASTNode} o, m\'as precisamente, de alguna de sus subclases.
      Un nodo interno tiene dos atributos:
      \begin{itemize}
      \item \texttt{tag}: indica el ``tipo'' de nodo del que se trata.
            Por ejemplo
            una instancia de la clase \texttt{ASTStmtIf}
            representa un comando \texttt{if-then-else},
            y el tag asociado es el s\'imbolo \texttt{N\_StmtIf}.
      \item \texttt{children}: es la lista de hijos del nodo.
            Por ejemplo,
            las instancias de la clase \texttt{ASTStmtIf}
            tienen exactamente tres hijos:
            el primero es una expresi\'on que representa la condici\'on
            del if,
            el segundo es un comando que representa la rama \texttt{then},
            y el tercero puede ser \texttt{null} (si la rama \texttt{else}
            se encuentra ausente), o un comando que representa la rama \texttt{else}.
      \end{itemize}
\item Como se mencion\'o arriba, en algunos (pocos) casos
      las hojas del \'arbol tambi\'en pueden ser \texttt{null},
      que se usa para indicar la ausencia de algunas
      componentes opcionales del \'arbol (tales como la rama \texttt{else}
      de un \texttt{if}).
\item Los hijos eventualmente tambi\'en pueden ser listas de ASTs.
\end{itemize}

Abajo se especifica la forma que tiene un \'arbol usando una sintaxis
similar a la de la declaraci\'on de un tipo de datos inductivo en
Haskell.
Los tipos escritos \type{EN\_MAY\'USCULAS} representan el tipo de los tokens.
Los tipos escritos \type{EnMin\'usculas} representan categor\'ias
abstractas de ASTs
(por ejemplo, \type{Statement} es la categor\'ia abstracta de aquellos
AST que representan comandos).
Las palabras escritas \ast{EnVerde} representan categor\'ias concretas
(en la terminolog\'ia de Haskell, constructores; en el caso de JavaScript
corresponden a subclases de \texttt{ASTNode}).
Por ejemplo, \ast{StmtIf} es la categor\'ia concreta de los AST que
representan un comando if-then-else.
En JavaScript, su clase asociada se llama \texttt{ASTStmtIf},
y su tag asociado es el s\'imbolo \texttt{N\_StmtIf}.

% El siguiente tex se genera a partir de 03-ast.json usando gendoc.py.
\input{03-ast.tex}

\section{An\'alisis sem\'antico}

La etapa de an\'alisis sem\'antico (o {\em linting}) verifica de manera est\'atica que el programa cumpla las siguientes condiciones.
\bigskip

{\bf Programa principal.}
\begin{itemize}
\item El programa \PUEDE estar completamente vac\'io (sin ninguna definici\'on).
\item Si el programa no est\'a completamente vac\'io, \DEBE tener exactamente una definici\'on de programa
      (ya sea un \ast{DefProgram} o \ast{DefInteractiveProgram}).
\item El programa \NOPUEDE tener dos (o m\'as) definiciones de programa
      (ya sean \ast{DefProgram} o \ast{DefInteractiveProgram}).
\end{itemize}

{\bf Nombres globales.}
\begin{itemize}
\item Hay cinco tipos de nombres globales:
  \begin{itemize}
  \item Nombres de procedimientos, declarados con \texttt{procedure}.
  \item Nombres de funciones, declaradas con \texttt{function}.
  \item Nombres de tipos, declarados con \texttt{type}.
  \item Nombres de constructores.
        Coinciden con el nombre del tipo en la declaraci\'on de un tipo \texttt{record}.
        Pueden coincidir o no con el nombre del tipo en la declaraci\'on de un tipo \texttt{variant},
        en cuyo caso se declaran con \texttt{case}.
  \item Nombres de campos, declarados con \texttt{field}.
  \end{itemize}
\item El programa \NOPUEDE tener dos (o m\'as) funciones con el mismo nombre.
\item El programa \NOPUEDE tener dos (o m\'as) procedimientos con el mismo nombre.
\item El programa \NOPUEDE tener dos (o m\'as) tipos con el mismo nombre.
\item El programa \NOPUEDE tener dos (o m\'as) constructores con el mismo nombre.
\item El programa \NOPUEDE tener dos (o m\'as) campos con el mismo nombre correspondientes a un mismo constructor.
      (P.ej. la definici\'on: \texttt{type A is record \{ field x field x \}} se rechaza).
\item El programa \PUEDE tener dos (o m\'as) campos con el mismo nombre si corresponden a distintos constructores,
      ya sea del mismo tipo o de distintos tipos.
      (P.ej. las definiciones: \texttt{type A is record \{ field x \} type B is record \{ field x \}} se aceptan).
\item El programa \NOPUEDE tener una funci\'on y un campo que tengan el mismo nombre.
\item El programa \PUEDE tener tipos y constructores con el mismo nombre.
      P.ej. la definici\'on: \texttt{type A is variant \{ case A {} \}} se acepta.
      De hecho este es el comportamiento normal cuando se declara un registro:
      \texttt{type A is record \{ \}} define simult\'aneamente un tipo \texttt{A}
      y un constructor \texttt{A}.
\item El programa \PUEDE tener procedimientos con el mismo nombre que un tipo o que un constructor.
\end{itemize}

{\bf Return.}
\begin{itemize}
\item Los procedimientos \NOPUEDEN tener un \texttt{return}.
\item Los programas declarados con \texttt{interactive program} \NOPUEDEN tener un \texttt{return}.
\item Las funciones \DEBEN tener un \texttt{return} como \'ultimo comando del bloque.
\item Los programas declarados con \texttt{program} \PUEDEN tener un \texttt{return} como \'ultimo comando del bloque.
\item \NOPUEDE haber un \texttt{return} en ninguna otra posici\'on salvo
      las mencionadas, es decir,
      como el \'ultimo comando de una funci\'on o como el \'ultimo comando de un \texttt{program}.
\end{itemize}

{\bf Nombres locales.}
\begin{itemize}
\item Hay tres tipos de nombres locales:
  \begin{itemize}
  \item Par\'ametros --- est\'an ligados en la lista de par\'ametros de
        un procedimiento, o en la lista de par\'ametros de una funci\'on, 
        o en la lista de variables ligadas al hacer {\em pattern matching}
        con \texttt{switch}. Por ejemplo \texttt{x} e \texttt{y} son par\'ametros
        en los comandos:
        \begin{enumerate}
        \item \texttt{switch (c) \{ Coord(x, y) ->\ ... \}}
        \item \texttt{switch (c) \{ (x, y) ->\ ... \}}
        \item \texttt{switch (c) \{ x ->\ ... \}}
        \end{enumerate}
  \item \'Indices --- est\'an ligados por un \texttt{foreach}.
  \item Variables --- su valor se declara en una asignaci\'on \texttt{x := e} o en una asignaci\'on
        a una tupla \texttt{(x1, ..., xN) := e}.
  \end{itemize}
\item Alcance de los nombres locales:
  \begin{itemize}
  \item Par\'ametros de procedimientos y funciones --- locales a todo el cuerpo del procedimiento o funci\'on.
  \item Variables ligadas en los patrones de un \texttt{switch} --- locales al bloque a la derecha de la correspondiente flecha \texttt{->}.
  \item \'Indices --- locales al cuerpo del \texttt{foreach}.
  \item Variables --- locales a todo el cuerpo del procedimiento o funci\'on.
  \end{itemize}
\item Los nombres locales \PUEDEN
      coincidir con los nombres globales (nombres de funciones y campos), sin
      que unos opaquen a otros.
\item Los nombres locales \NOPUEDEN coincidir con otros nombres locales que comparten el mismo alcance.
      En particular:
  \begin{itemize}
  \item Las funciones y procedimientos \NOPUEDEN tener nombres de par\'ametros repetidos.
  \item Los \'indices de dos \texttt{foreach} anidados \NOPUEDEN tener el mismo nombre.
  \item Los \'indices de dos \texttt{foreach} que no est\'an anidados \PUEDEN tener el mismo nombre.
  \item Los nombres de variables, \'indices, y par\'ametros \NOPUEDEN coincidir.
  \end{itemize}
\item En una asignaci\'on de tuplas \texttt{let (x$_1$, ..., x$_n$) := e}
      las variables \texttt{x$_1$, ..., x$_n$} \DEBEN ser todas distintas. 
\end{itemize}

{\bf Pattern matching.}
\begin{itemize}
\item Hay seis tipos de patrones:
  \begin{enumerate}
  \item Patr\'on comod\'in (\texttt{\_}).
  \item Patr\'on variable (identificador ligado localmente).
  \item Patr\'on num\'erico (un n\'umero $n$, que puede ser positivo, negativo o cero).
  \item Patr\'on estructura (\texttt{C} o alternativamente \texttt{C(x$_1$, ..., x$_n$)}).
  \item Patr\'on tupla (\texttt{(x$_1$, ..., x$_n$)}).
  \item Patr\'on timeout (\texttt{TIMEOUT($n$)}).
  \end{enumerate}
\item Actualmente los patrones se pueden utilizar en cuatro lugares:
      \begin{enumerate}
      \item en las ramas de un \texttt{interactive program},
      \item en las ramas de un \texttt{switch},
      \item en las ramas de un \texttt{matching..select},
      \item como patr\'on de un \texttt{foreach},
            siempre y cuando la opci\'on \texttt{DestructuringForeach}
            haya sido habilitada con la directiva \texttt{/*@LANGUAGE@DestructuringForeach@*/}.
            De lo contrario, el patr\'on de un \texttt{foreach}
            puede ser \'unicamente un patr\'on variable (\'indice).
      \end{enumerate}
\item En un patr\'on estructura, el nombre del constructor en cuesti\'on \DEBE ser un constructor existente de
      alg\'un tipo.
\item En un patr\'on estructura, el constructor \PUEDE tener $0$ par\'ametros, independientemente del n\'umero
      de campos que tenga el constructor correspondiente.
\item Si un patr\'on estructura tiene $1$ o m\'as par\'ametros, el n\'umero \DEBE coincidir con el n\'umero
      de campos del constructor correspondiente.
\item En una secuencia de ramas los patrones estructura \PUEDEN aparecer en cualquier orden, sin respetar necesariamente el orden en que est\'an declarados.
\item Una secuencia de ramas \NOPUEDE tener dos patrones num\'ericos con el mismo valor num\'erico.
\item Una secuencia de ramas \NOPUEDE tener dos patrones estructura asociados al mismo constructor.
\item Una secuencia de ramas \NOPUEDE tener dos patrones tupla con la misma longitud.
\item Una secuencia de ramas \NOPUEDE tener dos patrones timeout.
\item Una secuencia de ramas \PUEDE tener o no tener un patr\'on comod\'in. (No es obligatorio como \'ultima rama).
\item Si una secuencia de ramas tiene un patr\'on comod\'in o un patr\'on variable, dicho patr\'on \DEBE estar en la \'ultima rama.
\item Una secuencia de ramas \NOPUEDE tener un patr\'on comod\'in o un patr\'on variable en ninguna otra rama que no sea la \'ultima.
\item Un patr\'on comod\'in \PUEDE ser inalcanzable.
      Es decir, un patr\'on comod\'in puede estar presente incluso si la secuencia de ramas
      cubre todas las alternativas de constructores posibles.
\item En una secuencia de ramas todos los patrones \DEBEN ser compatibles.
      Son patrones compatibles:
      \begin{itemize}
      \item Dos patrones num\'ericos.
      \item Dos patrones estructura cuyos constructores pertenecen al mismo tipo.
      \item Un patr\'on timeout con cualquier otro constructor del tipo \texttt{\_EVENT}
            (que corresponde a los eventos que pueden darse en un programa interactivo).
      \item Un patr\'on comod\'in con cualquier otro patr\'on.
      \item Un patr\'on variable con cualquier otro patr\'on.
      \end{itemize}
      Dos tipos son incompatibles en cualquier otro caso. En particular, son patrones incompatibles:
      \begin{itemize}
      \item Un patr\'on num\'erico y un patr\'on estructura.
      \item Un patr\'on num\'erico y un patr\'on tupla.
      \item Dos patrones estructura cuyos constructores pertenecen a distintos tipos.
      \item Dos patrones tupla con distinto n\'umero de componentes.
      \item Un patr\'on estructura y un patr\'on tupla.
      \end{itemize}
\item Los patrones de las ramas del \texttt{interactive program}
      \DEBEN ser eventos y \NOPUEDEN ser patrones variable, es decir,
      pueden ser
      patrones timeout,
      patrones estructura del tipo \texttt{\_EVENT}
      o patrones comod\'in.
\item Los patrones de las ramas de los \texttt{switch} y los \texttt{matching..select} \NOPUEDEN ser eventos, es decir:
      pueden ser
      patrones num\'ericos,
      patrones estructura de tipos que no sean \texttt{\_EVENT},
      patrones tupla,
      patrones variable,
      o patrones comod\'in.
\item El patr\'on de un \texttt{foreach} \NOPUEDE ser un evento.
\end{itemize}

{\bf Expresiones.}
\begin{itemize}
\item Los usos de par\'ametros, \'indices y variables (\ast{ExprVariable}) \PUEDEN no corresponder a par\'ametros, \'indices o variables definidas.
      La restricci\'on de que las variables se pueden usar solamente despu\'es de que se les haya dado un valor es una restricci\'on din\'amica.
\item Cuando se construye una instancia de un tipo (registro o variante) con un constructor (\ast{ExprStructure}),
      el nombre del constructor \DEBE ser el nombre de un constructor existente.
\item Cuando se construye o se actualiza una instancia con un constructor (\ast{ExprStructure}, \ast{ExprStructureUpdate}),
      \NOPUEDE haber nombres de campos repetidos en la lista de {\em bindings}.
\item Cuando se construye o se actualiza una instancia con un constructor (\ast{ExprStructure}, \ast{ExprStructureUpdate}),
      los nombres de los campos que aparecen en la lista de {\em bindings}
      \DEBEN ser nombres de campos v\'alidos para dicho constructor. (Correctitud).
\item Cuando se construye una instancia con un constructor (\ast{ExprStructure}),
      los nombres de los campos que aparecen en la lista de {\em bindings}
      \DEBEN cubrir todos los posibles nombres de campos v\'alidos para dicho constructor. (Completitud).
\item Cuando se construye o se actualiza una instancia con un constructor (\ast{ExprStructure}, \ast{ExprStructureUpdate}),
      el constructor \NOPUEDE ser un constructor del tipo \texttt{\_EVENT} (esto t\'ecnicamente depende
      del entorno global en el que se eval\'ue el programa, pero t\'ipicamente
      los eventos son las teclas como \texttt{K\_ENTER}, etc.).
\end{itemize}

{\bf Invocaciones a funciones y procedimientos.}
\begin{itemize}
\item En las invocaciones a procedimientos, el nombre del procedimiento \DEBE corresponder a un procedimiento definido.
\item En las invocaciones a funciones, el nombre de la funci\'on \DEBE corresponder
      o bien a una funci\'on definida o bien al nombre de un campo (usado como funci\'on observadora).
\item El chequeo de coincidencia del n\'umero de argumentos (aridades) se hace est\'aticamente.
      Todos los chequeos de tipos son din\'amicos.
\item El n\'umero de argumentos pasados a un procedimiento \DEBE coincidir con el n\'umero de par\'ametros declarados en su definici\'on.
\item El n\'umero de argumentos pasados a una funci\'on \DEBE coincidir con el n\'umero de par\'ametros declarados en su definici\'on.
\item El n\'umero de argumentos pasados a un campo (usado como funci\'on observadora) \DEBE ser exactamente 1.
\end{itemize}

\section{M\'aquina virtual}

Un programa en Gobstones/XGobstones se compila a una serie de instrucciones para una m\'aquina
virtual {\em ad hoc}. La implementaci\'on de un compilador y una m\'aquina virtual,
en lugar de un mero int\'erprete recursivo, agrega bastante complejidad a la base de c\'odigo,
y es razonable preguntarse hasta qu\'e punto hacer un compilador no es {\em overkill}.

La principal raz\'on para contar con un compilador en este caso no tiene que ver con cuestiones de
eficiencia, sino con la posibilidad de tener representado expl\'icitamente el estado de
ejecuci\'on de un programa.
Esto permite:
\begin{enumerate}
\item Hacer un {\em step} controlado del programa,
      para poder visualizar el avance paso a paso de la ejecuci\'on.
\item Potencialmente pausar y continuar la ejecuci\'on de un programa.
\item Ejecutar programas que potencialmente se cuelgan abort\'andolos por medio de diferentes
      criterios de {\em timeout}.
\end{enumerate}
Esta funcionalidad no se puede implementar de manera directa en un int\'erprete recursivo
(las posibles implementaciones, por ejemplo usando continuaciones, son
dif\'iciles de entender y mantener).

El c\'odigo para la m\'aquina virtual es una instancia de la clase \texttt{Code},
que b\'asicamente consta de una lista de instrucciones. Las instrucciones est\'an
basadas en una arquitectura sencilla ``orientada a pila''.

El estado de ejecuci\'on de un programa consta de los siguientes datos:
\begin{itemize}
\item Un c\'odigo (\texttt{Code}) que, como dijimos, es b\'asicamente una lista de instrucciones.
\item Una pila no vac\'ia de estados globales.
      El estado global actual es el estado en el tope de la pila.
      En Gobstones/XGobstones el estado global corresponde al tablero,
      pero podr\'ia corresponder a otras entidades mutables en otras variantes
      concebibles del lenguaje.
      Cada vez que se ingresa a una funci\'on definida por el usuario,
      el estado global actual se copia y se mete en la pila de estados globales
      (con la instrucci\'on \instruction{SaveState}).
      Cada vez que finaliza una funci\'on definida por el usuario,
      se saca el estado global actual del tope de la pila de estados globales
      (con la instrucci\'on \instruction{RestoreState}).
      Esto permite implementar la sem\'antica de Gobstones,
      de acuerdo con la cual las funciones no tienen efectos (todos sus efectos
      se deshacen).
\item Una ``pila de llamadas'' (\texttt{callStack}).
      La pila de llamadas es una pila no vac\'ia de {\em frames}.
      Un {\em frame} es el estado local
      o contexto de ejecuci\'on de la rutina actual (tambi\'en conocido como
      {\em stack frame} o {\em registro de activaci\'on} en la literatura).
      Un {\em frame} es una instancia de la
      clase \texttt{Frame} y consta de los siguientes datos:
      \begin{itemize}
      \item El {\em instruction pointer}, que es un \'indice dentro de la lista de instrucciones.
      \item Una pila de valores locales.
      \item Un diccionario de nombres locales, que asocia los nombres de
            par\'ametros, \'indices y variables a un valor.
      \end{itemize}
\end{itemize}
Cuando decimos ``el {\em instruction pointer}''
nos referimos al {\em instruction pointer} del {\em frame} que est\'a en el tope de la pila de llamadas.
De igual modo, cuando decimos ``la pila''
nos referimos a la pila del {\em frame} que est\'a en el tope de la pila de llamadas.
\'Idem para el diccionario de nombres locales.

\subsection{Instrucciones}

Las instrucciones de la m\'aquina virtual se describen a continuaci\'on:

% El siguiente tex se genera a partir de 04-instructions.json usando gendoc.py.
\input{04-instructions.tex}

\subsection{Primitivas}

Los tipos, procedimientos y funciones disponibles en el lenguaje de manera primitiva se listan a continuaci\'on:

% El siguiente tex se genera a partir de 04-instructions.json usando gendoc.py.
\input{05-builtins.tex}

\subsection{Snapshots}

Las rutinas (\texttt{program}, procedimientos y funciones),
ya sean primitivas o definidas por el usuario,
tienen asociados dos atributos booleanos:
\begin{itemize}
\item \texttt{recorded}:
      indica si la rutina debe ser ``grabada'', es decir,
      si se debe tomar una {\em snapshot} en el momento en que se retorna de dicha rutina.
\item \texttt{atomic}:
      indica si la rutina debe ser considerada ``at\'omica'', es decir,
      si {\bf no} debe grabarse ninguna {\em snapshot} que ocurra de manera interna
      (es decir, {\em snapshots} correspondientes a rutinas internas).
\end{itemize}
Se aplican las siguientes reglas:
\begin{itemize}
\item El \texttt{program} nunca \texttt{atomic}.
      Además el \texttt{program} {\bf no} es \texttt{recorded}:
      se toma una {\em snapshot} al comienzo del \texttt{program},
      pero no al final. La \'ultima {\em snapshot} será la
      ocasionada por el \'ultimo comando que tenga el atributo \texttt{recorded}.
\item Las funciones nunca son \texttt{recorded} y siempre son \texttt{atomic}.
      (Los efectos que se producen durante la ejecuci\'on de una funci\'on
      son invisibles desde el exterior, de manera que cualquier cambio en el estado
      que se produzca durante la ejecuci\'on de una funci\'on no debe grabarse).
\item Los procedimientos primitivos son \texttt{recorded}.
      (Es irrelevante si son \texttt{atomic}, ya que durante la ejecuci\'on de un procedimiento
      primitivo nunca se invoca a otro procedimiento).
\item Los procedimientos definidos por el usuario, por defecto,
      no son \texttt{recorded} ni \texttt{atomic}.
      (Al ejecutar un procedimiento definido por el usuario, no se graba
      de manera especial el estado que se obtiene al finalizar el procedimiento,
      pero s\'i se graban las {\em snapshots} de todo lo que ocurre en su interior,
      lo que t\'ipicamente incluye el estado que se obtiene al final de su ejecuci\'on).
\end{itemize}
En el futuro se pretende que los atributos \texttt{recorded} y \texttt{atomic}
de las rutinas definidas por el usuario puedan controlarse a trav\'es de pragmas.

\end{document}
