[comments inline, because otherwise I become lost]
On Tue, Feb 7, 2012 at 3:43 PM, Viktor Cerovski
<[email protected]> wrote:
> Raul Miller-4 wrote:
>>> Here is where ADT show some power in reasoning about data,
>>> because we can ask what does it mean for instance, "everything
>>> is array". Well, as I wrote some time ago, to me in J scalars are
>>> not arrays because the equation
>>> a-:a,x
>>> has no solution for any scalar a, but has solution for an array a.
>>> So, ADT could be helpful in sorting this type of questions with
>>> some rigour.
>>
>> But why is the ',' operation the determining issue, here? Is your
>> reasoning based on the existence of the ',' verb?
>
> Indeed. But this existence is not accidental---pretty much every
> programming language has some sort of append, concatenate, etc.
> It's as far as J primitives go, pretty primitive operation, also
> frequently used.
Agreed -- it's a simple operation which is useful fairly wide variety
of contexts.
> Furthermore, I'd like to put "everything is array" to the test: are
> scalars arrays? Is there any way to decide or test it or is it a mere
> conventional saying?
It's clear to me that everything is not an array.
For example: verbs, such as the operation denoted by (,) are not
arrays (though they may represented as arrays and their arguments and
results are arrays).
> Then I said scalars are not arrays because I don't have a noun in J
> that I can append to a scalar and get that same scalar, but I have
> such nouns in the case of arrays. Sounds somewhat arbitrary? I'll
> come back to this question from the perspective of ADT.
Indeed, it sounds arbitrary. In part because "append" is arbitrary.
I (and have) constructed programs that use arrays which do not use
append. Why should append be relevant to those programs?
> First, the way you circumvent the problem:
>
>> If so, let's say I defined:
>>
>> viktor=:4 :0
>> R=. x,y
>> if. (1-:#R) *. 0 e. x ,&(#@$) y do. {.R end.
>> )
>>
>> ..and let's say that I use this 'viktor' operation in place of ',' --
>> has the definition of "Array" changed?
>
> Array hasn't changed, but append *has* changed to accommodate
> the exception.
No, append has not changed. Not unless we define append as something
like "whatever operation we happen to be considering". The existence
of (viktor) does not replace the existence of (,).
> Equivalently,
>
> p =: *.&(''&-:) $@]
> append =: ,`[@.(p~)`]@.p
3 (append -: viktor) i. i. 3
0
> (x p y is the predicate: is x scalar and y empty array?)
>
>> Is your argument that , is a language primitive where 'viktor' is not
>> a language primitive? If so, does that mean that
>>
>> i.2 2
>> 0 1
>> 2 3
>>
>> is not a matrix, because +/ .* is not a primitive?
>
> I think that if , were defined as you suggest or in a similar way
> we would have had somewhat better definition of append, more
> attuned to the 'everything is array' statement.
But why?
We can have all three definitions -- the language allows us to do that.
> ADT let us see better where is the problem.
> I begin with the following definition of the type of integer J arrays as:
>
> Jarr = [int]*[int]
>
> The first list is the rank, the second elements. Clearly, scalars fit into
> this type---number 5 would be represented as []*[5], number 2 as []*[2]
> 5 + 2 as []*[5] + []*[2] = []*[7], and appending is done as:
> []*[5] , []*[2] = [2]*[5 2]. So far so good, everything is array,
> and we actually formulated ADT that accurately describes J int arrays, no?
Maybe... (note that I have to buy into the unstated idea that a square
bracket delimited list is a one dimensional list of constant time, and
I think another unstated idea is that the product of the first list
must describe the number of elements in the second list, there may be
other issues).
> Well, the problem is that Jarr type, together with operations + and ,
> is isomorphic to (which roughly means "the same as" or "equivalent to"
> or "structurally same as") the following type:
>
> Jarr' = int + [int]*[int]
Or we could say:
Jarr'= int + [int]+ [[int]] + [[[int]]] + ...
with some constraints on the sizes of the underlying sublists.
But I see no advantage to mixing explicit shape with implicit shape
for different instances of the same type.
> where the list representing rank is now further constrained to
> *non-empty* ranks, while operations + and , now work as:
> 2 + 5 = 7
> 2 , 5 = [2]*[2,5]
> 2 , [1]*[5] = [3]*[2,1,5]
> etc
Here 7 is equivalent to []*[7]
> We *explicitly* discriminate between scalars and arrays that are
> not scalars at the type level. So which one is the correct type?
Jarr represented scalars by having the first list of the list pair be
empty. And, Jarr represented non-scalars by having the first list of
the pair be non-empty. I see nothing wrong with using Jarr.
But if we can argue that Jarr is not the correct type, then that
suggests that an absolute value operation which takes an int argument
and produces an int result requires that negative values cannot be
considered to be int (because the absolute value operation cannot
produce negative int results from an int argument).
But, in my mind, the existence of an absolute value operation would be
no justification for saying that int now must be represented as:
positiveInt + generalInt
I can see that as an allowable expansion, but... required? I am not
seeing the requirement.
> Jarr or Jarr'? Both are equivalent at the level of J, since J does not
> insist on either Jarr or Jarr' representation of arrays. Insisting on Jarr
> would have been pointless, because definition of J as we know it
> would not have changed if we used Jarr' to implement it.
But, likewise, insisting on Jarr' seems pointless.
> but this also means that the question "is everyting array in J?"
> is a mute point, almost an arbitrary qualification. It's nothing
> wrong with it, there are very nice things in J like identity functions,
> but how can it be justified from the perspective of ADT?
It seems, to me, that introducing Jarr''s extra complexity would be
the thing needs to be justified.
> Here neither yours nor mine augmentation of , would make
> any difference, because if we program them using Jarr type,
> then we still dynamically check whether something is scalar or
> not, and if we program them using Jarr' type, we'd end up
> most likely defining a polymorphic function/procedure that
> discriminates between int and [int]*[int] types from Jarr'.
Yes, I think we can agree that Jarr''s extra complexity does not
prevent it from emulating Jarr.
>> I am trying to make sense of your reasoning, and I am struggling.
>>
>>>> But a bigger problem is that we don't really have a good definition of
>>>> "type". And by "good" I mean:
>>>>
>>>> a. concise,
>>>> b. accurate, and
>>>> c. consistent.
>>>>
>>> I don't know what's wrong with types as we use it today,
>>> either in simplest cases or in some deep theoretical sense.
>>
>> That sounds excellent -- but what is this definition for 'type'?
>>
> We gather some things together and give them a common name:
> like numbers 1,2,3,4,5 and call them int1to5, or True and False
> and call them Bool, or all 32 bit machine integers and call them Int32,
> all possible lists of ints, including empty list, and call them [int] etc.
>
> There also have to be some operations available and/or definable
> in order to make programs, and it is often that types are chosen
> according to operations that are to be done with values of a given
> type.
Ok... I will try and keep this definition in mind next time I see
statements that make assertions based on concepts of "type", to see if
the statements still make sense. Thank you.
But I often see "type" used as almost equivalent to "domain" and
"range" -- for example, the distinction between "static" and "dynamic"
type systems seems to imply that in a "static type system" the domain
of all functions must exactly match the underlying type. I am not
sure how I could make sense of that kind of thinking with your
definition.
>>>> Note also that i. i. 4 has 0 ints... and a shape of four. So the type
>>>> here might be "1" though if you also consider the shape information
>>>> the type here might be int*int*int*int.
>>>>
>>> oh, I see where you're headed. You're asking for type
>>> representation for arrays including empty ones of arbitrary
>>> shape. Well, ADT might be simply:
>>> [int]*[int]
>>> so your array would be represented as [0,1,2,3]*[]
>>
>> Ok, though this leaves me with issues like: what is the type of the array
>> (0 1)?
>>
> Its type is [int]*[int] (this is Jarr), and concrete value that represents
> the array is [2]*[0 1].
>
> It could be also of type Jarr' and the same representation just as well,
> as I discussed moment ago.
0 and 1 are boolean values, in J.
But perhaps you are saying that Jarr deviates from J in this context.
>> Hypothetically, I could see a J array being: T*[int]*[atom] where T
>> matches the type of the atoms and product([int]) matches the number of
>> atoms.
>
> Sure thing (just the type would be more like T*[int]*[T], and my
> previous example with Jarr' would now become T*(T+[int]*[T]).)
And, of course: T*[int]*[T] < T*(T+[int]*[T])
But if we ignore the higher ranked arrays, your variant simplifies to
T*T which seems wrong.
>> But the underlying values here seem to be near-infinities, and
>> I am not certain how I could work with them. Or, if I take their base
>> 2 log, they seem to be a [relatively bland] restatement of the numbers
>> used by memory management.
>>
> I'm not sure what you mean: when we define type, we haven't really
> constructed a single instance of the type, just constructively described
> (finite or potentially infinite) collection of values that belong to the
> type.
I mean that the algebraic data type system seems to want to use
extremely large numbers when describing otherwise practical problems
(remembering that if ('int' represents a 32 bit integer value) then
('int' is 2^32) -- coincidentally a value too large to be represented
directly, using the 'int' data type).
> When the program rolls on, 0 or more instances of defined types are
> created, depending on program.
But those are values, and not algebraic data types.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
