\documentstyle[twocolumn]{article} 

\textwidth = 6.75in
\oddsidemargin = 0 in
\evensidemargin = -0.25 in
\topmargin = -0.25 in
\textheight = 9.5 in
%\footskip = 0.5 in

%\parindent = 0 in
%\parskip = 10 pt

\begin{document}
\bibliographystyle{alpha}

\title {
			A Compiler for the Tcl Language
}

\author {Adam Sah and Jon Blow \\
\\ %skip some space
Computer Science Division \\
Electrical Engineering and Computer Sciences \\
University of California \\
Berkeley, CA 94720 \\
(asah@cs.Berkeley.EDU, blojo@xcf.Berkeley.EDU)
}
\date {May 24, 1993}

\maketitle
\begin{abstract}

Tcl is a highly dynamic language that is especially challenging to execute
  efficiently.  The dual-language nature of the system enforced by the C
  callback mechanism makes traditional compilation and optimization
  unrealistic.  In addition, the lack of formal data types (and therefore
  type checking) places severe limits on the ability to provide for
  efficient data storage at compile time.  In this paper, we discuss the
  many issues involved with compiling Tcl, and present a design for such a
  system, including the mechanism for embedding a Tcl script into the
  compiler itself in order to provide user extensibility.  The current
  implementation is presented along with results showing approximately ten
  times the performance of the existing Tcl interpreter.

\end{abstract}

\newcommand{\T}{\hspace{.2in}}

\newlength{\xwidth}
\newlength{\secwidth}
\settowidth{\xwidth}{\sc x}
\settowidth{\secwidth}{\sf $ mu$sec}
\addtolength{\secwidth}{-\xwidth}

\section{Introduction}

\subsection{Overview of the Tcl Language}

Tcl\cite{tcl} is designed to address the need for a ``scripting'' language,
  providing high-level control over a program.  The interface between Tcl
  and the running program consists of the Tcl runtime library, which is
  embedded into the C application code.

Tcl appears to the programmer as a syntactically simple combination of Lisp
  \cite{lispcraft}, Perl \cite{perl} and the Unix Shell language \cite{sh}.
  Like the Unix Shell, it supports nested commands, automatic
  concatenation, and newline-command-termination.  From Lisp, it borrows
  `defun'-like syntax, default procedure arguments, and eval().  Like Perl,
  Tcl's only data type is the string.

In Tcl, every statement can be thought of as a function call, in the form
  of ``cmd arg arg arg'', where the `cmd' pseudo-function is the first
  whitespace-separated argument and the args are the various
  whitespace-separated items that follow it.  Square-brackets denote nested
  commands; dollar-signs indicate variable substitution; curly-braces serve
  to group text into a single argument, without performing substitution.

An example follows:
\begin{verbatim}
# comments start with a '#' character.
# sets variable a to value "5"
#   (the string, not the number!)
set a 5
  
# sets b to the string "10".
# The 'expr' command converts the string
#   "5" to the number 5, (it is not
#   performed by the interpeter)
set b [expr $a+5]
  
# sets c to "5.510"
set c $a.$a$b
  
# outputs the string "5".
puts stdout $a
  
# define a new function
#  note default argument of '1'.
# 'proc' is a command taking "fact", 
#  "{n 1}" and "if ... " as arguments
#  (curlies are stripped by the interpreter).
proc fact { {n 1} } {
  if {$n <= 1} {
    return 1;
  } else {
    return [expr $n*[fact [expr $n-1]]];
  }
}
  
# "foo" is called with args "bar", "7"
foo bar 7
\end{verbatim}

One of the most interesting features of Tcl is its ability to be embedded
  and extended through its C language library.  From the C programmer's
  perspective, the Tcl interpreter is treated as an instantiable object
  (embedded), which is passed the contents of the script to be run.  This
  object exists as a data structure in C working in tandem with a C
  function library.  The Tcl runtime library exposes all of the core
  commands to the C programmer directly, so Tcl statements may be executed
  as C function calls to routines provided by the library.  This library is
  identical to the one that Tcl uses to evaluate statements in a script.
  Thus, programs like {\tt wish} are nothing more than main loops which
  collect user input and pass it one statement at a time to a routine
  called Tcl\_Eval().

Tcl can also be extended from the C program by registering commands with
  the Tcl interpreter.  The interpreter will call back to your C code when
  and if that Tcl command is executed.  In fact, this is how all of the
  core language commands are implemented.  In the above example, the {\tt
  set} command is nothing more than a registered callback whose function
  pointer is the library function which handles set - the very same one
  which is available to the C language programmer directly!  The last
  statement in the example, ``foo'' doesn't exist in the default Tcl
  language - it is either a call to a procedure defined in Tcl itself using
  the {\tt proc} mechanism, or a callback to a C function defined by the
  user, where the arguments ``bar'' and ``7'' are passed to it, in their
  string forms.

\subsection{Why Do We Need to Compile It?}

Most Tcl scripts and commands are designed to operate over high level,
  expensive constructs, where speed is not the primary consideration.  In
  these cases, the cost of the interpretation is negligible compared to the
  overhead within individual callback functions.  For example, on a Sun
  Sparc2, the {\tt set} command takes under 75 microseconds.  By
  comparison, creating a new window in X Windows can take a
  human-noticeable amount of time, even on faster workstations.  Using Tcl
  as a heavyweight integration tool generally does not impact application
  performance.  Even in cases where it does, performance bottlenecks in Tcl
  can easily be isolated and rewritten in C, in the form of callbacks.

However, this recoding is annoying and inbihits the configurability that
  Tcl offers; it can also remove some of the modularity of a well-written
  Tcl-based program.  For example, if you discover that a loop
  written in Tcl is a performance bottleneck, it would be rewritten in C,
  and a new command registered with the Tcl interpreter.  Once this has
  been done, any commands in the loop are now hard-coded relative to
  the high degree of configurability that Tcl offers.

\subsection{Summary}
In the remainder of the paper, we discuss the design and implementation of
  the compiler in depth.  Section 2 describes the compiler interface, an
  overview of the user's view of the compilation system.  Section 3
  discusses the high-level design decisions involved with the efficient
  execution of Tcl.  In Sections 4 and 5, the given implementation is
  presented, first in terms of the compiler, and then in terms of the runtime.
  Section 6 presents the results of this implementation through a series of
  small benchmarks, and Section 7 summarizes our efforts and proposes future
  work.

\section{The Compiler Interface}

\subsection{Previous Work}
\subsubsection{Emacs Lisp}

Emacs is a programmable editor whose underlying language is a variant of
  MockLisp called Emacs Lisp\cite{elisp} (or elisp for short).  Included in
  this system is a ``byte-compiler'' which preparses the code to a binary
  format.  All of the elisp source files are stored in a single directory,
  with names ending in ``.el''.  Byte-compilation of a source file is
  output to the same filename with the extension ``.elc''.  When this
  source file would otherwise be loaded, the system automatically looks for
  a compiled version of it and will load that in the place of an original
  source file.

The byte-compiler's output is highly portable.  This means that
  compiled elisp files can be placed on servers, side by side with the
  original source code, instead of requiring a separate set for each
  architecture.

\subsubsection{Perl}

Perl\cite{perl} is a scripting language with many characteristics of Tcl:
  it is designed for high-level control over arbitrary input, its syntax is
  designed around the string data type, and its support for data types is
  nearly identical- associative arrays, scalar variables, and arrays of
  scalars (which are similar to Tcl lists).

Perl lacks embeddability, and so fails to a large degree to serve as a
  high-level control language.  Note, however, that Perl does support
  arbitrary inter-process communication (IPC), so applications which can
  talk in this way can interface with Perl using this facility.

Perl is compiled on demand each time the script is loaded.

\subsection{The User Interface}

The Tcl Compiler (TC) operates much like the elisp byte compiler: it
  produces binary files which the runtime system knows to look for, and if
  found, will use in the place of the raw source when executing.  This
  runtime is essentially a replacement Tcl interpreter, which takes as
  input binary data from a file, instead of textual data.  Like elisp, TC's
  output files are portable, and so can be placed on servers.

The reason we chose this model is that Tcl cannot be compiled into
  pure machine code without the support of a large runtime library.  This
  is due to the user-extensibility system, where builtin commands can be
  overloaded, removed, added, etc.  Even simple statements may have
  completely different behaviors dependent on some portion of code that the
  compiler does not have access to.  This property is described in further
  detail below.

One alternative would have been to follow Perl's model, where the source
  code is read at runtime and compiled on-the-fly before each execution.
  However, Tcl has a high parsing cost, so it is desireable to preparse
  source code prior to execution.  Additionally, Tcl is used for large
  applications, some of which are 10,000 lines long.  These programs must
  be compiled prior to execution.

