text:
Write a Shift Interpreter
EDIT: As some of you suspected, there was a bug in the official interpreter: the order of composition in . was reversed. I had two versions of the interpreter, and used the wrong one here. The examples were also written for this incorrect version. I have fixed the interpreter in the repository, and the examples below. The description of > was also a bit ambiguous, so I've fixed that. Also, apologies for this taking so long, I was caught up in some real life stuff.
EDIT2: My interpreter had a bug in the implementation of . which was reflected in the examples (they relied on undefined behavior). The issue is now fixed.
Introduction
Shift is an esoteric functional programming language I made a couple of years ago, but published today.
It is stack-based, but also has automatic currying like Haskell.
Specification
There are two datatypes in Shift:

Functions, which have an arbitrary positive arity (number of inputs), and which return a list of outputs. For example, a function that duplicates its only input has arity 1, and a function that swaps its two inputs has arity 2.
Blanks, which are all identical and have no other purpose than not being functions.

A Shift program consists of zero or more commands, each of which is a single ASCII character.
There are 8 commands in total:

! (apply) pops a function f and a value x from the stack, and applies f to x. If f has arity 1, the list f(x) is added to the front of the stack. If it has arity n > 1, a new (n-1)-ary function g is pushed to the stack. It takes inputs x1,x2,...,xn-1 and returns f(x,x1,x2,...,xn-1).
? (blank) pushes a blank to the stack.
+ (clone) pushes to the stack a unary function that duplicates its input: any value x is mapped to [x,x].
> (shift) pushes to the stack a unary function that takes in an n-ary function f, and returns an (n+1)-ary function g that ignores its first argument x, calls f on the remaining ones, and tacks x in front of the result. For example, shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
/ (fork) pushes to the stack a ternary function that takes three inputs a,b,c, and returns [b] if a is a blank, and [c] otherwise.
$ (call) pushes to the stack a binary function that pops a function f and a value x, and applies f to x exactly as ! does.
. (chain) pushes to the stack a binary function that pops two functions f and g, and returns their composition: a function h that has the same arity as f, and which takes its inputs normally, applies f to them, and then fully applies g to the result (calls it as many times as its arity dictates), with unused items from the output of f remaining in the result of h. For example, suppose that f is a binary function that clones its second argument, and g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing [a,b,b], then g is applied to the first two elements of that since its arity is 2, producing [a(b),b], and the stack will finally be [a(b),b,c].
@ (say) pushes a unary function that simply returns its input, and prints 0 if it was a blank, and 1 if it was a function.

Note that all commands except ! simply push a value to the stack, there is no way to perform input, and the only way to output anything is to use @.
A program is interpreted by evaluating the commands one by one, printing 0s or 1s whenever "say" is called, and exiting.
Any behavior not described here (applying a blank, applying a stack of length 0 or 1, calling "chain" on a blank etc.) is undefined: the interpreter may crash, silently fail, ask for input, or whatever.
The Task
Your task is to write an interpreter for Shift.
It should take from STDIN, command line, or function argument a Shift program to be interpreted, and print to STDOUT or return the resulting (possibly infinite) output of 0s and 1s.
If you write a function, you must be able to access the infinite-length outputs in some way (generator in Python, lazy list in Haskell, etc).
Alternatively, you can take another input, a number n, and return at least n characters of the output if it is longer than n.
The lowest byte count wins, and standard loopholes are disallowed.
Test Cases
This Shift program prints 01:
?@!@@!

Starting from the left: push a blank, push say, then apply the say to the blank.
This outputs 0.
Then, push say twice, and apply the second say to the first.
This outputs 1.
This program loops forever, producing no output:
$+.!!+!!

Push call and clone, then apply chain to them (we need two !s since chain is a binary function).
Now the stack contains a function that takes one argument, duplicates it, and calls the first copy on the second.
With +!!, we duplicate this function and call it on itself.
This program prints 0010:
?@$.++>!.!!.!!.!!!!+?/!!!@!@>!!!

Push a blank and say.
Then, compose a binary function that copies its second argument b, then copies the first a and composes it with itself, then applies the composition to the copy of b, returning [a(a(b)),b].
Apply it to say and blank, then apply say to the two elements remaining on the stack.
This program prints 0.
For each !!! that you append to it, it prints an additional 0.
?@+$>!>!+>!///!!>!>!.!!.!!.!!+!!!!

Push a blank and say.
Then, compose a ternary function that takes f,g,x as inputs and returns [f,f,g,g(x)].
Clone that function, and apply it to itself, say, and the blank.
This application does not change the stack, so we can apply the function again as many times as we want.
This program prints the infinite sequence 001011011101111..., where the number of 1s always increases by one:
@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!

The repository contains an annotated version.

I'm a little confused here. When you write "takes in" like in the shift command, do you mean pops or do you mean applied by the apply command?

Also, I'm really not sure from your spec how chain is supposed to work. Could you clarify it with an example please?

@tecywiz121 This is how I understand it: say you've got two functions on the top of the stack, f(x1, x2, ..., xn) and g(y1, y2, ..., ym). Calling . pops both of them and pushes a function h(z1, z2, ..., zn). Now you can eat up all those arguments by gradually currying it with !. After n such applications, the remaining function had only one argument, and at that point it computes f(z1, z2, ..., zn) (i.e. f applied to all the arguments you curried in), which pushes some new values, and then immediately consumes m values from the stack and calls g on them.

@MartinBüttner If Zgarb thinks it's in line with the rules you could use a second input parameter defining the maximal size of the output. This would also be a solution for the lazy evaluation issue.

@tecywiz121 . works exactly as Martin described, except that if f returns a list of less than m values, the result is undefined (the composition has arity n, so it cannot eat more arguments from the stack). Essentially, the output of f is used as a temporary stack, on which g is pushed and applied m times using !, and the result of that is added to the main stack.

@randomra That's a good idea, I'll allow that. Also, apologizes for the delay, I've been unexpectedly busy; the extra examples will still have to wait...

I ran the third example program on my potential submission and got a "stack empty" error on the fourth-last !.  Tried to run the reference implementation for comparison, but got Could not find module 'Control.Monad.Trans.Maybe' (using runhaskell command after installing ghc 7.6.3 on Ubuntu 14.04).  1) Is the empty stack a bug in the Shift example or in my interpreter?  2) How should I configure Haskell so the reference implementation will run?  An answer to either question will make the other question unnecessary. :)

We really, really need some more test cases in order to implement this.

@DLosc I got the same error on my potential submission as well... It is possible that the last example is in fact in error.

Also, +$.!!+!! is not an infinite loop, its just a function. +$.!! is just a call-and-clone-the-results function. After the next +!, we have two call-and-clone-the-results functions. The last ! calls the first call-and-clone on the second. The first call-and-clone calls the first call-and-clone, which then attempts to call on an empty stack, so clearly the function is missing some arguments. So going back up the call stack, the second call-and-clone just embeds the first one as a parameter, and execution halts.

@AJMansfield I apologize for the delay. The composition function had a bug both in the interpreter and the examples, which are fixed now. Thanks for noticing it.

Why is there both $ and ! if they end up doing the same thing?

No problem about the delay, real life >> PPCG.  ;)

FYI, the last three example programs only work with Martin's definition of .--your version gives me an empty stack error in all three.  For example,  part of the 0010 program puts together the function chain(clone,chain(chain,call)) and calls it on say.  But after cloning say and chaining it with the copy, all we have on the temporary stack is chain(say,say), and so call fails.  If everything goes back on the global stack, however, we have a blank to use for the second argument of call.  (Hope this made sense--it's hard without stack diagrams.)

@kirbyfan64sos ! acts directly on the stack, whereas $ pushes a ! onto the stack for use later.

@DLosc Thanks for the observation! The examples and my interpreter are indeed bugged (again), but I think I know where the problem lies.

@DLosc The examples are now fixed.

