text:
Self-compiling compiler
This is based on a talk on compilers I listened to a while back, but I, unfortunately, can't remember when or where.
Create the shortest compiler in any language that can compile itself.  Target any reasonable ISA (68K, x86, MIPS, ARM, SPARC, IBM BAL, etc.) that doesn't have a "compile-program" instruction (this may exclude some versions of VAX).  Read source programs from stdin and print generated code to stdout.  You may use the standard C library for I/O and string processing (e.g., _printf).  You don't need to compile the whole language, just any subset that contains the compiler (i.e., just printing an assembly language quine, while impressive, does not count as a solution.)

You need to add some criteria to prevent people from ignoring the input and producing a hard-coded constant output.

Presumably the UCSD pcode machine is "reasonable" as there was a hardware implementation. What about the JVM? Lisp machine? OISC? Hardware forth implementation?

Wow... this is a challenge. (Especially for Perl.)

@dmckee: pcode looks fine, as do JVM bytecode and OISC.  The LISP machine didn't run LISP directly, but the ISA for the LISP machine is fine.  Forth strikes me as a bit too high-level to qualify as an ISA--even if there's hardware optimized to support it--but I'm not well-versed in the language so perhaps I'm misunderstanding its Wikipedia page.  To throw it out there, MMIX is totally fine, too.

Can we write a self-interpreting interpreter?

@George: Self-interpreting interpreters don't count, so I've split self-interpreting interpreters to this question

Actually, this reminds me of some guy who wrote a C-compiler in about 3000 bytes of C-code as a submission to the IOCCC.

@FUZxxl: That became tcc, which is a pretty cool product.

Is it okay to use C as a target "ISA", provided the language being compiled is sufficiently different than C?

@dmckee "C script supported: just add #!/usr/local/bin/tcc -run at the first line of your C source, and execute it directly from the command line." That's pretty cool.

Haskell subset → C - 18926 characters
This compiles a small subset of Haskell to C.  Features it supports:

Pattern matching and guards
Data declarations
Select infix operators
Lazy evaluation

