Lambda the Ultimate

Anyway, I was wondering whether anyone knew whether the ability to do so (create circular data structures) was intimately connected with some property of the language that might be otherwise useful (assuming that circular data structures in themselves are not that necessary). Is this a warning sign that my language is not sufficiently expressive, or just a surprising oddity?

Incidentally, I believe I can accomodate both eager and lazy evaluation, continuations, and first class functions (and I believe a HM type system will be possible - I hope to add it later), so this was a bit of a surprise ("my baby can't do that?!").

I suppose the answer to my question above will be "well, you need to understand why this isn't possible", which I will of course try to do (there's just a lot to think about at once - although it is great fun; I'm writing notes in my on-line diary, but can't publish them on my site until I get back to Santiago - various technical nuisances that boil down to a power cut outlasting my UPS...)

This is not something worth losing sleep over, I don't think. Even in SML, there's no shortage of people who dislike refs enough that they don't use them even to build graphs.

what about with lazy evaluation? this is a stack based language, so the concept of lexical scope (and closures) doesn't exist in the same way - i *think* that means lazy evaluation won't help either.

(so "letrec" doesn't carry across directly either, but the nearest equivalent is "safe", i believe)

(and i spent last night removing refs from some sml code, so i guess i won't be too upset without anything similar ;o).

http://pobox.com/~oleg/ftp/Scheme/parent-pointers.txt

It tries to solve a more general problem -- representing cyclical data structure, "tree" with parent pointers -- in a strict language. The section "A genuine _tree_ with thunked parent pointers" will perhaps be of most interest. It is indeed highly surprising that the approach worked out. It took me far longer to describe the code than to write it.

incidentally, i used the dictionary solution you describe in a similar problem last week (and for similar reasons) - my first reaction was that it was a terribly crude way of solving the problem (brought back memories of doing everything with fortran arrays!); after a little more thought i decided it was actually rather neat; finally i was left wondering why i'd not seen anyone else mention it, so it was reassuring to see it there.

I don't think it's a problem, as long as the language is Turing-complete. Even if you lack the ability to create circular references, you can still model circular structures indirectly by using indexes (or, more generally, paths or contexts). For example, to model a graph you can order the nodes and present the edges as an adjacency matrix.

I can imagine that the equivalence between modeling circularity directly via reference-like things and indirectly using indexes is a consequence of Turing-completeness, since it is obviously similar to the fact that Turing machines can emulate each other, metacircular interpreters and all that sort of stuff.

what about with lazy evaluation? this is a stack based language, so the concept of lexical scope (and closures) doesn't exist in the same way - i *think* that means lazy evaluation won't help either.

There is nothing preventing a `stack-based language' (this is a meaningless term, BTW, like `interpreted language') from implementing call-by-name, if that's what you mean.

i can see your point, to some extent (it's one of the things i've learnt while trying to work out how everything fits together), but what do you suggest instead for the intuitively obvious common approach to joy and forth that is not expressed in the same way in languages like ml, scheme and haskell?

(i'm not sure call by name is very useful terminology, since values are not named (they're identified purely by position on the stack). rather the operator is itself pushed on the stack of values and only evaluated if an attempt is made to access the stack beyond that point. i have no idea what the correct term is for this because i know very little of the family of languages whose name i do not know.)

I would call Forth and Joy combinator languages because, to my mind, they are in the same category (excuse the pun) as intermediate languages like categorical combinators (which CAML uses).

And I don't think that their approach `is not expressed in the same way' in languages like ml, scheme and haskell', since, in all those languages, one can define combinators. It's just that no one wants to do it because taking advantage of lexical scope makes things much easier. (Try it yourself; you can define pop, push, roll, etc. as combinators in Haskell and use composition to juxtapose them.) Basically, combinator languages are harder to use than term languages (I dunno if this is a good word for languages with scope) for the same reason that category theory can be harder to understand than logic: a lot of effort is spent on context-manipulation, that is, popping, rolling, etc. the `stack' to get at the part you need.

The difference between combinator languages and term languages can be precisely described using some categorical concepts like simple fibrations and tensorial strength. See, for example, Hasegawa Decomposing typed lambda calculus into a couple of categorical programming languages and Power and Thielecke Closed Freyd- and kappa-Categories. If you read this stuff you will see why languages with scope are preferable: they allow to abstract over the arrangement and composition of the `stack' (context). The key insight is that abstracting a term with respect to a parameter can be expressed by an adjoint to weakening, the idea being that most subterms in the body of an abstraction discard most of the stack (context) because it only needs to be propagated down if a descendant actually mentions the parameter.

And I don't think that their approach `is not expressed in the same way' in languages like ml, scheme and haskell', since, in all those languages, one can define combinators. It's just that no one wants to do it because taking advantage of lexical scope makes things much easier. (Try it yourself; you can define pop, push, roll, etc. as combinators in Haskell and use composition to juxtapose them.)

Speaking of Forth, it's interesting to note that Curry's combinators B, C, K, and W, which form a basis for the lambda calculus, are essentially the Forth words execute, swap, drop, and dup. B, C, and K are present in the Haskell Prelude (as $, flip, and const).

Basically, combinator languages are harder to use than term languages (I dunno if this is a good word for languages with scope) for the same reason that category theory can be harder to understand than logic: a lot of effort is spent on context-manipulation, that is, popping, rolling, etc. the `stack' to get at the part you need.

I agree with this, but I do notice that Haskell programmers have drifted more and more to a point free style when they can (which is usually impractical in ML because of all the eta-expansion required by the typechecker).

A striking example of the differences between combinator and term languages is Nielson and Nielson's two-level semantics (none of the papers appear to be online). They use a term language for one level and a meta language for the other level. The practice seems to have been dropped in favor of a pair of term languages in subsequent work (like Danvy and Filinski's CPS translation in Representing Control: A Study of the CPS Transformation).