# Your thoughts on a “Programming Language Theory” proposal

A proposal for a new Stack Exchange site is gaining support:

Programming Language Theory

Quoting Robert Cartaino from an earlier similar case:

I'm not generally opposed to creating a more-specialized site when it would attract a new audience whose subject is simply spread across too many sites to attract a comprehensive audience. But I wasn't sure if [Programming Language Theory] fits that criteria.

Are the subjects being discussed generally on topic for this community?

We don't have to nit pick specific questions. Even if there is a bit of an overlap, we are generally looking at the broader scope of the site as a whole. Basically, we are trying to determine if this proposal will attract a new community, or are we just duplicating or splitting of pieces of this (or other) sites.

So between CS (and perhaps CSTheory, Stack Overflow, Programmers), does this proposal add anything to the subject space of Stack Exchange? Or would you consider the subjects being discussed a welcomed part of this site?

• my suggestion is to improve community outreach efforts by cs.se to other sites incl area 51 & attempt to recruit that crowd. this includes community ads for cs.se on other sites of which there are currently zero approved anywhere. – vzn Sep 30 '14 at 17:46
• – vzn Oct 10 '14 at 18:51

## Analysis of the questions on the proposal

I went and analyzed the 40 questions with score 10 and above that define the proposal, checking their suitability for Computer Science.

1. When creating a programming language, should I choose an LL or LR grammar?

2. What are the downsides of adding type inference of local variables? That is, does type inference preclude certain other features?

3. Is the Switch / Select Case structure worthwhile or can you get away with just If ... Else If?
Elementary, but on-topic.

4. Is it possible to make variable assignment a well-typed expression of a functional programming language?
I don't understand how the answer isn't trivially yes (maybe something got lost when shrinking the question down to a title), but anyway, this is dead on topic.

5. How to reduce the impact of garbage collection on runtime performance and responsiveness?
Too broad. A more specific question would be perfectly on-topic.

