text:
Print 1 to 1000 in C++ without semi-colons
Following this popular question, present your solution which prints the numbers 1 to 1000 (all of them, not the string "1 to 1000" verbatim or something funny) in C++ without using any semi-colons. Unlike the original question, you may use conditionals and loops.
Solutions not requiring any compiler flags are preferred. Please mention any you use if you go against this. Undefined behaviour is allowed, so please specify the compiler and version you're using. Preference will be given to clever solutions. This is not a shortest code contest.
(I have a solution, which I'll post in 24 hours if a similar solution isn't posted before then.)

what about your solution?

@Deb The if condition in my statement evaluated to false. :)

@macrog:May I know which of the solution makes that evaluation? :-)

There is also a similar task in SPOJ which require you to code without semicolon.

Y CAnt use constructors since the question actually wants us to answer in c++ ..create 1000 objects ...everytime constructor gets called i++ ?? :)

@marcog: But show us your solution, please. I'm very interested on it.

I would laugh one day if this question was asked for scala.

The semicolon is not needed if you know the magic word. And no need to go obfuscated.
My solution has the additional fanciness that it doesn't use any comma either ;)
#include <iostream>
#define Please(x) if (x) {}

int Number(int x)
{
    if (x > 1)
        Please(Number(x-1))
    Please(std::cout << " " << x)
}

int main()
{
    Please(Number(1000))
}

This one is underrated.

#error "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000"

+1 Hadn't thought of doing that. That'll print to stderr, which makes me think: should it not be a rule that by default solutions have to output to stdout? No quibbering over this solution though.

@marcog: I'd leave that up to the individual task. Some are ok with error output, some are not. In both cases there are ways to golf it.

If you want stdout, it's not a huge leap to turn this into the obvious printf()

The thing is, it's not the program that prints the numbers, it's the compiler.  Who'll guarantee it's written in C++?

This is the only even remotely correct answer.

main(){if(printf("1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000")){}}

@John: He probably cut and pasted it. This isn't lines from your school. :-P :-P :-P

@Chris: Good Point.  :-P

I can't believe 4 people voted for this, this is wrong, prints till 999.

@st0le, oops better fix that before i get downvotes

@gnibbler Can you post the program that generated that program? ;)

@muntoo: He probably used Alexandru's program.  ;)

This is still wrong- main has no return type.

Simple and almost idiomatic:
#include <iostream>

void loop(int low, int high)
{
  if ( low <= high                   &&
       std::cout << low << std::endl &&
       (loop(low+1, high), false) )
  {}
}

int main()
{
  if (loop(1, 1000), false) {}
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(void) {
    if (char *p = (char *) malloc(10000U)) {
        if (__LINE__ < 106 && printf("%d\n", __LINE__ - 5)) {
            if (FILE *fp = fopen(__FILE__ ".tmp", "w")) {
                if (putc('\n', fp) &&
                    fwrite(p, 1U,
                           fread(p, 1U, 10000U, fopen(__FILE__, "r")), fp) &&
                    fclose(fp) ||
                    rename(__FILE__ ".tmp", __FILE__) ||
                    system("g++ " __FILE__ " && exec ./a.out")) {
                }
            }
        }
    }
}

Ouch, painful.. Why even use a file?

Very similar to other solutions, but with a minor variation: The step variable is declared in the if condition:
#include <iostream>

int main(){
if (int x = 1)
    while (x <= 1000 && std::cout << x++ << std::endl) {}
}

You ain't returning an int...

@Vercas: Undefined behavior is allowed here :)

@Vercas, main() has implicit return 0; in C++.

This works great on my Linux machine:
#include <cstdlib>

int main()
{
    if (system("seq 1 1000")){}
}

I know, I know, ...it's not portable.

seq 1000 suffices.

   /* No semicolons - or sense - //
  //  but at least there's      //
 //   undefined behaviour      //
*/                            //
#define __ if
#define ___ int
#define ____ std
#define ______ &&
#define _______ {
#define ________ (
#define _________ )
#define __________ }
#define ___________ .
#define ____________ ,
#define _____________ <
#define ______________ >
#define _______________ ::
#define zero 0
#define five 5
#include <cstdio>
#include <vector>
___ _ ________ ____ _______________
vector
_____________ ___ ______________ _____ _________ _______ __ ________ ____ _______________
distance
________ _____ ___________
emplace
________ _____ ___________
end
________ _________ ____________
zero
_________ ____________ _____ ___________
end
________ _________ _________ ______
printf
________
"%d\n\0 I may have got a bit too carried away with the obfuscation."
____________ _____ ___________
size
________ _________ _________ _____________
five
______ _ ________ _____ _________ _________ _______ __________ __________ ___
main
________ _________ _______ __ ________ _ ________ _______ __________ _________ _________  _______ __________ __________

Try it online!

#include <iostream>

void main()
{
   if (int i = 1)
   {
      while (std::cout << i << std::endl, i++ < 1000) {}
   }
}

wheres the i coming from?

Fixed and compiled with dmc.

main returns int, always

Almost any regular-looking program can do,
(no compiler specification necessary), like:
#include <stdio.h>
 void main(int argc, char*argv[])
{
if(argc=1000)
   while(argc-- && printf("%d ",1000-argc)) {}
}

can be formulated with C++ iostream in many different ways:
 #include <iostream>
 void main(int argc, char*argv[])
{
 if( ! (argc ^= argc) )
    while( argc++<1000 && std::cout.operator<<(argc) ) {

    }
}

main returns int, always.

#include <fstream>
#include <stdlib.h>

static int write_code(std::string str, std::ofstream out = std::ofstream())
{
    if (((
        out.open("my-thousand-tmp.cpp"),
        out) << str,
        out).close(),
        system("g++ -Wall -W -O3 my-thousand-tmp.cpp && exec ./a.out")
    ) {}

}

static int add_semicolons(std::string str, size_t i = 0)
{
    while (i < str.size())
        if (str[i++] == ':' && str[i-1]++) {}
    if (write_code(str)) {}
}

int main()
{
    if (add_semicolons(
        "#include <iostream>\n"
        "using namespace std:\n"
        "\n"
        "int main()\n"
        "{\n"
        "\tfor (int i = 1: i <= 1000: i++)\n"
        "\t\tcout << i << endl:\n"
        "\treturn 0:\n"
        "}\n"
    )) {}
}

I tried to initialize std::ofstream out by passing it as a parameter (i.e. write_code(str, std::ofstream()) ), but apparently, the copy constructor is private, and an expression like this can't be passed by reference.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    while(errno++ < 1000 && printf("%d ", errno)){}
}

#include <stdio.h>
#define __INTMAX_TYPE__ struct C { C(int x) { if (x == 1001?(puts(""),true):(printf("%d ",x),C(x+1),false)) {} } }
#include <stdint.h>
main(){if(intmax_t(1),false){}}

C++ (gcc), 57 bytes
This takes advantage that the number of operands is always 1. (Not a codegolf, but I want to golf it...)
Thx to @ceilingcat for replacing printf with __builtin_printf.

main(int i){while(1001-i&&__builtin_printf("%d ",i++)){}}

Try it online!
C (gcc), 43 bytes
They are also posting C answers, I assume?

main(i){while(1001-i&&printf("%d ",i++)){}}

Try it online!

I just saw the last comment…
However I believe this is valid C++:
#include <cstdio>

int main(int argc, char**) {
  while (argc != 1001
    and std::printf("%d, ", argc++)) {}
}

compiler explorer

int main(int i)
{
while(printf("%d ",i) && i<=1000 && i++){}
}

Doesn't work in C++, you have to include cstdio,

C++11 based solution using a lambda function:
/* golf.cpp */
#include <iostream>

int main() {
    if( [] (int from, int to) -> bool {
        while(std::cout << from << " " && ++from <= to
            || std::cout << std::endl && false) {}
    } (1, 1000) ) {}
}

Compiles and works:
$ g++ --version | head -n1
g++ (GCC) 4.8.2 20131017 (Red Hat 4.8.2-1)
...
$ g++ -std=c++11 golf.cpp -o golf
$ ./golf

Bonus 1: Adjusting the range to be printed is as easy as editing the two parameters of the call.
Bonus 2: Output terminated by a new line.

Your run-o'-the-mill recursion-based answer.
#include <iostream>

int main(int i, char *k[]) {
    if(
        k != NULL && (
            i = 0
        ),
        std::cout << i << ' ',
        i < 1e3 &&
            main(i + 1, NULL)
    ) {}
}

C++ with templates
#include <stdio.h>
#include <stdlib.h>

template<int THOU> void f() { while (printf("%d\n", THOU), f<THOU+1>(), 0) {} }
template<> void f<1001>() { while(exit(0), 0) {} }
int main()
{
    while (f<1>(), 0) {}
}

Notes:

Linux version 3.2.0-58-generic (buildd@allspice) (gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) ) #88-Ubuntu SMP Tue Dec 3 17:37:58 UTC 2013
64 bit (amd64) version of Kubuntu

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Decryption by pattern analysis
You are given an encrypted string, encrypted using a very simple substitution cipher.
Problem
You do not know what the cipher is but you do know the ciphertext is English and that the most frequent letters in English are etaoinshrdlucmfwypvbgkqjxz in that order. The only allowed characters are uppercase letters and spaces. You can do basic analysis - starting from single letters, but you can migrate onto more complex multi-letter analysis - for example, U almost always follows Q, and only certain letters can come twice in a row.
Examples
clear : SUBMARINE TO ATTACK THE DOVER WAREHOUSE AND PORT ON TUESDAY SUNRISE
cipher: ZOQ DUPAEYSRYDSSDXVYSHEYNRBEUYLDUEHROZEYDANYKRUSYRAYSOEZNDMYZOAUPZE

clear : THE QUICK BROWN FOX BEING QUITE FAST JUMPED OVER THE LAZY DOG QUITE NICELY
cipher: TNAEPDHIGEMZQJLEVQBEMAHL EPDHTAEVXWTEODYUASEQKAZETNAERXFCESQ EPDHTAELHIARC

clear : BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO
cipher: HV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRP

Challenges
See if you can decrypt the text in each of these ciphers:

SVNXIFCXYCFSXKVVZXIHXHERDXEIYRAKXZCOFSWHCZXHERDXBNRHCXZR  RONQHXORWECFHCUH
SOFPTGFIFBOKJPHLBFPKHZUGLSOJPLIPKBPKHZUGLSOJPMOLEOPWFSFGJLBFIPMOLEOPXULBSIPLBP
KBPBPWLIJFBILUBKHPGKISFG
TMBWFYAQFAZYCUOYJOBOHATMCYNIAOQW Q JAXOYCOCYCHAACOCYCAHGOVYLAOEGOTMBWFYAOBFF
ACOBHOKBZYKOYCHAUWBHAXOQW XITHJOV WOXWYLYCU
FTRMKRGVRFMHSZVRWHRSFMFLMBNGKMGTHGBRSMKROKLSHSZMHKMMMMMRVVLVMPRKKOZRMFVDSGOFRW

I have the substitution matrices and cleartext for each, but I will only reveal them if it becomes too difficult or someone doesn't figure it out.
The solution which can decrypt the most messages successfully is the winner. If two solutions are equally good, they will be decided by vote counts.

What defines »most elegant«? I think that's the same thing that Chris objected in 99 bottles already. It's a subjective criterion that's quite hard to judge.

@Joey Most upvotes? Let the community decide.

Re "most upvotes": I'm unhappy to see this become a popularity contest post, not least because the post is otherwise excellent; see http://meta.codegolf.stackexchange.com/questions/110/a-modest-proposal-the-popularity-contest-tag for my thoughts on the whole matter.

What does "elegant" mean here? Best big-O performance?

@Chris, what do you suggest?

@Thomas: I think mootinator's response to my post is a good middle ground. If nothing else, it will help you articulate clearly what you are expecting. Personally, I prefer to use a cut-and-dried winning criterion, simply because that has less potential for dispute, but, the fact that mootinator responded the way he had says that reasonable people can disagree on the level of black-and-whiteness required. Which I can live with---just be upfront with what you want.

@Thomas: In other words, if you want "elegant", at least define clearly what "elegant" means, so we're not dealing with blind men and an elephant.

@chris, I've changed it to a challenge then.

Can we use a dictionary?

@st0le you can use anything you need.

@Thomas: Thanks for the revision; ability to decrypt most messages seems to be easier to measure.

