Re: [stack] disallowing recursive definitions

----- Original Message ----- 
From: "Daniel Ehrenberg" <[email protected]>
To: <[email protected]>
Sent: Saturday, March 01, 2008 9:17 AM
Subject: Re: [stack] disallowing recursive definitions


>>  my sense is that programmers (and language designers) *still* do not
>> appreciate
>>  the power of array programming. here's an example i posted the other day on
>>  comp.lang.functional, a general sudoku solver written in q by arthur
>> whitney.
>>  for readability, i've replaced the case statement of q ($[x;y;z]) with
>> if-then-
>>  else pseudocode.
>>
>>  f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p
>> i:x find 0]find til 10]}
>>
>>  note the explicit tail-recursion on 'f' in the else clause. also note that
>> this is
>>  the standard algorithm used in sudoku solvers written in java, python,
>> ruby, ocaml,
>>  &c. compression is achieved through the use of a handlful of array
>> primitives
>>  (til, find, raze, where, all), one iterator (each), a primitive for
>> updating
>>  positions of an array (amend), and a single primitive extended from scalars
>> to
>>  arrays (=).
> 
> I'm having a little trouble parsing this example. Do you think you
> could translate this example to XY, or at least insert parens so it's
> clear where the grouping is, and explain what 27=x... means? 

hi dan.  

f:{if all x then enlist x else raze f each amend[x;i]each where 27=x[raze p i:x find 0]find til 10]}

here's the grouping:

f:{if all x 
   then enlist x 
   else raze 
    f each 
     amend[x;i]each 
      where 
       27=
        x[raze p i:x find 0]find 
         til 10]}

i.e. in the else clause, execute right-to-left (so read left-to-right).


The
> resistance of Factor to add array primitives comes from the idea
> within the community that explicit, strongly typed array operations
> are sufficient. (There are words like v* to multiply two sequences of
> numbers.) Replacing v* with * is something that looks prettier but
> doesn't directly add more functionality. Maybe there's someplace in
> the middle, where functions like raze can be added without going to
> full-blown array primitives. Another problem with array primitives is
> that, generalized, they make arrays a little less first-class, but
> this may be a misunderstanding on my part.

note that in f, there is only one "array primitive":  in x=y, x and y
are either scalars or, if both are arrays, they must be arrays of the
same "shape" (a scalar is considered to be the same shape as any array.)

perhaps this a misunderstanding about the term "array primitive".  in APL,
+, <, =, &c. are extended to arrays, but they are all scalar primitives,
i.e. they are defined on scalars.  primitives like 'find' and 'where' are
array (or list) primitives:  they take arrays as arguments and return arrays
or scalars as results.

perhaps this is a special case of a wider problem, viz. imprecision about
the terms "array", "list", &c.  i use these terms interchangeably, whereas
others may not.  for me, a list or array is an ordered collection parts of
which (sublists or subarrays or scalars) can be indexed/amended by position.
note that in some array languages, e.g. k/q, other "bulk datatypes" exist,
e.g. maps (or dictionaries), which are unordered collections parts of which
can be indexed by symbols in the domain.  but i always mean objects of
all bulk-types to be "first-class":  they can be assigned, passed as
arguments, returned as results.  in every way, they are semantically
identical to the atomic values out of which they are constructed.  moreover, 
all primitives (e.g. +) are defined (at least in principle) on all bulk-types.
e.g. a vector can be added to a map (yielding a map), a table can be added to
a vector (yielding a table), &c.  this "orthogonality property" is partly why
complex algorithms like the sudoku solver can be expressed so simply.

> 
> Thanks,
> 
> Dan
>