code review 6490089: exp/types/staging: typechecker API

exp/types/staging: typechecker API

First set of type checker files for review.
The primary concern here is the typechecker
API (types.go).

[gri, 2012-09-07 00:46:50]

Hello rsc@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go

[adonovan, 2012-09-07 14:59:17]

FYI

http://codereview.appspot.com/6490089/diff/7001/src/pkg/exp/types/staging/exp...
File src/pkg/exp/types/staging/exprstring.go (right):

http://codereview.appspot.com/6490089/diff/7001/src/pkg/exp/types/staging/exp...
src/pkg/exp/types/staging/exprstring.go:86: case *ast.BinaryExpr:
Is this output function intended for eyes only, or as input to a parser?  If so
you'll need to insert parens to disambiguate.  To do this optimally is a
function of the fixity, associativity and predecence of all your binary
operators; see Norman Ramsey (1998) "Unparsing Expressions with Prefix and
Postfix Operators".  [NB, there's a bug in that paper but Go's AST shouldn't hit
it.]

[gri, 2012-09-07 15:12:30]

Just FYI.

(A better CL will be coming today).
- gri

http://codereview.appspot.com/6490089/diff/7001/src/pkg/exp/types/staging/exp...
File src/pkg/exp/types/staging/exprstring.go (right):

http://codereview.appspot.com/6490089/diff/7001/src/pkg/exp/types/staging/exp...
src/pkg/exp/types/staging/exprstring.go:86: case *ast.BinaryExpr:
On 2012/09/07 14:59:17, adonovan wrote:
> Is this output function intended for eyes only, or as input to a parser?  If
so
> you'll need to insert parens to disambiguate.  To do this optimally is a
> function of the fixity, associativity and predecence of all your binary
> operators; see Norman Ramsey (1998) "Unparsing Expressions with Prefix and
> Postfix Operators".  [NB, there's a bug in that paper but Go's AST shouldn't
hit
> it.] 

This is for human eyes only - to provide nicer error messages. But independent
of that, the Go AST preserves original parentheses because the printer must
faithfully reproduce the original source code. Thus this function will do the
same (see ast.ParenExpr) and thus produce correct output if the input was
correct.

Thanks for the hint to the paper, though. I always re-invent the algorithm when
I need it.

[gri, 2012-09-07 20:01:43]

Hello rsc@golang.org, adonovan@google.com (cc: golang-dev@googlegroups.com),

Please take another look.