Either I made a mistake in my implementation, or the specification of chain doesn't fit to what the examples do. As I understand, when the output of f doesn't has the same number of arguments as the input of g, the result is undefined (i.e. the interpreter can throw an error, or do anything else). When running example 3 in my interpreter, I get an error when evaluating chain(f=shift(clone<1>)<2>, g=clone<1>)([say<1>, #]) (the angle brackets show the arity): f returns [say<1>, #, #], and this doesn't fit the arity of clone.

@PaŭloEbermann The output of f may have more arguments than g takes in. The extra arguments are left where they are, and become part of the output of chain(f,g). With your example, the output would be [say<1>, say<1>, #, #], since g takes only the first say<1> as its argument.

@Zgarb thanks, this fixes my interpreter ... I suggested an edit which hopefully makes this clearer (although actually the example already shows this behaviour). I will post my solution when I succeeded golfing it a bit.

Python 2, 752 667 534 506 445 436 427 404 398 393 bytes
This is by no means short... but I did my best. Any golfing suggestions would be very much appreciated...
EDIT6: This is now a script instead of a function. Save it to a file (shift.py, forex), then run it with $ python shift.py '<my_input>'. Make sure to put the input in single quotes, or bash will go crazy with the input characters.
EDIT7: Aaaaaaand... it's not readable anymore. But I got rid of 23 more bytes, so that's good, I guess? I'll post an ungolfed version too.
EDIT8: One more golf, thanks to @Zgarb.
k,d=[],[]
u=k.append
def z(f,a=1):f.a=a;return f
exec "i=!x:x(*map(k.pop,[-1]*x.a)));e=dict(zip('?+>/$.@',[0,!x:u(x)<u(x)),!x:u(!a,*_:x(*_)<u(a),x.a+1))),!x,y,z:u((z,y)[x<1]),3),!x,y:u(!*_:x(y,*_),x.a-1))if x.a>1 else x(y),2),!x,y:u(!*_:x(*_)<i(y),x.a)),2),!x:d.append(`+(x>0)`)<u(x))]))".replace('!',"z(lambda ")
for _ in raw_input():
 try:[i,u][_ in e](e.get(_,e['$']))
 except:break
print d

EDIT: thanks to @DLosc for the golfing help! Managed to reduce it by 85 bytes.
EDIT2: cut out a ton of unnecessary wrappers, and dropped it by another 133 bytes!
EDIT3: ...and 28 more thanks to @Sp3000 and @orlp in chat!
EDIT4: with help from @orlp & @Sp3000, removed all the decorators and now it's 61 bytes shorter.
EDIT5: help meeeeee, I can't stop golfing this.... 9 more bytes gone. Getting rid of the final print statement would save another 7, but then if you run m() in a loop, all the output is on the same line... is that ok?
Here's an ungolfed version:
stack = []
push = stack.append

def arity(func,a=1): #give each of our functions an arity
    func.arity = a
    return func

def do(func): ##pop the args off the stack, then call the function
    args = map(stack.pop,[-1]*func.arity)
    func(*args)

def call(func,arg): #apply is just do(call)
    if func.arity == 1:
        func(arg)
    else:
        def curried(*a): #a quick little currier
            func(arg, *a)
        curried = arity(curried, func.arity - 1)
        push(curried)

def clone(arg):
    push(arg)
    push(arg)

def shift(func):
    def shifted(a, *arg):
        func(*arg)
        push(a)
    shifted = arity(shifted, func.arity + 1)
    push(shifted)

def fork(a, b, c):
    if a == 0:
        push(b)
    else:
        push(c)

def chain(func, gunc):
    def composition(*args):
        func(*args)
        do(gunc)
    composition = arity(composition, func.arity)
    push(composition)

def say(arg):
    print '10'[arg == 0],
    push(arg)

commands = {'?': 0,
            '+': arity(clone),
            '>': arity(shift),
            '/': arity(fork, 3),
            '$': arity(call, 2),
            '.': arity(chain, 2),
            '@': arity(say)}

def interpret(input_string):
    for command in input_string:
        try:
            if command == '!':
                do(call)
            else:
                push(commands[command])
        except RuntimeError: #this handles max recursion depth errors
            break            # for infinite programs
    print

if __name__ == "__main__":
    interpret(raw_input())

Basic idea is that the python list works very nicely as a stack, and by storing u=k.append, not only do I save characters, but I can also use @u as a decorator for pushing functions (not anymore!).
Since the couple of functions which act on functions of n-arity need to be able to accept an arbitrary number of arguments, I had to use *args, which meant that my original plan of tracking f.func_code.co_argcount had to be replaced by an arity decorator attribute.
In terms of handling infinite programs, the interpreter runs until it hits max recursive depth; the RuntimeError handler at the bottom has it exit quietly at that point, and it prints out the current output string then.
Test cases:
>>> tests
['?@!@@!', '$+.!!+!!', '?@$..!!+.!!+>!.!!!!+?/!!!@!@>!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!!!!', '@?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!!']
>>> for t in tests: m(t)
0 1

0 0 1 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

My first reaction: @_@  Seriously, though, nice work--putting actual functions on the stack is a really neat solution.  A few tips: 1) Ternary operators can usually be shortened one way or another. 2) You can replace ['1','0'][...] with just '10'[...]. 3) Why x is 0 and not x==0 (or x<1)? 4) Don't bother specifying RuntimeError, just except will do. 5) Since you're using Python 2, tabs and spaces count as different indentation levels--ugly, but should save you ~25 bytes.

@DLosc thanks so much! I cut it down by ~80 bytes in total, which is a >10% improvement. I tried to get rid of the ternary expression in p(), but it threw a syntax error... :/

You should be able to cut it to x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))--the logical operators are still short-circuiting, but use fewer characters than the ternary. Then save another byte by using x.a-1 as the condition (0/false if x is 1, nonzero/true otherwise) and swapping the 'then' and 'else' expressions: x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y).  (Gotta golf mine some more now that you've passed me... ;^) )

Doesn't work, sadly... one of the functions doesn't get the right number of arguments, and it throws an error.  What I'm looking for right now is a way to deal with the decorators more succinctly.

After running into a similar problem with mine, I understand what's failing now--if x.a==1 is true but x(y) returns something falsy, it tries to evaluate u(...) as well.  But it looks as if you don't need to save the measly 3 bytes that would have given you!  I concede, sir: you have surpassed me.

Just one quibble: the specified output format doesn't have spaces--you can solve by various strategies, not sure which one is shortest.  Of course, your program handles the RuntimeError while mine just asks the user to redirect stderr... so we're probably even on quibbles.  ;^)

What is the *_ for in the lambdas?

@DLosc it didn't seem like the output format was that stringent to me, but I could be wrong - maybe OP would care to comment? I can output a spaceless string, it just costs me 9 bytes.

@mbomb007 each of apply, chain, and shift act on n-ary functions, so you have to be able to handle any size input.

Outputting a space-delimited string is fine.

This is unusually readable for a colf - well done. You can save a couple characters by combining the second and third lines and the eleventh and twelfth lines using semicolons.

@isaacg i have one more golf to post that removes the readability in favor of an exec/translate string... lol. cuts it down by 23 bytes, though... i should probably post an ungolfed version, or just go full Pyth (if i knew Pyth well enough).

Wouldn't raw_input be shorter than using sys.argv?

ha. yes, i believe it would. i shall update. EDIT: wait, maybe not. i'm using sys.stdout.write() for the output, since i can't print inside a lambda. i still need to import sys, so i might as well go with sys.argv[1]. EDIT2: nope, still shorter. good call.

Can you use .replace("!","z(lambda ") instead of .translate({33:u"z(lambda "})?

Oh, yeah, i forgot i don't need to do translate since I'm only subbing one character!

Two less: exec" instead of exec " and 1else instead of 1 else.

Ghostscript
Not golfed yet, since I still need to work out the parsing function.
This implementation uses _ and : instead of > and /, and it requires all the program characters to be separated with spaces. This is because > and / are not valid names in Postscript, and the operators are not self-delimiting, but this will be fixed when I write the parser.
The first part of the code should be fairly transparent, as it is merely repeating the definitions of the operator functions. The magic happens in the definition of !.
/switch {
    /y exch def
    /x exch def
    {x} {y} ifelse
} bind def

/unwrap {
    dup type (arraytype) eq {aload pop} if
} bind def

/! { % IN: <x> <f> OUT: <g>|<f(x)>
    [ 3 1 roll unwrap] cvx %prefix argument into function
    dup /fun exch def %bind

    [ count 1 roll ] { %run the function sandboxed so it can't take any additional args
        2 dict begin
        /=only {} def % suppress output
            {
                fun
            } stopped /err exch def clear err
        end
    } .runandhide

    exch {
        $error /errorname get
        (stackunderflow) ne {
            handleerror
        } if

        $error /newerror false put

        unwrap
    } {
        unwrap exec
    } ifelse
} def

/? 0 def
/+ {{dup}} def
/_ {{/f exch def pop f}} def % using _ instead of >
/: {{? ne 3 1 roll switch}} def % using : instead of /
/$ {{!}} def
/. {{/g exch def exec g}} def
/@ {{dup ? eq {0}{1} ifelse =only}} def

The way ! works is simple: First, it adds argument x to f by prefixing x to the contents of f, pushing it back on the stack, and naming a copy of the result fun.
It then wraps the entire stack up as an array. .runandhide is a Ghostscript extension for running sandboxed code, hiding the contents of the preceding array from the procedure it is invoked on. The dict command pushes a new dictionary on the dict stack, narrowing the scope of names defined within until end pops it back off. It also replaces =only (the output operator I use in @) with a dummy one, suppressing the output during the trial run. stopped is the PostScript equivalent of the try statement found in other languages, and it returns true if its procedure threw an error, and false if it ran to completion.
Once the trial run of fun completes, the program restores the original stack from the hidden array, and if fun completed without error, it then runs it for real, keeping the output.

Python3, 685 670 634 633 bytes
I'm pretty sure this is the longest thing I've ever golfed. It used to be somewhat readable, but following @sirpercival's advice has eliminated that drawback!
from re import*
E,*k="E"
P="e(k.pop(),k.pop())"
def H(a,b):global k;k+=list(a)+[N(b)];exec("k+=%s;"%P*Z(N(b)));return[]
def e(a,b):a=sub("(?<!\d)0",repr(N(b,1)).replace("\\",r"\\"),a,1);return Z(a)and[a]or list(eval(a))
D=list(zip("ilhydsSNZ",[3,2,2]+[1]*6,sub("A","N(a)",',b,c:[N([b,c][a>E])]|,b:e(A,N(b))|,b:["H(%s,%s)"%(A,repr(b))]|:print(0+(a>E),end="")or[A]|:[A]*2|:["S(0,%s)"%A]|,b:b+[A]|,b=-1:sub("\d+",lambda m:str(int(m.group())+b),a)|:len(split("\D0",a))-1').split("|")))
for n,r,f in D:exec(n+"=lambda a"+f)
F=dict(zip("/$.@+>?!",D))
for z in input():n,r,f=F[z];k+=z!="!"and[[n+"(%s)"%",".join("0"*r),E][z=="?"]]or eval(P)

k is the stack, which contains functions represented as strings like "h(0,0)" (which is chain). When a function is passed as an argument to another function, it gets repr'd and all the numbers incremented: "h('h(1,1)',0)". Once all the 0s are replaced in a function, the whole thing is passed to eval, thereby calling the appropriate Python function--most of which are lambda functions generated from the big string in line 6 by exec in line 7.
Getting multiple levels of nested functions incremented, quoted, and escaped properly was the biggest headache. I could save a bit more on regex operations if I could assume that function nesting won't proceed any deeper than 9 levels, but as pointed out in comments that's probably not a safe assumption.
Ungolfed earlier version of code:
from re import *
E="E"
stack=[]

clone=lambda a:[unnest(a)]*2
shift=lambda a:["shifted(0,%s)"%unnest(a)]
fork=lambda a,b,c:[unnest(c if a!=E else b)]
call=lambda a,b:apply(unnest(a),unnest(b))
chain=lambda a,b:["chained(%s,%s)"%(unnest(a),repr(b))]
def say(a):
 print(1 if a!=E else 0,end="")
 return [unnest(a)]

shifted=lambda a,b:b+[unnest(a)]
def chained(a,b):
 global stack
 stack+=list(a)+[unnest(b)]
 exec("stack+=apply(stack.pop(),stack.pop());"*zeros(unnest(b)))
 return []

nest=lambda a,direction:sub("\d+",lambda m:str(int(m.group())+direction),a)
unnest=lambda a:nest(a,-1)
zeros=lambda a:len(split("\D0",a))-1
def apply(a,b):
 a=sub("(?<!\d)0",repr(nest(b,1)).replace("\\",r"\\"),a,1)
 return [a] if zeros(a) else list(eval(a))

functions=dict(zip("+>/$.@",zip(["clone","shift","fork","call","chain","say"],[1,1,3,2,2,1])))

for cmd in input():
 if"!"==cmd:
  stack+=apply(stack.pop(),stack.pop())
 elif"?"==cmd:
  stack+=[E]
 else:
  name,arity=functions[cmd]
  stack+=[name+"(%s)"%",".join("0"*arity)]

The one potential flaw of this implementation is that it uses recursion, so programs that ought to be infinite hit the max recursion depth pretty quickly. (You probably want to redirect stderr when you run an infinite program--otherwise the stack trace will swamp the actual output.) Other than that, everything seems to be working.

Could you write a program that generates the above program and then executes it? You have lots of recurring code that should be compressible like lambda a and k.pop().

@mbomb007 ... I think my brain would explode.  (But see recent edit--I made the k.pop() situation a little less repetitive, anyway.)

can you do the exec/translate trick for all those lambdas? stick them all in one string?

one other comment: I doubt you can rely on function nesting <= 9 with this language

@sirpercival Yes, I was thinking of trying that. And no, I suppose not. :^P

Yup. Wasn't readable before. Is even less so now. Prettify markup should help.

Ceylon, 1167 1057 1031
I don't get it that short as the mono-typed python versions ...
import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}
Here is a formatted (and commented) version of the same code (with spaces/newlines/comments it becomes 4867 bytes):
import ceylon.language.meta.model {
    N=Function
}
import ceylon.collection {
    H=HashMap
}
//↑ Import of stuff we need – with a shorter alias.
// (The comment is down here due to a bug in my comment and space
//  remover – it doesn't remove a comment if it is the first token
//  at all.)

// Our data items are either functions or blanks.
interface D of F | b {}

// There is no point in having many blanks – so here a singleton.
object b satisfies D {}

// The function class. Our functions take a number of data items,
// and return a number of data items.
// We know the arity a, and have also an actual function f, and a number
// or already collected arguments.
class F(shared Integer a, [D+](D+) f, [D*] c = [])
        satisfies D {
    // apply once (= collect one parameter). Returns either the result,
    // or a function with arity one less.
    shared [D+] o(D i) {
        [D+] s = [i].prepend(c);
        return a == 1 then f(*s) else [F(a - 1, f, s)];
    }
    // apply fully (= with all needed parameters).
    // The input size should equal the arity.
    shared [D+] y([D+] i) {
        // merge collected and input arguments.
        return f(*i.prepend(c));
    }
}
// creates a shift function from a ceylon function,
// deriving the arity using reflection.
F m<A>(N<[D+],A> f)
        given A satisfies [D+]
        => F(f.parameterTypes.size, (D+ i) => f.apply(*i));

//
// clone: a unary function that duplicates its input: any value x is mapped to [x,x].
//
[D, D] e(D x) => [x, x];

//
// shift: a unary function that takes in an n-ary function f, and returns an
// (n+1)-ary function g that ignores its first argument x, calls f on the
// remaining ones, and tacks x in front of the result. For example,
// shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
//
[F] t(F f) {
    [D+] g(D+ i) {
        assert (is [D+] r = i.rest);
        return [i[0], *f.y(r)];
    }
    return [F(f.a + 1, g)];
}

//
// fork: a ternary function that takes three inputs a,d,c, and returns [d] if a is a blank,
// and [c] otherwise.
//
[D] k(D a, D d, D c) => a == b then [d] else [c];

//
// call: a binary function that pops a function f and a value x,
//        and applies f to x exactly as ! does.
//
[D+] l(F a, D x) => a.o(x);

//
// chain:  a binary function that pops two functions f and g, and returns their composition:
//         a function h that has the same arity as f, and which takes its inputs normally, applies
//         f to them, and then fully applies g to the result (calls it as many times as its arity
//         dictates), with unused items from the output of f remaining in the result of h. For
//         example, suppose that f is a binary function that clones its second argument, and
//         g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains
//         [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing
//         [a,b,b], then g is applied to the first two elements of that since its arity is 2,
//         producing [a(b),b], and the stack will finally be [a(b),b,c].
//
[F] n(F f, F g) {
    [D+] h(D+ i) {
        // call f, remember the results.
        [D+] r = f.y(i);
        // first some results from f are the arguments to g:
        assert (is [D+] d = r[0:g.a]);
        // remaining results from f are passed back directly, with the results from g.
        return g.y(d).append(r[g.a...]);
    }
    return [F(f.a, h)];
}

//
// say: a unary function that simply returns its input, and prints 0 if it was a blank,
//      and 1 if it was a function.
//
[D] y(D x) {
    process.write(x == b then "0" else "1");
    return [x];
}

