[Commit] papers/mint_2004 ChangeLog, NONE, 1.1 Makefile, 1.1, 1.2 abstract.tex, 1.1, 1.2 bib.bib, NONE, 1.1 lola.tex, 1.1, 1.2 mint.tex, 1.1, 1.2 nickle.tex, 1.1, 1.2

[Keith Packard]

Committed by: keithp

Update of /local/src/CVS/papers/mint_2004
In directory home.keithp.com:/tmp/cvs-serv21834

Modified Files:
	Makefile abstract.tex lola.tex mint.tex nickle.tex 
Added Files:
	ChangeLog bib.bib 
Log Message:
2004-11-28  Keith Packard  <keithp at keithp.com>

	* abstract.tex:
	Add {} to shut tex up.
	* Makefile:
	* mint.tex:
	* bib.bib:
	Add biblio entries
	* lola.tex:
	Grammar check a bit
	* nickle.tex:
	Add all text


--- NEW FILE: ChangeLog ---
2004-11-28  Keith Packard  <keithp at keithp.com>

	* abstract.tex:
	Add {} to shut tex up.
	* Makefile:
	* mint.tex:
	* bib.bib:
	Add biblio entries
	* lola.tex:
	Grammar check a bit
	* nickle.tex:
	Add all text

Index: Makefile
===================================================================
RCS file: /local/src/CVS/papers/mint_2004/Makefile,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- Makefile	29 Nov 2004 06:40:09 -0000	1.1
+++ Makefile	29 Nov 2004 07:58:15 -0000	1.2
@@ -12,7 +12,6 @@
 .PHONY: subdirs
 
 subdirs:
-#subdirs:
 #	@${MAKE} -C figures ${MAKECMDGOALS}
 #	@${MAKE} -C examples ${MAKECMDGOALS}
 

Index: abstract.tex
===================================================================
RCS file: /local/src/CVS/papers/mint_2004/abstract.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- abstract.tex	29 Nov 2004 06:40:09 -0000	1.1
+++ abstract.tex	29 Nov 2004 07:58:15 -0000	1.2
@@ -1,4 +1,4 @@
-\abstract
+\abstract{}
 The Nickle programming language extends C-like syntax and
 semantics to accomodate modern programming techniques and
 styles.  As such, it is a nice language for implementing

--- NEW FILE: bib.bib ---
@inproceedings{nickle:2001,
 title		= "{Nickle: Language Principles and Pragmatics}",
 author		= "Bart Massey and Keith Packard",
 booktitle	= "FREENIX Track, 2001 Usenix Annual Technical Conference",
 month		= "June",
 year		= 2001,
 organization	= "USENIX",
 address	= "Boston, MA",
 url = "\url{http://www.usenix.org/publications/library/proceedings/usenix01/freenix01/massey.html}",
}


Index: lola.tex
===================================================================
RCS file: /local/src/CVS/papers/mint_2004/lola.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- lola.tex	29 Nov 2004 06:40:09 -0000	1.1
+++ lola.tex	29 Nov 2004 07:58:15 -0000	1.2
@@ -7,35 +7,37 @@
 Parsers for the Lola output were written in C, Pascal and Kalypso.
 
 \begin{figure}
+\footnotesize
 \begin{verbatim}
 ;
 ; this grammar recognises integer
 ; expressions involving +,-,*,/ and unary -
 ;
 (
-(lines          (expr "PRINT" \n lines)
-                (\n lines)
-                ()
-                )
-(expr           (term + term "ADD")
-                (term - term "SUBTRACT")
-                (term)
-                )
-(term           (fact * fact "MULTIPLY")
-                (fact / fact "DIVIDE")
-                (fact)
-                )
-(fact           (|(| expr |)|)
-                (int "PUSH")
-                (- fact "NEGATE")
-                )
-(int            ("CLEAR" "ADD-DIGIT" digit digits)
-                )
-(digits         ("ADD-DIGIT" digit digits)
-                ()
-                )
-(digit          (|0|) (|1|) (|2|) (|3|) (|4|) (|5|) (|6|) (|7|) (|8|) (|9|)
-                )
+(lines  (expr "PRINT" \n lines)
+        (\n lines)
+        ()
+        )
+(expr   (term + term "ADD")
+        (term - term "SUBTRACT")
+        (term)
+        )
+(term   (fact * fact "MULTIPLY")
+        (fact / fact "DIVIDE")
+        (fact)
+        )
+(fact   (|(| expr |)|)
+        (int "PUSH")
+        (- fact "NEGATE")
+        )
+(int    ("CLEAR" "ADD-DIGIT" digit digits)
+        )
+(digits ("ADD-DIGIT" digit digits)
+        ()
+        )
+(digit  (|0|) (|1|) (|2|) (|3|) (|4|)
+        (|5|) (|6|) (|7|) (|8|) (|9|)
+        )
 )
 \end{verbatim}
 \caption{A sample Lola grammar}\label{fig-lola-grammar}
