Update and Questions

Update and Questions

[Noah Lavine]

Hello Guile developers,

Despite the long gap since my last email, I have in fact been working
on the compiler project. This email has two purposes: first, to make
sure that I have a basically reasonable design before I work more, and
second, to ask a logistical question.

First of all, I very much appreciated your suggestions of things to
read. I did look at the Reasoned Schemer. I also spent quite a while
studying Stalin (the compiler), because I believe that is the current
fastest Scheme compiler. (And therefore, it's the one I'd like to beat
with our compiler.) The design I am currently working with is the same
as Stalin's design.

It is a propagation network. Basically you have a graph of Tree-IL
nodes, where each Tree-IL node is connected to its parent, its
children, and optionally other nodes (a variable is connected to the
place it was declared. A primitive function is connected to the error
continuation it could jump to). The compiler propagates information
along the edges of this graph, attempting to find the minimum set of
possible values for each variable and each jump target. It also
performs partial evaluation as a special case of this.

What I have described also seems to be how Hindley-Milner type
inference works (although I think we can do a bit better than standard
Hindley-Milner systems). Does this seem like a good design for the
static analyzer portion?

One big oversight that I know of is that this doesn't do any sort of
specialization. I think that is an extremely important feature, but
when I looked at doing specialization I thought that it would use all
of the logic this would, but require a bit more work to keep the
complexity down, so I thought I should do this first.

I haven't thought much about the rest of the compiler yet, but I
imagine you can basically walk this graph and try to choose
representations for each piece of it using the information you
gathered in the analysis phase. The key ingredient for that will be a
library of representations for each Tree-IL node.

The second part of this post is a logistical question. I would like to
do this work in public, so other people can see it (and hopefully
contribute). Where is the best place to do this? Should I make a
branch on Savannah? That makes the most sense to me, but it seems a
bit unnatural, since this project is very separate from the rest of
Guile.

And finally, a fun thing. The current best Scheme compiler (that I
know of) is called Stalin. Therefore, I suggest that our compiler be
called "Stallman", after our fearless leader (whose name also starts
with "s"). :-)

Thanks a lot,
Noah

Re: Update and Questions

[David Kastrup]

Noah Lavine <noah.b.lavine@gmail.com> writes:

> And finally, a fun thing. The current best Scheme compiler (that I
> know of) is called Stalin. Therefore, I suggest that our compiler be
> called "Stallman", after our fearless leader (whose name also starts
> with "s"). :-)

I think that -pedantic should stay optional.

-- 
David Kastrup

Re: Update and Questions

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 3016 bytes --]

So it'd be the preform of something kind of Guile's AOT compiler which
we(all guilers)  had talked about few months ago?
I think it's a great idea!  And I'm glad to see your work.

PS:  I agree with "Stallman". ;-)

On Tue, Dec 6, 2011 at 12:25 PM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> Hello Guile developers,
>
> Despite the long gap since my last email, I have in fact been working
> on the compiler project. This email has two purposes: first, to make
> sure that I have a basically reasonable design before I work more, and
> second, to ask a logistical question.
>
> First of all, I very much appreciated your suggestions of things to
> read. I did look at the Reasoned Schemer. I also spent quite a while
> studying Stalin (the compiler), because I believe that is the current
> fastest Scheme compiler. (And therefore, it's the one I'd like to beat
> with our compiler.) The design I am currently working with is the same
> as Stalin's design.
>
> It is a propagation network. Basically you have a graph of Tree-IL
> nodes, where each Tree-IL node is connected to its parent, its
> children, and optionally other nodes (a variable is connected to the
> place it was declared. A primitive function is connected to the error
> continuation it could jump to). The compiler propagates information
> along the edges of this graph, attempting to find the minimum set of
> possible values for each variable and each jump target. It also
> performs partial evaluation as a special case of this.
>
> What I have described also seems to be how Hindley-Milner type
> inference works (although I think we can do a bit better than standard
> Hindley-Milner systems). Does this seem like a good design for the
> static analyzer portion?
>
> One big oversight that I know of is that this doesn't do any sort of
> specialization. I think that is an extremely important feature, but
> when I looked at doing specialization I thought that it would use all
> of the logic this would, but require a bit more work to keep the
> complexity down, so I thought I should do this first.
>
> I haven't thought much about the rest of the compiler yet, but I
> imagine you can basically walk this graph and try to choose
> representations for each piece of it using the information you
> gathered in the analysis phase. The key ingredient for that will be a
> library of representations for each Tree-IL node.
>
> The second part of this post is a logistical question. I would like to
> do this work in public, so other people can see it (and hopefully
> contribute). Where is the best place to do this? Should I make a
> branch on Savannah? That makes the most sense to me, but it seems a
> bit unnatural, since this project is very separate from the rest of
> Guile.
>
> And finally, a fun thing. The current best Scheme compiler (that I
> know of) is called Stalin. Therefore, I suggest that our compiler be
> called "Stallman", after our fearless leader (whose name also starts
> with "s"). :-)
>
> Thanks a lot,
> Noah
>
>

[-- Attachment #2: Type: text/html, Size: 3524 bytes --]

Re: Update and Questions

[David Kastrup]

Nala Ginrut <nalaginrut@gmail.com> writes:

> So it'd be the preform of something kind of Guile's AOT compiler which
> we(all guilers)  had talked about few months ago?
> I think it's a great idea!  And I'm glad to see your work.
>
>
> PS:  I agree with "Stallman". ;-)

Stallman -pedantic guile.scm

looks redundant.

-- 
David Kastrup