The last cipher has 5 M's in a row, but there are no words that I could find with more than 4 repeating letters.  Is this an error in the cipher?

@Bass5098, nope. It's just a difficult ciphertext which has been tainted to make it more resilient to frequency analysis.

Python
I've figured out all the secret phrases, but I won't post them here.  Run the code if you care.
The code works by picking a space character, enumerating all possible substitutions for each word, then searching for compatible substitutions.  It also allows for some out-of-lexicon words to deal with misspellings in the cleartext :)
I used a large lexicon (~500K words) from http://wordlist.sourceforge.net/.
import sys,re

# get input
message = sys.argv[1]

# read in lexicon of words
# download scowl version 7.1
# mk-list english 95 > wordlist
lexicon = set()
roman_only = re.compile('^[A-Z]*$')
for word in open('wordlist').read().upper().split():
  word=word.replace("'",'')
  if roman_only.match(word): lexicon.add(word)

histogram={}
for c in message: histogram[c]=0
for c in message: histogram[c]+=1
frequency_order = map(lambda x:x[1], sorted([(f,c) for c,f in histogram.items()])[::-1])

# returns true if the two maps are compatible.
# they are compatible if the mappings agree wherever they are defined,
# and no two different args map to the same value.
def mergeable_maps(map1, map2):
  agreements = 0
  for c in map1:
    if c in map2:
      if map1[c] != map2[c]: return False
      agreements += 1
  return len(set(map1.values() + map2.values())) == len(map1) + len(map2) - agreements

def merge_maps(map1, map2):
  m = {}
  for (c,d) in map1.items(): m[c]=d
  for (c,d) in map2.items(): m[c]=d
  return m

def search(map, word_maps, outside_lexicon_allowance, words_outside_lexicon):
  cleartext = ''.join(map[x] if x in map else '?' for x in message)
  #print 'trying', cleartext

  # pick a word to try next
  best_word = None
  best_score = 1e9
  for (word,subs) in word_maps.items():
    if word in words_outside_lexicon: continue
    compatible_subs=0
    for sub in subs:
      if mergeable_maps(map, sub): compatible_subs += 1
    unassigned_chars = 0
    for c in word:
      if c not in map: unassigned_chars += 1  #TODO: duplicates?
    if compatible_subs == 0: score = 0
    elif unassigned_chars == 0: score = 1e9
    else: score = 1.0 * compatible_subs / unassigned_chars   # TODO: tweak?
    if score < best_score:
      best_score = score
      best_word = word
  if not best_word:  # no words with unset characters, except possibly the outside lexicon ones
    print cleartext,[''.join(map[x] if x in map else '?' for x in word) for word in words_outside_lexicon]
    return True

  # use all compatible maps for the chosen word
  r = False
  for sub in word_maps[best_word]:
    if not mergeable_maps(map, sub): continue
    r |= search(merge_maps(map, sub), word_maps, outside_lexicon_allowance, words_outside_lexicon)

  # maybe this word is outside our lexicon
  if outside_lexicon_allowance > 0:
    r |= search(map, word_maps, outside_lexicon_allowance - 1, words_outside_lexicon + [best_word])
  return r

for outside_lexicon_allowance in xrange(3):
  # assign the space character first
  for space in frequency_order:
    words = [w for w in message.split(space) if w != '']
    if reduce(lambda x,y:x|y, [len(w)>20 for w in words]): continue  # obviously bad spaces

    # find all valid substitution maps for each word
    word_maps={}
    for word in words:
      n = len(word)
      maps = []
      for c in lexicon:
        if len(c) != n: continue
        m = {}
        ok = 1
        for i in xrange(n):
          if word[i] in m:                      # repeat letter
            if m[word[i]] != c[i]: ok=0; break  # repeat letters map to same thing
          elif c[i] in m.values(): ok=0; break  # different letters map to different things
          else: m[word[i]]=c[i]
        if ok: maps.append(m);
      word_maps[word]=maps

    # look for a solution
    if search({space:' '}, word_maps, outside_lexicon_allowance, []): sys.exit(0)

print 'I give up.'

PHP (Incomplete)
This is an incomplete PHP solution which works using the letter frequency information in the question plus a dictionary of words matched with regular expressions based on the most reliable letters in the given word.
At present the dictionary is quite small but with the appropriate expansion I anticipate that results would improve. I have considered the possibility of partial matches but with the current dictionary this results in degradation rather than improvement to the results.
Even with the current, small dictionary I think I can quite safely say what the fourth message encodes.
#!/usr/bin/php
<?php

    if($argv[1]) {

        $cipher = $argv[1];

        // Dictionary
        $words = explode("/", "the/to/on/and/in/is/secret/message");
        $guess = explode("/", "..e/t./o./a../i./.s/.e..et/.ess..e");

        $az = str_split("_etaoinshrdlucmfwypvbgkqjxz");

        // Build table
        for($i=0; $i<strlen($cipher); $i++) {
            $table[$cipher{$i}]++;
        }
        arsort($table);

        // Do default guesses
        $result = str_replace("_", " ", str_replace(array_keys($table), $az, $cipher));

        // Apply dictionary
        $cw = count($words);
        for($i=0; $i<$cw*2; $i++) {
            $tokens = explode(" ", $result);
            foreach($tokens as $t) {
                if(preg_match("/^" . $guess[$i%$cw] . "$/", $t)) {
                    $result = deenc($words[$i%$cw], $t, $result);
                    echo $t . ' -> ' . $words[$i%$cw] . "\n";
                    break;
                }
            }
        }

        // Show best guess
        echo $result . "\n";

    } else {

        echo "Usage: " . $argv[0] . " [cipher text]\n";

    }

    // Quick (non-destructive) replace tool
    function deenc($word, $enc, $string) {
        $string = str_replace(str_split($enc), str_split(strtoupper($word)), $string);
        $string = str_replace(str_split($word), str_split($enc), $string);
        return strtolower($string);
    }

?>

Try using /usr/share/dict/words if you're on a system that has it.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/

sort: votes


