Factor in Haskell - quotations

Last week we introduced factor, a concatenative programming language.

We have seen basic operations such as managing the stack and using functions, as follows:

6 7 * ! 42

We have not seen quotations, which are a way to line up operations delaying evaluation; they also come with associated functions, as follows:

8 [ 4 * ] call

[ 4 * ] is only applied when call is applied.

I have used “applied” purposefully here, because it looks like functions, even closures, functions capturing an environment.

It's not obvious, but we can directly push Stack-based functions, as follows:

bareQuote :: Stack '[Stack (Int : Int : xs) -> Stack (Int : xs), Int, Int]
bareQuote = push_ 2 .% push_ 6 % push_ (app21_ (-))

To ease quotations, we can come up with the following helpers:

type Quotation xs ys = Stack xs -> Stack ys

quote11_ :: (a -> b) -> Stack xs -> Stack (Quotation (a ': ys) (b ': ys) ': xs)
quote11_ = push_ . app11_

quote12_ :: (a -> (b, c)) -> Stack xs -> Stack (Quotation (a ': ys) (b ': c ': ys) ': xs)
quote12_ = push_ . app12_

quote21_ :: (a -> b -> c) -> Stack xs -> Stack (Quotation (a ': b ': ys) (c ': ys) ': xs)
quote21_ = push_ . app21_

quote22_ :: (a -> b -> (c, d)) -> Stack xs -> Stack (Quotation (a ': b ': ys) (c ': d ': ys) ': xs)
quote22_ = push_ . app22_

Which allows us to rewrite our previous example as follows:

quoted :: Stack '[Quotation (Int : Int : xs) (Int : xs), Int, Int]
quoted = push_ 2 .% push_ 6 % quote21_ (-)

The next step is to implement call, which is applying the top of the stack to the tail, as follows:

call_ :: Stack (Quotation xs ys ': xs) -> Stack ys
call_ (q :* ys) = q ys

It can be used as follows:

called :: Stack '[Int]
called = push_ 2 .% push_ 6 % quote21_ (-) % call_

The great idea behind this implementation is that it composes, for example, moving the element inside the quotation, as follows:

bareQuoteCurry :: Stack '[Quotation (Int : xs) (Int : xs), Int]
bareQuoteCurry = push_ 2 .% push_ (push_ 6 % app21_ (-))

Actually, if we want to be playful, and being playful should be more than a mindset, a lifestyle, we can work on composition, as follows:

bareQuotePartialApplied :: Stack '[Quotation (Int : xs) (Int : xs), Int]
bareQuotePartialApplied = push_ 2 .% push_ (push_ 6) % push_ (app21_ (-)) % comp_

factor has a function called curry which applies a “pure” value to a quotation; let's define comp_ for the moment as follows:

comp_ ::
  Stack (Quotation ys zs ': Quotation xs ys ': as) ->
  Stack (Quotation xs zs ': as)
comp_ (g :* f :* as) = (f % g) :* as

Additionally, we can compose quotations directly through Category, as follows:

newtype Quotation' xs ys = Q {runQ :: Stack xs -> Stack ys}

instance Category Quotation' where
  id = Q id
  Q f . Q g = Q (f . g)