adding construction to factor

[John Nowak]

I managed to add something like FP's construction form to Factor. It  
treats stacks as if they were vectors in More's array theory, e.g. '5  
== {5}'. I mentioned wanting to do this a few days ago, so I thought  
I'd share. Maybe it's useful.

Here are a few of examples:

    5 [( sq , dup , neg , drop ])  ==  25 { 5 5 } -5 { }
    5 3 2@ [( + , - )]  ==  8 2
    5 [( 5 + , 5 - )]  ==  10 0

And here's the implementation:

: 2@ 2array ;
: 3@ 3array ;
: 4@ 4array ;
: lift dup array? [ 1array ] unless ;
: lower dup length 1 = [ 0 swap nth ] when ;
: construct
   [ lift ] dip
   [ over [ with-datastack ] dip swap lower ] map
   nip [ ] each
;
: )] ;
: [( \ )]
   [ \ , 1array split [ >quotation ] map ] parse-literal
   \ construct suffix
; parsing

- John

[Christopher Diggins]

On Sun, Jan 4, 2009 at 10:40 AM, John Nowak <john@...> wrote:

> I managed to add something like FP's construction form to Factor. It
> treats stacks as if they were vectors in More's array theory, e.g. '5
> == {5}'. I mentioned wanting to do this a few days ago, so I thought
> I'd share. Maybe it's useful.
>
> Here are a few of examples:
>
> 5 [( sq , dup , neg , drop ]) == 25 { 5 5 } -5 { }
> 5 3 2@ [( + , - )] == 8 2
> 5 [( 5 + , 5 - )] == 10 0
>
> And here's the implementation:
>
> : 2@ 2array ;
> : 3@ 3array ;
> : 4@ 4array ;
> : lift dup array? [ 1array ] unless ;
> : lower dup length 1 = [ 0 swap nth ] when ;
> : construct
> [ lift ] dip
> [ over [ with-datastack ] dip swap lower ] map
> nip [ ] each
> ;
> : )] ;
> : [( \ )]
> [ \ , 1array split [ >quotation ] map ] parse-literal
> \ construct suffix
> ; parsing
>
> - John

This looks like line noise to me. Either I'm dense, or the code could
benefit from some comments.

- Christopher

[William Tanksley, Jr]

John Nowak <john@...> wrote:
> I managed to add something like FP's construction form to Factor.

That looks nice, John.

> It
> treats stacks as if they were vectors in More's array theory, e.g. '5
> == {5}'.

Is "stacks" a typo here?

> I mentioned wanting to do this a few days ago, so I thought
> I'd share. Maybe it's useful.
> Here are a few of examples:
>    5 [( sq , dup , neg , drop ])  ==  25 { 5 5 } -5 { }
>    5 3 2@ [( + , - )]  ==  8 2
>    5 [( 5 + , 5 - )]  ==  10 0

Yes; that's nice and clear. It occurs to me that this is a parallel
execution operator.

> And here's the implementation:

Nice and terse. Very clear.

> - John

-Wm

[John Nowak]

On Jan 4, 2009, at 11:16 AM, Christopher Diggins wrote:

> This looks like line noise to me. Either I'm dense, or the code could
> benefit from some comments.

I think the first half (up to and including the definition of  
'construct') should be fairly straightforward. If it helps, 'with-
datastack' is the same as Joy's 'infra', the 'Narray' words group N  
elements on the stack into an array, and '[ ] each' is a gross way of  
putting all of the elements in an array onto the stack.

The second half just makes this:

    [( f g , h i )]

parse to this:

    { [ f g ] [ h i ] } construct

How it does that, I'm not exactly sure. It was much trial and error  
modifying the definition of '[' to suit my needs. I'd not written a  
parsing word in Factor before, so perhaps there's a better way to do it.

- John

[John Nowak]

On Jan 4, 2009, at 11:31 AM, William Tanksley, Jr wrote:

>> It  treats stacks as if they were vectors in More's array
>> theory, e.g. '5 == {5}'.
>
> Is "stacks" a typo here?

Ah, perhaps. I suppose Factor calls them "arrays". I was thinking  
"stacks" because I was using them as such.

