[Fwd: Re: self initializing types and SPECIAL]

[Helmut Brandl]

Sorry, I have sent the response to you personally but not to the mailing
list.

I have to remember to press "reply all" for the FreeELKS mailing list.

Regards
Helmut

-------- Original Message --------
Subject: Re: [freeelks-devel] self initializing types and SPECIAL
Date: Fri, 05 Sep 2008 17:12:42 -0500
From: Helmut Brandl <helmut.brandl@...>
To: Simon Hudon <simon.hudon@...>
References: <48C01BDB.2030206@...>
<94ED6003-1316-489C-A123-1A7DCAF8ABC9@...>
<48C04A51.7060103@...> <48C04FFE.9000002@...>
<EECF8EB8-F5E5-4033-9714-5DD50A7799B8@...>



Simon Hudon wrote:
> Helmut,
>
> As far as I know, it is necessary to define default_create as a
> creation procedure in every expanded classes so the situation you
> mentioned cannot occur.
I don't think so. If I didn't miss anything there is no such requirement
that all expandeds have to be self-initializing. The basic types are all
self initializing.

Such a requirement would put an unecessary restriction on Eiffel. I can
imagine a lot of reasonable cases, where you don't want a type to be
self-initializing. With attached types you get help from the compiler
which will give you a strong message if you failed to initialize an
object properly. Why not have this advantage for expanded types as well.

>
>
> For the second, I can't find precise description of the interactions
> between detachable and expanded semantics and I would think that your
> expression would yield a true since it seems that manipulating an
> expanded object through a reference (e.g. an entity of type
> INTEGER_REF which is assigned an integer) keeps value semantics.  It
> would make sense to assume that, in the context of expanded types, a
> default value plays the role Void plays in the context of reference
> types.
>
> Obviously, Manus or Eric would be more capable or answering the
> particular question.

So let's wait if they do.

Helmut
The Eiffel Compiler: http://www.sourceforge.net/projects/tecomp
Documentation: http://tecomp.sourceforge.net

>
> On 4-Sep-08, at 5:15 PM, Helmut Brandl wrote:
>
>> Simon,
>>
>> I have got another challenge for you.
>>
>> Let's assume that there is an "expanded class EXP" which is not
>> self-initializing. What happens, if you create a SPECIAL[?EXP]? What
>> value will the n items of the array have? Will you need an extra flag
>> in objects of type EXP to mark whether they are initialized or not?
>>
>> What is the boolean value of {x:EXP} (create
>> SPECIAL[?EXP].make(100))[5]? Does ECMA allow detachable  versions of
>> expandeds?
>>
>> Note that usually it is not necessary to have a detached expanded type.
>>
>> Helmut
>>
>> The Eiffel Compiler: http://www.sourceforge.net/projects/tecomp
>> Documentation: http://tecomp.sourceforge.net
>>
>>
>>
>> Helmut Brandl wrote:
>>> Simon Hudon wrote:
>>>
>>>> I disagree with the need of introducing something more primitive
>>>> than SPECIAL.  In my perspective, SPECIAL has a very basic
>>>> definition which is used to implement all kinds of other data
>>>> structures.  It must be seen as a sequence of self-initialized type
>>>> whose size is fixed.  It is not intended to be carried around but
>>>> rather it should be seen as a component frequently used to
>>>> implement data structures.
>>>>
>>>> If you need a sequence of varying size which can range over more
>>>> than just self-initialized types, the useful abstraction is a LIST
>>>> which can effectively be implemented in terms of a SPECIAL.
>>>>
>>> I doubt that it will be very efficient, see below.
>>>
>>>> One could argue that there is a mismatch between the generic
>>>> parameter of ARRAYED_LIST [G] and the one that would be provided to
>>>> SPECIAL [?G].  This mismatch can be overcome using
>>>> an invariant saying that all items from 1 to count must not be
>>>> void.  Whenever the list has to returned, an object test would have
>>>> to be used (in an assertion, once it will be implemented).
>>>>
>>> With the current version of the kernel library, I don't see another
>>> way of implementing an ARRAYED_LIST than the one you proposed (it is
>>> probably implemented that way). With assertion checking on, it will
>>> not be very efficient. On the contrary. It can be awfully slow on
>>> large arrays. Each feature call has to check the invariant iterating
>>> over all the elements to check that they are attached. This has
>>> O(n2) complexity (e.g. inserting 1.000.000 items into a list will
>>> require (1.000.000+1)*1.000.000/2 checks). Each item query has to do
>>> an object test in an assertion. You can argue, that one could turn
>>> class invariant monitoring off for ARRAYED_LIST. But is this really
>>> the solution? Will ECMA specify, that assertions with object tests
>>> cannot be switched off (see next point)?
>>>
>>> Up to now I have not yet seen any clear strategy of the ECMA
>>> committee on how they will handle object test in assertions. The
>>> last that I understood from remarks of Manu is that even if
>>> assertion checking is off, assertions with object tests (or void
>>> test, which is practically the same) have to be executed. Remember
>>> that an object test has a side effect. You cannot switch the
>>> assertions off which have a side effect.
>>>
>>> Another way would be to have a kind of proofing engine in the
>>> compiler, which can prove, that the invariant will never be violated.
>>>
>>> And all this powerful machinery just for not having an elementary
>>> class with builtin features which will cost just an attribute more
>>> (the actual count) than the class SPECIAL. No O(n2) invariant
>>> checking, no object tests necessary, the change would not break any
>>> code. So my question is rather straightforward: What do you loose,
>>> if you had a very primitive builtin class like SPECIAL_SEQUENCE? And
>>> what a gain in performance and reduced complexity for implementing
>>> classes like ARRAYED_LIST?
>>>
>>>
>>> It may be possible, that the ECMA committee will abandon the
>>> possibility of object tests in assertions. What then? To be honest,
>>> I don't see a lot of use of having object tests in assertions except
>>> for providing a workaround for not having a primitive class like
>>> SPECIAL_SEQUENCE. All the other cases you can probably handle by
>>> intelligent use of attached types.
>>>
>>> Peter mentioned in some previous post the possibility that object
>>> tests in assertions are just a migration facility to
>>> attached/detachable types. I think he has got a point. Look into the
>>> libraries being developed without having void safety. You see a lot
>>> of assertions like require arg /= Void. Accepting that as a CAP
>>> gives you the possibility of introducing attached types without
>>> breaking code. But maybe the ladder will be removed after successful
>>> migration ..... Then the ECMA committee might come up with a class
>>> like SPECIAL_SEQUENCE ....
>>>
>>>
>>>> This way, you have a sequence equivalent to your SPECIAL_SEQUENCE
>>>> but implemented in terms of SPECIAL.  I believe also that this
>>>> precise implementation is not much different of what you would have
>>>> to do for SPECIAL_SEQUENCE [G].
>>>>
>>>> Did you see any use of SPECIAL_SEQUENCE not covered by an
>>>> ARRAYED_LIST?
>>>>
>>> No, it does not give me more functionality. SPECIALS_SEQUENCE can be
>>> the primitive class for building classes like ARRAYED_LIST,
>>> ARRAYED_SET, ARRAYED_MAP, ARRAYED_LIST_SORTED, ... The improvement I
>>> see is the reduced complexity and improved performance. Note that
>>> SPECIAL_SEQUENCE does not require any additional indirection like
>>> ARRAYED_LIST. So for applications, where that difference counts (I
>>> admit, that very few application will suffer from the one more
>>> indirection in ARRAYED_LIST, but they surely will suffer from the
>>> needed assertions, if the list contains a big number of items), they
>>> have the freedom to use the more basic class SPECIAL_SEQUENCE.
>>>
>>> Helmut
>>> The Eiffel Compiler: http://www.sourceforge.net/projects/tecomp
>>> Documentation: http://tecomp.sourceforge.net
>>>
>>>
>>>
>>>> I'm waiting for your feedback.
>>>>
>>>> Regards,
>>>>
>>>> Simon Hudon
>>>>
>>>> On 4-Sep-08, at 1:33 PM, Helmut Brandl wrote:
>>>>
>>>>
>>>>> From my perspective, the actual generic of SPECIAL has to be a self
>>>>> initializing type.
>>>>>
>>>>> This seems to be necessary, because the creation of a SPECIAL object
>>>>> returns an array with all entries initialized to their default value.
>>>>>
>>>>> In addition to SPECIAL I would like to have a class
>>>>> SPECIAL_SEQUENCE[G]
>>>>> in the kernel library which is initially empty, but has the
>>>>> capacity to
>>>>> be filled with objects. For that class, we would not need the
>>>>> restriction of feeding it with a self initializing actual generic. I
>>>>> would consider SPECIAL_SEQUENCE more basic than SPECIAL (you can
>>>>> implement SPECIAL with SPECIAL_SEQUENCE but not the other way round).
>>>>>
>>>>> Opinions?
>>>>>
>>>>> Helmut
>>>>>
>>>>> The Eiffel Compiler: http://www.sourceforge.net/projects/tecomp
>>>>> Documentation: http://tecomp.sourceforge.net
>>>>>
>>>
>>> -------------------------------------------------------------------------
>>>
>>> This SF.Net email is sponsored by the Moblin Your Move Developer's
>>> challenge
>>> Build the coolest Linux based applications with Moblin SDK & win
>>> great prizes
>>> Grand prize is a trip for two to an Open Source event anywhere in
>>> the world
>>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>>> _______________________________________________
>>> freeelks-devel mailing list
>>> freeelks-devel@...
>>> https://lists.sourceforge.net/lists/listinfo/freeelks-devel
>>>
>>>
>

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
freeelks-devel mailing list
freeelks-devel@...
https://lists.sourceforge.net/lists/listinfo/freeelks-devel