Perpetual Weekend

3 March 2007

Forth as a Haskell DSL, or Lambda: The Ultimate Stack?

Filed under: Uncategorized — shaurz @ 20:05

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?

About these ads

5 Comments »

  1. Chris Okasaki. 2002. Techniques for embedding postfix
    languages in Haskell
    . In Proceedings of the 2002 Haskell
    workshop, ed. Manuel M. T. Chakravarty, 105-113. New York: ACM
    Press.

    Code
    ACM

    Comment by Chung-chieh Shan — 4 March 2007 @ 6:34

  2. I’m an amateur but I think Over kba = kbab, not kaba.

    Comment by Jay Hermans — 4 March 2007 @ 20:51

  3. Chung-chieh, thanks for the links. I will check them out. Sorry for the delay in you comment appearing, I had to approve it since it had > 2 links.

    Comment by shaurz — 4 March 2007 @ 22:07

  4. Jay, my definition of ‘over’ works, but I think I might have the direction of the stack diagrams messed up. It should probably be:

    over k a b = k b a b

    P.S. I’m just an amateur too :-)

    Comment by shaurz — 4 March 2007 @ 22:12

  5. You might want to consider a language based fully on combinatorics, such as Fexl (Function EXpression Language): http://fexl.com . That lets you write functions however you like, with or without intermediate symbols.

    Comment by Patrick — 25 May 2011 @ 15:40


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: