Implement hyperexponentiation/tetration without the use of '^'

J, score is 7 (12 chars - 5 points for avoiding multiplication)

+/@$/@$~/@$~

usage:

   4 +/@$/@$~/@$~ 3
1.34078e154
t=.+/@$/@$~/@$~  NB. define a function
   4 t 3
1.34078e154
   2 t 2
4

Just few nested folds:

• Using multiplication it would be */@$~/@$~
• Using power it would be ^/@$~ where $~ creates array, / is a fold function.

Haskell, 87 85 - 5 == 80 82

import Data.List
t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)

Uses neither of exponentiation, multiplication or addition (!), just list operations. Demonstration:

Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3

...
ahm... you didn't say anything about performance or memory, did you? But given enough billions of years and some petabytes of RAM, this would still yield the correct result (genericLength can use a bigInt to count the length of the list).

GolfScript, 15 18 chars

~])*1\+{[]+*{*}*}*

Yes, one of the *s is a multiplication operator (exercise: which one?) so I don't qualify for the 5 char bonus. Still, it's just barely shorter than Peter's solution.

This earlier 15-char version is otherwise the same, but produces no output when the second argument is 0. Thanks to r.e.s. for spotting the bug.

~])*{[]+*{*}*}*