What I essentially mean to say is that construction needs a single  
array of values to operate on. If you give it a non-array, it'll  
bundle it into a one element array for you (else it won't touch it).  
For each value that results from the construction, it will convert one  
element arrays to just the elements they contain non-recursively (else  
it won't touch them).

That's not exactly how More's theory works, but it seemed to make a  
little more sense to do it this way given that I'm grafting it onto a  
stack-based language. Ideally, you'd base the whole language on  
vectors instead of stacks which would give you a nice syntax for  
conveying the semantics. For example, if parentheses represented  
vectors, I could write the semantics very simply:

    x [(F)]   == (x F)
    x [(F,G)] == (x F) (x G)
    ...

>> 5 [( sq , dup , neg , drop ])  ==  25 { 5 5 } -5 { }
>> 5 3 2@ [( + , - )]  ==  8 2
>> 5 [( 5 + , 5 - )]  ==  10 0
>
> Yes; that's nice and clear. It occurs to me that this is a parallel
> execution operator.

Aye. Unlike with cleave, there's no way the quotations can interact  
here (barring side-effects). Even the type system I have cannot  
prevent interaction from occuring in cleave; I'd have to add row  
variable concatenation to be able to handle it (where '0' is the empty  
row and '++' is concatenation):

    bi :: R x [R x -> S] [0 x -> T] -> S++T

Compare this to the usual type for 'bi' (which allows the second  
quotation to access the result of the first):

    bi :: R x [R x -> S] [S x -> T] -> T

Anyway, I'm thinking of writing up an interpreter for a Joy-like  
language that uses vectors instead of lists and separates vectors from  
quotation. Both changes should make it easier to do parallel  
reduction. The change to vectors should make it easier as it makes  
construction more useful and construction enables parallel evaluation  
as you already discovered. Separating vectors from quotations and  
making quotation opaque will help as it's not generally legal to  
simplify a quotation in Joy. This is because '[1 2 +] != [3]' as you  
could always use it as a list instead of a quotation later on and  
they're obviously not equivalent lists. Making it impossible to peek  
inside a quotation solves this problem.

- John

[LittleDan]

I don't know what you're talking about; that code is perfectly
idiomatic and readable, save for the missing stack effect comments and
indentation. It's as much factored as I would write it. Probably it is
difficult to read because you are unfamiliar with Factor's library. I
think it's a nice little piece of syntactic sugar, well-implemented.

Dan

On Sun, Jan 4, 2009 at 10:16 AM, Christopher Diggins <cdiggins@...> wrote:
> This looks like line noise to me. Either I'm dense, or the code could
> benefit from some comments.
>
> - Christopher
>
>

[Christopher Diggins]

> Probably it is
> difficult to read because you are unfamiliar with Factor's library.

Of course I'm unfamiliar with Factor's library, this is not a Factor
mailing list. I have the expectation that my experience with Joy,
PostScript, combinatory logic, lambda calculus, over a dozen other
programming language plus my own concatenative language, should be
enough to figure out code posted to this list.

This is why I made the suggestion that some comments would be helpful.
If I am having problem understanding it then maybe some others readers
have troubles as well. But hey, if the post is only intended for
Factor programmers, then fine.

- Christopher

[John Nowak]

On Jan 4, 2009, at 6:12 PM, Christopher Diggins wrote:

>> Probably it is
>> difficult to read because you are unfamiliar with Factor's library.
>
> Of course I'm unfamiliar with Factor's library, this is not a Factor
> mailing list. I have the expectation that my experience with Joy,
> PostScript, combinatory logic, lambda calculus, over a dozen other
> programming language plus my own concatenative language, should be
> enough to figure out code posted to this list.

Here's a Joy implementation:

LIBRA
reverse == [] [swons] fold;
@N == [] swap [cons] times reverse;
@2 == 2 @N;
@3 == 3 @N;
@4 == 4 @N;
quote == [] cons;
when == [] ifte;
unless == [] swap ifte;
lift == [list] [quote] unless;
single == [null] [pop false] [uncons null popd] ifte;
lower == [single] [first] when;
over == [dup] dip swap;
infralowermap == [over [infra] dip swap lower] map;
construct == [lift] dip infralowermap popd [] step;
.

- John