behavior of lists:append/1

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

behavior of lists:append/1

Karlo Kuna
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Michał Muskała
My understanding is that for most functions in the Erlang standard library, if you don't uphold the contract the documentation specifies the function can crash, but it could also return whatever - in short "garbage in, garbage out" applies.

Michał.
On 15 Sep 2019, 18:45 +0100, Karlo Kuna <[hidden email]>, wrote:
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Karlo Kuna
Michal, 
i really prefer crashing than garbage in, garbage out policy. 
also it would be nice if someone from OTP team confirms if stdlib has "garbage in garbage out" policy. i can certainly see benefits of it but in this case fix is easy and small.  

On Sun, Sep 15, 2019 at 7:54 PM Michał Muskała <[hidden email]> wrote:
My understanding is that for most functions in the Erlang standard library, if you don't uphold the contract the documentation specifies the function can crash, but it could also return whatever - in short "garbage in, garbage out" applies.

Michał.
On 15 Sep 2019, 18:45 +0100, Karlo Kuna <[hidden email]>, wrote:
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Dmitry Belyaev-3
Every additional check further reduces performance and some of us are concerned about it.

If you need correctness checks try to use static analysis tools like dialyzer/gradualizer, that way you catch the bug, we don't have reduced performance.

On 16 September 2019 4:02:25 am AEST, Karlo Kuna <[hidden email]> wrote:
Michal, 
i really prefer crashing than garbage in, garbage out policy. 
also it would be nice if someone from OTP team confirms if stdlib has "garbage in garbage out" policy. i can certainly see benefits of it but in this case fix is easy and small.  

On Sun, Sep 15, 2019 at 7:54 PM Michał Muskała <[hidden email]> wrote:
My understanding is that for most functions in the Erlang standard library, if you don't uphold the contract the documentation specifies the function can crash, but it could also return whatever - in short "garbage in, garbage out" applies.

Michał.
On 15 Sep 2019, 18:45 +0100, Karlo Kuna <[hidden email]>, wrote:
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

--
Kind regards,
Dmitry Belyaev
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Richard O'Keefe
In reply to this post by Karlo Kuna
This particular issue goes back nearly 60 years.
Here is the traditional definition of "append", using Erlang syntax.

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append(_,      Ys) -> Ys.

This was tightened up in more recent Lisp systems to the equivalent of

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append([],     Ys) -> Ys.

To this day, if you fire up a Common Lisp REPL, you can get this
* (append '(x) 'y)

(X . Y)
That was CMU Common Lisp 21d.  You get the same in Scheme.
And in Erlang,
1> [a]++b.
[a|b]

The point of this is that you want the cost of (append Xs Ys) to be
O(length(Xs)).  We really really don't want it to be O(length(Xs++Ys)).
Now suppose we did

append([X|Xs], Ys) -> [X | append(Xs, Ys)];
append([],     Ys) when is_list(Ys) -> Ys.

What good would that actually do?  is_list is not well named.
3> is_list([a|b]).
true

So instead of append([a], b) -> [a|b] we would still have
append([], [a|b]) -> [a|b].  The only way to ensure that the result
of append is a well formed list is to check the *entire* spine of the
second argument, and now we have this big cost we really wanted to avoid.

I've been talking about the traditional "append" function.  You were
talking about append/1.  But it's the same thing.  Instead of
append([[a],b]) -> [a|b], we'd still have append([[],[a|b]]) -> [a|b].
Inserting a call to is_list/1 would *only* add overhead without doing
anything practical to address the issue.

Erlang's solution is the type checker.  This is also the solution adopted
by SML, O'CAML, Haskell, Clean, Goedel, Mercury, the DEC-10 Prolog type
checker (originally inspired in part by a desire to prove theorems about
Prolog's append/3 that are not in fact sound without a type checker) and
several other languages in the Lisp family.

On Mon, 16 Sep 2019 at 05:45, Karlo Kuna <[hidden email]> wrote:
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Richard O'Keefe
In reply to this post by Karlo Kuna
Your proposed fix may be easy and small, but it is not a fix.

Why do you suppose append/1 wasn't written *this* way?

app([X|Xs], Ys) -> [X | app(Xs, Ys)];
app([],     Ys) -> Ys.

app([Xs|Xss]) -> app(Xs, app(Xss));
app([])       -> [].

I coded this up, using app instead of append, and got this:

2> app:app([[],[a|b]]).
** exception error: no function clause matching app:app(b,[]) (app.erl, line 4)
     in function  app:app/2 (app.erl, line 4)
     in call from app:app/1 (app.erl, line 7)

That would seem to be what you are after, and it's *simpler* than the
existing code.  So what is the point?

Let L be a well formed list, and consider

   append([[1],[2],...,[N],L])

The fact that L is a well-formed list is verified N times,
for a total cost O(N * |L|).  But with the current definition,
the cost is O(N), independent of |L|.

Oddly enough, there *is* a way to check that a list is well formed
in a guard.  Let's try this.

append([Xs]) when length(Xs) >= 0 -> Xs;
append([Xs|Xss]) -> Xs ++ append(Xss);
append([]) -> [].

This actually *would* be a "fix", and the cost would be
O(N + |L|) instead of O(N * |L|).
But that would make append([Xs,Ys]) inconsistent with
Xs++Ys.

I will say that I've been using languages in the Lisp family for
a little over 40 years, and this has been the very *least* of my
problems.

On Mon, 16 Sep 2019 at 06:02, Karlo Kuna <[hidden email]> wrote:
Michal, 
i really prefer crashing than garbage in, garbage out policy. 
also it would be nice if someone from OTP team confirms if stdlib has "garbage in garbage out" policy. i can certainly see benefits of it but in this case fix is easy and small.  

On Sun, Sep 15, 2019 at 7:54 PM Michał Muskała <[hidden email]> wrote:
My understanding is that for most functions in the Erlang standard library, if you don't uphold the contract the documentation specifies the function can crash, but it could also return whatever - in short "garbage in, garbage out" applies.

Michał.
On 15 Sep 2019, 18:45 +0100, Karlo Kuna <[hidden email]>, wrote:
Hello,

i have found surprising  behavior of function lists:append/1: 

spec and documentation  are in a agreement that this function should accept lists of lists ( [List] ) , 
and return list of T ( [T] ), however when we use function like: 
 
     lists:append([a]) %wrong input parameter 
one gets: 
     a  % wrong type of a return 

implementation assumes correct type: 

append([E]) -> E; % E is not checked for type 
append([H|T]) -> H ++ append(T);
append([]) -> [].

simple solution could be: 

lists:append([E]) when is_list(E) -> E 

am i missing something? 

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Lukas Larsson-8
In reply to this post by Karlo Kuna

On Sun, Sep 15, 2019 at 8:02 PM Karlo Kuna <[hidden email]> wrote:
Michal, 
i really prefer crashing than garbage in, garbage out policy.  
also it would be nice if someone from OTP team confirms if stdlib has "garbage in garbage out" policy. i can certainly see benefits of it but in this case fix is easy and small.  

It is impossible to guard against every possible faulty input, so yes, we do have "a garbage in, garbage out policy". However, we do try to guide the user to write correct code where possible without losing too much performance. Where to draw the line of what "too much performance" means is a constant debate as shown by the other answers to your question.

Lukas

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Mikael Pettersson-5
On Mon, Sep 16, 2019 at 9:54 AM Lukas Larsson <[hidden email]> wrote:

>
>
> On Sun, Sep 15, 2019 at 8:02 PM Karlo Kuna <[hidden email]> wrote:
>>
>> Michal,
>> i really prefer crashing than garbage in, garbage out policy.
>>
>> also it would be nice if someone from OTP team confirms if stdlib has "garbage in garbage out" policy. i can certainly see benefits of it but in this case fix is easy and small.
>
>
> It is impossible to guard against every possible faulty input, so yes, we do have "a garbage in, garbage out policy". However, we do try to guide the user to write correct code where possible without losing too much performance. Where to draw the line of what "too much performance" means is a constant debate as shown by the other answers to your question.

The bottom line, if I may draw on ROK's comment, is that runtime type
checking adds a measurable cost, generally O(size of term), in
dynamically typed languages.  Adding such a check when not necessary
for the actual operation in question would be a performance bug, and
could easily even raise the asymptotic complexity of the code
involved.  That's why dynamically typed languages generally do not do
any more type checking that absolutely necessary.
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Kostis Sagonas-2
In reply to this post by Lukas Larsson-8
On 9/16/19 9:54 AM, Lukas Larsson wrote:

>
> On Sun, Sep 15, 2019 at 8:02 PM Karlo Kuna <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Michal,
>     i really prefer crashing than garbage in, garbage out policy.
>
>     also it would be nice if someone from OTP team confirms if stdlib
>     has "garbage in garbage out" policy. i can certainly see benefits of
>     it but in this case fix is easy and small.
>
>
> It is impossible to guard against every possible faulty input, ...

Although I agree with the rest of Lukas' answer, "impossible" is too
strong a word here; we are not talking about an undecidable problem
after all.

I think that "undesirable", "costly", etc. would have been a better
choice in this context.

Kostis
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
In reply to this post by Richard O'Keefe
On 2019/09/16 11:49, Richard O'Keefe wrote:
> The fact that L is a well-formed list is verified N times,
> for a total cost O(N * |L|).  But with the current definition,
> the cost is O(N), independent of |L|.

Hm... just to beat a dead horse...I suppose we could get away with a
single check:

   -export([append/2]).

   append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).

   combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
   combine([],       Ys) -> Ys.

