text:
Multiply two numbers without using any numbers
You are given as input two strings representing positive integers in base 10, such as "12345" and "42". Your task is to output a string containing their product, "518490" in this case.
The twist is that you may not use any numerical types in your code. No ints, floats, unsigned longs, etc., no built-in complex number types or arbitrary precision integers, or anything along those lines. You many not use literals of those types, nor any function, method, operator etc. that returns them.
You can use strings, booleans, arrays, or anything else that wouldn't normally be used to represent a number. (But note that neither indexing into an array nor getting its length are likely to be possible without invoking a numeric type.) chars are permitted, but you may not perform any arithmetic or bitwise operations on them or otherwise treat them as anything else other than a token representing part of a string. (Lexicographical comparison of chars is allowed.)
You may not work around the restriction. This includes (but is not limited to) using numeric types inside an eval type function, implicit type conversions into numerical types, using numeric or bitwise operators on non-numeric types that support them, using numerical types stored inside container types, or calling functions or external programs that return numerical results in string form. (I reserve the right to add to this list if other workarounds appear in the answers.) You must implement the multiplication yourself using only non-numeric types.
Input and output may be by any convenient method, as long as the data enters and exits your code in the form of a string. You may assume each of the two input arguments contains only the ASCII characters [0-9] and will not start with 0.  Your output shouldn't have leading zeroes either.
One more thing: your code must correctly handle inputs up to at least 10 characters in length, and must run in under a minute on a modern computer for all inputs in that range. Before posting, please check that when given inputs 9999999999 and 9999999999, your program gives an output of 99999999980000000001, in less than a minute. This restriction exists specifically to prevent answers that work by allocating an array of size a*b and then iterating over it, so please bear in mind that answers of that form will not be eligible to win.
This is code-golf, so the shortest valid solution (in bytes) wins.

Can we accept "12345" from STDIN rather than 12345? Or can we accept both numbers as "12345", "42"?

My first thought was to write a function taking string arguments of length m and n and returning an argument of length m*n. But as the strings have to literally contain the ASCII representation of the numbers, I guess that's against the rules.

@Quincunx yes, that sort of thing is fine.

@steveverrill sorry, yes, it really does have to be the base-10 representation in ASCII format.

Say I simply want to increment a char in 0123456789 to the next one. I presume I can't just increase the char code by one because that's a number? Or search for the char in string "0123456789" and take the next one because the  index is a number? So far, I'm not seeing a way to do this without writing out nine cases.

@Quincunx yeah, I really wanted to post this with addition instead of multiplication (at least at first), but I thought it might get closed as a duplicate of http://codegolf.stackexchange.com/questions/20996/add-without-addition-or-any-of-the-4-basic-arithmetic-operators (although it would actually be quite a bit harder). Maybe I'll post the addition version later, depending on how this one goes.

@xnor in many languages it might be shorter to write out all the cases. But I did find this way in Python: a,b="0123456789x".split('0');c=iter(b).next()
if c=='x': c='0'

or in Python 3, a,b="0123456789x".split(x);c,*d=b if c=='x': c='0'

@Nathaniel d='123456789';I=dict(zip('0'+d,d+'0'))

OP is adding rules to invalidate existing answers. On top of that, if we are not allowed to interpret the string input as integer in any way, then there is no difference in multiplying two string integers vs two strings of non integers. Thus, I am voting to close this question as unclear.

@Optimizer I'm not adding rules, I'm clarifying them. The rule is "you may not work around the restriction ... you must implement the multiplication yourself using only non-numeric types." The list in that paragraph is just a list of examples of workarounds. The point of the challenge is that you have to implement a multiplication algorithm, e.g. the long multiplication that you used in school, using string manipulations or other data structures.

@Optimizer also note that even if you interpret adding to the list as changing the rules, no answer has been invalidated by it. millinon's answer and your Javascript answer were both invalid because they don't run in under a minute in the worst case, independently of the rules about workarounds, and that rule has not changed.

The example "long multiplication that you used in school" is also invalid as we are not supposed to used int types in order to add the first argument second number of times. Also, "you may not work around the restrictions" is a very vague rule and that is why I voted to close as unclear what you are asking.

@Optimizer yes, you have to implement addition as well, e.g. also using the algorithm you used in school, and then you have to use that to implement long multiplication. It is a hard challenge. I want answers that actually take up the challenge to be able to compete on a fair playing field, and that is why all workarounds are banned. I do not think this is unreasonable.

Can we lexicographically compare chars? Because that's basically comparing numbers, but might be necessary.

@MartinBüttner hmm, I think I'll somewhat arbitrarily say yes, that's allowed, on the basis that it's a lexicographical operation rather than an arithmetic one. It definitely isn't necessary, because you could always chain up a load of ifs, but I can certainly see it helping.

12345 times 42 = 518490, not 51890 ;)

@COTO d'oh - that was left over from when I was deciding whether to make this challenge addition or multiplication. (Fixed.)

@Nathaniel: Are bools ok? I'd like to use them for indexing in Python, like result=(x,y)[a>b]...

Are languages with implicit type conversion allowed? in Lua you can multiply two strings and the interpreter will take care of interpreting them as number if possible

@Alessandro using such a feature would definitely be a workaround, I'm afraid.

@Falko that's a tricky one, but I think I have to say no, because I think the bool is being implicitly converted to a numerical type in this case. (Using bools in other contexts is fine though.)

is pointer arithmetics allowed?

@LưuVĩnhPhúc no, that comes under "using numeric or bitwise operators on non-numeric types that support them".

Unlambda seems like a great language for this challenge.

Haskell - 180 206 214
r=reverse
f=filter
z=['0'..'9']
a?f|f="1"!a
a?_=a
(a:b)!(c:d)=e:b!d?(e<a)where e=fst$last$zip(f(>=c)z++z)$f(<=a)z
a!c=a++c
a%(b:c)=foldr(!)('0':a%c)$f(<b)z>>[a]
_%b=b
a#b=r$r a%r b

Implements multiplication via repeated addition, and all kinds of digit magic are handled by shifting and filtering the ['0'..'9'] list. Defines an operator # of the type String -> String -> String:
*> :set +s
*> "9990123456789"#"9999876543210"
"99900001219316321126352690"
(0.02 secs, 9862288 bytes)

Looks like we have a new winner! (Though as before, I can't read Haskell of this degree of sophistication - can someone independently check it meets the spec?)

(Also the ['0'..'9'] feels a bit like implicitly treating chars as numbers that can be iterated - is there a short way to generate that list from the string "0123456789" instead?)

@Nathaniel Well first of all the string "0123456789" is the list ['0'..'9']. Second, in Haskell [a..b] is an enumeration, types that have declared instances of the Enum typeclass can be enumerated like that, and the declaration describes how the enumeration works. Bool, the boolean type also has an instance, and therefore you can also do [False..True]. There are barely any numbers involved.

sed, 339 338 bytes
I know this is an old one, but I was browsing and this piqued my interest.  Enough to actually register as a user!  I guess I was swayed by "I would quite like to see a full sed solution – Nathaniel"...

s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g
:o
s/\( .*\)0$/0\1/
/x$/{
x
G
s/ .*/\n/
:a
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
ta
s/\n//g
:c
s/^x/0x/
s/0xxxxxxxxxx/x0/
tc
x
s/x$//
}
/ 0/bo
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

This sed script expects two decimal numbers as input, separated by one space
tests:
time test 518490 = $(./40297.sed <<<)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed <<<"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed <<<"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed <<<"33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917") || echo fail

You might recognise last two as RSA-100 (50 x 50 digits) and RSA-768 (116 x 116 digits).
Using GNU sed on a not-very-modern (2007-era Intel Core 2), the last of those takes over a minute, but it comes faster on a newer processor:

Q6600: >1 minute
i7-3770: 26 seconds
i7-6700: 22 seconds

The puny 10-digit multiply specified in the question takes well under a second on any of these (despite being full of pathological nines).
I believe it's standard sed, with no extensions.  POSIX guarantees hold space of 8192 bytes only, which limits us to multiplying 400x400 digit numbers, but implementations can provide more.  GNU sed is limited only by available memory, so could manage something much bigger, if you're willing to wait.
And I'm confident that I have complied with the rules - that's almost a given in a language that has no numbers.  :-)
Explanation
I use a unary/decimal hybrid, converting decimal numbers into a sequence of unary:
 42 => _xxxx_xx

In unary decimal, addition is easy.  We iterate from least-significant to most-significant digit, concatenating the x's:
   X=965                   Y=106                                 SUM
   _xxxxxxxxx_xxxxxx_xxxxx _x__xxxxxx
   _xxxxxxxxx_xxxxxx       _x_                          _xxxxxxxxxxx
   _xxxxxxxxx              _x                    _xxxxxx_xxxxxxxxxxx
                                      _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx

We then remove whitespace, and deal with carry by converting 10
consecutive x's to one of the next unit:
 _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx       10.6.11
 _xxxxxxxxxx_xxxxxxx_x                10.7.1
 _x__xxxxxxx_x                        1.0.7.1

Once we have addition, multiplication is possible.  We multiply x*y by considering the last digit of
y.  Add x to the accumulator that many times, then move to the next
digit and shift x one decimal place to the left.  Repeat until y is
zero.
Expanded code
#!/bin/sed -f

# Convert to unary decimal.  We save two or three bytes of code by
# reusing 0 as the digit separator.
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

# until y==0

:one

# y ends in zero => x *= 10 and y /= 10
s/\( .*\)0$/0\1/

# while y%10, acc += x, y -= 1
/x$/{
x
G
s/ .*/\n/
# Add x
:add
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
tadd
s/\n//g
:carry
s/^x/0x/
s/0xxxxxxxxxx/x0/
tcarry

# repeat for each unit of y
x
s/x$//
}

# y?
/ 0/bone

# convert hold space to decimal
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

Very satisfying answer, thank you!

Python – 312 286 273
D={}
e=t=""
N=[e]
for c in"0123456789":D[c]=t;D[t]=c;t+="I";N+=N
B=lambda s:[D[c]for c in reversed(s)]
Y=B(input())+N
for a in B(input())+N:
 for c in a:
    s=[];o=e
    for a,b in zip(N,Y):i=a+b+o;o=t<=i and"I"or e;s+=i.replace(t,e),;N=s
 Y=[e]+Y
