Re: [stack] disallowing recursive definitions

hi dan

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


>>  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.
> 
> You're right, there is some misunderstanding. What I was talking
> about, and what Factor's missing, is the property of things like "+"
> to denote both scalar and vector addition; how, in APL-based
> languages, certain operators like +, =, <, etc are defined to map
> their operation to atoms within vectors (assuming that shapes match).
> Everything else can be fairly easily defined in the library with no
> modifications to existing code, if it doesn't already exist. I might
> be misunderstanding the nature of array languages, but here's my
> problem with this: it creates a primitive, difficult-to-extend concept
> of an array which isn't quite first-class as far as I can tell.

in k, two arrays can be added if either or both are atoms, or their
shapes are conformable.  so e.g. a 2x3x4 can be added to an array of
shape 2 (a vector), or 2x3, or 2x3x4, or 2x3x4x...  or using various
combinations of each, each-left, and each-right, a 2x3x4 can be added
to a 7x2x3x4 or ...   the combinators allow you to control the way
the dimensions line up for the operations.

the k bulk datatypes are:  list, map, table (transposed map of lists),
and keytable (map of a table with unique rows to a table.)  all 
primitives are defined on all types and combinations of types.  the
combinations have different comformability and extension rules.

an interesting question is what machinery, and in what strength,
could be added to support user-defined datatypes.  at minimum, it
would require (i) defining what the primitives do on each combination
of the new datatype and existing datatypes, and (ii) what the
conformability rules are (since for any datatype x, you would have
to support at the very least lists and maps of x's.  an open question.

but k, at least, has been grudging about the addition of new datatypes.
in practice, the policy has always been:  simulate the new datatype,
see how useful it is, think about how it could be integrated, &c.
the process seems to take about five years.  a small number of ideas
make it into the interpreter core, but when they do, their behavior
is fully defined for each primitive and each bulk datatype.  at some 
point, i may describe the evolution of the concept of tables in k, from 
APL\360 to q.  it's an interesting story.

so rather than proliferate datatypes (indefinitely if you leave it
up to the programmer) and give up orthogonality, we try to represent
pieces of the world with a very small set of bulk datatypes and an
orthogonal, generalized set of primitives.  (atomic datatypes are
easier to deal with, and there are lots of these.) 

> 
> Anyway, I'm in the process of decoding the example given (since I
> don't know Q) and translating it directly to Factor to see if adding
> any idioms would be appropriate. Stevan, could you tell me what the
> function f is supposed to take as an argument? 

http://www.wagerlabs.com/blog/2008/02/shortest-sudoku.html

Either way, when I find
> myself writing explicit tail recursion (which is fairly but not
> extremely rare in Factor) I often try to abstract it into a
> combinator. When I make these abstractions, it's only because the
> existing ones (the higher order functions like each, map and reduce
> that Factor and APL basically share

no, i think that's a misconception.  the k higher-order functions
take functions of any valence.  e.g. 

    f:{x+y*z}
    f'[a;b;c] / each applies f to corresponding elements of a,b,c

? ) can't express it. I can't imagine
> a situation where the fact that + operates on vectors as well as
> scalars would change whether I would have to write explicit tail
> recursion.

the sudoku solver contains a single scalar function =.  you'd have
to write either a loop or a recursion to handle that.  other examples
abound.  see eugene macdonell's paper, linked to in an earlier post.
this is what i was unable to get slava to see:  extending + to arrays
(or in factor's case, vectors via v+) by itself doesn't seem to get
you anything terribly useful.  so big deal, how often do i want to
add vectors?

> 
> I use tail recursion when I'm either (a) interfacing with non-arrays
> that still have to be iterated over in some way, for example an I/O
> stream (b) doing something weird that'd be awkward to express in terms
> of the abstractions I know. So (a) would be hard to eliminate, 

why isn't a stream a list?

and (b)
> is more of a cause for concern. I encountered a lot of (b) cases in
> implementing things like Unicode normalization and case conversion,
> and in those cases I built some semi-general abstractions using tail
> recursion. I wonder if some of these should be moved to a more
> general-purpose library, but even if they should, that's not a case
> for array primitives in the sense of + to be integrated deeply into
> the language.

lower-to-upper case in k:

    u:_ci@[!256;97+!26;-;32]    
    i:_ic"a99*bc"
    u i
  "A99*BC"
    
no loops, no recursion.  depends on - being defined on arrays.

look, this is what i meant when i said that the power of the array
approach is not obvious -- it can't be "read off" the definitions of
the primitives.  or if i didn't say that, that's what i meant.  as
i *have* been trying to say for several years now is that with the
right set of primitives and datatypes, all sorts of non-obvious 
solutions arise.  that's why the k sudoku is so short (i think it's
down to 54 characters now.)

> 
> (Just for the record, it's very annoying that there are two languages
> named Q, and the one relevant here has a very small online footprint,
> and that in that small website, the maintainers can't be bothered to
> type out "docs", instead calling the directory "d". Also, I just had a
> sort of "whoa" moment when I realized that the same guy who came up
> with the first good polynomial-time tree diffing algorithm is the same
> guy who's doing all this K/Q stuff...)

you mean dennis shasha?  he's also the math games editor for scientific
american.  he's the man!

> 
> Dan
>