Hacker News Reader

Comment by vanderZwan | Hacker News Reader

What I find a bit strange is that outside of Kitten (and Cat before it) nobody seems to have tried to make any stack-based languages with a strong typing system that prevents this. I mean, shouldn't it be trivial to follow which type of data a word expects from a stack, and which type it returns? The only limitation I can think of is words that leave a variable amount of data on the stack (one workaround would be to forbid that, or to have the type system be able to express that as well).

I suspect something like Julia's type system, with Bits types and Abstract types, would work perfectly here[0][1].

[0] https://docs.julialang.org/en/release-0.4/manual/types/#bits...

[1] https://docs.julialang.org/en/release-0.4/manual/types/#abst...

View on HN

Even with a strongly-typed system, not having named local variables introduces a lot of opportunities for error. E.g. consider the following program:

val (a,b): (Int, Int) = f(); g(b, a);

Now compare this to a concatenative program: f swap g

It's too easy to pass the two variables in incorrect order (forgetting to use swap, for example) when you are not forced to assign them local names.

Replying to you and vanderZwan.

People have investigated typing for stack-based languages before, [1] is a good overview. I've been implementing a dialect of Joy in Python and it turns out that it is pretty straight forward to implement type-inference and -checking.[2]

However, I recently realized that I was doing waaaay too much work. I reimplemented Joy in Prolog and got typing for free. Several pages of Python became two pages of Prolog and the interpreter is more powerful, I could go on. It's really weird being so excited on the one hand and so rueful on the other. This is so cool but I wasted so much time!

Anyhow, going by what you're saying the_grue about passing variables in the wrong order, I think you may have been going at it in the wrong way.

Using Joy and deriving new definitions with it I've only very occasionally had bugs related to "typos" in argument order of stack items. If you start with little pieces and build up stable conceptual interfaces as you go the process seems to flow and lead to correct code. It's like playing with Legos, or deriving a mathematical theorem.

[1] http://prl.ccs.neu.edu/blog/2017/03/10/type-inference-in-sta...

[1] http://joypy.osdn.io/notebooks/Types.html

Looking forward to reading both links tonight after work!

> It's really weird being so excited on the one hand and so rueful on the other. This is so cool but I wasted so much time!

I wouldn't be surprised if the whole struggle to create a Python implementation was necessary to get a clear enough picture of how it all comes together, which is why it then was so easy to re-implement it in a much fewer lines of code. That is how learning how to program works in my experience, at least. So don't be too hard on yourself there.

> I wouldn't be surprised if the whole struggle to create a Python implementation was necessary to get a clear enough picture of how it all comes together, which is why it then was so easy to re-implement it in a much fewer lines of code.

There was definitely some of that, but much less than you might think. The timeframe I'm talking about is a bit longer: a friend of mine tried to interest me in Prolog twenty years ago and the "penny has dropped" only now. Better late than never. But I estimate I may have wasted, outright wasted, three to five man-years of work. (I spend a lot of waking hour on programming, a lot.)

The impact of the realization is so severe that I've coined a new personal rule (the first in over a decade) to wit: Always use the highest-level language/system and only "drop-down" to a lesser paradigm if I absolutely have to (for efficiency or expressiveness.)

(The paradigm hierarchy being: Logical/Relational >= Functional >= Imperative)

I find myself pivoting from being an expert Python programmer to a tyro Prolog programmer. It's disorienting, exciting, it makes me giddy at moments. I'm already more productive, and it's easier to write bug-free code.

In the particular case of implementing Joy in Python and in Prolog, I had previously learned about Logic Programing and Unification by studying an implementation of miniKanren in Python[1], so I knew what I was doing when implementing the type inference. There even came a moment when I realized that I should reimplement in Kanren or Prolog if I wanted to do things like propagate constraints ("value types", etc...)

Then a link here on HN to "Logic Programming and Compiler Writing" by David H. D. Warren[2] finally pushed me to do it. I was in the middle of writing a compiler (to Python/Cython) for Joy and I realized that Warren's paper showed a better way.

Reimplementing Joy in Prolog was as simple as typing in descriptions of the basic relations, which are then already executable.

Something curious happened next. I went to reimplement the type inference code and when I had finished I realized that I had just reimplemented the interpreter. In other words, in Prolog, the interpreter and the type inferencer are the same thing.

(Also, ten pages of Python code became one page of Prolog.)

[1] https://github.com/logpy/logpy

[2] https://news.ycombinator.com/item?id=17674859

Reply on news.ycombinator.com