print e.join(B(N)).lstrip("0")

If (lots of) leading zeroes are allowed, the last 12 characters are not needed.
This essentially performs the standard multiplication by hand. Digits are represented as strings of repeated Is (like primitive Roman numerals). Numbers are represented as lists of digits in reverse order. Addition of single digits is performed by cocatenating strings and removing ten Is if necessary.
Here is an ungolfed version:
N = [""] # zero object: list with a lot of empty strings
D = {}   # dictionary for conversion from and to digits
i = ""   # iterates over digits
for c in "0123456789":
    D[c] = i  # map digit to Roman digit
    D[i] = c  # and vice versa
    i += "I"  # increments Roman digit
    N += N    # add leading zeros to zero

ten = "IIIIIIIIII" # Roman digit ten

# Conversion function
B = lambda s: [D[c] for c in reversed(s)]

def Add(x,y):
    Sum = []
    carryover = ""
    for a,b in zip(x,y):
        increment = a+b+carryover
        carryover = "I" if ten in increment else ""
        increment = increment.replace(ten,"") # take increment modulo ten
        Sum += [increment]
    return Sum

def M(x,y):
    Sum = N[:] # Initiate Sum as zero
    X = B(x)+N # Convert and add leading zeros
    Y = B(y)+N
    for a in X:
        for c in a:
            Sum = Add(Sum,p+Y)
        Y = [""] + Y # multiply Y by 10
    return "".join(B(Sum)).lstrip("0") # Convert back and to string, remove leading zeros.

M(input(),input())

What is this sorcery! How does it work! Wow. Also, here's another golf you could do: def A(x,y):\n S=[];o="" -> def A(x,y,S=[],o=""):. Also, unfortunately, ["","1"][t in i] isn't allowed; it's using a bool to index, treating it as a number. I think that t in i and"1"or"" should work, though.

@Quincunx: Defining S as an argument with a default would not have worked, as it would always be the same list even for different calls of the function and thus not reset to []. You were right about ["","1"][t in i], I fixed that. I also added an explanation.

This is pretty amazing. It gets the green tick for now. (I've edited the question to clarify that leading zeroes in the output aren't allowed - sorry!)

Brainfuck (1328 bytes)
Considerations at first:

Not sure if brainfuck is a valid answer to this questions since I'm not sure whether you consider the cell values as 'numerical types' or not. I don't think so since bf doesn't know types, but that's my own opinion, please correct me if I'm wrong.
An implementation supporting (nearly) unlimited values is necessary.
It might be far too slow, based on the implementation.

I only tested the program with my own interpreter, you can find it here.
Input must be both numbers separated by a single ASCII space.
Golfed:
,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

Ungolfed:
,
>++++++[<----->-]<--
[                                           # read input until space
    >,
    >++++++[<----->-]<--                    # decrease cell by 32 to check if it's a space
]
>>>+<<<<                                    # set multiplier to 1

