adding construction to Joy-like languages

[John Nowak]

This may be more of a post-holiday brain dump than anything  
interesting. If so, just ignore.

One of the things I really like about FP is the functional form of  
construction. I've mentioned this in earlier emails, but here's a  
quick summary:

   Here's a construction involving three functions:

     [f, g, h]

   Applying (denoted ':') the construction to a value works as such:

     [f, g, h]:x  ==  <f:x, g:x, h:x>  -- angle brackets denote a list

In short, construction is very similar to the cleave combinators in  
Factor. Unfortunately, the cleave combinators are not nearly as  
convenient as construction for a number of reasons:

1. The single form of construction handles any number of inputs and  
outputs properly. In contrast, a family of cleave combinators is  
needed. Factor has "smart combinators" that rely on the types of the  
functions involved to get around this, but they're quite awkward in  
comparison to FP's approach.

2. FP has functions which, given a list, return a single element from  
that list. Factor has no way (that I know of) to index into a stack  
returning only the element selected.

3. FP uses lists to group more than one element. As such, you can do  
something like '[sq, dup]:5' to get '<25, <5, 5>>'. Emulating this  
behavior is nearly impossible in Factor because all values are carried  
inside a stack. As such, you must either return a flat stack like '25  
5 5' (which is what '[sq] [dup] bi' would do) or return all stacks  
independently like '{25} {5 5}' which makes getting at the values  
painful. I've mentioned this problem earlier but I'm not sure if I'm  
explaining it adequately.

The solution I propose has four parts:

1. Replace the stack with a vector in the style of More's array  
theory. Here, a vector containing a single element is equivalent to  
the element it contains (and vice versa). We'll denote such nestable  
vectors with parentheses, e.g. '1 (2 3)' is a two element vector  
containing '1' and the two element vector '(2 3)'. Note that, as in  
More's array theory, '(1)' is equivalent to '1'. As such, '1 2 3 + *'  
can be written '(1 (2 3 +) *)' without changing the meaning of the  
expression. '()' denotes the empty vector.

2. Add functions for indexing into a vector, e.g. '1 2 3 4 2nd' yields  
'3'.

3. Add a set of functions for grouping values, e.g. '1 2 3 4 2g'  
yields '1 2 (3 4)'.

4. Add a syntax for construction of the form [|f0, f1 .. fN|].

What construction will do for us is take the top value of the vector  
passed to it and apply every function in the construction of N  
functions to it yielding a vector that is the concatenation of the  
vector below the initial value and the N values produced from the  
application. Whew.

Here are some examples:

   1 2 3 [|sq, neg|]  ==  1 2 9 -3  -- works as '3' == '(3)'
   3 4 2g [|+, -|]  ==  7 -1
   5 [|sq, dup, drop|]  ==  25 (5 5) ()
   5 12 [|1st sq, 2nd sq|] +  ==  (5 sq) (12 sq) +  ==  25 144 +  ==  
169

Something marginally more useful:

   discriminant = 3g [|2nd sq, [|1st, 3rd|] * 4 *|] -

Instead of adding a new syntax, we could alternatively offer c2, c3,  
etc, to denote construction over a set number of functions:

   discriminant = 3g [2nd sq] [[1st] [3rd] 2c * 4 *] 2c -

Useful? I'm not sure. The need to group things into a single vector  
all the time means it is still less convenient than the FP version:

   discriminant = - [sq 2nd, * [* [1st, 3rd], 4]]

This is especially if we use an infix syntax (e.g. 'f g h == g:[f,  
h]') like J's monadic hook:

   discriminant = (sq 2nd) - 4 * 1st * 3rd  -- all associate right

- John

[John Nowak]

On Dec 29, 2008, at 10:05 PM, John Nowak wrote:

> Something marginally more useful:
>
>   discriminant = 3g [|2nd sq, [|1st, 3rd|] * 4 *|] -
>
> Useful? I'm not sure. The need to group things into a single vector
> all the time means it is still less convenient than the FP version...
> This is especially if we use an infix syntax (e.g. 'f g h == g:[f,
> h]') like J's monadic hook:
>
>   discriminant = (sq 2nd) - 4 * 1st * 3rd  -- all associate right

I suppose I could be more fair in my comparison; I managed to throw  
out all the benefits of the concatenative programming style in my  
example as I was doing a direct FP translation. Here's a better version:

   3g [|2nd sq, 4 * *|] -

Compare to what you'd probably write in Factor now:

   [sq swap] dip 4 * * -

I think the first version is better. It's clear that you're dealing  
with three values, clear you're squaring the second, clear you're  
getting two results and then taking the difference, etc.

I can't help but think there's some good way to combine FP with Joy-
style languages. I think using More-style vectors as the primary data  
structure may be a good start.

- John

[stevan apter]

----- Original Message -----
From: "John Nowak" <john@...>
[:]
>
> 2. FP has functions which, given a list, return a single element from  
> that list. Factor has no way (that I know of) to index into a stack  
> returning only the element selected.

why limit yourself to a single element, or to indexing only at the
top level of a list?

i'll use "S" and "D" to denote the surface and depth indexing functions,
and i'll write them infix.  the left argument is the list to index,
the right argument is the index:

    10 20 30 S 2
  30
    10 20 30 D 2
  30
    10 20 30 S 2 0
  30 10
    (10 20 30)(40 50) S 0
  10 20 30
    (10 20 30)(40 50) D 0(2 1)
  30 20

i.e. the right argument of D describes a path through the list.

    () = X D ()
    () = X S ()

it's useful to have a null of some kind to represent all the
elements.  i'll use "N":

    (10 20 30)(40 50) D N 1
  20 50

detaching the index from the function allows you to compute
the elements to index, e.g.

   10 20 30 40 50 60 S where 10 20 30 40 50 60 > 30
40 50 60

(this is very APLish:  10 20 30 40 50 60 > 30 -> 0 0 0 1 1 1, and
where 0 0 0 1 1 1 -> 3 4 5.)

>
> 3. FP uses lists to group more than one element. As such, you can do  
> something like '[sq, dup]:5' to get '<25, <5, 5>>'. Emulating this  
> behavior is nearly impossible in Factor because all values are carried  
> inside a stack. As such, you must either return a flat stack like '25  
> 5 5' (which is what '[sq] [dup] bi' would do) or return all stacks  
> independently like '{25} {5 5}' which makes getting at the values  
> painful. I've mentioned this problem earlier but I'm not sure if I'm  
> explaining it adequately.

k has a pair of functions which might be useful to consider.  i'll
use "T" and "C" to denote 'take' and 'cut'.  with list on the left,
control argument on the right:

    1 2 3 4 5 6 T 2
 1 2
    1 2 3 4 5 6 T -2
 5 6
    1 2 3 4 5 6 T 2 3
 (1 2 3)(4 5 6)
    1 2 3 4 5 6 T 3 2
 (1 2)(3 4)(5 6)

    1 2 3 4 5 6 C 2
 3 4 5 6
    1 2 3 4 5 6 C -2
 1 2 3 4
    1 2 3 4 5 6 C 0 2
 (1 2)(3 4 5 6)
    1 2 3 4 5 6 C 0 1 3
 1 2(3 4 5 6)

again, detaching the control argument from the function name allows
you to compute the take/cut.

>
> The solution I propose has four parts:
[:]

i'm not sure what the problem is, so my suggestions might be off-
target.  my sense is that you may be starved for examples.  what
i mean is this:  your data universe is the set of nested vectors.
that's your machinery for representing the world.  so you want a
small set of primitives which give you maximum expressivity and
also combine in powerful ways.  that pretty much describes the
history of innovation in the array programming world over the
last 50 years.  

[John Nowak]

On Dec 30, 2008, at 8:41 AM, Stevan Apter wrote:

>> 2. FP has functions which, given a list, return a single element from
>> that list. Factor has no way (that I know of) to index into a stack
>> returning only the element selected.
>
> why limit yourself to a single element, or to indexing only at the
> top level of a list?

The type system, mainly. For indexing within a vector within another  
vector, you'd have to use something equivalent to Joy's "infra". For  
example:

    1 2 (3 (4 5)) [1st] infra 2nd
    1 2 (3 (4 5) 1st) 2nd
    1 2 (3 5) 2nd
    1 2 3

It's possible that some additional special form could be introduced to  
make such indexing a bit easier. For homogeneous vectors of  
indeterminate length, things could be done a bit differently. It's  
sort of like the difference between tuples and lists in something like  
ML; The former is tracked much more closely on the type level while  
the latter admits a much broader set of operations. Right now, I'm  
only dealing with the former.

> i'm not sure what the problem is, so my suggestions might be off-
> target.

I apologize for not explaining it well.

Essentially what I'm trying to do is come up with something like  
"cleave" for a concatenative language that behaves a bit better. To  
illustrate the current problem with the cleave family, take this  
example (where 'x' is an object and 'F' and 'G' are functions):

    x [F] [G] bi

In a language like Factor, it's hard to say much about this. It's  
unclear if 'F' or 'G' will need more values on the stack beyond the  
'x' that is provided. It's unclear how many values will be returned as  
a result. It's unclear if G will access any values produced by F. Etc.

What I want to be able to do for the above example is solve all of  
those problems. I want it to be clear that the 'x' provided is all F  
and G care about. I want it to be clear that F and G will not  
interact. I want it to be clear that the result will be two values.  
Finally, I want this all to be syntactically obvious; I do not want to  
have to employ the type system to do it.

This is already a solved issue in FP. For example:

    [F, G]:x   -- the construction of 'F' and 'G' applied to 'x'
               -- reduces to...
    <F:x, G:x> -- the list of 'F' and 'G' each applied to 'x'

Essentially, I was trying to add this form of construction to a  
concatenative language. My first attempt was as follows:

1. Limit the functions involved to only using the top element of the  
stack
2. Return the result of each function in its own stack

As a trivial example (where braces denote a stack):

    5 [sq] [dup] bi-construct
    {5 sq} {5 dup}
    {25} {5 5}

The problem with this is that I now have two stacks on the stack. To  
get at the 25, I need to manually pull the value out of the second  
stack. This makes the whole thing too awkward to use.

The solution I proposed was to replace the notion of a stack with the  
notion of a vector where a vector containing a single element is  
equivalent to the element it contains. Here's the same example using  
vectors:

    5 [sq] [dup] bi-construct
    (5) [sq] [dup] bi-construct
    (5 sq) (5 dup)
    (25) (5 5)
    25 (5 5)

Because '5 == (5)', I was able to use construction. Because '(25) ==  
25', I can now access the value without manually pulling it out of the  
stack. At the same time, the result of the other function which  
yielded two values is still nicely bundled up. I get all the  
guarantees I was after without the drudgery.

- John

[LittleDan]

Factor can, in fact, do all of these things within the typical stack
model, though I've never needed any of them in practical programming
problems. Going through your list,

On Mon, Dec 29, 2008 at 10:05 PM, John Nowak <john@...> wrote:
> 1. The single form of construction handles any number of inputs and
> outputs properly. In contrast, a family of cleave combinators is
> needed. Factor has "smart combinators" that rely on the types of the
> functions involved to get around this, but they're quite awkward in
> comparison to FP's approach.

Could you elaborate on why this is insufficient? Maybe it can be
remedied, if there's a specific use case you can show.
>
> 2. FP has functions which, given a list, return a single element from
> that list. Factor has no way (that I know of) to index into a stack
> returning only the element selected.

