Writing a Forth: Quotations

Factor, another Forth-like language, introduces ‘quotations’ to the concatenative paradigm.

[ 1 1 = ] .
\ [ 1 1 = ]

[ 1 + ] [ 2 * ] compose .
\ [ 1 + 2 * ]

4 [ > ] curry .
\ [ 4 > ]

5 [ 1 + 2 * ] call .
\ 12

Quotations serve the same role as lambda’s in other languages, but have a few key advantages:

data Val = Number Int
         | Bool Bool
         | Symbol String
         | Word { immediate :: Bool,
                  wordType  :: WordType }
         | Nil
         deriving (Eq)


data WordType = Primitive (Forth Val)
              | User [Val]


instance Show Val where
  -- ...
  show Word {wordType = User stack} =
    "[ " ++ unwords (map show stack) ++ " ]"  


instance Eq WordType where
  User s == User z = s == z
  _ == _ = False

Brackets delimit a quotation.

exprs :: Parser [Val]
exprs = many expr

expr :: Parser Val
expr = between spaces spaces $
  bool <|> word <|> number <|> quotation

quotation :: Parser Val
quotation = do
  char '['
  es <- exprs
  char ']'
  return $ makeWord es

They are evaluated like ordinary values: pushed on the stack, not invoked.

eval :: Val -> Forth ()
eval val = do
  state <- get
  case val of
    -- ...
    Word _ _ ->
      push val
    -- ...

To call a quotation, evaluate it’s body.

call = do
  q <- pop
  evalBody (wordBody q)

To compose two quotations, concatenate their bodies.

compose = do
  y <- pop
  x <- pop
  push $ makeWord (wordBody x ++ wordBody y)

To partially apply a quotation, add the second stack item to the front of it’s body.

curry' = do
  q <- pop
  x <- pop
  push $ makeWord (x : wordBody q)