[

    >>++++[<<---->>-]<<                     # decrease by 16 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<                                    # delete old multiplier

,[>,]                                       # read second number until end of input
>>>+<<<<                                    # set new multiplier

[

    >>+++++++[<<------->>-]<<+              # decrease by 48 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<<<<<                                # delete multiplier

[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>          # multiply both values

# magical algorithm for printing cell value as number taken from Cedric Mamo's code from a previous question
[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

I've taken the code for the output of the value from this answer, thanks to the author for that!
The program might not be valid, but in either way I wanted to share it with you ^^
Update: You can now test it (only for small multiplications) here, thanks to @Sp3000's answer to this contest and SE's new Stack Snippets!

var NUM_CELLS = 30000;var ITERS_PER_SEC = 100000;var TIMEOUT_MILLISECS = 5000;function clear_output(){document.getElementById("output").value="";document.getElementById("stderr").innerHTML=""}function stop(){running=false;document.getElementById("run").disabled=false;document.getElementById("stop").disabled=true;document.getElementById("clear").disabled=false;document.getElementById("wrap").disabled=false;document.getElementById("timeout").disabled=false;document.getElementById("eof").disabled=false}function interrupt(){error(ERROR_INTERRUPT)}function error(e){document.getElementById("stderr").innerHTML=e;stop()}function run(){clear_output();document.getElementById("run").disabled=true;document.getElementById("stop").disabled=false;document.getElementById("clear").disabled=true;document.getElementById("wrap").disabled=true;document.getElementById("timeout").disabled=true;document.getElementById("eof").disabled=true;code=document.getElementById("code").value;input=document.getElementById("input").value;wrap=document.getElementById("wrap").value;timeout=document.getElementById("timeout").checked;eof=document.getElementById("eof").value;loop_stack=[];loop_map={};for(var e=0;e<code.length;++e){if(code[e]=="["){loop_stack.push(e)}else if(code[e]=="]"){if(loop_stack.length==0){error(ERROR_BRACKET);return}else{var t=loop_stack.pop();loop_map[t]=e;loop_map[e]=t}}}if(loop_stack.length>0){error(ERROR_BRACKET);return}running=true;start_time=Date.now();code_ptr=0;input_ptr=0;cell_ptr=Math.floor(NUM_CELLS/2);cells={};iterations=0;bf_iter(1)}function bf_iter(e){if(code_ptr>=code.length||!running){stop();return}var t=Date.now();for(var n=0;n<e;++n){if(cells[cell_ptr]==undefined){cells[cell_ptr]=0}switch(code[code_ptr]){case"+":if(wrap=="8"&&cells[cell_ptr]==255||wrap=="16"&&cells[cell_ptr]==65535||wrap=="32"&&cells[cell_ptr]==2147483647){cells[cell_ptr]=0}else{cells[cell_ptr]++}break;case"-":if(cells[cell_ptr]==0){if(wrap=="8"){cells[cell_ptr]=255}if(wrap=="16"){cells[cell_ptr]=65535}if(wrap=="32"){cells[cell_ptr]=2147483647}}else{cells[cell_ptr]--}break;case"<":cell_ptr--;break;case">":cell_ptr++;break;case".":document.getElementById("output").value+=String.fromCharCode(cells[cell_ptr]);break;case",":if(input_ptr>=input.length){if(eof!="nochange"){cells[cell_ptr]=parseInt(eof)}}else{cells[cell_ptr]=input.charCodeAt(input_ptr);input_ptr++}break;case"[":if(cells[cell_ptr]==0){code_ptr=loop_map[code_ptr]}break;case"]":if(cells[cell_ptr]!=0){code_ptr=loop_map[code_ptr]}break}code_ptr++;iterations++;if(timeout&&Date.now()-start_time>TIMEOUT_MILLISECS){error(ERROR_TIMEOUT);return}}setTimeout(function(){bf_iter(ITERS_PER_SEC*(Date.now()-t)/1e3)},0)}var ERROR_BRACKET="Mismatched brackets";var ERROR_TIMEOUT="Timeout";var ERROR_INTERRUPT="Interrupted by user";var code,input,wrap,timeout,eof,loop_stack,loop_map;var running,start_time,code_ptr,input_ptr,cell_ptr,cells,iterations
<div style="font-size:12px;font-family:Verdana, Geneva, sans-serif;"> <div style="float:left; width:50%;"> Code: <br> <textarea id="code" rows="4" style="overflow:scroll;overflow-x:hidden;width:90%;">,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]</textarea> <br>Input: <br> <textarea id="input" rows="2" style="overflow:scroll;overflow-x:hidden;width:90%;">7 6</textarea> <p> Wrap: <select id="wrap"> <option value="8">8-bit</option> <option value="16">16-bit</option> <option value="32" selected="selected">32-bit</option> </select>   Timeout: <input id="timeout" type="checkbox"></input>  EOF: <select id="eof"> <option value="nochange">Same</option> <option value="0" selected="selected">0</option> <option value="-1">-1</option> </select> </p> </div> <div style="float:left; width:50%;"> Output: <br> <textarea id="output" rows="6" style="overflow:scroll;width:90%;"></textarea> <p> <input id="run" type="button" value="Run" onclick="run()"></input> <input id="stop" type="button" value="Stop" onclick="interrupt()" disabled="true"></input> <input id="clear" type="button" value="Clear" onclick="clear_output()"></input>   <span id="stderr" style="color:red"></span></p></div></div>

I don't know if it's valid either! I guess either everything's a number in Brainfuck, or nothing is.

I like this answer. I ve been messing about with bf myself lately. it kind of sheds light on the fact that at the machine level, everything is just tokens anyway. Hard to say whether this really follows the rules or not.

Ruby: 752 698
This is just to get an answer out there, just done out of curiosity. Edited: now golfed a bit.
$F='0123456789'
$G="#{$F}abcdefghij"
def x(a,b);p(a=~/[13579]$/?b:"",a==""?"":x(Hash[*%w(b0 5 b1 6 b2 7 b3 8 b4 9)].to_a.inject(a.tr($F,'0011223344').chars.zip(a.tr($F,'ababababab').chars).flatten.join("")){|n,q|k,v=q;n.gsub(k,v)}.gsub(/[ab]/,'').sub(/^0*/,''),p(b,b)));end
def p(a,b);j,k=["0#{a}","0#{b}"].map{|c|c.gsub(/./,'0')};c="#{k}#{a}".chars.zip("#{j}#{b}".chars).drop_while{|z|z==%w(0 0)}.map{|m|$G.sub(/#{m.map{|n|"122333444455555666666777777788888888999999999".chars.select{|c|c==n}}.flatten.map{|c|'.'}.join("")}/,"").chars.first}.flatten.join("");d=nil;
while c!=d
 d=c;c="0#{d}".gsub(/[0-9][a-j]/) {|m| m.tr($G,"123456789a#{$F}")}.sub(/^0/,'')
end;c;end
puts x(ARGV.shift,ARGV.shift)

Usage: I had this in a file called peasant.rb:
$ time ruby peasant.rb 9999999999 9999999999
99999999980000000001

real    0m0.129s
user    0m0.096s
sys 0m0.027s

Explanation: it's peasant multiplication, so I repeatedly halve&double. Halving is done by halving digits & marking remainders like so: 1234 -> 0b1a1b2a; then find and replace on the b's: 06a17a; then cleaning up -> 617.
Addition is done like so... first of all, I pad both strings to the same length and make pairs from the digits. Then I add the digits by constructing a string that has the length of each digit and concatenating; I remove a string of that length from the start of '0123456789abcdefghij', and then keep the first char. So, eg, "9"+"9"->"i". NB I avoid actually using length functions here to avoid number types entirely; removing the prefix is done with a regexp instead.
So now I have a string containing a mix of digits and letters. The letters represent numbers with a carry digit; I prepend 0 to the number, then repeatedly replace digit-letter patterns with the result of the carry until the addition is complete.

Very clever answer, exactly the sort of thing I was hoping to see!

I'm actually hoping someone will post one with Church numerals!

That would be cool, though I'm not sure if it would work with the efficiency requirement - I think converting between strings and Church numerals would effectively involve counting up to 99999999980000000001.

Haskell, 231 bytes
This defines an operator # which multiplies two string representations of natural numbers. It works by defining an elementary increment/decrement operation on strings, then uses it to build up addition and multiplication. A little extra magic gives some exponential speedups that make it all possible..
r=reverse
n="9876543210"
t=True
c&(x:y)|c==x=head y|t=c&y
m%[]="1";m%(c:s)|c==last m=head m:m%s|t=c&m:s
[]!y=y;x![]=x;(x:a)!('0':b)=x:a!b;x!y=(r n%x)!(n%y)
"0"?_="0";x?('0':y)|all(=='0')y="0"|t=('0':x)?y;x?y=x?(n%y)!x
x#y=r$r x?r y

This approach is fast enough that even on a 2008 laptop in the unoptimized ghci REPL, the test case takes just a fraction of a second:
λ> :set +s
λ> let test = replicate 10 '9'
(0.00 secs, 0 bytes)
λ> test
"9999999999"
(0.00 secs, 1069784 bytes)
λ> test # test
"99999999980000000001"
(0.06 secs, 13451288 bytes)

Here's a check that all of the two-digit products are correct:
λ> and [ show (x * y) == (show x # show y) | x <- [0..100], y <- [0..100] ]
True

Looks like we have a new leader! (I can't read Haskell though - can someone independently confirm that it fits the spec?)

Yes, that's perfectly cromulent haskell, it fits the spec, and works as advertised. Good job!

Python, 394 349 340 chars
D='0123456789'
R=reversed
U=lambda x:[R for y in D if y<x]
T=U(':')
def A(a,b,r='',c=[]):
 for x,y in map(None,R(a),R(b)):
    d=U(x)+U(y)+c;t=T;c=[R]
    if d<T:t=c=[]
    r=min(k for k in D if U(k)+t>=d)+r
 if c:r='1'+r
 return r
a,b=input()
m=''
while b:
 if list(b).pop()in'13579':m=A(m,a)
 b=list(A(b,A(b,A(b,A(b,b)))));b.pop();a=A(a,a)
print m

Run like:
echo '"9999999999","9999999999"' | ./mulstr.py

Takes 50 milliseconds.
Uses Russian Peasant multiplication.  When adding digits, we convert them to unary ('5' => [R,R,R,R,R]), concatenate the lists, then convert back.  U converts to unary, using R as the unary digit.  We compute b/=2 as b=b*5/10.

A couple golfs: def A(a,b):\n r='';c=[] -> def A(a,b,r='',c=[]):, similarly for def M. You might be able to change for z in D:d.pop()\n c=['X'] to [d.pop()for z in D];c=['X'], in which case you could even collapse it onto the previous if. Also, can if list(b).pop()in'13579' just be if b[:].pop()in'13579'?

@Quincunx: Thanks.  The last one won't work because on the first iteration b is a string, not a list.

You could skip M and write a complete program; a,b=input() is allowed.

b*5/10 is a nice trick.

I just stumbled upon reduce, which allows you to nicen A(b,A(b,A(b,A(b,b)))) to reduce(A,[b,b,b,b,b]). Sadly, this does not affect the character count.

@Wrzlprmft You can simplify to reduce(A,[b]*5) (Depending if such a use of the * operator is counted as being allowed or not)

@meiamsome: It’s rather the 5, that’s the problem, since it’s of a numerical type.

@Wrzlprmft Aha, didn't think about that :P

JavaScript (E6) 375 395 411 449
Edit Golfed
Edit Bug fixed: missing clearing a carry flag
It can be done with just symbol manipulation in near 0 time.
In this version you could use any char instead of the digits, as long as the symbol are in ascending order.
Notes: using strings, hashmap with string key, arrays used as list. No indexing, the arrays are traversed using 'map' or rotated using push & shift.
All '+' are string concatenation.
M=(x,y,S=a=>a.shift()||z,R=a=>[...a].reverse(),e=R('9876543210'),d=[...e])=>
  R(y)[T='map'](b=>
     R(x)[T](a=>(
       u=R[e[a+=b]+v],
       v=R[S[a]+(u<v?'1':z)],
       p[P](t=R[S(o)+u]),
       t<u?v=R[v+'1']:v
     ),o=p,p=[])
    +(v>z&&p[P](v),x+=v=z),
    d[T](a=>d[T](b=>e[P='push'](R[a+b]=S(e)))+e[P](S(e))),
    d[T](a=>d[T](b=>e[d[T](c=>v=c<a?(u=R[u+b])<b?R[v+'1']:v:v,v=u=z='0'),S[a+b]=v,a+b]=u)),
    p=[v=z]
  )&&R(p).join(o)

Less Golfed (maybe I'll add an explanation tomorrow)
M=(x,y)=>(
  R=a=>[...a].reverse(),
  // Addition table s
  s={},
  e=[...'9012345678'],
  [for(a of(d='0123456789'))for(b of(e.push(e.shift()),d))e.push(s[a+b]=c=e.shift())],
  // Multiplication table m,n
  m={},n={},
  [for(a of d)for(b of d)(
     [for(c of(z=u=v='0',d))
     c<a&&(t=s[u+b],t<u?v=s[v+'1']:v,u=t)
     ],m[a+b]=u,n[a+b]=v
  )],
  x=R(x),v=z,o=[],p=[],
  [for(b of R(y))(
     [for(a of x)(
       u=s[m[a+b]+v],v=s[n[a+b]+(u<v?'1':z)],
       p.push(t=s[(o.shift()||z)+u]),
       t<u?v=s[v+'1']:v
     )],
     v>z?p.push(v):o,o=p,p=[],x.unshift(v=z)
  )],
  R(o).join('')
)

Test In FireFox/FireBug console
t0=-new Date
r=M('9999999999','9999999999')
t1=-new Date
console.log("Result",r, "time ms", t0-t1)

Output
Result 99999999980000000001 time ms 14

Possibly there's a slight bug - the output from the 9999999999 case should be 99999999980000000001, not 99999999980000000081

:( going to check

If you're using multiplication tables, how are you getting around the fact that summation isn't allowed?

Summation IS allowed using a hashtable (s in the code). Ex. s['34'] --> '7'. Just symbols, not numbers.  Could be s['cd'] -->'g'

JavaScript: 3710 3604 bytes

Using string lookup tables with 1 digit multiplication and add with carry.
The multiplication is done by digit x digit instead of digit x line.

Golf:
var M={
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};
var A={
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
}
Array.prototype.e=function(){return(''+this)==='';}
String.prototype.s=function(){return this.split('').reverse();}
function B(a,b,c) {
var r='',s='';
a=a.s();
b=b.s();
while (!a.e()||!b.e()||c!=='0') {
x=a.e()?'0':a.shift();
y=b.e()?'0':b.shift();
s=A[c+x+y];
s=s.s();
r=s.shift()+r;
c=s.e()?'0':'1';
}
return r;
}
function m(a,b) {
var s='0',m='';
b.split('').reverse().forEach(function(e){
var z=m;
a.split('').reverse().forEach(function(f){s=B(s,M[e+f]+z,'0');z+='0';});
m+='0';
});
return s;
}

Ungolfed with tests:
var mul = {
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};

var adc = {
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
}

Array.prototype.isEmpty = function() {
  return (''+this) === '';
}

function add(a, b, c) {
  var r = '', s = '';
  a = a.split("").reverse();
  b = b.split("").reverse();
  while (!a.isEmpty() || !b.isEmpty() || c !== '0') {
    x = a.isEmpty() ? '0' : a.shift();
    y = b.isEmpty() ? '0' : b.shift();
    s = adc[c + x + y];
    s = s.split("").reverse();
    r = (s.shift()) + r;
    c = (s.isEmpty()) ? '0' : '1';
  }
  return r;
}

function mult(a, b) {
  var s = '0';
  var m = '';
  b.split('').reverse().forEach(function(e) {
    var z = m;
    a.split('').reverse().forEach(function(f) {
      s = add(s, mul[e + f] + z, '0');
      z = z + '0';
    });
    m = m + '0';
  } );
  return s;
}

function test(a, b) {
  var t0 = (new Date()).getTime();
  var r = mult(a,b);
  var t1 = (new Date()).getTime();
  var e = t1 - t0;
  console.log('mult ' + a + ' * ' + b + ' = ' + r + " (" + e + " ms)");
}

test('12345', '42');
test('9999999999', '9999999999');

This outputs:
mult 12345 * 42 = 518490 (3 ms)
mult 9999999999 * 9999999999 = 99999999980000000001 (47 ms)

Haskell 507 496
This works for arbitrarily large integers. I define custom representations for the natural numbers from 0 to 18 (the largest natural number equal to the sum of two digits), and define little-endian multiplication in terms of digit*number multiplication, which I define in terms of number+number addition, which I define in terms of digit+digit addition. I have a reduction function that expands 10--18 values into their digital decomposition. This then just reads and reverses the two strings, translates to the custom bindings, multiplies, and translates back, reversing to get the right result.
Edit 2
I saved a few characters by creating short local aliases for multi-character commands I use more than once, as well as removing spaces and parentheses, and by replacing (-) pairs with $ when possible.
data S=Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R deriving(Enum, Ord, Eq)
p Z=id
p x=succ.p(pred x)
s Z=id
s x=pred.s(pred x)
z=s J
r[]=[]
r(x:y)|x<J=x:r y
r(x:[])=z x:[A]
r(x:y)=z x:(r$p A a:b)where(a:b)=r y
a x y=r$w(r x)(r y)
m Z _=[]
m _[]=[]
m x y=r$a y(m(pred x)y)
t[]_=[Z]
t _[]=[Z]
t(x:z)y=r$a(m x y)(Z:r(t z y))
i '0'=Z
i x=succ.i.pred$x
b Z='0'
b x=succ.b.pred$x
w[]y=y
w x[]=x
w(x:c)(y:d)=p x y:(w c d)
o=map
v=reverse
f=(o i).v
g=v.o b
main=getLine>>=putStrLn.(\[x,y]->g$t(f x)(f y)).words

For reference, S is the custom integer-like data type, p is 'plus' (digit+digit addition), s is subtract (for reduction), r is reduce (expand into digital decomposition), a is addition (number+number addition), m is multiply (digit*number multiplication), t is times (number*number multiplication), i is 'interpret' (convert string to list of S), b is 'back' (list of S to string), and f and g are just shortenings for golfing purposes. I didn't use numbers, even implicitly; the closest I got was using successors and predecessors, which are much higher level mathematical concepts than addition and multiplication of natural numbers.
Edit
Forgot to include the time profile.
> time echo "9999999999 9999999999" | runhaskell multnonum.hs
99999999980000000001

real    0m0.246s
user    0m0.228s
sys     0m0.012s

Just for good measure:
> time echo "99999999980000000001 99999999980000000001" | runhaskell multnonum.hs
9999999996000000000599999999960000000001

real    0m0.244s
user    0m0.224s
sys     0m0.016s

Let's go insane!
> time echo "9999999996000000000599999999960000000001 9999999996000000000599999999960000000001" | runhaskell multnonum.hs
99999999920000000027999999994400000000699999999944000000002799999999920000000001

real    0m0.433s
user    0m0.424s
sys     0m0.004s

confirmation

Python 2 (555)
I wouldn't normally answer my own challenge so quickly (or at all), but I wanted to prove it could be done. (Luckily some other answers did that before this one, but I couldn't help wanting to finish it.) There's some more golfing that could be done, but I think this is reasonable. It handles the 9999999999x9999999999 case in under 0.03s on my machine.
d="123456789";I=dict(zip('0'+d,d+'0'))
def r(x):return reversed(x)
def s(x):return''.join(x)
def i(x):
    try:
        h=I[x.next()]
        if h!='0':h+=s(x)
        else:h+=i(x)
        return h
    except:return'1'
def b(x,y):
    for c in'0'+d:
        if c==y:break
        x=iter(i(x))
    return x
def a(x,y):
    z=''
    for c in y:
        x=b(x,c)
        try:z+=x.next()
        except:z+='0'
    return z+s(x)
def n(x,y):
    z='0'
    for c in'0'+d:
        if c==y:break
        z=a(iter(z),x)
    return z
def o(x,y):
    x=s(x)
    l='';z=''
    for c in y:
        z=a(iter(z),l+s(n(x,c)))
        l+='0'
    return z
def m(x,y):
    return s(r(o(r(x),r(y))))

Example use: m("12345","42")
It works by doing long multiplication using string manipulations. Sometimes the variables are strings and sometimes they're iterators over strings, which makes it possible to get the first element without using an integer literal. Everything's stored with the digits reversed, so that the first element is the least significant digit.
Here's a function-by-function explanation:

r and s are bookkeeping functions. (r is just an alias for reversed, which makes a reverse iterator, and s converts iterators into strings.)
i increments the number in a string by 1, including cases like 39+1=40 and 99+1=100.
b adds x and y, but y must be only one digit. It works by incrementing x y times.
a adds two numbers together that can both have multiple digits, by calling b for each digit in y.
n multiplies x and y, but y must be only one digit. It works by adding x to itself y times.
o multiplies x and y, where both arguments can have multiple digits. It uses classic long-multiplication
m just converts its string inputs into reverse iterators and hands them to o, then reverses the result and converts it into a string.

Couple golfs: def a(x,y): -> def a(x,y,z=''): and remove next line; similar tricks for other functions, in def o(x,y):, change the x=s(x) to x=s(x);l='';z='', in that for loop, similarly remove newline + paces; instead use ;. Also, I think the if h!='0':h+=s(x)\nelse:h+=i(x) can simply be h+=h!='0'and i(x)or s(x); maybe even h+=(h!='0'and i or s)(x); otherwise, simply change to if'0'!=h. Also things like def r(x):return reversed(x) -> r=reversed

Also, I forgot to mention for s, m: s=lambda x:''.join(x), m=lambda x,y:s(r(o(r(x),r(y)))) instead of the entire function declaration. With just the things that I know work, this brings your byte-count down to 521.

Oh, and one more: for your for loops: for c in'0'+d:\nif c==y:break\nz=a(iter(z),x) -> for c in'0'+d:\nif c!=y:z=a(iter(z),x), although this could significantly change the speed of your program.

@Quincunx thanks! I can see another few improvements as well this morning. (Mostly nesting the loops instead of defining functions.) I'll make these changes if some more competitive answers appear, which seems likely - currently they would put me in the lead, which seems a bit unfair since it was my question and I've had longer to think about it.

Scala, 470 characters
(the ⇒ are standard scala but can equivalently be replaced with => if we're counting bytes)
def p(a: String,b: String)={type D=List[Char]
val d="0123456789".toList
def v(s: String)=s.toList.map{c⇒d.takeWhile(c.!=)}
def u(l:D, a:D):(Char,D)=l match {
case _::_::_::_::_::_::_::_::_::_::m⇒u(m,'a'::a)
case _⇒(('a'::l).zip(d).last._2,a)}
val o=(("", List[Char]())/:v(a).tails.toList.init.map{l⇒(v(b) map {_.flatMap(_⇒l.head)})++l.tail.map(_⇒Nil) reverse}.reduce(_.zipAll(_, Nil, Nil).map{t⇒t._1++t._2}))({(t,e)⇒val s=u(t._2++e,Nil);(s._1+t._1,s._2)})
u(o._2, Nil)._1+o._1}

Here we're emulating digits using the length of lists, being careful not to use any numeric operations - only folds, maps, zips and the like. A number is a list of these digits (order strategically reversed halfway through the computation); we multiply individual digits with flatMap and our rows up with reduce. u handles figuring out the carry (by directly matching against a list of >10 elements, and recursing) and converting digits back to characters, and we use a /: to work our way through the stack with that. The required example completes in less than a second.

Python 2 - 1165, 712, 668 664
I,T,V,N,X,J=raw_input,dict,reversed,None,zip,''.join
D='0123456789'
z,o='01'
A,B=I(),I()
r=i=""
K=map(J,X('666622222222911111551111555884444447773333333','678945672389954132987698765898967457989837654'))
P=T(X(K,map(J,X('344501110011800000440000332673322124652202211','628480244668154132507698505422648609367491852'))))
S=T(X(K,'cdef678945abi65243ed87a9cbaghcdab89egfcb6a987'))
for d in D:P[z+d]=z;S[z+d]=d
def Z(A,B,R=r):
 for a,b in V(map(N,V(z+A),V(z+B))):c=(a or z)+(b or z);s=S[min(c)+max(c)];R=Z(R,o)+T(X('abcdefghi',D))[s]if s>"?"else R+s
 return R
for a in V(A):
 j=""
 for b in V(B):r=Z(r,P[min(a+b)+max(a+b)]+i+j).lstrip(z);j+=z
 i+=z
print r if r else z

Note that I'm not using logical indexing like Z = [X, Y][N == "0"], because this could be interpreted as a boolean casted to a numeric index.
Ungolfed:
A = raw_input()
B = raw_input()

P = {'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
     '10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
     '20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
     '30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
     '40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
     '50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
     '60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
     '70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
     '80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
     '90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81',
     }
S = {'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
     '10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'a',
     '20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'a','29':'b',
     '30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'a','38':'b','39':'c',
     '40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'a','47':'b','48':'c','49':'d',
     '50':'5','51':'6','52':'7','53':'8','54':'9','55':'a','56':'b','57':'c','58':'d','59':'e',
     '60':'6','61':'7','62':'8','63':'9','64':'a','65':'b','66':'c','67':'d','68':'e','69':'f',
     '70':'7','71':'8','72':'9','73':'a','74':'b','75':'c','76':'d','77':'e','78':'f','79':'g',
     '80':'8','81':'9','82':'a','83':'b','84':'c','85':'d','86':'e','87':'f','88':'g','89':'h',
     '90':'9','91':'a','92':'b','93':'c','94':'d','95':'e','96':'f','97':'g','98':'h','99':'i',
     }
L = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8'}

def strSum(A, B):
    R = ""
    for a, b in reversed(map(None, reversed("0" + A), reversed("0" + B))):
        if a == None: a = '0'
        if b == None: b = '0'
        s = S[a + b]
        if s.isdigit():
            R += s
        else:
            R = strSum(R, "1") + L[s]
    return R

i = ""
r = "0"
for a in reversed(A):
    j = ""
    for b in reversed(B):
        p = P[a + b] + i + j
        r = strSum(r, p)
        j += "0"
    i += "0"

r = r.lstrip("0")
if r == "":
    r = "0"

print r

I would say that using min() and max() functions shouldn't be allowed because those are comparing actual integer values, aren't they?

@WorldSEnder: I'd say they compare characters, which is allowed in this challenge. ("Lexicographical comparison of chars is allowed.")


text:
Edge Elimination Number
From Erich Friedman's Math Magic, (problem #2 on that page) your challenge is to find the edge elimination number of a connected graph.
A single edge elimination is the removal of an edge from a graph, without disconnecting the graph, except for creating lone vertices.  For instance, in the graph below, the two leftmost edges and the rightmost edge may be legally eliminated, but the center edge may not, because that would lead to two  disconnected components larger than a single vertex.

An edge elimination sequence is the elimination of every edge in a graph in a specified order. Each elimination must be legal at the point in the sequence when it is performed. For instance, one legal edge elimination sequence on the above graph would be to remove the rightmost edge, then the center edge, then the top-left edge, then the bottom-left edge.
The edge elimination number of a graph is the number of different edge elimination sequences that a graph has. For instance, the above graph has an edge elimination number of 14. There are 4 sequences starting with the top left edge, 4 with the bottom left edge, and 6 with the right edge.
Input: The input graph is guaranteed to be connected. The graph will be given as a list of edges with labeled vertices. for instance, the above graph might be given as:
[(0,2), (1,2), (2,3), (3,4)]

Within that requirement, whatever format is most convenient for your language/code is fine. Don't cheese this. (e.g. no code in the vertex labels.)
Code: You may write a program taking input from the command line or from STDIN, or a function, or a verb, or your language's equivalent.
This is code golf, fewest bytes wins.
Tests:
One edge:
[(0,1)]
1

Path:
[(0,1), (1,2), (2,3), (3,4)]
8

Triangle with two additional edges off one vertex:
[(0,1), (1,2), (0,2), (0,3), (0,4)]
92

Randomly generated:
[(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)]
1240

[(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)]
16560

Again, this is code golf, fewest bytes wins. Please ask any clarifying questions, or tell me if I've done something wrong.

Pyth, 23
L?/1lbf!tfaYTbbsmy-b]db

Explanation:
L: defines a function, y, of one input, b. Returns the value of its body.
?: _ if _ else _
The first argument to ? will be the value returned if we terminate. The second will be the termination test, and the third will be the recursive case.
/1lb: If we terminate, there are two possibilities: we have reached a graph with 1 edge, or we have reached a clearly disconnected graph, which thus has more than one edge. /1lb is 1, floor divided by the length of the input graph. This returns 1 in the base case of a 1 edge graph, or 0 in any disconnected termination case.
faYTb: This is the inner filter of 2nd argument. It filters out every edge Y that overlaps with the edge T of the outer filter. a is setwise intersection.
!tfaYTb: ! is logical not, t is tail, so this will be True if there is exactly 1 edge sharing a vertex with T, or False otherwise.
f!tfaYTbb: This runs the above test on every edge in the graph. It is evaluated in a boolean context, and it is truthy if any edge in the graph shares no vertices with any other edge in the graph. If this is the case, we terminate, because the graph is either disconnected or has 1 edge. Note that there are some disconnected graphs that we do not terminate on, but their recursive calls will eventually terminate with a return value of 0.
smy-b]db: This is the recursive case. We take the sum, s, of the edge elimination number, y, of the graph with each edge removed. -b]d is b with the edge d removed, y-b]d is the EEN of that graph, and my-b]db is this value for d being each edge in the graph, and smy-b]db is the sum of those values.
Tests: (yQ runs the function on the input)
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1)]'
1
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (2,3), (3,4)]'
8
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (0,2), (0,3), (0,4)]'
92
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2), (0,4), (1,2), (1,4), (2,5), (3,4), (3,5)]'
1240
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2),(0,3),(1,3),(1,4),(1,5),(2,3),(3,4),(3,5)]'
16560

