[erlang-questions] A dialyzer question on improper list detection of list appends

[Kostis Sagonas]

Jesper Louis Andersen wrote:
> I have some code which goes like this (in gproc):
> 
> qlc_next(_, '$end_of_table') -> [];
> qlc_next(Scope, K) ->
>     case ets:lookup(?TAB, K) of
>         [{{Key,_}, Pid, V}] ->
>             [{Key,Pid,V} | fun() -> qlc_next(Scope, next(Scope, K)) end];
>         [] ->
>             qlc_next(Scope, next(Scope, K))
>     end.
> 
> The dialyzer does not like it, it reports:
> 
> gproc.erl:1149: Cons will produce an improper list since its 2nd
> argument is fun(() -> maybe_improper_list({_,_,_},fun(() ->
> maybe_improper_list(any(),fun(() -> any()) | [])) | []))
> 
> This is entirely true and the warning is in addition good. Improper
> lists is somewhat of a mistake :) Since this is a problem in general
> with QLCs, and qlc_next/1 I wondered how it was fixed for, say, ETS
> tables in Erlang. In lib/stdlib/src/ets.erl we find:
> 
> qlc_next(_Tab, '$end_of_table') ->
>     [];
> qlc_next(Tab, Key) ->
>     ets:lookup(Tab, Key) ++ fun() -> qlc_next(Tab, ets:next(Tab, Key)) end.
> 
> Hmm, clever! So I change the code from gproc to:
> 
> @@ -1157,7 +1146,7 @@ qlc_next(_, '$end_of_table') -> [];
>  qlc_next(Scope, K) ->
>      case ets:lookup(?TAB, K) of
>          [{{Key,_}, Pid, V}] ->
> -            [{Key,Pid,V} | fun() -> qlc_next(Scope, next(Scope, K)) end];
> +            [{Key,Pid,V}] ++ fun() -> qlc_next(Scope, next(Scope, K)) end;
>          [] ->
>              qlc_next(Scope, next(Scope, K))
>      end.
> @@ -1166,7 +1155,7 @@ qlc_prev(_, '$end_of_table') -> [];
>  qlc_prev(Scope, K) ->
>      case ets:lookup(?TAB, K) of
>          [{{Key,_},Pid,V}] ->
> -            [{Key,Pid,V} | fun() -> qlc_prev(Scope, prev(Scope, K)) end];
> +            [{Key,Pid,V}] ++ fun() -> qlc_prev(Scope, prev(Scope, K)) end;
>          [] ->
>              qlc_prev(Scope, prev(Scope, K))
>      end.
> 
> and magically, the Dialyzer warning disappears. Now the million dollar
> question is: Why? Both are equivalent improper lists, right? Maybe
> Kostis or someone else with dialyzer-fu can shed some light on this?

It's really very very simple.

Pay attention to the fine line of the warning: "Cons will produce ..."
In the ++ case there is no explicit cons involved ;-)

Now, can I have my million dollars? :)

Seriously though, the core of the problem is that you are making an 
assumption which does not hold. You are implicitly assuming that 
dialyzer is a tool which is *sound for correctness*: i.e., capable of 
detecting a complete set of warnings (of a certain kind). It is NOT. 
It's explicitly designed to be a tool which is *sound for defect 
detection*: i.e., it will never give you a false warning but you have no 
guarantee that it will give you all warnings. (Granted of course that in 
this particular case, it's damn easy to special-case ++/2 also, and 
indeed we might do this when and if we feel like it... not likely to 
happen soon though, so you are safe for the time being.)

Cheers,
Kostis