5
$\begingroup$

There are some groups of question on the site which are not tagged well, especially outside of "core" TCS (which we have covered pretty well, I think).

One of these are questions about . Many questions have only the main tag, or maybe tags about other concepts if the question is a comparative one.

Can we tag these questions better? In particular, there are quite some that involve transforming λ-terms into each other; I think these should have their own "technique" tag (similar to which does not quite apply here).

I would ask users knowledgeable in this area to propose a (small) set of tags that can help differentiate the space of λ-calculus questions better. Attempts at generalisation so tags can be used for many calculi (e.g. π-calculus, μ- calculus) are appreciated.

Ideally, suggestions would contain (stubs for) tag wikis, too.

If you think another area is covered badly by existing tags, please open another meta discussion!

$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

(I'm not an expert on lambda calculus, but I was taught by one.)

I don't think our questions about lambda calculus are particularly badly tagged.

I've retagged one question which only had the tag. The remaining questions which are only tagged or only are about elementary to absolute-beginner considerations of beta-reductions (and sometimes eta-reductions) between lambda terms and encoding of data structures such as Church numerals (with one exception which I've just closed as unclear).

I don't see much room for more precise tags for the bulk of these questions. Here are candidate tags that could complement for which at least one question exists on the site:

Going in the other direction, some of these very elementary questions are really about term rewriting, as they are simply about applying the beta reduction rule. We have a tag for that, or rather two which I've just merged (not sure about the direction): = . I think this is the “technique” tag that you envision. But these elementary questions are not very interesting to people interested in rewriting systems in general.

I don't see any room for general aspects of rewriting systems that would lead to other tags being applied to any existing question.

Incidentally, when I see reductions, I always think of rewriting systems first. Using the tag name for the use in complexity and computability theory feels strange to me. Rewriting wouldn't compete for the tag name even if the site didn't have a strong bias towards these fields, as questions about reduction are about .

$\endgroup$
8
  • $\begingroup$ What you write makes sense, but I'll let experts be the final judges. Just a few comments: 1) "elementary questions are not very interesting to people interested in rewriting systems in general." -- this case can be made for all general tags, I think, so no harm done. 2) What are you saying with your last paragraph -- should we find a better way for complexity/computability reductions (I don't like the name choice myself as the term is heavily overloaded), or do you think it's fine? $\endgroup$
    – Raphael Mod
    Commented Sep 17, 2013 at 19:44
  • $\begingroup$ Come to think of it, what do you think of using programming-languages and functional-programming on questions about lambda-calculus? I noticed a few instances. $\endgroup$
    – Raphael Mod
    Commented Sep 17, 2013 at 19:45
  • 1
    $\begingroup$ @Raphael Some of the questions with both lambda-calculus and either programming-languages or functional-programming are about applying lambda calculus to the study of programming languages and thus properly tagged. A couple could lose the FP or PL tag, I'll make a pass. The one that bothers me is logic, it's used on plenty of questions that have nothing to do with logic except in the sense that all math is applied logic. $\endgroup$
    – Gilles 'SO- stop being evil' Mod
    Commented Sep 17, 2013 at 20:01
  • 1
    $\begingroup$ @Raphael While reductions is slightly prone to confusion, the rewriting use wouldn't use “reductions” as a tag name, so I think it's ok unless you can think of a more descriptive name (“problem-reductions” would be worse). $\endgroup$
    – Gilles 'SO- stop being evil' Mod
    Commented Sep 17, 2013 at 20:02
  • 1
    $\begingroup$ @Raphael I've retagged cs.stackexchange.com/questions/14133/…, the rest warranted the FP or PL tag. $\endgroup$
    – Gilles 'SO- stop being evil' Mod
    Commented Sep 17, 2013 at 20:08
  • $\begingroup$ Regarding reductions, what about turing-reductions? As far as I know, that's the most general term in computability and complexity. The logic tag, I may have introduced that a couple of times myself when the question seemed to be about a logic calculus thing. Feel free to retag as you see fit. $\endgroup$
    – Raphael Mod
    Commented Sep 18, 2013 at 9:01
  • $\begingroup$ @Raphael I like “Turing reduction”, but isn't that applicable only to computability and not complexity? $\endgroup$
    – Gilles 'SO- stop being evil' Mod
    Commented Sep 18, 2013 at 10:07
  • $\begingroup$ Wikipedia says (and I agree) that the "complexity-reductions" are special cases, i.e. restrictions of what the reduction function may do (they are all computable, which is pretty much the only restriction of Turing reductions). It may invoke unwanted associations, that's true. $\endgroup$
    – Raphael Mod
    Commented Sep 18, 2013 at 10:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .