Lambda the Ultimate

Linear Logic and Permutation Stacks--The Forth Shall Be First by Henry Baker, 1993.

Girard's linear logic can be used to model programming languages in which each bound variable name has exactly one "occurrence"--i.e., no variable can have implicit "fan-out"; multiple uses require explicit duplication. Among other nice properties, "linear" languages need no garbage collector, yet have no dangling reference problems. We show a natural equivalence between a "linear" programming language and a stack machine in which the top items can undergo arbitrary permutations. Such permutation stack machines can be considered combinator abstractions of Moore's Forth programming language.

I remembered this paper while chatting with a friend who's designing a stack-based instruction set and looking for relevant compilation techniques (imagine compiling C to Forth). Do you have some relevant references?

Today I found this paragraph particularly intriguing:

Since Forth is usually implemented on a traditional von Neumann machine, one thinks of the return stack as holding "return addresses". However, in these days of large instruction caches, in which entire cache lines are read from the main memory in one transaction, this view should be updated. It is well-known that non-scientific programs have a very high rate of conditional branches, with the mean number of instructions between branches being on the order of 10 or less. Forth programs are also very short, with "straight-line" (non-branching) sequences averaging 10 items or less. In these environments, it makes more sense to view the return stack itself as the instruction buffer cache! In other words, the return stack doesn't hold "return addresses" at all, but the instructions themselves! When a routine is entered, the entire routine is dumped onto the top of the return stack, and execution proceeds with the top item of this stack. Since routines are generally very short, the transfer of an entire routine is about the same amount of work as transferring a complete cache line in present architectures. Furthermore, an instruction stack-cache-buffer is normally accessed sequentially, and therefore can be implemented using shift register technology. Since a shift register can be shifted faster than a RAM can be accessed, the "access time" of this instruction stack-cache-buffer will not be a limiting factor in a machine's speed. Executing a loop in an instruction stack-cache-buffer is essentially the making of connections necessary to create a cyclic shift register which literally cycles the instructions of the loop around the cyclic shift register.

Imagine that!

Programming languages are ultimately interfaces for people to interact with the world of computational possibilities. In that backdrop, I've recently been interested in the influence of cognitive models on programming language design and would like to hear the thoughts of the tU community on the topic.

I think the recent rise of DSLs warrants more research in this area. Past work has been largely populated by debates on completeness, compiling vs. interpreting, efficiency, dynamic vs. static, typed vs. untyped, parallel vs. sequential, distribution, designer idiosyncrasies and, not to mention, elegant vs. ugly.

While I don't deny the importance of the debates, the only one that comes anywhere near the territory of cognitive models is this notion of "elegance", but that's (as far as I know) never dealt with formally.

I see a few areas of work here -

1. Bringing schemes from models of brain function and cognition to programming languages.
2. Using findings of cognitive psychology in designing aspects of programming languages
3. Studying how we model the languages that we use and "like" - i.e. cognitive modeling of programming languages.

(Maybe others strike you.)

For an example of (1), Drescher's schema building mechanism seems a very interesting angle to building interfaces to the world of computation. (see Made-up Minds) .. and it does look like people are trying to apply that approach to special areas. Production rules (grammars) are another category. Of course, one can't forget Prolog.

AppleScript and Hypercard are simple examples of (2), 'cos they were intended to be usable by non-computer science folk and yet are powerful enough scripting languages. Elements of the language such as "tell ...", and "it" exploit our ability to refer to "at hand" and relative entities without much effort. The Logo world and, particularly, Scratch must be mentioned too. I myself got interested in this topic after I worked on adding "the" and "it" to my own scheme toy and found some cognitive modeling results such as working memory size useful in determining usage boundaries.

(3) is interesting as part of the design iteration loop.

Thots?

---
Link summary (extracted from posts) -

1. Chris Barker
2. Inform (language for interactive fiction)