I had an idea that passing arguments on the stack, in a language like Forth, is like partially applying a continuation with the contents of the stack (does that make any sense?) We represent a Forth program in continuation-passing style, passing extra arguments to the continuation to “push the stack”, taking arguments and not passing them on to “pop the stack”. In Haskell we can define the following “words”:
> push x k = k x > pop k a = k > dup k a = k a a > swap k b a = k a b > over k b a = k a b a > nip k b a = k b > cond k f t p = (if p then t else f) k > when k t p = if p then t k else k
Haskell provides us the correct polymorphic types automatically.
push :: a -> (a -> b) -> b pop :: a -> b -> a dup :: (a -> a -> b) -> a -> b swap :: (a -> b -> c) -> b -> a -> c over :: (a -> b -> a -> c) -> b -> a -> c nip :: (a -> b) -> a -> c -> b cond :: a -> (a -> b) -> (a -> b) -> Bool -> b when :: a -> (a -> a) -> Bool -> a
Now we can write Forth-like programs by nested partial application. To avoid getting Lost In Superfluous Parentheses we use the dollar ($) operator. Welcome to “DollarForth”.
> binop op k b a = k (op a b) > add = binop (+) > sub = binop (-) > mul = binop (*) > lt k b a = k (a < b) > neg k x = k (-x) > square k = dup $ mul $ k : square dup * ; > absolute k = dup $ push 0 $ lt $ push (neg) $ when $ k : absolute dup 0 < if negate then ; > boolToStr k = push (push "yes") $ push (push "no") $ cond $ k : boolToStr if "yes" else "no" then ; > main = do > print $ push 8 $ square $ id > print $ push 10 $ push 20 $ dup $ add $ swap $ sub $ id > print $ push 4 $ absolute $ push (-4) $ absolute $ binop (,) $ id > putStrLn $ push "hello, " $ push "world!" $ binop (++) $ id > print $ push True $ boolToStr $ push False $ boolToStr $ binop (,) $ id > print $ push "x" $ push "y" $ over $ binop (++) $ binop (++) $ id > print $ push 1 $ push 2 $ swap $ nip $ id
The good news: we now have a statically-typed Forth, with static stack inference, for free. The bad news: it is very difficult to program in this style – type errors are common and utterly indecipherable. It is also very hard to understand how it works – I have only a vague idea myself.
I have failed to define a loop operator or use recursion in DollarForth. Is it even possible within the bounds of Haskell’s type system?