text:
Nokia mystery puzzle
A friend sent me this puzzle. I'm pretty sure solving it will require some programming. Can anyone crack it? The original is here in case of encoding issues in the past below.
Did you know that...
List of prime numbers include 2 as only even number, but not 1 which is equally not divisible by any other number than itself and 1?
Indexes in most of the programming languages start from 0?
Random mess is often considered as just "life"?
Prime bits of life include open position in Nokia?
Start here:
QnšmzFyN\�Li�B§TJ�vhgUEg�XbDMb¯o�ag�wUF�Iv¶u²nGTbf�vFc�]n¡vbD^Q@utJjMthn wŸ�B�CiŸ`yuftlyF]^Qvfh¹ºK[fF�wXuHdojG�YftvTP�OwmU�gzF�zuYQ�Z[gEn�wjU�MmŽ`FDtœPC�Sw`�Raw^»DuFlVvUdEa@uiluigJQhgtc[ŒGVcBSUL�OtnouŠ�KwGTI hEtwžgtEAtl§wuZoE�Qvvc[wZ@¢Pu\T�fo[RXtGVU¶wCdySwU[{w��wGX\�\v^ŽBFS_v^^@yXPmctvPcoWvHlfBwI�FJGu�AbWcnuªOv@[j�tu@GwBNB[tX�USioimTC¶KQŸbv\iiYK£DQ�[Ich`Oš[vcwaOyJ\RoŸP�tMQvtEvLKºWbwBvtvQžf�kXv°A\TA¬�PPwU�eTT[NAIAFhvti{WOga{`H�tRJ{a`BMHUI[ZI`lIDb\BA�fa`mtd€gK\@BwCTeR�³ww�NFDCGvfQSz£t`FBZ¬wMevA^Rv¢^iSct¢Bk�\zjNBv¢tRbIwNv\¹E³tiBHxwCH«\mtt`xgNBu@hJŸkeZbQŠaaF^o_YEcLii£F`tKjU_wHt��w®wDvO^²¶[DDvAvP�uk»gAOtx]JHRuWvcu�dQmŠn_\guZD]DlHh[€DGvfb@_X¬TMt^Xun@F«twOMTIv�]ZjvKSTwdRicvxG\K�¯mStILhUvOjwb^t�xi_VJUuRwh§v`Wg]W{JoŽh]uvIdw�@QXZ]«ŽinWJ�R_ZtwB¶Vu_JStI@UUMxT`²VYyuV�l\eW]lOghv]²NP\i�xySiuJvZG±ut�`\jMEtVZuv�twv±o_Awu�vn�oŽzYTM^fEt\bWH�M�lGilw�BI²tPgTvaE`h±e�x\aafvBNmt[RŠn£hjOBEUtmhNHtAuVHP�va_uOn�\UKnuBAHW_waFwH{WLu\ZRvT[nmvv«B]Yj�JbF¹BgyDNcv^`@iAwwlweFYlwe�§fk@mnPNh�Fg\`Di[�{j¬enk�Jw{Wh^[�cYO]`MWu®�oclQTg`X�VbnXlK\\ŠMuvAw]_^®SvTA�ZSmwB`PUwYw�»\utCnl[JGcuWVTXo€¬M¡aoPuvjR[jvV[�C_zM�nUn�wP«t¿IMVtuhwFJXvº@t^UEtIhGbCXt]bVSE€CMuZktmH_uvtwuIt¹vtKy{wNC«YivUM[BG�ntCJ^aBBFdhfNlPoBE@kuTe�VC�kRwwhZdTtfnt�^v^mg�cPeh�§Au°^BtND�Jd[f\th§`jNwRvFHLu@MNwvuSR`CdSE]vaaw_wPIvRjw^HXDi°fQ�wIfNTS`ttSA¢jv XX�EP@lbDALWdzkuG€_VQvmjIX�EkTummeC³iuZokw�]uQfMcBu�SXH_Whtuv^SjyejxoEtœwStoD�xVeaOA�jtJBa_KDPwtK^\ounwfZKDDuL@[vhIDI»tvvJc\cµvWe�FPvv�beWKUtaOtvA�DMTLcPh]nDD[Qfc�R�vwštAvhfWEv^hEZPuvaCNDBQtwdvuaw@�D@dPCG�wIdttYMKvau²wQnm^mOuvaZNB�viKBvkuDj¶BuVb_§hGtkEZvSc�tttµ_GxwvGwŒ]U�[{KJcv�h�ŒKv¯vRQIPHOivFG©LtXvtljuIB\^v�zDiPBgtcm�@tUdetwYhQuvK§¥t[�HONFwcXDxH�w`t_J`�tcHXM`vO°wkQQttw§@t£uvI[TTRgvŠbf¡AJoWoRfT�dP�g�wi�S{wYYh¢uleHR@\�KnK³u\vNcx{FHkvwTMEwP�gngEvutdGOE[teWDµwKOdG�G^�wEGARcNYutf�tvmdutv@TvvF�QHkX�]tPbvšlwvVJwuKu�So@o©]LNLx�btvXGDdlLz@eVzCltvwvt�Vb£L²wPXh_viyOw[XEkSvEJdIvmVJuw�@VGTw�tjKhjv�uWmEUhI®TtwRiuŒFZ�lYtuH\\F�Ufšn®YSu�dšOk�xuVdDgmOIEBUdw@]kvtEYAt^�NutW®®ebtMhv\kfljk@±nLgEB[�fImIKt[[�jo¯OnMtwcfgKcŒuEEªvvN\�tEw`GvNQ[gUK_euho�oY[�WTKMBatvl^twJ¿cK^lAaHw�M_uFK�DvtfNªKw€šKnIv@FiI�vj°S±Ru@wid»Qt\uRvZDvZjkwuFQVH\�zW[�hMUUkNe^�famV�TGw[hJovbtugIw`t`BDwl�tlVwQmtQ^YnOA¡StuCiv�]µ€BJj`n�]BeYi[PLtY@mAoPxHxI�SwIiJ�LA±uMhPm[oPG¯OUHuKvlIbwNttX�w_k]gwmL_`m�Ef]AVvwuPiwNT±Œfw¢`XAAKuwBvkLVXNix®]lVGSo�b]XS�[foSn�]Hu®md[Lf�QJcY�ZtkŸBtjtvPH�MfYBFnLYty_dBTQzdwT@W�[uvFwama[oj@Zh�IBmYtPJEie¹�Bw]\wOwŠNdfNul^zSwwYuOu^u]`nm¬vBBvmDP^ZGRgtIxcZYbn�Dn\D¥`otŽi^E_BvD]_w u\w�EvimvuPGwH�ST^otQ¥u]�KU¥W[CR¯l@vjt€^ATNu¥HVªTvC�ifzwteG[[`gtFJŠK¡tjt�MNbkuSuMDU£lt^[E�tiLc{ZhFu`RX]tdXvYuXuTdAKvuaxPXfi[Wg]wAeukeQkuP�utvvVBExOjgi{ad`HtaiŒuvo^u@lN©Awbub\kDWµ\»WYuRYZFHR{QvojtyNbtvwDOIv_YnAu^wttunyu[VCOQWE^dTuwtuYUwl^�VXlGž�NNFk��``KQV\NWHG] ^RNkRVQw\JAO@@wdV�ev«tc[vLAZNMoYZQk�H�uFBOdt]c]ADKDfvfC[�u`®\tSX�vUDE^vu_e�JwOhmd]EMwiRHmUH]\W°vtHzWµ\@j]^mh{MAxnAPu\QuvQuekthoµRTwNX`uTcŸS_Bc�SZwJJwe_cye^ªNtwv�Wuu�ev�IQ¹B�Xt]Q_gbVkmXwh_XUL±»tvvId`wAgX�]bžmVumB«DlJ_G�D@egUoPtu�@i[S¥e\ŽFIMFweI`ut_wIOD«vZ[_wiGuVZKFk±PDG�Aw@^`vAoS{nvw``kXUSuuZWù

The challenge is over.
Thoughts are running through your mind:
"YES! I did it!"
"Was this all?"
"This was easy! I want more!"... :)

Python - 132 chars
Data is read from stdin, starting from the "Qn..."
I=raw_input()
print("%X"%int("".join(`ord(I[x/8])>>(7-x%8)&1`*all(x%f for f in range(2,x))for x in range(2,24024)),2)).decode('hex')

How do I run it? Cmd.exe text encoding doesn't allow me to paste the text correctly

I just get a bunch of gibberish.

Me too /15chars

@John, M28, you'll have to copy it from the provided link, the version in the question doesn't work at all

Hmm..I'm still getting gibberish.

Me too, again :(

I also got gibberish at first. It was an encoding issue. Try this: wget http://www.otit.fi/mystery.txt; sed '1,6d' mystery.txt | python nokia.py

That was it the whole time?!?  -facepalm-  +1

What's the result?


text:
Twinkle Twinkle Little Star
Write a program to play the popular English nursery rhyme.

(This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license. Attribution: Helix84 at the English language Wikipedia; Blahedo at the English language Wikipedia.)
Some Wikipedia articles that may be useful:

Twinkle Twinkle Little Star (has an audio clip of what your program's output should sound like)
Modern musical symbols (to learn about the music notation used above)
Musical note#Note frequency (in hertz) (the formula for calculating the frequency of each note)

Some guidelines for your submission:

Your program must use the computer's sound card. If your programming language doesn't have convenient access to audio hardware, your program must create an output file in some standard format such as WAV or MIDI.

Your program must actually generate its output. For example, embedding the Ogg Vorbis file from Wikipedia would not be allowed.

The audio quality must be acceptable. At the very least, the song should be easily recognizable. Preferably, it should sound good as well.

The focus should be on code size, sound quality, or both (explain which one you decided on). Elegant solutions would also be great. Have fun!

This is a code-golf, so shortest code wins

can I approximate note frequencies?

Why is this closed?

@programmer5000 I'd say the close reason describes it extremely well...

Even after making it code golf, I'd say this is still off topic.  The audio quality must be acceptable. is not an objective validity criterion.

@Dennis I'd say that's more like "unclear" rather than "off-topic".

QBasic (56)
A$="CCGGAAG2FFEEDDC2"
B$="GGFFEED2"
PLAY "L4"+A$+B$+B$+A$

Focus is on reminiscence :)
(Don't have a QBasic to test this though)

Works on my DOSBox installation at least, but could you modify it to play the full song?

Done. I'll go work on my reading skills :/

Hmm is this page wrong?   http://en.wikibooks.org/wiki/QBasic/Appendix#PLAY -- >An octave begins with C and ends with B.  I did half expect QBASIC to be middle C based, but that notation would suggest it's A220 based if exactly correct :)

Wow, this brings back memories of my first programming experiences with QBasic...which involved, among other things, writing cheesy music!

Great. Just change >AA< to AA and it sounds great.

@idealmachine: are you sure? A has to be in a higher scale than the other notes.

@Eelvex: QBasic seems to consider C the first note in an octave (C-D-E-F-G-A-B), as verified by testing your code without the octave shifts. I also tried PLAY "CDEFGAB>C" and it performed how I expected it to.

Technically this doesn't qualify, though, as the task specifies that the program must use the computer's sound card.

+1 for trip down memory lane! Now all I need is a DRAW command sample :)

Why the L4?  Aren't quarter notes the default?

JavaScript (214 212 211 characters)
Open Safari, Opera, or Google Chrome to JavaScript Shell, then enter the code below:
for(s="",y=192e3;x=--y/4e3|0;)s+="~ "[(y%4e3>800|x%8==1)&Math.pow(2,"024579702457245702457970"[x>>1]/12)*y/31%2];open("data:audio/wav;base64,UklGRiXuAgBXQVZFZm10IBAAAAABAAEAQB8AAEAfAAABAAgAZGF0YQHuAgCA"+btoa(s))

Unminified for readability (even then it may be hard to understand):
for(s = "", y = 192E3; x = --y / 4E3 | 0;) {
  s += "~ "[(y % 4E3 > 800 | x % 8 == 1) & Math.pow(2, "024579702457245702457970"[x >> 1] / 12) * y / 31 % 2];
}
open("data:audio/wav;base64,UklGRiXuAgBXQVZFZm10IBAAAAABAAEAQB8AAEAfAAABAAgAZGF0YQHuAgCA" + btoa(s));

With several more characters, it could work on Firefox as well, but you can change the audio/wav part to at least save the WAV file.

Works just fine in Chrome.

@mootinator: Works for me as well. I hadn't thought of checking it in Chrome -- it had not gained WAV file support until fairly recently. http://code.google.com/p/chromium/issues/detail?id=23916

Wow!  This is wonderful.

what do you mean by "with several more characters"?  What would those characters be?

@cf_PhillipSenn: When I ran the code on Firefox, I got a non-functional QuickTime Player. I had to change the code open(...) to Audio(...).play() (8 more characters) to get it to use Firefox's working built-in audio player.

This works for me in Firefox 25.

C# (Length: LOL)
So, what I did here was implement support for generating a .wav file from the string used for the QBasic solution in C# (single octave, no accidentals).  Emphasis was on:

Avoiding unsafe code blocks
Not wasting too much of my time doing it
Making it relatively simple to extend

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text.RegularExpressions;
using System.IO;

namespace ConsoleApplication1
{
    public static class Extension
    {
        public static byte[] ToByteArray(this object o)
        {
            return o.GetType().GetProperties(BindingFlags.Public | BindingFlags.Instance)
                .SelectMany(x =>
                                {
                                    var value = x.GetValue(o, null);
                                    if (value.GetType().Equals(typeof (UInt16)))
                                    {
                                        return BitConverter.GetBytes((UInt16) value);
                                    }
                                    if (value.GetType().Equals(typeof (UInt32)))
                                    {
                                        return BitConverter.GetBytes((UInt32) value);
                                    }
                                    if (value.GetType().Equals(typeof(char[])))
                                    {
                                        return ((char[]) value).Select(y => Convert.ToByte(y));
                                    }
                                    if (value.GetType().Equals(typeof(byte[])))
                                    {
                                        return (byte[]) value;
                                    }
                                    throw new NotImplementedException();
                                }).ToArray();
        }
    }
    public class Wave
    {
        public readonly byte[] WavFile;

        public Wave(string notes)
        {
            var header = new Header();
            var data = new List<Chunk>();
            var f = new Fmt(8000);
            data.Add(f);
            data.Add(new WavData(notes, f));
            var thefile = data.SelectMany(x => x.ToByteArray()).ToArray();
            header.Size = (uint)thefile.Length + 4;
            WavFile = header.ToByteArray().Concat(thefile).ToArray();
        }
        class WavData: Chunk
        {
            private static IEnumerable<byte> RenderNote(string note, int length, Fmt fmt)
            {
                double frequency;
                switch (note)
                {
                    case "A":
                        frequency = 440;
                        break;
                    case "B":
                        frequency = 493.883;
                        break;
                    case "C":
                        frequency = 261.626;
                        break;
                    case "D":
                        frequency = 293.665;
                        break;
                    case "E":
                        frequency = 329.628;
                        break;
                    case "F":
                        frequency = 349.228;
                        break;
                    case "G":
                        frequency = 391.995;
                        break;
                    default:
                        throw new NotImplementedException("Unsupported Note");
                }
                var result = new byte[fmt.SampleRate / length * 2];  // For 120BPM tempo
                for (int i = 0; i < result.Length; i++)
                {
                    double time = (i % fmt.SampleRate) / (double)fmt.SampleRate;
                    double position = time * frequency;
                    if (result.Length - i <= fmt.SampleRate / 16)
                        result[i] = 127;
                    else
                        result[i] = (byte)Math.Round((Math.Sin(position * 2 * Math.PI) + 1) * 127);
                }
                return result;
            }
            public WavData(string notes, Fmt fmt)
            {
                Samples = new byte[0];
                foreach (var note in Regex.Matches(notes, @"[A-G][1|2|4|8]?").OfType<Match>().Select(x => x.Value))
                {
                    Samples = Samples.Concat(RenderNote(note[0] + "", note.Length > 1 ? note[1] - '0' : 4, fmt)).ToArray();
                }

            }
            public override char[] Id
            {
                get { return "data".ToCharArray(); }
            }
            public override uint DataSize
            {
                get { return (uint)Samples.Length; }
            }
            public byte[] Samples { get; private set; }
        }
        class Fmt : Chunk
        {
            public Fmt(UInt32 sampleRate)
            {
                CompressionCode = 1; // Unknown/PCM
                Channels = 1;
                SampleRate = sampleRate;
                SignificantBits = 8;
            }
            public override char[] Id
            {
                get { return "fmt ".ToCharArray();}
            }
            public override uint DataSize
            {
                get { return 16; }
            }
            public UInt16 CompressionCode { get; private set; }
            public UInt16 Channels { get; private set; }
            public UInt32 SampleRate { get; private set; }
            public UInt32 AvgBytesPerSecond { get { return SampleRate*BlockAlign; } }
            public UInt16 BlockAlign { get { return (UInt16) (SignificantBits/8*Channels); } }
            public UInt16 SignificantBits { get; private set; }
        }
        class Header
        {
            public Header()
            {
                Type = "RIFF".ToCharArray();
                RiffType = "WAVE".ToCharArray();
                Size = 0;
            }

            public char[] Type { get; private set; }
            public UInt32 Size { get; set; }
            public char[] RiffType { get; private set; }
        }
        abstract class Chunk
        {
            public abstract char[] Id { get; }
            public abstract UInt32 DataSize { get; }
        }
    }
    class Program
    {
        public static void Main(string[] args)
        {
            var p1 = "CCGGAAG2";
            var p2 = "FFEEDDC2";
            var p3 = "GGFFEED2";
            var w = new Wave(p1+p2+p3+p3+p1+p2);
            using (var f = new FileStream("testfile.wav", FileMode.Create))
                f.Write(w.WavFile, 0, w.WavFile.Length);
        }
    }
}

I noticed the output wave has a very small amplitude in my answer above.  Clearly I'm missing something about how an 8 bit sample works.

Ah, fixed it.  Order of operations is important.  Sample output here: http://dl.dropbox.com/u/469380/testfile.wav

FromDigits["LOL",36]==28101 That does not look like LOL36 bytes...

C - 520
#include <linux/fd.h>
#include <time.h>
struct timespec t,p;char*q="AAHHJJH  FFEECCA  HHFFEEC  HHFFEEC  AAHHJJH  FFEECCA";x,y,z,v,w;main(){x=open("/dev/fd0",3);for(y;q[y];y++){clock_gettime(CLOCK_MONOTONIC,&p);if(q[y]>' ')for(w=z=0;z<4e8;z+=t.tv_nsec,w++){struct floppy_raw_cmd s={0};s.flags=FD_RAW_NEED_SEEK;v=!v;s.track=v;ioctl(x,FDRAWCMD,&s);clock_gettime(CLOCK_MONOTONIC,&t);t.tv_nsec=(w+1)*5e8/pow(2.,q[y]/12.)-(t.tv_sec-p.tv_sec)*1e9-t.tv_nsec+p.tv_nsec;t.tv_sec=0;nanosleep(&t,0);}t.tv_nsec=2e8;nanosleep(&t,0);}}

Why use past century's hardware like speakers and headphones? This excellent piece of code lets you play the song on a modern piece of hardware: a floppy drive!
No special requirements:

An IDE floppy drive
Linux kernel
Compile with -lm
Make sure the program can access /dev/fd0, so either chown the device or run as superuser

Bends the rules a bit, but let's for a second consider the floppy drive a sound device, and the IDE controller an integrated sound card.

I'd say this is reasonable, floppy drives are surprisingly capable for this task https://youtu.be/LkqYLOa76E0

Desmos, 148 116 bytes
The viewport has been manually changed to x=0 to 20, and y=0 to 12, because the audio trace feature in Desmos is affected by the viewport (the song will become distorted if the viewport is moved or zoomed in/out). I'm not sure if that contributes to the byte count or not. For now, I'm going to assume that it doesn't affect byte count, but please let me know otherwise if this isn't the case.
A=join(F(0,7,9,7,x),F(5,4,2,0,x))
B=F(7,5,4,2,x)
F(a,b,c,d,x)=\join([a,b,c]\{x<1,1.1<x<2.1\},d\{x<2\})
join(A,B,B,A)

Try It On Desmos!
Try It On Desmos! - Prettified
I focused on both song quality and code length (basically, shortest code in which the audio still sounds good).
To play the audio, click the join(A,B,B,A) expression (it should be outlined in blue). Then press ALT+T, and after that, H, after which you will hear the audio play if everything is done correctly.
Big thanks to @hyper-neutrino for helping me find the sequence of numbers that represents the notes in chat. I was having a very hard time finding that myself; I don't know a thing about music lol.
Explanation
This answer takes advantage of one of Desmos's accessibility features: Audio Tracing, which can play any graph as a sound. By plotting horizontal line segments at specific places in the viewport, the audio tracing will be able to play that line segment as a single note for a certain duration, depending on how long that line segment is. Specifically, the viewport is split as follows:

Bottomest vs toppest lines of the graph correspond to the range of an octave... the 12 steps within this range correspond to the half-tones in the music scale. (Source)

As I am not familiar with music at all, I pretty much have no idea what this means, but hopefully that is understandable to all of you that know music.
The next part is to actually find the sequence of y-values so that it will play the song. As I mentioned above, hyper-neutrino basically did all the work and found the correct sequence of y-values which play the song (I pretty much have no idea how he found them; something about intervals and semitones?). The sequence is as follows:
0 0 7 7 9 9 7, 5 5 4 4 2 2 0, 7 7 5 5 4 4 2, 7 7 5 5 4 4 2, 0 0 7 7 9 9 7, 5 5 4 4 2 2 0

where every 7th note (the note before each comma, and the last note) is a half note, meaning it is played twice as long as the other notes, which are quarter notes. Graphically, this means that the line segment that represents a half note is twice as long as that of a quarter note.
With that out of the way, the next thing to do is to actually put all of this into Desmos. So how are we going to do this? Well, first I found that a line segment of length 1 is long enough for a note, so each quarter note will be length 1, while each half note will be length 2.
Secondly, we will need to put a short pause in between every note, or else two repeated notes will just play as one half note instead. I decided to use a 0.1 length pause in between each note.
My plan was to construct a huge list of line segments which Desmos can graph and audio trace over.
A pattern I noticed with the notes is that every 7 notes always follows a a a b b c c d (half note) pattern. To take advantage of that, I made a function F which takes in 4 notes a,b,c,d and constructs a list of line segments in accordance to that pattern. Let's take a look at it:
F(a,b,c,d,x)=\join([a,b,c]\{x<1,1.1<x<2.1\},d\{x<2\})

The function F takes first takes in 4 notes a,b,c,d, then x because we are plotting something (the function won't work without it).
Let's first take a look at the first part of the function:
[a,b,c]\{x<1,1.1<x<2.1\}

Because of the list [a,b,c], this entire expression results in a list of 3 horizontal line segments: one segment at y levels a, b, and c. Now let's take a look at the domain restriction. It splits the lines y=[a,b,c] into two parts: one where x<1 and another where 1.1<x<2.1, effectively splitting it into two line segments of length 1 with a 0.1 gap in between them (the viewport is from x=0, so x<1 is functionally the same as 0<x<1). The audio trace will first play the x<1 segment (one quarter note), then a very short pause later, play the 1.1<x<2.1 segment (another quarter note). It does this for a, then b, then c.
Finally, this list is joined with d\{x<2\}, which is a line segment of length 2 at y level d. This will play the note d for twice as long, emulating a half note.
With a full understanding of function F, we can now encode the number sequence shown earlier with F.
First note that the first 14 notes (0 0 7 7 9 9 7, 5 5 4 4 2 2 0) are repeated at the end as well. Also, the middle 14 notes (7 7 5 5 4 4 2, 7 7 5 5 4 4 2) is just 7 7 5 5 4 4 2 repeated twice.
We can encode 0 0 7 7 9 9 7 as F(0,7,9,7,x) and 5 5 4 4 2 2 0 as F(5,4,2,0,x). By joining the two resultant lists and storing it in a variable A, we can re-use these 14 notes at the end of the song.
We can encode 7 7 5 5 4 4 2 as F(7,5,4,2,x) and set it to a variable B so that we can re-use these notes.
Finally, we can join the notes like so: join(A,B,B,A) to get the final sequence of notes. Desmos will then automatically graph all the line segments in the resultant list, which we can then audio trace over.

zoomed out and was not disappointed

Python (259)
import pysynth

c=('c',4)
g=('g',4)
a=('a',4)
b=('b',4)
d=('d',4)
e=('e',4)
f=('f',4)
g2=('g',2)
c2=('c',2)
d2=('d',2)

s=(c,c,g,g,a,a,g2,f,f,e,e,d,d,c2,g,g,f,f,e,e,d2,g,g,f,f,e
            ,e,d2,c,c,g,g,a,a,g2,f,f,e,e,d,d,c2)

pysynth.make_wav(s,fn="s.wav")

couldn't this be shortened to import ttls?

@zzz: Um, is that a joke?

no more than this is sarcasm.

@zzz: -Bangs-head-on-desk- What are you saying exactly?

@John it's obviously a koan. you should either bow or hit him.

(very late comment) For reference, here is a version -60 bytes, because it's really golfed.

bash + say + gunzip, 136 bytes
say, of course, being the OS X text-to-speech command. This is... dorky. Yeah, let's go with dorky.
printf '<117 bytes>'|gunzip|sh

The 117 bytes is, of course, a gzip stream containing unprintable characters. Here's an xxd dump of the script including those characters:
00000000: 7072 696e 7466 2027 1f8b 085c 305c 305c  printf '...\0\0\
00000010: 305c 305c 3002 032b 4eac 54d0 2d0b c9c8  0\0\0..+N.T.-...
00000020: cf4d 2c56 c8e7 c2ca 75cc cb4b c4ce 71cb  .M,V....u..K..q.
00000030: ccc7 c90b 4b4d 85f0 7252 530b 14f4 4ca0  ....KM..rRS...L.
00000040: c2de 8945 a979 4061 6cbc e0c4 dcc4 bc92  ...E.y@al.......
00000050: 8c44 dc02 2e89 7999 a939 685c 5c74 7723  .D....y..9h\\tw#
00000060: ec44 755c 6e2a 8f8a ee19 581b 8767 1402  .Du\n*....X..g..
00000070: 5c30 fa36 7e25 2599 025c 305c 3027 7c67  \0.6~%%..\0\0'|g
00000080: 756e 7a69 707c 7368                      unzip|sh

Explanation
The 117 bytes is the following script gzipped:
say -vThomas o
say -vThomas o
say -vAnna o
say -vAnna o
say -vFiona o
say -vFiona o
say -vVeena o
sleep .4
say -vKaren o
say -vKaren o
say -vSamantha o
say -vSamantha o
say -vDaniel o
say -vDaniel o
say -vThomas o
sleep .4
say -vVeena o
say -vVeena o
say -vKaren o
say -vKaren o
say -vSamantha o
say -vSamantha o
say -vDaniel o
sleep .4
say -vVeena o
say -vVeena o
say -vKaren o
say -vKaren o
say -vSamantha o
say -vSamantha o
say -vDaniel o
sleep .4
say -vThomas o
say -vThomas o
say -vAnna o
say -vAnna o
say -vFiona o
say -vFiona o
say -vVeena o
sleep .4
say -vKaren o
say -vKaren o
say -vSamantha o
say -vSamantha o
say -vDaniel o
say -vDaniel o
say -vThomas o

That's right, I just made a bunch of different say voices say "o." To figure out which ones, I wrote a script using aubionotes to get a quick-and-dirty estimate of each voice's pitch, then did a lot of trial and error the find ones that sound mostly right.
I considered trying to golf this manually, but there's so much repetition that I figured Zopfli would make shorter work of it, so I took the easy way out.

I want to hear how it sounds! Perhaps include a render of it for those of us not on OSX?

C, 277 characters
#include<math.h>
a[]={0,7,9,7,5,4,2,0,7,5,4,2,7,5,4,2,0,7,9,7,5,4,2,0},i,j,f;main(){unsigned char
b[8000];f=open("/dev/dsp",1);for(i=0;i<24;i++){for(j=0;j<8000;j++){b[j]=(i%4==3
||j/400%20!=9?1+sinf(j*powf(2,a[i]/12.)):1)*127;}for(j=0;j<8000;j+=write(f,b+j,
8000-j));}close(f);}

Perl, 203 characters
open F,'>:raw','/dev/dsp';for$a(0,7,9,17,5,4,2,10,7,5,4,12,7,5,4,12,0,7,9,17,5,4
,2,10){$b=pack'C*',map 127*($a>9||$_/400%20!=9?1+sin($_*2**($a%10/12)):1),0..
7999;$b=substr$b,syswrite F,$b while length$b}

Conveniently, OSS's /dev/dsp defaults to 8kHz mono u8; all I do here is open the device and write computed samples.

Post Perl separately; you're on codegolf :)

179 - j,f;main(i){char b[8000];f=open("/dev/dsp",1);for(i=24;i--;write(f,b,j))for(j=0;j<8000;j++)b[j]=(i%4&&j/400%20==9?1:1+sinf(j*powf(2,("@BDEGIG@BDEGBDEG@BDEGIG@"[i]-64)/12.)))*127;}

C, 96 chars
main(t){for(;++t>>16<3;)putchar(t*!!(t>>9&7|!(-t>>12&7))*(96+"#d|dOE3#dOE3dOE3"[t>>13&15])>>5);}

Produces raw 8-bit unsigned mono audio data in classic bytebeat style.  Recommended sample rates for playback are between 8 and 16 kHz; changing the sample rate changes the tempo and pitch.
To compile and play under Linux, save the code above as twinkle.c and run the following commands:
gcc twinkle.c -o twinkle
./twinkle | aplay

Some notes on how the code works:

The general trick used for bytebeat compositions like this is that putchar() takes an integer value but only prints the low eight bits of it.  Thus, putchar(t), where t is an increasing counter, generates a sawtooth wave, and the frequency of the wave can be altered by multiplying t with a suitable value.
!!(t>>9&7|!(-t>>12&7)) produces the repeating 6+1 note pattern.  Specifically, !!(t>>9&7) evaluates to 0 whenever t>>9 & 7 == 0 and to 1 otherwise.  Thus, it produces a 512-sample gap in the waveform every 4096 samples, while the !(-t>>12&7) eliminates every eighth such gap.
96+"#d|dOE3#dOE3dOE3"[t>>13&15] generates the melody: the ASCII code of each characters in the string plus 96 gives the relative frequency of the corresponding note.  Actually, the values are the approximate frequencies in Hz of concert pitch notes in the 3rd / small octave, i.e. with A corresponding to 220.  However, since the base tone with which these values are multiplied is about 64 Hz (when played at 16 kHz, or 32 Hz when played at 8 kHz), we need to scale the result down by five octaves with >>5 to get the frequency back into a reasonable range.

Ps. If you want to try this code on a JavaScript-based bytebeat player, replace [t>>13&15] with .charCodeAt(t>>13&15).

HyperCard 2.2 - 113
play harpsichord "c c g g a a gh fq f e e d d ch gq g f f e e dh gq g f f e e dh cq c g g a a gh fq f e e d d ch"

Usage: Start HyperCard, type ⌘M to open the Message Box, paste the code above, and press enter.
harpsichord may be replaced with flute or boing to get different sounds.

(very late comment) harpsichord -> flute -6 remove the space between instrument and quotes -1 total -7

PowerShell: 207
Golfed code:
filter n {switch($_){C{262}D{294}E{330}F{349}G{392}A{440}}}$t="CCGGAAGFFEEDDCGGFFEEDGGFFEEDCCGGAAGFFEEDDC";1..6|%{$t[0..5]|n|%{[console]::beep($_,600)};$t[6]|n|%{[console]::beep($_,1200)};$t=$t.SubString(7)}

Ungolfed, with comments:
# Filter to define note frequencies.
filter n {switch($_){C{262}D{294}E{330}F{349}G{392}A{440}}}

# Notes for Twinkle, Twinkle, Little Star.
$t="CCGGAAGFFEEDDCGGFFEEDGGFFEEDCCGGAAGFFEEDDC"

# Run through each phrase in the song.
1..6|%{
    # Play first six notes as quarter notes.
    $t[0..5]|n|%{[console]::beep($_,600)}
    # Play seventh note as half note.
    $t[6]|n|%{[console]::beep($_,1200)}
    # Left-shift $t by 7 notes.
    $t=$t.SubString(7)
}

Not the greatest-sounding rendition of the song ever, but it works.

(late comment) Can you do n{ instead of n {?

JavaScript, 194 177 176
Now that WebAudio is a thing, I thought it would be fun to write this. (Yes, I know ES6 and WebAudio came out after the challenge was posted.) Tested on Microsoft Edge.

a=new AudioContext,o=a.createOscillator(i=0)
o.connect(a.destination)
setInterval(_=>o.frequency.value=4*[65,73,82,87,98,110]['045432104321432104543210'[i++]]|0,1e3)
o.start(1)

Given the lack of strict output requirements, I took the liberty of detuning some frequency values to be divisible by 4. It still sounds passable, relative-pitch wise. The final notes are off by -11, -10, -9, -6, 0, and 0 cents, for c, d, e, f, g, and a respectively, giving a total window of 11 cents. Not great to the trained ear, but recognizable as the tune, which is all the challenge requires.
There are also no breaks between notes, but that wasn't a requirement either.

Wolfram Language (Mathematica), 93 bytes
Sound[s=SoundNote;If[#>9,s[#-10,2],{s@#,s@#}]&/@Join[a={0,7,9,17,5,4,2,10},b={7,5,4,12},b,a]]

Arduino, 688
int length=15;char notes[]="ccggaag ffeeddc ggffeed ggffeed ccggaag ffeeddc";int beats[]={1,1,1,1,1,1,2,1,1,1,1,1,1,2,4};int tempo=300;void playTone(int tone,int duration){for(long i=0;i<duration*1000L;i+=tone*2){digitalWrite(11,HIGH);delayMicroseconds(tone);digitalWrite(11, LOW);delayMicroseconds(tone);}}void playNote(char note, int duration){char names[]={'c','d','e','f','g','a','b','C'};int tones[]={1915,1700,1519,1432,1275,1136,1014,956};for(int i=0;i<8;i++){if(names[i]==note){playTone(tones[i], duration);}}}void setup(){pinMode(11, OUTPUT);}void loop(){for(int i=0;i<length;i++){if(notes[i]==' '){delay(beats[i]*tempo);}else{playNote(notes[i],beats[i]*tempo);}delay(tempo/2);}}

Plug in the buzzer on output 11. I concentrated mainly on quality, but also on code length.

(late comment) "ccggaag ffeeddc ggffeed ggffeed ccggaag ffeeddc " remove space? int beats[] = remove space? for (long remove space? 11, LOW remove space? note, int remove space? i], duration remove space? 11, OUTPUT remove space?

Did you actually forget some spaces? As far as I understand, the space in ffeeddc " is for some sort of delay, which you do not need at the end, and beats[] = has no reason to have a space. Also, you should make a version concentrating on code length, just for the heck of it!

I suppose the variables could all be one letter but I don't think it's worth the time on such an old answer. Thanks for those tips.

Ok, feel free to post as a separate answer if you'd like.

@Timtech As the question is closed, that can't be done unfortunately... :-(

Python 317 305 301
This is my solution, using only standard python libraries:
import math,wave,struct;d=24000;r=1100.;t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""));a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2]
for h in[math.sin(6*[240*2**(j/12.)for j in a+b+c+c+a+b][x/1000]*(x/r))*(x%500>9 or x/1000%4>2)for x in range(d)]:t.writeframes(struct.pack('h', int(h*64000/2)))

And here it is with some more whitespace for readability:
import math,wave,struct;d=24000;r=1100.
a=[0,7,9,7];b=[5,4,2,0];c=[7,5,4,2];s=[240*2**(j/12.) for j in a+b+c+c+a+b]
z=[math.sin(6*s[int(x/1000)]*(x/r))*(x%500>10 or int(x/1000)%4>2) for x in range(d)]
t=wave.open("t.wav","w");t.setparams((1,2,int(r),d,"NONE",""))
for h in z:t.writeframes(struct.pack('h', int(h*64000./2)))

Powershell, 120 117 bytes
[Console]::beep, note labels and frequencies inspired by Iszi
 ($a='ccggaaGffeeddC')+'ggffeeD'*2+$a|% t*y|%{[console]::beep((0,110,0,65,73,82,87,98)[$_-band7]*4,600+600*($_-lt97))}

Main idea:

The melody is encoded in a string.
The notes are encoded with chars A,C,D,E,F,G.
Uppercase means a double duration.
3 lower bits ($_-band7) of each note uses as index in the frequencies array (A->1,C->3,D->4...)
This script uses the reduced sampling rate for frequencies: (0,110,0,65,73,82,87,98)[$_-band7]*4 instead Iszi's (0,440,0,262,294,330,349,392)[$_-band7]. [console]::Beep is not the most accurate musical instrument, so it can slightly fake :)

Explanation: For each char from the melody string ccggaaGffeeddCggffeeDggffeeDccggaaGffeeddC, the script:

lookups frequensies from the array using the lower bits as index
calculates a duration based on char uppercase/lowercase
calls [console]::beep to play the note

SmileBASIC, 45 bytes
BGMPLAY"{M=CCGGAAG2FFEEDDC2}{M}[GGFFEED2]2{M}

Raku, 115 bytes
for 'xPHPZ`jxPZ`jPZ`jxPHPZ`jx'.ords.kv ->\i,\p {print 9*(4*$_ div p%2&&2900>$_)*(3==i%4||!(1500>$_>1400))for ^3e3}

Pipe to aplay to listen.

C (MSVC + Win32), 163 bytes
#include<windows.h>
#include<math.h>
main(){for(char*s="DDKKMMK IIHHFFD KKIIHHF KKIIHHF DDKKMMK IIHHFFD ";*s;s++)*s-32&&Beep(220*pow(1.06,*s-65),s[1]-32?400:800);}

In Windows 7, Beep was rewritten to pass the beep to the default sound device for the session. This is normally the sound card, except when run under Terminal Services, in which case the beep is rendered on the client.

Easyfuck, 46 bytes

Þ¡åGÕÔäPúPMýôÔðQSTS&GÔýïûMJGÜ8_¡Áõ␎␒APCpá␁␅PLDøoÝ¹jÁ°

due to lack of unicode representations for c1 control characters, they have been replaced by their superscripted abbreviations
Decompressed:
o(<T>W)d(>SooS)p(ddd>S{o}S)$>pp_Pp>PpJ>pp@␠X_a_]\ZX␛

Explanation:
o(<T>W)d(>SooS)p(ddd>S{o}S)$>pp_Pp>PpJ>pp@␠X_a_]\ZX␛
o(<T>W)                                              1 note playing function
       d(>SooS)                                      2 note playing function
               p(ddd>S{o}S)                          2+2+2+1 note playing function
                             pp  p  p  pp            p function invocations
                           $>  _P >P J>              pointer moving magic
                                         @           return
                                          ␠X_a_]\ZX␛ initializer data

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Write an interpreter for the untyped lambda calculus
The challenge is to write an interpreter for the untyped lambda calculus in as few characters as possible. We define the untyped lambda calculus as follows:
Syntax
There are the following three kinds of expressions:

A lambda expression has the form (λ x. e) where x could be any legal variable name and e any legal expression. Here x is called the parameter and e is called the function body.
For simplicity's sake we add the further restriction that there must not be a variable with the same name as x currently in scope. A variable starts to be in scope when its name appears between (λ and . and stops to be in scope at the corresponding ).
Function application has the form (f a) where f and a are legal expressions. Here f is called the function and a is called the argument.
A variable has the form x where x is a legal variable name.

Semantics
A function is applied by replacing each occurrence of the parameter in the functions body with its argument. More formally an expression of the form ((λ x. e) a), where x is a variable name and e and a are expressions, evaluates (or reduces) to the expression e' where e' is the result of replacing each occurrence of x in e with a.
A normal form is an expression which can not be evaluated further.
The Challenge
Your mission, should you choose to accept it, is to write an interpreter which takes as its input an expression of the untyped lambda calculus containing no free variables and produces as its output the expression's normal form (or an expression alpha-congruent to it). If the expression has no normal form or it is not a valid expression, the behaviour is undefined.
The solution with the smallest number of characters wins.
A couple of notes:

Input may either be read from stdin or from a filename given as a command line argument (you only need to implement one or the other - not both). Output goes to stdout.
Alternatively you may define a function which takes the input as a string and returns the output as a string.
If non-ASCII characters are problematic for you, you may use the backslash (\) character instead of λ.
We count the number of characters, not bytes, so even if your source file is encoded as unicode λ counts as one character.
Legal variable names consist of one or more lower case letters, i.e. characters between a and z (no need to support alphanumeric names, upper case letters or non-latin letters - though doing so will not invalidate your solution, of course).
As far as this challenge is concerned, no parentheses are optional. Each lambda expression and each function application will be surrounded by exactly one pair of parentheses. No variable name will be surrounded by parentheses.
Syntactic sugar like writing (λ x y. e) for (λ x. (λ y. e)) does not need to be supported.
If a recursion depth of more than 100 is required to evaluate a function, the behaviour is undefined. That should be more than low enough to be implemented without optimization in all languages and still large enough to be able to execute most expressions.
You may also assume that spacing will be as in the examples, i.e. no spaces at the beginning and end of the input or before a λ or . and exactly one space after a . and between a function and its argument and after a λ.

Sample Input and Output

Input: ((λ x. x) (λ y. (λ z. z)))
Output: (λ y. (λ z. z))
Input: (λ x. ((λ y. y) x))
Output: (λ x. x)
Input: ((λ x. (λ y. x)) (λ a. a))
Output: (λ y. (λ a. a))
Input: (((λ x. (λ y. x)) (λ a. a)) (λ b. b))
Output: (λ a. a)
Input: ((λ x. (λ y. y)) (λ a. a))
Output: (λ y. y)
Input: (((λ x. (λ y. y)) (λ a. a)) (λ b. b))
Output: (λ b. b)
Input: ((λx. (x x)) (λx. (x x)))
Output: anything (This is an example of an expression that has no normal form)
Input: (((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
Output: (λ a. a) (This is an example of an expression which does not normalize if you evaluate the arguments before the function call, and sadly an example for which my attempted solution fails)
Input: ((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
Output: `(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
This computes 2^3 in Church numerals.

Can we assume that there will not be prepended or appended whitespace to the string and that whitespace is otherwise as specified in the sample input? That is, no whitespace between brackets, between the dot and the parameter name and other instances of whitespace is exactly 1 space.

@JPvdMerwe: Yes, good point, you may assume that.

Are there any free variables? I mean variables unbound by a lambda like in the expression (\y. a).

Another question: May I choose other names for the variables in the output? I mean (\a. a) instead of (\b. b)`?

And a third one: Can you make the varnames to one char each? This would make my solution shorter.

@FUZxxl: 1. There won't be any free variables in the input. 2. Yes, you may print any expression which is alpha-congruent to the expected output. 3. I think making the conditions easier after there already is a solution which works for the current specification would be unfair. Feel free to post both solutions, but as far as "winning" goes the one which can handle long variable names is the one that counts.

Does the last example mean the interpreter has to support non-strict (a.k.a. lazy) evaluation?

@Joey: Yes, it should find a normal form for every expression which has one, so it can't use strict evaluation.

Many or all of the solutions here fail to implement capture-avoiding substitution! You should add a test case like ((λ f. (λ x. (f x))) (λ y. (λ x. y))), which should evaluate to (λ x. (λ z. x)), not (λ x. (λ x. x)).

@Kaseorg in ((λ f. (λ x. (f x))) (λ y. (λ x. y))) what is the result? is it  (λ x. (λ z. x))? what is z?

what is the result of "(λ a. ((( w(a) ))) )z"   "w(z)"   "(w(z))"  or "((( w(z) )))" ?

the lambda program allow the result of  (/x.(/y. x^2+y^2)3)7  to be 7^2+3^2?

@RosLuP The correct result is (λ x. (λ z. x)) because the function should return the outer function's argument, not the inner function's argument. z is a new identifier that was chosen over x, because x would shadow the outer x, leading to a wrong result. Instead of z any other valid identifier could also have chosen. (λ a. ((( w(a) ))) )z is not an input you need to handle as it doesn't adhere to the parenthesization rules I've described (i.e. one pair of parentheses around ever abstraction and application and that's it) and because there won't be free variables in the input.

@RosLuP So the result can be anything you want, but I'd say the most correct result would still be conforming to the parenthesization rules, so (w z). There's no need to support numbers or infix operators.

(w z) has parentesis different from (λ x. (λ z. x)) so it would be [λ x. [λ z. x]]

@RosLuP What do you mean? As I said, the rules are to parenthesize function application and abstraction (with one pair of parentheses each) and nothing else. Both (w z) and (λ x. (λ z. x)) follow these rules exactly. I'm not sure what you mean by "so it would be [λ x. [λ z. x]]". Where did the square brackets come from all of the sudden?

i'm not one expert and this is the first time i see lambda calculus... now i see (a w) as one function and  (λ z. x) as a macro substitution to strings... so they are different and for not confuse parentesis different they for me have to have different type of parentesis so [λ z. x]

@RosLuP First of all (λ z. x) creates a function (or is a function, really) and (f x) applies a function. So both deal with functions - there are no macros in the lambda calculus. Secondly addition is different from multiplication, but nobody would suggest that something like ((x + y) * z) should instead be written ([x + y] * z). That is, there's no rule that says that different types of expressions need to be parenthesized with different types of parentheses. No programming language in the world has such a rule (inb4 obscure counter example). Thirdly the usual syntax ...

... for the lambda calculus uses round parentheses everywhere and that's what this challenge asks for.

@sepp2k Have you considered adding ((λ f. (λ x. (f x))) (λ y. (λ x. y))) as a test case and unaccepting the current answer which incorrectly produces (λ x. (λ x. x))?

@RosLup. The presence of a lambda indicates whether an expression is a macro or a literal expression.

Newest:
I've squeezed it down to 644 chars, I factored parts of cEll into cOpy and Par; cached calls to cell and cdr into temporary local variables, and moved those local variables to globals in "terminal" (ie. non-recursive) functions. Also, decimal constants are shorter than character literals and this nasty business ...
atom(x){
    return m[x]>>5==3;
}

... correctly identifies lowercase letters (assuming ASCII), but also accepts any of `{|}~. (This same observation about ASCII is made in this excellent video about UTF-8.)
Et viola:|
#include<stdio.h>
#include<string.h>
#define X m[x]
#define R return
char*n,*m;int u,w,d;C(x,y){w=n-m;n+=sprintf(n,y?"(%s %s)":"(%s)",&X,m+y)+1;R w;}T(x){R X>>5==3;}
L(x){R X==92;}O(x,j){w=n-m;memcpy(n,&X,j);n+=j;*n++=0;R w;}E(x){X==' '?++x:0;R
X==41?0:L(x)?O(x,4):P(x);}P(x){d=0,w=x;do{X==40?d++:X==41?d--:0;++x;}while(d>0);R
O(w,x-w);}D(x){u=E(x+1);R u?E(x+1+strlen(m+u)):0;}V(x){int a=E(x+1),b=D(x);R
T(x)|T(a)?x:L(a)?C(a,V(b)):L(E(a+1))?V(S(V(b),E(a+3),D(a))):V(C(V(a),b?V(b):0));}S(w,y,x){R
T(x)?(X==m[y]?w:x):C(L(w+1)?E(x+1):S(w,y,E(x+1)),D(x)?S(w,y,D(x)):0);}
Y(char*s){n+=strlen(s=strcpy(n,s))+1;printf("%s\n%s\n\n",s,m+V(s-m));n=m+1;}

char*s[]={
"((\\ a. a) (b))",
"((\\ x. x) (\\ y. (\\ z. z)))",
"(\\ x. ((\\ y. y) x))",
"(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
"((\\ x. (\\ y. y)) (\\ a. a))",
"(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
"((\\x. (x x)) (\\x. (x x)))",0};
#include<unistd.h>
main(){char**k;n=m=sbrk(4096);*n++=0;for(k=s;*k;k++)Y(*k);R 0;}

Earlier:
Can I get a few votes for effort? I've been working on this day and night for a week. I dug out the original McCarthy paper and was plagued by a bug in the paper itself until I read the appendix to Paul Graham's The Roots of Lisp. I was so distracted that I locked myself out of my house, then completely forgot until arriving home again that night at 12:30 (a little late to be calling the building manager who lives way out in the county), and had to spend the night at my grandmother's (hacking away until my laptop battery was dry).
And after all that, it's not even close to the winning entry!
I'm not sure how to make this any shorter; and I've used all the dirty tricks I can think of! Maybe it can't be done in C.
With some generosity in the counting (the first chunk takes a string and prints out the result), it's 778 770 709 694 chars. But to make it stand-alone, it has to have that sbrk call. And to handle more complicated expressions, it needs the signal handler, too. And of course it cannot be made into a module with any code that tries to use malloc.
So, alas, here it is:
#include<stdio.h>
#include<string.h>
#define K(j) strncpy(n,m+x,j);n+=j;goto N;
#define R return
#define X m[x]
#define L =='\\'
char*m,*n;T(x){R islower(X);}V(x){int a=E(x+1);R
T(x)?x:T(a)?x:m[a]L?C(a,V(D(x))):m[E(a+1)]L?V(S(V(D(x)),E(a+3),D(a))):V(C(V(a),D(x)?V(D(x)):0));}
C(x,y){char*t=n;sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y);n+=strlen(n)+1;R
t-m;}Y(char*s){char*t=strcpy(n,s);n+=strlen(n)+1;printf("%s=>%s\n",s,m+V(t-m));n=m+1;}S(x,y,z){R
T(z)?(m[z]==m[y]?x:z):C(m[z+1]L?E(z+1):S(x,y,E(z+1)),D(z)?S(x,y,D(z)):0);}D(x){R
E(x+1)?E(x+strlen(m+E(x+1))+1):0;}E(x){char*t=n,d=0;if(X==' ')++x;if(T(x)){K(1)}if(X
L){K(4)}do{d=X?(X=='('?d+1:(X==')'?d-1:d)):0;*n++=m[x++];}while(d);N:*n++=0;R t-m;}

char*samp[]={
    "a","a","b","b",
    "((\\ a. a) (b))", "(b)",
    "((\\ x. x) (\\ y. (\\ z. z)))", "(\\ y. (\\ z. z))",
    "(\\ x. ((\\ y. y) x))", "(\\ x. x)",
    "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))", "(\\ a. a)",
    "((\\ x. (\\ y. y)) (\\ a. a))", "(\\ y. y)",
    "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))", "(\\ b. b)",
    "((\\x. (x x)) (\\x. (x x)))", "undef",
    NULL};
#include<unistd.h>

unsigned sz;
#include<signal.h>
void fix(x){signal(SIGSEGV,fix);brk(m+(sz*=2));}
main(){
    char**t;
    signal(SIGSEGV,fix);
    m=n=sbrk(sz=10*getpagesize());
    *n++=0;
    for(t=samp;*t;t+=2){
        Y(*t);
        printf("s.b. => %s\n\n", t[1]);
    }
    return 0;
}

Here's the block just before the final reductions. The tricks here are integer cursors instead of pointers (taking advantage of the 'implicit int' behavior), and the use of 'scratch memory': the char*n is the 'new' or 'next' pointer into the free space. But sometimes I write a string into the memory, then call strlen and increment n; effectively using memory and then allocating it, after the size is easier to calculate.
You can see it's pretty much straight from the McCarthy paper, with the exception of cell() which interfaces between the functions and the string representation of data.
#include<stdio.h>
#include<string.h>
char*m,*n;  //memory_base, memory_next
atom(x){  // x is an atom if it is a cursor to a lowercase alpha char.
    return x?(islower(m[x])?m[x]:0):0;
}
eq(x,y){  // x and y are equal if they are both atoms, the same atom.
    return x&&y&&atom(x)==atom(y);
}
cell(x){  // return a copy of the list-string by cursor, by parsing
    char*t=n,d=0;
    if(!x||!m[x])
        return 0;
    if(m[x]==' ')
        ++x;
    if(atom(x)){
        *n++=m[x];
        *n++=0;
        return(n-m)-2;
    }
    if(m[x]=='\\'){  // our lambda symbol
        memcpy(n,m+x,4);
        n+=4;
        *n++=0;
        return(n-m)-5;
    }
    do{  // um ...
        d=m[x]?(m[x]=='('?d+1:(m[x]==')'?d-1:d)):0;
        *n++=m[x++];
    }while(d);
    *n++=0;
    return t-m;
}
car(x){  // return (copy of) first element
    return x?cell(x+1):0;
}
cdr(x){  // return (copy of) rest of list
    return car(x)?cell(x+strlen(m+car(x))+1):0;
}
cons(x,y){  // return new list containing first x and rest y
    char*t=n;
    return x?(sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y),n+=strlen(n)+1,t-m):0;
}
subst(x,y,z){  // substitute x for z in y
    if(!x||!y||!z)
        return 0;
    return atom(z)? (eq(z,y)?x:z):
        cons(m[z+1]=='\\'?car(z):
        subst(x,y,car(z)),cdr(z)?subst(x,y,cdr(z)):0);
}
eval(x){  // evaluate a lambda expression
    int a;
    return atom(x)?x:
        atom(a=car(x))?x:
        m[a]=='\\'?cons(a,eval(cdr(x))):
        m[car(a)]=='\\'?eval(subst(eval(cdr(x)),cell(a+3),cdr(a))):
        eval( cons(eval(a),cdr(x)?eval(cdr(x)):0));
}
try(char*s){  // handler
    char*t=strcpy(n,s);
    n+=strlen(n)+1;
    printf("input: %s\n", s);
    printf("eval => %s\n", m+eval(t-m));
    n=m+1;
}

I found a few more tricks to save a character or two, but nothing radical. sprintf(n,...);n+=strlen(n)+1; is better as n+=sprintf(n,...)+1; Inverting the array syntax x[m] instead of m[x] allow me to replace all indirections with a 'postfix' macro #define M [m]...x M which saves 1 char and gives a "free" line break since whitespace is necessary to separate the tokens.

There appear to be some similarities with this and jar.2 xlisp 4.0 from IOCCC 1989.

I tried to expand this into a fuller Lisp interpreter.

The code commented // um ... is looping through the string and counting parentheses until it finds the matching close-paren at the correct nesting level.

Have an upvote for your effort and your grandma's story from 8 years later :)

542

islower can be shortened to & 32. '\\' can be shortened to 92.

Binary Lambda Calculus 186
The program shown in the hex dump below
00000000  18 18 18 18 18 18 44 45  1a 10 18 18 45 7f fb cf  |......DE....E...|
00000010  f0 b9 fe 00 78 7f 0b 6f  cf f8 7f c0 0b 9f de 7e  |....x..o.......~|
00000020  f2 cf e1 b0 bf e1 ff 0e  6f 79 ff d3 40 f3 a4 46  |........oy..@..F|
00000030  87 34 0a a8 d0 80 2b 0b  ff 78 16 ff fe 16 fc 2d  |.4....+..x.....-|
00000040  ff ff fc ab ff 06 55 1a  00 58 57 ef 81 15 bf bf  |......U..XW.....|
00000050  0b 6f 02 fd 60 7e 16 f7  3d 11 7f 3f 00 df fb c0  |.o..`~..=..?....|
00000060  bf f9 7e f8 85 5f e0 60  df 70 b7 ff ff e5 5f f0  |..~.._.`.p...._.|
00000070  30 30 6f dd 80 5b b3 41  be 85 bf ff ca a3 42 0a  |00o..[.A......B.|
00000080  c2 bc c0 37 83 00 c0 3c  2b ff 9f f5 10 22 bc 03  |...7...<+...."..|
00000090  3d f0 71 95 f6 57 d0 60  18 05 df ef c0 30 0b bf  |=.q..W.`.....0..|
000000a0  7f 01 9a c1 70 2e 80 5b  ff e7 c2 df fe e1 15 55  |....p..[.......U|
000000b0  75 55 41 82 0a 20 28 29  5c 61                    |uUA.. ()\a|
000000ba

doesn't accept quite the format you propose.
Rather, it expects a lambda term in binary lambda calculus (blc) format.
However, it does show every single step in the normal form reduction,
using minimal parentheses.
Example: computing 2^3 in Church numerals
Save the above hex dump with xxd -r > symbolic.Blc
Grab a blc interpreter from http://tromp.github.io/cl/uni.c
cc -O2 -DM=0x100000 -m32 -std=c99 uni.c -o uni
echo -n "010000011100111001110100000011100111010" > threetwo.blc
cat symbolic.Blc threetwo.blc | ./uni
(\a \b a (a (a b))) (\a \b a (a b))
\a (\b \c b (b c)) ((\b \c b (b c)) ((\b \c b (b c)) a))
\a \b (\c \d c (c d)) ((\c \d c (c d)) a) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c \d c (c d)) a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b (\c a (a c)) ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b a (a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a ((\c a (a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a (a (a ((\c \d c (c d)) ((\c \d c (c d)) a) b))))
\a \b a (a (a (a ((\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) b))))
\a \b a (a (a (a ((\c \d c (c d)) a ((\c \d c (c d)) a b)))))
\a \b a (a (a (a ((\c a (a c)) ((\c \d c (c d)) a b)))))
\a \b a (a (a (a (a (a ((\c \d c (c d)) a b))))))
\a \b a (a (a (a (a (a ((\c a (a c)) b))))))
\a \b a (a (a (a (a (a (a (a b)))))))

Since the hexdump is rather unreadable, here is a "disassembled" version
@10\\@10\\@10\\@10\\@10\\@10\@\@\@\@@\@1010\@\\\@10\\@10\@\@@@1111111111101
1110@11111110\@@110@11111110\\\\@1110\@1111110\@@101101111110@111111110\@111
111110\\\\@@110@111111011110@11111011110@@10@1111110\@10110\@@111111110\@111
111110\@110@101111011110@1111111111010@1010\\@1110@11010@\@\@1010\@110@1010\
\@@@@@\@1010\@\\\\@@@10\@@111111111011110\\@@101111111111111110\@@101111110\
@@10111111111111111111111110@@@@1111111110\\110@@@@\@1010\\\\@@10\@@@1111101
11110\\@\@@@10111111101111110\@@1011011110\\@@11111010110\\@111110\@@1011110
1110@111010\10\1011111110@111110\\\@101111111111011110\\@@11111111110@@11111
0111110\10\@@@@11111110\\@10\\1101111101110\@@1011111111111111111111110@@@@1
11111110\\@10\\@10\\11011111101110110\\\@@101110110@1010\\11011111010\@@1011
111111111111110@@@@\@1010\@\\@@@10\@@@1110@10\\\@1011110\\110\\\@10\\\@1110\
@@@11111111110@1111111101010\10\\@\@@@1110\\\@10@1110111110\\1110\110@@@1111
0110@@@1111010\\110\\\@10\\\@@1101111111101111110\\\@10\\\@@1101111110111111
10\\\110@1010110\\101110\\@@11010\\\@@1011111111111110@11110\@@1011111111111
101110\@\@@@@@@@@11010101010101010\\110\\10\\1010\10\\\1010\\1010@@@110\110\
@

replacing 00 (lambda) with \ and 01 (application) with @
Now it's almost as readable as brainfuck:-)
Also see http://www.ioccc.org/2012/tromp/hint.html

-1 Unreadable.  Golfing isn't really a compiled language's activity.

BLC just happens to use a binary alphabet. 00 is lambda, 01 is application, and 1^{n}0 is a variable in unary. There's no compilation involved.

Well, yes, but now you're just claiming a ×3 codegolf score improvement over the honest-to-goodness readable BF-or-better type of languages.  I'm not pissed off anymore, but my downvote remains.

Where do you get a factor x3? You actually raise a good point in that languages with smaller source alphabets like BF are penalised. For fair comparison, all sizes should be expressed in bits, and BF characters only take 3 bits each. Most other languages need 7 bits for ASCII, some use all 8.

@JohnTromp Yes, some kind of bit-density-weighting seems like a very good candidate for a golf rule. Some of the ones I've seen with unicode chars seem to be getting away with something. (grumble, grumble).

BTW +1 This is damn cool!

If fractran in fractran is acceptable, I don't see why this should be a problem at all. You can't read it? You want to? Learn!

What would it take to make it read the actual input format? I think that's where you're losing potential upvotes.

Oh here you are again. I don't stop being amused by this guy's work.

@JohnTromp Can you please update the link to blc? It returns a 404.

Fixed. Also added link to 2012 IOCCC winner of "Most Functional".

Haskell, 342 323 317 305 characters
As of this writing, this is the only solution that evaluates ((λ f. (λ x. (f x))) (λ y. (λ x. y))) to the correct result (λ x. (λ z. x)) rather than (λ x. (λ x. x)).  Correct implementation of the lambda calculus requires capture-avoiding substitution, even under this problem’s simplifying guarantee that no variable shadows another variable in its scope.  (My program happens to work even without this guarantee.)
data T=T{a::T->T,(%)::ShowS}
i d=T(i. \x v->'(':d v++' ':x%v++")")d
l f=f`T`\v->"(λ "++v++". "++f(i(\_->v))%('x':v)++")"
(?)=q.lex
q[(v,s)]k|v/="("=k(maybe T{}id.lookup v)s|'λ':u<-s,[(w,_:t)]<-lex u=t? \b->k(\e->l$b.(:e).(,)w).tail|0<1=s? \f->(?(.tail).k. \x z->f z`a`x z)
main=interact(? \f->(f[]%"x"++))

Notes:

This runs in GHC 7.0, as required because this challenge was set in January 2011.  It would be 13 characters shorter if I were allowed to assume GHC 7.10.

Ungolfed version with documentation.

your prog in ideone haskell compiler to the input ((\ x. x) (\ y. (\ z. z)))
return "run time error" even in ((\ x. x) (\ y. (\ z. z)))... what does it mean "lex" in Haskell?

@RosLuP My program accepts λ, not .

type this imput ((λ x. x) (λ y. (λ z. z))) in ideone.com return:
Runtime error time: 0 memory: 4876 signal:-1

@RosLuP Ideone seems to have broken Unicode support. Try the command line or another online interpreter (it works on Rextester, for example).

From Rextester ((λ a. (λ b. (a (a (a b))))) (λ x. (λ d. (c (c d))))) to this input your prog returns a.out: source_file.hs:5:26-28: Missing field in record construction a.
Some  program from input =((\ a. (\ b. (a (a (a b))))) (\ x. (\ d. (c (c d))))) returns =(\ b. (\ A. (c (c A))))

@RosLuP That input is invalid because c is a free variable; the OP commented “there won't be any free variables in the input”.

Let us continue this discussion in chat.

As far as I can see (λ x. (λ x. x)) is the correct result according to the specification. The specification says each variable is replaced by the argument, not by a modified form of the argument. So this answer doesn't fulfil the specification - which is unfortunate because it's a brilliant program.

@codeshot The question author has already commented that ((λ f. (λ x. (f x))) (λ y. (λ x. y))) ↦ (λ x. (λ z. x)) is correct for this problem (just like the real lambda calculus).

Ruby 254 characters
f=->u,r{r.chars.take_while{|c|u+=c==?(?1:c==?)?-1:0;u>0}*''}
l=->x{x=~/^(\(*)\(\\ (\w+)\. (.*)/&&(b,v,r=$1,$2,$3;e=f[1,r];(e==s=l[e])?b==''?x:(s=f[2,r];(x==y=b.chop+e.gsub(v,s[2+e.size..-1])+r[1+s.size..-1])?x:l[y]):(b+'(\\ '+v+'. '+s+r[e.size..-1]))||x}

It can be used like
puts l["((\\ x. (\\ y. x)) (\\ a. a))"]    # <= (\ y. (\ a. a))

The solution is not yet fully golfed but already almost unreadable.

hello envy, my old friend :)

This fails to do capture-avoiding substitution. For example, ((\ f. (\ x. (f x))) (\ y. (\ x. y))) evaluates incorrectly to (\ x. (\ x. x)).

In addition to the above capture bug, this also incorrectly evaluates (\ y. (\ xx. ((\ x. xx) y))) to (\ y. (\ xx. yy)), where overzealous string substitution has manufactured the nonexistent variable yy.

Edit: check my answer below for 250 under pure JavaScript.
2852 243 characters using LiveScript (No Regex! Not fully golfed - could be improved)
L=(.0==\\)
A=->it.forEach?&&it.0!=\\
V=(.toFixed?)
S=(a,b,t=-1,l=0)->|L a=>[\\,S(a.1,b,t,l+1)];|A a=>(map (->S(a[it],b,t,l)),[0 1]);|a==l+-1=>S(b,0,l+-1,0)||a|l-1<a=>a+t;|_=>a
R=(a)->|L a=>[\\,R a.1]|(A a)&&(L a.0)=>R(S(R(a.0),R(a.1)).1)|_=>a

Test:
a = [\\,[\\,[1 [1 0]]]]
b = [\\,[\\,[1 [1 [1 0]]]]]
console.log R [a, b]
# outputs ["\\",["\\",[1,[1,[1,[1,[1,[1,[1,[1,[1,0]]]]]]]]]]]

Which is 3^2=9, as stated on OP.
If anyone is curious, here is an extended version with some comments:
# Just type checking
λ = 100
isλ = (.0==λ)
isA = -> it.forEach? && it.0!=λ
isV = (.toFixed?)

# Performs substitutions in trees
# a: trees to perform substitution in
# b: substitute bound variables by this, if != void
# f: add this value to all unbound variables
# l: internal (depth)
S = (a,b,t=-1,l=0) ->
    switch
    | isλ a             => [λ, (S a.1, b, t, l+1)]
    | isA a             => [(S a.0, b, t, l), (S a.1, b, t, l)]
    | a == l - 1        => (S b, 0, (l - 1), 0) || a
    | l - 1 < a < 100   => a + t
    | _                 => a

# Performs the beta-reduction
R = (a) ->
    switch
    | (isλ a)               => [λ,R a.1]
    | (isA a) && (isλ a.0)  => R(S(R(a.0),R(a.1)).1)
    | _                     => a

# Test
a = [λ,[λ,[1 [1 0]]]]
b = [λ,[λ,[1 [1 [1 0]]]]]
console.log show R [a, b]

This doesn’t conform to the input and output specifications from the problem.

Waterhouse Arc - 140 characters
(=
f[is cons?&car._'λ]n[if
atom._ _
f._ `(λ,_.1,n:_.2)(=
c n:_.0
e _)(if
f.c(n:deep-map[if(is
c.1 _)e.1
_]c.2)(map n
_))]λ[n:read:rem #\._])

Where can I get Waterhouse Arc?

Invalid as an interpreter is nowhere to be found

@AndersKaseorg here

@ASCII-only I know what Arc is, but the “Waterhouse” part suggested to me that some particular dialect was necessary. Have you gotten it to run?

@AndersKaseorg Never mind. Found it

C 1039 bytes
#define F for
#define R return
#define E if(i>=M||j>=M)R-1;
enum{O='(',C,M=3999};signed char Q[M],D[M],t[M],Z,v,*o=Q,*d=D,*T;int m,n,s,c,w,x,y;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){d[j]=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!='\\'){d[j++]=o[i++];R K(i,j,i);}F(i+=2,y=w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0,!y&&o[i]=='.'?y=i+2:0;E;if(c){F(;d[j++]=o[i++];)E;R 0;}F(c=y;c<w;++c)if(o[c]=='\\')F(n=0,m=w+2;m<i;++m){if(o[m]==o[c+2]){F(x=0;o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[c+2+x];++x);if(o[c+2+x]!='.'||isalpha(o[m+x]))continue;if(v>'Z')R-1;F(n=c+2;n<w;++n)if(o[n]==o[m]){F(x=0; o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[n+x];++x);if(o[m+x]=='.'&&!isalpha(o[n+x]))F(;--x>=0;) o[n+x]=v;}++v;}}F(c=y;c<w&&j<M;++c){F(x=0;o[c+x]&&o[c+x]==o[k+4+x]&&isalpha(o[c+x]); ++x);if(o[k+4+x]=='.'&&!isalpha(o[c+x])){F(m=w+2;m<i-1&&j<M;++m)d[j++]=o[m];c+=x-1;}else d[j++]=o[c];}E;Z=2;R K(i,j,i);}char*L(char*a){F(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;v='A';F(;++s<M;){Z=0;n=K(0,0,0);if(Z==2&&n!=-1)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}

Variables allow as input using lowercase letters [from a..z] the sys can generate variables using uppercase letters [from A..Z] if need in the output...
Assume ascii character configuration.
#define P printf
main()
{char  *r[]={ "((\\ abc. (\\ b. (abc (abc (abc b))))) (\\ cc. (\\ dd. (cc (cc dd)))))",
              "((\\ fa. (\\ abc. (fa abc))) (\\ yy. (\\ abc. yy)))",
              "((\\ x. x) z)",
              "((\\ x. x) (\\ y. (\\ z. z)))",
              "(\\ x. ((\\ y. y) x))",
              "((\\ x. (\\ y. x)) (\\ a. a))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (\\ y. y)) (\\ a. a))",
              "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (x x)) (\\ x. (x x)))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) ((\\ x. (x x)) (\\ x. (x x))))",
             0}, *p;
 int    w;

 for(w=0; r[w] ;++w)
   {p=L(r[w]);
    P("o=%s d=%s\n", r[w], p==0?"Error ":p);
   }
 R  0;
}

/*1.039*/

The specification requires \ or λ, not /. It also requires support for multi-letter variable names.

'\n' etc symbol '' has other uses it is better use '/' instead

Still, the challenge is to satisfy the specification, not to make it better.

i wrote something for be it a little more conforming... but size explode...

932 bytes

Python: 1266 characters (measured using wc)
from collections import *;import re
A,B,y,c=namedtuple('A',['l','r']),namedtuple('B',['i','b']),type,list.pop
def ab(t):c(t,0);p=c(t,0);c(t,0);return B(p,tm(t))
def tm(t):return ab(t)if t[0]=='\\'else ap(t)
def at(t):
    if t[0]=='(':c(t,0);r=tm(t);c(t,0);return r
    if 96<ord(t[0][0])<123:return c(t,0)
    if t[0]=='\\':return ab(t)
def ap(t):
    l = at(t)
    while 1:
        r = at(t)
        if not r:return l
        l = A(l,r)
def P(s):return tm(re.findall(r'(\(|\)|\\|[a-z]\w*|\.)',s)+['='])
def V(e):o=y(e);return V(e.b)-{e.i} if o==B else V(e.l)|V(e.r)if o==A else{e}
def R(e,f,t):return B(e.i,R(e.b,f,t)) if y(e)==B else A(R(e.l,f,t),R(e.r,f,t))if y(e)==A else t if e==f else e
def N(i,e):return N(chr(97+(ord(i[0])-96)%26),e) if i in V(e)else i
def S(i,e,a): return A(S(i,e.l,a),S(i,e.r,a)) if y(e)==A else(e if e.i==i else B(N(e.i,a),S(i,R(e.b,e.i,N(e.i,a)),a)))if y(e)==B else a if e==i else e
def T(e):
    if y(e)==A:l,r=e;return S(l.i,l.b,r)if y(l)==B else A(T(l),r)if y(l)==A else A(l,T(r))
    if y(e)==B:return B(e.i,T(e.b))
    q
def F(e):o=y(e);return r'(\%s. %s)'%(e.i,F(e.b))if o==B else'(%s %s)'%(F(e.l),F(e.r)) if o==A else e
def E(a):
    try: return E(T(a))
    except NameError:print(F(a))
E(P(input()))

Not the shortest by a long shot, but it correctly handles alpha-renaming and all the examples listed in OPs post.

You can shorten some of those function names, and turn some of them into lambdas. You also have some excess whitespace here and there

(1) Replacing 4-space indentation with a single space will save quite a few bytes. (2) Can you replace except NameError with just except? (3) Two-character function names can be renamed to one-character names. (4) There are a few places where you have assignments that have spaces around the =. (5) if t[0]=='c' can be replaced with if'c'==t[0].

1045 bytes through mostly formatting changes like indentation and lambdas

C++ (gcc), 782 766 758 731 bytes
#include <string>
#include <map>
#define A return
#define N new E
using S=std::string;using C=char;using I=int;S V(I i){A(i>8?V(i/9):"")+C(97+i%9);}S W(C*&s){C*b=s;while(*++s>96);A{b,s};}struct E{I t,i;E*l,*r;E(E&o,I d,I e){t=o.t;i=o.i+(o.i>=d)*e;t?l=N{*o.l,d,e},t-1?r=N{*o.r,d,e}:0:0;}E(I d,std::map<S,I>m,C*&s){t=*s-40?i=m[W(s)],0:*++s-92?l=N{d,m,s},r=N{d,m,++s},++s,2:(m[W(s+=2)]=d,l=N{d+1,m,s+=2},++s,1);}I R(I d){A t?t-1?l->t==1?l->l->s(d,0,*r),*this=*l->l,1:l->R(d)||r->R(d):l->R(d+1):0;}I s(I d,I e,E&v){t?t-1?l->s(d,e,v),r->s(d,e,v):l->s(d,e+1,v):i==d?*this={v,d,e},0:i-=i>d;}S u(I d){A t?t-1?S{"("}+l->u(d)+' '+r->u(d)+')':S{"(\\ "}+V(d)+". "+l->u(d+1)+')':V(i);}};S f(C*s){E a{0,{},s};for(I c=999;a.R(0)&&c--;);A a.u(0);}

Try it online!
The basic idea here is that the code uses an internal representation based on the idea of de Bruijn indices -- except that I reverse the indices to indicate the lambda-depth of the binding of the referred variable.  In the code:

E::t represents the type of a node - 0 for a variable leaf node, 1 for a lambda node, and 2 for a function application node.  (Chosen so that it coincides with the arity of the node, which just happens to be possible.)  Then E::l and E::r are the children as appropriate (just E::l for a lambda node), and E::i is the lambda-depth index for a variable leaf node.
The constructor E::E(E&o,int d,int e) clones a subexpression which was initially at lambda-depth d for pasting into a new location at lambda-depth d+e.  This involves preserving variables at lambda-depth less than d while incrementing variables at lambda-depth at least d by e.
E::s does a substitution of the subexpression v into variable number d in *this while decrementing variable numbers greater than d (and e is an internal detail tracking the lambda-depth increment for when it needs to call E::c).
E::R searches for a single beta-reduction to perform, preferring top-most or left-most instances according to a pre-order search through the AST.  It returns nonzero if it found a reduction to perform or zero if it found none.
E::u is a to_string type operation which reconstitutes a "human readable" string using synthetic names for the variables.  (Note that because of a little golfing of the V helper function it will only generate names containing a through i.)
The constructor E::E(int d, std::map<std::string, int> m, char*&s) does parsing of an input string s into an expression AST based on a mapping m of currently bound variable names into lambda-depth indices.
f is the main function answering the question.

(As you can see at the TIO link, the code does handle variable names with multiple characters, and it also gets a correct answer of (\ a. (\ b. a)) for ((\ f. (\ x. (f x))) (\ y. (\ x. y))).  It also just so happens that the parsing code can handle variable shadowing at no extra cost.)

-16 bytes partially due to idea by ceilingcat (which I had also come up with independently), and partially due to changing E*a=new E; to E&a=*new E; and then changing a-> to a.
-8 more bytes due to another comment by ceilingcat (factor out assignment of a.t from ternary)
-27 bytes from converting parser and clone into constructors of E

702 bytes

Haskell 456 C
It can be much shorter if the lazy evaluation feature of Haskell is fully utilized. Sadly, I don't know how to do it.
Also, many characters are wasted in the parsing step.
data T=A[Char]|B[Char]T|C T T
(!)=(++)
s(A a)=a
s(B a b)="(λ "!a!". "!s b!")"
s(C a b)='(':s a!" "!s b!")"
e d(A a)=maybe(A a)id(lookup a d)
e d(B a b)=B a.e d$b
e d(C a b)=f d(e d a)(e d b)
f d(B x s)q=e((x,q):d)s
f d p q=C p q
d=tail
p('(':'λ':s)=let(A c,t)=p(d s);(b,u)=p(d.d$t);in(B c b,d u)
p('(':s)=let(a,t)=p s;(b,u)=p(d t)in(C a b,d u)
p(c:s)|elem c" .)"=(A "",c:s)|1<2=let((A w),t)=p s in(A(c:w),t)
r=s.e[].fst.p
main=do l<-getLine;putStrLn$r l

Ungolfed version
data Expression = Literal String
                | Lambda String Expression
                | Apply Expression Expression
                deriving Show

type Context = [(String, Expression)]

show' :: Expression -> String
show' (Literal a) = a
show' (Lambda x e) = "(λ " ++ x ++ ". " ++ show' e ++ ")"
show' (Apply e1 e2) = "(" ++ show' e1 ++ " " ++ show' e2 ++ ")"

eval :: Context -> Expression -> Expression
eval context e@(Literal a) = maybe e id (lookup a context)
eval context (Lambda x e) = Lambda x (eval context e)
eval context (Apply e1 e2) = apply context (eval context e1) (eval context e2)

apply :: Context -> Expression -> Expression -> Expression
apply context (Lambda x e) e2 = eval ((x, e2):context) e
apply context e1 e2 = Apply e1 e2

parse :: String -> (Expression, String)
parse ('(':'λ':s) = let
    (Literal a, s') = parse (tail s)
    (e, s'') = parse (drop 2 s')
    in (Lambda a e, tail s'')

parse ('(':s) = let
    (e1, s') = parse s
    (e2, s'') = parse (tail s')
    in (Apply e1 e2, tail s'')

parse (c:s) | elem c " .)" = (Literal "", c:s)
            | otherwise    = let ((Literal a), s') = parse s
                             in (Literal (c:a), s')

run :: String -> String
run = show' . eval [] . fst . parse
main = do
  line <- getLine
  putStrLn$ run line

This fails to do capture-avoiding substitution. For example, ((λ f. (λ x. (f x))) (λ y. (λ x. y))) evaluates incorrectly to (λ x. (λ x. x)).

Got 231 with JavaScript / no Regex
(function f(a){return a[0]?(a=a.map(f),1===a[0][0]?f(function d(b,a,e,c){return b[0]?1===b[0]?[1,d(b[1],a,e,c+1)]:2===b[0]?b[1]===c-1?d(a,0,c-1,0)||b:c-1<b[1]?[2,b[1]+e]:b:[d(b[0],a,e,c),d(b[1],a,e,c)]:b}(a[0],a[1],-1,0)[1]):a):a})

Receives 2-elements arrays. 1 stands for λ and 2 stands for a bruijn index variable.
Test:
zero = [1,[1,[2,0]]]; // λλ0
succ = [1,[1,[1,[[2,1],[[[2,2],[2,1]],[2,0]]]]]]; // λλλ(1 ((2 1) 0))
console.log(JSON.stringify(reduce([succ,[succ,[succ,zero]]]))); // 0+1+1+1
// Output: [1,[1,[[2,1],[[2,1],[[2,1],[2,0]]]]]] = λλ(1(1(1 0))) = number 3

This doesn’t conform to the input and output specifications from the problem.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/