Re: Writing a FAST compiler.

kend@data.uucp (Ken Dickey)
Wed, 7 Aug 91 09:44:59 PDT

          From comp.compilers

Related articles
Writing a FAST compiler. (1991-08-05)
Re: Writing a FAST compiler. (1991-08-07)
Re: Writing a FAST compiler. (1991-08-07)
Re: Writing a FAST compiler. (1991-08-07)
Re: Writing a FAST compiler. kend@data.uucp (1991-08-07)
Re: Writing a FAST compiler. ames!! (Tom Wicklund) (1991-08-08)
| List of all articles for this month |

Newsgroups: comp.compilers
From: kend@data.uucp (Ken Dickey)
Keywords: performance, bibliography, interpreter, available
Organization: Compilers Central
References: 91-08-022
Date: Wed, 7 Aug 91 09:44:59 PDT (Patrick C Beard) writes:

>... Therefore, my question is, how do I go about creating a compiler/
>interpreter that goes as fast as possible, uses as little memory as possible,
>and produces reasonably efficient code as possible. The obvious application
>is for a compiler that runs on a microcomputer such as the Macintosh, with
>limited resources. What are some general approaches I can follow to create
>a compiler that generates slow to moderate code very quickly?

Two general methods are bytecode-compilers and flow-graph compilers

Doing a byte-code compiler gives about a 5->1 compression over native code
for about a 5 X speed hit. (Example: LightShip's MacScheme "interpreter",
David Betz's XScheme compiler, TI's PC-Scheme).

"Compiling" to a linked flow-graph and executing the graph is also
used (Example: ELK, Gambit Scheme's "interpreter"). A flow-graph may
be traversed to generate byte (virtual) codes or native code. In
general, flow-graphs tend to be a bit more space-consumptive (although
the "closure comilation" method looks pretty compact {Warning: I have
not measured comparitive sizes}.

IMHO doing good, fast, runtime support is probably as critical for
speed as the compilation process--it makes sense to spend time in both
areas for speed.

-Ken Dickey kend@data.uucp

M. Feeley and G. LaPalme, "Using Closures for Code Generation", Journal
of Computer Languages 12, 1 (1987), 47-66, Pergamon Press.

Davidson & Gresh: "Cint: A RISK Interpreter for the C Programming
Language", SIGPLAN Notices v22, #7, July 1987 == Proceedings of the
SIGPLAN '87 Symposium on Interpreters and Interpretive Techniques
{Note also other papers here}.

S. Kamin, in _Programming Languages: An Interpreter-based Approach_,
Addison-Wesley, Reading, Mass., 1990.

...[I don't have my refs handy, I can dig up some more on request]


Some Scheme implementations (including Marc Feeley's closure compiler)
& code are available from the Scheme Repository: anonymous ftp from [] under pub/scheme.

XScheme is widely available on BBSs and is probably the most simple
bytecode source available (note also XLisp by the same author).


Implementation: Elk
Implemented by: Oliver Laumann <net@tub.UUCP> <net@tub.BITNET>
Hardware: VAX, Sun-3, Sun-4, ISI 680x0, Intel 80386, Mips,
                                                IBM/RT, and others
Operating Systems: UNIX/SunOS/Ultrix
Price/Availability: Free. Available as source code through the usual
                                                sources archives and by e-mail from the author
Intended Use: Primarily as a general extension language

Elk (Extension Language Kit) is a Scheme interpreter intended to be
used as a general extension language; it is also useful as a stand-alone
implementation of Scheme.

One purpose of the Elk project is to end the recent proliferation of
mutually incompatible Lisp-like extension languages. Instead of
inventing and implementing yet another extension language, application
programmers can link the Scheme interpreter into their application
in order to make it extensible and highly customizable.

The Elk project was started in 1987 to support ISOTEXT, an ODA-based
document system (a WYSIWYG editor) that is being developed at the
Technical University of Berlin. Elk has been successfully demonstrated
as the extension language kernel of ISOTEXT, e.g. at the Hanover Fair 1989.

The Elk Scheme interpreter is R^3RS compatible (with some minor exceptions
listed in a separate document); future releases will conform to the R^4RS
and/or P1178 as soon as the respective standards become available.

Non-standard features of the Scheme implementation include:

            o dynamic loading of object files
            o creation of an executable image from the running
                  interpreter (``unexec'')
            o a macro facility
            o environments as first-class objects
            o dynamic-wind, fluid-let
            o autoloading, provide/require

The Scheme interpreter can easily be extended by application-specific
new types and primitive procedures. Such extensions are typically
written in C or C++ and dynamically loaded into the running interpreter.

The current release of Elk includes several such extensions, e.g.
interfaces to the X11 Xlib and to the application programmer interface
of the Xt intrinsics, and interfaces to the Athena, HP, and Motif
widget sets.


This message announces the availablility of Scheme release scm2d. All
bugs that were reported have been fixed. Scm now has an error,
system, and read-string! functions, file positioning, and can open
files for simultaneous reading and writing.

Scm conforms to Revised^3.99 Report on the Algorithmic Language Scheme
[Draft August 31, 1989] and the IEEE specification. Scm runs under
Unix and similar systems, VMS, and MS-DOS.

Scm is interpreted and has 30 bit immediate integers for numbers.
Tail recursion is implemented for interpreted code. Scm uses and
garbage collects off the C-stack. This allows routines to be written
in C without regard to GC visibility. Full
call-with-current-continuations are supported except on VAX and SUN-4.
Stack (escape) call-with-current-continuations are supported on all
machines. ASCII and EBCDIC are supported.

Documentation is included on the internal representation and how to
extend or include scm in other programs.

ftp [] (anonymous)
cd archive/scm

This directory contains the distribution version 2d of scm.
    `scm2d.shar' is a shar file of the C code distribution.
    `scm2d.tar.Z' is a compressed tar file of the C code distribution.
    `test.scm' is Scheme code which tests conformity with the IEEE spec.
It is included in the shar and tar files. I will include
additions that are mailed to me.
    `utils.scm' contains Scheme code for tracing functions as well as
provide and require.
    `public.lic is the GNU General Public License.

Be sure to get and read the GNU General Public License (public.lic).
It is included in the shar and tar files.

To receive an IBM PC floppy disk with the source and executable files
send $50 to Aubrey Jaffer, 84 Pleasant St. Wakefield MA 01880, USA.

If you like scm you can support the development and maintainence of
it by buying a disk from me or by sending money to the above address.
Money received will also help speed the release of a free symbolic
mathematics system (written in scheme).



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.