On Sun, May 31, 2015 at 10:41 AM, Jonathan S. Shapiro <s...@eros-os.org> wrote:
> On Sat, May 30, 2015 at 5:17 PM, Matt Oliveri <atma...@gmail.com> wrote:
>> On Sat, May 30, 2015 at 5:28 PM, Jonathan S. Shapiro <s...@eros-os.org>
>> wrote:
>> > Except I'm not sure that we can forward-reference a
>> > template in this way.
>>
>> Right. ASTNode should've gone before Expr.
>
> The dependency is cyclic. We either need a way to forward-declare
> ASTNode<T>, or we need a way to define the entire set of types as mutually
> co-recursive.
Maybe I should mention at this point that I've never used C++ very
heavily, so you may be right about this _in C++_, maybe due to a
stupid decision about how to instantiate templates. But that would be
a pretty uncomfortable and unnecessary-seeming restriction, and
there's no such restriction in languages with ML-based type
parameters.
To check again that we're talking about the same thing, the following
compiles in OCaml:
type 'a bar = 'a * ('a->'a);;
type foo =
Done |
Foo of int * foo bar;;
let huh = Foo(5,(Done,fun _->Done));;
bar doesn't depend on foo.
A similar thing compiles in Java:
interface Bar<T>
{
T thing();
T action(T t);
}
abstract class AbsFoo {}
class Done extends AbsFoo
{
public static final Done i = new Done();
private Done() {}
}
class Foo extends AbsFoo
{
int i;
Bar<AbsFoo> b;
public Foo(int i,Bar<AbsFoo> b) {this.i = i; this.b = b;}
}
public class FooBar
{
public static void main()
{
AbsFoo huh = new Foo(5,new Bar<AbsFoo>()
{
public AbsFoo thing() {return Done.i;}
public AbsFoo action(AbsFoo f) {return Done.i;}
});
}
}
Bar doesn't depend on AbsFoo.
(I am reminded how awkward it is to try simple things in Java.)
>> Anyway, why does this problem keep switching languages? At first I
>> thought you were doing something in F#, then I showed it in OCaml, now
>> today for a while I thought you wanted to be able to do it in BitC,
>> and now you're talking about templates from C++.
>
> I went to C++ because you introduced ASTNode<T>, so I assumed you were
> talking about C++ templates. Sorry if I misunderstood you. And I agree that
> C++ is a uniquely bad language to talk about this in.
Nah. Java and C# ripped off C++'s syntax for type parameters, but it's
not templates.
> But here's the key point to keep in mind:
>
> In OCaml, F#, and Haskell, value constructors are not procedures. You cannot
> pass them as parameters.
I thought they were in Haskell. Anyway, it doesn't matter; I didn't do that.
> Also (at least in these languages) union leg
> constructors are not types. You cannot use a leg constructor name to
> instantiate a type variable.
Yeah yeah.
> Because of this, I'm not seeing how
> parameterization tricks in *any* of these languages get us anywhere.
Because you can have a 1-to-1 correspondence between types and value
constructors, if it's called for. Not having constructors
automatically be types is not a real restriction.
> It's clear to me that we *could* design a language in which these things
> *are* types, and it's clear to me that there are some valid use-cases for
> doing so. I'm just not sure that there are *enough* valid use cases to be
> worth bothering.
I think from an implementation point of view, it's more natural to
think of constructors as types. And it is sometimes convenient. But
maybe typed functional languages aren't implemented quite how I'd
expect, and there's some reason to avoid it.
>> While I am saying that you should be able to do this (factoring with
>> Node, not subunion) in any of those, I don't know if it'd be a good
>> way to do it in any of those except OCaml.
>
> Fair enough. Though note that without subunion (or something that serves a
> similar function) we can't really express ASTs with static typing.
> Ultimately we either have to deal with the fact that
>
> expr == mulexpr | divexpr | addexpr | subexpr
>
> or we have to deal with a lot of unnecessary case legs and weak checking of
> the tree hierarchy. If we have to accept weak checking, we aren't getting
> much value out of the static typing for validating the construction of the
> tree.
Performance issues aside, subunions should never be technically
necessary either. We can just coerce from a union with few
constructors to one with more. But I can't think of why we'd actually
need to do that coercion when traversing the AST. As a consequence, I
don't actually see why you'd need subunions for an AST.
> Just to be clear: this may very well be a case where it isn't worth the
> bother to push static types this hard.
Maybe. But I still think it works.
>> > Even if we can, it begs the question of how to specialize the member
>> > functions of ASTNode, which need to do different things depending on how
>> > T was instantiated. We really don't want do this by using a distinct
>> > function for each type T.
>>
>> Back when I recommended it, Node was just an alias for a tuple type.
>> No member functions. If the AST were to be a variant datatype, it
>> wouldn't technically have member functions either. I showed how you'd
>> define a function by pattern matching on Node and then the children
>> field (which didn't have a name at the time).
>>
>> If you're doing this in a class-oriented way, I wouldn't recommend Node at
>> all.
>
> Whether the functions are member functions or global functions isn't really
> the point. That's just syntactic sugar. The point is that we probably don't
> want to have to write a distinct function for each variant of the Node type.
> It's too difficult in practice to maintain things that way.
Sure. My point was that you seem to be making assumptions about how
code working with my style of AST would work, and that it would be a
mess. But the style of code I recommended was not a mess. The only
operations on Node would be to access the common fields and the
children structure, which are generic.
_______________________________________________
bitc-dev mailing list
bitc-dev@coyotos.org
http://www.coyotos.org/mailman/listinfo/bitc-dev
