<div dir="ltr"><div class="gmail_default" style="font-family:monospace,monospace">I'm sorry, but what O(1) runtime check are we talking about here?</div><div class="gmail_default" style="font-family:monospace,monospace">I don't know of any O(1) way to test "is this a proper list" in</div><div class="gmail_default" style="font-family:monospace,monospace">Erlang.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">A little bit of history here.</div><div class="gmail_default" style="font-family:monospace,monospace">Erlang has roots in Strand88 which has roots in Prolog which (in its</div><div class="gmail_default" style="font-family:monospace,monospace">current form) is an "Edinburgh" language which has roots in Pop-2 and</div><div class="gmail_default" style="font-family:monospace,monospace">Lisp.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">In Prolog, you can construct a term [H|T] before you know what H and/or</div><div class="gmail_default" style="font-family:monospace,monospace">T are.  Indeed, [1,2,...,1000000|T] is possible.  When eventually T is</div><div class="gmail_default" style="font-family:monospace,monospace">bound, the runtime system has no way of telling that it is used as the</div><div class="gmail_default" style="font-family:monospace,monospace">final tail of an incomplete list.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">In Lisp, (cons H T) must know what H and T are.  So</div><div class="gmail_default" style="font-family:monospace,monospace">   (set! X (cons 1 (cons 2 (cons 3 nil))))</div><div class="gmail_default" style="font-family:monospace,monospace">   (list? X)</div><div class="gmail_default" style="font-family:monospace,monospace">is possible.  But it's pretty much useless, because</div><div class="gmail_default" style="font-family:monospace,monospace">the fact that X is a list *now* doesn't mean it will *always*</div><div class="gmail_default" style="font-family:monospace,monospace">be a list.  Things like</div><div class="gmail_default" style="font-family:monospace,monospace">   (set-cdr! X 42)</div><div class="gmail_default" style="font-family:monospace,monospace">are possible, as indeed are things like</div><div class="gmail_default" style="font-family:monospace,monospace">   (set-cdr! X X)</div><div class="gmail_default" style="font-family:monospace,monospace">I used Scheme syntax here because Scheme has list? and Lisp doesn't.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Pop-2, the rival language where Edinburgh Prolog was developed,</div><div class="gmail_default" style="font-family:monospace,monospace">is an interesting case.  It's a strict imperative language that also</div><div class="gmail_default" style="font-family:monospace,monospace">has lazy lists.  So <br></div><div class="gmail_default" style="font-family:monospace,monospace">function islist x;<br>   if x.ispair then<br>      x.back -> x;<br>      x.ispair or x = nil or x.isfunc<br>   else<br>      x = nil<br>   close<br>end;<br></div><div class="gmail_default" style="font-family:monospace,monospace">takes O(1) time, recognises cons(1,[]) as a list, rejects cons(1,2),</div><div class="gmail_default" style="font-family:monospace,monospace">but given what *might* be a lazy list guesses that it is, rather than</div><div class="gmail_default" style="font-family:monospace,monospace">expand what might well be an infinite sequence.  Thanks to lazy</div><div class="gmail_default" style="font-family:monospace,monospace">lists, x.islist might be true *now*, but after evaluating it one</div><div class="gmail_default" style="font-family:monospace,monospace">step, it might be false quite soon.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">So in the 1960s and 1970s, programmers using Lisp, Pop-2, and Prolog</div><div class="gmail_default" style="font-family:monospace,monospace">got used to the idea that "is this a well-formed list" was somewhere</div><div class="gmail_default" style="font-family:monospace,monospace">between impossible to implement, usable only at the instant of testing,</div><div class="gmail_default" style="font-family:monospace,monospace">or dangerously expensive.  Lisp and Pop-2 settled on having LISTP or</div><div class="gmail_default" style="font-family:monospace,monospace">islist tests that are fast but unreliable.  Prolog settled on using</div><div class="gmail_default" style="font-family:monospace,monospace">pattern matching.  And Erlang followed Lisp.<br></div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Returning now to Erlang.</div><div class="gmail_default" style="font-family:monospace,monospace">Historically, just like Lisp, Pop-2, and Prolog,</div><div class="gmail_default" style="font-family:monospace,monospace">Erlang uses the *same* data type for arbitrary pairs and for</div><div class="gmail_default" style="font-family:monospace,monospace">nodes in a list.  [1|2] is legal Erlang data.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">This means that we can do</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">fakeout(0) -> 0;</div><div class="gmail_default" style="font-family:monospace,monospace">fakeout(N) -> [N | fakeout(N-1)].</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">...</div><div class="gmail_default" style="font-family:monospace,monospace">   [a,b] ++ fakeout(1000000)</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Because Erlang</div><div class="gmail_default" style="font-family:monospace,monospace"> * uses only strict evaluation, so all data are known in full</div><div class="gmail_default" style="font-family:monospace,monospace"> * does not allow data to be changed</div><div class="gmail_default" style="font-family:monospace,monospace">it _would_ be possible to change the data representation used</div><div class="gmail_default" style="font-family:monospace,monospace">by Erlang to distinguish between</div><div class="gmail_default" style="font-family:monospace,monospace"> - a pair whose tl is a proper list</div><div class="gmail_default" style="font-family:monospace,monospace"> - a pair whose tl is not a proper list.</div><div class="gmail_default" style="font-family:monospace,monospace">This would allow an "is_proper_list/1" test that is not only</div><div class="gmail_default" style="font-family:monospace,monospace">constant time but fast, at the price of slowing down every</div><div class="gmail_default" style="font-family:monospace,monospace">constructive use of [H|T].</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Now no-one who is unwilling to make a speed-for-safety tradeoff</div><div class="gmail_default" style="font-family:monospace,monospace">would be using Erlang in the first place.  So the community may</div><div class="gmail_default" style="font-family:monospace,monospace">well decide that this major overhaul to BEAm is worth while.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">But until such a change is made, there is no O(1) test that we</div><div class="gmail_default" style="font-family:monospace,monospace">can use in (++) that will guarantee the result is well formed.</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Now I am a bear of very little brain, and I haven't been getting</div><div class="gmail_default" style="font-family:monospace,monospace">as much sleep as I should lately, so it would be the very reverse</div><div class="gmail_default" style="font-family:monospace,monospace">of surprising if I was wrong about this.  But if I am, it would</div><div class="gmail_default" style="font-family:monospace,monospace">be very much appreciated if people saying that we should use an</div><div class="gmail_default" style="font-family:monospace,monospace">O(1) test in appending would actually say what test they are</div><div class="gmail_default" style="font-family:monospace,monospace">talking about.  (Hint: is_list/1 is *not* that test.)</div><div class="gmail_default" style="font-family:monospace,monospace"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, 19 Sep 2019 at 09:54, zxq9 <<a href="mailto:zxq9@zxq9.com">zxq9@zxq9.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 2019/09/18 21:00, Raimo Niskanen wrote:<br>
> On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:<br>
>> On 2019/09/17 22:13, Raimo Niskanen wrote:<br>
>>> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:<br>
>>> No.<br>
>>><br>
>>> lists:append/2 can be used and *is* used by existing code to construct<br>
>>> improper lists.  It would break backwards compatibility.<br>
> <br>
> ...to construct improper lists even as in appending a tail element (that is<br>
> need not be a list) to a list...<br>
<br>
At least here we can put down a line and say "that's a violation of the <br>
typespec", because it is:<br>
<a href="http://erlang.org/doc/man/lists.html#append-2" rel="noreferrer" target="_blank">http://erlang.org/doc/man/lists.html#append-2</a><br>
<br>
So if we want to continue to use append/2 to *create* improper lists <br>
(which I've never once encountered anywhere in the last decade, but <br>
maybe you've got some examples of super wizard code where this is <br>
necessary?) then the typespec should be changed, otherwise I think it <br>
isn't unreasonable to do at +O(1) cost at runtime what Dialyzer would <br>
do, or just leave things as they are and actively discourage deliberate <br>
construction of improper lists via append/2.<br>
<br>
I'm not particularly opposed to changing the typespec to say "List2 can <br>
be whatever because who cares whether lists are lists or not? Let's <br>
ditch type sanity because a handful of people feel like it! WOOO!" but I <br>
*do* believe it is inconsistent to the extreme to say "Well, we're going <br>
to have Dialyzer (and all users who read the documentation... har har <br>
har! Joke's on them!) believe that both arguments must be lists!" and <br>
then in unofficial -- but heavily referenced -- discussion have an OTP <br>
developer say "well, append/2 is used by some people to deliberately <br>
construct improper lists, so let's just ignore the discussion entirely <br>
even though there is actually a way to efficiently check this at runtime".<br>
<br>
-Craig<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div>