Lambda the Ultimate

However, the kinds of thing you mention is also worth discussing, of course.

And one more thing: Let's try to give concerete examples ("we study binding. Here is a let expression in Scheme, whch binds x.." etc.)

• Raising the level of abstraction available to the programmer. This path starts in... what, Babbage's engine? But we can perhaps jump to assembly, and then gradually add compiled languages, functional abstractions, heaps, garbage collection, objects, matrices and matrix operators, iterators, collections, ... (in varying orders depending on which branch of the programming-language family tree you traverse, of course.)
• Managing state, and/or trying to get along while pretending that there is no state (only Zuul.)
• Managing concurrency and parallelism, particularly when you're allowing as to how there might, actually, be state. This covers a range from database-style transactions (Atomicity, etc.) to multithreaded programming (under various memory consistency models, even.)
• Providing fault-tolerance. (Not sure how much this is language vs. algorithms, but what the hell.)
• Statically proving things about how a program will behave when it runs.
• Verifying that a program adheres to certain conventions, be they classical data typing, information flow control, etc. Typically, the theorists are interested in what they can prove statically, yes?
• Proving things about irritating logic puzzles accidentally created by programming language designers, e.g. showing that C++ template expansion at compile-time is actually Turing-complete.

Added a few minutes later, with a Duh! and a smack to my own forehead:

• Efficient implementation!
• Proving that some construct is fundamental in that it can be used to build a number of other popular constructs, e.g., the original lamba-the-ultimate papers; continuations and continuation passing style; and single-instruction Turing-complete architectures.

They break new grounds ?

Just like natural languages and mathematical languages, programming languages shape thought. One could say that designing new programming languages and studying their properties is all about removing thought barriers.

For instance, without automatic garbage-collection, programs must be in great part designed and structured around memory management. Since garbage-collection appeared, we know that there are other, often better, ways we are allowed to think about a program.

Similarly, modules and abstract data types, as seen in ML or (slightly differently) in numerous object-oriented languages, are in great part about modularisation of code. They give us reasoning/design tools for abstracting away parts of the program, hence hopefully making us more efficient at working in groups.

At least, I guess that's one way of looking at this.

Hi Sean, I was struck by your question "why" since I've been thinking about that a lot lately. At work over the last year or so (at two different employers) I noticed "why?" is often asked in a way loaded with aggression because the asker usually means "why the hell did you do that??" For some reason, it's rarely a request for information; it's a challenge that one has been wasting time on unnecessary issues.

You can see why I relate to a context you cite where justification is necessary for research. When I'm asked "why?" at work, the other person nearly always implies one of two equivalent approaches might be wrong, even when -- as always -- they are equivalent. But "wrong" merely means not to their taste. Often it's asked to question choice of syntax or even choice of language.