The biggest missing features are nested variables (meaning no lambda/let/where/case), type checking, and type classes.  Resulting programs leak memory, and self-compilation takes about 200 megabytes on my system (the Boehm garbage collector helps a lot, but only if the compiler optimizes tail recursion well).
To bootstrap, uncomment the first three lines (not counted in the score) and compile with GHC.  The compiler takes Haskell-subset code on stdin and produces C code on stdout.
It's long not because the language is complex, but because I'm lazy.  However, it's currently the shortest solution  Not anymore.  Guess I won't be bored this weekend.
-- import Prelude hiding (fmap, lookup, snd, zip);import Data.Char
-- import Data.List hiding (lookup, zip);data P a b = P a b;data B = B
-- add=(+);sub=(-);showInt=show;append[]ys=ys;append(x:xs)ys=x:append xs ys
data Program = Program [[Constructor]] [Function]
data Toplevel = TD [Constructor] | TE Equation | TO
data Constructor = Constructor String Int
data Function = Function String Int [Equation]
data Equation = Equation String [Pattern] (Maybe Expression) Expression
data Pattern = PVar String | PCon String [Pattern]
data Expression = Var String | Con String | Int String | Char String | String String | Ap Expression Expression
data Environment = Environment [P String Int] [P String VarInfo]
data VarInfo = VBox String | VArg Int | VItem VarInfo Int
main = interact (compile . parse)
constructorName (Constructor name _) = name
functionName (Function name _ _) = name
equationName (Equation name _ _ _) = name
sortToplevels [] = (P [] [])
sortToplevels (TD x : xs) = applyFst ((:) x) (sortToplevels xs)
sortToplevels (TE x : xs) = applySnd ((:) x) (sortToplevels xs)
sortToplevels (TO : xs)   = sortToplevels xs
pcons x xs = PCon "Cons" [x, xs];pnil = PCon "Nil" []
ebinary op a b = Ap (Ap (Var op) a) b;ebinaryE op a b = Ap (Ap op a) b
econs x xs = Ap (Ap (Con "Cons") x) xs
enil = Con "Nil"
listEq eq [] [] = True
listEq eq (x:xs) (y:ys) | eq x y = listEq eq xs ys
listEq _ _ _ = False
snd (P a b) = b
zip = zipWith P
lookup q (P k v : _)  | listEq (==) q k = Just v
lookup q (_     : xs)                   = lookup q xs
lookup q _                              = Nothing
compose2 f g x y = f (g x y)
applyFst f (P x y) = P (f x) y
applySnd f (P x y) = P x (f y)
fMaybe f Nothing  = Nothing
fMaybe f (Just x) = Just (f x)
cond f t False = f
cond f t True = t
condList f t [] = f
condList f t xs = t xs
countFrom n = n : countFrom (add n 1)
range l h | l > h = []
range l h         = l : range (add l 1) h
parse = makeProgram . sortToplevels . concatMap parse_p . ((:) prelude) . preprocess
parse_p (P lineno line) = maybe (parse_err lineno line) snd (parseLine line)
parse_err lineno line = error (concat ["Parse error on line ", showInt lineno, ": `", line, "`"])
preprocess = filter (not . isCommentOrEmpty . snd) . zip (countFrom 1) . map (dropWhile isBlank) . lines
isCommentOrEmpty = parserSucceeds (pro (ignore (pro (parseS "--") (parseS "import "))) parseEof)
liftA2 f a b = ap (fmap f a) b
parserSucceeds p s = maybe False (const True) (p s)
fmap f p = fMaybe (applySnd f) . p
pure x s = Just (P s x)
ap1 b (P s x) = maybe Nothing (ap2 x) (b s)
ap2 x (P s y) = Just (P s (x y))
empty = (const Nothing)
pro a b s = maybe (b s) Just (a s)
ap a b = maybe Nothing (ap1 b) . a
prc = liftA2 (:)
pra = liftA2 append
prl = liftA2 const
prr = liftA2 (const id)
many p = pro (some p) (pure [])
some p = prc p (many p)
optional p = pro (fmap Just p) (pure Nothing)
choice = foldr pro (const Nothing)
parseEof = parseEof_1
parseEof_1 [] = Just (P "" B)
parseEof_1 _  = Nothing
parsePred pred = parsePred_1 pred
parsePred_1 pred (x:xs) | pred x = Just (P xs x)
parsePred_1 _    _               = Nothing
manyParsePred = justFlipSplit
justFlipSplit pred xs = Just (P (dropWhile pred xs) (takeWhile pred xs))
someParsePred pred = prc (parsePred pred) (manyParsePred pred)
parseC = parsePred . (==)
parseS = foldr (prc . parseC) (pure [])
wrapC = wrapSpace . parseC
wrapS = wrapSpace . parseS
skipPred pred = prr (parsePred pred) (pure B)
manySkipPred pred = prr (manyParsePred pred) (pure B)
preSep p sep = many (prr sep p)
sepBy1 p sep = prc p (many (prr sep p))
sepByChar p c = pro (sepByChar1 p c) (pure [])
sepByChar1 p c = sepBy1 p (wrapSpace (parseC c))
wrapSpace p = prl (prr skipSpace p) skipSpace
ignore = fmap (const B)
isBlank c | c == ' ' || c == '\t' = True
isBlank _                         = False
isDigit1 c = c >= '1' && c <= '9'
parseBetween l r p = prl (prr (parseC l) (wrapSpace p)) (parseC r)
skipSpace = manySkipPred isBlank
chainl1 f sep p = fmap (foldl1 f) (sepBy1 p sep)
chainr1 f sep p = fmap (foldr1 f) (sepBy1 p sep)
chainl f z sep p = pro (fmap (foldl f z) (sepBy1 p sep)) (pure z)
chainr f z sep p = pro (fmap (foldr f z) (sepBy1 p sep)) (pure z)
parseNonassoc ops term = liftA2 (flip ($)) term (pro (liftA2 flip (choice ops) term) (pure id))
parseVar = prc (parsePred (orUnderscore isLower)) (many (parsePred (orUnderscore isAlphaNum)))
orUnderscore p c | p c || c == '_' = True
orUnderscore _ _ = False
parseCon = prc (parsePred isUpper) (many (parsePred (orUnderscore isAlphaNum)))
parseInt = pro (parseS "0") (prc (parsePred isDigit1) (many (parsePred isDigit)))
parseEscape q (c:x:xs) | c == '\\' = Just (P xs (c:x:[]))
parseEscape q [c]      | c == '\\' = Just (P [] [c])
parseEscape q (c:xs)   | c /= q    = Just (P xs [c])
parseEscape q _                    = Nothing
parseStringLiteral q = pra (parseS [q]) (pra (fmap concat (many (parseEscape q))) (parseS [q]))
parsePattern = chainr1 pcons (wrapC ':') (pro (liftA2 PCon parseCon (preSep parsePatternPrimary skipSpace)) parsePatternPrimary)
parsePatternPrimary = choice [fmap PVar parseVar, fmap (flip PCon []) parseCon, parseBetween '(' ')' parsePattern, parseBetween '[' ']' (fmap (foldr pcons pnil) (sepByChar parsePattern ','))]
relops f = relops_1 (ops_c f)
otherops f = f ":" (Con "Cons") : otherops_1 (ops_c f)
ops_c f x y = f x (Var y)
relops_1 f   = [f "<=" "_le", f "<" "_lt", f "==" "_eq", f ">=" "_ge", f ">" "_gt", f "/=" "_ne"]
otherops_1 f = [f "$" "_apply", f "||" "_or", f "&&" "_and", f "." "_compose"]
parseRelops = parseNonassoc (relops parseRelops_f)
parseRelops_f op func = prr (wrapS op) (pure (ebinaryE func))
parseExpression = chainr1 (ebinary "_apply") (wrapC '$') $ chainr1 (ebinary "_or") (wrapS "||") $ chainr1 (ebinary "_and") (wrapS "&&") $ parseRelops $ chainr1 econs (wrapC ':') $ chainr1 (ebinary "_compose") (wrapC '.') $ chainl1 Ap skipSpace $ choice [fmap Var parseVar, fmap Con parseCon, fmap Int parseInt, fmap Char (parseStringLiteral '\''), fmap String (parseStringLiteral '"'), parseBetween '(' ')' (pro parseSection parseExpression), parseBetween '[' ']' (chainr econs enil (wrapC ',') parseExpression)]
parseSection = choice (append (relops parseSection_f) (otherops parseSection_f))
parseSection_f op func = prr (wrapS op) (pure func)
parseEquation = ap (ap (ap (fmap Equation parseVar) (many (prr skipSpace parsePatternPrimary))) (optional (prr (wrapC '|') parseExpression))) (prr (wrapC '=') parseExpression)
skipType = ignore (sepBy1 (sepBy1 skipTypePrimary skipSpace) (wrapS "->"))
skipTypePrimary = choice [ignore parseVar, ignore parseCon, parseBetween '(' ')' skipType, parseBetween '[' ']' skipType]
parseDataDecl = prr (parseS "data") (prr skipSpace (prr parseCon (prr (preSep parseVar skipSpace) (prr (wrapC '=') (sepByChar1 (liftA2 Constructor parseCon (fmap length (preSep skipTypePrimary skipSpace))) '|')))))
skipTypeSignature = prr parseVar (prr (wrapS "::") skipType)
skipTypeAlias = prr (parseS "type") (prr skipSpace (prr parseCon (prr (preSep parseVar skipSpace) (prr (wrapC '=') skipType))))
parseToplevel = choice [fmap (const TO) (pro skipTypeSignature skipTypeAlias), fmap TD parseDataDecl, fmap TE parseEquation]
parseLine = prl (prl (sepByChar1 parseToplevel ';') skipSpace) parseEof
patternCount (Equation _ ps _ _) = length ps
makeProgram (P ds es) = Program ds (makeFunctions es)
makeFunctions = map makeFunctions_f . groupBy makeFunctions_g
makeFunctions_f []     = error "Internal error: No equations in binding group"
makeFunctions_f (x:xs) = cond (error (concat ["Equations for ", equationName x, " have different numbers of arguments"])) (Function (equationName x) (patternCount x) (x:xs)) (all (((==) (patternCount x)) . patternCount) xs)
makeFunctions_g (Equation name_a _ _ _) (Equation name_b _ _ _) = listEq (==) name_a name_b
lookupCon name (Environment c _) = lookup name c
lookupVar name (Environment _ v) = lookup name v
walkPatterns f = walkPatterns_items f VArg
walkPatterns_items f base = concat . zipWith (walkPatterns_f2 f) (map base (countFrom 0))
walkPatterns_f2 f v (PCon name ps) = append (f v (PCon name ps)) (walkPatterns_items f (VItem v) ps)
walkPatterns_f2 f v p              = f v p
compile (Program decls funcs) = concat [header, declareConstructors decls, declareFunctions funcs, boxConstructors decls, boxFunctions funcs, compileConstructors decls, compileFunctions (globalEnv decls funcs) funcs]
globalEnv decls funcs = Environment (append (globalEnv_constructorTags decls) (globalEnv_builtinConstructors)) (append (map (globalEnv_f . functionName) funcs) globalEnv_builtinFunctions)
globalEnv_f name = (P name (VBox name))
globalEnv_constructorTags = concatMap (flip zip (countFrom 0) . map constructorName)
globalEnv_builtinConstructors = [P "Nil" 0, P "Cons" 1, P "P" 0]
globalEnv_builtinFunctions = map globalEnv_f ["add", "sub", "_lt", "_le", "_eq", "_ge", "_gt", "_ne", "_and", "_or", "divMod", "negate", "not", "error"]
localEnv ps (Environment t v) = Environment t (append (walkPatterns localEnv_f ps) v)
localEnv_f v (PVar name) = [P name v]
localEnv_f _ (PCon _ _)  = []
declareFunctions_f [] = ""
declareFunctions_f xs = concat ["static Function ", intercalate ", " xs, ";\n"]
declareConstructors = declareFunctions_f . map ((append "f_") . constructorName) . concat
declareFunctions = declareFunctions_f . map ((append "f_") . functionName)
boxConstructors = concatMap boxConstructors_f . concat
boxConstructors_f (Constructor name n) = boxThing name n
boxFunctions = concatMap boxFunctions_f
boxFunctions_f (Function name n _) = boxThing name n
boxThing name n | n == 0 = concat ["static Box b_", name, " = {0, f_", name, ", NULL};\n"]
boxThing name n = concat ["static Partial p_", name, " = {", showInt n, ", 0, f_", name, "};\n", "static Box b_", name, " = {1, NULL, &p_", name, "};\n"]
compileConstructors = concatMap (concat . zipWith compileConstructors_f (countFrom 0))
compileConstructors_f tag (Constructor name n) = concat ["static void *f_", name, "(Box **args)\n", "{\n", allocate n, "\tv->tag = ", showInt tag, ";\n", concatMap initialize (range 0 (sub n 1)), "\treturn v;\n", "}\n"]
allocate n | n == 0 = "\tValue *v = malloc(sizeof(Value));\n\t(void) args;\n"
allocate n = concat ["\tValue *v = malloc(sizeof(Value) + ", showInt n, " * sizeof(Box*));\n"]
initialize i = concat ["\tv->items[", showInt i, "] = args[", showInt i, "];\n"]
compileFunctions env = concatMap (compileFunction env)
compileFunction env (Function name argc equations) =  concat ["static void *f_", name, "(Box **args)\n", "{\n", concatMap (compileEquation env) equations, "\tNO_MATCH(", name, ");\n", "}\n"]
compileEquation genv (Equation _ patterns guard expr) = compileEquation_a (localEnv patterns genv) patterns guard expr
compileEquation_a env patterns guard expr = compileEquation_b (concat ["\treturn ", compileExpressionStrict env expr, ";\n"]) (append (compilePatterns env patterns) (compileGuard env guard))
compileEquation_b returnExpr preds = condList returnExpr (compileEquation_f returnExpr) preds
compileEquation_f returnExpr xs = concat ["\tif (", intercalate " && " xs, ")\n\t", returnExpr]
compilePatterns env = walkPatterns (compilePatterns_f env)
compilePatterns_f _ _ (PVar name) = []
compilePatterns_f env v (PCon name ps) = compilePatterns_h v name (lookupCon name env)
compilePatterns_h v name (Just n) = [concat ["match(", compileVarInfo v, ",", showInt n, ")"]]
compilePatterns_h v name Nothing  = error (append "Not in scope: data constructor " name)
compileGuard env Nothing     = []
compileGuard env (Just expr) = [concat ["isTrue(", compileExpressionStrict env expr, ")"]]
compileExpressionStrict env (Var name) = concat ["force(", compileVar (lookupVar name env) name, ")"]
compileExpressionStrict _   (Con name) = concat ["force(&b_", name, ")"]
compileExpressionStrict _   (Int s)    = concat ["mkInt(", s, ")"]
compileExpressionStrict _   (Char s)   = concat ["mkInt(", s, ")"]
compileExpressionStrict _   (String s) = concat ["mkString(", s, ")"]
compileExpressionStrict env (Ap f x)   = concat ["apply(", compileExpressionStrict env f, ",", compileExpressionLazy env x, ")"]
compileExpressionLazy env (Var name) = compileVar (lookupVar name env) name
compileExpressionLazy _   (Con name) = concat ["&b_", name, ""]
compileExpressionLazy _   (Int s)    = concat ["box(mkInt(", s, "))"]
compileExpressionLazy _   (Char s)   = concat ["box(mkInt(", s, "))"]
compileExpressionLazy _   (String s) = concat ["box(mkString(", s, "))"]
compileExpressionLazy env (Ap f x)   = concat ["deferApply(", compileExpressionLazy env f, ",", compileExpressionLazy env x, ")"]
compileVar (Just v) _    = compileVarInfo v
compileVar Nothing  name = error (append "Not in scope: " name)
compileVarInfo (VBox name) = append "&b_" name
compileVarInfo (VArg n)    = concat ["args[", showInt n, "]"]
compileVarInfo (VItem v n) = concat ["item(", compileVarInfo v, ",", showInt n, ")"]
header="#include <assert.h>\n#include <stdarg.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\ntypedef struct Box Box;\ntypedef struct Value Value;\ntypedef struct Partial Partial;\ntypedef void *Function(Box**);\nstruct Box{int state;Function *func;void*vc;Box*fx[];};\nstruct Value{int tag;Box *items[];};\nstruct Partial{int remaining;int applied;Function *func;Box *args[];};\n#define copy(...)memdup(&(__VA_ARGS__), sizeof(__VA_ARGS__))\n#define countof(...)(sizeof(__VA_ARGS__) / sizeof(*(__VA_ARGS__)))\n#define match(box, expectedTag)(((Value*)force(box))->tag == (expectedTag))\n#define item(box, n)(((Value*)(box)->vc)->items[n])\n#define isTrue(value)(!!*(int*)(value))\n#define NO_MATCH(func)fatal(\"Non-exhaustive patterns in function \" #func)\nstatic void fatal(const char *str){fprintf(stderr,\"*** Exception: %s\\n\", str);exit(EXIT_FAILURE);}\nstatic void *memdup(void *ptr, size_t size){void*ret=malloc(size);memcpy(ret,ptr,size);return ret;}\nstatic void *force(Box *box){switch(box->state){\ncase 0:box->state=2;box->vc=box->func(box->vc);box->state=1;\ncase 1:return box->vc;\ndefault:fatal(\"infinite loop\");}}\nstatic void *apply(Partial*f,Box*x){Partial*f2=malloc(sizeof(Partial)+(f->applied+1)*sizeof(Box*));\nmemcpy(f2->args,f->args,f->applied*sizeof(Box*));f2->args[f->applied]=x;\nif(f->remaining>1){f2->remaining=f->remaining-1;f2->applied=f->applied+1;f2->func=f->func;return f2;\n}else return f->func(f2->args);}\nstatic void*deferApply_cb(Box**a){return apply(force(a[0]),a[1]);}\nstatic Box*deferApply(Box*f,Box*x){\nBox*ret=malloc(sizeof(Box)+2*sizeof(Box*));\nret->state=0;\nret->func=deferApply_cb;\nret->vc=ret->fx;\nret->fx[0]=f;\nret->fx[1]=x;\nreturn ret;}\n\nstatic Box*defer(Function*func,void*ctx){\nBox*ret=malloc(sizeof(Box));\nret->state=0;\nret->func=func;\nret->vc=ctx;\nreturn ret;}\n\nstatic Box *box(void *value)\n{\n\tBox *ret = malloc(sizeof(Box));\n\tret->state = 1;\n\tret->func = NULL;\n\tret->vc = value;\n\treturn ret;\n}\n\nstatic int *mkInt(int n)\n{\n\tint *ret = malloc(sizeof(*ret));\n\t*ret = n;\n\treturn ret;\n}\n\nstatic Function f_Nil, f_Cons, f_P;\nstatic Box b_Nil, b_Cons, b_P, b_main;\n\n#define FUNCTION(name, argc) \\\n\tstatic Function f_##name; \\\n\tstatic Partial p_##name = {argc, 0, f_##name}; \\\n\tstatic Box b_##name = {1, NULL, &p_##name}; \\\n\tstatic void *f_##name(Box **args)\n\n#define intop(name, expr) \\\n\tFUNCTION(name, 2) \\\n\t{ \\\n\t\tint a = *(int*)force(args[0]); \\\n\t\tint b = *(int*)force(args[1]); \\\n\t\treturn mkInt(expr); \\\n\t}\n\n#define intop1(name, expr) \\\n\tFUNCTION(name, 1) \\\n\t{ \\\n\t\tint a = *(int*)force(args[0]); \\\n\t\treturn mkInt(expr); \\\n\t}\n\nintop(add,  a + b)\nintop(sub,  a - b)\n\nintop(_lt,  a <  b)\nintop(_le,  a <= b)\nintop(_eq,  a == b)\nintop(_ge,  a >= b)\nintop(_gt,  a >  b)\nintop(_ne,  a != b)\nintop(_and, a && b)\nintop(_or,  a || b)\n\nintop1(negate, -a)\nintop1(not,    !a)\n\nFUNCTION(divMod, 2)\n{\n\tint n = *(int*)force(args[0]);\n\tint d = *(int*)force(args[1]);\n\tint div = n / d;\n\tint mod = n % d;\n\t\n\tif ((mod < 0 && d > 0) || (mod > 0 && d < 0)) {\n\t\tdiv--;\n\t\tmod += d;\n\t}\n\t\n\tBox *pair[2] = {box(mkInt(div)), box(mkInt(mod))};\n\treturn f_P(pair);\n}\n\nstatic void *mkString(const char *str)\n{\n\tif (*str != '\\0') {\n\t\tBox *cons[2] =\n\t\t\t{box(mkInt(*str)), defer((Function*) mkString, (void*)(str + 1))};\n\t\treturn f_Cons(cons);\n\t} else {\n\t\treturn force(&b_Nil);\n\t}\n}\n\nstatic void putStr(Value *v, FILE *f)\n{\n\tif (v->tag == 1) {\n\t\tint c = *(int*)force(v->items[0]);\n\t\tputc(c, f);\n\t\tputStr(force(v->items[1]), f);\n\t}\n}\n\nFUNCTION(error, 1)\n{\n\tfflush(stdout);\n\tfputs(\"*** Exception: \", stderr);\n\tputStr(force(args[0]), stderr);\n\tputc('\\n', stderr);\n\texit(EXIT_FAILURE);\n}\n\nstruct mkStringFromFile\n{\n\tFILE *f;\n\tconst char *name;\n};\n\nstatic void *mkStringFromFile(struct mkStringFromFile *ctx)\n{\n\tint c = fgetc(ctx->f);\n\t\n\tif (c == EOF) {\n\t\tif (ferror(ctx->f))\n\t\t\tperror(ctx->name);\n\t\treturn force(&b_Nil);\n\t}\n\t\n\tBox *cons[2] = {box(mkInt(c)), defer((Function*) mkStringFromFile, ctx)};\n\treturn f_Cons(cons);\n}\n\nint main(void)\n{\n\tstruct mkStringFromFile c_in = {stdin, \"<stdin>\"};\n\tBox *b_in = defer((Function*) mkStringFromFile, copy(c_in));\n\tputStr(apply(force(&b_main), b_in), stdout);\n\treturn 0;\n}\n"
prelude = P 0 "_apply f x=f x;_compose f g x=f(g x);data List a=Nil|Cons a(List a);data P a b=P a b;data B=B;data Maybe a=Nothing|Just a;data Bool=False|True;id x=x;const x _=x;flip f x y=f y x;foldl f z[]=z;foldl f z(x:xs)=foldl f(f z x)xs;foldl1 f(x:xs)=foldl f x xs;foldl1 _[]=error\"foldl1: empty list\";foldr f z[]=z;foldr f z(x:xs)=f x(foldr f z xs);foldr1 f[x]=x;foldr1 f(x:xs)=f x(foldr1 f xs);foldr1 _[]=error\"foldr1: empty list\";map f[]=[];map f(x:xs)=f x:map f xs;filter p[]=[];filter p(x:xs)|p x=x:filter p xs;filter p(x:xs)=filter p xs;zipWith f(x:xs)(y:ys)=f x y:zipWith f xs ys;zipWith f _ _=[];append[]ys=ys;append(x:xs)ys=x:append xs ys;concat=foldr append[];concatMap f=concat.map f;length[]=0;length(_:l)=add 1(length l);take n _|n<=0=[];take _[]=[];take n(x:xs)=x:take(sub n 1)xs;takeWhile p[]=[];takeWhile p(x:xs)|p x=x:takeWhile p xs;takeWhile _ _=[];dropWhile p[]=[];dropWhile p(x:xs)|p x=dropWhile p xs;dropWhile p xs=xs;span p[]=P[][];span p(x:xs)|p x=span_1 x(span p xs);span p xs=P[]xs;span_1 x(P ys zs)=P(x:ys)zs;break p=span(not.p);reverse=foldl(flip(:))[];groupBy _[]=[];groupBy eq(x:xs)=groupBy_1 x eq(span(eq x)xs);groupBy_1 x eq(P ys zs)=(x:ys):groupBy eq zs;maybe n f Nothing=n;maybe n f(Just x)=f x;all p=foldr(&&)True.map p;intersperse _[]=[];intersperse _[x]=[x];intersperse sep(x:xs)=x:sep:intersperse sep xs;intercalate xs xss=concat(intersperse xs xss);isDigit c=c>='0'&&c<='9';isAlphaNum c=c>='0'&&c<='9'||c>='A'&&c<='Z'||c>='a'&&c<='z';isUpper c=c>='A'&&c<='Z';isLower c=c>='a'&&c<='z';showInt n|n<0='-':showInt(negate n);showInt n|n==0=\"0\";showInt n|n>0=reverse(map(add 48)(showInt_1 n));showInt_1 n|n==0=[];showInt_1 n=showInt_2(divMod n 10);showInt_2(P div mod)=mod:showInt_1 div;lines []=[];lines s=lines_1(break((==)'\\n')s);lines_1(P l[])=[l];lines_1(P l(_:s))=l:lines s;interact=id"

