[nem-bug] [Nemerle 0001004]: problem typing recursively-typed values where the type is based on another algebraic type

[feedback at nemerle.org]

A NOTE has been added to this issue.
======================================================================
<http://nemerle.org/bugs/view.php?id=1004> 
======================================================================
Reported By:                biosap
Assigned To:                
======================================================================
Project:                    Nemerle
Issue ID:                   1004
Category:                   Compiler (type engine)
Reproducibility:            always
Severity:                   minor
Priority:                   normal
Status:                     new
======================================================================
Date Submitted:             05-04-2007 22:31 CEST
Last Modified:              05-05-2007 10:24 CEST
======================================================================
Summary:                    problem typing recursively-typed values where the
type is based on another algebraic type
Description: 
Trying to compile the program below, I get these type errors:

coros_problem.n:17:5:22:6: error: expected option[(int * Unit.t ->
coroutine[Unit.t, int])], got option[(int- * ? -> option[(int * Unit.t ->
coroutine[Unit.t, int])]--)-]- in function return value:
Nemerle.Core.option is not a subtype of coroutine [simple require]
coros_problem.n:32:21:32:39: error: expected option[('a.897 * Unit.t ->
coroutine[Unit.t, 'a.897])], got coroutine[Unit.t, 'a.897] in assigned
value: coroutine is not a subtype of Nemerle.Core.option [simple require]
make: *** [build/coros_problem.exe] Error 1

start of code ---->

using System;
using Nemerle.Imperative;

module Unit
{
    public variant t {
        | Instance
    };
    public v : t = t.Instance()
}

type coroutine['a,'b] = option['b*('a->coroutine['a,'b])];
type generator['b] = coroutine[Unit.t,'b];

module CoroutineTest
{
    public range(start:int,stop:int,step:int=1) : generator[int]
    {
        if (start==stop) None()
        else Some((start, (_)=>
                   range(start+1,stop,step)))
    }

    public enumerateGenerator['a](g: generator['a]) :
System.Collections.Generic.IEnumerable['a]
    {
        mutable gen : generator['a] = g;
        while (true) {
            match (gen) {
                | None => break
                | Some((x,more)) => { 
                    yield x;
                    gen = more(Unit.v)
                }
            }
        }
    }

    public printNums() : void
    {
        foreach (x in enumerateGenerator(range(0,10))) {
            System.Console.WriteLine(x)
        }
    }
}

CoroutineTest.printNums()

<---- end of code

start of expected output --->
0
1
2
3
4
5
6
7
8
9
<---- end of expected output

By "inlining" the use of the option datatype, I managed to avoid these
errors, but I think Nemerle would be a slightly better language if one
could use the definition above - because then functions and macros that
work on option['a] would also work on coroutine['b,'c].


======================================================================

----------------------------------------------------------------------
 biosap - 05-04-07 22:35 
----------------------------------------------------------------------
runtime: mono 1.2.3.1
ncc: SVN trunk revision 7626

----------------------------------------------------------------------
 malekith - 05-05-07 10:24 
----------------------------------------------------------------------
I'm kind of surprised it doesn't crash the compiler...

The problem is that type = ... definitions are just aliases, which are
expanded whenever they are seen. And here, with recursive alias, I would
expect infinite expansion.

The easiest way to avoid it, would be to define a variant coroutine:

variant coroutine['a,'b]
{
  | More { b : 'b; f : 'a -> coroutine['a,'b]; }
  | Last { b : 'b }
}

or something like that.

Issue History
Date Modified  Username       Field                    Change              
======================================================================
05-04-07 22:31 biosap         New Issue                                    
05-04-07 22:35 biosap         Note Added: 0001870                          
05-05-07 10:24 malekith       Note Added: 0001872                          
======================================================================