(At Akamai, the chief architect often asked "why did you write that in C++ instead of C?" when the same thing could always be done in either language, of course. My answer was usually, "Because I was told we wanted more C++." And he'd say it wasn't "necessary" and order conversion to C. When comparing two approaches in two different Turing complete languages, it's odd when a person implies one language should only be used when necessary, as if only one could yield some effect.)

When someone asks "why?", they nearly always imply a shared set of standards for weighting values, so that X is better than Y, for some choice of X and Y. But it's seldom the case with two coding practitioners. Folks typically differ (dramatically) on desired levels of simplicity, abstraction, indirection, syntax verbosity, and a lot of other personal cognitive preferences. All of them might affect maintainability, code longevity, and stability; but judgment on this is highly subjective.

In the hardware field, cost/benefit analysis might be easier to perform. "More expensive" is easier to measure if it is manufacturing cost. And "faster" is easier to measure if a benchmark will capture it. But in software, cost and benefit are both hard to measure, and subjective opinion differs enormously, often depending on basically religious principles.

In software, cost is often a function of what happens in a developer's mind, either when first creating software, or when updating it later, or when sharing with other developers with attendant effects in their own minds. Cost is whatever makes software slower to write, or buggier to run, or harder to move forward in evolutionary changes. Measuring this is nasty, and comparisons that drive answer to "why?" can seldom be justified between two developers.

So when one developer asks another "why?", often they mean, "Why didn't you write this exactly the way I would have written it?" The answer is typically, "Because I'm not you." So the asking person is playing a dominance game, basically, but disguised as rational discourse.

p.s. (Folks might remember me from my treedragon site, when I still went by David McCusker instead of Rys McCusker. I think this is the first time I posted here.)

I think this is a quite good example on how humanistic and non-technical PLT really is.

Thank you, Rys, for this discourse on the human side of computer programming from an obviously experienced point of view.

So when one developer asks another "why?", often they mean, "Why didn't you write this exactly the way I would have written it?" The answer is typically, "Because I'm not you." So the asking person is playing a dominance game, basically, but disguised as rational discourse.

This is unfortunate, but I can see how it is true. Personally, in my graduate work, I have come to see the importance of understanding why something is done. To me, understanding the "why" tells me how something is useful, where it fits in the jigsaw puzzle, and what I could do with it. Perhaps it comes from reading too many papers in my field, but I need to be motivated before I can come to acknowledge any proposed idea. Too many things haven't worked (even though they were published) and it takes some experience to know if others will succeed or fail. Computer architects tend to take on a very skeptical (sometimes even negativist) attitude due to this fact.

What I would like to know is, do these dominance games or religious battles occur even in PLT research? Yes, we see it all the time in popular literature, but I haven't noticed it too much in the papers posted on LtU. Well, except for the static type-checking vs. dynamic type-checking battle perhaps... ;)

It is easier to answer the why question about specific reseach projects. For example, concerning a recent paper I mentioned on the home page, you might say that "aliasing causes bugs, and linear types might provide part of the solution."

Answering the why question regarding the entire enterprise of PLT (or any other field) is much harder. My personal answer would be that (a) the subject is intrinsically interesting and worth studying (the same way fundamental science is), and the study is intellecuatlly rewarding and (b) there are many reasons to think that sound PLT can improve both the experience of programming and the quality of software.

While I personally am strongly in the camp that opposes the Sapir-Whorfian hypothesis, I believe that like most strongly-held beliefs, there is an aspect of truth to it that ought not to be overlooked. Surely it is possible for humans to "think" visually, musically, spatially, etc. But what verbal thinking allows is something special. The essence of programming is names and values. So what's in a name? A *lot*. A name, or a word, is a social contract regarding concepts. A name has meaning when we agree that it refers to particular mental states that we have. Whether those mental states correspond to visual stimuli, aural stimuli, somatic stimuli, or imagined stimuli doesn't matter, which is exactly what makes words powerful. What the word does is give us a tag for a potentially complex state so that we don't have to describe that state in terms of its components. In a word, a word is an abstraction.

Jargon exists because it is useful for practitioners in a field to name commonly referred constructs with a simple tag. Imagine if we had to spell out what "recursion" means every time we referred to the concept. The very tedium of doing so would slow down any effort to carry on a discourse about the subject. When we coin new words, we are creating new building blocks of thought in the sense that we are creating new social contracts regarding concepts that we believe are somehow fundamental due to the regularity of their appearance. Being able to say that a problem is NP-complete is much more convenient than having to say that a problem is isomorphic to TSP, which is a very hard problem that cannot be solved in a time scale which can be expressed as a polynomial of the problem size, nor whose solutions can be checked within that time frame. It makes talking about computational problems much easier, and papers can be tens of pages instead of hundreds.

When it comes to PLs, the "words" of the PL are not the identifiers, but the symbolic constructs that actually do the heavy lifting. A dot (period) in C doesn't do nearly as much as a dot in Haskell, all contexts considered. When we "expand our vocabulary" by adding new intrinsic operations (words), we are recognizing patterns of regularity that should be encoded into the language itself, rather than as patterns expressed by the language (words, rather than paragraphs). In some sense, our ability to think is expanded, because we can now address the relevant concept by a word rather than a sentence or paragraph. The language's ability to express solutions is correspondingly expanded.

So I would argue that at the highest level, the purpose of PLT is to add new "words" to the metaphorical problem-solving dictionary, because it enhances the ways we can talk about things, and that allows us to express more powerful solutions in a space that our puny brains can deal with. It is well-known that our brains seem to be able to deal with "chunks" of information in short-term memory on the order of 6-8 chunks at a time. What is surprising is that this limit appears to be independent of the nature of the chunks themselves. So one can view abstraction as the brain's "hack" for getting around this physiological limitation. By making each chunk more semantically loaded, we are able to climb the ladder of sophistication with a finite working memory. Perhaps also this is why we have a sense of "mathematical" beauty that recognizes economy and elegance.

Indeed, the words which we speak in today's generation of languages are very powerful compared to the words of languages just 50-60 years prior. And if software is to progress as a science, we need to continue identifying new patterns and naming them in powerful ways, just as physicists and chemists identify patterns in space and matter, and name them. The act of naming is powerful. It is a way for the brain to "capture" a wild beast in the space of the mind. That beast may be a shape-shifter, shimmering in different colors, and lead us to give it several names at first. But over time, we reign it in, see it for what it is, and give it an even more powerful name, to increase our dominion over it.

Different names capture different patterns. Not all patterns are universal. Not all patterns are relevant to all practitioners. That's why we have different PLs. But the justification of PLT as a whole is that there are patterns out there that are general enough to be captured and tamed. And when we bring new words into the fold, our speech becomes more powerful, and we can say much more with less.

I especially liked the last sentence. ;)