Re: Update and Questions

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 540 bytes --]

-pedantic? Sorry, but I'm afraid I didn't see it in Noah's description.
Anyone give me some context?

On Thu, Dec 15, 2011 at 11:34 PM, David Kastrup <dak@gnu.org> wrote:

> Nala Ginrut <nalaginrut@gmail.com> writes:
>
> > So it'd be the preform of something kind of Guile's AOT compiler which
> > we(all guilers)  had talked about few months ago?
> > I think it's a great idea!  And I'm glad to see your work.
> >
> >
> > PS:  I agree with "Stallman". ;-)
>
> Stallman -pedantic guile.scm
>
> looks redundant.
>
> --
> David Kastrup
>
>
>

[-- Attachment #2: Type: text/html, Size: 1017 bytes --]

Re: Update and Questions

[David Kastrup]

Nala Ginrut <nalaginrut@gmail.com> writes:

> -pedantic? Sorry, but I'm afraid I didn't see it in Noah's
> description. 
>
> Anyone give me some context?

gcc has an option -pedantic for strict standard adherence.

-- 
David Kastrup

Re: Update and Questions

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 528 bytes --]

well, I see. I haven't used Stalin before, so I guess the generated C code
must be compiled without any Gcc extension?

@Noah: Anyway, will you add r5rs support to it? I found Stalin doesn't
provide that.

On Fri, Dec 16, 2011 at 12:00 AM, David Kastrup <dak@gnu.org> wrote:

> Nala Ginrut <nalaginrut@gmail.com> writes:
>
> > -pedantic? Sorry, but I'm afraid I didn't see it in Noah's
> > description.
> >
> > Anyone give me some context?
>
> gcc has an option -pedantic for strict standard adherence.
>
> --
> David Kastrup
>

[-- Attachment #2: Type: text/html, Size: 993 bytes --]

Re: Update and Questions

[Noah Lavine]

On Thu, Dec 15, 2011 at 11:19 AM, Nala Ginrut <nalaginrut@gmail.com> wrote:
> well, I see. I haven't used Stalin before, so I guess the generated C code
> must be compiled without any Gcc extension?

I think he's making a joke that Richard Stallman is always pedantic,
so the -pedantic flag is redundant.

> @Noah: Anyway, will you add r5rs support to it? I found Stalin doesn't
> provide that.

I would love to. That is far in the future, though - my current goal
is to type-check Tree-IL. I have been working on that, and I think I
am close to having something ready to show, although not quite there.
Expect an email about the wip-compiler branch in the next few days.

Noah

> On Fri, Dec 16, 2011 at 12:00 AM, David Kastrup <dak@gnu.org> wrote:
>>
>> Nala Ginrut <nalaginrut@gmail.com> writes:
>>
>> > -pedantic? Sorry, but I'm afraid I didn't see it in Noah's
>> > description.
>> >
>> > Anyone give me some context?
>>
>> gcc has an option -pedantic for strict standard adherence.
>>
>> --
>> David Kastrup
>
>

Re: Update and Questions

[Nala Ginrut]

[-- Attachment #1: Type: text/plain, Size: 901 bytes --]

On Fri, Dec 16, 2011 at 7:06 AM, Noah Lavine <noah.b.lavine@gmail.com>wrote:

> On Thu, Dec 15, 2011 at 11:19 AM, Nala Ginrut <nalaginrut@gmail.com>
> wrote:
> > well, I see. I haven't used Stalin before, so I guess the generated C
> code
> > must be compiled without any Gcc extension?
>
> I think he's making a joke that Richard Stallman is always pedantic,
> so the -pedantic flag is redundant.
>
>
cool.
If Stallman imply -pedantic, then you may consider "Stallman -hasty" for
enabling Gcc extension.


> > @Noah: Anyway, will you add r5rs support to it? I found Stalin doesn't
> > provide that.
>
> I would love to. That is far in the future, though - my current goal
> is to type-check Tree-IL. I have been working on that, and I think I
> am close to having something ready to show, although not quite there.
> Expect an email about the wip-compiler branch in the next few days.
>
>
 cool too~

[-- Attachment #2: Type: text/html, Size: 1571 bytes --]

Re: Update and Questions

[Ludovic Courtès]

Hi Noah,

And as is more often the case, sorry for the delay!

Noah Lavine <noah.b.lavine@gmail.com> skribis:

> It is a propagation network. Basically you have a graph of Tree-IL
> nodes, where each Tree-IL node is connected to its parent, its
> children, and optionally other nodes (a variable is connected to the
> place it was declared. A primitive function is connected to the error
> continuation it could jump to). The compiler propagates information
> along the edges of this graph, attempting to find the minimum set of
> possible values for each variable and each jump target. It also
> performs partial evaluation as a special case of this.
>
> What I have described also seems to be how Hindley-Milner type
> inference works (although I think we can do a bit better than standard
> Hindley-Milner systems). Does this seem like a good design for the
> static analyzer portion?

I’m not an expert in that area, but it does look sensible to me at first
sight.

> One big oversight that I know of is that this doesn't do any sort of
> specialization.

What if your static analyzer was plugged after the peval run?  I expect
part of it would be redundant with peval, but for a start we could live
with the code redundancy, and look at factorizing it later.  WDYT?

[...]

> And finally, a fun thing. The current best Scheme compiler (that I
> know of) is called Stalin. Therefore, I suggest that our compiler be
> called "Stallman", after our fearless leader (whose name also starts
> with "s"). :-)

Heheh. :-)

Thanks,
Ludo’.