\section{Difficulties with Compiling}

\subsection{Some Terms}
To simplify this paper, some terms are explicitly defined.  A ``statement''
  refers to an individual line of Tcl code, including all arguments.  The
  first argument is called the ``command''; all subsequent
  whitespace-separated arguments are called ``arguments'' or ``args''.  If
  a command was not defined by {\tt proc}, but exists in the interpreter
  (eg.  it is a registered C callback function), it is called a
  ``builtin''.  Note that the entire Tcl core command set is implemented as
  builtins.

\subsection{Overview}

It is tempting to naively design a traditional compiler for Tcl, which
  outputs pure executable code.  However, there are numerous problems with
  this.  First, Tcl is highly dynamic in nature.  Commands (functions in
  the C model) can be called by their string names or rebound at any point
  through the {\tt rename} command.  Similarly, variables can be {\tt
  unset}, commands may not exist (and hence trigger {\tt unknown} to be
  called), traces can be placed on all data objects, and so on.  To
  implement all of these features would require both a large runtime
  library and enormous overhead in each usage, not dissimilar from the same
  overhead that the existing interpreter incurs.

Second, it is unclear how to efficiently store data for Tcl.  Since there
  are no types in the language, there is no obvious data layout method one
  can use besides strings.  Again, this is what the current interpreter
  does.

Lastly, Tcl uses C callbacks (``builtins'') as first-class functions, where
  the callbacks have direct access to the interpreter state.  Callback
  functions are free to make changes to, or depend on, the state of the
  virtual machine; these are called ``side effects'' in compiler parlance.
  The difficulty with these side effects in the Tcl/C model is that they
  are impossible to predict.  Without this knowledge, the compiler cannot
  be sure that any given statement won't cause a {\tt rename}, {\tt unset}
  or some other state change in the virtual machine.

\subsection{Preparsing}

A more humble approach is needed.  In this vein, one can start by noting
  that Tcl's ``cmd arg arg arg'' style statements lend themselves to
  preparsing.  This is because it is always possible to determine the
  arguments to a given command.  At the very least, the compiler can break
  up the statement into string arguments, which will save some amount of
  parsing effort normally expended at runtime.  Preparsing is very valuable
  in Tcl; a typical Tcl script spends most of its non-work-related
  execution time scanning and parsing statements.

However, preparsing statements into arg lists is not a panacea.  Many
  important commands take arguments containing large amounts of data.  For
  example, {\tt if}, {\tt while}, {\tt proc}, {\tt for}, and other commands
  all take ``command lists'' in one or more arguments.  These cmdlists are
  often hundreds of bytes long; they effectively can contain entire scripts
  within them.  Clearly, one would like to parse these internally as well.
  By the same token, we would like to also preparse the boolean expressions
  associated with {\tt for}, {\tt if}, and {\tt while}, and the list
  structures used by {\tt lindex} and the other list commands, and so on.
  In the following example, if arguments weren't individually parsed, the
  body of this {\tt for} loop would remain in string form, and would
  require runtime parsing, and thus the compiler would provide little
  performance improvement.

\begin{verbatim}
  for {set i 0} {$i<1000} {incr i} {
      <many lines of code>
  }
\end{verbatim}

To accomplish this, a typing system for Tcl is needed, where one doesn't
  exist.  Normally, the types are coerced from string data at runtime, on a
  per-command basis.  It is happenstance that the list format is universal
  among list commands, for example.  Thus, some way is needed to inform the
  compiler as to the argument types each command expects.  Then, if a
  static string is found at compile-time, we can preparse this to be of
  that type.  For example, since almost all cmdlists are surrounded by
  curly braces in Tcl source code, the contents are static (no substitution
  will occur prior to the argument being passed to the command).  These can
  then be parsed at compile-time, and treated as a list of commands.  In
  the case where variable substitution is allowed, such preparsing cannot
  happen, since the argument value depends on a variable's value, which is
  unknown at compile-time.

\subsection{Solving the Side Effects Problem}

While it seems that user-defined C callbacks present an intractable
  optimization problem, it actually is possible to guess the state of the
  virtual machine from the Tcl source code.  In Tcl, user-defined callbacks
  are required to use a set of C library routines to access the Tcl
  internals (ie. variable values).  Our system adds hooks to this core Tcl
  library, which will call out to TC routines when triggered.  This allows
  the TC runtime to maintain more efficient structures, and keep them
  updated if they change unexpectedly.  For example, the TC runtime
  maintains a table of commands, which is directly indexed, in order to
  save on the hashing costs normally associated with Tcl variable access.
  When a C callback function attempts to rename a command, this is trapped
  and the table entry is updated.

However, this mechanism is still insufficient to allow for more aggressive
  optimizations, since you cannot determine what the dependencies are until
  they are triggered.  Thus, it is impossible to implement optimizations
  that involve code motion, elimination of unused variable assignments, and
  so on.

\section{The TC Implementation}

\subsection{Preparsing- Expression Forest}

The Tcl compiler uses a preparsing method, as described above, to output a
  tree-like structuring of expressions and commands.  At the roots are the
  individual top level script statements, which include only those commands
  not nested in cmdlists within control structures.  For example, all
  commands found within the arglists for commands like {\tt proc}, {\tt
  if}, etc.  cannot be roots of the tree, although the {\tt proc}, etc.
  commands can be, if they themselves are not nested.

The node types for this tree include notations for nested commands ({\tt [
  ...  ]}), concatenated expressions (ie. {\tt \$a\$b}), etc.  An example
  follows:

\vspace{.1in}

{\bf Source Code}

\begin{verbatim}
# this is a comment
set a 5                    

# concatenate the returns of the two nested
#   commands and pass it as an arg to foo.
foo [bar set][foo {5}]     
\end{verbatim}

\vspace{.1in}