I spent half a day trying to translate my algorithm into Pyth, to see how much it would save me, but I couldn't figure out how it worked.

@marinus Sorry for the confusingness of Pyth. I'm planning to write a more detailed learner's guide, but it's going to take a while.

APL (77)
{0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵}

This is a function that takes a list of edges as a graph, i.e.:
      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} (0 2)(0 3)(1 3)(1 4)(1 5)(2 3)(3 4)(3 5)
16560

(Incidentally, this takes about half a second on my computer.)
So the format is [[v1,v2], [v1,v2], ...]. To pass in a single-edge graph, you need to enclose it first, otherwise you get [0,1] instead of [[0,1]]:
      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} ⊂0 1
1

Explanation:

Base case 1 (empty graph):

0=⍴,⍵:1: if the graph is empty, return 1: the current path has emptied the graph while keeping it connected.

Base case 2 (unconnected graph):

C←0/⍨⍴V←∪∊G←⍵: store the list of edges in G, the vertices in V, and a 0 for each vertex in C.
{...}⊃V: See if the graph is connected. Starting with the first vertex:

C[V⍳⍵]:⍬: if the vertex has already been visited, do nothing
C[V⍳⍵]←1: mark the current vertex as visited
G/⍨⍵∊¨G: find each edge this vertex is connected to
⍵~⍨∊: find all vertices involved in those edges, except the current vertex
∇¨: visit all those vertices