Custom Language → C - (7979)
Since the question doesn't preclude creating my own language, I thought I'd give that a try.
The Environment
The language has access to two stacks, The Call Stack, and The Data Stack. The Call Stack is used for the jumping instructions { and }, while The Data Stack is used by most other instructions.  The Call Stack is opaque to applications.
The Data Stack can hold three different types of values: integer, text, and empty. Integers are of type intptr_t, while text is stored as C-style strings.
The ^ instruction has access to The Array. The Array is a constant array of length 17 of text items. You should probably see the source for the indexing scheme since it's a little wonky.
The Language
#   -   Begin number    - Marks the beginning of a number, for example: #42.
.   -   End number      - Marks the end of a number and pushes it to the data stack.
^   -   Translate       - Pops a number, and pushes the corresponding text from The Array.
<   -   Write           - Pops a value, and prints it to stdout.
>   -   Read            - Reads a character from stdin and pushes it as a number. If EOF,
                          exit.
{   -   Start Loop      - Pushes the current location in the program to the call stack.
}   -   End Loop        - Go to the position specified by the top of the call stack.
+   -   Add             - Pop two numbers from the data stack, add them, push the result.
-   -   Subtract        - Pop into A, pop into B, push B - A. Both B & A must be numbers.
!   -   Duplicate       - Pop from The Data Stack, push that value twice.
_   -   Discard         - Pop from The Data Stack.
=   -   Skip if Equal   - Pop two values, if they are equal skip the next instruction
                          and pop one item from the call stack.
?   -   Loop            - Pop one number, subtract one, if it's less than one, pop one
                          item from the call stack and skip the next instruction.
@   -   Array Separator - Marks the end of an array item.
$   -   Program End     - Marks the end of the program.

The Compiler
This is the compiler. It isn't golfed, and I expect it could be cut down considerably. It should be possible to use machine code directly and output a dos COM file, but I haven't gotten around to that yet. I know this looks like a C program, but the actual compiler implementation is down at the end.
Currently the compiler generates a lot of debugging information on stderr.
#include <string.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>
#include <stdbool.h>

const char* position;
const char* array[] = {"@"};

void die(const char* reason)
{
    fprintf(stderr, "%s\n", reason);
    exit(1);
}

//
// Stack Functions
//

#define T_EMPTY     (0)
#define T_NUMBER    (1)
#define T_TEXT      (2)

typedef struct {
    unsigned char type;
    union {
        const char* text;
        intptr_t number;
    };
} stack_entry;

#define STACK_MAX   (1024)
stack_entry stack[STACK_MAX];
size_t stack_position = 0;

stack_entry* _push()
{
    if (stack_position >= STACK_MAX) {
        die("out of stack space");
    }
    return &stack[stack_position++];
}

void push(stack_entry v)
{
    if (v.type == T_EMPTY) {
        fprintf(stderr, "\tpushed: None\n");
    } else if (v.type == T_TEXT) {
        fprintf(stderr, "\tpushed: %s\n", v.text);
    } else {
        fprintf(stderr, "\tpushed: %d\n", v.number);
    }
    stack_entry* entry = _push();
    *entry = v;
}

void push_empty()
{
    fprintf(stderr, "\tpushed: None\n");
    stack_entry* entry = _push();
    entry->type = T_EMPTY;
    entry->number = 0;
}

void push_number(intptr_t number)
{
    fprintf(stderr, "\tpushed: %d\n", number);
    stack_entry* entry = _push();
    entry->type = T_NUMBER;
    entry->number = number;
}

void push_text(const char* text)
{
    fprintf(stderr, "\tpushed: %s\n", text);
    stack_entry* entry = _push();
    entry->type = T_TEXT;
    entry->text = text;
}

// Polymorphic Push (for literals)
#define PUSH0()     do { fprintf(stderr, "literal:\n"); push_empty(); } while (0)
#define PUSH1(a)    do { fprintf(stderr, "literal:\n"); push_number(a); } while (0)

#define GET_MACRO(_0, _1, NAME, ...) NAME
#define PUSH(...) GET_MACRO(_0, ##__VA_ARGS__, PUSH1, PUSH0)(__VA_ARGS__)

stack_entry pop()
{
    if (stack_position <= 0) {
        fprintf(stderr, "\tpopped: None\n");
        return (stack_entry) {.type = T_EMPTY, .number = 0};
    }

    stack_entry v = stack[--stack_position];
    if (v.type == T_EMPTY) {
        fprintf(stderr, "\tpopped: None\n");
    } else if (v.type == T_TEXT) {
        fprintf(stderr, "\tpopped: %s\n", v.text);
    } else {
        fprintf(stderr, "\tpopped: %d\n", v.number);
    }
    return v;
}

stack_entry peek()
{
    if (stack_position <= 0) {
        return (stack_entry) {.type = T_EMPTY, .number = 0};
    }

    return stack[stack_position-1];
}

//
// Jump Functions
//

#define JUMP_MAX    (1024)
jmp_buf jump[JUMP_MAX];
size_t jump_position = 0;

#define start()                                     \
    do {                                            \
    if (jump_position >= JUMP_MAX) {                \
        die("out of jump space");                   \
    }                                               \
    fprintf(stderr, "start: %d\n", jump_position);  \
    setjmp(jump[jump_position++]);                  \
    } while (0)

void pop_jump() {
    if (jump_position <= 0) {
        die("empty jump stack");
    }
    jump_position -= 1;
}

#define end()                                       \
    do {                                            \
    if (jump_position <= 0) {                       \
        die("empty jump stack");                    \
    }                                               \
    fprintf(stderr, "end: %d\n", jump_position-1);  \
    longjmp(jump[jump_position-1],1);               \
    } while (0)

//
// Program functions
//

void translate()
{
    fprintf(stderr, "translate:\n");
    stack_entry entry = pop();
    if (entry.type == T_TEXT) {
        die("translating text");
    } else if (entry.type == T_EMPTY) {
        push_empty();
    } else {
        switch (entry.number) {
            case 0:
            case 1:
                push_text(array[entry.number]);
                break;
            case 64:
                push_text(array[2]);
                break;
            case 94:
                push_text(array[3]);
                break;
            case 45:
                push_text(array[4]);
                break;
            case 43:
                push_text(array[5]);
                break;
            case 62:
                push_text(array[6]);
                break;
            case 60:
                push_text(array[7]);
                break;
            case 33:
                push_text(array[8]);
                break;
            case 95:
                push_text(array[9]);
                break;
            case 61:
                push_text(array[10]);
                break;
            case 63:
                push_text(array[11]);
                break;
            case 123:
                push_text(array[12]);
                break;
            case 125:
                push_text(array[13]);
                break;
            case 35:
                push_text(array[14]);
                break;
            case 46:
                push_text(array[15]);
                break;
            case 36:
                push_text(array[16]);
                break;
            default:
                push_empty();
                break;
        }
    }
}

void subtract()
{
    fprintf(stderr, "subtract:\n");
    stack_entry v1 = pop();
    stack_entry v2 = pop();

    if (v1.type != T_NUMBER || v2.type != T_NUMBER) {
        die("not a number");
    }

    push_number(v2.number - v1.number);
}

void add()
{
    fprintf(stderr, "add:\n");
    stack_entry v1 = pop();
    stack_entry v2 = pop();

    if (v1.type != T_NUMBER || v2.type != T_NUMBER) {
        die("not a number");
    }

    push_number(v2.number + v1.number);
}

void read()
{
    fprintf(stderr, "read:\n");
    int in = getchar();

    if (in >= 0) {
        push_number(in);
    } else {
        die("end of input");
    }
}

void write()
{
    fprintf(stderr, "write:\n");
    stack_entry v = pop();

    if (v.type == T_NUMBER) {
        putchar(v.number);
    } else if (v.type == T_TEXT) {
        const char* x = v.text;
        char y;
        while (0 != (y=*(x++))) {
            y -= 128;
            putchar(y);
        }
    }
}

void duplicate()
{
    fprintf(stderr, "duplicate:\n");
    stack_entry v = pop();
    push(v);
    push(v);
}

void discard()
{
    fprintf(stderr, "discard:\n");
    pop();
}

bool equals()
{
    fprintf(stderr, "equals:\n");
    stack_entry x = pop();
    stack_entry y = pop();

    bool skip;

    if (x.type != y.type) {
        skip = false;
    } else if (x.type == T_EMPTY) {
        skip = true;
    } else if (x.type == T_NUMBER) {
        skip = x.number == y.number;
    } else {
        skip = strcmp(x.text, y.text) == 0;
    }

    if (skip) {
        pop_jump();
    }

    return !skip;
}

bool question()
{
    fprintf(stderr, "question:\n");
    stack_entry x = pop();

    intptr_t value;

    if (x.type == T_EMPTY) {
        value = 0;
    } else if (x.type == T_NUMBER) {
        value = x.number;
    } else {
        die("it is bad form to question text");
    }

    value -= 1;

    if (value < 1) {
        pop_jump();
        return false;
    } else {
        push_number(value);
        return true;
    }
}

int main()
{
@","@translate();@subtract();@add();@read();@write();@duplicate();@discard();@if(equals())@if(question())@start();@end();@PUSH(@);@return 0;}@

#0.^<                           Emit the preface

#17.{                           Loop for as many array slots exist
    #.{<>#128.+!#192.=}         Copy characters, adding 128 until reaching an at sign
    #128.-
    ^<                          Emit the code between array items
?}                              Return to start

#1.^<                           Emit the prologue

{{
>!^<                            Read character, translate it, and print it
!#35.=}                         Check if we have a literal
#.{<>!#46.=}^<                  If so, verbatim copy characters until a period
}                               Continue executing
$

To compile the generated C code:
gcc -finput-charset=CP437 -fexec-charset=CP437 -std=gnu11

The charset is required because the compiler escapes special characters by adding 128.
The Bootstrap
To compile the first compiler, I wrote a python interpreter for the language.
import sys
from collections import defaultdict
KEYS = [0,1] + map(ord, ['@','^','-','+','>','<','!','_','=','?','{','}','#','.','$'])

# Read the source file
with file(sys.argv[1]) as f:
    data = f.read()
pos = 0

# Initialize the environment
array = defaultdict(str)
jmp = []
stk = []

def log(x):
    sys.stderr.write(x + '\n')

def read():
    global pos,data
    pos += 1
    return data[pos-1]

def pop():
    global stk
    try:
        x = stk.pop()
    except IndexError:
        x = None
    log('\tpopped ' + repr(x))
    return x

def push(value):
    global stk
    log('\tpushing ' + repr(value))
    stk.append(value)

# Read the array initialization section
for key in KEYS:
    while True:
        c = read()
        if c == '@':
            break
        array[key] += c

# Execute the program
while pos < len(data):
    c = read()
    if c == '^':
        log('translate:')
        push(array.get(pop(), None))
    elif c == '-':
        log('subtract:')
        x = pop()
        y = pop()
        push(y - x)
    elif c == '+':
        log('add:')
        x = pop()
        y = pop()
        push(y + x)
    elif c == '>':
        log('read:')
        push(ord(sys.stdin.read(1)))
    elif c == '<':
        log('write:')
        v = pop()
        if isinstance(v, int):
            sys.stdout.write(chr(v))
        elif v is not None:
            sys.stdout.write(v)
    elif c == '!':
        log('duplicate:')
        x = pop()
        push(x)
        push(x)
    elif c == '_':
        log('discard:')
        pop()
    elif c == '=':
        log('skip if equal:')
        x,y = pop(),pop()
        if x == y:
            pos += 1
            jmp.pop()
    elif c == '?':
        log('loop:')
        x = pop()
        x -= 1
        if x < 1:
            pos += 1
            jmp.pop()
        else:
            push(x)
    elif c == '{':
        log('start: ' + repr(pos))
        jmp.append(pos)
    elif c == '}':
        log('end:')
        pos = jmp[-1]
    elif c == '#':
        literal = ''
        while True:
            c = read()
            if c == '.':
                log('literal: ' + repr(literal))
                if literal == '':
                    push(None)
                else:
                    push(int(literal))
                break
            else:
                literal += c

Putting It All Together
Assuming you've saved the compiler as compiler.cmp and the bootstrap as bootstrap.py, here's how to build the compiler, and then use it to compile itself:
$ cat compiler.cmp |
  python bootstrap.py compiler.cmp 2> trace-bootstrap |
  gcc -finput-charset=CP437 -fexec-charset=CP437 -std=gnu11 -o result -xc -
$ cat compiler.cmp | ./result 2> trace-final

So I'm not much of a C programmer, nor am I much of a language designer, so any suggestions on improving this are quite welcome!
Example Programs
Hello, World!
Hello, World!@@@@@@@@@@@@@@@@@#0.^<$

While impressive, this violates the [tag:code-golf] rules as defined in the Help Center.

Correction, the rule is found in the [tag:code-golf] tag wiki here as well as in Meta.

@Iszi I hadn't come across that page before, and you are totally correct... However, I'd like to provide some mitigating facts before you consider sentencing: This language is general purpose, and does not provide a "one character solution", and secondly, if you include the language implementation in the solution, my score doesn't change, since it implements itself (granted, I couldn't claim that my solution compiles C, so it wouldn't solve the original problem.)

What's your language called?

You should add your language to esolangs.org

Extended Brainfuck v0.9: 618 bytes (not counting the uneccesary linefeeds)
:c:n:z:g:i:t:w:a:p++++++++[->++++++++<]>[->>>>>>>[>>>>>>>>]+[<<<<<<<<]>]>>>>>>>[->>>>>>>>]@i
$i,[[-$t+$w+$i]$t[-$i+$t]+$a+++[-$w-----------$a]$w---[$a++[-$w-----------$a]$w[--[--[--[$i.
$t+++++++[-$w++++++++$t]$w[-]]$t[-$p[-]$i.$n,.[-<[<<]+[>>]<]@n$c[<<]>[-<<<+>>>>[>>]@z$p+$c[<
<]>]<<<[->>>+<<<]>>>>[->>]@z$t]$w]$t[-$i.$p+$t]$w]$t[-$i.$p-$t]$w]$t[$i.$n,.[-<[<<]+[>>]<]@n
$g[-$t+$c[<<]>+>[>>]@z>]$c[<<]>>[->>]@z$t[-$g+$t]$t]$w]$t[-$i.[-]$n,.[-<[<<]+[>>]<]@n$c[<<]>
[-<<<+>>>>[>>]@z$i+$a+$c[<<]>]<<<[->>>+<<<]>>>>[->>]@z<++++++[->++++++++++<]$w+$p[$a[-$w-]<[
@w-$p[-$z.$p]+$t]$w+$p-]$z++$w-$a[-$z.$a]$z[-]$i[-$p+$i]$t]$w$i,]

This is a golfed version of my very first version of EBF with removed support for comments and dead code to support removing of variables.
So basically it's BrainFuck with variables. :x creates variables x. The compiler knows where you are so $y will produce <'s and >'s to get to that position. Sometimes you need asymmetric loops and then you need to tell the compiler where you are with @x. As current EBF it compiles to Brainfuck.
This first version had only one char variable names, but I have used this version to compile the next version and so on until the current version that has an impressive feature set. When compiling from github source it actually downloads the handcompiled binary to bootstrap 6 intermediate ebf versions in order to create the current version.
To bootstrap it you may use this first and only binary in the EBF git repository which was compiled by hand successfully after a couple of tries.
wget -nv https://raw.githubusercontent.com/westerp/ebf-compiler/34c378c8347aafa5dbf37f4973461d42c8120ea4/ebf-handcompiled.bf
beef ebf-handcompiled.bf < ebf09.ebf > ebf09a.bf
beef ebf09a.bf < ebf09.ebf > ebf09b.bf
diff -s ebf09a.bf ebf09b.bf # Files ebf09a.bf and ebf09b.bf are identical

Brainfuck has a few hardware implementations, eg. this, this and this to mention a few. But mostly it's so easy to implement you can practically implement an interpreter on any system at all. I use to joke that Zozotez LISP, which is written in EBF, probably is the most portable LISP ever.

Hex, 550 bytes
This specifically targets x86_64 systems running Linux.
7f454c4602010100000000000000000002003e0001000000780040000000000040000000000000000000000000000000000000004000380001004000000000000100000005000000000000000000000000004000000000000000400000000000130100000000000013010000000000000000200000000000e81700000085c07c0b31ff01c7e879000000ebec31c089c7b03c0f05e84c0000004885c07c203c2178f2741b89c7e825000000c0e00450e83100000089c7e8150000005900c8c3e8210000003c0d7ff774ca3c0a75f1ebc489f831c93c400f9cc148ffc980e12780c13028c8c36a004889e631c089c2fec289c70f0531c985c0580f95c148ffc94809c8c3574889e631c0fec089c289c70f0558c3

In this language, source code consists of bytes represented as two lowercase hexadecimal digits, [0-9a-f][0-9a-f]. These bytes may have any amount of surrounding whitespace, but nothing may occur between the digits that form a single byte. Further, '!' is a line-comment character: it is ignored, as well as everything between it and the next '\n' character.
If you understand x86 assembly, here's a much more readable version of the source code:
! ELF Header !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
7f 45 4c 46                !e_ident[EI_MAG0] (0x7F "ELF")
02                         !e_ident[EI_CLASS] (64-bit)
01                         !e_ident[EI_DATA] (little-endian)
01                         !e_ident[EI_VERSION] (ELF v1)
00                         !e_ident[EI_OSABI] (System V ABI)
00                         !e_ident[EI_ABIVERSION] (version 0)
00 00 00 00 00 00 00       !e_ident [EI_PAD]
02 00                      !e_type (executable)
3e 00                      !e_machine (x86_64)
01 00 00 00                !e_version (ELF v1)
78 00 40 00 00 00 00 00    !e_entry (0x40078)
40 00 00 00 00 00 00 00    !e_phoff (0x   40)
00 00 00 00 00 00 00 00    !e_shoff (0x    0)
00 00 00 00                !e_flags
40 00                      !e_ehsize (ELF header size = 64 bytes)
38 00                      !e_phentsize (Program headers = 56 bytes)
01 00                      !e_phnum (1 program header)
40 00                      !e_shentsize (Section headers = 64 bytes)
00 00                      !e_shnum (no section headers)
00 00                      !e_shstrndx (section names, not useful here)

! Program Headers !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
01 00 00 00                !p_type (LOAD)
05 00 00 00                !p_flags (R+E)
00 00 00 00 00 00 00 00    !p_offset (file-loc 0)
00 00 40 00 00 00 00 00    !p_vaddr (vmem-loc 0x40000)
00 00 40 00 00 00 00 00    !p_paddr (pmem-loc 0x40000)
13 01 00 00 00 00 00 00    !p_filesz (length 0x113 bytes)
13 01 00 00 00 00 00 00    !p_memsz (allocate 0x113 bytes)
00 00 20 00 00 00 00 00    !p_align (align pages in 0x20000 increments)

! Program Code !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!! _start: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      e8 17 00 00 00 ! callq _gethx
               85 c0 ! test %eax,%eax
               7c 0b ! jl .+11
               31 ff ! xor %edi,%edi
               01 c7 ! add %eax,%eax
      e8 79 00 00 00 ! callq _putch
               eb ec ! jmp .-20
               31 c0 ! xor %eax,%eax
               89 c7 ! mov %eax,%edi
               b0 3c ! mov $0x3c,%al
               0f 05 ! syscall

!! _gethx: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      e8 4c 00 00 00 ! callq _getch
            48 85 c0 ! test %rax,%rax
               7c 20 ! jl _gethx+42
               3c 21 ! cmp $0x21,al
               78 f2 ! js _gethx
               74 1b ! je _gethx+43
               89 c7 ! mov %eax,%edi
      e8 25 00 00 00 ! callq _h2d
            c0 e0 04 ! sal $4,%al
                  50 ! push %rax
      e8 31 00 00 00 ! callq _getch
               89 c7 ! mov %eax,%edi
      e8 15 00 00 00 ! callq _h2d
                  59 ! pop %rcx
               00 c8 ! add %cl,%al
                  c3 ! retq
      e8 21 00 00 00 ! callq _getch
               3c 0d ! cmp $0xd,%al
               7f f7 ! jg _gethx+43
               74 ca ! je _gethx
               3c 0a ! cmp $0xa,%al
               75 f1 ! jne _gethx+43
               eb c4 ! jmp _gethx

!! _h2d: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
               89 f8 ! mov %edi,%eax
               31 c9 ! xor %ecx,%ecx
               3c 40 ! cmp $0x40,%al
            0f 9c c1 ! setl %cl
            48 ff c9 ! dec %rcx
            80 e1 27 ! and $0x27,%cl
            80 c1 30 ! add $0x30,%cl
               28 c8 ! sub %cl,%al
                  c3 ! retq

!! _getch: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
               6a 00 ! push $0
            48 89 e6 ! mov %rsp,%rsi
               31 c0 ! xor %eax,%eax
               89 c2 ! mov %eax,%edx
               fe c2 ! inc %dl
               89 c7 ! mov %eax,%edi
               0f 05 ! syscall
               31 c9 ! xor %ecx,%ecx
               85 c0 ! test %eax,%eax
                  58 ! pop %rax
            0f 95 c1 ! setne %cl
            48 ff c9 ! dec %rcx
            48 09 c8 ! or %rcx,%rax
                  c3 ! retq

!! _putch: !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                  57 ! push %rdi
            48 89 e6 ! mov %rsp,%rsi
               31 c0 ! xor %eax,%eax
               fe c0 ! inc %al
               89 c2 ! mov %eax,%edx
               89 c7 ! mov %eax,%edi
               0f 05 ! syscall
                  58 ! pop %rax
                  c3 ! retq

If you extract the assembly language from the comments below ! Program Code, you can assemble and run the Hex compiler. Input and output use stdin and stdout.

Hex is not a language.

@TùxCräftîñg That's not exactly true.  It doesn't have a Wikipedia page, but it did exist in this form, with this implementation, before I knew of this question (unnamed at the time).  From my svn: http://lutras-hacking.ddns.net/websvn/listing.php?repname=sasm  The idea was to build an assembler from nothing, but I never got that far.

Oh, sorry >_> ...

Since it's not a very known esolang, you can put a link to the repo in the post

@TuxCopter I suppose, that "x86 linux assembly" is name of language

05AB1E, 2 bytes (possibly non-competing)
.V

Try it online!
Code on the first line of input, inputs on subsequent lines.

Nil, 0 bytes

Incredibly, despite not being Turing-complete, the Nil language is expressive enough to implement an interpreter for itself, much more concisely than many 'proper' languages can. The example presented here is a simple implementation, but using advanced compression techniques Nil developers have been able to produce working interpreters in as little as 0 lines of code.

@ØrjanJohansen https://codegolf.meta.stackexchange.com/a/10426/aa

Gah! remembering what on meta is currently relevant is too hard.

Lumber, 0 bytes
Lumber is a complete esoteric programming language invented by Unrelated String written in just 10 lines of Prolog code.
Can't believe it? These programs had comments removed and makes the interpreter source more concise.
lumber_corefuncs.pl:
:- use_module(lumber_types).

lumber_types.pl
:- module(lumber_types,
          []).

lumber_corefuncs.pl takes in the library lumber_types; and in turn, this library defines a module with nothing in it. Therefore, Lumber does nothing on arbitary inputs, which is in turn a self-compiler.

https://codegolf.meta.stackexchange.com/questions/10421/do-submissions-have-to-be-answered-with-a-programming-language/10426#10426

@A__ Just because it's a technically valid answer, doesn't mean it's a good one, especially if it is lazy or rather nonsensical (especially when there's already an existing answer using the same excuse with 3 downvotes)