@@ -44,7 +46,7 @@
 The Flo tool was a grammar-to-grammar transformation tool to factor left
 common sub-expressions out of a grammar to permit more compact and easier to
 understand representations of LL(1) languages.  It was also written in
-Kalypso.  Grammars are represented in lisp s-expressions as see in
+Kalypso.  Grammars are represented in lisp s-expressions as in
 Figure~\ref{fig-lola-grammar}, eliminating the need for a custom grammar
 parser and permitting easier grammar-to-grammar transformation tool
 development.  

Index: mint.tex
===================================================================
RCS file: /local/src/CVS/papers/mint_2004/mint.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- mint.tex	29 Nov 2004 06:40:09 -0000	1.1
+++ mint.tex	29 Nov 2004 07:58:15 -0000	1.2
@@ -1,5 +1,5 @@
-\documentclass{article}
-\title{MINT Is A Nickle Translator\\
+\documentclass[twocolumn,12pt]{article}
+\title{MINT Is A Nickle Translator:\\
 Generating Cross-Lingual Recognizers
 }
 \author{Emma Kuo \and James LaMar \and Bart Massey\\
@@ -11,5 +11,7 @@
 \input{abstract}
 \input{lola}
 \input{nickle}
+\bibliography{bib}
+\bibliographystyle{plain}
 \end{document}
 

Index: nickle.tex
===================================================================
RCS file: /local/src/CVS/papers/mint_2004/nickle.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- nickle.tex	29 Nov 2004 06:40:09 -0000	1.1
+++ nickle.tex	29 Nov 2004 07:58:15 -0000	1.2
@@ -1,2 +1,140 @@
 \section{The Nickle Programming Language}
 
+The Nickle Programming Language\cite{nickle:2001} was developed as a C-like
+procedural imperative language with strong types and several useful notions
+adopted from the functional programming community.  Originally targetted
+twenty years ago as an algorithmic prototyping language, it has become more
+generally useful as computer performance has increased over the last two
+decades.
+
+\subsection{Polite Types}
+
+The Nickle type system provides both ``polite'' static typechecking along
+with full dynamic typechecking.  The rule for the compile-time checker is to
+never reject a correct program.  For example, the division operator `/',
+when given integer operands, returns integer results only when the divisor
+is evenly divisible by the dividend, otherwise it returns a ratioanl
+result.  The function:
+\begin{verbatim}
+	int f (int a, int b) { return a / b; }
+\end{verbatim}
+is acceptable to the static typechecking system because it may produce an
+integer result.  Dynamic typechecking is inserted into the generated code to
+check to make sure the result is of the right type at run-time.
+
+\subsection{Structured Values}
+
+Nickle includes an array of composite data types, from arrays and hash
+tables to records and tagged unions.  These behave much like their C
+bretheren, with the exception of arrays which are first-class objects in
+Nickle, unlike C.  Assignment and function parameter passing is done by
+value.
+
+Any non-recursive value within Nickle can be represented within the
+compilation environment as a constant or initializer.  This means that large
+data structures can be generated entirely in-place and used in a dynamic
+context, without resorting to intermediate variables.
+\begin{verbatim}
+	h = (int [string]) { "hello" => 1, "world" => 2 }
+\end{verbatim}
+produces a hash table with the two given elements.  A new hash table is
+constructed each time the constant expression is evaluated.
+
+\subsection{Other Language Features}
+
+Nickle provides for namespaces which are similar to Java modules.  This
+provides a reasonably usable module mechanism with minimal overhead.
+Standard libraries present their functionality entirely within a namespace
+permitting brief names without cluttering the space for application names.
+
+The numeric system in Nickle provides three representations:
+
+\begin{enumerate}
+\item Arbitrary precision integers
+\item Arbitrary precision rationals
+\item Arbitrary mantissa-length floats with arbitrary precision exponents
+\end{enumerate}
+
+The semantics of all operators is well defined by the language specification
+in all cases and is constant across all Nickle implementations.  Rationals
+are normally presented with `{' and `}' surrounding the repeating part of
+the decimal expansion.  Floating point numbers default to 256 bits of
+mantissa, providing sufficient accuracy for iterative development
+of numeric algorithms.
+
+From the functional programming community, Nickle inherits first-class
+functions, closures and continuations.  Nickle exposes continuations
+throught the C-like setjmp/longjmp API which has proven a comprehensible
+mechanism to programmers transitioning from purely imperative languages.
+
+A thread API is included to permit the development of parallel algorithms.
+This includes threads, mutexes, semaphores and a fixed priority scheduler.
+
+\subsection{Well Defined Behaviour}
+
+Every operator in Nickle has a well defined behaviour; there are no
+``implemenetation defined'' sections in the specification.  Expressions in
+Nickle are always evaluated left-to-right.  Integers and rational values are
+arbitrary precision, avoiding machine word size dependencies.  Floating
+point numbers have user-defined mantissa size and arbitrary precision
+exponents, permitting precise numeric computations.  These guarantees provide
+a consistent and straightforward interpretation for Nickle programs in all
+implementations.
+
+\subsection{The Nickle Grammar}
+
+With a sometimes painful adoption of C syntax, Nickle has stretched the
+capabilities of existing parser generators significantly.  There remain in
+the current LALR grammar four reduce/reduce conflicts and one shift/reduce
+conflict.  The reduce/reduce conflicts are ``resolved'' by ensuring that the
+more common expressions are accepted while the unusual ones rejected.
+Obviously it would be nice if this artificial syntax restriction were
+removed.
+
+The YACC-based tools provide only for synthesized attributes and Nickle
+uses inherited attributes at some points in the parse.  To work around this,
+a kludge was inserted into the actions to store inherited attributes inside
+the existing value stack using ``$0'' and ``$-2'' as positional values.
+
+Printing a function value produces a text representation of the function, so
+the compiler must retain the entire parse tree.  With YACC tools, a
+hand-constructed tree is used.  Each time the language syntax changes, this
+code must be modified to match.
+
+\subsection{Using Nickle for Parser Generation}
+
+The choice of implementation language for any project is generally quite
+important.  Selecting the right language reduces the semantic gap between
+problem and program representation.  Contrarywise, the wrong language can
+cause the programmer to spend large amounts of time in low level bookkeeping
+algorithms and other semantic impedence matching code.
+
+As parser generation involves complex data structures and manipulations on
+large sets of objects, a language which provides reasonable typechecking
+along with automatic storage management seems like a good fit.  As with Lola
+and Flo above, the ability to interact with the parser immediately reduces
+the time needed to verify changes in the grammar.
+
+All of these make Nickle a good choice for a parser generator implementation.
+
+\subsection{Using Nickle for Parsing}
+
+Given a Nickle-based parser generator, one possible result would be to force
+developers to also use Nickle for the resulting parser.  Such a B\&D approach
+would not serve the developers well:
+
+\begin{enumerate}
+\item Nickle is not a widely used language.  As such, few developers would
+be able to develop parsers.
+\item Nickle is not a high performance language.  With strictly defined
+semantics and arbitrary precision numerics, the typical Nickle program runs
+tens of times slower than equivalent C or Java code.  A parser in Nickle
+would probably not perform acceptably in most environments.
+\item Parsers are often embedded in other applications.  Attempting to
+access a Nickle function from an existing application places significant
+demands on the application developer.
+\end{enumerate}
+
+Hence, while a good language for producing a parser generator, it would
+behoove the designers to consider permitting other languages for the
+final parser implementation.