0∊C...:0: afterwards, if one of the vertices is not visited, the graph is no longer connected. The current path is invalid, so return 0.

Recursive case:

⍵∘~∘⊂¨⍵: For each edge, create the graph formed by removing that edge, along with any orphaned vertices, from the current graph.
∇¨: For each of those graphs, find its edge elimination number.
+/: Sum those.

Python, 228 bytes
p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

One edge:
c([(0,1)])
1

Path:
c([(0,1), (1,2), (2,3), (3,4)])
8

Triangle with two additional edges off one vertex:
c([(0,1), (1,2), (0,2), (0,3), (0,4)])
92

Randomly generated:
c([(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)])
1240
c([(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
16560

Explanation:
In the first Statement I create a function that checks if a given graph d is connected.
 p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))

The idea of this is: You have to reduce a graph with the given edge-tuples to a list which contains every connected point, called connected_set and a list with all not-connected-yet tuples, called not_connected. Core is the reduce-function, which is a built-in what calls every a given function with two parameters for each element in a list. Reduce works so: reduce(callable, list, initial)
1. callable(initial, list[0]) returns element
2. callable(element, list[1]) ...
3. callable(element, list[n])

For given code I return a tuple contained of (connected_set, not-connected-yet).
The initial value is the connected_set containing of the first found point of the graph. the not-connected-yet is initial en empty list.
lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x])

