[m-rev.] for review: detect cycles in typeclass hierarchy

[Mark Brown]

On 19-Jan-2005, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> Mark Brown, Wednesday, 19 January 2005:
> > Index: compiler/check_typeclass.m
> > +
> > +:- pred check_for_cyclic_classes(class_table::in, bool::out, io::di, io::uo)
> > +	is det.
> > +
> > +check_for_cyclic_classes(ClassTable, Errors, !IO) :-
> > +	ClassIds = map__keys(ClassTable),
> > +	foldl2(find_cycles(ClassTable, []), ClassIds, set.init, _, [], Cycles),
> 
> You might want to consider using map__foldl2 to avoid constructing the
> list of keys.

I didn't think of that.  It turns out not to work very easily, though, since
the recursive call to find_cycles is a foldl over a list.  Making two
versions of find_cycles, one for map and one for list, is probably not
worth it due to the added complexity of the code.

> 
> > +	(
> > +		Cycles = [],
> > +		Errors = no
> > +	;
> > +		Cycles = [_ | _],
> > +		Errors = yes,
> > +		foldl(report_cyclic_classes(ClassTable), Cycles, !IO)
> > +	).
> > +
> > +:- type class_path == list(class_id).
> > +
> > +	% find_cycles(ClassTable, Path, ClassId, !Visited, !Cycles)
> > +	%
> > +	% Perform a depth first traversal of the class hierarchy, starting
> > +	% from ClassId.  Path contains a list of nodes joining the current
> > +	% node to the root.  When we reach a node that has already been
> > +	% visited, check whether there is a cycle in the Path.
> > +	%
> > +:- pred find_cycles(class_table::in, class_path::in, class_id::in,
> > +	set(class_id)::in, set(class_id)::out,
> > +	list(class_path)::in, list(class_path)::out) is det.
> > +
> > +find_cycles(ClassTable, Path, ClassId, !Visited, !Cycles) :-
> > +	(
> > +		set.member(ClassId, !.Visited)
> > +	->
> > +		(
> > +			find_cycle(ClassId, Path, [ClassId], Cycle)
> > +		->
> > +			!:Cycles = [Cycle | !.Cycles]
> > +		;
> > +			true
> > +		)
> > +	;
> > +		svset.insert(ClassId, !Visited),
> > +		ClassIds = get_superclass_ids(ClassTable, ClassId),
> > +		foldl2(find_cycles(ClassTable, [ClassId | Path]), ClassIds,
> > +			!Visited, !Cycles)
> > +	).
> 
> When there are so few "state" changes, I usually prefer to just number
> states explicitly rather than use state variable notation.

The problem is not so much number of state changes, but number of paths
through the code.  Using state variables avoids the need to add goals
such as "Cycle = Cycle0" to paths that don't change the state, so in this
case I think it is more readable to use state variables.

> 
> Otherwise, that looks fine.

Okay, I'll commit it soon.

Cheers,
Mark.

--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------