New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
What is the semantics of improper lists anyway? #110
Comments
I think of it this way: A singly-linked list is a list of Cons Cells. A Cons cell is just a 2-tuple, thus The empty list is it's own type known as So pretending a Cons Cell is just a 2-tuple (which it really is), let's use tuple syntax, so a list of A list on the BEAM is just a Cons cell, where a proper list is a Cons cell of the type So for any thinking about improper lists, just pretend an improper list is a 2-tuple where the second element is 'usually' an improper list but can be anything. |
Do note, that means that |
This is overly simplistic. My question is about
It's certainly tempting to introduce a |
The typing rule for an improper list is quite literally
In language it is mostly syntax sugar on top of the Cons cell syntax though, |
Where are you getting this from? There is no official type system for Erlang, only the type language that we are currently discussing. The documentation states that
So, you are saying that The question here isn't about the Erlang term representation of lists (which I think we're all familiar with), but about how to interpret the types for improper lists. Both semantically (what is the set of Erlang values belonging to the type |
My interpretation: The "maybe" is referring to the improperness. Thus, for the maybe_improper list types, the list may also be proper.
Terminology:
There is no possibly-empty -type maybe_improper_list(A, B) :: [] | nonempty_maybe_improper_list(A, B).
-type nonempty_maybe_improper_list(A, B) :: cons(A, B | maybe_improper_list(A, B)).
-type nonempty_improper_list(A, B) :: cons(A, B | nonempty_improper_list(A, B)). |
I have a few arguments against the "maybe" meaning it can be
Neither are of course very strong arguments. Trying to divine some deeper meaning in the type language docs can be quite futile, and dialyzer would rather no one used improper lists at all. I would lean towards picking a semantics that doesn't clash too badly with people's expectations and making it the official interpretation. I would not be violently opposed to the interpretation you gave. Note that you only need -type maybe_improper_list(A, B) :: [] | nonempty_maybe_improper_list(A, B).
-type nonempty_maybe_improper_list(A, B) :: non_empty_improper_list(A, [] | B).
-type nonempty_improper_list(A, B) :: cons(A, B | nonempty_improper_list(A, B)). |
Tradition from other languages. I know Erlang doesn't have an official typing system so I have to relate to others. :-)
Ah is it not allowed to be empty? It's not clear based on the name alone.
Yep, I'm primarily focusing on the semantics mostly related to the ML style languages (as erlang is very conceptually close to).
Makes sense then, so no
I'd agree here. It would be nice if Erlang were explicit about its types, but untyped languages tend to be rather ill-defined so it's expected.
Good point. |
thanks, Ulf, for starting this thread to clarify this hazy topic. I also only had gut feelings about "maybe" referring to properness, as Viktor described. |
Thanks for an amazingly well-written breakdown, Ulf! I think your arguments for the YesNo interpretation are quite compelling. Personally, I've always assumed the YesYes interpretation that Victor is arguing for. I think it would be fairly safe to use an interpretation which is more lenient than Dialyzer, i.e. YesNo or YesYes. (I'm not even going to consider NoYes as an alternative.) We wouldn't introduce any new kinds of error that people haven't encountered before. The flip side is that we wouldn't be able to catch certain errors but given that the waters are so muddy here it seems to me that it would be better to lean towards leniency. So I'm currently in favor of YesYes with YesNo being a reasonable alternative. |
I agree, very good summary of docs and dialyzer behaviour Ulf!
I'm was actually arguing for NoYes. That's what I intended anyway. That is, In the docs, we have maybe_improper_list() :: maybe_improper_list(any(), any()). Assuming
Yes, that's an indication of YesNo, although it could have been included just for clarity. A counter-indication is that %% For reference
-type iodata() :: binary() | iolist().
-type iolist() :: maybe_improper_list(byte() | binary() | iolist(), binary() | [])`. @josefs, may I ask why you don't want to consider NoYes as an alternative? Why is there no type called just |
To me NoYes feels nonsensical. What is the purpose of the second type parameter to |
Aha, I understand how you are thinking. The purpose of the second parameter is to be the type of the "terminator". I guess you could consider |
Ok, I think I see what you mean now :-) Yes, I still disagree with this standpoint because we also have the type |
Under NoYes I'm warming up to NoYes. The mathematician in me still prefers the elegance of YesNo, but I find the |
Yes, exactly. Regarding -type nonempty_maybe_improper_list (a, b) :: nonempty_improper_list(a, b) | nonempty_list(a). |
More evidence...
|
Well just as note, ((x) & (_TAG_PRIMARY_MASK-TAG_PRIMARY_LIST)) So all it checks is that the element directly passed in is of list type (proper or improper), which is essentially just a C array where the first N-1 elements is the list elements and the last is the tail element (which is |
[off topic] @OvermindDL1 It seems what you have found is the |
@zuiderkwast fwiw I don't find |
The question is how we should come to a decision on this issue. Given that the documentation is unclear and the existing tools don't agree with the documentation means that we'll just have to take our own stance. In order to move forward I'd like to gather everyones opinion and see if we can find some common ground. |
I support NoYes. (I base this intuition on the definitions of iolist and iodata - which I think are the most used and very widely used maybe-improper lists - and the existing list type variant names, as summarised in a table by @zuiderkwast ) |
I think a consensus would be nice, rather than a fast decision. Of course we can take a preliminary decision if we want to, but there is no hurry to implement the improper stuff IMO. I suggest we contact Kostis and Tobias who wrote the page about Types and their syntax. The text is taken almost unchanged from EEP8: http://erlang.org/eeps/eep-0008.html . Perhaps they have an idea of what "one would expect" means. We can also check with the community in erlang-questions. Meanwhile, I suggest we focus on implementing other features for the beta release. I have the impression that most of the remaining stuff is strait-forward. Pattern matching on maps for example. Self-gradualizing reveals quite some bugs (e.g. tuples not matching |
Of course |
Were Kostis and Tobias contacted? |
I suppose this is more of an Erlang Questions kind of topic, but I'm afraid I would get five people with incompatible answers each claiming that theirs is the obvious answer. Also, we have the opportunity to decide what the interpretation of improper lists should be, since dialyzer will complain as soon as you use them at all.
My interpretation
Anyway, this got triggered by a discussion in #109, where I realised I'm not actually sure of what the improper-lists types really mean. I always thought they meant this:
In other words, the type
maybe_improper_list(a, b)
has elementsand
nonempty_improper_list(a, b)
would be the same except withoutb
. We would also have[a] == maybe_improper_list(a, [])
and[a, ...] == nonempty_improper_list(a, [])
.This isn't the only possible interpretation though. I guess the two key questions are (but see Dialyzer below for more subtleties):
b :: maybe_improper_list(a, b)
?[] :: maybe_improper_list(a, b)
?which I have down as a Yes and a No, respectively (henceforth referred to as the YesNo position).
The documentation
Let's see what the documentation says:
That's not very specific but seems to suggest a No on the second question. This is further reinforced by the definition of
iolist
which explicitly lists[]
as a possible terminator:Then there's this gem:
Ah, yes. The terms one would expect. Thanks. 🙄
I guess we can put the docs in the
MehNo
camp.Dialyzer
So, what does dialyzer think?
So that's a NoNo.
Does that make
maybe_improper_list
andnon_empty_improper_list
the same? Not quite:This seems to be implemented as a special case for
[]
though becauseIt looks like dialyzer's definition is something like
Gradualizer
Gradualizer currently takes the safe approach and doesn't admit any closed values of improper list types, failing all the improper lists above.
Conclusion
We should implement something for improper lists. I'd argue that the YesNo position is the sensible one (it's certainly the easiest to write down), but the fact that dialyzer does something different makes it less obviously the right thing to do.
The text was updated successfully, but these errors were encountered: