# adding construction to Joy-like languages

## John Nowak — 2008-12-30 03:05:48

    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 — 2008-12-30 03:23:17

    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 — 2008-12-30 13:41:23

    ----- 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 — 2008-12-30 22:50:17

    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

## Daniel Ehrenberg — 2009-01-01 05:23:22

    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 — 2009-01-01 10:50:25

    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