I think this is very true. It's what has interested me in Haskell (which then brought me to LtU). To be able to write a program in clear, concise vocabulary; to force myself to express ideas in different ways; to think outside the box....

Thanks again, by the way, for that response on abstract algebra in a previous thread. It helped me find some direction.

It's amazing how many years you can devote to something without stopping to ask why...

Always happy to challenge the status quo!

My personal answer would be that (a) the subject is intrinsically interesting and worth studying (the same way fundamental science is), and the study is intellecuatlly rewarding [...]

I've found that the unfortunate thing with computer architecture is, though there are a great many intrinsically interesting ideas that could be studied, the selection is limited to those useful to the industry. They have since determined that some things just will not survive (or even get published) whether due to market forces or simple disinterest.

PLT does not appear to be so tightly bound. Problems (such as aliasing or encapsulating I/O) may be derived from industry experiences and solutions may be proposed by research; however, (as Rys so clearly wrote) there may be multiple solutions for multliple practitioners. The industry may or may not pick up on any solution, but that doesn't necessary correlate to it being interesting or useful. I like how PLT has this flexibility

and (b) there are many reasons to think that sound PLT can improve both the experience of programming and the quality of software.

And this attracts me in that it incorporates logical reasoning and mathematics into a practical environment (for me, the engineer at heart).

The why of PL research...

If one agrees with "No Silver Bullet" (and I personally do), then one must anticipate that advances in the ways we make software will come only by a series of hard-won, incremental improvements. The programming languages we use shape the way we think about problems. Presumably, a better programming language can help us think about problems in a better way, which leads to shorter development times, or more secure software, or some other desirable outcome. I see PL research as doing a kind of semi-directed search through the PL design space to see which techniques a) are good frameworks for reasoning about problems and b) lend themselves to providing desired outcomes.

Perhaps there aren't enough professors here to give a useful answer? :(

Sorry, I think I contributed to off topic influence instead of sticking to what professors actually study.

Ehud Lamm: Much less outstanding research is done on other aspects, such as syntax, implementation and runtime issues, and languages as wholes (compared to the study indvidual constructs).

But I wish these things were actually studied more. :-) I was very excited by the Smalltalk blue book on the VM in the early 90's, as well as other books on the mechanics of just getting the details to bootstrap and go. Why isn't this sort of thing a study priority?

When I have noticed PL research, it has often struck me as rather more math-bound than I'm comfortable with. (Part of the reason for this is that I'm a spatial geometer type math guy as opposed to a verbal algebraist type of math guy; professionals seem to be more of the verbal/algebraic sort.)

Type theory almost always seems that way to me. I get lost reading ML source when dispatch types must be inferred from patterns. I guess I don't like deduction much in programming languages. I like literal languages favoring do-exactly-what-I-say. I like to see what patterns you can get to emerge from that starting point.

Is there any tendency for favor research topics that are harder for laymen to understand, because it increases the factor of eminence due to exclusion? (This reminds me of research into writing styles that shows folks are perversely likely to grade writing as better if it is more obtuse rather than clear.)

They actually are quite closely related and come together in fields like categorical logic, topos theory, and theory of fibrations. A key idea is that objects in a cateogry are collections of equivalent proofs and morphisms functions between the proofs. Relevant authors you can google are Lambek and Scott, Johnstone, Bell....

Although I believe there is much to be learned by mastering specific programming languages, I don't think this is where all the value is. Programming language theory should be about going beyond specific instances.

Think of an algebrist that knows how to operate in various algebraic systems, but has never noticed the fact that there is an underlying theory that concerns all structures that are groups, or rings, or whatever. He would be missing a lot of what lies deep in the world of algebraic structures.