6. How is multimethod dispatch implemented?
A bit broad, but on-topic. (How it's implemented in a specific language might not be.)

7. What features of the grammar for a programming language make it easier to implement a REPL (command line interface)?

8. How does one guarantee that the commutative, associative and distributive Laws hold for a type?

9. Is there anything you can do with an eval() type function that would be impractical to implement in any other way?

10. Are there any good resources for the design of new languages available? (which features should (not) coexist, what fits for certain domains and so on)
A poster child for too broad, and not suitable for Stack Exchange. But topic-wise, no problem.

11. Should a drag-n-drop language (e.g. Scratch) actually be considered a programming language?
On-topic.

12. What are the advantages / disadvantages of indent and line break syntax (like Python) compared to curly brackets and semicolons (like C etc.)
Flame-prone, but if it can work anywhere, it's on a site with scientists who are used to backing up their assertions. Risks being too opinion-based, but on-topic.

13. What, if any, are the benefits of functional programming languages over imperative languages?

14. What limits are imposed by compilation-to-C? Does it render some language features impossible?

15. Why does C++ disallow use of unused symbols as operators? (Such as @ or \$...)
Borderline, as it's about a design decision for a concrete language. Can be made firmly on-topic by pushing towards the reasons why one would allow or disallow it.

16. What are the practical alternatives to conventional 'libraries' for packaging, sharing, and reusing code? Do any of them eliminate configuration hell?

17. What is being added to languages to ensure they produce provable code e.g. type inferencing, proof carrying code, models that can be verified, i.e. F*

18. What is a straightforward tool or process to help define a language grammar?

19. What is a memory-efficient way to implement dynamic array size?

20. To what extent do type safety and memory safety help or hinder programmer productivity and runtime performance?
That's more of a software engineering question than a computer science question. That being said, scientific analysis of software engineering is an existing, if slow to emerge, field. We're a bit waffling on these.

21. What properties makes a language good or bad for 'live coding' (i.e. programming as performance)?

22. Is type inference essential for typestate (e.g. in Mezzo or Plaid) to scale?
Firmly on-topic.

23. The C++ preprocessor is non-Turing-complete. How do languages with Turing-complete preprocessors (Scheme?) deal with unbounded compilation time?
On-topic.

24. Wolfram's new language is the first I've seen that integrates a massive knowledge base. What are the security implications of this design?
On-topic.

25. How can Hindley-Milner type checking be applied in the design of a new language?
Unclear what you're asking. But all the parts are on-topic.

26. Why do some languages use := for assignment and = for equality versus = for assignment and == for equality, and what are the advantages of either?
Syntax again, somewhere between science and history of technology. Borderline.

27. What is the smallest programming language (statements etc.) that not only is Turing-complete, but also useful for teaching programming to beginners?
Flame-prone. But if it can succeed anywhere, it needs to be asked in a venue for people who teach computer science. Here is where they hang out.

28. What features are necessary or useful for systems programming, especially embedded systems?
Too broad. Could be construed as a question for computer scientists or for programmers.

29. What's the easiest way to hook up a garbage collector to the object code generated by a new compiler?

30. What is the cleanest way to define a type that represents a process with multiple input/output streams? (parallel access, multiple possible errors)
The question needs clarifying: is it about language design (→ CS.SE) or about API design (→ SO)?

31. How can I go about implementing a language that allows concurrency?
Too broad, obviously. All the steps would be on-topic.

32. What features are essential for a PL to serve as a 'systems' language?
Duplicate of #28, which is too broad and borderline.

33. What are the known lexer+parser algorithms? Can an exhaustive list of all strategies be created how to transform textual source into AST?

34. Futamura projection is difficult to implement. If we go for all-out speed or all-out size (tersity), does it become straightforward?
On-topic.

35. Is it possible to integrate Session Types into imperative language?

36. What are the real life programming constructs depending on dynamic typing that are so useful that they can justify using a dynamically typed language?

37. Are there any technical reasons why one language cannot be appropriate for systems/scientific/web scripting etc. usage?
Too broad. Could be ok if more focused, but would also be ok on Programmers.

38. Shouldn't product types be commutative? (Int * String = String * Int) just as sum types (Int + String = String + Int)
Definitely on-topic.

39. In a certain language, the relative position of each token fully defines its semantics. What are the brackets, commas and other punctuation for, then?
On-topic.

40. Where can I find a description of the algorithm for a functional language that checks that an algebraic type is fully covered by the match function?
On-topic.

Analysis of the data:

• 33 questions out of 40 are unambiguously on-topic. The remaining 7 are borderline, either because the title given here is ambiguous and could go either way, or because the topic is at the limit of CS. All the remaining 7 would be at home on Stack Overflow or Programmers if not on CS.
• Half the questions are too broad. While this is a common problem on Area 51, I think this crop of questions is below average, which doesn't bode well. It looks like most of the questions were written by non-experts.

Conclusion:

The proposal is a subset of Computer Science. Furthermore, it is likely that Computer Science would have better expertise to answer these questions than the founding audience of the proposal.

## My personal opinion

I am a former academic in the field of programming language theory. I consider Computer Science perfectly adequate for questions in that field. I would find it harmful to split computer science into niche sites. Niche sites do make some sense for cross-disciplinary topics such as cryptography or machine learning, but for core computer science topics, there is no sense in forcing people into cells.

CSTheory makes sense because it caters to a distinctive audience — researchers in theoretical computer science. CS.SE already caters to the audience of the PLT proposal: computer scientists who actually know how to design a language, students thereof, programmers who want to understand the languages they're using, amateurs who want to dabble in language creation.

This proposal is pointless. Interested people should ask their questions here.

• While I tend to agree that many of these questions look like they're on topic, something about your analysis gives me pause. In my perception, CS.SE has developed a culture that is a bit different from when the site was starting. I have to imagine this culture would not be warmly receptive of the kinds of questions that are in the proposal; you're among the more tolerant long-timers, and even you think more than half aren't good for this site as-is. I could imagine SE sites - possibly new ones - with a more receptive culture welcoming all of these questions... I'm not sure they're as – Patrick87 Sep 30 '14 at 17:09
• fundamentally bad as you imply. Programmers, for instance, is much more receptive than CS is, after accounting for on-topicness... or at least that's my impression. Stackoverflow even moreso. Seriously, it's pretty hard to ask a question on Stackoverflow and not get pertinent answers. Here, you accidentally put a semicolon in your pseudocode and God help you. – Patrick87 Sep 30 '14 at 17:10
• @Patrick87 I think we live in universes where Computer Science is the same and Stack Overflow are different. SO, more receptive??? It's rather the opposite: there are quite a few questions at the CS/programming border that would get shot to death on SO or Programmers but stand a chance here — any question that asks “why” is at a high risk on SO. – Gilles 'SO- stop being evil' Sep 30 '14 at 17:25
• That may be your experience with SO, but it's not mine. It seems like a much higher proportion of "borderline" questions get shot to pieces, unanswered, here than at SO. Even questions that are typically shot down at SO get some pertinent answers. Think of it from the asker's POV: they want an answer. They're more likely to get one from SO if the question is borderline, IMHO. – Patrick87 Sep 30 '14 at 17:33
• For instance: of the last 50 questions tagged "formal-languages" on SO, all of which are CS's bread and butter, only 3 have been closed... and two of them for reasons that would have seen them closed here as well. And one of those had an accepted answer. Dare I perform the same check here? – Patrick87 Sep 30 '14 at 17:38
• I agree that it's pointless. There is already a lot of duplication of effort as it is IMO. – d'alar'cop Oct 2 '14 at 16:18
• Thank you for the thorough analysis, @Gilles. It was very helpful. – Robert Cartaino Oct 3 '14 at 1:17
• I agree with the basic sentiment. However, even stretching my view of CS there are some questions I'd say are offtopic (11,16,18,21) and some that may be, depening on the full question post (12,13,23,24,27,36). Most of these should be okay on Software Engineering and/or Stack Overflow. (If you feel discussion is in order, please take it to Computer Science Chat.) – Raphael Oct 6 '14 at 9:35
• @Raphael Quite a few of these could go either way between Computer Science and Stack Overflow/Software Engineering, depending on what's behind the title. I answered from the Computer Science perspective, so I focused on the CS interpretation. 11, 16, 18, 21 do contain a CS question. – Gilles 'SO- stop being evil' Oct 6 '14 at 10:07
• @Gilles I agree for the second list I give, but not the others. 11 maybe; 16 has "practical" right there in the title; 18 is a tool request, we have been closing such; "live coding" in 21 is not a CS artifact. But anyway, disagreement on four out of forty does not change your verdict, only gives different prognoses for what would actually work here. – Raphael Oct 6 '14 at 10:16

One observation: a majority of the users are actively involved in StackOverflow, a very practically-oriented site dealing with issues of implementation and specifics. Fewer than 10% are involved in any given "scientific" site (Mathematics/TCS/CS/etc.) While the questions in the proposal might be on-topic here, there might be a bias in the proposal stage for making questions broader, and more academic, than is intended for the real site. I'd imagine questions there would stray into two areas far too much for CS to be a useful place for them:

1. How programming languages are used in the wild. Not on topic here, squarely on topic at Programmers.
2. How programming languages are implemented. Not on topic here, squarely on topic at SO.

Questions about principles - sure, maybe they're on topic here, but we've already got a topic that will be spread across three sites. I can't bring to mind many CS questions that wouldn't be handled well by at least one of {TCS, StackOverflow, Programmers, Mathematics}, but we still had our way. Why not let them have theirs? The argument for a separate SE might get even stronger if they can incorporate the Compilers proposal.

That said, it would definitely be valuable to understand (a) why they want to be different from CS and (b) if they're OK with CS, why they proposed it in the first place (advertising problem? etc.).

• A large part of how programming languages are implemented is on-topic here (applied CS). There are many CS questions that were not handled well on the other sites! It's not about “letting them have their way”: they are us. Experts in programming language theory are computer scientists. – Gilles 'SO- stop being evil' Sep 30 '14 at 17:26
• @Gilles It's probably a simple matter of a poorly-named proposal, then. Look at the user stats. None of them are on science sites. They're into Programming Language Design, or maybe just Programming Languages in general. I'd consider what they're trying to do to be closer to Programmers than to CS. – Patrick87 Sep 30 '14 at 17:30
• @Patrick87: I proposed changing the name of the Programming Language Theory SE to Programming Language Design and Implementation. (Also, I consider what they are trying to do to be CS, as it's the kind of work I do every other day.) – Dave Clarke Oct 1 '14 at 15:31
• @DaveClarke: and I seconded your proposal to change the name (and merge with Compilers, and a substantial number of the viewers seem to agree with us. – Wandering Logic Oct 1 '14 at 16:30
• @DaveClarke: you are the only one of us that actually committed to the proposal, so could, I think, give us a useful and unique perspective on why you think the proposal has value. – Wandering Logic Oct 1 '14 at 16:32
• @WanderingLogic: Thanks for the vote. I just spotted this now and it's too late to do anything about it. I will give my perspective, soon, I hope. – Dave Clarke Oct 1 '14 at 20:18
• "I can't bring to mind many CS questions that wouldn't be handled well by at least one of {TCS, StackOverflow, Programmers, Mathematics}" -- Oh, I can. Everything undergrad algorithms is either plain offtopic or not treated in any way that is close to CS education on any site but Computer Science. (Some select gems on Stack Overflow notwithstanding.) – Raphael Oct 6 '14 at 9:38
• While I disagree with parts of your reasoning, I agree with the concern: it does not make sense to tell a community of programmers that their questions about PL design are unequivocally ontopic here -- because in all likelihood they won't be, the current question list notwithstanding. If they want to have a site for practical concerns of PL design and implementation (cf the proposed name change) and feel that Stack Overflow et al. don't work for them, I see no reason (from the Computer Science perspective) not to accomodate them. The problem is now what is "correct": the question list or the user list? – Raphael Oct 6 '14 at 9:43

Something to consider is that, as we keep specializing CS sites, the quality of CS.SE is going to lower.

A question about programming language theory is well on topic here. There is already a flood of low-quality, off topic questions. Segregating specialized questions to their own site means that CS.SE is really only left with the odd general question, and a flood of low-quality homework helps.

• That may be true, but does not address concerns the PLDI community may have (which make them create and support the proposal). – Raphael Oct 8 '14 at 8:53