[perl #17030] [PATCH] Implementation of Lists for languages/scheme
Dan Sugalski
>The recent discussion of languages independence rememberd me of an
>very old patch of mine which implements scheme pairs. (January 2002).
>The languages/scheme directory did not change very much since then,
>but the key system totally changed since then.
>
>But neverless, I got it running. The dedicate SchemePair PMC is not
>necessary any more, I just used an Array of size 2.
>
>scheme now can create pairs with (cons) and lists with (list), print
>them using (write) and access its elements using
>(car), (cdr), (set-car!) and (set-cdr!). See lists.t for examples.
Cool, applied. How far from "real" scheme are we?
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Juergen Boemmels
> At 1:58 PM +0000 9/5/02, "Jürgen" "Bömmels" (via RT) wrote:
> >The recent discussion of languages independence rememberd me of an
> >very old patch of mine which implements scheme pairs. (January 2002).
> >The languages/scheme directory did not change very much since then,
> >but the key system totally changed since then.
> >
> >But neverless, I got it running. The dedicate SchemePair PMC is not
> >necessary any more, I just used an Array of size 2.
> >
> >scheme now can create pairs with (cons) and lists with (list), print
> >them using (write) and access its elements using
> >(car), (cdr), (set-car!) and (set-cdr!). See lists.t for examples.
>
> Cool, applied. How far from "real" scheme are we?
I think its quite far.
The first thing is symbols and strings. But how do I represent them at
parrot-level. PerlString maybe, but then how will they be distinct
from each other. Or just leave out strings for a while.
Lexicals are also missing. I haven't looked closely to that. Without
variables a language is not very useful.
lambda-expression: this may compile just down to a sub.pmc
Functions like map, apply, list?, etc. have to be implemented.
Macros, tail-recursion, eval, and call/cc are also needed to call it
"real".
I hope the next patch will not need another half a year.
juergen
--
Juergen Boemmels boem...@physik.uni-kl.de
Fachbereich Physik Tel: ++49-(0)631-205-2817
Universitaet Kaiserslautern Fax: ++49-(0)631-205-3906
PGP Key fingerprint = 9F 56 54 3D 45 C1 32 6F 23 F6 C7 2F 85 93 DD 47
Piers Cawley
f> Dan Sugalski <d...@sidhe.org> writes:
>
>> At 1:58 PM +0000 9/5/02, "Jürgen" "Bömmels" (via RT) wrote:
>> >The recent discussion of languages independence rememberd me of an
>> >very old patch of mine which implements scheme pairs. (January 2002).
>> >The languages/scheme directory did not change very much since then,
>> >but the key system totally changed since then.
>> >
>> >But neverless, I got it running. The dedicate SchemePair PMC is not
>> >necessary any more, I just used an Array of size 2.
>> >
>> >scheme now can create pairs with (cons) and lists with (list), print
>> >them using (write) and access its elements using
>> >(car), (cdr), (set-car!) and (set-cdr!). See lists.t for examples.
>>
>> Cool, applied. How far from "real" scheme are we?
>
> I think its quite far.
> The first thing is symbols and strings. But how do I represent them at
> parrot-level. PerlString maybe, but then how will they be distinct
> from each other. Or just leave out strings for a while.
Symbol: [ '*symbol*', "symname" ]
Held in a Hash (hashed on the string name).
String: [ '*string*', "a string" ]
Which means Pairs become: [ '*pair*', <car>, <cdr> ]
(Or, more likely)
{ type => '*symbol*', value => 'symbol', (vtable => ...)? }
{ type => '*string*', value => 'a string' }
{ type => '*pair*', value => [ <car>, <cdr> ] }
{ type => '*int*', value => 1 }
{ type => '*rational*', value => 1/2 }
> Lexicals are also missing. I haven't looked closely to that. Without
> variables a language is not very useful.
{ type => '*environment*' value => {scratchpad => aScratchPadPMC}
> lambda-expression: this may compile just down to a sub.pmc
> Functions like map, apply, list?, etc. have to be implemented.
{ type => '*function*', value => {env => anEnvironment,
arglist => aListOfSymbols,
sequence => aListOfForms} }
{ type => '*compiled-function*', value => aSubPMC }
All these types should possibly also carry a pointer to either a jump
table or a hash of type methods so, for instance the default car
becomes (in perlish pseudocode)
sub car ($thing) { $thing.{vtable}{car}.($thing) }
For bonus points things should be arranged so that 'vtable{car}' can
be any of a scheme function, a sub.pmc or a custom op. For tail call
bonus points it should be possible to alter the current continuation
before calling (or just to make a tail call to it as appropriate...)
> Macros, tail-recursion, eval, and call/cc are also needed to call it
> "real".
Oh yes: continuation: { type => '*continuation*',
value => aContinuation.pmc }
The empty list: { type => '*the-empty-list*',
value => '*the-empty-list*' }
etc...
Implementation is a simple matter of coding. I've been reasonably
convinced since PerlHashes became ready for primetime that one could
implement a full blown, if not necessarily very *fast* version of
scheme whilst maintaining one's own environments, continuations and
all the other good stuff, but lack of tuits has tended to get in the
way of implementing it.
Things would almost certainly be easier with full blown PMCs handling
dispatch for the 'thing' that a '*function*' points at, but not
entirely necessary. Another option is to make first class PMCs of all
the various types, but I'm not sure how one would go about
implementing 'mixed' vtables, where some things are implemented in C,
others PBC and still others in one interpreted language or
another. One option for that would be to have a single 'SchemeObject',
which as well as having a vtable implemented in C would first do
dispatch through its 'scheme_vtable' hash. Continuations, Integers,
Rationals, and other things which map directly onto existing PMC types
(and which don't need extra methods) could then just use their normal
PMC.
Thoughts?
--
Piers
"It is a truth universally acknowledged that a language in
possession of a rich syntax must be in need of a rewrite."
-- Jane Austen?
John Porter
> Juergen Boemmels <boem...@physik.uni-kl.de> writes:
> > But how do I represent them at parrot-level.
>
Etc.
The point being, we're building these things into parrot so that
HLLs can use them natively, rather than have to invent each their
own particular flavor of wheel.
--
John Douglas Porter
Juergen Boemmels
[...]
> >> Cool, applied. How far from "real" scheme are we?
> >
> > I think its quite far.
> > The first thing is symbols and strings. But how do I represent them at
> > parrot-level. PerlString maybe, but then how will they be distinct
> > from each other. Or just leave out strings for a while.
>
> Symbol: [ '*symbol*', "symname" ]
>
> Held in a Hash (hashed on the string name).
>
> String: [ '*string*', "a string" ]
>
> Which means Pairs become: [ '*pair*', <car>, <cdr> ]
That would be a possibility. The object-size increase would only be
33-50%. To get a working prototype this is ok. Not everything is an
object, but everything is an array.
The later way would be to have two PMCs SchemeSymbol and SchemePair,
both inheriting from PerlString (or maybe this will be renamed to
String). The only diffrence would be the type and maybe the stringify
function.
> (Or, more likely)
>
> { type => '*symbol*', value => 'symbol', (vtable => ...)? }
> { type => '*string*', value => 'a string' }
> { type => '*pair*', value => [ <car>, <cdr> ] }
> { type => '*int*', value => 1 }
> { type => '*rational*', value => 1/2 }
No, I don't think so. This would be a Scheme Interpreter written in
Perl, and compiled to Parrot, and not a Scheme program compiled to
Parrot. If language-independent means that you can write an
interpreter for any language the C is language independent too.
> > Lexicals are also missing. I haven't looked closely to that. Without
> > variables a language is not very useful.
>
> { type => '*environment*' value => {scratchpad => aScratchPadPMC}
There is already a ScratchPadPMC. Where is it? It's not in classes/,
is it. As a first implementation a PerlHash is sufficent, (I actually
have a patch doing exactly this, it just needs a little polish. Maybe
I will submit it tomorrow). But most of the lexical scope can resolved
at compile time. parrot_assembly.pod describes an op fetch_lex_p_i_i
but this seems not implemented yet.
> > lambda-expression: this may compile just down to a sub.pmc
> > Functions like map, apply, list?, etc. have to be implemented.
>
> { type => '*function*', value => {env => anEnvironment,
> arglist => aListOfSymbols,
> sequence => aListOfForms} }
>
> { type => '*compiled-function*', value => aSubPMC }
I haven't thought much about this yet.
[...]
> Implementation is a simple matter of coding. I've been reasonably
> convinced since PerlHashes became ready for primetime that one could
> implement a full blown, if not necessarily very *fast* version of
> scheme whilst maintaining one's own environments, continuations and
> all the other good stuff, but lack of tuits has tended to get in the
> way of implementing it.
I also think it would be possible to implement scheme. The major
show-stopper the access to aggregates has been solved.
> Things would almost certainly be easier with full blown PMCs handling
> dispatch for the 'thing' that a '*function*' points at, but not
> entirely necessary. Another option is to make first class PMCs of all
> the various types, but I'm not sure how one would go about
> implementing 'mixed' vtables, where some things are implemented in C,
> others PBC and still others in one interpreted language or
> another.
IMHO this is the way to go.
SchemeString, SchemeSymbol -> Kind of PerlString, just diffrent type.
SchemePair -> Special Class abusing pmc->data and pmc->cache.pmc_val
as car and cdr (this needs a custom mark function) but getting rid
of one extra indirection.
Envoirments -> The find_lex/fetch_lex looks promising.
Functions -> Subs should be enough.
> One option for that would be to have a single 'SchemeObject',
> which as well as having a vtable implemented in C would first do
> dispatch through its 'scheme_vtable' hash.
The diffrence would be the subtype. But AFAIK there is no way to get
this subtype from the PMC in bytecode. Maybe a subtypeof_i_p op is
missing. But this would lead to an extra indirection at runtime:
SchemeObject->vtable->subtype->vtable
For the primary objects of a language this should not be necessary.
> Continuations, Integers,
> Rationals, and other things which map directly onto existing PMC types
> (and which don't need extra methods) could then just use their normal
> PMC.
>
> Thoughts?
see above
b.
Piers Cawley
Thanks for that John. I always relish being patronized. One wonders if
you actually read to the bottom of the message where I outlined the
beginnings of a SchemeObject.PMC to provide a consistent interface to
this sort of thing (and, potentially to *any* Object like thing).
Piers Cawley
Um... I don't see what having appropriate datatypes inside the
interpreter has to do with the language in which the interpreter is
implemented. Personally I think there's a very good case for
implementing the lot directly in IMCC (apart from the Object and Class
PMCs, obviously -- see below).
>> > Lexicals are also missing. I haven't looked closely to that. Without
>> > variables a language is not very useful.
>>
>> { type => '*environment*' value => {scratchpad => aScratchPadPMC}
>
> There is already a ScratchPadPMC. Where is it? It's not in classes/,
> is it. As a first implementation a PerlHash is sufficent, (I actually
> have a patch doing exactly this, it just needs a little polish. Maybe
> I will submit it tomorrow). But most of the lexical scope can resolved
> at compile time. parrot_assembly.pod describes an op fetch_lex_p_i_i
> but this seems not implemented yet.
Up to a point Lord Copper. That's not going to fly (easily) once you
have a read eval print loop in place. I want to be able to do, say
repl> (define (make-adder n) (lambda (x) (+ n x)))
#t
repl> (define add1 (make-adder 1))
#t
repl> (add1 10)
11
in an interactive session, otherwise what would be the point?
>> > lambda-expression: this may compile just down to a sub.pmc
>> > Functions like map, apply, list?, etc. have to be implemented.
>>
>> { type => '*function*', value => {env => anEnvironment,
>> arglist => aListOfSymbols,
>> sequence => aListOfForms} }
>>
>> { type => '*compiled-function*', value => aSubPMC }
>
> I haven't thought much about this yet.
Ah. Now, to my way of thinking this is the most important
part. Functions are absolutely fundamental to Scheme and you might as
well not bother until you've worked out how you're going to implement
them.
> [...]
>
>> Implementation is a simple matter of coding. I've been reasonably
>> convinced since PerlHashes became ready for primetime that one could
>> implement a full blown, if not necessarily very *fast* version of
>> scheme whilst maintaining one's own environments, continuations and
>> all the other good stuff, but lack of tuits has tended to get in the
>> way of implementing it.
>
> I also think it would be possible to implement scheme. The major
> show-stopper the access to aggregates has been solved.
>
>> Things would almost certainly be easier with full blown PMCs handling
>> dispatch for the 'thing' that a '*function*' points at, but not
>> entirely necessary. Another option is to make first class PMCs of all
>> the various types, but I'm not sure how one would go about
>> implementing 'mixed' vtables, where some things are implemented in C,
>> others PBC and still others in one interpreted language or
>> another.
>
> IMHO this is the way to go.
> SchemeString, SchemeSymbol -> Kind of PerlString, just diffrent type.
> SchemePair -> Special Class abusing pmc->data and pmc->cache.pmc_val
> as car and cdr (this needs a custom mark function) but getting rid
> of one extra indirection.
> Envoirments -> The find_lex/fetch_lex looks promising.
> Functions -> Subs should be enough.
Not even close to enough. Unless you're going to have the
Read/Eval/Print thing I showed above compile any functions down to
parrot immediately, which would be fine, but we don't yet have the
capability to create and execute parrot code on the fly, so that's a
showstopper right there. But we *can* represent scheme functions as
environments + arglist + sequence of forms already.
>> One option for that would be to have a single 'SchemeObject',
>> which as well as having a vtable implemented in C would first do
>> dispatch through its 'scheme_vtable' hash.
>
> The diffrence would be the subtype. But AFAIK there is no way to get
> this subtype from the PMC in bytecode. Maybe a subtypeof_i_p op is
> missing. But this would lead to an extra indirection at runtime:
> SchemeObject->vtable->subtype->vtable
> For the primary objects of a language this should not be necessary.
typeof is a *really* bad idea. Let the 'Object' PMC handle the
multilevel vtable look up (in exactly the same way that one does
lexical lookup in the environment chain) and method invocation. So,
for instance, the bare Object would have no 'cdr' method, so to do
C<< call_method Pn, 'cdr' >> would throw an exception. But then one
could do
pair_cdr:
...
ret
...
new P1, .Class
new P2, .Sub
set_addr I0, pair_cdr
set P1["cdr"], P2
set P1["classname"], "SchemePair"
set P1["isa"], "SchemeObject"
set P2["class"], P1
...
set I1, 0
set I2, 1
set P3, "foo"
call_method P2, "set_car"
set P3, "bar"
call_method P2, "set_cdr"
call_method P2, "car"
print P3 # prints "foo"
The thing is, we're going to need a Class/Object structure along these
lines for Perl/Ruby/Parrot objects anyway, so even though scheme won't
expose these PMCs to the end user, the effort in implementing them is
definitely worth while. And I think the extra code organizing
capability they give us is really important.
Note too, that it wouldn't be hard to set up SchemeFunc, CompiledSchemeFunc
and NativeFunc (he said, guessing at names) so that they all looked
like Sub PMCs when it came to function call time...
NB: I have a proof of concept scheme interpreter running in Perl that
uses these OO techniques, and it works really neatly, which is why
I've been thinking of doing the Parrot scheme interpreter in a similar
fashion.
John Porter
>
> >> Juergen Boemmels <boem...@physik.uni-kl.de> writes:
> >> > But how do I represent them at parrot-level.
>
You're welcome, but that wasn't for you, that was for Juergen
and anyone else who might have been wondering the same sort
of thing.
--
John Douglas Porter
Piers Cawley
Cautioning against reinventing the wheel is all very well, but it
isn't reinventing when the wheel doesn't actually exist yet.
Piers Cawley
> Piers Cawley <pdca...@bofh.org.uk> writes:
[...]
>> multilevel vtable look up (in exactly the same way that one does
>> lexical lookup in the environment chain) and method invocation. So,
>> for instance, the bare Object would have no 'cdr' method, so to do
>> C<< call_method Pn, 'cdr' >> would throw an exception. But then one
>> could do
[...]
> Intresting aproach. Doing Scheme object oriented. I have to think
> about this approach another day.
I lifted the idea from a scheme in scheme implementation I found in
_The Seasoned Schemer_ which used functions for *everything*,
including pairs, so things like car and cdr became:
(define (car obj) (obj 'car))
(define (cdr obj) (obj 'cdr))
This had the advantage of allowing for new types to be added easily as
the implementation got extended; just implement another generic
function. The approach translated almost trivially to OO.
>> The thing is, we're going to need a Class/Object structure along these
>> lines for Perl/Ruby/Parrot objects anyway, so even though scheme won't
>> expose these PMCs to the end user, the effort in implementing them is
>> definitely worth while. And I think the extra code organizing
>> capability they give us is really important.
>>
>> Note too, that it wouldn't be hard to set up SchemeFunc, CompiledSchemeFunc
>> and NativeFunc (he said, guessing at names) so that they all looked
>> like Sub PMCs when it came to function call time...
>>
>> NB: I have a proof of concept scheme interpreter running in Perl that
>> uses these OO techniques, and it works really neatly, which is why
>> I've been thinking of doing the Parrot scheme interpreter in a similar
>> fashion.
>
> I would be very intrested to hear more about this interpreter
I'll see about stripping it down (it does *scary* stuff with C<redo
LABEL> to get tail call optimization) to the basic objects and a
simple minded interpreter then (if I can find the source...). Who
knows, maybe we can port it to functional style perl 6 faster than we
can implement it in raw parrot.
Juergen Boemmels
[...]
> > There is already a ScratchPadPMC. Where is it? It's not in classes/,
> > is it. As a first implementation a PerlHash is sufficent, (I actually
> > have a patch doing exactly this, it just needs a little polish. Maybe
> > I will submit it tomorrow). But most of the lexical scope can resolved
> > at compile time. parrot_assembly.pod describes an op fetch_lex_p_i_i
> > but this seems not implemented yet.
>
> Up to a point Lord Copper. That's not going to fly (easily) once you
> have a read eval print loop in place. I want to be able to do, say
>
> repl> (define (make-adder n) (lambda (x) (+ n x)))
> #t
> repl> (define add1 (make-adder 1))
> #t
> repl> (add1 10)
> 11
>
> in an interactive session, otherwise what would be the point?
Ah I see the point. There needs to be a way to get the lexical adress
from a string. Otherweise it would be really doubling of
information: One in the compiler to get the mapping
symbol => lexical adress, and one in the repl to get the mapping
symbol => value (which internally does something like symbol =>
lexical adress => value).
Anyway the lexical scope resolution at compile-time is some kind of
optimization that wont be in the first implementation. Always look up
a lexical via find_lex/store_lex
> >> > lambda-expression: this may compile just down to a sub.pmc
> >> > Functions like map, apply, list?, etc. have to be implemented.
> >>
> >> { type => '*function*', value => {env => anEnvironment,
> >> arglist => aListOfSymbols,
> >> sequence => aListOfForms} }
> >>
> >> { type => '*compiled-function*', value => aSubPMC }
> >
> > I haven't thought much about this yet.
>
> Ah. Now, to my way of thinking this is the most important
> part. Functions are absolutely fundamental to Scheme and you might as
> well not bother until you've worked out how you're going to implement
> them.
Yes, functions are the heart of Scheme. Slowly some ideas on
implementing them come up. Your idea of using the 3 elements env,
arglist, sequence looks like the way to go. The scheme way would be to
use a list for that. The sequence would be convertet to an entry
point, as the function can be compiled in advance. The arglist may go
away when the lexical scope resolution at compile time is fully
implemented, because the only functions having access to the arglist
are the ones which are already compiled in this scope. I haven't
thought this through in detail.
> > IMHO this is the way to go.
> > SchemeString, SchemeSymbol -> Kind of PerlString, just diffrent type.
> > SchemePair -> Special Class abusing pmc->data and pmc->cache.pmc_val
> > as car and cdr (this needs a custom mark function) but getting rid
> > of one extra indirection.
> > Envoirments -> The find_lex/fetch_lex looks promising.
> > Functions -> Subs should be enough.
>
> Not even close to enough.
Ack. Thinking a little more about it, I recognized you can't get
arround the environment pointer. But perl-subs will need this pointer
also, so it may be added to the sub.pmc
sub make_add { my $add = shift; return sub { my $x = shift; return $x
+ $add }}
$add_1 = make_add (1); print $add_1->(2);
> Unless you're going to have the
> Read/Eval/Print thing I showed above compile any functions down to
> parrot immediately, which would be fine, but we don't yet have the
> capability to create and execute parrot code on the fly, so that's a
> showstopper right there.
Read/Eval/Print-Loops use eval. Eval is not the simplest part of
Scheme, but it can be implemented in Scheme, compile to parrot with
the compiler, and then get used in a repl. Then the function will
definitly have the form :
(environments arglist sequence)
> But we *can* represent scheme functions as
> environments + arglist + sequence of forms already.
Ok, you convinced me.
[...]
Intresting aproach. Doing Scheme object oriented. I have to think
about this approach another day.
> The thing is, we're going to need a Class/Object structure along these
> lines for Perl/Ruby/Parrot objects anyway, so even though scheme won't
> expose these PMCs to the end user, the effort in implementing them is
> definitely worth while. And I think the extra code organizing
> capability they give us is really important.
>
> Note too, that it wouldn't be hard to set up SchemeFunc, CompiledSchemeFunc
> and NativeFunc (he said, guessing at names) so that they all looked
> like Sub PMCs when it came to function call time...
>
> NB: I have a proof of concept scheme interpreter running in Perl that
> uses these OO techniques, and it works really neatly, which is why
> I've been thinking of doing the Parrot scheme interpreter in a similar
> fashion.
I would be very intrested to hear more about this interpreter
bye
juergen
Jonathan Sillito
up. The patch in [perl #16797] adds a scratchpad pmc (among other
things). Hopefully it is not too far out of date to apply. I
believe Melvin is looking into it ...
--
Jonathan Sillito
archie
written in lisp by peter norving a ways back. seems like
you guys are mostly strugging with lower-level things,
but give it a look. there are more advanced versions of
the compiler on his website (compile2.lisp and compile3.lisp)
this one is the shortest.
http://www.norvig.com/paip/compile1.lisp
sil...@cs.ubc.ca (Jonathan Sillito) wrote in message news:<Pine.LNX.4.44.020910...@taipan.cs.ubc.ca>...