Re: Adding Identities to Peval

[Noah Lavine]

Hello,

On Thu, Feb 16, 2012 at 10:06 AM, Andy Wingo <address@hidden> wrote:
> On Thu 16 Feb 2012 14:18, Noah Lavine <address@hidden> writes:
>
>>>  (let ((x (random)))
>>>    (eq? x x))
>>
>> (let* ((x (random))
>>        (y (list x))
>>        (z (car y))
>>   (eq? x z))
>
> This one should reduce to the same thing, but currently doesn't because
> (list x) is not considered a "constant expression" because `let' is a
> "constructor" (quotes to indicate the language of peval).  If we can
> propagate it (probably true in this case, given that it has only one
> use), then the expression folds as before:
>
>  (let* ((x (random))
>         (z (car (list x))))
>    (eq? x z))
>  =>
>  (let ((x-129 (random)))
>    (eq? x-129 x-129)))
>
> So I don't think that for this purpose (identity) we need any more
> mechanism

So you're saying that the gensym that comes from psyntax should
essentially be the identity marker, because there is one gensym for
each value. To make sure I understand, in the x-y-z example, psyntax
would produce different gensyms for x and z, but peval could merge
them later on, right?

In that case, peval would maintain the invariant "if two values must
always be the same, they have the same gensym". Correct?

This seems just a good as what I implemented. I am happy with either way.

>> In order to type-check, you need to be able to associate extra
>> information with a value (its type) even in cases where you don't know
>> the value.
>
> For this purpose, have you considered creating a functional database of
> facts?  Then you can add facts when you see conditionals, for example,
> and you get different facts in the different branches.
>
>  (if test consequent alternate)
>  ;; assuming the test doesn't fold
>  => (make-if (for-test test current-facts)
>              (for-tail consequent (add-fact test #t current-facts))
>              (for-tail consequent (add-fact test #f current-facts)))

This is an interesting idea, and I hadn't really considered it. I had
certainly planned to let the information associated with values change
as the environment changes, which would let it use conditional and
nonlocal-exit information. But a database goes beyond that.

The big difference is that a database could express relationships
between values - if information is associated with a value, where does
the information x < y go? This makes me think that a database is a
long-term solution.

However, if you're not expressing relationships, then I think the
functional database would just amount to keeping an environment
mapping value names to information about them. I hadn't thought this
through when I made my post, but I realize that this is what I would
have to do to let my information-about-values change over time. So
three paragraphs later, I think we agree :-). However, what I'd really
like to do is use an IR that expresses control flow, as you say below.

> This is related to range analysis.  But, it's also something that's
> easier to do with an explicit notion of control flow (i.e. a CPS IR).

Yes, I think you're right. I would be very interested in working on a
CPS IR, but I remember you had a blog post a couple months ago where
you said you weren't sure if CPS or ANF was better for Guile. What do
you think about intermediate representations now?

Noah