Converting Yacas script code to other languages
Introduction
This section describes an implementation of a minimal environment
in Common Lisp that allows execution of code originally written
in Yacas script code.
Small Lisp interpreters can easily be written in any language.
Being able to directly compile the interpreter into a program
from for instance Common Lisp or Java allows the freedom to first
print the code for the reference Yacas interpreter implementation,
and then use it in other projects later on.
The main aim for Yacas is to allow for mathematically-oriented
algorithms to be written easily. Being able to compile that
code to code that can be compiled into other syntax gives
flexibility. This effort thus also defines tha absolute bare
minimum required for such a system.
Common Lisp was chosen because it is sufficiently close to Yacas,
Yacas resembling a Lisp interpreter internally. Yacas already
comes with a parser for Yacas script code, and can easily
manipulate expressions to bring them into a form suitable for
execution in another environment.
Not all of Yacas will be made available, just the functional
subset needed for doing CAS. Other systems have their own
functionality for interacting with the system (file input/output
and such).
Relevant parts of the system
The minimum set up consists of:
- A parser. Although not highly necessary, the author feels
the Yacas syntax is a comfortable one. One reference implementation
can be written in the mini sub-set of Lisp that will be used.
- A compiler for converting from Yacas script to Common Lisp
evaluable expressions and functions.
- Various small utility functions written in a small sub-set
of Lisp, to offer functionality required for executing Yacas script
at run time. Pattern matching functionality for instance can be implemented
easily in Lisp code itself.
- if necessary, a custom eval operation to alter the default
evaluation behaviour. For instance, in Common Lisp, when a function
or variable is not bound, the system raises an error, whereas Yacas
returns the expression unevaluated.
Thus this project takes a minimum subset of Common Lisp to implement
a minimum environment for running code originally written in Yacas
script. In practice this system could then also be used in other
Lisp dialects like Scheme or elisp, or a minimum Lisp interpreter
implementation can be written for other environments.
The following sections describe the implementation of the parts
described above.
Naming conventions
Along with the code that is converted to Lisp code, and the
code to do this conversion (written in Yacas code), comes
a small body of utility functions written in Lisp, which
are required for simulating Yacas in a Lisp environment.
The functions defined that offer specific functionality
for Yacas interpretation are prepended with a yacas-,
in order to be able to easily recognize their origin.
Functions compiled from Yacas script have yacas-script-
prepended, and -arity-n appended (where n is the arity
of the function defined).
The lisp code is divided into the following modules:
- yacas.lisp - the main top-level entry code. This module
loads all other modules, and implements the top-level read-eval-print
loop.
- match.lisp - implementation of dynamic pattern matching.
- yacasread.lisp - implementation of the parser.
- yacaseval.lisp - implementation of the Yacas evaluation scheme.
- yacasprint.lisp - implementation of the infix pretty printer.
- yacassupport.lisp - various other utility routines, defining
a small API that can be called from Yacas code or the command line.
Functions used from the Common Lisp environment
The conversion to Common Lisp uses a small sub-set of what
Common Lisp offers, or worded differently, it only needs
a small subset in order to be implemented. Better optimized
versions can be made specifically for Common Lisp, but the exercise
is to define a minimum required set of features.
The following is used from Common Lisp:
- the T and NIL atoms, where NIL is the empty list but
also designates 'false' when used in a predicate. Anything other
than NIL is considered to represent 'true'.
- defun, cond, equal, atom, eval, and, bound, listp, first, rest
The read-eval-print loop
Yacas can be invoked from within the Common Lisp shell
by typing (yacas). This starts the normal read-eval-print
loop, parsing Yacas syntax, converting it to internal
format, evaluating it, and lastly printing the result
on screen in the same infix syntax used for input.
Note that in theory both read and print can be replaced
by something else, or not implemented at all (then the
standard Lisp print and read can be used.
The functions to perform these tasks are yacas-read,
yacas-eval and yacas-print.
Making the Yacas parser available
The parser acts as a front-end to Yacas functionality,
converting infix notation more commonly used by humans for
writing down mathematical expressions into an internal
representation. For Lisp the representation is fixed: linked
lists of atoms.
Compiling functions to native Lisp syntax
The pattern matcher
The custom evaluator
Part of the language lies in how expressions get evaluated,
after they have been converted to internal format, taking
an input expression and returning some result after performing
an operation on the expression commonly referred to as evaluation.
There are slight differences between the way Common Lisp evaluates and
the way Yacas expressions should be evaluated, necessitating
a bit of code between the two.
In Yacas, when a function is not defined or a variable not bound
to a value, the expression in question is returned unevaluated
(actually, in the case of a function call, its arguments are evaluated).
Since interpreting a Lisp program is just an algorithm, and any algorithm
can be implemented in Lisp, one could write a Lisp interpreter in Lisp
itself. In fact, it is very simple to do so. This section describes an
example Lisp interpreter written in Lisp itself. It will be used in the
end to implement an interpreter for Yacas code.
The advantage of directly compiling to native code (c++/Java) is clear;
one stands a chance of writing a Lisp interpreter in Lisp itself, and
have it be as efficient as the internal interpreter itself (if the
compiler
is good enough). The interpreting code just needs to be compiled by a good
compiler.
The system in action
Example output code generated by the compiler