> I will say that I've been using languages in the Lisp family for
> a little over 40 years, and this has been the very *least* of my
> problems.

The whole issue boils down to the above. I can see some trivial merit in
doing a type check over Ys at the outset (since we'll crash on bad Xs in
the actual procedure) but this business of moving to the last element to
check whether the list is properly formed is both insane and almost
certainly a legacy code killer, as there are a handful of systems out
there that depend on being able to manipulate improper lists for
whatever reason.

I didn't follow this thread closely, but I'm surprised I didn't see
doing a single type check on entry as a possibility. What issues would
make this a bad idea?

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
by
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

by
Well, if we can put the type check on entry, we can put the type check before we call this function :-)

Yao

> 在 2019年9月16日,21:53,zxq9 <[hidden email]> 写道:
>
> On 2019/09/16 11:49, Richard O'Keefe wrote:
>> The fact that L is a well-formed list is verified N times,
>> for a total cost O(N * |L|).  But with the current definition,
>> the cost is O(N), independent of |L|.
>
> Hm... just to beat a dead horse...I suppose we could get away with a single check:
>
>  -export([append/2]).
>
>  append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).
>
>  combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
>  combine([],       Ys) -> Ys.
>
>> I will say that I've been using languages in the Lisp family for
>> a little over 40 years, and this has been the very *least* of my
>> problems.
>
> The whole issue boils down to the above. I can see some trivial merit in doing a type check over Ys at the outset (since we'll crash on bad Xs in the actual procedure) but this business of moving to the last element to check whether the list is properly formed is both insane and almost certainly a legacy code killer, as there are a handful of systems out there that depend on being able to manipulate improper lists for whatever reason.
>
> I didn't follow this thread closely, but I'm surprised I didn't see doing a single type check on entry as a possibility. What issues would make this a bad idea?
>
> -Craig
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions
>

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Pierpaolo Bernardi
In reply to this post by Karlo Kuna

Il giorno 16 settembre 2019, alle ore 15:54, zxq9 <[hidden email]> ha scritto:

>I didn't follow this thread closely, but I'm surprised I didn't see
>doing a single type check on entry as a possibility. What issues would
>make this a bad idea?

Only that you add a linear factor to every use of append.

Many linear algorithms would became quadratic, etc etc


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Richard O'Keefe
In reply to this post by zxq9-2
Briefly, the problem with
append(Xs, Ys) when is_list(Ys) ->
    combine(Xs, Ys).
is that is_list/1 ***ISN'T A TYPE CHECK FOR LISTS***.
It is misnamed.
is_list([_|_]) -> true;
is_list([])    -> true;
is_list(_)     -> false.
Try is_list([a|b]).
The result is true, despite [a|b] not being a list.
Unsurprisingly, (LISTP '()) and (LISTP '(1 . 2)) are
true in Common Lisp.   There is an interesting
difference between Common Lisp and Scheme:
(list? '(1 . 2)) is false in Scheme.  But the
Scheme function takes O(|list|) time.

Oddly enough, since Erlang is strict and functional,
it *would* be possible for Erlang to tag pairs whose
tail is a proper list differently from pairs whose
tail is *not* a proper list, with small constant
overhead.  *That* is what it would take to have an
affordable is_really_a_well_formed_list/1.


On Tue, 17 Sep 2019 at 01:54, zxq9 <[hidden email]> wrote:
On 2019/09/16 11:49, Richard O'Keefe wrote:
> The fact that L is a well-formed list is verified N times,
> for a total cost O(N * |L|).  But with the current definition,
> the cost is O(N), independent of |L|.

Hm... just to beat a dead horse...I suppose we could get away with a
single check:

   -export([append/2]).

   append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).

   combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
   combine([],       Ys) -> Ys.

> I will say that I've been using languages in the Lisp family for
> a little over 40 years, and this has been the very *least* of my
> problems.

The whole issue boils down to the above. I can see some trivial merit in
doing a type check over Ys at the outset (since we'll crash on bad Xs in
the actual procedure) but this business of moving to the last element to
check whether the list is properly formed is both insane and almost
certainly a legacy code killer, as there are a handful of systems out
there that depend on being able to manipulate improper lists for
whatever reason.

I didn't follow this thread closely, but I'm surprised I didn't see
doing a single type check on entry as a possibility. What issues would
make this a bad idea?

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Raimo Niskanen-11
In reply to this post by zxq9-2
On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:

> On 2019/09/16 11:49, Richard O'Keefe wrote:
> > The fact that L is a well-formed list is verified N times,
> > for a total cost O(N * |L|).  But with the current definition,
> > the cost is O(N), independent of |L|.
>
> Hm... just to beat a dead horse...I suppose we could get away with a
> single check:
>
>    -export([append/2]).
>
>    append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).
>
>    combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
>    combine([],       Ys) -> Ys.

