PRL Blog

Note that I was specifically talking about the sequential case, not multi-threaded languages.

OCaml has had one since the 1990s [1]; it's a fairly standard generational, compacting collector with incremental collection for the old generation. Lua has had an incremental GC since version 5.1 (in 2006); as it's frequently used as a scripting language for video games, it's safe to assume that pause times aren't much of an issue.

The problem is that virtually every language since then has pretty much decided to have all threads use a global shared heap. Once you do that, you run into all kinds of challenges, such as root discovery from thread stacks without stopping the world. That said, there are plenty of languages that have this option, anyway; it's simply more challenging, not impossible.

Languages that are single-threaded maintain thread-local heaps don't have the problem. Python and Ruby (unlike Lua) have issues for historical reasons (they started out with basic reference counting and mark-and-sweep collection, respectively, and then had to maintain backwards compatibility [2]).

Intermediate designs (having both thread-local heaps and shared heaps at the same time) are also possible, but that design space hasn't been explored much.

[1] http://prl.ccs.neu.edu/blog/2016/05/24/measuring-gc-latencies-in-haskell-ocaml-racket/#ocaml-version

[2] I think that in principle one could make the cycle detector in Python incremental (it's basically a form of trial deletion); Ruby…

01. [On the criteria to be used in decomposing systems into modules – David Parnas](https://prl.ccs.neu.edu/img/p-tr-1971.pdf)

02. [A Note On Distributed Computing – Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall](https://www.cc.gatech.edu/classes/AY2010/cs4210_fall/papers/smli_tr-94-29.pdf)

03. [The Next 700 Programming Languages – P. J. Landin](http://thecorememory.com/Next_700.pdf)

04. [Can Programming Be Liberated from the von Neumann Style? – John Backus](http://www.csc.villanova.edu/~beck/csc8310/BackusFP.pdf)

05. [Reflections on Trusting Trust – Ken Thompson](http://users.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf)

06. [Lisp: Good News, Bad News, How to Win Big – Richard Gabriel](https://www.dreamsongs.com/Files/LispGoodNewsBadNews.pdf)

07. [An experimental evaluation of the assumption of independence in multiversion programming – John Knight and Nancy Leveson](http://sunnyday.mit.edu/papers/nver-tse.pdf)

08. [Arguments and Results – James Noble](http://www.laputan.org/pub/patterns/noble/noble.pdf)

09. [A Laboratory For Teaching Object-Oriented Thinking – Kent Beck, Ward Cunningham](http://c2.com/doc/oopsla89/paper.html)

10. [Programming as an Experience: the inspiration for Self – David Ungar, Randall B. Smith](https://suif.stanford.edu/~lam/cs343/programming-as-experience.pdf)

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-stack-based-programming-languages/

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

Do they really insert extra dynamic checks?

Is Sound Gradual Typing Dead?
https://news.ycombinator.com/item?id=11041272

http://prl.ccs.neu.edu/gtp/research.html

It was my understanding that MyPy was purely compile time with no runtime checks. But I could be wrong. Gradual Typing as implemented in the original paper would lead to much much slower code. The weight of a static language bolted onto a dynamic runtime for the worst of both possible worlds. Sufficiently abstract Python code is almost un-typable.

I think eventually we will get there, where one can explore a program in a dynamic language and ship a correctly statically typed one. Types are only the beginning.

The term information hiding used in this thread is very confusing (to me, at least).

I believe David Parnas introduced it in 1971 to mean that a program's design was sliced along shared units of concerns (things that vary together) rather than "steps in a flowchart".

https://prl.ccs.neu.edu/img/p-tr-1971.pdf

I believe what you are trying to convey is called "data abstraction", as for example used by Reynolds, 1975;

mentioned here:
https://www.cs.utexas.edu/~wcook/papers/OOPvsADT/CookOOPvsADT90.pdf

explained here:
https://link.springer.com/chapter/10.1007%2F978-1-4612-6315-9_22

I like to refer to computing history as much as the next person, but the references in this post [0][1][2] came across as rather weak and mostly anachronistic.

Computer hardware, networking, and server software has evolved by leaps and bounds over the last 5-10 years, let alone 50!

[0] https://prl.ccs.neu.edu/img/p-tr-1971.pdf (1971)

[1] https://en.wikipedia.org/wiki/The_Mythical_Man-Month (1975)

[2] https://en.wikipedia.org/wiki/Fallacies_of_distributed_computing (1997?)