{\bf Expression Dictionary (Parse Tree)}
\begin{tabbing}
  xxxx \= xxxx \= xxxxxxxxxxxxxxxx \= \kill
  \> 1. \>  cmd   	\>	``set'' \\
  \> 2. \>  constant  \>  ``a'' \\
  \> 3. \>  constant  \>  ``5'' \\
  \> 4. \>  cmd   	\>	``foo'' \\
  \> 5. \>  cmd   	\>	``bar'' \\
  \> 6. \>  constant  \>  ``set'' \\
  \> 7. \>  nested statement  \>      [2 args][\#5][\#6] \\
  \> 8. \>  nested statement  \>      [2 args][\#4][\#3] \\
  \> 9. \>  concat     \>   [2 args][\#7][\#8]
\end{tabbing}

\vspace{.1in}

{\bf Top Level Command List (Tree Roots)}

\begin{verbatim}
  [3 args][#1][#2][#3][2 args][#4][#9]
\end{verbatim}

Notes: ``\#n'' refers to a reference to item number n.  The compiler
  detects multiple uses of the same constants and other primitive objects,
  and reuses these entries.  For example, the entry for the {\bf foo}
  command (\#4) is reused.  This system is also able to recognize the
  difference between commands and static strings, where the command name is
  the first argument.  It also strips the curly braces from the static
  string in the third line of code.  The concatenation and nested commands
  were discovered at compile time.  Lastly, comments have been stripped.

\subsection{Argument Parsing}

As described previously, it is necessary to preparse arguments in order to
  achieve real performance gains.  To support this, we introduce a type
  system into Tcl for parsing compile-time constants, and a system for
  determining which builtin commands expect which types for each argument.
  
Consider the `incr' command.  In its first argument, it expects to be
  passed the name of a variable.  In its second argument it (optionally)
  expects an integer value (a string which can be parsed as an integer).
  Thus, if the input contains the statement

\begin{verbatim}
  incr a 5
\end{verbatim}

  we can know to treat ``a'' as the variable whose name is ``a'', not the
  string ``a''.  Likewise, ``5'' here is the integer value 5.  Note that if
  the ``5'' were replaced by ``\$b'' for example, then we couldn't assume
  anything, except that the value of b might be a string which has an
  integer representation.  Even this is not necessarily true, since Tcl
  supports exception handling, so this blunder may be intentional!  The
  handling of these more difficult cases is discussed below in the runtime
  system, since these are dynamic effects that are orthognal to the
  problems encountered by the compiler.

It would be entirely possible to hardcode the compiler to recognize these
  types and the commands which use them.  However, Tcl is extendable.  This
  means that a user could potentially author his or her own builtin which
  takes as an argument a list or some other large structure, which we would
  like preparse.  Thus, it makes more sense to allow the compiler itself to
  be extensible, so such power users can compile their own commands and
  arguments.

For this job, Tcl itself is ideal, and hence we embed an interpreter into
  the compiler.  This interpreter reads in a config script at startup which
  declares data type support and associates them to builtin commands.  The
  Tcl script contains the following two commands, in addition to the Tcl
  core.  The backslahes indicate that the arguments should be part of a single
  command.

{\small
\begin{verbatim}
  type <name> <parseproc> <codegenproc> \
       <loadproc> <printproc>
\end{verbatim}
}

This declares a new argument type, which will use {\tt parseproc} to
  convert string data into parsed data of this type, {\tt codegenproc} to
  output into binary form, {\tt loadproc} to load at runtime, and {\tt
  printproc} to converted back into string form for output.  These procs
  are just names, which are associated statically by the C callbacks to
  real C function pointers taking specific arguments, using the Tcl hashing
  mechanism provided by the Tcl core library (Tcl\_HashXxxx).

{\small
\begin{verbatim}
  builtin <name> <parseproc> <codegenproc> \
          <loadproc> <execproc> {
      { <type1>   <argname1> }
      { <type2>   <argname2> <default2> }
      ...
  } <return_type>
\end{verbatim}
}

This declares a new command to be compiled specially, named {\tt <name>},
  with procs defined for its compilation and evaluation.  Note that all but
  the execproc may be left empty (passed {\tt \{\} }, which evaluates to
  the null string) because virtually all commands follow a standard style
  employing known types for each argument.  When left empty, TC substitutes
  a default routine to process the builtin.

For each list element in the body of the builtin declaration, we specify
  what argument type should be passed to this command.  A name is required
  for identification, debugging, and bookkeeping purposes.  The optional
  third element is a default string for that argument.  For example, the
  `incr' command is described as follows:

\begin{verbatim}
  builtin incr {} {} {} exec_incr {
      { variable	var }
      { integer	i	1 }
  } integer
\end{verbatim}

The ``1'' is preparsed as type integer and entered into the dictionary.  If
  {\tt incr} is called with only one argument, the runtime will substitute
  this default value for the second argument.

\section{Runtime Issues}

As described previously, the TC runtime consists of an interpreter capable
  of reading in byte encoded Tcl scripts, preparsed as above.  In order to
  support possible state changes such as command renaming, the
  Tcl core library is modified to update the state of the byte-code
  interpreter when these changes occur.

It is now appropriate to discuss the actual execution of commands in this
  new environment.  In order to take advantage of the preparsing the
  compiler has done, we need a new callback interface.  This is because the
  standard argc/argv interface defeats the purpose of preparsing by taking
  string as arguments.

This implies the need to modify the C callback routines for any commands
  which are to be compiled.  This requirement is entirely reasonable.
  First, the new interface is very easy to construct from the argc/argv one
  for a given command.  Second, the argc/argv interface is extremely slow
  due to its use of runtime parsing, and would require modification in any
  higher-performance system.  Lastly, not builtins need to be compiled.
  Only those which are frequently called or which are passes large amounts
  of data impact the performance of the final application.

This model needs to be extended in order to minimize the parsing done at
  runtime, which still happens for non-static strings.  First, we modify
  the data return system from using only strings (Tcl\_AppendResult()) to
  using this parsed form of a typed data pointer when the new style of
  compiled callbacks are in use.  This is needed so that the results of one
  command can be passed directly to another without reparsing the data
  return.  An example follows:

\begin{verbatim}
  incr a [expr 4+5]
\end{verbatim}

  Assuming that both {\tt incr} and {\tt expr} are being compiled, we would
  like the return from {\tt expr} to be the value 9, not the string ``9''.
  This could then be directly sent into {\tt incr} without reparsing.  The
  only way to avoid such reparsing is if {\tt expr} doesn't convert its
  result into string format.  Hence the need for this new style of return.

We also need to change the way that variables are stored in the Tcl
  interpreter.  If we take the above example and modify it to read

\begin{verbatim}
  set b [expr 4+5]
  incr a $b
\end{verbatim}

  it becomes clear that if we disallow the value of ``b'' to be stored in
  parsed form, we cannot avoid reparsing it before its usage in {\tt incr}.
  Thus, TC ``dual-ports'' its variables, storing both a string pointer as
  well as a compiled data value (the ``typed data field'').  Now, if {\tt
  expr} returns an integer, then ``b'' will store it in the typed data
  field, and invalidate the string field.  {\tt incr} can then be called
  directly with this parsed value.  If ``b'' were of some other type, it
  would need to be converted to a string first, then back to an integer, as
  Tcl currently does implicitly.

If this seems overly complex, recall that Tcl is a typeless language.
  Lists, boolean expressions, integers and so on are not distinguished by
  Tcl until individual commands throw exceptions based on bad data.  The
  following code with execute without error:

\begin{verbatim}
  proc cdr {list} { 
      return [lrange $list 1 end]
  }
  set i 2; set j 3; set k "3 4"
  linsert "$j $k" [cdr {1 2}] $i$j
\end{verbatim}

  The output of this command is ``3 3 23 4''.  During the course of
  execution we have implicitly converted from string to integers, strings
  to lists, lists to integers, and integers to strings.  While this is
  clearly not an example of good coding practice, it is legal Tcl input,
  and in many cases similar usages may appear in real source code.
  It is imperative that the TC runtime be able to perform these
  operations smoothly.

The ``dual-port'' implementation provides sufficient machinery to coerce
  data into parsed form, and keep it there as long as possible.  The rule
  for statements is now simple: for each argument, convert the given data
  to the proper type, then call the compiled callback interface once the
  arguments are assembled.  The rules for conversion amount to treating the
  two data fields as caches to the value.  If the data is required in a
  specific type, and does not currently exist in that form, it is
  converted.  If the destination type is a string, its value is stored in
  the string field; otherwise, the value is stored in the
  typed data field.  The writing of a field is treated as follows:

\begin{center}
\begin{tabular}{lll}
{\bf Currently} & & \\
{\bf Valid}	&	{\bf Writer}	&	{\bf Action} \\ \hline
string only		&	string	&	string form updated. \\ \hline
typed only		&	string	&	string form updated, \\
				&			&	typed form invalidated. \\ \hline
both			&	string	&	string form updated, \\
				&			&	typed form invalidated. \\ \hline
typed only		&	typed	&	typed form updated. \\ \hline
string only		&	typed	&	typed form updated, \\
				&			&	string form invalidated. \\ \hline
both			&	typed	&	typed form updated, \\
				&			&	string form invalidated. \\ \hline
\end{tabular}
\end{center}

  An example is provided:

\begin{verbatim}
  set a 2
  set b [expr 4*$a]
  incr b
  puts stdout $b$a
\end{verbatim}

When {\bf a} is initially set to ``2'', its value becomes the string ``2'',
  rather than the integer value 2.  This is because we cannot assume its
  usage as an integer later (and data lossage might result if we guessed
  wrong).  Its usage in the {\tt expr} call is without curly-braces, so
  again we cannot make assumptions about the compile-time parsing of
  ``4*\$a'' (consider what happens if {\bf a} is reset to the string
  ``4+5'').  As grim as this seems, {\bf b} still receives the integer
  value ``8'', because the call to {\tt expr} returned the numeric value 8.
  Hence the call to {\tt incr} requires no parsing.  In the {\tt puts} call
  of the last statement, {\bf b} requires conversion to string form, but
  {\bf a} does not.

To see the real benefits of this system, a more realistic example is
  presented, where we sum the first thousand integers (the hard way):

\begin{verbatim}
  set sum 0
  for {set counter 0} {$counter<1000} {
       incr counter} {
    incr sum $counter
  }
\end{verbatim}
  
In the standard Tcl interpreter, this requires 6000 calls to hash the
  strings ``counter'', ``sum'' and ``incr''; the value of ``counter'' is
  parsed 3000 times and the value of ``sum'' 1000 times; and the comparison
  string is parsed 1000 times.  In TC, no hashing occurs (it happens at
  load time), the values are parsed precisely once (during the first
  iteration, when it converted the values to integers), and the comparison
  string was preparsed, so no effort was required at runtime.

\section{Results}

The above example involving summing the first 1000 integers required 630
  milliseconds on a DecStation 3100 using {\tt wish}.  Using TC, it
  required only 57 milliseconds for speedup of 11 times.  Some more
  examples follow which illustrate the relative strengths and weaknesses of
  TC.  Note that in no case is TC slower than the original Tcl interpreter.

\vspace{.25in}

Test 1: Simple variable access and the {\tt incr} command.
  This is espeically fast under TC, because only the first iteration needs
  to parse the value of {\tt counter}.  The {\tt time} command is used to
  perform iteration because a {\tt for} loop would interact with the timing
  data.  Note that the times are per iteration in this case.

\begin{verbatim}
  set counter 0
  puts stdout [
      time {incr counter} 50000
  ]
\end{verbatim}

\begin{center}
\begin{tabular}{lrl}
\multicolumn{3}{c}{\bf Performance- $\mu$sec per iter.} \\ \hline
Uncompiled Tcl:	&	219		&	$\mu$sec \\
Compiled Tcl:	&	18 		&	$\mu$sec \\ \hline
Speedup:		&	{\bf 12.17x}	&			 \\
\end{tabular}
\end{center}

\vspace{.3in}

Test 2: Empty loop.  The limiting factor of loops are the
  boolean expressions, which are less efficient to evaluate than simple
  variable accesses, as compared to uncompiled Tcl.

\begin{verbatim}
for {set counter 0} {
     $counter<10000} {
     incr counter} {
}
\end{verbatim}

\begin{center}
\begin{tabular}{lrl}
\multicolumn{3}{c}{\bf Performance- msec total} \\ \hline
Uncompiled Tcl:	&	 3,670		&	msec \\
Compiled Tcl:	&	   425 		&	msec \\ \hline
Speedup:		&	{\bf 8.64x}	&			 \\
\end{tabular}
\end{center}

\vspace{.3in}

Test 3: Nested loops.  This shows a more realistic example of
  the relative speedups of loops.

\begin{verbatim}
for {set count1 0} {	
  $count1<1000} {incr count1} {	
  for {set count2 0} {	
    $count2<1000} {incr count2} {			
  }			
}	  
\end{verbatim}

\begin{center}
\begin{tabular}{lrl}
\multicolumn{3}{c}{\bf Performance- msec total} \\ \hline
Uncompiled Tcl:	&	14,090		&	msec \\
Compiled Tcl:	&	 1,649 		&	msec \\ \hline
Speedup:		&	{\bf 8.54x}	&			 \\
\end{tabular}
\end{center}

\vspace{.3in}

Test 4: Pessimistic case- we can do nothing but break the
  inner command into arguments and pass to the normal evaluation mechanism,
  because the command is not known at compile time.

\begin{verbatim}
set oper incr			 
set count 0  
puts stdout [time {
  $oper count 2} 10000   
]      
\end{verbatim}

\begin{center}
\begin{tabular}{lrl}
\multicolumn{3}{c}{\bf Performance- $\mu$sec per iter.} \\ \hline
Uncompiled Tcl:	&	244			&	$\mu$sec \\
Compiled Tcl:	&	188 		&	$\mu$sec \\ \hline
Speedup:		&	{\bf 1.30x}	&			 \\ \hline
\end{tabular}
\end{center}

\vspace{.3in}

%%%Note: the optimal fibonacci implementation in Tcl is:
%%%proc fib n {if $n<2 {return $n} {return [expr [fib [incr n -1]]+[fib [incr n -1]]]}}

\section{Conclusions and Future Work}

When this project was started, it was unclear that compiling Tcl was even
  feasible, much less useful.  The performance metrics taken clearly
  show that it is feasible.  The latter will be determined as this project
  nears release and users begin compiling real Tcl scripts.  However, the
  results are auspicious: ten-fold performance improvements are almost
  always useful.

The existing system is far from complete.  There are many types and many
  commands which have not been implemented, and are currently being left in
  string form by the compiler and runtime system.  Internally, the software
  has been kludged in several places in order to provide fast
  proof-of-concept, at the expense of long-time viability, which will have
  to be replaced in the near future.  Lastly, there are the usual array of
  bugs, which must be eradicated before any attempt is made at production
  usage.

On the wish list, we include the ability to support direct-conversion
  functions.  This is needed in the case of a arg-type mismatch of two
  similar types, where one would want implicit conversion (ie. int to
  float).  This has the potential to provide great performance gains in
  these cases, as compared to the current system which converts to a string
  and then into the detsination type.

Second, few of the data types are implemented.  Of these, the most
  important are lists.  Some preliminary tests indicate possible gains of
  1-2 orders of magnitude over the existing system of storing lists as
  strings.

Lastly, we propose make the replacement callback style (structure pointers
  instead of string pointers) become the standard for Tcl for some future
  version.  In this system, callbacks which want strings would need to ask
  for them as a real data type.  This has the potential to channel the
  performance improvements back to users employing the command line, since
  such a system would not need to rely on the compiler.

We would like to thank the following people for their advice, contributions
  and other assistance: John Ousterhout, Sue Graham, Raph Levien, Brian
  Dennis, and the members of the Tcl/Tk Users Group.  Ashok Singhal, Colas
  Nahaboo, and Wayne Throop provided a multi-language test suite.

%\section{Bibliography}
\bibliography{tclhack}
\end{document}

%%z%%%%From: throopw%sheol@concert.net
%%z%%%%Newsgroups: comp.lang.tcl
%%z%%%%Subject: Re: How fast is TCL?
%%z%%%%Date: 4 Mar 93 20:50:21 GMT
%%z%%%%
%%z%%%%
%%z%%%%: From: nick@west.msi.com (Nick Erndt)
%%z%%%%: Message-ID: <1993Mar3.235757.387@msi.com>
%%z%%%%: How does TCL compare to other string parsing languages?
%%z%%%%: Perl?  LISP?  sh?  csh?  Dylan?
%%z%%%%
%%z%%%%
%%z%%%%Faster than you might expect, given that it stores procedure bodies as
%%z%%%%strings.  But against languages that pre-parse, not very fast.  Here
%%z%%%%are timings for a benchmark for a few interpretive string bashing
%%z%%%%languages I have lying around:
%%z%%%%
%%z%%%%
%%z%%%%    tcl   14.6u 0.5s 0:18 83% 386+376k
%%z%%%%    perl   6.9u 2.3s 0:12 74% 894+4257k
%%z%%%%    nawk   1.9u 0.2s 0:03 66% 150+176k
%%z%%%%    oosp   1.3u 0.3s 0:02 61% 172+160k
%%z%%%%
%%z%%%%
%%z%%%%As compared to .027 seconds or so for compiled C code.
%%z%%%%
%%z%%%%
%%z%%%%Note that the benchmark (code for which given below) does NOT really
%%z%%%%measure string-bashing performance, but really basic recursive
%%z%%%%call/return overhead.  For example, if more string-bashing and/or
%%z%%%%iterative tasks were measured, perl would improve its standing because
%%z%%%%so many of them are builtins in perl (and because it's better at
%%z%%%%iteration than recursion).  Also, I have found that many of these
%%z%%%%interpreters are very sensitive to exactly how the test is expressed,
%%z%%%%so if I've pessimistically coded the tcl example, people should point this out.
%%z%%%%
%%z%%%%Tcl is not the slowest, by the way.  The article from which I drew the
%%z%%%%benchmark gave ksh timings measured in hours, as I recall.  I can
%%z%%%%retrieve the original article (which was concerned with the performance
%%z%%%%of object-oriented method-lookup as opposed to simple function
%%z%%%%invocation) if there is interest.  It had timings for many more
%%z%%%%interpretive languages, including elisp, elk, siod, REXX (I think),
%%z%%%%the ksh as mentioned, and so on.  It didn't have Dylan though.
%%z%%%%
%%z%%%%I have some thoughts on how to speed tcl up by (optimistically)
%%z%%%%about five times.  I've been attempting to write a proof-of-concept
%%z%%%%core interpreter to measure the kinds of speedup that might be
%%z%%%%expected, but my time to devote to the project is prohibitively small.
%%z%%%%
%%z%%%%--
%%z%%%%
%%z%%%%    The times given above were a result of csh "time fib.$interp 20"
%%z%%%%    commands, executed against the scripts below.
%%z%%%%
%%z%%%%    #!/usr/bin/env tcl-f
%%z%%%%    proc fib {n} {
%%z%%%%	if {$n<2} {
%%z%%%%	    return $n
%%z%%%%	} {
%%z%%%%	    expr [fib [expr $n-1]]+[fib [expr $n-2]]
%%z%%%%	}
%%z%%%%    }
%%z%%%%    puts stdout [fib [lindex $argv 0]]
%%z%%%%
%%z%%%%    #!/usr/bin/env perl
%%z%%%%    sub fib {
%%z%%%%	local($n) = @_;
%%z%%%%	if ($n < 2) { $n } else { &fib($n-1) + &fib($n-2); }
%%z%%%%    }
%%z%%%%    print &fib(@ARGV[0]), "\n";
%%z%%%%
%%z%%%%    #!/usr/bin/env nawk-f
%%z%%%%    function fib(n) {
%%z%%%%	if (n<2) {
%%z%%%%	    return n;
%%z%%%%	} {
%%z%%%%	    return fib(n-1)+fib(n-2);
%%z%%%%	}
%%z%%%%    }
%%z%%%%    BEGIN {print fib(ARGV[1]); exit}
%%z%%%%
%%z%%%%    #!/usr/bin/env oosp-r
%%z%%%%    void declare'fib '1
%%z%%%%    void define'fib with'n arg'1
%%z%%%%	if int< val'n '2
%%z%%%%	    val'n
%%z%%%%	    + fib - val'n '1 fib - val'n '2
%%z%%%%    fib val'$1 line
%%z%%%%
%%z%%%%--
%%z%%%%
%%z%%%%    #include <stdio.h>
%%z%%%%    int fib(int n) {
%%z%%%%	if (n < 2)
%%z%%%%	    return n;
%%z%%%%	else
%%z%%%%	    return fib(n-1) + fib(n-2);
%%z%%%%    }
%%z%%%%    int main(int n, char**a) { printf("%d\n", fib(atoi(a[1])) ); }
%%z%%%%
%%z%%%%--
%%z%%%%Wayne Throop   throopw%sheol@concert.net
%%z%%%%	       throop%aurgate@concert.net
%%z%%%%
%%z%%%%
%%z%%%%From: colas@opossum.inria.fr (Colas Nahaboo)
%%z%%%%Newsgroups: comp.lang.tcl
%%z%%%%Subject: Re: How fast is TCL?
%%z%%%%Date: 9 Mar 93 09:26:55 GMT
%%z%%%%Organization: Koala Project, Bull Research France
%%z%%%%
%%z%%%%In article <1993Mar3.235757.387@msi.com>, nick@west.msi.com (Nick Erndt)
%%z%%%%writes:
%%z%%%%> How does TCL compare to other string parsing languages?
%%z%%%%
%%z%%%%I applied the fibonnacci tests to some interpreted languages, here is what I
%%z%%%%got:
%%z%%%%Notes:
%%z%%%%[1] see that result depend on the processor. Simpler systems work better on
%%z%%%%    RISCs than CISCs
%%z%%%%[2] it is possible to link TK to another language, bypassing TCL totally
%%z%%%%    we have done it with wool, if what you want is Tk but are ready to trade
%%z%%%%    TCL for a faster or prefered language
%%z%%%%[3] wool source is alas not yet freely available. Binary is available, we
%%z%%%%    provide a Tk/wool wish binary. For now you will have to sign some
%%z%%%%    non-disclosure to get wool sources. contact me for details.
%%z%%%%[4] TCL is slow, but not as slow as you may have thought, and it is not
%%z%%%%    necessary for a glue language to be fast, other qualities are more
%%z%%%%    important (ease of integration, ease of use, debugging)
%%z%%%%
%%z%%%%
%%z%%%%-------------------------------------------------------------------------------
%%z%%%%
%%z%%%%
%%z%%%%
%%z%%%%	The small interpreters naive benchmark: Fibo Festival!
%%z%%%%
%%z%%%%	======================================================
%%z%%%%
%%z%%%%
%%z%%%%
%%z%%%%		Sony News, 68030 25Mhz   SparcStation2
%%z%%%%		(compiled with gcc -O).  (comp. with cc -O)
%%z%%%%
%%z%%%%
%%z%%%%		(fib 20)(fibobj (fibobj  (fib 20)(fibobj (fibobj
%%z%%%%			 15)     20)              15)     20)
%%z%%%%
%%z%%%%
%%z%%%%C                0.07s                  0.014s
%%z%%%%wool 2.1p        3.82s  1.71s   19s     2.44s   0.95s   10.56s
%%z%%%%xscheme 0.22 [1] 4s     3s      30s     2s      2s      13s
%%z%%%%lucid CL [*]                            3.60s
%%z%%%%siod 2.4 [4]     6.07s                  1.13s
%%z%%%%fools 1.3.2      9s
%%z%%%%elk 1.5 [3]     10s     87s             5s
%%z%%%%emacs-lisp [5]  11s                     4s
%%z%%%%franz lisp [*]  14s
%%z%%%%xlisp 2.1d      16.83s  21.13s 235s     6.08s   8.47s   94.50s
%%z%%%%perl 4.019 [6]  20.52s                  7.35s
%%z%%%%tcl 6.2         34.5s                   21s
%%z%%%%lelisp v16.01 [*]                       24s
%%z%%%%Iconiconde                              53s
%%z%%%%ksh           9m24s
%%z%%%%
%%z%%%%		i386 33Mhz running SCO
%%z%%%%		(compiled with gcc -O).
%%z%%%%
%%z%%%%		(fib 20)        (fibobj 15)     (fibobj 20)
%%z%%%%
%%z%%%%wool 2.1t       3.21s           1.33s           14.75s
%%z%%%%xscheme 0.22    3.43s           2.63s           26.95s
%%z%%%%emacs-lisp byte-compiled 6s
%%z%%%%emacs-lisp      9s
%%z%%%%xlisp 2.1d      9.58s           13.52s          150s
%%z%%%%
%%z%%%%
%%z%%%%NOTES:
%%z%%%%[*] Commercial full-scale traditional lisp systems (may have assembly code)
%%z%%%%    in interpreted mode
%%z%%%%[1] XScheme is byte-coded, this explains its efficiency
%%z%%%%    to have a better comparison with wool, (fib 25) on a sony is done in
%%z%%%%    44.62s in wool, and in 46s in xscheme and in 27.50s and 19s on a
%%z%%%%    sparcstation2
%%z%%%%[3] version with stack handler in 68000 assembly code (faster)
%%z%%%%[4] with the mark&sweep gc (faster than stop&copy)
%%z%%%%    (cfib 20) on sony: 0.90s
%%z%%%%[5] 9s if byte-compiled on sony, but still 4s compiled on sparc2
%%z%%%%[6] fib0 is fastest on sony and sun4
%%z%%%%
%%z%%%%These are NAIVE tests, to give just a rough indication of a the speed
%%z%%%%of a language. Times are best of at least 5 runs on an otherwise idle
%%z%%%%machine.
%%z%%%%Times given with hundredth of seconds are timed by system primitives,
%%z%%%%otherwise (seconds only) by a hand-held stopwatch.
%%z%%%%
%%z%%%%The goal of these tests is to test the object layer of the small
%%z%%%%interpreters,
%%z%%%%as this is not often tested speed-wise. It is also the most difficult to
%%z%%%%test,
%%z%%%%since they all have a different programming model!
%%z%%%%
%%z%%%%Note the interesting differences between a CISC CPU (sony) and a RISC one
%%z%%%%(sparc), some languages are speeded more than 5 times, other only 50% more!
%%z%%%%
%%z%%%%Please add to this list:
%%z%%%% - new languages (Implementations of fib & fibobj in a straightforward way)
%%z%%%% - new timings on other machines
%%z%%%% - timing primitives in languages that I didn't find
%%z%%%% - better implementations of benchmarks, making use of language knowledge to
%%z%%%%   optimize it
%%z%%%%
%%z%%%%Please send all remarks and additions to:
%%z%%%%
%%z%%%%Colas Nahaboo, colas@sa.inria.fr, Bull Research, Koala Project, GWM X11 WM
%%z%%%%Pho:(33) 93.65.77.70(.66 Fax), INRIA, B.P.93 - 06902 Sophia Antipolis,
%%z%%%%FRANCE.
%%z%%%%
%%z%%%%/*****************************************************************************\
%%z%%%%*                            Fibonnacci code
%%z%%%%used                             *
%%z%%%%\*****************************************************************************/
%%z%%%%
%%z%%%%/************************************************************** COMMON LISP
%%z%%%%*/
%%z%%%%; generic common lisp code (wool, Common Lisps, xlisp...) and emacs lisp
%%z%%%%
%%z%%%%(defun fib (n)
%%z%%%%  (if (< n 2) n
%%z%%%%    (+ (fib (- n 1)) (fib (- n 2)))))
%%z%%%%
%%z%%%%/******************************************************************** SCHEME
%%z%%%%*/
%%z%%%%; generic scheme code (elk, fools, siod, xscheme...)
%%z%%%%; code provided in elk distribution
%%z%%%%
%%z%%%%(define (fib  n)
%%z%%%%  (if (< n 2) n
%%z%%%%    (+ (fib (- n 1)) (fib (- n 2)))
%%z%%%%))
%%z%%%%
%%z%%%%/*********************************************************************** TCL
%%z%%%%*/
%%z%%%%# may be not optimal!
%%z%%%%proc fib {n} {
%%z%%%%  if {$n < 2} then {return $n} else {
%%z%%%%  return [expr {[fib [expr {$n - 1}]] + [fib [expr {$n - 2}]]}]}
%%z%%%%}
%%z%%%%
%%z%%%%proc fib n {if {$n<2} {return $n} {return [expr [fib [incr n -1]]+[fib [incr n -1]]]}}
%%z%%%%
%%z%%%%/*********************************************************************** ksh
%%z%%%%*/
%%z%%%%# totally unreasonable, just for fun...
%%z%%%%fib(){
%%z%%%% if let "$1<2"
%%z%%%% then echo $1
%%z%%%% else
%%z%%%%     let N1=$1-1
%%z%%%%     let N2=$1-2
%%z%%%%     let "N=`fib $N1`+`fib $N2`"
%%z%%%%     echo $N
%%z%%%% fi
%%z%%%%}
%%z%%%%
%%z%%%%/********************************************************************** perl
%%z%%%%*/
%%z%%%%
%%z%%%%# perl code, contributed by Kresten Krab Thorup <krab@iesd.auc.dk>
%%z%%%%# and J.T.Conklin@Gain.COM (J.T. Conklin)
%%z%%%%
%%z%%%%sub fib0 {
%%z%%%%	local($n)=@_;
%%z%%%%	($n < 2
%%z%%%%	   ? $n
%%z%%%%	   : &fib($n-1)+&fib($n-2));
%%z%%%%}
%%z%%%%
%%z%%%%sub fib1 {
%%z%%%%	local($n)=@_;
%%z%%%%	if($n < 2) {
%%z%%%%	   return $n;
%%z%%%%	} else {
%%z%%%%	   return (&fib1($n-1)+&fib1($n-2));
%%z%%%%	}
%%z%%%%}
%%z%%%%
%%z%%%%
%%z%%%%sub fib2 {
%%z%%%%	local($n)=@_;
%%z%%%%	($n-- < 2
%%z%%%%	   ? ++$n
%%z%%%%	   : &fib2($n--)+&fib2($n));
%%z%%%%}
%%z%%%%
%%z%%%%$start = (times)[0];
%%z%%%%&fib0(20);
%%z%%%%$end = (times)[0];
%%z%%%%printf "fib0(20) took %.2f CPU seconds\n", $end - $start;
%%z%%%%
%%z%%%%$start = (times)[0];
%%z%%%%&fib1(20);
%%z%%%%$end = (times)[0];
%%z%%%%printf "fib1(20) took %.2f CPU seconds\n", $end - $start;
%%z%%%%
%%z%%%%$start = (times)[0];
%%z%%%%&fib2(20);
%%z%%%%$end = (times)[0];
%%z%%%%printf "fib2(20) took %.2f CPU seconds\n", $end - $start;
%%z%%%%
%%z%%%%
%%z%%%%/************************************************************************* C
%%z%%%%*/
%%z%%%%
%%z%%%%/* timing functions are BSD */
%%z%%%%#include <stdio.h>
%%z%%%%#include <sys/types.h>
%%z%%%%#include <sys/times.h>
%%z%%%%#include <sys/timeb.h>
%%z%%%%#include <sys/time.h>
%%z%%%%#include <sys/resource.h>
%%z%%%%
%%z%%%%main(argc, argv)
%%z%%%%    int argc;
%%z%%%%    char **argv;
%%z%%%%{
%%z%%%%    int n = 20;
%%z%%%%    int milliseconds;
%%z%%%%    int result;
%%z%%%%
%%z%%%%    if (argc > 1) {
%%z%%%%	n = atoi(argv[1]);
%%z%%%%    }
%%z%%%%    milliseconds = current_time();
%%z%%%%    result = fib(n);
%%z%%%%    milliseconds = current_time() - milliseconds;
%%z%%%%    printf("fib(%d) = %d in %d milliseconds\n", n, result, milliseconds);
%%z%%%%}
%%z%%%%
%%z%%%%int current_time()
%%z%%%%{
%%z%%%%    struct timeb time_bsd;
%%z%%%%
%%z%%%%    ftime(&time_bsd);
%%z%%%%    return 1000 * time_bsd.time + time_bsd.millitm;
%%z%%%%}
%%z%%%%
%%z%%%%int fib(n)
%%z%%%%    int n;
%%z%%%%{
%%z%%%%    if (n < 2)
%%z%%%%	return n;
%%z%%%%    else
%%z%%%%	return fib(n-1) + fib(n-2);
%%z%%%%}
%%z%%%%
%%z%%%%
%%z%%%%/*****************************************************************************\
%%z%%%%*                              Fib-object
%%z%%%%code                                *
%%z%%%%\*****************************************************************************/
%%z%%%%
%%z%%%%/********************************************************************** WOOL
%%z%%%%*/
%%z%%%%
%%z%%%%
%%z%%%%(defclass Num () ((n :initform 0 :accessor Num.n)))
%%z%%%%
%%z%%%%(setq Num1 (make-instance Num 'n 1))
%%z%%%%(setq Num2 (make-instance Num 'n 2))
%%z%%%%
%%z%%%%(defmethod add ((n1 Num) n2)
%%z%%%%  (make-instance Num 'n (+ (get n1 'n) (get n2 'n)))
%%z%%%%)
%%z%%%%(defmethod minus ((n1 Num) n2)
%%z%%%%  (make-instance Num 'n (- (get n1 'n) (get n2 'n)))
%%z%%%%)
%%z%%%%(defmethod less ((n1 Num) n2)
%%z%%%%  (< (get n1 'n) (get n2 'n))
%%z%%%%)
%%z%%%%
%%z%%%%(defun fibobj (n)
%%z%%%%  (setq t0 (get-internal-run-time))
%%z%%%%  (setq fibobj:result (dofibobj (make-instance Num 'n n)))
%%z%%%%  (? (- (get-internal-run-time) t0) "ms\n")
%%z%%%%  fibobj:result
%%z%%%%)
%%z%%%%
%%z%%%%(defun dofibobj (n)
%%z%%%%  (if (less n Num2) n
%%z%%%%    (add (dofibobj (minus n Num1)) (dofibobj (minus n Num2)))
%%z%%%%  )
%%z%%%%)
%%z%%%%
%%z%%%%/********************************************************************* XLISP
%%z%%%%*/
%%z%%%%
%%z%%%%(load "init.lsp")
%%z%%%%(load "classes.lsp")
%%z%%%%
%%z%%%%(defclass Num ((n 0)))
%%z%%%%
%%z%%%%(setq Num1 (send Num :new :n  1))
%%z%%%%(setq Num2 (send Num :new :n  2))
%%z%%%%
%%z%%%%(defmethod Num :add (n2)
%%z%%%%  (send Num :new :n (+ n (send n2 :n)))
%%z%%%%)
%%z%%%%(defmethod Num :minus (n2)
%%z%%%%  (send Num :new :n (- n (send n2 :n)))
%%z%%%%)
%%z%%%%(defmethod Num :less (n2)
%%z%%%%  (< n (send n2 :n))
%%z%%%%)
%%z%%%%
%%z%%%%(defun fibobj (n)
%%z%%%%  (setq fibobj:result (time (dofibobj (send Num :new :n n))))
%%z%%%%  (send fibobj:result :n)
%%z%%%%)
%%z%%%%
%%z%%%%(defun dofibobj (n)
%%z%%%%  (if (send n :less Num2) n
%%z%%%%    (send (dofibobj (send n :minus Num1))
%%z%%%%    :add (dofibobj (send n :minus Num2)))))
%%z%%%%
%%z%%%%/*********************************************************************** elk
%%z%%%%*/
%%z%%%%
%%z%%%%(require 'oops)
%%z%%%%
%%z%%%%(define-class Num (instance-vars (n 0)))
%%z%%%%
%%z%%%%(define Num1 (make-instance Num (n 1)))
%%z%%%%(define Num2 (make-instance Num (n 2)))
%%z%%%%
%%z%%%%(define-method Num (add n2)
%%z%%%%  (make-instance Num (n (+ n (with-instance n2 n)))))
%%z%%%%
%%z%%%%(define-method Num (minus n2)
%%z%%%%  (make-instance Num (n (- n (with-instance n2 n)))))
%%z%%%%
%%z%%%%(define-method Num (less n2)
%%z%%%%  (< n (with-instance n2 n)))
%%z%%%%
%%z%%%%(define (fibobj N)
%%z%%%%  (with-instance (dofibobj (make-instance Num (n N))) n)
%%z%%%%)
%%z%%%%
%%z%%%%(define (dofibobj n)
%%z%%%%  (if (send n 'less Num2) n
%%z%%%%    (send (dofibobj (send n 'minus Num1))
%%z%%%%    'add (dofibobj (send n 'minus Num2)))
%%z%%%%))
%%z%%%%
%%z%%%%/******************************************************************* XScheme
%%z%%%%*/
%%z%%%%
%%z%%%%;; fibobj
%%z%%%%;; coded from what I could guess from the docs (colas)
%%z%%%%
%%z%%%%(set! Num (class 'new '(n)))
%%z%%%%
%%z%%%%(Num 'answer 'set '(x) '((set! n x) self))
%%z%%%%(Num 'answer 'get '() '(n))
%%z%%%%
%%z%%%%(Num 'answer 'add '(n2) '(
%%z%%%%    ((num 'new) 'set (+ n (n2 'get)))))
%%z%%%%
%%z%%%%(Num 'answer 'minus '(n2) '(
%%z%%%%    ((num 'new) 'set (- n (n2 'get)))))
%%z%%%%
%%z%%%%(Num 'answer 'less '(n2) '(
%%z%%%%    (< n (n2 'get))))
%%z%%%%
%%z%%%%((set! num1 (num 'new)) 'set 1)
%%z%%%%((set! num2 (num 'new)) 'set 2)
%%z%%%%
%%z%%%%(define (fibobj x)
%%z%%%%    (system "date")
%%z%%%%    (set! res ((dofibobj ((num 'new) 'set x)) 'get))
%%z%%%%    (system "date")
%%z%%%%    res
%%z%%%%)
%%z%%%%
%%z%%%%(define (dofibobj x)
%%z%%%%  (if (x 'less num2) x
%%z%%%%      ((dofibobj (x 'minus num1)) 'add (dofibobj (x 'minus num2)))))
%%z%%%%
%%z%%%%--
%%z%%%%Colas Nahaboo, Koala (Bull Research). Full sig. by: finger
%%z%%%%colas@koala.inria.fr
%%z%%%%
%%z%%%%
%%z%%%%From: ashoks@duckjibe.Eng.Sun.COM (Ashok Singhal)
%%z%%%%Newsgroups: comp.lang.tcl
%%z%%%%Subject: TCL is "fast enough": a practical example
%%z%%%%Date: 10 Mar 1993 23:43:50 GMT
%%z%%%%Organization: Sun Microsystems, Inc.
%%z%%%%Distribution: world
%%z%%%%Reply-To: ashoks@duckjibe.Eng.Sun.COM
%%z%%%%NNTP-Posting-Host: duckjibe
%%z%%%%
%%z%%%%Arguing about TCL's speed tends to lead nowhere because it's hard to come up
%%z%%%%with a
%%z%%%%reasonable metric (and it's an absolutely herculean feat to get everyone on
%%z%%%%the
%%z%%%%net to agree! Never been done :-)
%%z%%%%
%%z%%%%But here is an example where I thought TCL's speed would be an issue but
%%z%%%%it turned out to be fast enough.
%%z%%%%
%%z%%%%A machine that I helped build at Sun (SPARCcenter2000) has a number of
%%z%%%%programmable
%%z%%%%hardware performance counters.  I wrote a XView program to take samples of
%%z%%%%these
%%z%%%%counters, compute various interesting results from the raw samples as well
%%z%%%%as
%%z%%%%from various software performance measures, display the results in
%%z%%%%stripcharts,
%%z%%%%log the results, etc.  I decided to include an embedded interpreter in the
%%z%%%% program for the following reasons:
%%z%%%%
%%z%%%%1. There are several configurations, and a fully configured system has a
%%z%%%%large number of counters and each of the counters can be programmed
%%z%%%%to count different things.  When I started I had no idea what would be the
%%z%%%%set of "interesting" things to compute from large number of combinations of
%%z%%%%these counters.  Rather than "hard-code" them in C, I thought it better to
%%z%%%%use an embedded interpreter to do the computations; that way one could add a
%%z%%%%new computation without recompiling.
%%z%%%%
%%z%%%%2.  I wanted the capability of scripting (program the tool to start
%%z%%%%sampling,
%%z%%%%start off one benchmark, log result, then change something else, restart
%%z%%%%the benchmark and so on...).
%%z%%%%
%%z%%%%3. This was not my main job and I'm not a software weenie.  So I thought I
%%z%%%%could get this tool done quickly using an interpreter.  I chose TCL because
%%z%%%%it was simple, well written, well documented and I COULD UNDERSTAND THE
%%z%%%%CODE!
%%z%%%%Well, most of it anyway...
%%z%%%%(Like I said, I'm no software weenie and my eyes glaze over when I encounter
%%z%%%%makefiles that make makefiles that make makefiles that compile programs).
%%z%%%%
%%z%%%%I wrote simple primitives to interface with the device driver for the
%%z%%%%counters (ioctls to program the counters, reads) and the XView widgets
%%z%%%%that comprised the GUI (insert into scrolling list, get selection from
%%z%%%%srolling list, insert into stripchart display list, etc).
%%z%%%%[I did not use Tk because at the time it was not quite stable enough for
%%z%%%%me].
%%z%%%%
%%z%%%%I defined a few TCL commands to access those primitives and everything else
%%z%%%%was written with TCL scripts.  I was concerned that since TCL was
%%z%%%%interpreted
%%z%%%%it would incur substantial overhead and the performance monitor would be too
%%z%%%%intrusive (i.e. it would perturb the measured program/hardware too much).
%%z%%%%I resolved to press on anyway.  I was not overly conscious of efficiency
%%z%%%%and decided to profile the code when it was done and to move the frequently
%%z%%%%used TCL code to C.
%%z%%%%
%%z%%%%Turns out I never had to do anything of the sort.  Running SPEC benchmarks,
%%z%%%%for
%%z%%%%example, on a uniprocessor I noticed about a couple of percent drop in
%%z%%%%performance due to simultaneously running the performance monitor and
%%z%%%%measuring a
%%z%%%%fair amount of "stuff".  On an otherwise idle system I see only a minor
%%z%%%%impact on things like cache miss rates, bus utilization etc.  I'm sure I
%%z%%%%could
%%z%%%%improve on performance, but right now I see no reason to and I've got better
%%z%%%%things to do.
%%z%%%%
%%z%%%%TCL's performance is just fine, thank you. This was quite a pleasant
%%z%%%%surprise.
%%z%%%%
%%z%%%%- Ashok Singhal
%%z%%%%
%%z%%%%
%%z%%%%
%%z%%%%
%%z%%%%
%%z%%%%Future Work
%%z%%%%Bibliography
%%z%%%%ls.
%%z%%%%
%%z%%%%
%%z%\bibliography{report}
%%z%\end{document}
%%z%
%%z%
%%z%The compilation of Tcl is most similar to the byte-compilation of Emacs
%%z%  Lisp code\cite{elisp}.  While hardly a necessity for emacs users, it is
%%z%  strictly advantageous to leave the portable compiled files in a shared
%%z%  directory, since they are automatically detected and used, completely
%%z%  portable, always execute faster, and are essentially hassle-free.  For
%%z%  some large applications, like the `gnus' USENET news reader, it becomes
%%z%  invaluable.
%%z%
%%z%One side effect of compilation is that is removes comments, keywords and
%%z%  names from the code.  In addition to overall speed improvement, this also
%%z%  removes the performance penalty script-writers currently pay for use of
%%z%  long identifiers and hides the script from the end user, which is
%%z%  important in commercial applications.
%%z%
%%z%
%%z%\subsubsection{The Runtime System}
%%z%
%%z%The runtime system loads the compiled files that the front-end has output
%%z%(these are in ``tc file format'').  This file consists of a dictionary
%%z%(which will be described in detail later in this paper) and a list
%%z%of commands, each of which is represented as a collection of references
%%z%into the dictionary.
%%z%
%%z%Once the dictionary has been read, commands are loaded and evaluated one by
%%z%one.  This evaluation is performed by a routine called Tc\_Eval(), which
%%z%is a sister routine to the standard Tcl\_Eval(); the difference is that
%%z%Tc\_Eval() deals with compiled data structures.
%%z%
%%z%When a compiled program is running, Tc\_Eval() will try to represent as
%%z%many values as possible in compiled form (rather than their native
%%z%Tcl string representations).  It must deal with both representations,
%%z%however; compiled data must coexist with string representations, since
%%z%the application (in which the Tcl interpreter has been embedded) could
%%z%perform arbitrary Tcl evaluations at any time, and these require 
%%z%traditional Tcl data representation.
%%z%
%%z%The runtime system also must perform type coercion.  In traditional
%%z%Tcl, since all data are strings, there can be no type conflicts;
%%z%a singleton list containing the string `2' can be treated as the
%%z%number `2' because they both look the same.  (Obviously, in plain
%%z%Tcl there is no such thing as a `list' type; lists are represented
%%z%as strings which follow some simple formatting conventions.)  In
%%z%the Tc runtime system, however, numbers and lists are represented
%%z%differently in memory, so we cannot merely interchange them.
%%z%
%%z%To deal with these intricacies, the runtime system has the capability to
%%z%  coerce a value from any type to any other.  This is detailed in the
%%z%  Implementation section below.
%%z%
%%z%\section{Implementation}
%%z%\subsection{Compiler (Front-End)}
%%z%
%%z%\subsubsection{Adding Named Procedures}
%%z%
%%z%In the previous discussion of the configuration script, no description was
%%z%  given as to how C procedures were actually assigned names for the Tcl
%%z%  script.  This is achieved through a standard Tcl mechanism whereby
%%z%  strings can be hashed into records, each holding an arbitrary data
%%z%  pointer.  In our case, this pointer refers to a C function.
%%z%
%%z%\subsubsection{Portability}
%%z%
%%z%Like byte-compiled elisp, our binaries are portable among architectures,
%%z%  regardless of endian-ness or word length.  The way this is achieved is by
%%z%  saving references\footnote{by ``references'', we really meant memory
%%z%  offsets (as opposed to memory addresses), and so this implementation will
%%z%  work on both 32- and 64- bit architectures.} to disk as four unsigned
%%z%  characters, in MSB to LSB order.  The backend pays a small penalty for
%%z%  this by having to reconstruct the number.
%%z%
%%z%The advantage is that binaries may be left on file server machines along
%%z%  with the source, and all users of this shared resource can take advantage
%%z%  of compilation.
%%z%
%%z%\subsubsection{Output Format}
%%z%
%%z%The output of compilation is a dictionary and a command list specifying the
%%z%  commands present in the top level script.  The dictionary entries are an
%%z%  array of preparsed strings.  A commands list follows, which contains
%%z%  references into the dictionary for each argument.
%%z%
%%z%The details of the compiler output are beyond the scope of this paper.
%%z%  However, a simple example will help illustrate the work that is done by
%%z%  the overall system, because the runtime data structures closely match the
%%z%  format of the compiled file.
%%z%
%%z%\subsection{Runtime Interpreter (Back-End)}
%%z%\subsubsection{The Loading Process}
%%z%
%%z%The loading process is expedited by a fast memory-allocation scheme: header
%%z%  information in the .tc file tells the loader how much memory it will
%%z%  need; this is allocated with a single malloc() before loading the
%%z%  dictionary.  Storage allocation for dictionary elements within this block
%%z%  is managed by a simple pointer-increment scheme.
%%z%
%%z%Commands are executed as they are loaded from the file; they are then
%%z%  discarded to make room for the next command \footnote{Commands like
%%z%  `proc' create data structures that are persistent and hold other
%%z%  commands, but once this is done the `proc' command itself is thrown
%%z%  away.}.  Commands are represented as arrays of references into the
%%z%  dictionary.  Items in the dictionary are considered permanent and
%%z%  are never deallocated.
%%z%
%%z%\subsubsection{Execution}
%%z%Tc\_Eval performs evaluation of all compiled commands.  Note the
%%z%following Tcl code fragment:
%%z%
%%z%\begin{verbatim}
%%z%  set i 0
%%z%  while {$i<100} {
%%z%      cback $i
%%z%      incr i
%%z%  }
%%z%\end{verbatim}
%%z%
%%z%In this example, Tc\_Eval is first called with the `set' command as an
%%z%  argument.  The compiled version of `set' takes a variable as first
%%z%  argument and any type as second; the ``0'' will have been parsed as
%%z%  a string by the compiler. There are no type conflicts here, so the
%%z%  arguments will be passed to `set' as is.  The overall result is that
%%z%  the string ``0'' will be stored into variable `i'.
%%z%
%%z%Tc\_Eval() will then be called with the `while' loop as an argument.  The
%%z%  compiled version of `while' takes a boolean expression and a command list
%%z%  as arguments; the two arguments are of the proper types, so they are
%%z%  passed to `while' as is.  The while command will then begin looping,
%%z%  evaluating the boolean expression at the start of each cycle to decide
%%z%  when to stop.  When the boolean is evaluated, there will be an attempted
%%z%  comparison between `\$i' and the number 100.  The value in i is not an
%%z%  integer, however; it is a string.  When the value is fetched, it will be
%%z%  coverted on demand into an integer by passing the value through integer's
%%z%  parseproc. The integer result will be cached in the variable record for
%%z%  i.  The boolean expression evaluation proceeds and returns true.
%%z%
%%z%Since we now have an integer value for i, each subsequent reference
%%z%  to it is already dealing with a number, and so proceeds quickly.
%%z%
%%z%If a type coercion ever fails, the compiled command cannot be called,
%%z%  since we cannot pass it the data representation it wants.  In this
%%z%  case, Tc\_Eval will coerce all arguments into string form and fall
%%z%  back to the standard (slow) Tcl evaluation mechanism.
%%z%
%%z%\subsubsection{Support for Dynamic Configuration}
%%z%
%%z%To manage installation of new builtins and types, the runtime system
%%z%  contains a type registry which associates names with function pointers,
%%z%  like the one in the front end.
%%z%
%%z%To add runtime support for a new builtin, one must create and register an
%%z%  execproc that performs evaluation for that command.  A loadproc for a
%%z%  command may also be specified, but is optional; if omitted, a default
%%z%  will be used.  The names of these builtins are matched at load time, when
%%z%  they are read from the .tc file.
%%z%
%%z%To install a new type into the backend, one must write a printproc, a
%%z%  loadproc, and a parseproc.  None of these are optional since there
%%z%  is no sensible default to fall back to; the operations of each of these
%%z%  procedures is highly dependent on the internal representation chosen.
%%z%
%%z%\subsubsection{Modification of the standard Tcl library}
%%z%
%%z%Some changes were made to the standard Tcl library to support coexistence
%%z%  of standard Tcl (exemplified by Tcl\_Eval()) and commpiled Tcl (exemplified
%%z%  by Tc\_Eval()).
%%z%
%%z%When retrieval of a variable's string value is re\-quested, a hook in
%%z%  Tcl\_GetVar() checks to see if a compiled value for that variable exists
%%z%  and shadows the string value.  If so, the value's printproc is called and
%%z%  the result is stored in the variable record.  We do this string
%%z%  translation at string-request-time rather than when a compiled value is
%%z%  stored in a variable, since it is faster (we may store several compiled
%%z%  values into a variable before a request for its string value is made.)
%%z%
%%z%Routines for invalidating compiled values upon storage of a string
%%z%  were added to Tcl\_SetVar().  Also, a hook is required in Tcl\_SetVar(),
%%z%  since it may reallocate a variable record, moving its location in memory;
%%z%  when this happens, Tcl\_SetVar() calls a routine that updates the pointer
%%z%  in the string table.
%%z%
%%z%No changes are required when variables are unset; an existing flag
%%z%  in the plain Tcl variable record, VAR\_UNDEFINED, is used instead.
%%z%
%%z%Similar backpatching is done for commands, when they are rebound or
%%z%  renamed.  In addition, a flag was added to a `proc' record to tell
%%z%  whether the code it contains is in plain Tcl or tc format; if a
%%z%  proc is in tc format, Tcl\_Eval() will call Tc\_Eval() to evaluate that
%%z%  proc.
%%z%
%%z%\section{Results}
%%z%
%%z%The following time measurements were taken using the Tcl 'time' command;
%%z%  'time' repeats an evaluation (given as its first argument) for a number
%%z%  of times given as its second argument, and returns the average time spent
%%z%  (total time divided by the number of iterations).  We used a compiled
%%z%  version of the `time' command to take the measurements; it is equivalent
%%z%  in all respects to the original.
%%z%
%%z%At this point, `fast' versions of many of the Tcl core commands have not
%%z%  yet been implemented.  The tests below use some of the implemented
%%z%  commands.  They are in no way intended to be complete; they are merely
%%z%  included to give a rough idea of the compiler's performance.  Detailed
%%z%  benchmarks will be published for the Tcl conference this summer.
%%z%