//
// Interpreter class, which manages the stack and interprets the commands.
// Just call the r method with the individual command characters.
//
class I() {
    // The stack. The only variable in the whole program.
    variable D[] s = [];

    // a hash map of items to be pushed by commands, most build using the m function.
    // The apply command is not here, this is handled separately by the interpreter.
    value c = H {
        '?'->b,
        '+'->m(`e`),
        '>'->m(`t`),
        '/'->m(`k`),
        '$'->m(`l`),
        '.'->m(`n`),
        '@'->m(`y`)
    };

    // Interprets one command, indicated by a character.
    // Will throw an AssertionError for unknown commands.
    shared void r(Character i) {
        if (i == '!') {
            assert (
                is F f = s[0],
                is D x = s[1]);
            // apply f on x, push the result onto a shortened version of the stack.
            s = f.o(x).append(s[2...]);
        } else {
            assert (is D d = c[i]);
            // push d on top of the stack.
            s = [d].append(s);
        }
    }
}

shared void z() {
    process.readLine()?.collect(I().r);
}

The functions clone e, shift t, fork k, call l, say y and chain n use the last letter of the names for the abbreviated version, because that gave less collisions.
(Trivia: fork was originally defined this way: [Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c]; – when I renamed blank to b, this broke, because it now compared the parameters a and b instead a with the blank. Took me some time to debug.)
The z function is shared because my IDE runs those functions – the command line tool can also run non-shared ones.

The looping versions actually will throw a StackOverflowError at some point, finishing then. The JVM has no recursion stack optimization (or at least none which would work for my program).


text:
Java Package Correction
I have a lot of java projects and I am often making new ones. I have a few helper classes (Vector, Logger, etc.) and it takes a lot of time correcting the first line to the correct package, I would really need a little program to help me fix it automatically.
Your program will first take the name of the package the files are moved to (eg. com.google.raycasting), after that each file with ****<FILENAME>**** between them. You read the input however you want (STDIN, program arguments, file, etc.).
When an EOF is reached, the program should output each file in the same way as in the input, but with the package declaration changed.
Example:
Input:
com.loovjo.tetris
****Vector.java****
package com.loovjo.someoldproject;
class Vector {
    public Vector (int x, int y) {
        System.out.println(x + ", " + y);
    }
}
****Logger.java****
package com.loovjo.someoldproject;
class Logger {
    public String name;
    public Logger(String name) {
        this.name = name;
    }
}

(Of course these aren't the real files.)
Output:
****Vector.java****
package com.loovjo.tetris;
class Vector {
    public Vector (int x, int y) {
        System.out.println(x + ", " + y);
    }
}
****Logger.java****
package com.loovjo.tetris;
class Vector {
    public Vector (int x, int y) {
        System.out.println(x + ", " + y);
    }
}

Further specification on Input/Output:

The package declaration will not always be on the first line, the input may contain some newlines/spaces before it. If this is the case, those characters must be there in the output.
The files in the input will always have correct syntax.

Remember, this is Code Golf, so the shortest code wins!

or .. you can create those helper classes as separate jars and import them ;)

But where's the fun in that?

Test cases should really cover the corners. How about a class which starts with two lines /*Hello*/package foo;//world (both with leading and trailing whitespace)?

I need more examples of input/output.

Mathematica, 106 bytes
StringReplace[Rest@#~StringRiffle~"\n","package "~~__~~";"->"package "<>#[[1]]<>";"]&@StringSplit[#,"\n"]&

Works by splitting the string into its lines and returning all but the first line with any package declarations replaced with the new package.

The Java spec doesn't require the package statement to begin at the beginning of a line, end at the end of a line, or to be on a single line.

@PeterTaylor The code rejoins them before doing the replacement.

Java, 286 bytes
import java.util.*;class P{public static final void main(String[]a){Scanner s=new Scanner(System.in);for(String p="package "+s.nextLine(),e;(e=s.findWithinHorizon("(package[^;]+)|\"([^\"]|\\\\.)*\"|//.*|/\\*([^*]|\\*[^/])*|.|\n",0))!=null;System.out.print(s.match().start(1)>=0?p:e));}}

Take input from STDIN. Test case:
com.loovjo.tetris
****Foo.java****
    package something;
****Bar.java****
package
something.something
;
"package aaa;"
// package bbbb;
/**
 * package cccc;
 */
****Baz.java****
//comment:
package dddd;

Output:
****Foo.java****
    package com.loovjo.tetris;
****Bar.java****
package com.loovjo.tetris;
"package aaa;"
// package bbbb;
/**
 * package cccc;
 */
****Baz.java****
//comment:
package com.loovjo.tetris;

Cannot work with things like package/*;*/stuff, because regex.

source: Stack Exchange

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

sort: votes


text:
Group Therapy: Identify Groups
Write a program, that determines whether the multiplication table of the given finite magma represents a group.
A magma is a set with a binary operation that is closed, that means

for all \$a,b\$ in \$G\$, \$a*b\$ is again in \$G\$ (Closedness)

Let \$(G, * )\$ be a magma. \$(G, * )\$ is a group if

for all \$a,b,c\$ in \$G\$, \$(a*b) * c = a * (b*c)\$ (Associativity)
there exists an element \$e\$ in \$G\$ such that \$e * a = a * e = a\$ for all \$a\$ in \$G\$ (Existence of neutral Element)
for all \$a\$ in \$G\$ there is a \$b\$ in \$G\$ such that \$a * b = b * a = e\$ where \$e\$ is the neutral element (Existence of Inverse)

Specs
The input is of a string of \$n^2-1\$ characters (one character for each element of the magma, allowed are 0-9,a-z) and just represents the table read row by row, omitting the operator name. You can assume that the input represents a valid magma (that means each of the elements appears exactly once in the header row/column).
Example:
Here we have the table of \$\mathbb Z_4\$
+ | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 2 3 0
2 | 2 3 0 1
3 | 3 0 1 2

The input string will be 012300123112302230133012. (Or if we use symbols it could also be nezdnnezdeezdnzzdneddnez). Be aware that the sequence of the elements in the row and in the column do not have to be the same, so the table of \$\mathbb Z_4\$ could also look like so:
+ | 1 3 2 0
-----------
1 | 2 0 3 1
0 | 1 3 2 0
2 | 3 1 0 2
3 | 0 2 1 3

This also means that the neutral element is not necessarily in the first column or first row.
If it is a group, the program has to return the character representing the neutral element. If not it has to return a falsy (distinct from the values 0-9a-z) value
Test cases
Non-groups can easily be constructed by just altering one digit of the string or by artificially altering the tables defining a operation that contradicts one of the group axioms.
Groups
Trivial
* | x
-----
x | x

xxx

Neutral Element: x

\$\mathbb H\$ (quaternion group)
* | p t d k g b n m
-------------------
m | b d t g k p m n
p | m k g d t n p b
n | p t d k g b n m
b | n g k t d m b p
t | g m n p b k t d
d | k n m b p g d t
k | t b p m n d k g
g | d p b n m t g k

ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk

Neutral Element: n

\$D_4\$
* | y r s t u v w x
-------------------
u | u x w v y t s r
v | v u x w r y t s
w | w v u x s r y t
x | x w v u t s r y
y | y r s t u v w x
r | r s t y v w x u
s | s t y r w x u v
t | t y r s x u v w

yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw

Neutral Element: y

\$\mathbb Z_6 \times \mathbb Z_2\$
x | 0 1 2 3 5 7 8 9 a b 4 6
---------------------------
0 | 0 1 2 3 5 7 8 9 a b 4 6
1 | 1 2 3 4 0 8 9 a b 6 5 7
2 | 2 3 4 5 1 9 a b 6 7 0 8
7 | 7 8 9 a 6 2 3 4 5 0 b 1
8 | 8 9 a b 7 3 4 5 0 1 6 2
9 | 9 a b 6 8 4 5 0 1 2 7 3
a | a b 6 7 9 5 0 1 2 3 8 4
b | b 6 7 8 a 0 1 2 3 4 9 5
3 | 3 4 5 0 2 a b 6 7 8 1 9
4 | 4 5 0 1 3 b 6 7 8 9 2 a
5 | 5 0 1 2 4 6 7 8 9 a 3 b
6 | 6 7 8 9 b 1 2 3 4 5 a 0

01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0

Neutral Element: 0

\$A_4\$
* | i a b c d e f g h j k l
---------------------------
i | i a b c d e f g h j k l
a | a b i e c d g h f l j k
b | b i a d e c h f g k l j
c | c f j i g k a d l b e h
d | d h k b f l i e j a c g
e | e g l a h j b c k i d f
f | f j c k i g d l a h b e
g | g l e j a h c k b f i d
h | h k d l b f e j i g a c
j | j c f g k i l a d e h b
k | k d h f l b j i e c g a
l | l e g h j a k b c d f i

iabcdefghjkliiabcdefghjklaabiecdghfljkbbiadechfgkljccfjigkadlbehddhkbfliejacgeeglahjbckidfffjckigdlahbegglejahckbfidhhkdlbfejigacjjcfgkiladehbkkdhflbjiecgalleghjakbcdfi

Neutral Element: i

Non-Groups
A loop (Group missing associativity, or a Quasi-Group with neutral element)
* | 1 2 3 4 5
-------------
1 | 1 2 3 4 5
2 | 2 4 1 5 3
3 | 3 5 4 2 1
4 | 4 1 5 3 2
5 | 5 3 2 1 4

12345112345224153335421441532553214

Neutral Element: 1
(2*2)*3 = 4*3 = 5 != 2 = 2*1 = 2*(2*3)

An IP-loop
(from http://www.quasigroups.eu/contents/download/2008/16_2.pdf)
* | 1 2 3 4 5 6 7
-----------------
1 | 1 2 3 4 5 6 7
2 | 2 3 1 6 7 5 4
3 | 3 1 2 7 6 4 5
4 | 4 7 6 5 1 2 3
5 | 5 6 7 1 4 3 2
6 | 6 4 5 3 2 7 1
7 | 7 5 4 2 3 1 6

123456711234567223167543312764544765123556714326645327177542316

Neutral Element: 1
2*(2*4) = 2*6 = 5 != 7 = 3*4 = (2*2)*4

Monoid (by Quincunx, thanks!)
Monoids are Magmas with associativity and a neutral element.
* | 0 1 2 3
-----------
0 | 0 1 2 3
1 | 1 3 1 3
2 | 2 1 0 3
3 | 3 3 3 3

012300123113132210333333

Neutral Element: 0

Another Monoid
(Multiplication mod 10, without the 5)
We obviously do not have inverses, and the associativity is given by the multiplication modulo 10.
* | 1 2 3 4 6 7 8 9
-------------------
1 | 1 2 3 4 6 7 8 9
2 | 2 4 6 8 2 4 6 8
3 | 3 6 9 2 8 1 4 7
4 | 4 8 2 6 4 8 2 6
6 | 6 2 8 4 6 2 8 4
7 | 7 4 1 8 2 9 6 3
8 | 8 6 4 2 8 6 4 2
9 | 9 8 7 6 4 3 2 1

Neutral Element: 1   12346789112346789224682468336928147448264826662846284774182963886428642998764321

Thought I'd add another table, much bigger, just for fun: http://ideone.com/823aRG

Just for fun, here's another really big one that breaks the 0-9a-z rule: http://ideone.com/vC0ewt

For one that knows nothing about groups,magmas and so on, the specs are fuzzy. For instance, are operations commutative? (so the table is redundant). Moreover. the position of neutral in first row is not related to having the same order in row and column: with 10101010 the order is the same and the neutral is in the last row and column

@edc Groups are not necessarily commutative (commutative groups are called abelian). The definition of the a group is complete (it is the usual definition), anything additional would provide further restriction. In those tables the multiplication with the neutral element is usually in the first row/column, and the sequence of the elements of the header row/column are usually the same, but you can still write down a valid table without following those conventions, which is what I wanted to include here.

If you're curious about the name, there is a question on ELU.  What do you expect from a name made up by a made-up French mathematician?

I deleted some comments which appeared to be obsolete. Please notify me of any comments that should be undeleted.

Octave, 298 290 270 265 chars
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
e=(isscalar(e=find(all(a==u')))&&a(e,:)==u&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

265: Removed unnecessary function handle.
270: After all, the check that e==h for e always satisfying e·a=a and h always satisfying a·h=a was not necessary. This is not possible for them to be different (e·h=?).
The details from the explanation for solution below are still relevant.

290:
function e=g(s)
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')');
for i=2:b a(a==a(i))=i-1;end;
a=a(2:b,2:b--);u=1:b;
s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&sum(t=a==e)==1&&t==t')*e;
for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;e=d(e+1);

The first line
c=@sortrows;d=a=c(c(reshape(a=[0 s],b=numel(a)^.5,b)')'); just stores the input into n x n table (with zero character at the place of operation mark), and then lexicographically sorts columns and rows, so that rows and columns receive the same order:
+ | z a t b                        + | a b t z
-----------                        -----------
z | t b a z         becomes        a | t a z b
b | z a t b      ============>     b | a b t z
t | a z b t                        t | z t b a
a | b t z a                        z | b z a t

Now, I remap "a","b","t","z" to standard 1, 2, 3, 4 , so that I can index the table efficiently. This is done by the line for i=2:b a(a==a(i))=i-1;end;. It yields table like
0   1   2   3   4
1   3   1   4   2
2   1   2   3   4
3   4   3   2   1
4   2   4   1   3

, where we can get rid of the first row and column with a=a(2:b,2:b--);u=1:b;:
3  1  4  2
1  2  3  4
4  3  2  1
2  4  1  3

This table has the given properties:

if the neutral element e exists, exactly one (isscalar) row and one column have the value of row vector u=[1 2 3 ... number-of-elements]:

s=@isscalar;e=(s(e=find(all(a==u')))&&s(h=find(all(a'==u')'))&&...

if each element a has a reverse element a', two things hold:
the neutral element e occurs only once each column and only once each row (sum(t=a==e)==1) and, to satisfy a'·a = a·a', the occurences of e are symmetrical in respect to translation t==t'

a·b can be retrieved by simple t(a,b) indexing. Then we check the associativity in the boring loop:

for x=u for y=u for z=u e*=a(a(x,y),z)==a(x,a(y,z));end;end;end;
The function returns the neutral element the way it appeared in original table (e=d(e+1)) or nil character if the table does not describe a group.

Well done and well explained. Should return the neutral element instead of 1.

Corrected, now returns proper value.

OCTAVE FTW=) I am not sure about two things (coming from matlab), but perhaps you can use it to improve your answer: Could  a(f(a==a(i)))=i-1 be reduced to a(a==a(i))=i-1? Other than that you can perhaps use (...)^.5 instead of sqrt(...).

@flawr Thanks, they both work in octave (version 3.8.1).

Ruby, 401 ... 272
f=->s{n=(s.size+1)**0.5
w=n.to_i-1
e=s[0,w].split''
s=s[w,n*n]
m={}
w.times{(1..w).each{|i|m[s[0]+e[i-1]]=s[i]}
s=s[n,n*n]}
s=e.find{|a|e.all?{|b|x=m[a+b]
x==m[b+a]&&x==b}}
e.all?{|a|t=!0
e.all?{|b|x=m[a+b]
t||=x==m[b+a]&&x==s
e.all?{|c|m[m[a+b]+c]==m[a+m[b+c]]}}&&t}&&s}

This is my first ruby program! This defines a lambda function that we can test by doing puts f[gets.chomp]. I return false for my false value. The first half of the function is simply parsing the input into a map, then the second half checks the possibilities.
f=->s{
    n=((s.size+1)**0.5).to_i
    w=n-1
    e=s[0,w].split'' # create an array of elements of the potential group
    s=s[w,n*n]
    m={} # this map is what defines our operation
    w.times{
        (1..w).each{               # for each element in the row of the table
            |i|m[s[0]+e[i-1]]=s[i] # put the value into the map
        }
        s=s[n,n*n]
    }
    s=e.find{|a| # s is the identity
        e.all?{|b|
            x=m[a+b]
            x==m[b+a]&&x==b # is a the identity?
        }
    }
    e.all?{|a| # implicit return statement
        t = !0 # t = false
        e.all?{|b| # check for inverses
            x=m[a+b]
            t ||= x==m[b+a]&&x==s # t is now true if b was a's inverse
            e.all?{|c|
                m[m[a+b]+c]==m[a+m[b+c]] # check associativity
            }
        } && t
    }&&s
}

Welcome to the wonders of golfing in Ruby! ;) nil is a shorter falsy value than false. Functions can be defined as lambdas like q=->{abort'false'} (if they take parameters, then use [] to call them instead of ()). I believe .chars should already give you an array, so no need for .to_a. If you don't need a trailing newline $><< is one byte shorter than puts plus space. Hash.new doesn't need the parentheses. That's all I can see for now. Keep it up! ;)

The chars thing is odd. What version of Ruby are you using?

@MartinBüttner 1.9.3

Ah, right, I've been looking at the documentation of 2.1.5.

You can replace Math.sqrt(...) with ...**0.5. Also, a if b can be rewritten: b&&a to avoid the two spaces

Seriously wondering if anyone knows why it fails to combine the .all?{...} for finding the identity with the .each{...} for checking associativity, while .each{...}.all?{...} doesn't. For some reason, using just the .all?{...} makes it so that b only goes through the values once, then when the outer .each repeats, it doesn't reset.

JavaScript (ES6) 285 243 278
Run snippet to test (being ES6 it works only on Firefox)
Edit 2 Bug fix. I was wrong in finding the neutral element, checking just one way. (Need better test cases!!!)
Edit Using simpler string concatenation instead of double index (like @Quincunx), I don't know what I was thinking. Also, simplified inverse check, it should still work.

F=t=>(
  e=t.slice(0,d=Math.sqrt(t.length)|0),
  t=t.slice(d).match('.'.repeat(d+1),'g'),
  t.map(r=>{
    for(v=r[i=0],
        j=e.search(v)+1, // column for current row  element
        r!=v+e|t.some(r=>r[j]!=r[0])?0:n=v; // find neutral
        c=r[++i];
       )h[v+e[i-1]]=c
  },h={},n=''),
  e=[...e],!e.some(a=>e.some(b=>(
    h[a+b]==n&&--d, // inverse
    e.some(c=>h[h[a+b]+c]!=h[a+h[b+c]]) // associativity
  )
  ))&&!d&&n
)
input { width: 400px; font-size:10px }
Click on textbox to test - Result :

<input value='...' onclick='O.innerHTML=F(this.value)'> (?)

Groups

<input value='nezdnnezdeezdnzzdneddnez' onclick='O.innerHTML=F(this.value)'> (n)

<input value='ptdkgbnmmbdtgkpmnpmkgdtnpbnptdkgbnmbngktdmbptgmnpbktddknmbpgdtktbpmndkggdpbnmtgk' onclick='O.innerHTML=F(this.value)'> (n)

<input value='yrstuvwxuuxwvytsrvvuxwrytswwvuxsrytxxwvutsryyyrstuvwxrrstyvwxusstyrwxuvttyrsxuvw' onclick='O.innerHTML=F(this.value)'> (y)

<input value='01235789ab46001235789ab4611234089ab6572234519ab67087789a623450b1889ab7345016299ab684501273aab6795012384bb678a0123495334502ab67819445013b67892a5501246789a3b66789b12345a0'onclick='O.innerHTML=F(this.value)'> (0)

Non groups

<input value='12345112345224153335421441532553214' onclick='O.innerHTML=F(this.value)'> (FAIL)

<input value='123456711234567223167543312764544765123556714326645327177542316' onclick='O.innerHTML=F(this.value)'> (FAIL)

<input value='012300123113132210333333' onclick='O.innerHTML=F(this.value)'> (FAIL)

Haskell 391B
import Data.Maybe
import Data.List
o a b=elemIndex b a
l£a=fromJust.o a$l
a§b=[a!!i|i<-b]
f s|isJust j&&and(map(isJust.o h)s)&&and[or[p%q==e|q<-h]&&and[p%(q%r)==(p%q)%r|q<-h,r<-h]|p<-h]=[e]|True="!"where n=floor$(sqrt(fromIntegral$length s+1))-1;h=take n s;g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]];v=s§[n,1+2*n..n+n*n];a%b=g!!(b£v)!!(a£h);j=o g h;e=v!!fromJust j

Curse those imports!

import Data.Maybe
import Data.List

{- rename elemIndex to save characters -}
o a b=elemIndex b a

{- get the index of l in a -}
l£a=fromJust.o a$l

{- extract a sublist of a with indices b -}
a§b=[a!!i|i<-b]

f s |isJust j {-Identity-}
     &&and (map (isJust.o h) s) {-Closure-}
     &&and[
        or [p%q==e|q<-h] {-Inverse-}
        && and [ p%(q%r)==(p%q)%r | q<-h,r<-h ] {-Associativity-}
     |
        p<-h
     ]=[e]
    |True="!"
    where
    {-size-}    n=floor$(sqrt(fromIntegral$length s+1))-1
    {-horiz-}   h=take n s
    {-table-}   g=[s§[a..b]|(a,b)<-zip[1+n,2+n+n..][n+n,3*n+1..(n+1)^2]]
    {-vert-}    v=s§[n,1+2*n..n+n*n]
    {-operate-} a%b=g!!(b£v)!!(a£h)
                j=o g h {-index of the first row identical to the top-}
    {-ident-}   e=v!!fromJust j

Explanation
f::String->String maps the string to either e::Char, the identity element, or !.
The where clause creates a bunch of variables and functions, which I've commented; v::[Int] is the vertical list of elements, h::[Int] the horizontal one.
%::Char->Char->Char applies the group operation to its arguments.
g::[[Int]] is the group table (for dereferencing using %)
j::Maybe Int contains the index of the identity in v if it exists, otherwise Nothing, which is why isJust j is the condition in f for identity.

Can you explain a little bit what is going on here?

I've added a few comments, but the basic gist is 'apply the tests to the group table'. Note that {- -} is a comment. Do you have any more specific questions, or does that clear it up?

Thanks. I guess to really understand it I would need to learn some Haskell first :-)

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 Antiquine
Definitions:
I define a "true antiquine" as follows:

A true antiquine is a non-empty computer program of length n which takes no input and produces a copy of every valid program of length n in the same language, except the original program.

I define a "modified antiquine" as follows:

A modified antiquine is a non-empty computer program of length n which takes no input and produces a copy of every valid ASCII (0-127/7-Bit ASCII, specifically) string of length n, except the original program.

Here's what I mean when I say "produces":

A program is said to produce a string if it, were it allowed to run for an arbitrary finite period of time, would print and/or save and/or display a string that contains the string to be produced. In other words, the output must only contain the produced string as a substring. Inversely, any string that is a substring of the output is considered produced, and conversely, any string which does not contain a substring has not produced that substring.

Problem:
Write either a true antiquine or modified antiquine. The program doesn't need to finish in any reasonable amount of time, but has to finish eventually.
The program must be at least 20 characters long. If writing a true antiquine, there must be at least two other valid programs of the same length in the same language as that the program is written in.
If writing a "modified antiquine", the character length restriction is lifted, but of course, a bigger score penalty is received.

Scoring:
The lowest score wins. The formula for scoring programs is as follows:
(Bytes of Code) [ * 10 if a modified antiquine ]

I like the concept of this question, but I dislike the penalizing of esolangs. This has been discussed many times on Meta and the answer is always: a golfing language always wins but so what? You can get more rep from upvotes for a clever algorithm in a normal language than you can from the green checkmark. Then comes the issue of what is an esolang? Are APL & J esolangs just because they have short programs? The issue here is to find a way of ensuring non-trivial output, as mentioned by @Calvin'sHobbies on Martin's answer. Voting to close. Will delete my own answer if this issue can be solved

I'm voting to close this question because there is currently a major loophole allowing programs that produce no output

@steveverrill Loophole's closed.

@steveverrill: I think if your language is listed on http://esolang.org, you can consider it an esolang. Since APL and J are real programming languages (i.e. intended for real programs), they are legitimate. If APL is to be excluded from this challenge it should be because it doesn't use the ASCII character, not because it has short programs.

Does my program have to terminate eventually?

How will solutions be verified? The number of 20 length programs is way too large.

@BrainSteel Eventually. But the restriction that it must terminate is in more of a theoretical sense.

I'm voting to put this question on hold not because of the loopholes, but because I believe the spec to be unclear. For example, in its current state the true antiquine definition would require all programs containing Unicode to be printed for languages where Unicode is allowed, and for languages where only ASCII 0-127 is allowed a modified antiquine is also a true antiquine, since it's not required that non-programs are not printed. The producing definition also makes little sense, since if abc and def are programs, then the output abcdef also produces bcd and cde.

I think this question could be interesting if the various problems could be resolved. Have a meta discussion.

CJam, 2400
'¡G42#{(_128b:co0c24*o}h

This takes advantage of what seems to be yet another loophole in the question. My code contains the character ¡ (codepoint 161 in Unicode or ISO-8559-1) to avoid checking if the output may produce the original source codes).
Also, after every program with 24 or less bytes, 24 NUL bytes are printed to avoid generating the original source code as part of two outputs and to make sure all strings starting with a run of NUL characters are generated.
How it works
'¡        " Push a non-ASCII character.                   ";
G42#      " Push I := 16 ** 42 = 128 ** 24.               ";
{         " Do:                                           ";
  (_      " Decrement I and push a copy.                  ";
  128b:co " Get the associated ASCII string and print it. ";
  0c24*o  " Print 24 NUL bytes.                           ";
}h        " While I is positive, repeat.                  ";

C, 392 * 10 = 3920
Nobody's submitted a true answer yet, so I'll offer up a baseline solution:
char*s="char*s=%c%s%c;n;main(){char b[999],t[392]={0};sprintf(b,s,34,s,34);while(1){n=0;while(n<392&&t[n]==127)t[n++]=0;if(n==392)break;t[n]++;if(strcmp(b,t)){for(n=0;n<392;n++)putchar(t[n]);putchar(10);}}}";n;main(){char b[999],t[392]={0};sprintf(b,s,34,s,34);while(1){n=0;while(n<392&&t[n]==127)t[n++]=0;if(n==392)break;t[n]++;if(strcmp(b,t)){for(n=0;n<392;n++)putchar(t[n]);putchar(10);}}}

Testing is not recommended outside of a debugging environment--this program will not terminate on its own for the foreseeable future. Prints every combination of 392 characters that isn't the source, separated by newlines. Because the source contains no newlines, the full source will never appear in the output. I've run it through most of the tests I can think of, and it seems to work, but this is of course difficult to verify. This program is essentially a modified quine--rather than printing the source out, it saves it in the string b. It generates a unique string, checks it against b, and outputs it if it is different. This could probably be shortened a bit.

330 bytes


text:
Code Explanation Formatter
Successful code golf submissions are, by nature, filled with crazy symbols all over the place.  To make their submission easier to understand, many code-golfers choose to include an explanation of their code.  In their explanation, the line of code is turned into a vertically exploded diagram.
For example, if this were my code:
1_'[3:~2@+]`

One of the many possible diagrams I could create would look like this:
1
 _'
   [      ]
   [3:    ]
   [  ~   ]
   [   2@ ]
   [     +]
           `

The Goal
In this challenge, you will write an explanation auto-formatting tool which takes a line of code and creates a diagram to which explanatory text can be easily added.
In order to make this a more useful challenge, the user will be able to specify the contents of each line, by providing a formatting string.  The formatting string will be a second line, containing only letters A-Za-z, that is the same length as the program.  The letters show the order in which the characters of the program should be printed in the explanation.
Here is an example of I/O without any bracket-like formatting:
123423
AabcBC

1
    2
     3
 2
  3
   4

Brackets
If more than one character in the program has the same priority level, then that set of characters acts as a single block of code (if they form a group) or a set of brackets (if they contain other characters in-between).  The general rules are simple:

Characters do not appear in a line of the diagram until all other characters of greater priority have already appeared on the lines above it in the diagram.
Characters of equal priority are always printed on the same lines.  If a certain character appears on a line, all other characters of equal priority appear on the line.
A set of characters of equal priority continue to appear on each line until all other characters enclosed by it have appeared at least once.  This allows for "bracket-like" constructions.  If bceab are the priorities, then the b characters will appear on the second line (they are second-highest priority) and will continue to appear until all of the cea characters have appeared.  If the priority string is abcadeafga, then all of bcdefg are considered contained within it, an all 4 as will continue to appear until the g has appeared.

More formatting requirements
All lines of output should be the same length (the length of the input lines), padded with spaces as necessary.  The input program line may contain spaces, although those spaces will also be given a priority letter.  Trailing newlines on output/input are optional.
Scoring
This is code golf, fewest bytes wins.

Examples
Here is a commented example of a piece of code with more complex formatting.
1_'[3:~2@+]`
abbcddeffgch

1            #highest priority is denoted by the lowercase letter a
 _'          #priority b
   [      ]  #all characters with priority c
   [3:    ]  #priority d, but priority c still printed because it encloses more
   [  ~   ]  #priority e
   [   2@ ]  #priority f
   [     +]  #priority g, last line of c because all enclosed characters have appeared
           ` #priority h

An example in Perl:
$_=<>;s/[^aeiou\W]/$&o$&/gi;print
aaaaaabbccccccccccbdddddbbbbeeeee

$_=<>;
      s/          /     /gi;
      s/[^aeiou\W]/     /gi;
      s/          /$&o$&/gi;
                            print

Here are a few examples in CJam, courtesy of Martin Büttner:
l~2*{_2%{3*)}{2/}?_p_(}g;
aabbcdddefffeeggeehhiiccj

l~
  2*
    {                 }g
    {_2%              }g
    {   {   }{  }?    }g
    {   {3*)}{  }?    }g
    {   {   }{2/}?    }g
    {             _p  }g
    {               _(}g
                        ;

q{_eu'[,66>"EIOU"-#)g{'o1$}*}/
abcccddddddeeeeeeefgghiijjhhbb

q
 {                          }/
 {_eu                       }/
 {   '[,66>                 }/
 {         "EIOU"-          }/
 {                #         }/
 {                 )g       }/
 {                   {    }*}/
 {                   {'o  }*}/
 {                   {  1$}*}/

Here is a crazy example just to mess with you:
1_'[3:~2@+]`
azTABACBDCAT

   [ :    ]
   [3: 2  ]
   [3:~2 +]
   [ :~ @+]
  '        `
1
 _

Here is a more explicit example of what happens when brackets overlap like abab.  (Normally, this is not the way you would choose to format your explanation.)
aabbccddaaeebb
aabbccddaaeebb

aa      aa
aabb    aa  bb
aabbcc  aa  bb
aabb  ddaa  bb
  bb      eebb #"aa" no longer appears because all of "bbccdd" have already appeared.

Pyth, 33 40 bytes
JwFHS{Js.e?@zk&gHYsm&gdH}d>_>JxJYx_JYJdJ

Try it online: Pyth Compiler/Executor
Explanation:
Generated with the string aabbbbbzccdeeegfffqhjiiikkpnmmllloooohec:
                                          implicit: z = first input line
Jw                                        J = second input line
  FHS{J                                   for H in sorted(set(J)):
        .e                             J    map each k,Y of enumerate(J) to:
        .e?                            J      .... if ... else ...
        .e @zk                        dJ      z[k] if ... else " "
                                              condition:
        .e @zk gHY                    dJ        H >= Y
        .e @zk&                       dJ        and
        .e @zk     m                 JdJ        map each d of J to:
        .e @zk     m gdH             JdJ          d >= H
        .e @zk     m&                JdJ          and
        .e @zk     m    }d           JdJ          d in ...
        .e @zk     m          xJY    JdJ          index of Y in J
        .e @zk     m        >J       JdJ          substring of J (from index to end)
        .e @zk     m       _         JdJ          reverse substring
        .e @zk     m             x_JYJdJ          index of Y in reversed J
        .e @zk     m      >          JdJ          substring of reversed (from index to end)
        .e @zk    s                   dJ       sum up the booleans (acts as any)
       s                                    sum up the chars and print

So the first input line is z, the second input line is J.
The loop iterates over all chars of J in sorted order and without duplicates. The current char is called H.
Then for each Y of J I print the correspondent char of z or a whitespace, depending on if both of the following conditions are satisfied:

Y <= H (a char first appears in the line H)
there is a char d >= H, which appears in a block starting and ending with Y (brackets).

Examples
This shows how the forth line of the input abcdaeb, abcdaeb is printed. The fourth line is a good representation, since most of the possible cases happen:
code input:  "abcdaeb"
order input: "abcdaeb"

printing the fourth line, H = "d":

   "a" is printed, because "a" <= "d" and ("d" >= "d" and "d" is in "abcda")
   "b" is printed, because "b" <= "d" and ("d" >= "d" and "d" is in "bcdaeb")
   "c" are not printed, because neither "d" nor "e" (chars >= "d") are not in "c"
   "d" is printed, because "d" <= "d" and ("d" >= "d" and "d" is in "d")
   "a" is printed, because "a" <= "d" and ("d" >= "d" and "d" is in "abcda")
   "e" is not printed, because "e" > "d"
   "b" is printed, because "b" <= "d" and ("d" >= "d" and "d" is in "bcdaeb")

therefore the fourth line is: aabb__ddaa__bb

And another example based on a test-case, @Optimizer gave me. (which destroyed my 33 solution).
code input:  "acab"
order input: "acab"

printing the second line, H = "b":

   "a" is printed, because "a" <= "b" and ("c" >= "b" and "c" is in "aca")
   "c" is not printed, because "c" > "b"
   "a" is printed, because "a" <= "b" and ("c" >= "b" and "c" is in "aca")
   "b" is printed, because "b" <= "b" and ("b" >= "b" and "b" is in "b")

therefore the second line is: a_ab

Old version: 58 57 52 bytes
JwKNFHS{J=K.e?eS>_>JxJHx_JHqYH@KkJs.e?@zknYNdK=KXKHN

Try it online: Pyth Compiler/Executor
This creates a mask, which I'll modify before and after printing each line. For more information see the edit history.

CJam, 48 bytes
ll:i:T.{___T#TW%@#~T<>+:e>)1$-@*123Se]m>}z_|(;N*

Explanation
l                                                Code.
 l                                               Priority.
  :i                                             Convert priority to integer.
    :T                                           Save to T.
      .{                                }        For corresponding items:
      .{___                             }        Copy the current priority 3 times.
      .{   T#                           }        First position with this priority.
      .{     TW%                        }        Reverse T.
      .{        @#                      }        First (last) position with this priority.
      .{          ~T<                   }        Cut T at the end of this priority.
      .{             >                  }        Cut at the beginning of this priority.
      .{              +                 }        Insert the current priority to
                                                 prevent the array being empty.
      .{               :e>              }        Array maximum.
      .{                  )1$-          }        Count of integers between the current
                                                 priority and the maximum, inclusive.
      .{                      @*        }        That number of the current character.
      .{                        123Se]  }        Fill irrelevant priorities with spaces.
      .{                              m>}        Rotate the array to make non-spaces
                                                 starting at the current priority.
                                                 Returns a column containing 123 items.
                                         z       Zip to get the rows from columns.
                                          _|     Remove duplicate rows, including
                                                 unused priorities and all-space rows.
                                            (;   Remove the first row (an all-space row).
                                              N* Insert newlines.

CJam, 82 bytes
Pretty long currently and I think I can shave off a few more bytes.
leel:F]z::+F$_&\f{{W=1$=},\;}{]_{0f=_W=),\0=>Lf&Ra#)},F,S*\:+{~;1$L+:L;t}%oNo~}%];

Algorithm
Basic algorithm is as following:

leel:F]z::+ : Group the code, the formatting and the index of each character together
F$_&\f{{W=1$=},\;} : Group the above triplets into priority of printing using the formatting string. This code also makes sure that the priorities are sorted.
]_{0f=_W=),\0=>Lf&Ra#)}, : For each priority group of triplets, get the bounding index range and see if any index is not printed yet. If there is an unprinted index, include this priority group into the "to be printed in this step" group.
F,S*\:+{~;1$L+:L;t}%oNo~}% : After getting all groups to be printed in this step, fill the code into the correct index of an empty space string and then print that string. Also update the array containing the list of printed indexes.

Code explanation to be followed when I am done golfing this.
Example
Here is the code run on the code itself:
Input:
leel:F]z::+F$_&\f{{W=1$=},\;}{]_{0f=_W=),\0=>Lf&Ra#)},F,S*\:+{~;1$L+:L;t}%oNo~}%];
aaabbbcccccdddddeefgghhiffggejkklmmmnoooopppqrrrssssllttttuuuvwwxxxxxxxyvvzzzzjjjj

Output:
lee
   l:F
      ]z::+
           F$_&\
                f{          }
                f{{     },  }
                f{{W=   },\;}
                f{{W=1$ },\;}
                f{{W=  =},\;}
                             {                                                }%];
                             {]_                                              }%];
                             {  {                   },                        }%];
                             {  {0f=                },                        }%];
                             {  {   _               },                        }%];
                             {  {    W=),           },                        }%];
                             {  {        \0=        },                        }%];
                             {  {           >       },                        }%];
                             {  {            Lf&    },                        }%];
                             {  {               Ra#)},                        }%];
                             {                        F,S*                    }%];
                             {                            \:+                 }%];
                             {                               {          }%    }%];
                             {                               {~;        }%    }%];
                             {                               {  1$L+:L; }%    }%];
                             {                               {         t}%    }%];
                             {                                            oNo~}%];