Going beyond specific systems and noticing their underlying theoretical principles allows us to go deeper and look farther. This is another instance of the saying to avoid losing the forest for the trees.

...where did the programming languages come from? Why are they the way they are? How can we describe them? How can we define them? How can we make them better? How can we compare them? Now that's what I'm talkin' about. ;)

"This book brings you face-to-face with the most fundamental idea in computer programming:

The interpreter for a computer programming language is just another program.

I totally forgot about it. I should add it to the quotes page...

In addition, the reason you study them is because they are cool and they make you (personally) more productive.

But this aspect of the question wasn't the intention of this thread.

The reason I posted this question was that it seemed to me that some people don't realize that the personal reasons, and the kinds of tricks you and me love about programming, are not the same thing as programming language theory.

People not following the academic papers don't always realize that academic reseach is rarely about questions such as "is multiple assignment easier in Java or in Python".

I am not dismissing practical questions. I just wanted to make the distinction clearer. There's a real gap, and conversation would probably be easier is this gap is known and accepted.

P.S

Being a contributing editor, Olivier, you can help set the agenda! Simply post something to your liking... ;-)

LtU is not supposed to be just about theory. However, given that there is a large, active and successful body of PL theory, which has had a great influence on programming languages and the practice of programming over the years, discussion related to programming languages which takes place without being at all grounded in theory is somewhat suspect, to say the least.

So perhaps the headline should be something like "The Programming Languages Weblog, with Associated Discussion Informed by Theory". Doesn't exactly roll off the tongue...

I was thinking about the second formulation when I posted the thread, but both are ok, I guess...

There was a nice discussion about this in http://lambda-the-ultimate.org/comment/reply/1067/11335
In resume, in OO, data and operations are together with mutable state, and in ADT, data and operations are separate and data is stateless.

ADTs can have date. I would say that objects are an extension of the ADT idea in which:

1) types (interfaces) can have multiple coexisting implementations (classes)
2) types can extend (subtype) other types
3) type implementations can be constructed by inheriting from and overriding other implementations

Actually, a page with a Who's Who of PLT, listing the big names in each major area of study might be useful to people looking for more information on topics. It might also serve to give a high-level perspective of PLT by showing which areas get the most attention (though that might be more accurately determined by looking at the number of papers published).

A couple of useful pages:

Mark Leone's Programming Language Research Page.

Teaching About Programming Languages Project

Matt Markland
marklandm@acm.org

Everything I've seen, from Dijkstra to Wadler, seems to me to be fundamentally concerned with increasing the increases in expressivity.

Being a run-of-the-mill corporate programmer, I've always felt more like I was fighting the programming languages I've used rather than working with them, hence my lurking here. I'm no researcher in PLT, but a novice trying to wade through things that are too complex for what passes as my initial education. The thing that's driven me through this frustrating madness the whole time is expressivity. We can make machines, say, a two-bit adder, that do something. Then we can layer on abstractions until we get to the "zipWith" function. That's a big win. Thus, I think that PLT really drives from two questions:

1. How do/can we gain expressivity over what already exists (the 2-bit adder)?

2. How do we make the new expressivity actually practical to use, given what we currently have to work with?

(Then, perhaps, there's the meta-question of "what is expressivity and how do we adjudge something to be an increase in it?" Sort of an "I know it when I see it" thing, I suppose.)

Type systems, for example, enable us to express facts or constraints about what it is we manipulate with our programs. Similarly with Pi-calculus. All these things, at least to me, fall into this one kernel.

Otherwise, we wouldn't have programming languages; we'd have clever arrangements of switches.

You just reminded to look up ACM Computing Surveys and, lo and behold, look what I found!

Lowering the barriers to programming: A taxonomy of programming environments and languages for novice programmers (14MB PDF).
Caitlin Kelleher, Randy Pausch. ACM Computing Surveys. Vol. 37. No. 2. Jun 2005.

Since the early 1960's, researchers have built a number of programming languages and environments with the intention of making programming accessible to a larger number of people. This article presents a taxonomy of languages and environments designed to make programming more accessible to novice programmers of all ages. The systems are organized by their primary goal, either to teach programming or to use programming to empower their users, and then, by each system's authors' approach, to making learning to program easier for novice programmers. The article explains all categories in the taxonomy, provides a brief description of the systems in each category, and suggests some avenues for future work in novice programming environments and languages.

Front page material?