No.

lists:append/2 can be used and *is* used by existing code to construct
improper lists.  It would break backwards compatibility.
--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
On 2019/09/17 22:13, Raimo Niskanen wrote:

> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
>> On 2019/09/16 11:49, Richard O'Keefe wrote:
>>> The fact that L is a well-formed list is verified N times,
>>> for a total cost O(N * |L|).  But with the current definition,
>>> the cost is O(N), independent of |L|.
>>
>> Hm... just to beat a dead horse...I suppose we could get away with a
>> single check:
>>
>>     -export([append/2]).
>>
>>     append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).
>>
>>     combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
>>     combine([],       Ys) -> Ys.
>
> No.
>
> lists:append/2 can be used and *is* used by existing code to construct
> improper lists.  It would break backwards compatibility.

The accept/2 -> combine/2 combination accepts improper lists just fine.
That was the whole point and I addressed the detail of actually
*needing* to accept improper lists for the sake of legacy code. It only
checks whether the 'Ys' is a list *at all* before proceeding.

The beaten horse is now absolutely craven for some abuse.

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Raimo Niskanen-11
On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:

> On 2019/09/17 22:13, Raimo Niskanen wrote:
> > On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
> >> On 2019/09/16 11:49, Richard O'Keefe wrote:
> >>> The fact that L is a well-formed list is verified N times,
> >>> for a total cost O(N * |L|).  But with the current definition,
> >>> the cost is O(N), independent of |L|.
> >>
> >> Hm... just to beat a dead horse...I suppose we could get away with a
> >> single check:
> >>
> >>     -export([append/2]).
> >>
> >>     append(Xs, Ys) when is_list(Ys) -> combine(Xs,Ys).
> >>
> >>     combine([X | Xs], Ys) -> [X | combine(Xs, Ys)];
> >>     combine([],       Ys) -> Ys.
> >
> > No.
> >
> > lists:append/2 can be used and *is* used by existing code to construct
> > improper lists.  It would break backwards compatibility.

...to construct improper lists even as in appending a tail element (that is
need not be a list) to a list...

>
> The accept/2 -> combine/2 combination accepts improper lists just fine.
> That was the whole point and I addressed the detail of actually
> *needing* to accept improper lists for the sake of legacy code. It only
> checks whether the 'Ys' is a list *at all* before proceeding.
>
> The beaten horse is now absolutely craven for some abuse.
>
> -Craig
> _______________________________________________
> erlang-questions mailing list
> [hidden email]
> http://erlang.org/mailman/listinfo/erlang-questions

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
On 2019/09/18 21:00, Raimo Niskanen wrote:

> On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:
>> On 2019/09/17 22:13, Raimo Niskanen wrote:
>>> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
>>> No.
>>>
>>> lists:append/2 can be used and *is* used by existing code to construct
>>> improper lists.  It would break backwards compatibility.
>
> ...to construct improper lists even as in appending a tail element (that is
> need not be a list) to a list...

At least here we can put down a line and say "that's a violation of the
typespec", because it is:
http://erlang.org/doc/man/lists.html#append-2

So if we want to continue to use append/2 to *create* improper lists
(which I've never once encountered anywhere in the last decade, but
maybe you've got some examples of super wizard code where this is
necessary?) then the typespec should be changed, otherwise I think it
isn't unreasonable to do at +O(1) cost at runtime what Dialyzer would
do, or just leave things as they are and actively discourage deliberate
construction of improper lists via append/2.

I'm not particularly opposed to changing the typespec to say "List2 can
be whatever because who cares whether lists are lists or not? Let's
ditch type sanity because a handful of people feel like it! WOOO!" but I
*do* believe it is inconsistent to the extreme to say "Well, we're going
to have Dialyzer (and all users who read the documentation... har har
har! Joke's on them!) believe that both arguments must be lists!" and
then in unofficial -- but heavily referenced -- discussion have an OTP
developer say "well, append/2 is used by some people to deliberately
construct improper lists, so let's just ignore the discussion entirely
even though there is actually a way to efficiently check this at runtime".

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Richard O'Keefe
I'm sorry, but what O(1) runtime check are we talking about here?
I don't know of any O(1) way to test "is this a proper list" in
Erlang.

A little bit of history here.
Erlang has roots in Strand88 which has roots in Prolog which (in its
current form) is an "Edinburgh" language which has roots in Pop-2 and
Lisp.

In Prolog, you can construct a term [H|T] before you know what H and/or
T are.  Indeed, [1,2,...,1000000|T] is possible.  When eventually T is
bound, the runtime system has no way of telling that it is used as the
final tail of an incomplete list.

In Lisp, (cons H T) must know what H and T are.  So
   (set! X (cons 1 (cons 2 (cons 3 nil))))
   (list? X)
is possible.  But it's pretty much useless, because
the fact that X is a list *now* doesn't mean it will *always*
be a list.  Things like
   (set-cdr! X 42)
are possible, as indeed are things like
   (set-cdr! X X)
I used Scheme syntax here because Scheme has list? and Lisp doesn't.

Pop-2, the rival language where Edinburgh Prolog was developed,
is an interesting case.  It's a strict imperative language that also
has lazy lists.  So
function islist x;
   if x.ispair then
      x.back -> x;
      x.ispair or x = nil or x.isfunc
   else
      x = nil
   close
end;
takes O(1) time, recognises cons(1,[]) as a list, rejects cons(1,2),
but given what *might* be a lazy list guesses that it is, rather than
expand what might well be an infinite sequence.  Thanks to lazy
lists, x.islist might be true *now*, but after evaluating it one
step, it might be false quite soon.

So in the 1960s and 1970s, programmers using Lisp, Pop-2, and Prolog
got used to the idea that "is this a well-formed list" was somewhere
between impossible to implement, usable only at the instant of testing,
or dangerously expensive.  Lisp and Pop-2 settled on having LISTP or
islist tests that are fast but unreliable.  Prolog settled on using
pattern matching.  And Erlang followed Lisp.

Returning now to Erlang.
Historically, just like Lisp, Pop-2, and Prolog,
Erlang uses the *same* data type for arbitrary pairs and for
nodes in a list.  [1|2] is legal Erlang data.

This means that we can do

fakeout(0) -> 0;
fakeout(N) -> [N | fakeout(N-1)].

...
   [a,b] ++ fakeout(1000000)

Because Erlang
 * uses only strict evaluation, so all data are known in full
 * does not allow data to be changed
it _would_ be possible to change the data representation used
by Erlang to distinguish between
 - a pair whose tl is a proper list
 - a pair whose tl is not a proper list.
This would allow an "is_proper_list/1" test that is not only
constant time but fast, at the price of slowing down every
constructive use of [H|T].

Now no-one who is unwilling to make a speed-for-safety tradeoff
would be using Erlang in the first place.  So the community may
well decide that this major overhaul to BEAm is worth while.

But until such a change is made, there is no O(1) test that we
can use in (++) that will guarantee the result is well formed.

Now I am a bear of very little brain, and I haven't been getting
as much sleep as I should lately, so it would be the very reverse
of surprising if I was wrong about this.  But if I am, it would
be very much appreciated if people saying that we should use an
O(1) test in appending would actually say what test they are
talking about.  (Hint: is_list/1 is *not* that test.)


On Thu, 19 Sep 2019 at 09:54, zxq9 <[hidden email]> wrote:
On 2019/09/18 21:00, Raimo Niskanen wrote:
> On Tue, Sep 17, 2019 at 11:25:11PM +0900, zxq9 wrote:
>> On 2019/09/17 22:13, Raimo Niskanen wrote:
>>> On Mon, Sep 16, 2019 at 10:53:57PM +0900, zxq9 wrote:
>>> No.
>>>
>>> lists:append/2 can be used and *is* used by existing code to construct
>>> improper lists.  It would break backwards compatibility.
>
> ...to construct improper lists even as in appending a tail element (that is
> need not be a list) to a list...

At least here we can put down a line and say "that's a violation of the
typespec", because it is:
http://erlang.org/doc/man/lists.html#append-2

So if we want to continue to use append/2 to *create* improper lists
(which I've never once encountered anywhere in the last decade, but
maybe you've got some examples of super wizard code where this is
necessary?) then the typespec should be changed, otherwise I think it
isn't unreasonable to do at +O(1) cost at runtime what Dialyzer would
do, or just leave things as they are and actively discourage deliberate
construction of improper lists via append/2.

I'm not particularly opposed to changing the typespec to say "List2 can
be whatever because who cares whether lists are lists or not? Let's
ditch type sanity because a handful of people feel like it! WOOO!" but I
*do* believe it is inconsistent to the extreme to say "Well, we're going
to have Dialyzer (and all users who read the documentation... har har
har! Joke's on them!) believe that both arguments must be lists!" and
then in unofficial -- but heavily referenced -- discussion have an OTP
developer say "well, append/2 is used by some people to deliberately
construct improper lists, so let's just ignore the discussion entirely
even though there is actually a way to efficiently check this at runtime".

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

zxq9-2
On 2019/09/19 10:33, Richard O'Keefe wrote:
> I'm sorry, but what O(1) runtime check are we talking about here?
> I don't know of any O(1) way to test "is this a proper list" in
> Erlang.

Not checking for whether something is a properly formed list (the whole
objection some have is that append/2 should be able to accept an
improper list as the second argument) but merely checking whether the
second argument is a list of any form at all.

A single is_list/1 check guarding the leading clause can do that.

The discussion has gone through:

A1: "The typespec says both arguments must be lists"
B1: "Use Dialyzer"

A2: "The check should be dynamic at runtime"
B2: "Checking for *proper* lists is too much overhead"

A3: "We should accept improper lists as a second argument"
B3: "Then is_list/2 could check the 2nd arg on entry only"

A4: "Some people use append/2 to *construct* improper lists"
B4: "Then why do we even have a typespec at all?"

My position is that B2 and A3 are valid, and B3 is a reasonable
compromise that shouldn't break legacy code. I think A4 is unreasonably
inconsistent, though, and would wonder why we're even going to have a
typespec.

-Craig
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: behavior of lists:append/1

Richard O'Keefe
"Not checking for whether something is a properly formed list (the whole
objection some have is that append/2 should be able to accept an
improper list as the second argument) but merely checking whether the
second argument is a list of any form at all."

But what the heck is the point of *that*?
Why is it important for  [a] ++ c to fail
but OK for [a] ++ [b|c] to succeed?
I'm sorry, but that makes no sense to me at all.




On Thu, 19 Sep 2019 at 18:58, zxq9 <[hidden email]> wrote:
On 2019/09/19 10:33, Richard O'Keefe wrote:
> I'm sorry, but what O(1) runtime check are we talking about here?
> I don't know of any O(1) way to test "is this a proper list" in
> Erlang.

Not checking for whether something is a properly formed list (the whole
objection some have is that append/2 should be able to accept an
improper list as the second argument) but merely checking whether the
second argument is a list of any form at all.

A single is_list/1 check guarding the leading clause can do that.

The discussion has gone through:

A1: "The typespec says both arguments must be lists"
B1: "Use Dialyzer"

A2: "The check should be dynamic at runtime"
B2: "Checking for *proper* lists is too much overhead"

A3: "We should accept improper lists as a second argument"
B3: "Then is_list/2 could check the 2nd arg on entry only"

A4: "Some people use append/2 to *construct* improper lists"
B4: "Then why do we even have a typespec at all?"

My position is that B2 and A3 are valid, and B3 is a reasonable
compromise that shouldn't break legacy code. I think A4 is unreasonably
inconsistent, though, and would wonder why we're even going to have a
typespec.

-Craig

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
12