[r, 2012-09-07 20:41:13]

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/predicates.go
File src/pkg/exp/types/predicates.go (right):

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/predicates...
src/pkg/exp/types/predicates.go:86: if typ, ok := typ.(*NamedType); ok {
do either of these guys wants fors rather than ifs? or maybe another function
pair like that?

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go
File src/pkg/exp/types/types.go (right):

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:24: // compiles without errors.
the package's source code has no type errors.

don't make claims about the compiler.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:38: func Check(fset *token.FileSet, pkg *ast.Package,
types map[ast.Expr]Type) error {
why do i need fset and pkg? can't i get to fset from pkg? i can certainly get to
the Files.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:147: implementsType
what's this?

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:181: Recover
might want to open a gap here, for future growth

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:186: Sizeof
ditto

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:198: Nargs int // Nargs < 0 indicates variable number
of arguments
i'd prefer an IsVariadic field rather than overload this way.

[gri, 2012-09-08 00:08:03]

PTAL

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/predicates.go
File src/pkg/exp/types/predicates.go (right):

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/predicates...
src/pkg/exp/types/predicates.go:86: if typ, ok := typ.(*NamedType); ok {
On 2012/09/07 20:41:14, r wrote:
> do either of these guys wants fors rather than ifs? or maybe another function
> pair like that?

No. Underlying types are never NamedTypes. Added comments to that effect.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go
File src/pkg/exp/types/types.go (right):

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:24: // compiles without errors.
On 2012/09/07 20:41:14, r wrote:
> the package's source code has no type errors.
> 
> don't make claims about the compiler.

Done.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:38: func Check(fset *token.FileSet, pkg *ast.Package,
types map[ast.Expr]Type) error {
On 2012/09/07 20:41:14, r wrote:
> why do i need fset and pkg? can't i get to fset from pkg? i can certainly get
to
> the Files.

fset is only needed for error position information - like anywhere else. It
would be nice it it were not needed, but that's how the AST is for now.

(I have some ideas to simplify this in the future, but for now this is the
standard way for all tools).

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:147: implementsType
On 2012/09/07 20:41:14, r wrote:
> what's this?

This if for internal use only. Not exported anymore.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:181: Recover
On 2012/09/07 20:41:14, r wrote:
> might want to open a gap here, for future growth

I think people should use the actual constants and than this should be fine.
Do have something else in mind?

But since builtins cannot escape I won't export this anymore.

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:186: Sizeof
On 2012/09/07 20:41:14, r wrote:
> ditto
ACK

http://codereview.appspot.com/6490089/diff/11001/src/pkg/exp/types/types.go#n...
src/pkg/exp/types/types.go:198: Nargs int // Nargs < 0 indicates variable number
of arguments
On 2012/09/07 20:41:14, r wrote:
> i'd prefer an IsVariadic field rather than overload this way.

Changed.

This is internal use only - not exported anymore (Builtins can only be called,
never assigned, so the type becomes never visible outside).

[r, 2012-09-08 00:15:13]

LGTM but let others respond

[rsc, 2012-09-10 17:37:18]

LGTM

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
File src/pkg/exp/types/staging/types.go (right):

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:30: // 3) If a non-nil but non-empty types
map is provided, Check type-
I have minor discomfort about treating len 0 map separately from len > 0 map. It
means if you have a list of things you care about and you do something like

m := make(map[ast.Expr]Type)
for _, thing := range things {
    m[thing] = nil
}

then you get fast behavior except when len(things) == 0. It might be worth
making this a separate function. CheckSubset or something like that.
Like I said, only minor discomfort.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:42: // All types implement the Type
interface.
Is there anything else callers should know about types? Can they be compared
with == ?
Are there other common methods they'll have?

I wonder if all Types should have a few things like Kind() Kind (replacing
BasicKind with a few more things like Struct Func etc) and Info() Info. Just a
suggestion, though. I'm sure you've weighed these before.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:127: Typ         Type
s/Typ/Type/?

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:129: IsAnonymous bool
Make comments clear about whether Name == "" for anonymous.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:150: // A Signature represents a user-defined
function type func(...) (...).
Not a Func?

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:151: // TODO(gri) consider using tuples to
represent parameters and results.
Please don't expose 'tuples'. So many people are confused about whether Go has
tuples already. If the concept must be exposed it would be better as a different
name, like 'List' or 'ReturnList'. But probably ObjList is okay.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/uni...
File src/pkg/exp/types/staging/universe.go (right):

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/uni...
src/pkg/exp/types/staging/universe.go:21: var Typ = [...]*Basic{
s/Typ/BasicType/ ?
Or maybe BasicKind should have a Type() Type method that indexes this (then
unexported) table? Bool.Type() etc.

[rog, 2012-09-10 18:47:47]

On 10 September 2012 18:37,  <rsc@golang.org> wrote:
> LGTM
>
>
>
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> File src/pkg/exp/types/staging/types.go (right):
>
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> src/pkg/exp/types/staging/types.go:30: // 3) If a non-nil but non-empty
> types map is provided, Check type-
> I have minor discomfort about treating len 0 map separately from len > 0
> map. It means if you have a list of things you care about and you do
> something like
>
> m := make(map[ast.Expr]Type)
> for _, thing := range things {
>     m[thing] = nil
> }
>
> then you get fast behavior except when len(things) == 0. It might be
> worth making this a separate function. CheckSubset or something like
> that.
> Like I said, only minor discomfort.
>
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> src/pkg/exp/types/staging/types.go:42: // All types implement the Type
> interface.
> Is there anything else callers should know about types? Can they be
> compared with == ?
> Are there other common methods they'll have?
>
> I wonder if all Types should have a few things like Kind() Kind
> (replacing BasicKind with a few more things like Struct Func etc) and
> Info() Info. Just a suggestion, though. I'm sure you've weighed these
> before.

It occurs to me that people might find this more approachable
if at least some of the API looked similar to the reflect Type API.
That is, each concrete type (still exported) could implement an interface
that looked pretty much the same as reflect.Type.  It could perhaps
even use the same constants for Kind.

Just a thought.

[gri, 2012-09-10 21:39:46]

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
File src/pkg/exp/types/staging/types.go (right):

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:30: // 3) If a non-nil but non-empty types
map is provided, Check type-
On 2012/09/10 17:37:18, rsc wrote:
> I have minor discomfort about treating len 0 map separately from len > 0 map.
It
> means if you have a list of things you care about and you do something like
> 
> m := make(map[ast.Expr]Type)
> for _, thing := range things {
>     m[thing] = nil
> }
> 
> then you get fast behavior except when len(things) == 0. It might be worth
> making this a separate function. CheckSubset or something like that.
> Like I said, only minor discomfort.
> 

It's a valid concern. CheckSubset/checkPartial was just an idea that I thought
would be quite useful for things like go fix where you only need some of the
information. Leaving it away for now, easy to add, hard to remove once it's
here.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:42: // All types implement the Type
interface.
On 2012/09/10 17:37:19, rsc wrote:
> Is there anything else callers should know about types? Can they be compared
> with == ?
> Are there other common methods they'll have?
> 
> I wonder if all Types should have a few things like Kind() Kind (replacing
> BasicKind with a few more things like Struct Func etc) and Info() Info. Just a
> suggestion, though. I'm sure you've weighed these before.

Probably there should be more. For instance there are predicates isIdentical,
isBoolean, isString, etc. that could be exported and/or made methods of Type.
For now I kept it at the minimum because it's easy to add those things once it
all works (but tedious to maintain before).

Added comment.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:127: Typ         Type
On 2012/09/10 17:37:19, rsc wrote:
> s/Typ/Type/?

I'me using typ for all the non-exported fields, hence Typ in this case.
Changed.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:129: IsAnonymous bool
On 2012/09/10 17:37:19, rsc wrote:
> Make comments clear about whether Name == "" for anonymous.

Done.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:150: // A Signature represents a user-defined
function type func(...) (...).
On 2012/09/10 17:37:19, rsc wrote:
> Not a Func?

I'm considering having a much better type Objects hierarchy, where we'd have
Consts, Vars, Funcs, etc. and then I cannot reuse Func here. Signature seemed
pretty clear. Happy to reconsider if things turn out differently.

http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
src/pkg/exp/types/staging/types.go:151: // TODO(gri) consider using tuples to
represent parameters and results.
On 2012/09/10 17:37:19, rsc wrote:
> Please don't expose 'tuples'. So many people are confused about whether Go has
> tuples already. If the concept must be exposed it would be better as a
different
> name, like 'List' or 'ReturnList'. But probably ObjList is okay.
> 
> 

ACK. Will change. Added comment for now.

[gri, 2012-09-10 21:53:41]

I think if that is a desirable goal it should be fairly easy to change (or
add) later as it's essentially a thin veneer on top of what's here now.

I've tried an approach where every type is simply a special kind of
concrete Type (no hierarchy), and while that may have some (performance)
advantages it really doesn't use the Go type system very well but instead
relies on run-time panics in case of errors. The current reflection
implementation is the result of several iterations, and one of the driving
concerns there was performance and minimum amount of allocation. Arguably
it would be nicer if each type had its own corresponding Go type (as was
the case in the beginning).

I've been iterating this (too) many times and each approach has pros and
cons. At this point my goal is to get this fully working. Once we're there
we can fine-tune. I agree that having both APIs somewhat similar might be
nice.

- gri



On Mon, Sep 10, 2012 at 11:47 AM, roger peppe <rogpeppe@gmail.com> wrote:

> On 10 September 2012 18:37,  <rsc@golang.org> wrote:
> > LGTM
> >
> >
> >
> >
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> > File src/pkg/exp/types/staging/types.go (right):
> >
> >
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> > src/pkg/exp/types/staging/types.go:30: // 3) If a non-nil but non-empty
> > types map is provided, Check type-
> > I have minor discomfort about treating len 0 map separately from len > 0
> > map. It means if you have a list of things you care about and you do
> > something like
> >
> > m := make(map[ast.Expr]Type)
> > for _, thing := range things {
> >     m[thing] = nil
> > }
> >
> > then you get fast behavior except when len(things) == 0. It might be
> > worth making this a separate function. CheckSubset or something like
> > that.
> > Like I said, only minor discomfort.
> >
> >
>
http://codereview.appspot.com/6490089/diff/1018/src/pkg/exp/types/staging/typ...
> > src/pkg/exp/types/staging/types.go:42: // All types implement the Type
> > interface.
> > Is there anything else callers should know about types? Can they be
> > compared with == ?
> > Are there other common methods they'll have?
> >
> > I wonder if all Types should have a few things like Kind() Kind
> > (replacing BasicKind with a few more things like Struct Func etc) and
> > Info() Info. Just a suggestion, though. I'm sure you've weighed these
> > before.
>
> It occurs to me that people might find this more approachable
> if at least some of the API looked similar to the reflect Type API.
> That is, each concrete type (still exported) could implement an interface
> that looked pretty much the same as reflect.Type.  It could perhaps
> even use the same constants for Kind.
>
> Just a thought.
>

[gri, 2012-09-10 21:54:56]

*** Submitted as http://code.google.com/p/go/source/detail?r=26b1cb07dc52 ***

exp/types/staging: typechecker API

First set of type checker files for review.
The primary concern here is the typechecker
API (types.go).

R=rsc, adonovan, r, rogpeppe
CC=golang-dev
http://codereview.appspot.com/6490089