Mini Scheme -- A science project
Load syntactic analyzer implementation:
perl scheme.pl [-quiet] [-no-init] [-no-stats] [-echo-file <filename>] [-load <filename>] [-init-file <filename>]Load metacircular evaluator implementation:
perl metacircular.pl [-quiet] [-no-init] [-no-stats] [-echo-file <filename>] [-load <filename>] [-init-file <filename>]This is for a science project that I am doing. The abstract of my project:
Title
Studying the Effects of a Syntactic Analyzer on Scheme Program Execution Time
Introduction
In the MIT introductory book to computer programming, Structure and Interpretation of Computer Programs, the outline for a simple Scheme interpreter is given. In following sections, enhancements are made to this interpreter. One of the most radical changes to the interpreter is done by separating syntactic analysis of a Scheme expression from the execution of the same. According to the authors, this greatly improves execution times.
The purpose of this experiment is to study the effects of a syntactic analyzer on run time. We believe that if a syntactic analyzer is used before evaluation of Scheme code, a great increase in speed will be observed.
For the full, up-to-date lab report, see the doc/ directory in this project.
In chapter 4 of Structure and Interpretation of Computer Programs, the authors describe a simple scheme interpreter. In subsequent sections, enhancements are made to this interpreter. The two main versions of interpreters are "metacircular" interpreters and "syntactic analyzers".
TODO: Write how a metacircular evaluator works.
TODO: Write how a syntactic analyzer works.
- quiet
-
When this flag is present, load messages are silenced.
- no-init
-
When this flag is present, the init file in init.scm is not loaded.
- no-stats
-
When this flag present, memory statistics are suppressed.
- load
-
Takes a filename and loads it immediately after loading the "init file" and printing the memory statistics.
- echo-file
-
This takes a file name to output memory statistics.
- init-file
-
Takes a alternate "init file" to load. Default is init.scm in the working directory.
No hygienic macro system.
The numeric tower is not implemented. All number types are snarfed directly from Perl.
STRING is a special form. This is purely for ease of implementation.
The following features are adapted from CMU Common Lisp:
NIL is a symbol.
No tail-call optimizations.
Next to no type checking.
Next to no error checking.
- Init file
-
The default init file is init.scm in the working directory. An alternate file may be specified with the "-init-file" option.
- Lexical Addressing
-
This cut down my execution times by about 50%. Big win.
When I get around to it, I'll try to add these things in:
- Debugger
-
BIG maybe.
I think I could optimize memory in the following manner: because of syntactic analysis, we can know what variables are going to be needed in a given expression. We can use this to do two things: warn the user when there is a variable that is not used, and optimize which variables get saved in a closure environment.
I might be able to replace the Cons class with some more low-level managing of hashes. This might make it a bit more difficult to distinguish between different data types, but it might make my data structures operate a bit faster. I think I might be able to get a big speed gain out of this.
DOTimes is not working in the metacircular interpreter. Big problem.
Macros are not inserted into the global enviroment. This allows for namespace collision. If a symbol, defined as a macro, is defined as a function, the macro will be expanded, to the confusion of the programmer. Also, a symbol may be a variable without conflict.
I could add checking for this in variable/function lookups, definitions, and assignments.
The Cons package may have self-referential data structures, not allowing the garbage collector to reallocate memory so consumed.
Too slow. I'm looking for optimizations.
NIL really needs some clean-up.
Backquote does not handle dotted tail notation properly.
Ashton Wiersdorf <ashton.wiersdorf@mailblock.net>