Also, it's not Perl, it's Prolog. (Also also I'll probably have a legitimate answer for this in Lumber some time this decade)

authors: Евгений Новиков


text:
Write a JSON validator
Write a program that determines whether its input is valid JSON.

Input: ASCII text: [\x00-\x7F]*
Note: if ASCII is problematic, feel free to use another encoding, but indicate it in your post.

Output: Valid or Invalid.  Trailing newline may be omitted.

Example:
 $ echo '{"key": "value"}' | ./json-validate
 Valid
 $ echo '{key: "value"}' | ./json-validate
 Invalid

Rules:

Do not use a JSON parsing library.
Partially-correct solutions are allowed, but frowned upon.
Post your test suite score (see below).

The shortest correct solution wins.
Please run json-validate-test-suite.sh on your program, and post your score.  Example:
$ ./json-validate-test-suite.sh ./buggy-prog
fail: should be invalid:  [ 0.1e ]
fail: should be invalid:  [ 0.1e+-1 ]
fail: should be invalid:  [ 0.1e-+1 ]
score: 297/300

Resources:

json.org - Concise definition of the JSON grammar with easy-to-follow pictures.
RFC 4627 - JSON specification
json-validate.c - A 200-line implementation that passes the testsuite.

The JSON grammar is as follows:
json: object | array

object: '{' members? '}'
    members: pair (',' pair)*
    pair:    string ':' value

array: '[' elements? ']'
    elements: value (',' value)*

value: string
     | number
     | object
     | array
     | 'true'
     | 'false'
     | 'null'

string: '"' char* '"'
    char: [^"\\\x00-\x1F]
        | '\' escape
    escape: ["\\/bfnrt]
          | u [0-9A-Fa-f]{4}

number: '-'? (0 | [1-9][0-9]*) ('.' [0-9]+)? ([Ee] [+-]? [0-9]+)?

Also, whitespace can appear before or after any of the six structural characters {}[]:,
ws = [\t\n\r ]*

Bear in mind the following:

Be careful with functions like isspace().  Whitespace in JSON is [\t\n\r ], but isspace() also treats \v (vertical tab) and \f (form feed) as space.  Although word has it that isdigit() can accept more than just [0-9], should be okay to use here, as we assume input is in ASCII.
\x7F is technically a control character, but the JSON RFC doesn't mention it (it only mentions [\x00-\x1F]), and most JSON parsers tend to accept \x7F characters in strings.  Because of this ambiguity, solutions may choose to either accept them or not.

Your "partially-correct solutions allowed" note is making me dream of extracting a regex from a genetic algorithm.  I must be insane.

@J B: That would be awesome.

Just curious, why is {key: "value"} consider invalid JSON ? It is valid javascript.

@HoLyVieR: I imagine it's so JSON will be easier to parse and less ambiguous to implementors.  I'm not sure I like this restriction either.

Anyone got a copy of the validator script?

@Alison: I fixed the links.  Sorry about that.

I'm going to close this question as unclear.  Back in the day we had a lot looser rules on clarity, but things have changed.  A more modern question would have to include an actual spec and couldn't have such as "partially-correct solutions allowed".

PHP : 297 285 264 253 characters
<?=preg_match(<<<'R'
~([\h
]*)({(?1)((("([^"\\\0- ]| |\\(["\\/bfnrt]|u[\dA-Fa-f]{4}))*")(?1):(?1)((?5)|-?(0|[1-9]\d*)(\.\d+)?([Ee][+-]?\d+)?|(?2)|true|false|null))(((?1),(?1))(?4))*)?}|\[(?1)((?8)((?13)(?8))*)?(?1)])(?1)\z~A
R
,`cat`)?'Valid':'Invalid';

score: 300/300
This is a full, recursive implementation of the JSON grammar.
It works only on PHP ≥ 5.3 due to nowdoc syntax (heredoc would have required to double all \).
Readable version:
(this is the same regex, with named capture groups and extended syntax):
#!/usr/bin/env php
<?php

$re = <<< 'RE'
~\A (?P<ws>[\t\n\r ])* (
    (?P<object>\{ (?P>ws)*
        (?P<members>
            (?P<pair>
                (?P<string>
                    "(?P<char>
                        [^"\\\x00-\x1F]
                        |\\(?P<escape>
                            ["\\/bfnrt]
                            |u [0-9A-Fa-f]{4}
                        )
                    )*"
                ) (?P>ws)* : (?P>ws)* (?P<value>
                    (?P>string)
                    | (?P<number>-? (0 | [1-9][0-9]*) (\. [0-9]+)? ([Ee] [+-]? [0-9]+)? )
                    | (?P>object)
                    | (?P>array)
                    | true
                    | false
                    | null
                )
            ) ( (?P>ws)* , (?P>ws)* (?P>pair) )*
        )?
    \})
    |(?P<array>\[ (?P>ws)*
        (?P<elements>
            (?P>value) ( (?P>ws)* , (?P>ws)* (?P>value) )*
        )?
    (?P>ws)* \])
) (?P>ws)* \z~x
RE;

if (preg_match($re, stream_get_contents(STDIN))) {
    echo 'Valid';
} else {
    echo 'Invalid';
}

Wow.

You need to include the <?php IMO.

Added. 264 chars now :-)

Python - 340 314 299 292 chars
import re,os
r=x=re.sub
z=r('0\.0+','0',r('e[+-]?0+|[\t\n\r]',' ',r(r'"(\\["nrtb\\/]|[^\\"\0-\37])*"','1',r(r'true|false|null|\\u\w{4}|[1-9]\d*','0',os.read(0,99)))))
while z!=x:z,x=r('\{(1:\d)?(,\\1)*\}|\[(-?\d(,-?\d)*)?\]','0',r(' *([][{}:,]) *','\\1',z)),z
print['Inv','V'][z=='0']+'alid'

score
$ ./json-validate-test-suite.sh ./codegolf-474.py
score: 300/300

Scala - 390 chars
import scala.util.parsing.combinator.JavaTokenParsers
object J extends JavaTokenParsers{def j=o|a
def o:Parser[Any]="{"~repsep(p,",")~"}"
def p=s~":"~v
def a:Parser[Any]="["~repsep(v,",")~"]"
def v=s|o|a|"true"|"false"|"null"
def s=stringLiteral
def n=floatingPointNumber}
object Main{def main(a:Array[String]){print(if(J.parseAll(J.j,readLine()).successful)"Valid"else"Invalid")}}

This is no-brainer soluton, using parser combinators. Written in 1 or 2 minutes, literally. Cannot get validator script, browser said that server not found.

looks like an interesting solution; validator link has been fixed.

Is there a simple way to do it on Windows? (without cygwin or similar heresy)

Bash + jq, 29 bytes
jq -r '"Valid"'||echo Invalid

Try it online!
TIO's bash instance conveniently has jq installed for us so try it online at your leisure!

This is not a valid answer because the program is expected to print Valid or Invalid, and any other output format is not allowed (i.e. jq alone can't solve this challenge). Always watch out for I/O formats when trying very old challenges.

Uh oh, thanks @Bubbler. I totally missed that! I'm surprised though that our current I/O standards don't apply. Do those only apply when I/O isn't already strictly defined?

Yes, I/O defaults only apply when the challenge doesn't specify the I/O. (Also, changing I/O rules for an existing challenge is fundamentally a breaking change, so we don't do that.)

Thanks bunches @Bubbler, I'll fix this right away!

(The only way to fix this answer is to delete it, since if you use something like Bash + jq, then jq surely counts as a "JSON parsing library" which is banned.)

@Bubbler Oh no, I've just done that! I don't think it's fair to consider jq a JSON parsing library, though. That's like calling a calculator a number parser. It turns out to be a convenient side effect of a simple calculator that it won't have any idea how to handle 'a1b2c3'. Instead it'll error, but that's more of a bug than a feature :p A concrete example: echo 1|bc  runs successfully, whereas echo 1a|bc errors. But I wouldn't call using bc a 'number-parsing library'.

Of course jq can do much more than that, but the first thing it does is to parse JSON for you (and error if the input is not a valid JSON). And I'd interpret "JSON parsing library" as "anything that can parse JSON for you without effort", since "following the spirit of the challenge" was important in the old days.

@Bubbler But the rules say that "partially correct solutions are allowed but frowned upon". Doesn't that override the typical invalidity policy and make this answer not need to be deleted?

@TheFifthMarshal I believe the specific line is talking about not passing 100% of the test cases provided (which is a dead link now, btw). I'd say this is not a partially correct solution but a rule-breaking solution.

@Bubbler Oh, I missed that there was a test suite. I would say that the rule allowing partially correct solutions makes the challenge unclear, though, as there's no threshold for determining when an answer is correct enough to be valid, and it's not a [tag:test-battery].

source: Stack Exchange

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

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

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

sort: votes


text:
Chris Pine's "Deaf Grandma"
I'm a mentor at RubyLearning and one of the exercises we give to our students is the "Deaf Grandma" exercise from Chris Pine's book "Learn to Program". Here's the description:

Write a Deaf Grandma program. Whatever you say to grandma (whatever
  you type in), she should respond with:
  "Huh?! Speak up, sonny!", unless you
  shout it (type in all capitals). If
  you shout, she can hear you (or at
  least she thinks so) and yells back:
  "No, not since 1938!"
To make your program really believable, have grandma shout a
  different year each time; maybe any
  year at random between 1930 and 1950.
  (This part is optional, and would be
  much easier if you read the section on
  Ruby's random number generator at the
  end of the methods chapter.) You can't
  stop talking to grandma until you
  shout "BYE".

After several course iterations I tried to see how small I can get this and now have it down to 112 characters:
puts (s||='').upcase==s ? "NO, NOT SINCE #{1930+rand(21)}!":"HUH?! SPEAK UP, SONNY!" until(s=gets.chomp)=="BYE"

I'm curious to see in how few characters this can be achieved in the language of your choice, because I think Ruby is already doing really well here.
Edit: The Perl solution posted below led to
ruby -nle 'puts($_=="BYE"?exit: $_.upcase!? "HUH?! SEPAK UP, SONNY!":"NO, NOT SINCE #{1930+rand(21)}!")'

which is 92 characters for the expression + 2 more for the n and l options.

In a golfing context, this needs additional specification.  What should happen if there's any extra output past BYE?

Only "BYE" exactly terminates the program.

Perl, 85 91
Run with perl -nE '<code goes there>' (n counted in program size):
$==1930+rand 21;say/^BYE$/?last:uc eq$_?"
NO, NOT SINCE $=!":"HUH?! SPEAK UP, SONNY!"

That trailing exclamation mark is very expensive...
Edits suggested by IK:

Using a regexp instead of a string match spares the -l global option as well as two program characters: -3.
Using an actual variable to save a value and use it later for interpolation (Genius! Who'd have thought of using a variable for that?): 0.
Making that variable $=, constrained to be an integer: -4.

(and it still doesn't add up and I'm too sleepy to find out why.  Oh well, the final count is right at least)

Abusing $= and using a regexp for "BYE" gets this down to 84+1: perl -nE '$==1930+rand 21;say/^BYE$/?last:uc eq$_?"NO, NOT SINCE $=!":"HUH?! SPEAK UP, SONNY!"'

@IlmariKaronen Integrated, thanks!

Python 120 Characters
r=raw_input
s=r()
while'BYE'!=s:
 print["HUH?! SPEAK UP, SONNY!","NO, NOT SINCE %d!"%(1930+id(s)%21)][s.isupper()];s=r()

Any hints to improve?

You don't need the brackets around that if statement, also I'm pretty sure python has a recursion ceiling - but that could just simulate your grandma falling asleep.

Oh! I forgot to remove the brackets. Thanks :)

You can save some characters if you remove the first line, replace the second with s='', reorder your statements in your while loop, and put the whole while loop on one line: https://gist.github.com/3787809 If you were really determined, you could save 2 characters by using python 3 (raw_input() -> input(), but print -> print())

131 characters in PowerShell:
for(){$j=read-host;if($j-ceq"BYE"){break}if($j-ceq$j.ToUpper()){"No, not since 19$(10..90|random)!"}else{"Huh?! Speak up, sonny!"}}

W/ whitespace:
for(){
  $j = read-host;
  if ( $j -ceq "BYE" ) { break }
  if ( $j -ceq $j.ToUpper() ) { "No, not since 19$(10..90|random)!" }
  else { "Huh?! Speak up, sonny!" }
}

Squeezed 18 characters from Joey's suggestion.
BTW, 'Learn to Program' was the first programming book I ever read cover to cover.

You might want to take a look here: http://codegolf.stackexchange.com/questions/191/tips-for-golfing-in-windows-powershell

You can get this down to 120 by squishing the first if... into the conditional check of the for() like so: for(;($j=read-host)-cne"BYE"){if($j-ceq$j.ToUpper()){...
Also, the spec says 1930-1950.

C# - 234 Chars
using System;class P{static void Main(){for(;;){var s=Console.ReadLine();if(s!=s.ToUpper()){Console.WriteLine("Huh?! Speak up, sonny!");continue;}if(s=="BYE")break;Console.WriteLine("No, not since 19{0}!",new Random().Next(30,51));}}}

More readable:
using System;
class P
{
    static void Main()
    {
        for(;;)
        {
            var s=Console.ReadLine();
            if(s!=s.ToUpper())
            {
                Console.WriteLine("Huh?! Speak up, sonny!");
                continue;
            }
            if(s=="BYE")
                break;
            Console.WriteLine("No, not since 19{0}!",new Random().Next(30,51));
        }
    }
}

Ah missed a few simple ones in mine, and made some silly mistakes. Nice +1

Befunge - 27x6 = 162 characters
> ~:0`  #v _            vv<
         >:"a"`!#v  _:"z"`|
^                <       <
v"Huh?! Speak up, sonny!"0<
v"No, not since 1938!"0 <
>:# #, _@

EDIT: Completely missed the "BYE" part.  New version coming soon.
EDIT 2: Actually, that makes it a bit too complex for my meager Befunge skills.  I might try again later, but I can't think of any simple way to implement it at the moment.

C# - 194 CHARS
using System;class P{static void Main(){var s=Console.ReadLine();if(s!="BYE"){Console.Write((s==s.ToUpper()?"No, not since 19"+new Random().Next(30, 51):"Huh?! Speak up, sonny")+"!");Main();}}}

With whitespaces:
using System;
class P
{
    static void Main()
    {
        var s = Console.ReadLine();
        if (s != "BYE")
        {
            Console.Write((s == s.ToUpper() ? "No, not since 19" + new Random().Next(30, 51) : "Huh?! Speak up, sonny") + "!");
            Main();
        }
    }
}

With some inspiration from Nellius and fR0DDY.
Please let me know if it can be improved.

Short, but FWIW, i think this leaks (recursively calling Main()). Also, i think you want parens in the ?: expression to get the ! in both. I added an answer with this and EOL (but still leaks).

i see you added the parens and removed your comment. Good job. Now my edit to add screenshots to my answer of with and without the parens is moot. (But, still leaky) :-)

@bill Yes, I messed my testing initially. The non leaky version would be 199 chars, waaay too long :)

ha. I like the Main(); solution... no sane person would use this program long enough for it to be a problem.

As Phoshi said in the comment to fR0DDY. The program crashes when grandma falls asleep.

D: 246 Characters
import std.random,std.stdio,std.string;void main(){auto r=rndGen();for(;;){auto t=strip(readln());if(t=="BYE")break;if(t.toupper()==t)writefln("No, not since %s!",{r.popFront();return r.front%20+1930;}());else writeln("Huh?! Speak up, sonny!");}}

More Legibly:
import std.random, std.stdio, std.string;

void main()
{
    auto r = rndGen();

    for(;;)
    {
        auto t = strip(readln());

        if(t == "BYE")
            break;

        if(t.toupper() == t)
            writefln("No, not since %s!", {r.popFront(); return r.front % 20 + 1930;}());
        else
            writeln("Huh?! Speak up, sonny!");
    }
}

javascript, 142 characters, 29 of them perform random year
n='a'; while((/[a-z]/.test(n)?r="HUH?! SPEAK UP, SONNY!":n=="BYE"?r='':r="NO, NOT SINCE "+Math.floor(Math.random()*21+1930))!=''){n=prompt(r)}

Windows PowerShell, 121 117
Due to the nature of the task this looks pretty much identical to Ty Auvil's solution, although it was written independently:
for(;($j=read-host)-cne'BYE'){if($j-cmatch'[a-z]'){'Huh?! Speak up, sonny!'}else{"No, not since 19$(30..50|random)"}}

Thanks to SpellingD for the suggestion,

I like your regex matching, but the switch statement is way bulky. Along with the suggestion I gave Ty, you could reduce your character count to 117 by using regex with an if instead like this: for(;($j=read-host)-cne'BYE'){if($j-cmatch'[a-z]'){'Huh?! Speak up, sonny!'}else{"No, not since 19$(30..50|random)"}}

Awk: 97 95 characters
Thanks to

tail spark rabbit ear for replacing string equality testing with regex matching (-2 characters)

/^BYE$/{exit}$0=toupper($0)==$0?"NO, NOT SINCE "int(rand()*21+1930)"!":"HUH?! SPEAK UP, SONNY!"

Try it online!

95 hytes

Doh! How I didn't thought to? Thank you, @tailsparkrabbitear.

heh... before reading this I came up with /^BYE$/{exit}$0=toupper($0)!=$0?"Huh?! Speak up, sonny!":"No, not since "1930+systime()%21"!" which is almost identical...  Using 1930+systime()%21 is a  little shorter.

Yes, but that would make it Gawk only. Currently works with any Awk.

Haskell (189)
import Random
import Char
main=getLine>>=g
g"BYE"=return""
g s|s/=map toUpper s=putStrLn"HUH?! SPEAK UP SONNY!">>main|4>2=randomRIO(30,50::Int)>>=putStrLn.("NO, NOT SINCE 19"++).show>>main

The weird thing is, Haskell code is usually a lot shorter than comparable C code when writing a 'serious' program.

You can avoid importing Char by using any(`elem`['a'..'z'])s to test for lower case letters.

APL (76)
 {'BYE'≢A←⍞:∇⎕←{∧/⍵∊⎕A:'No, not since ',⍕1938+?20⋄'Huh?! Speak up sonny!'}A}⍬

C# - 345 Chars
using System;class Program{static void Main(){for(;;){if(!t(Console.ReadLine()))break;}}static bool t(string s){bool b=false;if(s=="BYE")return b;int i=0;for(;i<s.Length;i++){b=(s[i]>65&&s[i]<90)?true:false;if(!b)break;}if(b) p("NO, NOT SINCE 1938!");else p("HUH?! SPEAK UP, SONNY!");return true;}static void p(string s){Console.WriteLine(s);}}

Damn verbose language ... :-)

You can call the class just P. And this doesn't detect uppercase correctly. I can shout at it and it still cannot hear me. You can shorten the main method to while(t(Console.ReadLine()));. You can use using C=System.Console; at the start to shorten access to ReadLine() and WriteLine() to C.ReadLine() and C.WriteLine().

C# - 196 chars (but leaky)
using System;class P{static void Main(){var s=Console.ReadLine();if(s!="BYE"){Console.Write((s==s.ToUpper()?"No, not since 19"+new Random().Next(30, 51):"Huh?! Speak up, sonny")+"!\n");Main();}}}
That's @Richard's (leaky) answer with two parens (see below) and a \n added in there to get the EOL in both cases. Otherwise the " + " is just wasted space.
Formatted
using System;
class P
{
    static void Main() {
        var s = Console.ReadLine();
        if (s != "BYE") {
            Console.Write((
                s == s.ToUpper() ?
                "No, not since 19" + new Random().Next(30, 51) :
                "Huh?! Speak up, sonny"
                ) + "!\n");
            Main();
        }
    }
}

UPDATE: to clarify my comment about the parens being needed, here's what i get without the parens (i.e. with @Richard's original solution):

And with the parens:

Neither of these use my additional \n though.

It's 195 here, only. Did you count an unnecessary line break at the end?

Bash: 136 128 characters
while read s
do
[[ $s = BYE ]]&&break
[[ ${s^^} = $s ]]&&echo NO, NOT SINCE $[RANDOM%21+1930]!||echo HUH?! SPEAK UP, SONNY!
done

Limited alternative: 132 123 characters
f(){
read s
[[ $s = BYE ]]||{
[[ ${s^^} = $s ]]&&echo NO, NOT SINCE $[RANDOM%21+1930]!||echo HUH?! SPEAK UP, SONNY!
f
}
}
f

You can talk to a deaf infinitely, but the conversation with this later code is limited by the call stack. (In my test it gets terminated after 4989 calls.)

Javascript - 133 131 130 128 127 121 chars
golfed version of www0z0ks solution

g='';while((i=prompt(g))!='BYE'){/[a-z]/.test(i)?g='Huh?! Speak up, sonny!':g='No, not since '+Math.floor(Math.random()*21+1930)+'!'}

g='';while((i=prompt(g))!='BYE'){g=/[a-z]/.test(i)?'Huh?! Speak up, sonny!':'No, not since '+Math.floor(Math.random()*21+1930)+'!'}

g='';while((i=prompt(g))!='BYE'){g=/[a-z]/.test(i)?'Huh?! Speak up, sonny!':'No, not since '+Math.ceil(Math.random()*21+1929)+'!'}

for(g='';(i=prompt(g))!='BYE';g=/[a-z]/.test(i)?'Huh?! Speak up, sonny!':'No, not since '+Math.ceil(Math.random()*21+1929)+'!');

for(g='';(i=prompt(g))!='BYE';g=/[a-z]/.test(i)?'Huh?! Speak up, sonny!':'No, not since '+parseInt(Math.random()*21+1930)+'!');

for(g='';(i=prompt(g))!='BYE';g=/[a-z]/.test(i)?'Huh?! Speak up, sonny!':'No, not since '+(Math.random()*21+1930|0)+'!');

Edit: Saved another six chars with this great tip

Write the ternary operator as g=/[a-z]/.test(i)?'Huh?!...':'No...' and you spare 2 characters.

Edited, thanks for the pointer.

1 more character I found: Math.ceil() is shorter than Math.floor(). Just change the base year to keep the interval unchanged: Math.ceil(Math.random()*21+1929).

Great, +1! I saved another two chars with changing the while to a for loop.

Jelly, 54 bytes
21X+⁽¤Ḷ“Ð€ÑƊʂ!ṡxẈ»,K”!
ɠ¢“®VẹQƝɗi³ỤwṖoỴ»ŒuƑ?ṄßƊḟ⁻?“BYE

Try it online!
Jelly, 49 bytes
21X+⁽¤Ḷ“Ð€ÑƊʂ!ṡxẈ»,K”!µ“®VẹQƝɗi³ỤwṖoỴ»ŒuƑ?ḟ⁻?“BYE

Try it online!
Jelly, 51 bytes
21X+⁽¤Ḷ“Ð€ÑƊʂ!ṡxẈ»,K;”!µ“®VẹQƝɗi³ỤwṖoỴ»ŒuƑ?ḟ⁻?“BYE”

Try it online!

The first one is perhaps the most faithful interpretation of the question. It is a full program which reads input line by line from STDIN and acts on it line by line, terminating either when it reaches "BYE" or the end of STDIN (at which point it exits with an error).
The second is a full program which takes a single string as input (e.g. Hello, HELLO, BYE, etc.) and outputs the corresponding output (an empty output for BYE)
This third is a function which can be repeatedly called with arguments in a similar version to the second, but each argument is independent - calling it with BYE will not prevent you calling it again.
All three output not in uppercase, reflecting the text of the question rather than the sample program provided. +5 bytes to output in all uppercase

As they all have the same basic structure, I'll only explain the first one, and leave the other two as exercises for the reader
How it works
21X+⁽¤Ḷ“Ð€ÑƊʂ!ṡxẈ»,K”! - Helper link. This takes no arguments, outputs a string and returns "!"
21                     - Yield 21
  X                    - Choose a random integer between 1 and 21 inclusive
    ⁽¤Ḷ                - Compressed integer: 1929
   +                   - Add to the random integer. Call that Y
       “Ð€ÑƊʂ!ṡxẈ»     - Compressed string: "No, not since"
                  ,    - Pair; ["No, not since", Y]
                   K   - Join the two with spaces
                    ”! - Unparseable nilad; Output the space separated string and return "!"

ɠ¢“®VẹQƝɗi³ỤwṖoỴ»ŒuƑ?ṄßƊḟ⁻?“BYE - Main link f(). Takes no arguments
ɠ                               - Read a line of STDIN, L
                          ?     - If:
                         ⁻ “BYE -   Condition: L does not equal "BYE"
                       Ɗ        -   Then:
                    ?           -     If:
                   Ƒ            -       Condition: L does not change when:
                 Œu             -         Converted to uppercase
 ¢                              -       Then: Call the helper link, yielding "!"
  “®VẹQƝɗi³ỤwṖoỴ»               -       Else: Compressed string "Huh?! Speak up, sonny!"
                     Ṅ          -     Print with a trailing newline
                      ß         -     Recurse, calling f() again
                        ḟ       -   Else: Return the empty string and halt execution

Vyxal, 57 bytes
{:‛Ṗ⊍⇧≠|aA[`No, λ† ∧Ṡ %!`»÷ḟ»21℅+%,|`Huh?! ∞⇧ up, ½Ŀny!`,

Try it Online!
Vyxal's not particularly good at English compression.
{                                # While...
 :   ≠|                          # Take an input, is it not equal to...
  ‛Ṗ⊍⇧                           # "BYE"
       aA[                       # If all uppercase
          `...`        %,        # Print "No, not since" formatted by
               »÷ḟ»21℅+          # 1929 + random(1..21)
                          `...`, # Otherwise print "Huh?! Speak up, sonny!"

Clojure - 160 154 Characters
(#(if(= % "BYE")%(do(if(=(.toUpperCase %)%)(prn(str"No, not since "(+ 1930(rand-int 9))"!"))(prn"Huh?! Speak up, sonny!"))(recur(read-line))))(read-line))

Working on golfing it a bit more.  Suggestions welcome.
Run through REPL

Q, 115
{while[1;v:read0 0;$[v~"BYE";'`;v~upper v;-1"No, not since ",/:(($)1?1930+(!)20),'"!";-1"Huh?! Speak up, sonny!"]]}

usage
q){while[1;v:read0 0;$[v~"BYE";'`;v~upper v;-1"No, not since ",/:(($)1?1930+(!)20),'"!";-1"Huh?! Speak up, sonny!"]]}`
Hi
Huh?! Speak up, sonny!
Hello
Huh?! Speak up, sonny!
HELLO!
No, not since 1938!
Goodbye Grandma
Huh?! Speak up, sonny!
BYE
'

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


text:
Free a Binary Tree
So before you read some basic computer science concepts.

A binary tree is a dynamically allocated structure (usually used for ordered storage).
Because of its nature traversal of binary trees is usually recursive;
This is because linear traversal (via a loop) is not natural when there are two avenues of looping.

Recursive: This means a function that calls itself.

In old fashioned languages, memory management requires manual memory management.

Manual: Means you have to do it yourself.

When you do manual memory management you need to actual ask the underlying system to free each member of the tree.

Free: recover the memory in to the global poos so it can be re-used and you don't run out of memory.
Freeing: this is done by calling the function free() and passing it the pointer you want to recover.
Pointer: Its like a virtual stick. At the end is memory. When you ask for memory you are given a pointer (virtual stick) that has memory. When you are done you give back the pointer (virtual stick).

The recursive solution:
freeTree(Node* node)
{
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

The problem then is that recursion means you are repeatedly calling the same function. This grows the stack. Growing the stack uses more memory. The reason you are freeing the tree is you want memory back using more memory is counterproductive (even if you do get both bits of memory back).
At last the question:
SO the problem centers around converting the recursive version above into a linear solution (so that you don't have to use memory).
Give the node type
typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Write a function to free a tree of these nodes.
Restrictions:

Cannot use recursion (not even indirectly)
Cannot allocate any dynamic space for tracking.
Note there is an O(n) solution

Winner:

Best Complexity.
Tie Break 1: First Submitted
Tie Break 2: Least amount of characters.

Seems very close to O(n) to me:
This does a depth-first walk on the tree, and uses the ->left pointer of traversed nodes to keep track of the parent.
struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}

+1 Add the tick for the only answer. Its a bit more complex than the solution I present below but very good.

C99, 94, O(n)
Edit: everyone seems to refer to struct Node just as Node as if the typedefed it, so I did too.
this is actually my first C golf.
lots of segfaults.
anyways, this requires C99 because it uses a declaration inside a for loop's first statement.
void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

not even using #define!
this algorithm works by transforming the tree so that the top node has no left child, and then deleting it and moving on to it's right child.
for example, if we start with the tree
 1
/ \
2 3
 \
 4

the algorithm will mutate the pointers so that the tree will be
2
 \
 1
/ \
4 3

now we can delete the topmost node easily.

I did not use typedef because mine was in C++ (you forget these small differences between the languages). I have updated the question so it works the same in C and C++.

@LokiAstari I don't actually know c++, and I just started learning C recently. But I did know enough to answer this :-)

I am going to do a +1 for now. But I still have not worked out how it is working so I will be back after turkey. :-)

@LokiAstari it basically uses the fact that C mixes expressions and statements together to do thing using only expressions

c++ 99 O(n)
The thing here loops are great for chaining along a list but not going up and down hierarchies. user300 managed it (I am impressed) but the code is hard to read.
The solution is to convert the tree into a list.
The trick is to do it at the same time your deleting the nodes.
void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.
    Node* bottomLeft    = findBottomLeft(t);

    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Golf Version
void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf Expanded
void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

C/C++/Objective-C 126 characters (includes required trailing newline)
#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Does not run in O(n) time. But the OP does not require it, so here's my O(n2) solution.
Algorithm:
Walk down to a leaf from the root. Release it. Repeat until there are no leaves. Release the root.
Ungolfed:
void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}

Unfortunately that will not work. you don't set the pointer to the leaf to NULL before freeing it. Thus you will endlessly keep freeing the same leaf node and never get to the point where you free the tree.

@LokiAstari: Thanks for noticing the bug. It should be fixed now (though I haven't tested the code).

C, 150 bytes
f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Try It On JDoodle


text:
Remainder When N divided by 2^M
Write the shortest code to find the remainder when an input number N is divided by 2^M. You cannot use /,* and % operator.
Input Specification
Number of test cases followed by a pair of integers on each line.

Sample Input
1
150 6

Sample Output
22

Limits
1<T<1000
1<N<2^31
1<B<31

Time Limit
1 Sec

Golfscript - 16 chars
~]1>2/{~2\?(&n}/

For a single pair or numbers this would sufficient
~2\?(&

By the way, the / does not stand for division here :)

scanf("%d", &T);
while(T--){
   scanf("%d,%d", &N,&M);
   printf("%d",N&~(~0 << M));
}

What language is this?

Can't you C? ;)

Uh, guys, in pretty much any language, it would be
N & (1 << M  - 1)

Except M should be B and you forgot the code to read the input and loop through each case and write out the answer

@gnibbler, I think the point is that's it's a super-boring question.

@Peter, super-boring is rot13 or reversing stdin. This question isn't that bad by comparison

@gnibbler, it's on a par with factorial, and I don't think those two are separated from rot13 by more than a hair. Reversing stdin requires using a stack in most languages, but even so I don't think it's a worthwhile question either.

I don't think it's boring, I just think there's a canonically correct answer to the underlying math problem.  The problems around looping and printing are boring, or at least pointless, because that's not the way coding challenges present themselves in real life.

Java
With whitespace to make readable:
long F(long M, long N) {
  M = 2<<M;
  while(N>=M) N-=M;
  return N;
}

That would be too slow. :)

@fR0DDY You didn't specify any time constraints.

@marcog Ya! I am sorry about that.

Java (if I remember correctly).

Perl, 31
<>;/ /,say($`&~(-1<<$'))while<>

Perl 5.10 or later, run with perl -E '<code here>'

J, 15 12 9 bytes
6 bytes thanks to @miles.
#.@#:~#&2

Previous 12-byte version
#.@({.~-)~#:

Usage
>> f =: #.@({.~-)~#:
>> 6 f 150
<< 22

Where >> is STDIN and << is STDOUT.
Explanation
#: converts n to base 2.
({.~-)~ then takes the last m digits from it
#. converts it back to base 2.
Previous 15-byte version:
2#.(0-[){.[:#:]

Usage
>> f =: 2#.(0-[){.[:#:]
>> 6 f 150
<< 22

Where >> is STDIN and << is STDOUT.
Explanation
[:#:] converts n to base 2.
(0-[){. then takes the last m digits from it
2#. converts it back to base 2.

Using hooks, I've got #.@({.~-)~#: for 12 bytes.

Isn't the #. dyadic here?

No, it is used afterwards. For example, x f@g y = f (x g y) but something like x f&g y = (g x) f (g y).

Another approach is #.@#:~#&2 for 9 bytes which creates k copies of 2 and uses that to create a base 2 representation of n for the last k binary digits, and converts it back to base 10. Used as 150 (#.@#:~#&2) 6  which outputs 22.

Why don't you post that as a separate answer :)

Racket (scheme) 29 bytes
Kinda cheating because racket doesn't even have the % operator:
(λ(n m)(modulo n(expt 2 m)))

SmileBASIC, 36 characters
INPUT N,M?N AND(1<<M)-1

There's basically only one solution to this...

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


text:
Implement division
Implement a division algorithm in your favourite language which handles integer division. It need only handle positive numbers - but bonus points if it handles negative and mixed-sign division, too. Results are rounded down for fractional results.
The program may not contain the /, \, div or similar operators. It must be a routine which does not use native division capabilities of the language.
You only need to handle up to 32-bit division. Using repeated subtraction is not allowed.
Input
Take two inputs on stdin separated by new lines or spaces (your choice)
740
2

Output
In this case, the output would be 370.
The solution which is the shortest wins.

is 740,2 also permitted for the input? ie comma separated?

"Results are rounded down for fractional results" - ok, so apparently the input can also result in a non-integer number... But what about the divisor being larger than the divided (say, 5 and 10) - is that permitted or not?

@gnibber That would be fine, but make it clear in the program description.

@Aurel300 It is not required to have fractional output. 1/7 may produce 0.142857... or 0.

is using exponentials and other math functions really allowed? they use division behind the scenes, because many solutions are doing ab⁻¹

@SHiNKiROU - yeah I would consider that cheating too...

"Innovative solutions that do not use repeated subtraction" – so good old long division? Hardly innovative, that, though.

does golfscript's \ operator (swap two elements) count as forbidden?

this is shortest-time but I haven't seen anyone time the code

You should have waited to accept an answer. There's a shorter one now.

What does your '' operator mean?

Python - 73 chars
Takes comma separated input, eg 740,2
from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z

This, my friend, is CLEVER

Output for "740,2" is 369. Is this correct?

@Eelvex, should have been <=, fixed it and made it shorter :)

JavaScript, 61
A=Array,P=prompt,P((','+A(+P())).split(','+A(+P())).length-1)

This makes a string the length of the dividend ,,,,,, (6) and splits on the divisor ,,, (3), resulting in an array of length 3: ['', '', ''], whose length I then subtract one from. Definitely not the fastest, but hopefully interesting nonetheless!

My favorite implementation here so far. Congrats for the cool code!

I tried to make it a little shorter. A=Array,P=prompt,P((''+A(+P())).split(','+A(+P())).length)

JavaScript - 36 characters
p=prompt;alert(p()*Math.pow(p(),-1))

Replacing alert with p will net you some extra characters. :)

Python, 37
Step 1.  Convert to unary.
Step 2.  Unary division algorithm.
print('1'*input()).count('1'*input())

Python - 72 chars
Takes comma separated input, eg 740,2
x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z

Mathematica: 34 chars
Solves symbolically the equation (x a == b)
Solve[x#[[1]]==#[[2]],x]&@Input[]

23 chars, Solve[x#==#2]&@@Input[]

Python - 41 chars
Takes comma separated input, eg 740,2
x,y=input();z=x
while y*z>x:z-=1
print z

This, in some cases, is worse than continuously subtracting. e.g., input is 5,4. while loop will run 4 times while in case of subtraction, we will only have to subtract once.

Python, 70
Something crazy I just thought (using comma separated input):
from cmath import*
x,y=input()
print round(tan(polar(y+x*1j)[1]).real)

If you accept small float precision errors, the round function can be dropped.

APL (6)
⌊*-/⍟⎕

/ is not division here, but foldr. i.e, F/a b c is a F (b F c).
If I can't use foldr because it's called /, it can be done in 9 characters:
⌊*(⍟⎕)-⍟⎕

Explanation:

⎕: input()
⍟⎕: map(log, input())
-/⍟⎕: foldr1(sub, map(log, input()))
*-/⍟⎕: exp(foldr1(sub, map(log, input())))
⌊*-/⍟⎕: floor(exp(foldr1(sub, map(log, input()))))

Yabasic - 17 characters
input a,b:?a*b^-1

PHP - 82 characters (buggy)
$i=fgets(STDIN);$j=fgets(STDIN);$k=1;while(($a=$j*$k)<$i)$k++;echo($a>$i?--$k:$k);

This is a very simple solution, however - it doesn't handle fractions or different signs (would jump into an infinite loop). I won't go into detail in this one, it is fairly simple.
Input is in stdin, separated by a new line.
PHP - 141 characters (full)
$i*=$r=($i=fgets(STDIN))<0?-1:1;$j*=$s=($j=fgets(STDIN))<0?-1:1;$k=0;$l=1;while(($a=$j*$k)!=$i){if($a>$i)$k-=($l>>=2)*2;$k+=$l;}echo$k*$r*$s;

Input and output same as the previous one.
Yes, this is almost twice the size of the previous one, but it:

handles fractions correctly
handles signs correctly
won't ever go into an infinite loop, UNLESS the second parameter is 0 - but that is division by zero - invalid input

Re-format and explanation:
$i *= $r = ($i = fgets(STDIN)) < 0 ? -1 : 1;
$j *= $s = ($j = fgets(STDIN)) < 0 ? -1 : 1;
                                    // First, in the parentheses, $i is set to
                                    // GET variable i, then $r is set to -1 or
                                    // 1, depending whether $i is negative or
                                    // not - finally, $i multiplied by $r ef-
                                    // fectively resulting in $i being the ab-
                                    // solute value of itself, but keeping the
                                    // sign in $r.
                                    // The same is then done to $j, the sign
                                    // is kept in $s.

$k = 0;                             // $k will be the result in the end.

$l = 1;                             // $l is used in the loop - it is added to
                                    // $k as long as $j*$k (the divisor times
                                    // the result so far) is less than $i (the
                                    // divided number).

while(($a = $j * $k) != $i){        // Main loop - it is executed until $j*$k
                                    // equals $i - that is, until a result is
                                    // found. Because a/b=c, c*b=a.
                                    // At the same time, $a is set to $j*$k,
                                    // to conserve space and time.

    if($a > $i)                     // If $a is greater than $i, last step
        $k -= ($l >>= 2) * 2;       // (add $l) is undone by subtracting $l
                                    // from $k, and then dividing $l by two
                                    // (by a bitwise right shift by 1) for
                                    // handling fractional results.
                                    // It might seem that using ($l>>=2)*2 here
                                    // is unnecessary - but by compressing the
                                    // two commands ($k-=$l and $l>>=2) into 1
                                    // means that curly braces are not needed:
                                    //
                                    // if($a>$i)$k-=($l>>=2)*2;
                                    //
                                    // vs.
                                    //
                                    // if($a>$i){$k-=$l;$l>>=2;}

    $k += $l;                       // Finally, $k is incremented by $l and
                                    // the while loop loops again.
}

echo $k * $r * $s;                  // To get the correct result, $k has to be
                                    // multiplied by $r and $s, keeping signs
                                    // that were removed in the beginning.

You used a division operator in this one, you might get away with a bit shift though. ;)

@Thomas O yeah... I noticed it now... I was actually thinking about a bit shift (when I changed it to /=2 instead of /=10) - but it was one more char... Guess I'll have to use it anyway... Btw that is not division at all :D.

The question says you need to use stdin, which PHP does have support for.

@Bass5098 Aaahhh... Oh well, gained 4 chars... Fixed.

Ruby 1.9, 28 characters
(?a*a+?b).split(?a*b).size-1

Rest of division, 21 characters
?a*a=~/(#{?a*b})\1*$/

Sample:
a = 756
b = 20
print (?a*a+?b).split(?a*b).size-1  # => 37
print ?a*a=~/(#{?a*b})\1*$/         # => 16

For Ruby 1.8:
a = 756
b = 20
print ('a'*a+'b').split('a'*b).size-1  # => 37
print 'a'*a=~/(#{'a'*b})\1*$/          # => 16

NoMethodError: private method `split' called for 69938:Fixnum

@rkj, Sorry, Ruby 1.9 only. To run on Ruby 1.8 you must do ('a'*a+'b').split('a'*b).size-1, 3 characters bigger.

PHP, 55 characters
<?$a=explode(" ",fgets(STDIN));echo$a[0]*pow($a[1],-1);

Output (740/2): http://codepad.viper-7.com/ucTlcq

44 chars: <?$a=fgetcsv(STDIN);echo$a[0]*pow($a[1],-1); Just use a comma instead of a space to separate numbers.

Scala 77
def d(a:Int,b:Int,c:Int=0):Int=if(b<=a)d(a-b,b,c+1)else c
d(readInt,readInt)

Haskell, 96 characters
main=getLine>>=print.d.map read.words
d[x,y]=pred.snd.head.filter((>x).fst)$map(\n->(n*y,n))[0..]

Input is on a single line.
The code just searches for the answer by taking the divisor d and multiplying it against all integers n >= 0. Let m be the dividend. The largest n such that n * d <= m is picked to be the answer. The code actually picks the least n such that n * d > m and subtracts 1 from it because I can take the first element from such a list. In the other case, I would have to take the last, but it's hard work to take the last element from an infinite list. Well, the list can be proven to be finite, but Haskell does not know better when performing the filter, so it continues to filter indefinitately.

Common Lisp, 42 charaacters
(1-(loop as x to(read)by(read)counting t))

Accepts space or line-separated input

Python - 45 chars
Takes comma separated input, eg 740,2
x,y=input()
print-1+len((x*'.').split('.'*y))

Bash, 72 64 characters
read x y;yes ''|head -n$x>f;ls -l --block-size=$y f|cut -d\  -f5

Output an infinite number of newlines, take the first x, put them all into a file called f, then get the size of f in blocks the size of y.
Took manatwork's advice to shave off eight characters.

As “Take two inputs on stdin separated by new lines or spaces (your choice)”, better choose the later, the space separated values. In which case you can write read x y. With a few more spaces removed can be reduced to 64 characters: http://pastebin.com/Y3SfSXWk

Python, 37
x,y=input()
print len(('0'*x)[y-1::y])

Constructs a string of length x ('0'*x) and uses extended slicing to pick every yth character, starting from the index y-1. Prints the length of the resulting string.
Like Gnibbler, this takes comma separated input. Removing it costs 9 chars:
i=input
x,y=i(),i()
print len(('0'*x)[y-1::y])

Retina 0.7.3, 33 bytes
Takes space-separated input with the divisor first. Dividing by zero is undefined.
\d+
$*
^(.+) (\1)+.*$
$#+
.+ .*
0

Try it online

How do you count this as 25 bytes? If you expect unary I/O you should say so (and I think then it's 24 bytes). Not sure why you treat the 0 case separately though: http://retina.tryitonline.net/#code=LisKJCoKKC4rKcK2KFwxKSouKgokIys&input=Mgo3NDA

It was mis-copied

Python, 46 bytes
Nobody had posted the boring subtraction solution, so I could not resist doing it.
a,b=input()
i=0
while a>=b:a-=b;i+=1
print i

Python, 94 characters
A recursive binary search:
a,b=input()
def r(m,n):return r(m,m+n>>1)if n*b>a else n if n*b+b>a else r(n,2*n)
print r(0,1)

Python, 40 characters
print(float(input())*float(input())**-1)

C, 43 bytes
Implements a/b in a linear search. Handles only positive arguments.
i;f(a,b){i=0;while(1)if(++i*b>a)return--i;}

Ungolfed:
i;
f(a, b){
  i = 0;
  while (1)
    if (++i * b > a)
      return --i;
}

Smalltalk, Squeak 4.x flavour
define this binary message in Integer:
% d
    | i |
    d <= self or: [^0].
    i := self highBit - d highBit.
    d << i <= self or: [i := i - 1].
    ^1 << i + (self - (d << i) % d)

Once golfed, this quotient is still long (88 chars):
%d|i n|d<=(n:=self)or:[^0].i:=n highBit-d highBit.d<<i<=n or:[i:=i-1].^1<<i+(n-(d<<i)%d)

But it's reasonnably fast:
[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n%d)]].
] timeToRun.

-> 127 ms on my modest mac mini (8 MOp/s)
Compared to regular division:
[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n//d)]].
] timeToRun.

-> 31 ms, it's just 4 times slower
I don't count the chars to read stdin or write stdout, Squeak was not designed for scripting.
FileStream stdout nextPutAll:
    FileStream stdin nextLine asNumber%FileStream stdin nextLine asNumber;
    cr

Of course, more stupid repeated subtraction
%d self>d and:[^0].^self-d%d+1

or plain stupid enumeration
%d^(0to:self)findLast:[:q|q*d<=self]

could work too, but are not really interesting

DC: 26 characters
?so?se0[1+dle*lo>i]dsix1-p

I do admit that it is not the fastest solution around.

Python 54
Takes comma delimited input.

Makes a string of dots of length x
Replaces segments of dots of length y with a single comma
Counts commas.

Words because markdown dies with a list followed by code?:
x,y=input()
print("."*x).replace("."*y,',').count(',')

Q, 46
{-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}

.
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;2]
370
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;3]
246