Comment by n_c | Hacker News Reader

Comment by n_c | Hacker News Reader

Parent Full thread

The execution model of rhoScript isn't so different from that of any other concatenative language. There are two differences I can think of at the moment:

- The lazyness of lists. "1 naturals (add) map" will produce an infinite list of integers from 1. This introduces some interesting difficulties. For example, what would you expect "1 naturals (add) map 2 swap 5 take" to produce? It will clearly either be (1 2 3 4 5) or (2 3 4 5 6). I pick the first because it produces less surprising results. So, when map is called, it saves the state of the stack, so it doesn't end up seeing the 2 pushed on the stack.

- I added lexically-scoped "arguments" to functions because I found them useful. The commands "arg-[a-d]" will "remember" the top four values on the stack, even if the lazyness of the language changes the top four values on the stack by the time it reaches these commands.

I guess one other difference is that functions here are typed, but that's not really a fundamental difference with other concatenative languages.

As for F and XY, I haven't looked in to them much. A cursory glance, however, leads me to believe that when pushed to their limits, I'd expect the arithmetic-encoded programs to be significantly shorter. The 22 different tokens in the 8 queens program condense in to 17 bytes. (And, this assumes that all functions of a valid type are equally likely to be called -- I'd expect most programs to get shorter once I spend some time figuring out reasonable weights for the encoder). That said, I definitely see some things I'm going to steal from those languages.

How are you doing the concatenation typing? Is it like Cat's type system?

http://cat-language.com/

It's very similar. There are major differences with how functions are typed, however. Namely, in Cat, they are, and in this, they are not. There's a good reason for that, though!

Imagine you write the program "(add print) call". Clearly that function takes two integer arguments. Right?

Well, that's only because you're looking at the high-level version. Compile it down and you get AE 1D B0 88. If you run it on two integers, you get the sum, as expected.

But what happens if you run it with a list on the stack? Then it happens to run the program "(arg-min arg-a) call". Why? The arithmetic-decoder just sees some bytes, and it decodes them to match the correct types.

Representing the actual type of functions would require more bits, make programs longer, and so I haven't implemented that. I'm still pondering things to do here.

This is the first time I've seen dynamic typing arising from simple systems as opposed to making the implementation more complex.

Beautiful!

From a Haskell background I want to suggest typeclass mechanisms to enable valid polymorphism types. The compiled form can be the same, but the classes help to note that the initial syntax version has that kind of polymorphic effect.

IMO a types stack languages does not make much sense. If the stack side effect is typed a function does alway have to return the same number of arguments and consume the same number. That IMO takes the by far biggest advantage of postfix languages away.

Dynamic stack effects are pretty hard to reason about in nontrivial programs. Even Factor, which is largely dynamic wrt typing and dispatch, has a very limited number of words with dynamic stack effect.

Also, static types don’t necessarily preclude dynamic stack effects, as long as those effects can be characterised somehow by the type system. In my statically typed concatenative language, Kitten, I originally considered a notion of “regular” types that would let you do something like this:

    { :: r -> r End
    } :: r End a* -> r [a]

    { 1 2 3 } :: [Int]

In practice that proved to be too much of an implementation headache for not much benefit. Fixed arities also let you avoid sentinel values (as above) and parentheses (as in Lisps).

Factor's typing discipline is largely dynamic. However, they enforce the usage of annotations for higher order operations (recursive and inline) and strongly encourage the use of stack effect annotations. A stack checker, which is effectively a simple type system, proved pretty useful for debugging & optimizing.

See: http://docs.factorcode.org/content/article-inference.html

I do not have many experience with postfix languages. I mostly use RPL for simple ad-hoc programs, and I dynamic stack effects all the time. Mostly for logging and for error messages. In the "real world" one would not do that, so maybe I'm overestimating it.

Factor supports both dynamic and statically-unbalanced stack effects, but the former risks destabilizing the runtime and the later requires that defunctionalization (read: inlining) ultimately resolve to a static, balanced stack effect. It's all documented quite well in subpages of that article I linked you to.

In practice, all of the unbalanced stack-effects will become trivially balanced at word boundaries & dynamic stack-effects only occur when metaprogramming.

Reply on news.ycombinator.com