Add section about checks to technote
[barrelfish] / doc / 025-sockeye / Sockeye.tex
1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2 % Copyright (c) 2017, ETH Zurich.
3 % All rights reserved.
4 %
5 % This file is distributed under the terms in the attached LICENSE file.
6 % If you do not find this file, copies can be found by writing to:
7 % ETH Zurich D-INFK, Universitaetstr 6, CH-8092 Zurich. Attn: Systems Group.
8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
9
10 \providecommand{\pgfsyspdfmark}[3]{}
11
12 \documentclass[a4paper,11pt,twoside]{report}
13 \usepackage{amsmath}
14 \usepackage{bftn}
15 \usepackage{calc}
16 \usepackage{verbatim}
17 \usepackage{xspace}
18 \usepackage{pifont}
19 \usepackage{pxfonts}
20 \usepackage{textcomp}
21
22 \usepackage{multirow}
23 \usepackage{listings}
24 \usepackage{todonotes}
25 \usepackage{hyperref}
26
27 \title{Sockeye in Barrelfish}
28 \author{Barrelfish project}
29 % \date{\today}   % Uncomment (if needed) - date is automatic
30 \tnnumber{025}
31 \tnkey{Sockeye}
32
33
34 \lstdefinelanguage{sockeye}{
35     morekeywords={is,are,accept,map,over,to,at},
36     sensitive=true,
37     morecomment=[l]{//},
38     morecomment=[s]{/*}{*/},
39     morestring=[b]",
40 }
41
42 \presetkeys{todonotes}{inline}{}
43
44 \begin{document}
45 \maketitle      % Uncomment for final draft
46
47 \begin{versionhistory}
48 \vhEntry{0.1}{12.06.2017}{DS}{Initial Version}
49 \end{versionhistory}
50
51 % \intro{Abstract}    % Insert abstract here
52 % \intro{Acknowledgements}  % Uncomment (if needed) for acknowledgements
53 \tableofcontents    % Uncomment (if needed) for final draft
54 % \listoffigures    % Uncomment (if needed) for final draft
55 % \listoftables     % Uncomment (if needed) for final draft
56 \cleardoublepage
57 \setcounter{secnumdepth}{2}
58
59 \newcommand{\fnname}[1]{\textit{\texttt{#1}}}%
60 \newcommand{\datatype}[1]{\textit{\texttt{#1}}}%
61 \newcommand{\varname}[1]{\texttt{#1}}%
62 \newcommand{\keywname}[1]{\textbf{\texttt{#1}}}%
63 \newcommand{\pathname}[1]{\texttt{#1}}%
64 \newcommand{\tabindent}{\hspace*{3ex}}%
65 \newcommand{\Skate}{\lstinline[language=sockeye]}
66 \newcommand{\ccode}{\lstinline[language=C]}
67
68 \lstset{
69   language=C,
70   basicstyle=\ttfamily \small,
71   keywordstyle=\bfseries,
72   flexiblecolumns=false,
73   basewidth={0.5em,0.45em},
74   boxpos=t,
75   captionpos=b
76 }
77
78
79 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
80 \chapter{Introduction and usage}
81 \label{chap:introduction}
82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
83
84 \emph{Sockeye}\footnote{Sockeye salmon (Oncorhynchus nerka), also called red salmon, kokanee salmon, or blueback salmon, is an anadromous species of salmon found in the Northern Pacific Ocean and rivers discharging into it. This species is a Pacific salmon that is primarily red in hue during spawning. They can grow up to 84 cm in length and weigh 2.3 to 7 kg. 
85 Source: \href{https://en.wikipedia.org/wiki/Sockeye_salmon}{Wikipedia}}
86 is a domain specific language to describe SoCs (Systems on a Chip). With Sockeye these descriptions can be made available in Barrelfish's System Knowledge Base (SKB) \cite{skb}.
87
88 \todo{More info in introduction}
89
90 The Sockeye compiler is written in Haskell using the Parsec parsing library. It
91 generates Prolog files from the Sockeye files.
92
93 The source code for Sockeye can be found in \texttt{SOURCE/tools/sockeye}.
94
95 \section{Use cases}
96
97 We envision the following non exhausting list of possible use cases for Sockeye:
98
99 \todo{Specify use cases}
100
101
102 \section{Command line options}
103 \label{sec:cmdline}
104
105 \begin{verbatim}
106 $ sockeye [options] file
107 \end{verbatim}
108
109
110 The available options are:
111 \begin{description}
112         \item[-P] Generate a prolog file that can be loaded into the SKB.
113         \item[-C] Just perform checks, do not compile.
114   \item[-o] \textit{filename} The path to the output file (including the file extension)
115   \item[-h] show usage information
116 \end{description}
117
118 The backend (capital letter options) specified last takes precedence.
119
120 The Sockeye file to compile is give via the \textit{file} parameter. The typical file extension for Sockeye files is \verb|.soc|.
121
122
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
124 \chapter{Lexical Conventions}
125 \label{chap:lexer}
126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
127
128 The Sockeye parser follows a similar convention as opted by modern day 
129 programming languages like C and Java. Hence, Sockeye uses a java-style-like
130 parser based on the Haskell Parsec Library. The following conventions are used:
131
132 \begin{description}
133 \item[Encoding] The file should be encoded using plain text.
134 \item[Whitespace:]  As in C and Java, Sockeye considers sequences of
135   space, newline, tab, and carriage return characters to be
136   whitespace.  Whitespace is generally not significant. 
137
138 \item[Comments:] Sockeye supports C-style comments.  Single line comments
139   start with \texttt{//} and continue until the end of the line.
140   Multiline comments are enclosed between \texttt{/*} and \texttt{*/};
141   anything inbetween is ignored and treated as white space.
142
143 \item[Identifiers:] Valid Sockeye identifiers are sequences of numbers
144   (0-9), letters (a-z, A-Z), the underscore character ``\texttt{\_}'' and hyphens ``\texttt{-}''.  They
145   must start with a letter.
146   \begin{align*}
147     identifier & \rightarrow letter (letter \mid digit \mid \_ \mid -)^{\textrm{*}} \\
148     letter & \rightarrow (\textsf{A \ldots Z} \mid  \textsf{a \ldots z})\\
149     digit & \rightarrow (\textsf{0 \ldots 9})
150 \end{align*}
151   
152 \item[Integer Literals:] A Sockeye integer literal is a sequence of
153   digits, optionally preceded by a radix specifier.  As in C, decimal (base 10)
154   literals have no specifier and hexadecimal literals start with
155   \texttt{0x}. Octal literals start with \texttt{0o}.
156
157 \begin{align*}
158 digit & \rightarrow (\textsf{0 \ldots 9})^{\textrm{1}}\\
159 hexadecimal & \rightarrow (\textsf{0x})(\textsf{0 \ldots 9} \mid \textsf{A \ldots F} \mid \textsf{a \ldots f})^{\textrm{1}}\\
160 octal & \rightarrow (\textsf{0o})(\textsf{0 \ldots 7})^{\textrm{1}}\\
161 \end{align*}
162
163 \item[Reserved words:] The following are reserved words in Sockeye:
164 \begin{verbatim}
165 is, are, accept, map, over, to, at
166 \end{verbatim}
167
168 \end{description}
169
170
171
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
173 \chapter{Decoding Net Declaration}
174 \label{chap:declaration}
175 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
176
177 In this chapter we define the layout of a Sockeye file.
178
179 \section{Syntax Highlights}
180 In the following sections we use the syntax highlighting as follows:
181 \begin{syntax}
182 \synbf{bold}:      Keywords  
183 \synit{italic}:      Identifiers
184 \verb+verbatim+   constructs, symbols etc.
185 \end{syntax}
186
187
188
189 \section{Conventions}
190 \todo{Specify conventions}
191
192 \section{The Sockeye File}
193 A Sockeye file consists of one or more node declarations.
194 A node declaration contains one or more identifiers and the node specification.
195 Nodes are specified by declaring their type, the set of accepted addresses, the set of translated addresses and an overlay.
196 Each of these are optional.
197 The order in which the nodes are specified does not matter.
198
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
200 \chapter{Checks on the AST}
201 \label{chap:checks}
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
203 The Sockeye compiler performs some sanity checks on the parsed AST.
204
205 \section{No Duplicate Identifiers}
206 This check makes sure that there aren't two node declarations with the same identifer.
207
208 \section{No References to Undefined Nodes}
209 This check makes sure that all nodes referenced in translation sets and overlays are declared in the same file.
210
211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
212 \chapter{Prolog Mapping for Sockeye}
213 \label{chap:prolog}
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
215
216
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
218 \bibliographystyle{abbrv}
219 \bibliography{barrelfish}
220
221 \end{document}