means:
def reducer((connected_set, not-connected-yet), element):
    #an edge is connected, if left or right point is in connected_set
    if element[0] in connected_set or element[1] in connected_set:
        #add both points to connected_set
        connected_set |= set([x[0], x[1])
        #resolve not-connected-yets
        check_graph(connected_set, not-connected-yet=[], list=not-connected-yet)
        return (connected_set, not-connected-yet)
    else
        return (connected_set, not-connected-yet + [element]

def check_graph(connected_set, not-connected-yet, list):
    return reduce(reducer, list, (connected_set, not-connected-yet))

A Graph is connected, when check_graph returns a tuple, which second element is an empty list.
The rest is addition:
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

means readable:
def count_graph(graph)
    sequences = 0
    #iterate over the possibilities to eliminate an edge on given graph
    # e.g.: graph = [1, 2, 3]
    # i=0: parted_graph = [2, 3]
    # i=1: parted_graph = [1, 3]
    # i=2: parted_graph = [2, 3]
    for i in range(len(graph)):
        parted_graph = graph[:i] + graph[i+1:]
        if len(parted_graph) < 2:
            # a graph with one edge is result of a sequence so raise num
            sequences += 1
        else:
            # continue eliminating if graph is connected
            if check_graph(set(parted_graph[0]), [], parted_graph)[0] == []:
                sequences += count_graph(parted_graph)
    return sequences

Thanks for the answer, and welcome to Programming Puzzles and Code Golf Stack Exchange. If you get a chance, could you provide an explanation of your answer?

I edited an explanation of my answer

Awesome, that's a very clear explanation.

source: Stack Exchange

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/

sort: votes


text:
Simulate a Cyclic Tag System
A cyclic tag system is a tiny, Turing-complete computational model consisting of a two-symbol alphabet (I'll use {0,1}), a finite, nonempty cyclic list of productions that consist of those two symbols, and an unbounded word which also consists of those two symbols.
At each step:

the first element in the word is removed
if it was 0 the current production is skipped
if it was 1 the current production is appended to the end of the word.
the next production becomes active. If this was the last production, go back to the first one.

The system halts when the word becomes empty.
An example (from Wikipedia):
Productions: (010, 000, 1111)
Initial word: 11001

Generation  Production   Word (before)            Word (after)
   0           010           11001             →     1001010
   1           000            1001010          →      001010000
   2           1111            001010000       →       01010000
   3           010              01010000       →        1010000
   4           000               1010000       →         010000000
   5           1111               010000000    →          10000000
   6           010                 10000000    →           0000000010
   7           000                  0000000010 →            000000010
   8           1111                  000000010 →             00000010
   9           010                    00000010 →              0000010

Your task, if you choose to accept it, is to write a program or function that takes:

a list of productions,
the initial word, and
a generation,

and prints or returns the word at that generation.
For example,
cyclic_tag(
      prod=[[0,1,0],[0,0,0],[1,1,1,1]],
      word=[1,1,0,0,1],
      gen=4) => [1,0,1,0,0,0,0]

Implementation details:

The alphabet does not matter. You may use 0 and 1, True and False, T and NIL, A and B, or even 1 and 0, or whatever else you may come up with, as long as you are consistent. All input and output must use the same alphabet, and you must indicate what you are using for 0 and what for 1.
The length of the word must be theoretically unbounded. That is, you may not hardcode a maximum word length. If I run your program on an ideal computer with an infinite amount of memory, your program must theoretically be able to make use of it. (You may ignore your interpreter's/compiler's limits.)
If the given system halts before the given generation is reached, you must return or print the empty word.
The empty production exists, and you must be able to handle it. If you write a full program, your I/O must also be able to handle it.

Edit: I had originally intended for generation 0 to be the input word itself, and generation 1 to be the result of the first step. I.e., I had intended for you to return the before column. However, as I have not been clear enough in stating this, I will accept both options; for each generation you may return the value in either the before or the after column. You must state that you are following the after column, if you are doing so. You must also be consistent in which column you choose.
I will award the smallest code a week from now (10/27/2014).

Um, are you sure your output in the example is correct? Based on the other example you gave, I think that is gen 5...

Can we take the input in a different order?

@FryAmTheEggman: It's correct, I meant the 'before' column. If more people have made this mistake, I will change my question to accept either. I admit I wasn't very clear.

@MartinBüttner: as long as you specify the order, it does not matter.

GolfScript (17 to 19 bytes depending on input format and accepted output format)
18 bytes:
~.@*<{\1,or(@*+}/`

Takes input in the form [1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4 and gives output in the form [1 0 1 0 0 0 0]. (Could be 17 bytes without the last ` if output as 1010000 is acceptable).
Online demo
19 bytes:
~.@*<{\0`or(1&@*+}/

Takes input in the form "11001" ["010" "000" "1111"] 4.
Online demo
Dissection
~        # Evaluate input: stack: word productions gen
.@*<     # Produce a list of the right number of productions with suitable repetition
{        # For each of those productions:
  \      #   Bring the word to the top
  0`or   #   Ensure that we don't get an error if the word is empty
  (1&    #   Pop the first char from the word and evaluate it
  @*     #   Repeat the production that many times
  +      #   Concatenate 0 or 1 copies of the production to the rest of the word
}/       # Endforeach

Credit to Martin Büttner's CJam solution for the idea of generating the list of productions by repetition and truncation.

You are tied with the CJam solution you cite, so I've chosen that answer. If you shave another byte off I'll reconsider :)

@marinus, do you accept the 17 byte version I refer to in the text of my answer?

Hadn't seen that, but it looks valid. You should perhaps mark it a bit more clearly.

Haskell, 55 53 51
(t:w)%p|t=w++p|0<1=w
x%_=x
e w=(!!).scanl(%)w.cycle

this uses True as 1 and False as 0.
example run:
*Main> let t=True ; f=False
*Main> e [t,f,t] [[f,f,f],[t,t,t]] 4
[False,False,False,False,False]

CJam, 31 30 28 27 24 18 bytes
{_@*<{\_0a?(@*+}/}

This defines a block (the closest thing to a functioN), which expects the input to reside on the stack like this
[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9

It will similarly leave an array of 0s and 1s on the stack.
Test it here. Paste the input one the first line, the code on the third line, and append a ~ to actually evaluate the block. E.g.
[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 9
{_@*<{\_0a?(@*+}/}~

If output does not have to have the same form as input
Explanation:
_@*<{\_0a?(@*+}/
_@               "Duplicate the generation and pull the productions to the top.";
  *<             "Repeat the productions N times and take the first N elements.";
    {         }/ "For each element in that list, run this block.";
     \           "Swap production and current word W.";
      _0a?       "W = (W != []) ? W : [0]. This is to ensure we can unshift an element.";
          (      "Unshift the first 0 or 1 from the word.";
           @     "Rotate the stack, pulling the production to the top.";
            *    "Repeat it 0 or 1 times.";
             +   "Append to the word.";

The final state of the word is left on the stack.
Thanks to Peter Taylor for making me revisit this.

l~{_,g{('1=@(:Pa+@@P*+}*}*\; 28 and still scope for improvement (specially the (:P part), but time for lunch

@Optimizer Ah, good idea. Thank you. And yeah, the :P is also annoying me :D

l~{_,g{(si@(:Pa+@@P*+}*}*\; : 27 and after looking into it, :P is actually efficient :P

_,g can also be replaced with _!! but same bytes.

@Optimizer I might as well use _{...}{}? then.

Let us continue this discussion in chat.

Pyth 22
Requires all 3 arguments as separate inputs.
#Vvw=z+tz*@Q%NlQshz)zq

Takes arguments like:
11001
["010","000","1111"]
4

Explanation:
                        : Implicit: z = input(); Q=eval(input())
#                       : Loop until an exception is thrown
 Vvw               )    : for N in range(eval(input()))
    =z                  : assign to z
      +tz               : the sum of the tail of z and
         *@Q%NlQ        : Q[N%len(Q)] times
                shz     : the numeric value of the first character in z
                    zq  : print z then throw exception

Python 2 - 61 67 91 105 124
c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w

Pretty Joe-Basic answer. Assumes the empty production is [[]].
Thanks to @xnor, for pointing out that golfing at 2 a.m. is a poor decision.
Additional thanks to @xnor, to whom I seem to owe 50% of my score.
Sample:
>>> c([[0,1,0],[0,0,0],[1,1,1,1]],[1,1,0,0,1],4)
[1, 0, 1, 0, 0, 0, 0]

Surely it's shorter to use a lambda and just write g and w for x? Also, I think g*w should work to give a truthy value when both g is nonzero and w is nonempty.

Also, I don't understand the inner if x else w. Won't x always be true because this code is only run if x, or am I missing something?

@xnor Surely, you are entirely correct :)

Some more golfing with the and/or trick and rotating p instead of incrementing n: c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w

@xnor Thanks :) Also, now that you made it a function of 3 variables, I think I translate it to Pyth...

Your Pyth is only 3 chars longer than the CJam solution! I want to see it win. Any chance you can save chars by taking input from STDIN (automatic in Pyth) and doing a loop rather than recursing?

@xnor I tried to do that before, and regrettably failed to come anywhere near even this Pyth answer. I was running into problems unpacking the values (I don't think I am allowed to take input 3 times..?) as repeatedly indexing was costing way too much. That was at 2 in the morning, though. I'll try again...

@xnor Finally got it! The trick was to use # to catch the string blowing up, and to manually throw an exception if it finishes normally. Thanks for the motivation :)

Mathematica, 84 80 77 chars
f[_,w_,_]=w;f[p_,{x_,y___},n_/;n>0]:=f[RotateLeft@p,Flatten@{y,p~Take~x},n-1]

Example:
f[{{0, 1, 0}, {0, 0, 0}, {1, 1, 1, 1}}, {1, 1, 0, 0, 1}, 4]

{1, 0, 1, 0, 0, 0, 0}

Javascript ES6 - 88 bytes
f=(p,w,g,n)=>g?w.replace(/(.)(.*)/,(_,a,b)=>f(p,a*1?b+p[(n=n||0)%p.length]:b,g-1,n+1)):w

Looks eerily similar to Fry's answer which just popped up in my browser. (No copying, I do solemnly swear.)
It would appear he went the array route while I went the string/regex route, however.
Expanded:
f = (p,w,g,n) =>
    g ?
        w.replace( /(.)(.*)/, (_,a,b) =>
            f( p, a*1 ? b + p[(n=n||0)%p.length] : b, g-1, n+1 )
        )
    :
        w

Sample Output
f(['010','000','1111'],'11001',4)
"1010000"

Now watch the golf languages come in and massacre both of us. :D

I actually deleted my post because I was getting different answers for the two examples. Have you tried the example where he goes generation by generation? It seems to be off by one compared to the full call example he gave...

And don't worry, I believe you didn't copy me :P

@FryAmTheEggman: Mine consistently generates the "before" column for the numbered generation. This is consistent with the example in the OP, and it seems logical that "generation 0" would simply return the input without processing it, which is consistent with this interpretation. Incidentally, I added the "copy" disclaimer because the solutions were uncannily similar in some respects. We used the same argument names, the same basic recursive structure, and we even added the same phantom fourth argument, n. Great minds, eh? :D

Ok, I guess if either of us is wrong, we're both wrong! United we stand.

@FryAmTheEggman: You weren't wrong about Mr. Peppe. ;)

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


text:
Code Crosswords
This is a cops-and-robbers challenge. Answer here if you are a cop (crossword maker), answer the companion question if you are a robber (crossword solver). You may take on both roles.
Cops (Puzzlers)
Your task is to write a 10×10 crossword puzzle where, instead of words or phrases, snippets of code are the solutions to clues. Each clue will be a nonempty sequence of characters such that running the snippet of code it refers to will print the sequence to stdout.
Your post must include three things:

Your blank 10×10 crossword grid, using # for darks (clue separators) and _ for lights (cells to be filled in).

Every horizontal or vertical sequence of 2 or more lights (bounded by darks or the grid edge) is an entry you must write a clue for. For convenience you should number these in the usual way (left-to-right, top-to-bottom) by replacing the _ at the start of each entry with a unique character identifier (e.g. 1, 2,..., A, B,...).
Your grid may have any number of darks.
Your grid may have any number of clues.
Horizontal entries are always read left-to-right and vertical ones top-to-bottom.

A list of clues that contains every entry in your crossword, down and across.

Clues must contain at least 1 and no more than 10 characters.
If your clues contain spaces make sure they are obvious when you format your post.

Header and footer code snippets, each 20 characters or less.

These run respectively before and after a solution snippet, and may help in renaming long built-ins and such.

The procedure for ensuring a clue matches its corresponding code snippet is:

Concatenate the header, the snippet, and the footer: [header][snippet][footer].
Run this as a normal program (independent of past runs) and look at what was printed to stdout.
If this matches the clue the snippet is a valid solution.

For simplicity you may only use printable ASCII (hex codes 20 to 7E) throughout. The header and footer alone may also contain tabs and newlines.
Additional Notes

For any snippet, running [header][snippet][footer] should not take more than a minute on a decent modern computer.
You must specify your programming language (and version).
You may not use any common hashing algorithms.
You may not use external libraries.
Everything in your code must be deterministic, time invariant, and not need a network connection.
# and _ may occur in snippets (or anywhere else).
You may reveal some of the characters in the crossword as COTO has done. They still count as lights. Robbers are not required to use these, they are just nice hints.

Example
A simple example using Python 3. Header: p=print;t=5;. No footer.
Unsolved grid:
##########
1___2___##
_###_#####
_###_#####
_###_#####
####_#####
####_#####
###3______
####_#####
####_#####

Clues:
ACROSS
1: 8
3: A!
DOWN
1: 7
2: 10

Valid solution:
##########
print(8)##
(###+#####
7###=#####
)###5#####
####;#####
####p#####
###p('A!')
####t#####
####)#####

Robbers (Solvers)
Your task is to solve the crosswords posted by the cops. You must use the same exact programming language as the crossword was given in, but otherwise any solution that matches all the clues is valid.
You may not solve your own crosswords, and you may only attempt to answer each of the other crosswords once.
Remember to post your solutions in the companion question.
Scoring
If a crossword is solved within 72 hours it is no longer in the running. Once a crossword has lasted unsolved for 72 hours it is considered immune and the creator may post the solution (by editing their post and marking it immune).
The winning cop is the user who submitted the immune crossword with the fewest darks (#). In case of ties the highest voted submission wins. The solution must be posted for the answer to be accepted.
The winning robber is the user who solves the most crosswords. The tie-breaker is their sum of up-votes in the companion question.

@grc Sure. The snippet is appended directly to it.

You're already bored with Code Tetris?

@feersum Nobody is solving those. I'm hoping this one is easier on the robbers.

Header: sha512sum <<<", footer: "|head -c10 (in Bash).

@user23013 Yikes. I think I'll forbid hashing.

Designing these crosswords is so much fun. Mine is in CJam, I'll post it later today

"...it is considered immune and the creator may post the solution." Edit it into the answer in this thread, or post it in the robbers thread and link to it?

Damn, 10x10 is too small for some fun Mathematica grids. :D

@professorfish It doesn't really matter but you can just edit the post here. Perhaps put the solution in spoiler tags.

The winning cop is the user who submitted the immune crossword with the fewest darks (#). I think it should be the other way around, more darks makes it easier to solve so the more darks it has the less chances it wins. Winning with a lot of darks would be a lot harder than winning with none at all. Changing it this late into the competition wouldn't be nice though.

@Rodolvertice Then a solution with 100 darks would instantly win.

@Rodolvertice Though then again it could be said to have been said to be instantly solved...so maybe you're right. But I agree that it is too late to change that (making a good puzzle with no darks isn't exactly trivial).

Man, these take a while to make. I'm working on one, but I'm being intentional and careful in order to make one without darks, attempting to be devious.

Is this still active? Can I post new things here?

@ASCIIThenANSI You're welcome to, but there may not be many who will try to crack your entry.

@Calvin'sHobbies OK. Thanks. I'm actually going to see if there's any for me to crack C:

I thought this was a fun challenge. It's a pity there weren't many answers/robbers.

JavaScript, 0 darks – immune

 __________
|123456789A|
|B         |
|C         |
|D         |
|E         |
|F         |
|G         |
|H         |
|I         |
|J         |
 ----------

Here is the solution for all of you:

 __________
|~709-51+90|
|-0x33-31&8|
|8-42^07*70|
|306%4+0x34|
|0xb1204%51|
|-1+2+x>h--|
|'4'*32>>07|
|Math.E>2.7|
|8/2-1-7*22|
|'6'-025036|
 ----------

Header: var h=8,x=5;console.log(

Footer: );

Clues

Across
1. -671
B. 8
C. -460
D. 54
E. 33
F. false
G. 1
H. true
I. -151
J. -10776

Down
1. NaN
2. 15
3. "1131t2"
4. 64
5. -48
6. 49
7. 6
8. true
9. 8
A. 315

Let me know if you think there are any results that I miscalculated.

Are you sure you didn't mix up Across and Down?

MATLAB - 28 Darks
Solved by feersum
Boards
  CLUE #         RESERVED
 __________      __________
|12 3 4 5  |    |    [     |
|# # # # ##|    |#s# # # ##|
|6   # #7 8|    |    # #   |
|# # # # # |    |# # # # # |
|9 A       |    |6  7  y   |
|#B  # # # |    |#   # # # |
|C         |    |        g |
|# # ### # |    |# # ### # |
|# # ##D # |    |# # ##  # |
|E         |    |d         |
 ¯¯¯¯¯¯¯¯¯¯      ¯¯¯¯¯¯¯¯¯¯

Header
g=4;o=magic(3);disp(

Footer
);

Clues
Across

1 2
6 -1i
7 eye(3)
9 0
B sqrt(-1)
C 1/25000
D 0
E [0;0;0]

Down

2 log(1i)
3 100
4 10^16
5 [2,2;2,2]
8 512
A inv(1i)
D zeros(3)

Note that I've changed things up slightly in the clues for this puzzle. Since MATLAB outputs are invariably verbose (for example, even printing the imaginary unit 1i exceeds 10 characters [0 + 1.0000i]) and change depending on the default output format, the clues are all simple expressions whose displayed output is equivalent to that of the corresponding solutions.
In other words, you can consider an actual clue to be disp( CLUE ), where CLUE is the 10-character-or-less clue in the above lists.
Hopefully Calvin doesn't mind. I don't believe this violates the spirit of the clue length rule, which is likely to prevent crossword builders from inserting extremely-hard-to-generate solutions (i.e. words).
Key
    KEY
 __________
|max([1 2])|
|#s#1#0#*##|
|1i^3#*#o\o|
|#n#+#1#n#(|
|6 -7+eye&1|
|#(i)#1#s# |
|.1 ^ 5*(g)|
|#)#2### #^|
|#*#/##~2# |
|diag(-o)>3|
 ¯¯¯¯¯¯¯¯¯¯

solved here

Python
Solved by feersum
Here's one to start us off. I used Python 2.7.8 to obtain the clues. Good luck :)
I've revealed the last snippet since hashing is now disallowed. Also, the grid has 36 darks (I missed the scoring part when I made it).
I've revealed a few more characters to make it easier, but different solutions are fine too.
Crossword grid:
1_234##5##         * . ## ##
_#6_______         #  e /
_#7__##_##         # * ##6##
8________#        3   %    #
##_#_##_##        ##5# ## ##
#9________        #a   *   b
##_#_##_##        ## # ## ##
A________#        b   7  1 #
##_####_##        ## #### ##
#hash('9')        #hash('9')

Clues:
ACROSS
1: 440380.9
6: 12328.7671
7: 72
8: 4519217.0
9: 79920L
A: 1.55826556
B: 7296021944

DOWN
1: 1211477643
2: 17353.0
3: 5.4
4: 1719.0
5: 7514613.78

Header:
a=49481
b=97381
x=

Footer:
print`x`[:10]

To clarify, is the footer on it's own line or is the p right after each snippet?

@Calvin'sHobbies The footer begins on a new line.

Is A-across anything especially diabolical? I have a grid that works for everything except that one.

@feersum It's a mathematical expression like the others, but it could be quite tricky. Remember, the output gets truncated to 10 characters.

Solution

@feersum Well done!

Javascript ES4 - 37 Darks, 10 Reserved
Solved by bazzarg
Boards
   CLUE #         RESERVED
 __________      __________
|1  2 ###3#|    |     ### #|
| ## #45   |    | ## #I   4|
| ## ## # #|    |:##-## # #|
|6        #|    |         #|
| ## ## # #|    | ## ##.# #|
|7         |    |         ]|
| ## ## ###|    | ## ## ###|
|8   #9    |    | +  #   - |
| ## ## ###|    |'## ## ###|
| ##A      |    | ##   4   |
 ¯¯¯¯¯¯¯¯¯¯      ¯¯¯¯¯¯¯¯¯¯

Header
a=3;I=9;t=

Footer
;console.log(t);

Clues
Across

1 51
4 true
6 8.14159265 ...
7 "90"
8 0
9 -10
A "HI"

Down

1 5
2 "2pac"
3 3072
5 false

Note that I've included a second representation of the board marked "reserved" to indicate ten lights with characters already filled in. These are to assist the solver and to restrict/disambiguate the possible solutions. I'm not sure whether Calvin wants to count these as darks or lights.
I've used the two separate representations since some of the filled-in characters are numbers and might be confused for clue numbers, and to declutter the board generally.
There are no whitespace characters in any of the solutions, although you're welcome to fill lights with whitespace characters if they work.
Original Solution

__________
|{},51###6#|
|a##+#I/a<4|
|:##-##[#<#|
|5+Math.PI#|
|}##+##.#+#|
|[I+"0"][0]|
|'##p##/###|
|a+-a#a=~-I|
|'##c##=###|
|]##"\x48I"|
 ¯¯¯¯¯¯¯¯¯¯

As it turns out, bazzarg's solution for 9 across has the - in the wrong place, but the clue was supposed to be 10 instead of -10 (the clue and answer were originally different and I made the switch hastily). Hence we'll just say that two wrongs do make a right in this case. ;)

Interesting idea about the reserved characters. I won't make them count as darks because then people would have even more incentive to not use them.

I ran into the same problem while making a crossword but, this isn't valid. Clues must contain at least 1 and no more than 10 characters.

I don't know JavaScript but something like [object Window] (which is invalid anyway, as user N has pointed out) sounds like it depends on being run in a specific environment. If this is true shouldn't that be specified?

User 23013 is right. 8.141592653589793 and [object Window] are too long.

I can truncate the expression for 6-across. It should be obvious what the number is (and how to generate it) regardless of the number of decimal places. As for 9-across, the output is indeed browser-specific (although I believe the format I've used is common to all five major browsers). I'll amend the actual answer in this case.

@MartinBüttner: Thanks for pointing that out. It's a white.

Is ES4 really what's meant here? (since that spec was never finalized, and is abandoned). Got most of the answers in browser (ES5) then reached one that looked..odd, so thought I'd check.

ES3, then? The current browser standard. It shouldn't require any of the ES6 features.

Solution posted

C - 26 darks, 5 reserved - solved by feersum
   Clue #          Reserved
+----------+     +----------+
|1_2__3_#4_|     |"      #  |
|_#_##_#5_#|     | # ## #  #|
|6___7_8___|     |      8   |
|_#_#9____#|     | # #     #|
|_#AB_#C___|     | #   #    |
|D_#E_____#|     |  #      #|
|_#F#_#_#_#|     | # # # # #|
|_#GH__#I__|     | #    #   |
|_##J_#K#_#|     | ##  # # #|
|L___#M____|     |2 * # _   |
+----------+     +----------+

Header
z[4]={9};main(_){_=

Footer
;printf("%d",_);}

Clues
ACROSS:
1. 48
4. -8
5. -2
6. 0
9. 73
A. 9
C. 0
D. 5
E. 0
G. -2
I. 0
J. 0
L. 18
M. 6247483

DOWN:
1. 45
2. 7680
3. 22
4. -97
5. 0
7. -1073741824
8. 8
B. 0
F. 42
H. 0
K. -2

What is 5 down?

@feersum 5 down is 0 (answer edited)

Does it compile with gcc and run without arguments?

@grc yes it does

Just so I'm not barking up the wrong tree: in M-across, the number has no significance in terms of bit twiddling and I see no realistic way of obtaining it arithmetically. Placing & into M1 gets us the address of _, but this number is ridiculously compiler- and even version-specific. Is this what you were driving at, or is M-across obtainable without converting pointers to ints?

I've solved this one, barring resolution of the above issue.

Solution here

Was there a well-defined way to get 7down?

@feersum the original solution also used >>~_

CJam, 41 darks - solved by Martin Büttner
No header, footer or reserved squares. Let me know of any potential bugs.
The solution I originally had in mind had no whitespace - it is not the one that Martin Büttner found.
Board
#5###6#7__
#4_3____##
1##_#_#_#A
2____##_#_
_##_##9___
_##_#E#_#_
_#C#8_____
##_#_####_
##B_______
D__#_####_

Clues
Across
2: [[4 3]]
4: 24717
7: 32
8: E
9: "" (there is ONE trailing space after the quotes)
B: "m
D: 124

Down
1: [2 2 2 3]
3: 3010936384
5: 2017
6: "18"
7: ' "\"\""
8: !{}
A: -3u3
C: -1
E: Stack: ""

Good luck!

Solved. Thanks for the challenge, that was really fun! :)

Python 2, 0 darks - Immune
Python 2 is only because of the print in the footer. It should work the same way in Python 3 if you change the print statement.
I had fun making this, and overall I'm satisfied and a bit excited about the final result.
Let me know if you think my footer is too cruel (if I knew you could refrain from using a program to brute force it, I'd remove the cruelty.) Fun fact: the variables in the header spell 'bread'.
 __________
|123456789A|
|B         |
|C         |
|D         |
|E         |
|F         |
|G         |
|H         |
|I         |
|J         |
 ----------

Header:
b=7;r=3;e=6;a=.1;d=

Footer:
;print 2*str(d)[::3]

Clues:
Across
1. 74
B. 282.e2
C. 77
D. 8
E. 94
F. 247351.862e1
G. 99
H. -5312-5312
I. -32
J. 300000

Down
1. 61000
2. 251
3. 09333.8333
4. 7878
5. -70
6. -0045.164
7. 88
8. 61225
9. -350
A. 69971

Solution

   __________
 |r+111-37-r|
 |'2.48e+22'|
 |6+765-0*56|
 |30/7%140*2|
 |0xe6b/0x27|
 |18**+9.1-9|
 |047--01551|
 |04/-7.0131|
 |0-1512%989|
 |'30000700'|
  ----------


text:
Code Crosswords - Solutions
This is the companion question for Code Crosswords. Robber answers go here.
See Where should we put robbers? for meta-info.

Solution to es1024's C puzzle

 I had to fudge a bit on 7-Down by invoking undefined behavior. es1024 has indicated that this use of UB was the intended solution. It will work on most people's computers though. I came up with various expressions achieving the desired result such as -1 << 30, 3 << 30, 6 << 29, and ~(~0U/4) but all of them made it impossible for me to get 5-Across. So I used the Intel architecture-specific property that only the least significant 5 bits are used to determine the size of a left shift.
 Note that it needs to be ~_ and not ~1 so that the amount to shift by is not a compile-time constant.
I tested the expressions with the following code:
#define T(X) _ = c; _ = X; printf("%d\n", _);
z[4] = {9};
int main(c)
{
    int _;

    T("01"[0])
    T(-8)
    T(-2)
    T(11<-328111)
    T(+2+71)
    T(9+0)
    T(0**z)
    T(5;)
    T(0<-000)
    T(2+~3)
    T(!91)
    T(!_)
    T(2**z)
    T('_T;')

    T("11"?5*9:2)
    T(15<<9)
    T(0+22)
    T(-211*0-97;)
    T(-17*0)
    T(3+0<<~_)
    T(8+000)
    T(+0)
    T(42)
    T(+!z)
    T(~_)
}

Where does the macro come from? I avoided posting the solution because I couldn't get M-across.

@COTO I don't understand your question, "Where does the macro come from?"

Nevermind. I mistook the #define T as a necessary component to your solution. The question remains, though, why does M-across work? Does defining a multiple-character constant just concatenate the byte values? If so, I learned something new today. :)

@COTO Yes, it is like making a base-256 number. Character literals have type int, so you can put in up to four bytes without loss of information.

I surely did not know that. (Most likely because anyone who's used it in production code has been strangled to death by the people responsible for maintaining their code.) Props for getting it right. :)

professorfish, CJam, 41 darks
(This solution actually requires several spaces, so it's not the one professorfish was looking for.)
#K###I#'32
#HDJ*s\ ##
2##2#`#`#-
4Zm*`##L#3
m##6##]`'
f####e#`#'
`#0#'d1+eu
## #!####9
## '{;'"'m
C5(#}####q

That was great fun. Note that the # beneath the 6 is actually code and not a dark cell. Let's go through this:
Across
Hint 2: [[4 3]]. This was one of the trickier ones, because I really got stuck on trying 4Z]]` or similar. Turns out you can use the Cartesian product m* on stuff that isn't an array, and it will make an array for you. So here it is:
4Zm*`

Hint 4: 24717. By the time I got to this, the H, J, s and trailing space were already in place. The H gave away that I could probably just reuse the 17 and do \ at the end. The J pushes a 19 and 247 == 13 * 19, so:
HDJ*s\

Hint 7: 32. There are a bunch of ways to do this: Y5#, 3 2, ZY, YZ\, 4(2, 2)2, '32. I went with the last one, because starting with a character seemed promising for 7-down, and that turned out to be right.
Hint 8: E. I already had the 'd when I got there, so it was between choosing 'd1+eu, 'deu1+ or a variant where I used ) and a space instead of 1+ (for the non-CJam people, this taking the d character and increment and upper-casing it, in either order). However, the u in the final column looked useful for A-down. So I picked the first of those. In the end, 'd) eu would have worked, too.
Hint 9: "". Well, this had to be "empty string, get string representation, push a space". But also needed the ` for string representation in 7-down, and a space in A-down seemed useful, too, so I chose
]`'

Note that ] might also have been one of LMOQR.
Hint B: "m. I just really had to fit this one in with the rest, but there were few characters that mattered. I already had the { and the m. So instead of using a block, I turned { into a character, discarded it, and then pushed the two required characters:
 '{;'"'m

Hint D: 124. I solved this one together with C-down, which was easiest with a decrement at the end. So I push a 12, a 5, and decrement the latter:
C5(

Down
Hint 1: [2 2 2 3]. That looked too suspiciously like a prime factorisation for it not to be one. :)
24mf`

Hint 3: 3010936384. Factoring this showed that it's actually 386. The only question was how to get the 38 in compliance with 2-across. In the end I needed a * in the third place, so doubling 19 it was:
J2*6#

Hint 5: 2017. Two characters for such a large number? Just use built-in two-digit variables:
KH

Hint 6: "18". I think there's only a single way to do this in 3 characters. Use the built-in 18, convert it to a string, and then to its string representation.
Is`

Hint 7: ' "\"\"". Probably the hardest part of the puzzle. In particular, I needed to get the "\"\"" in only three characters. The trick was to get the string representation of the empty string twice. That led to:
' `L``+

THe + isn't necessary, but was needed by 8-across.
Hint 8: !{}. The block needed to go in the code, so that left only two characters for !, which meant using another literal:
'!{}

Hint A: -3u3.  With the u in place from 8-across, I started to put -3 and 3 in the corners where no other hint cared about them. But then I needed an m at the bottom. I think there are multiple ways to get a 3 with _m_, but the simplest was taking the square root of 9:
-3 'u9mq

Hint C: -1. I already had the decrement there, so I just put a 0 where no one else cared about:
0  (

Hint E: Stack: "". Well that was the simplest one. Just call the debugger:
ed

Calvin's Hobbies has spoken, the answer is valid. I'll edit it into my post

COTO, Javascript ES4, 37 Darks
 __________
|{}=51###6#|
|a##.#I-9<4|
|:##-##"#<#|
|5+Math.PI#|
|}##+##.#+#|
|["9"+0][0]|
|'##p##"###|
|a+-a#a=-10|
|'##c##=###|
|]##"\x48I"|
 ¯¯¯¯¯¯¯¯¯¯

6 across is 5+Math.PI or Math.PI+5; but the latter would leave 'M' and 'h' crossing over into other expressions, seemed unlikely.
A across had to be a string; with 4 in the middle it looked like an escape, the only way you have room for that is with "\x48I".
2 down now ends in a string, so probably is "pac" appended to a number; we'll come back to that.
8 ac is now xxxa, evaluating to zero, so -a+a? a+-a? 3+-a? a+-a looked best since it gave me what looked like a char in a string in 1dn.
1 down contained :5, which could only be legal grammar in {x:5}xxa'x. Since the value returned is 5, it must be pulling it out of the object, so {x:5}['a'], which means the final missing character is also a: {a:5}['a']
1 across now has { at the start. I guessed this was a red herring assignment, tried t={}=51, and it worked. Did not know that!
2 down now has 5xxax"pac"=>"2pac". This has to be 5-a+"pac", somehow, so the second char has to be '.' for the floating point literal.
7 ac is now [xx"xxxx], returning "90". So this has to be an array literal with the value pulled out; there's only room for one value so we have [xx"xx][0]. There's not room for two strings in there, but either "9"+0 or 9+"0" fit.
3 dn; 3072 is 3*1024; the power of 2 is suspicious, and I already had 'I' in there blocking other ways of getting large numbers (like 1eX). So, guessed bitshift; 6<<I turned out to be the answer, leaving +0 to add on to the end.
4 ac now contained a comparison operator; and the second char had to be a valid unary operator (to fit in after both 't=' and 'I'). I guessed '-', and there's several possible solutions left (I-I<4, I-6<4, etc)
5 dn now contained -x..]xxx4. The ".." threw me - there's only a couple of ways that can be legal syntax and is why I asked if ES4 is what was intended - was this some odd feature of that abandoned spec? But then I saw that this was a red herring; -"" is NaN, so -"..]"xx4 must be what's there - a comparison to NaN, returning false; '==' will do, but need to look at the last answer for confirmation...
9ac had several possible solutions, but the restriction on characters that would be allowed for 5dn made me think this was yet another red herring assignment; something =-10. To be honest I also looked at the earlier version of 9dn, and realised that must be something =top (to get a Window back). The variable assigned to could be a or I, it doesn't matter.

Tricky puzzle!

grc's Python puzzle

For all the lengthy floating-point expressions, I made a C++ program to generate Python mathematical expressions by force and evaluates them. It assumes all numbers are floating-point and only supports operators +, -, *, /, //, **, and ~. I used it to get every clue longer than 5 characters except a**9*27%b and the hash. With 6 or less blanks it finishes within a couple of seconds, while there is a bit of a wait for 7.

Solution to COTO's MATLAB puzzle
I guess I golfed this one pretty well, as there are 14 spaces.

This test script:
g=4;
o=magic(3);
D=@disp;

D(max([  2]));
D( i^3);
D(o^0);
D(6 -7+eye  );
D((i));
D(.1  ^5* g );
D(~2);
D(diag(~o)  );

D(asin (1)*i);
D((93+7) +~g);
D(  10e15);
D(2*ones (2));
D(02 ^  9 );
D(-i );
D(~o);

produces the following output:
     2

        0 - 1.0000i

     1     0     0
     0     1     0
     0     0     1

     0

        0 + 1.0000i

   4.0000e-05

     0

     0
     0
     0

        0 + 1.5708i

   100

   1.0000e+16

     2     2
     2     2

   512

        0 - 1.0000i

     0     0     0
     0     0     0
     0     0     0

Good show. A few spaces I didn't expect, but there are also quite a few in the key. I'll post that now. ;)