Try it online here

oNo can be replaced with n in TIO.

IDL 8.4, 316 318 304 bytes
New version, still too long, but shorter! And, in the true spirit of IDL, completely vectorized, which means (since there's no for loop) that I can now do it as one line, and run it on itself, once I get my version completely upgraded to 8.4. That'll be edited in later.
One line version:
c=(f='')&read,c,f&l=[0:strlen(f)-1]&c=strmid(c,l,1)&s=strmid(f,l,1)&u=s.uniq()&k=value_locate(u,s)&n=[0:max(k)]&d=hash(n,u.map(lambda(x,y,z:max(z[(r=stregex(y,'('+x+'(.*))?'+x,len=w)):r+w-1])),f,k))&print,n.map(lambda(n,l,c,d,i:i.reduce(lambda(x,i,l,c,d,n:x+(d[l[i]]ge n?c[i]:' ')),l,c,d,n)),k,c,d,l)&end

With line breaks (same number of bytes, subbing \n vs &), and commented:
c=(f='') ;initialize code and format as strings
read,c,f ;read two lines of input from the prompt
l=[0:strlen(f)-1] ;index array for the strings
c=strmid(c,l,1) ;split the code string into an array, via substrings of length 1
s=strmid(f,l,1) ;same for the format string, saving f for regex later
u=s.uniq() ;get the sorted unique values in the format string (sorts A->a)
k=value_locate(u,s) ;assign layer values to the format characters
n=[0:max(k)] ;index array for the unique format characters
d=hash(n,u.map(lambda(x,y,z:max(z[(r=stregex(y,'('+x+'(.*))?'+x,len=w)):r+w-1])),f,k))
print,n.map(lambda(n,l,c,d,i:i.reduce(lambda(x,i,l,c,d,n:x+(d[l[i]]ge n?c[i]:' ')),l,c,d,n)),k,c,d,l)
end ;end the script

Here's an algorithmic breakdown for line 9:
r=stregex(y,'('+x+'(.*))?'+x,len=w) ; r, w = starting position & length of substring in y {format string} bracketed by x {character} (inclusive)
z[(r=...):r+w-1] ; grab a slice of z {layer array} from r to r+w-1 -> layer values for each character in the substring
max(z[...]) ; max layer (depth) of any characters in that slice
u.map(lambda(x,y,z:max(...)),f,k) ;map an inline function of the above to every element of the unique-formatting-character array
d=hash(n,u.map(...)) ; create a hash using the unique indices, the result is a hash of (character:max_substring_depth)

...and 10:
x+(d[l[i]]ge n?c[i]:' ')) ; ternary concatenation: if maxdepth for this character >= current depth, add the character, otherwise add ' '
i.reduce(lambda(x,i,c,d,l,n:...)),,l,c,d,n) ;accumulate elements of i {code/format index array} by passing them through the inline ternary concatenation function
print,n.map(lambda(n,l,c,d,i:i.reduce(...)),k,c,d,l) ;map the depth index through the reduction, ending up with a string for each depth layer, then print it

Lines 9 and 10 do the real work, the rest of it sets up the variables you need for the end. I think this is about as golfed as it's going to get, I can't find anywhere else to do it better.
Old version (everything below here is out of date):
This is nowhere near short enough to win, because this is a terrible golfing language, but no one ever answers in IDL so I'm just gonna go for it.
a=(b='')
read,a,b
c=[0:strlen(b)-1]
d=strmid(b,c,1)
a=strmid(a,c,1)
e=d[uniq(d,sort(d))]
f=list(value_locate(e,d),/e)
s=hash()
for i=0,max(f)do begin
g=stregex(b,'('+e[i]+'(.*))?'+e[i],l=l)
s[i]=max(f[g:g+l-1])
print,f.reduce(lambda(x,y,z:x+(s.haskey(y)?z[y]:' '),s,a)
s=s.filter(lambda(x,y:x[1]gt y),i)
endfor
end

I'm not sure if there's any way I can cut it down more... I could call strmid on both a and b at the same time, but then I spend more bytes indexing d and it works out the same. I'll keep working on it, though! (And tomorrow I'll edit in an explanation of the algorithm.)