flee@guardian.cs.psu.edu (Felix Lee) (11/20/90)
Archive-name: sp-huh/19-Nov-90
Original-posting-by: flee@guardian.cs.psu.edu (Felix Lee)
Original-subject: Scheme in Perl? (sp?): The Blurb.
Archive-site: wuarchive.wustl.edu [128.252.135.4]
Archive-directory: /usenet/alt.sources
Reposted-by: emv@ox.com (Edward Vielmetti)
0. Scheme in Perl?
Why would anyone want to write a Scheme interpreter in Perl? I have
no idea. But here it is anyway.
Scheme is small, simple, and elegant; Perl is bloated, complex, and
obscene. The wedding of the two makes an uncomfortable marriage, but
it seems to work. Perhaps opposites attract.
I call the interpreter "sp?", for no good reason.
sp? may need Perl 3.0 patchlevel 37. I've tried to avoid egregious
new-isms, but sp? may tickle bugs in earlier Perls. sp? definitely
doesn't work with patchlevel 18, reason unknown.
1. The sp? Interpreter.
If sp? does not much resemble traditional Schemes like MIT Scheme,
that is entirely my fault. I have never written any serious
applications in Scheme. My knowledge of Scheme is bookish, hardly
practical. I learned Scheme from the inside out while writing sp?.
I wrote sp? using the Revised**3 Report on Scheme. sp? is not a
complete Scheme implementation, but I included as much of R3RS as I
easily could. Here's what's missing:
sp? is not properly tail recursive. Tail recursive calls can exhaust
both heap and stack storage. Adding garbage collection will save the
heap, but saving the stack requires removing internal recursion since
Perl doesn't have any sort of longjmp or throw.
sp? doesn't have call-with-current-continuation. This also requires
removing internal recursion.
sp? has half-hearted number support. No complex numbers, rationals,
or integers; only real numbers. No distinction between exact and
inexact numbers. The reader doesn't recognize full number syntax.
Adding full-hearted support will just take a little work. Plugging in
the new bignum packages should be trivial.
2. Structural Defects.
sp? isn't quite perfect. The defects are few and enumerable. Major
flaws are listed below. Minor flaws are marked in the code with XXX.
sp? is probably buggy. I have a small regression testing suite to
help stabilize sp?'s behavior, but it's woefully incomplete. Major
features like lambda and let have been well tested; it's the small
things like asin and acos that are likely to fail.
sp? is a great monolith that should be fragmented. It might be nice
to abstract a small module for recursive data types usable by other
Perl programs. (Doing recursive data types in Perl was part of the
motivation for writing sp?.)
sp? is slower than continental drift. Earlier versions were slower
than proton decay. Anybody want to run some benchmarks?
sp? lacks garbage collection. Hooray for virtual memory.
sp? doesn't have error handling. When an error occurs, sp? prints a
cryptic message and then calls the top. Perl doesn't do unwinding on
non-local gotos, so errors consume unrecoverable memory.
sp? lacks tracing and debugging support, making it difficult to debug
non-trivial Scheme code.
sp? needs more hooks from Scheme to Perl. File and system services
are lacking. Regexp/pattern matching would be nice.
sp? is inadequately documented, both internally and externally.
sp? is about due for another once-through rewrite.
3. The Perils of Perl.
Perl may be good for rapid prototyping, but it was the wrong language
to write a Scheme interpreter in. Most of the problem is the lack of
types in Perl. Imposing a type system is a non-trivial task. It took
several false starts before I settled on the current system, which is
pretty simple and relatively (ugh) fast.
Perl's aggregate datatypes are crippled by being non-recursive: you
can't have vectors of vectors or tables of vectors. Recursive types
in Perl can be done by using references, but this is fraught with
danger. References in Perl are a little fragile; early versions of
sp? tended to crash Perl, due to subtle synergistic interactions
(bugs). The current incarnation of sp? is fairly robust.
Another headache was a phenomenon I call "variable suicide". Consider
the following Perl fragment:
sub add { local($a, $b) = @_; return $a + $b; }
$a = 2;
print &add(40, $a);
This prints "80", instead of "42". It's a nasty bit of interaction
between local() and @_. To avoid it, sp? is sprinkled with code like
local(@sip) = @_;
local($a, $b, $c) = @sip;
And writing some of the numeric functions like modulo and round was
much harder than it had to be. Perl has only token number support.
4. The Next Generation.
It's easy to find possible speed improvements in almost any section of
sp?, but I doubt the lot of them will make much difference. sp? will
still be much much slower than useful.
Munching Scheme code some more may help. Lambdas could be compiled to
pseudo-machine code or translated to Perl and eval'ed.
And when the Scheme code is all munched up, sp? can support proper
tail recursion and continuations.
Fuller Scheme support and better compatibility with MIT Scheme would
be nice. Imagine sp? running EDWIN. Imagine an editor many orders of
magnitude slower than GNU Emacs.
And sp? could use garbage collection, for those without terabytes of
virtual memory and swap space. It would be nice if Perl itself had
garbage collection. Garbage collection is actually quite urgent with
I/O ports, since each stranded I/O port may claim one file descriptor.
64 file descriptors can be exhausted quite quickly.
Don't expect any of this anytime soon. I'm done playing with sp? for
now. Feel free to muck with sp? yourself. Bug me if you come up with
anything interesting.
Next time, a Perl compiler... Turn your nasty, slow Perl programs
into nasty, slow C programs.
--
Felix Lee flee@cs.psu.edu