In a functional language, the following optimization is valid
(assuming F and G are pure functions that terminate):

map G (map F xs) -> map (G . F) xs

This is not only an optimization: It is a law that can be used for
understanding and proving program properties.

For a concatenative language, we might assume the following rule
(using Joy's syntax):

[F] map [G] map -> [F G] map

Unfortunately, this is not valid because 'F' and 'G' can access more
than one value on the stack. Here is a counterexample to the above rule:

9 [1 2 3] [drop dup] map [[1 -] dip] map -- yields 6 [9 9 9]
9 [1 2 3] [drop dup [1 -] dip] map -- yields 6 [9 8 7]

This seems to be yet another argument against n-ary combinators where
the quotation is not called a fixed number of times. (Combinators that
call their quotation a fixed number of times like 'dip', 'twice', or
' <at> bi' are fine.) The fact that 'map' in a concatenative language is
still "purely functional" doesn't change the fact that the
unrestricted stack access complicates things the same way mutable
local variables do.

It seems the solution is to offer two versions of certain combinators.
The restricted versions ('map, 'each', etc) will be easier to reason
about and optimize, while the unrestricted versions ('map*', 'each*',
etc) will remain useful in a way only possible in stack-based
languages. I think this would be worthwhile to adopt in both typed and
untyped languages.

- John

John Nowak <john <at> johnnowak.com> wrote:
> Unfortunately, this is not valid because 'F' and 'G' can access more
> than one value on the stack. Here is a counterexample to the above rule:

Okay, I think I get this. (I certainly agree.)

> This seems to be yet another argument against n-ary combinators where
> the quotation is not called a fixed number of times.

_This_ I don't understand. What does that mean?

I would have said "this is an argument against combinators which
repeatedly call function inputs that do not have a statically known
stack effect." Am I being too restrictive? Are you being too
restrictive?

> It seems the solution is to offer two versions of certain combinators.
> The restricted versions ('map, 'each', etc) will be easier to reason
> about and optimize, while the unrestricted versions ('map*', 'each*',
> etc) will remain useful in a way only possible in stack-based
> languages. I think this would be worthwhile to adopt in both typed and
> untyped languages.

I definitely like this; although of course in Factor the asterisk
prefix is already taken.

> - John

-Wm

On Fri, Aug 1, 2008 at 4:52 AM, John Nowak <john <at> johnnowak.com> wrote:
> In a functional language, the following optimization is valid
> (assuming F and G are pure functions that terminate):
>
> map G (map F xs) -> map (G . F) xs
>
> This is not only an optimization: It is a law that can be used for
> understanding and proving program properties.
>
> For a concatenative language, we might assume the following rule
> (using Joy's syntax):
>
> [F] map [G] map -> [F G] map
>
> Unfortunately, this is not valid because 'F' and 'G' can access more
> than one value on the stack. Here is a counterexample to the above rule:
>
> 9 [1 2 3] [drop dup] map [[1 -] dip] map -- yields 6 [9 9 9]
> 9 [1 2 3] [drop dup [1 -] dip] map -- yields 6 [9 8 7]
>
> This seems to be yet another argument against n-ary combinators where
> the quotation is not called a fixed number of times. (Combinators that
> call their quotation a fixed number of times like 'dip', 'twice', or
> ' <at> bi' are fine.) The fact that 'map' in a concatenative language is
> still "purely functional" doesn't change the fact that the
> unrestricted stack access complicates things the same way mutable
> local variables do.
>
> It seems the solution is to offer two versions of certain combinators.
> The restricted versions ('map, 'each', etc) will be easier to reason
> about and optimize, while the unrestricted versions ('map*', 'each*',
> etc) will remain useful in a way only possible in stack-based
> languages. I think this would be worthwhile to adopt in both typed and
> untyped languages.

I think I understand. To summarize with Cat type notation:

map : (list ('a -> 'a) -> list)
map* : (list ('A 'b -> 'A 'b) -> list)

In other words, "map" accepts only 1->1 functions, while map* accepts
n->n functions where n >= 1.

FWIW I think this is a very good idea, and I like the notation.

In Cat I simply disallowed "map" and similar combinators from
modifying the stack. It made type analysis easier, it preserved the
fusion properties, and it didn't really cause any huge loss of
expressiveness AFAICT. However: there was definitely some scenarios,
where Joy would be more succinct.

- Christopher

- Christopher

On Fri, Aug 1, 2008 at 7:01 AM, William Tanksley, Jr
<wtanksleyjr <at> gmail.com> wrote:
>> This seems to be yet another argument against n-ary combinators where
>> the quotation is not called a fixed number of times.
>
> _This_ I don't understand. What does that mean?
>
> I would have said "this is an argument against combinators which
> repeatedly call function inputs that do not have a statically known
> stack effect." Am I being too restrictive? Are you being too
> restrictive?

I agree with William. In a high level language, it'd generally be
better if the compiler can figure out its optimizations itself without
needing changes in the language design. Here, it should be easy to
check whether the quotation given affects values lower down on the
stack. In its fusion optimization, the compiler can just use this
information, rather than change the kind of program that the user
writes.

(Maybe map* would be good for documentation purposes or something, but
this is not a good justification for it.)

Dan

On Fri, Aug 1, 2008 at 12:33 PM, Daniel Ehrenberg <microdan <at> gmail.com> wrote:
> On Fri, Aug 1, 2008 at 7:01 AM, William Tanksley, Jr
> <wtanksleyjr <at> gmail.com> wrote:
>>> This seems to be yet another argument against n-ary combinators where
>>> the quotation is not called a fixed number of times.
>>
>> _This_ I don't understand. What does that mean?
>>
>> I would have said "this is an argument against combinators which
>> repeatedly call function inputs that do not have a statically known
>> stack effect."

However, they *do* have a statically known stack effect.

> Am I being too restrictive? Are you being too
>> restrictive?
>
> I agree with William. In a high level language, it'd generally be
> better if the compiler can figure out its optimizations itself without
> needing changes in the language design.

> Here, it should be easy to
> check whether the quotation given affects values lower down on the
> stack.

Yes it is (in most scenarios).

> In its fusion optimization, the compiler can just use this
> information, rather than change the kind of program that the user
> writes.

That is a valid point. However, one of the benefits of being able to
manipulate the concatenative program syntactically while preserving
meaning is now lost.

> (Maybe map* would be good for documentation purposes or something, but
> this is not a good justification for it.)

There is a precedence for such a naming system in Scheme. Effectively
"map*" is a version with side-effects. We could perhaps call it
"map!". For Cat which was intended for use as an intermediate language
at least, the goal of being able to apply simply term rewriting to the
syntax of a program (e.g. identify "[f] map [g] map" and rewrite it
without analysis) was really quite appealing.

- Christopher

On Aug 1, 2008, at 10:01 AM, William Tanksley, Jr wrote:

>> This seems to be yet another argument against n-ary combinators where
>> the quotation is not called a fixed number of times.
>
> _This_ I don't understand. What does that mean?

I mean that in languages like Factor, allowing the quotation given to
'map' to use any amount of the stack can make things difficult -- even
if that quotation is appropriately balanced (e.g. 2 -> 2, 3 -> 3,
etc). Ideally, it would be nice to have '[F] map [G] map -> [F G] map'
be applicable in the general case, but it isn't unless you restrict
'F' and 'G' to only using one element. Of course, given that Factor
allows unrestricted side effects, there are other issues to deal with
anyway.

At least from an optimization standpoint, this is not an issue in a
language like 5th because "quotations" are supplied directly, stack
effects are always statically determinable, and side effects are
tracked on the type level. Still, it may be useful to offer both 'map'
and 'map*' so that certain optimizations (like map fusion) can be
guaranteed to the programmer more simply.

- John

On Aug 1, 2008, at 12:29 PM, Christopher Diggins wrote:

> I think I understand. To summarize with Cat type notation:
>
> map : (list ('a -> 'a) -> list)
> map* : (list ('A 'b -> 'A 'b) -> list)

I don't understand when you're allowed to omit row variables in Cat's
notation. I also think you mean "'a -> 'b" rather than "'a -> 'a".

In any case, here are the (simplified) type signatures as they'd
appear in 5th:

map[a -> b] : R (a) -> R (b).
map*[R a -> R b] : R (a) -> R (b).

> In other words, "map" accepts only 1->1 functions, while map*
> accepts n->n functions where n >= 1.

Correct.

> In Cat I simply disallowed "map" and similar combinators from
> modifying the stack. It made type analysis easier,

Why would it make type analysis easier?

> it preserved the fusion properties, and it didn't really cause any
> huge loss of
> expressiveness AFAICT.

This is arguably a reasonable solution in Cat because you have
'papply' (aka 'curry' in Factor). In 5th however, you don't, so you'd
have to use variables to write things like 'map-with':

x map-with[F] -> map[x F].

The only way to write 'map-with' without variables is to use a version
of 'map' that can call a function that uses more than one element:

map-with[F] -> map*[over dip[swap F]] nip.

Of the two, I prefer the first version for (obvious) reasons, so
perhaps this is a bad example.

Still, there are cases where 'map*', 'each*', etc, are quite handy,
even in a language like Cat. Slava has given me a few examples of
where they're used in Factor (although obviously not with those names).

- John

On Aug 1, 2008, at 12:44 PM, Christopher Diggins wrote:

> On Fri, Aug 1, 2008 at 12:33 PM, Daniel Ehrenberg
> <microdan <at> gmail.com> wrote:
>
>> In its fusion optimization, the compiler can just use this
>> information, rather than change the kind of program that the user
>> writes.
>
> That is a valid point. However, one of the benefits of being able to
> manipulate the concatenative program syntactically while preserving
> meaning is now lost.

This is essentially the point I was trying to make. How strong of a
point it is I am not sure.

> There is a precedence for such a naming system in Scheme. Effectively
> "map*" is a version with side-effects. We could perhaps call it
> "map!".

I think you need to be careful here. 'map*' acts strangely because it
is really some sort of map/fold combination. (I've not checked my
dictionary to figure out exactly what sort of morphism it is.)

I had a related discussion with Slava last night where he took issue
with the characterization of 'map*' as having side effects. Instead,
he preferred to talk more meaningfully about the additional stack
elements as loop-carried dependencies. You can find the discussion
here (luckily, it began right around midnight):

http://bespin.org/~nef/logs/concatenative/08.08.01

How come you never make it onto IRC chris? You're leaving me all alone
in my type system and rewriting interests...

> For Cat which was intended for use as an intermediate language
> at least, the goal of being able to apply simply term rewriting to the
> syntax of a program (e.g. identify "[f] map [g] map" and rewrite it
> without analysis) was really quite appealing.

How far along have you gotten on this? At least in my opinion, it is
an open question as to if function-level rewrite rules are a
worthwhile addition to other means of optimization. Their biggest
appeal to me isn't in their power (which likely isn't that great
compared to more advanced methods), but rather in their simplicity
which enables guarantees of optimization to be simply conveyed to
users of a language. Of course, such rules are useful for other things
like as proving program equality.

- John

I have been working hard on a virtual machine language called CVML
(Concatenative Virtual Machine Language). I know I have been promising
this for months, but I am trying to get a working demo up and working
by the end of September. This is in large part because I want to
submit a paper to an upcoming conference (PLDI). (If anyone is
interested in reviewing the paper, please let me know, I could really
use your help.)

For those with lots of imagination below is a teaser of the opcode
set. Please tear it apart. There are some strange ideas in it. It is
obviously not purely concatenative (for any definition), but it is
sufficiently so for quite a bit of analysis. The main advantages of
this bytecode are that (with only a few exceptions) we can easily
perform function call inlining, and automated subroutine extraction.
My implementation is an optimizing bytecode interpreter written in
C++, that translates from a high-level languages so it is taking a lot
of time to get everything off the ground.

enum OpCodeEnum
{
op_noop,

// literals
op_push_int,
op_push_char,
op_push_byte,
op_push_sub,
op_push_neg1,
op_push0,
op_push1,
op_push2,
op_push_true,
op_push_false,
op_push_string,

// stack shuffling
op_pop,
op_popd,
op_pop2,
op_pop3,
op_pop4,
op_dup,
op_dupd,
op_dup2,
op_dup3,
op_swap,
op_swapd,
op_swap13,
op_swap23,
op_swap14,
op_swap24,
op_swap34,
op_get,
op_get1,
op_get2,
op_get3,
op_get4,
op_set,
op_set1,
op_set2,
op_set3,
op_set4,

// integer comparison operators
op_lt_int,
op_gt_int,
op_lteq_int,
op_gteq_int,
op_eq_int,
op_neq_int,

// float comparison operators
op_lt_flt,
op_gt_flt,
op_lteq_flt,
op_gteq_flt,
op_eq_flt,
op_neq_flt,

// general comparison operators
op_lt,
op_gt,
op_lteq,
op_gteq,
op_eq,
op_neq,

// basic integer arithmetic
op_add_int,
op_sub_int,
op_div_int,
op_mul_int,
op_mod_int,
op_neg_int,
op_inc,
op_dec,

// basic floating-point arithmetic
op_add_flt,
op_sub_flt,
op_div_flt,
op_mul_flt,
op_mod_flt,
op_neg_flt,

// general arithmetic
op_add,
op_sub,
op_div,
op_mul,
op_mod,
op_neg,

// boolean operations
op_or,
op_not,
op_xor,
op_and,

// higher order functions
op_ret,
op_apply,
op_call,
op_tail_apply,
op_tail_call,
op_quote,
op_papply,
op_compose,
op_dip,
op_while,
op_if,

// objects
op_get_slot,
op_set_slot,
op_new,
op_null,

// arrays and lists
op_new_array,
op_count,
op_get_at,
op_set_at,
op_fold,
op_map,
op_filter,
op_filter_map,
op_range,
op_empty,
op_nil,

// types
op_typeof,

// used to find a name in the global environment.
// for example a standard library function
op_lookup,

// Used by the virtual machine for various purposes
op_reserved,

// Indicates that this is an extended byte-code set
op_extended
};