There's npick, which copies the nth item from the top of the stack on
to the top, given an integer parameter (IIRC). If you follow that by [
clear ] dip, then that'll be all that's on the stack. This seems no
less awkward than your solution (you can of course make a word : th
npick [ clear ] dip ; to make this easier) but I don't see the
motivation.
>
> 3. FP uses lists to group more than one element. As such, you can do
> something like '[sq, dup]:5' to get '<25, <5, 5>>'. Emulating this
> behavior is nearly impossible in Factor because all values are carried
> inside a stack. As such, you must either return a flat stack like '25
> 5 5' (which is what '[sq] [dup] bi' would do) or return all stacks
> independently like '{25} {5 5}' which makes getting at the values
> painful. I've mentioned this problem earlier but I'm not sure if I'm
> explaining it adequately.

A better solution is to use an explicit array for problems like this.
If you want it to be like a stack, you can use the with-datastack
combinator (this is infra). I have not seen a situation where this
would be needed, though.

The general stack philosophy, as I understand it, is that not all
parameters need to be seen by every function. To me, the stack is a
nice representation of this; it is very simple and easy to use. I
don't understand how the dataflow of a complicated function could be
represented with the vector system. I don't remember large functions
in the FP paper, just things like matrix multiplication. It'd be
interesting to see some existing Factor or Joy code translated into
this.

Dan

[John Nowak]

On Jan 1, 2009, at 12:23 AM, Daniel Ehrenberg wrote:

> Factor can, in fact, do all of these things within the typical stack  
> model

Factor is a flexible, reflective language that can be coerced into  
doing almost anything. I'm sure you can embed a nice Lisp or Prolog  
(if you already haven't) that works well with the stack. All you'd be  
doing though is implementing another language inside Factor.

> though I've never needed any of them in practical programming problems

That doesn't mean much. Insert your own "user X of language Y without  
feature Z never needed feature Z" analogy.

>> 1. The single form of construction handles any number of inputs and
>> outputs properly. In contrast, a family of cleave combinators is
>> needed. Factor has "smart combinators" that rely on the types of the
>> functions involved to get around this, but they're quite awkward in
>> comparison to FP's approach.
>
> Could you elaborate on why this is insufficient? Maybe it can be
> remedied, if there's a specific use case you can show.

1. They don't work unless the stack effects are known at the point of  
use.
2. They're meta-level constructs that rely on reflection.
3. They don't have any useful algebraic properties.
4. They can't be typed.
5. Their semantics are very complicated compared to construction.

>> 2. FP has functions which, given a list, return a single element from
>> that list. Factor has no way (that I know of) to index into a stack
>> returning only the element selected.
>
> There's npick, which copies the nth item from the top of the stack on
> to the top, given an integer parameter (IIRC). If you follow that by [
> clear ] dip, then that'll be all that's on the stack.

Good point. I doubt such a style would be remotely efficient in Factor  
though.

>> 3. FP uses lists to group more than one element. As such, you can do
>> something like '[sq, dup]:5' to get '<25, <5, 5>>'. Emulating this
>> behavior is nearly impossible in Factor because all values are  
>> carried
>> inside a stack. As such, you must either return a flat stack like '25
>> 5 5' (which is what '[sq] [dup] bi' would do) or return all stacks
>> independently like '{25} {5 5}' which makes getting at the values
>> painful. I've mentioned this problem earlier but I'm not sure if I'm
>> explaining it adequately.
>
> A better solution is to use an explicit array for problems like this.

Not for the problems I'm looking to address:

1. You'd still need a family of combinators. Smart combinators are not  
a good solution (as I explained above).

2. You're talking about doing something in an ad hoc manner when it's  
convenient. Such an approach doesn't give you any of the guarantees  
that I'm looking for, namely a syntactically obvious number of  
produced and consumed values. Again, with the vector approach I  
suggested, 'x [|f, g, h|]' always yields '(x f) (x g) (x h)'. You  
can't get that sort of rule by altering your programming style.

> I don't understand how the dataflow of a complicated function could be
> represented with the vector system. I don't remember large functions
> in the FP paper, just things like matrix multiplication.

Here's an implementation of FP (with a funny syntax) that comes with a  
number of examples (including a DFT implementation):

    http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/impl/fp_lp/fp/

Additionally, large programs have been written in J using a tacit  
style. I think that's sufficient evidence that the approach is feasible.

- John