[bitc-dev] Quick haskell question

[Jonathan S. Shapiro]

On Fri, Aug 13, 2010 at 3:04 PM, Mark P. Jones <mpj at cs.pdx.edu> wrote:

>
> I'm not sure it's productive to debate the meaning of a fairly
> standard term like "lexical scoping", but it seems clear that
> you and I currently understand this term in different ways.
>

Yes. It wasn't my intent to start a debate. Rather, I wanted to state my
understanding so as to identify where the disconnect lies. I think we've
done that. Sorry if it seemed like I was trying to start a debate.


In the following program, for example, we get an
> output of 1 with lexical scoping or 2 with dynamic scoping.
>
>   x := 1
>   f := \y -> y + x
>   x := 2
>   print (f 0)
>
> I can see how this might appear to tie in with the "left of
> the site of use" idea that you mentioned, but that's just an
> incidental detail, not an intrinsic part of the definition.
>

Oh dear. Our difference of understanding might be rather deeper than I had
thought. So first, let me confirm that by ":=" you mean to be writing
assignment rather than performing a new variable introduction. If so, then
the program should certainly return 2. This is true because the expression
"y + x" does not capture a *copy* of x; it captures the *location* of x, and
that location has been updated by the time of the application.

If you mean a new binding introduction, then the program is malformed,
because "x := 2" attempts to bind a variable that is already bound in the
same scope. That's generally considered illegal.

If you mean something like

let x = 1 in
  let f y = y + x in
    let x = 2 in
      print (f 0)

then I agree that we should be printing one, but I'm not sure whether this
was the program you intended.


> If "left of the site of use" was part of the definition, then
> you'd have to disqualify both Haskell and Java from being
> lexically scoped because both allow implicit forward
> references.
>

Ah. Yes. That certainly disqualifies both of them. The qualifier that
implicit forward reference is allowed is significant. It significantly
alters the rules for how environments must be constructed, for example.


> The classic use case might be a set of mutually recursive
> definitions like the following pseudo code:
>
>   infixr 6 <->
>   (<->)  :: some type goes here
>   x <-> y = some definition involving <*>
>
>   infixr 7 <*>
>   (<*>)  :: some other type here
>   x <*> y = some other definition, this time involving <->
>

Thanks. Once you mentioned implicit forward references I suspected that it
would be a case like this. My opinion is that this should not be allowed in
BitC. BitC permits explicit forward declaration, and the example you give
can be defined without difficulty in that fashion, without introducing
implicit forward reference.


> To me, however,
> the best part in all of this was the fact that it allowed me to
> clean up my implementation; I don't think it was harder or
> required more code, but it encouraged me to remove clunk special
> cases and replace it with clearer, more general code....
>

I'm actually surprised that you say this. The implicit forward reference
rule seems to imply that top-level bindings are formed in a letrec
environment. Which is fine, but given this, the convention of using LET to
introduce them seems (to me) a little odd.


> But let's suppose you want to stick with "declare before use"...
> In that case, there might still be somesticky details to deal with...
>
>    infixr 8 <*>
>
>    f x = ... something involving <*> ...
>     where infix 7 <*>   -- oops, fixity after use
>           x <*> y = ...
>

So far as I can tell, the "where" construct in Haskell is just a
syntactically unusual let binding. Textually it doesn't satisfy my "up and
left" rule, but logically it does. But because it introduces bindings in
trailling context I'm not convinced it's a good thing to have. In any case,
we don't have it right now.


>    h z = ... something involving <*> ...
>         -- be sure to use the infixr 8 fixity here
>         -- and not the more recent infix 7 that was
>         -- valid only in the definition of f.
>

This one doesn't seem difficult, since the environment formed by the where
clause is no longer in scope here.


> In my opinion, you really don't want to write a lexer that
> has to track "let"s and "in"s and maintain a stack of
> fixity bindings, just to handle code like this.  Such tasks
> are much better handled during static analysis where you
> have easy access to environment structures and few to no
> left-to-right constraints.
>

I wasn't actually contemplating having the lexer do it this way. Rather, I
was contemplating having the parser maintain suitable environments for
fixities only, and having the lexer use those to look up the fixities. One
has to do something along these lines at some point; it seems that it's
either this way or in the symbol resolver. We currently run some
simplification passes before the resolver, but those could be moved.

The argument for building expression ASTs late, in my mind, is less about
environment construction than it is about distfix. As we start to broaden
out the syntax of allowed mixfix constructs, we need a progressively more
sophisticated resolver, and operator precedence will cease to be the only
consideration involved. That appears to argue for having a pass that deals
with this explicitly.

Maybe you don't buy the need for local fixity declarations
> at all?  I'd be pretty much with you on that, having never
> used them myself as far as I can recall (except in test
> programs).


Quite the contrary, I think that local fixity declarations are important,
because they prevent "leakage" of fixities into unsuspecting code.

Actually, my concern about fixities is a bit different: blending fixities
can have lots of unforeseen consequences. My inclination, at the moment, is
to introduce a notion of a "syntax" that consists of a consistent set of
fixity specifications, and have constructs to "open" a syntax within a
clearly identified scope.

shap
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.coyotos.org/pipermail/bitc-dev/attachments/20100813/3c644b6c/attachment-0001.html