This lack of generality is clearly the cause of inconvenience #3.

One solution to this is to expand the definition of MatchFn to also return an IdMap (so chained functions can access it), and to write a few new chaining helper-functions that allow access to different parts of the returned tuple.

type MatchFn a = (IdMap, [Token]) -> Maybe (a, [Token], IdMap)

mfFmap            :: (         a ->         b) -> MatchFn a -> MatchFn b
mfFBindMaybe      :: (         a -> Maybe   b) -> MatchFn a -> MatchFn b
mfFBindIdm        :: (IdMap -> a ->         b) -> MatchFn a -> MatchFn b
mfFBindIdm'       :: (IdMap -> a -> MatchFn b) -> MatchFn a -> MatchFn b
mfFBindIdmMaybe   :: (IdMap -> a -> Maybe   b) -> MatchFn a -> MatchFn b
mfFBind           :: (         a -> MatchFn b) -> MatchFn a -> MatchFn b

This isn’t a very good solution, though, as it adds a lot of boilerplate (much of which is rarely used), and it doesn’t fix the other inconveniences. Additionally, by adding IdMap to the return type, it introduces the (albeit unlikely) possibility that a parsing function may modify the IdMap.

A better solution is to change MatchFn into a monad whose functions exactly match the desired behavior, then to use generic monadic functions instead of chFst and mchFst.

type MatchFn a = StateT [Token] (MaybeT (Reader IdMap)) a

It’s probably a little steep to try to completely explain this type, so I’ll keep it high-level. The names that end with ‘T’ are Monad Transformers, which take another monad as one of their type parameters, to form a single resulting monad. Each of the following is a monad.

• Reader IdMap
• MaybeT (Reader IdMap)
• StateT [Token] (MaybeT (Reader IdMap))

Monad transformers preserve the behavior of the monad they receive, and add their own behavior on top^.

It’s interesting to note that MatchFn itself is no longer a function: it is a monad whose state internal state is a function^.

This requires another reworking of the “match-” functions, but the “parse-” functions can (again) stay mostly the same, except (<$>) (fmap) replaces chFst, and (=<<) (or (>>=) or do-notation) replaces mchFst.

+evalMatchFn :: IdMap -> [Token] -> MatchFn a -> Maybe (a, [Token])
+evalMatchFn idm toks = (flip runReader) idm . runMaybeT . (flip runStateT) toks

+maybeMatch :: MatchFn a -> MatchFn (Maybe a)
+maybeMatch f = do
+    idm <- getIdm
+    toks <- get
+    case evalMatchFn idm toks f of
+        Nothing -> return Nothing
+        Just (x, toks') -> do
+            put toks'
+            return $ Just x

 matchOne :: [MatchFn a] -> MatchFn a
 -- return first successful match, else Nothing
-matchOne fns args = foldl try Nothing fns
-    where try (Just x) _ = Just x -- already found match
-          try Nothing f = f args
+matchOne [] = mzero
+matchOne (f:fs) = do
+    mb <- maybeMatch f
+    case mb of
+        Nothing -> matchOne fs
+        Just x -> return x

 matchAll :: [MatchFn a] -> MatchFn [a]
--- match every function in list (sequentially), returning their results, else Nothing
-matchAll fns (idm, toks) = chFst (reverse) . foldl try (Just ([], toks)) $ fns
-    where try Nothing _ = Nothing
-          try (Just (rs, ts)) f = case f (idm, ts) of
-              Just (r, ts') -> Just(r:rs, ts')
-              _ -> Nothing
+matchAll [] = return []
+matchAll (f:fs) = do
+    a <- f
+    as <- matchAll fs
+    return $ a:as

 -- ... etc.

 matchT2 :: (MatchFn a, MatchFn b) -> MatchFn (a, b)
-matchT2 (fa, fb) (idm, ts) = case fa (idm, ts) of
-    Nothing -> Nothing
-    Just (a, ts') -> case fb (idm, ts') of
-        Nothing -> Nothing
-        Just (b, ts'') -> Just ((a, b), ts'')
+matchT2 (fa, fb) = do
+    a <- fa
+    b <- fb
+    return (a, b)

 -- .. etc.

 parseOpOrFn :: MatchFn (Operator, FnTreeNode)
 parseOpOrFn = matchOne [
-        chFst (\_ -> (oReduce, FnLeafFn fReplicate)) . matchCh '/',
-        chFst (\_ -> (oScan, FnLeafFn fExpand)) . matchCh '\\',
-        chFst (\_ -> (oReduceFirst, FnLeafFn fReplicateFirst)) . matchCh '⌿',
-        chFst (\_ -> (oScanFirst, FnLeafFn fExpandFirst)) . matchCh '⍀'
+        (\_ -> (oReduce, FnLeafFn fReplicate)) <$> matchCh '/',
+        (\_ -> (oScan, FnLeafFn fExpand)) <$> matchCh '\\',
+        (\_ -> (oReduceFirst, FnLeafFn fReplicateFirst)) <$> matchCh '⌿',
+        (\_ -> (oScanFirst, FnLeafFn fExpandFirst)) <$> matchCh '⍀'
     ]

 parseArr :: MatchFn ArrTreeNode -- parse an entire literal array
-parseArr = chFst (_roll) . matchT2 (
+parseArr = (_roll) <$> matchT2 (
         parseArrComp,
-        chFst (concat) . matchMax [ matchOne [
-            chFst (Left) . parseArrComp,
-            chFst (\(_, il, _) -> Right il) . matchT3 (
+        (concat) <$> matchMax [ matchOne [
+            (Left) <$> parseArrComp,
+            (\(_, il, _) -> Right il) <$> matchT3 (
                 matchCh '[',
                 parseIdxList,
                 matchCh ']'
             )
         ]]
     )

 -- .. etc.

Evaluating mzero in the monad at any time causes the internal function to unconditionally return Nothing (effectively short-circuit). This behavior comes from MaybeT.

The new version of parseDerFn:

parseDerFn = matchOne [_parseOpExpr, parseFn]
    where _parseOpExpr = do
              lhs <- _parseArg
              otn <- parseOp
              _parseOpExprRec lhs otn
          _parseArg = matchOne [parseFn, FnLeafArr <$> parseArr]
          _parseOpExprRec :: FnTreeNode -> OpTreeNode -> MatchFn FnTreeNode
          _parseOpExprRec lhs otn = do
              df <- case unwrapOpTree otn of
                        (MonOp _ _) -> return $ FnInternalMonOp otn lhs
                        (DyadOp _ _) -> do rhs <- _parseArg
                                           return $ FnInternalDyadOp otn lhs rhs
              mb <- maybeMatch parseOp
              case mb of
                   Nothing -> return $ df
                   (Just otn2) -> _parseOpExprRec df otn2

Parser, Version 4 (+Applicative)

My favorite part about Haskell: realizing a built-in function does precisely what you want.

It turns out that, circa 2014, all Monads in Haskell are also Applicative Functors. (<*>), (<*), and (*>) remove the need for the MatchT functions, and the vast majority of lambdas (typically as the LHS’s of <$>).

 parseDerArr :: MatchFn ArrTreeNode
 parseDerArr = matchOne [
         parseArrAss,
-        (\(f, da) -> ArrInternalMonFn f da) <$> matchT2 (parseDerFn, parseDerArr),
-        (\(lhs, f, rhs) -> ArrInternalDyadFn f lhs rhs) <$> matchT3 (
-            parseArr,
-            parseDerFn,
-            parseDerArr
-        ),
+        ArrInternalMonFn <$> parseDerFn <*> parseDerArr,
+        (flip ArrInternalDyadFn) <$> parseArr <*> parseDerFn <*> parseDerArr,
         parseArr
     ]

 parseArrAss :: MatchFn ArrTreeNode
 parseArrAss = matchOne [
-        (\(id, _, da) -> ArrInternalAssignment id da) <$> matchT3 (
-            matchId,
-            matchCh '←',
-            parseDerArr
-        ),
-        (\(id, df, _, da) -> ArrInternalModAssignment id df da) <$> matchT4 (
-            matchId,
-            parseDerFn,
-            matchCh '←',
-            parseDerArr
-        )
+        ArrInternalAssignment <$> matchId <*> (matchCh '←' *> parseDerArr),
+        ArrInternalModAssignment <$> matchId <*> parseDerFn <*> (matchCh '←' *> parseDerArr)
     ]

 -- ... etc.

Version 4 is over 100 lines shorter than version 3.

Evaluation

This project was relatively large in scope (at least in comparison to what I’m used to), so there are a lot of nuances in the evaluation of the syntax trees. I’ve picked a few of the more-interesting ones to highlight.

Functions as Data

APL makes combination of functions very natural; adjacent functions and operators alone form trees (even before application to arrays)^.

For example, here’s the tree for the function h2n (from an earlier example):

    c2n ← '23456789TJQKA'∘⍳
    classify ← (5-≢⍤∪),(⌈/(+/∘.=⍨)),((5≡∪)×(⌈/c2n))
    h2n ← 13⊥classify,(¯1∘+c2n)
    h2n
 ┌──┼────────────┐
 13 ⊥ ┌──────────┼────────────────────────┐
  ┌───┼────────┐ ,                   ┌────┴─────┐
┌─┼─┐ ,    ┌───┼───────┐             ∘          ∘
5 - ⍤    ┌─┴─┐ ,   ┌───┼─────┐      ┌┴─┐ ┌──────┴──────┐
   ┌┴┐   / ┌─┴─┐ ┌─┼─┐ × ┌───┴────┐ ¯1 + 23456789TJQKA ⍳
   ≢ ∪ ┌─┘ /   ⍨ 5 ≡ ∪   /        ∘
       ⌈ ┌─┘ ┌─┘       ┌─┘ ┌──────┴──────┐
         +   ∘.        ⌈   23456789TJQKA ⍳
           ┌─┘
           =

Since functions are higher-order in Haskell, it’s natural to store them as normal data. Thus, upon evaluation (in this case, evaluation happens when h2n is assigned to^{), the variable h2n no longer has access to the syntax tree, it only holds a primitive haskell function, a string which represents the scrapped tree, and a few other values describing the behavior of the function.}

type FuncM = Array -> StateT IdMap IO Array
type FuncD = Array -> FuncM

data Function = MonFn FnInfoM FuncM
              | DyadFn FnInfoD FuncD
              | AmbivFn FnInfoA FuncM FuncD

-- "function tree": a tree that makes up a derived function:
-- the internal nodes are operators, and the leaves are functions or (derived) arrays
data FnTreeNode = FnLeafFn Function
                | FnLeafVar String
                | FnLeafArr ArrTreeNode
                | FnInternalMonOp OpTreeNode FnTreeNode
                | FnInternalDyadOp OpTreeNode FnTreeNode FnTreeNode
                | FnInternalAtop FnTreeNode FnTreeNode
                | FnInternalFork FnTreeNode FnTreeNode FnTreeNode
                | FnInternalAssignment String FnTreeNode
                | FnInternalQuadAssignment FnTreeNode
                | FnInternalAxisSpec FnTreeNode ArrTreeNode
                | FnInternalDummyNode FnTreeNode

evalFnTree :: FnTreeNode -> StateT IdMap IO (Either Array Function)

Practical Typeclasses

Like the parser, evaluation uses monads to handle state. Since any arbitrary function might have full control over the program state, in order to have a universal function type, that type (Function (see above)) must be impure^.

The majority of built-in Functions don’t touch the global state, and the ones that do usually only use it for a very narrow purpose. I wanted a mechanism that allowed me to define these Functions with maximally constraining types, yet to easily convert them into the full (non-constrained) monad (EvalM) without causing a combinatorial explosion of helper functions. I used the typeclass SubEvalM to do this.

{- SubEvalM (subset of EvalM): typeclass for wrapper monads -}

type EvalM = StateT IdMap IO

class (Monad m) => SubEvalM m where
    toEvalM :: m a -> EvalM a

instance SubEvalM Identity where
    toEvalM = return . runIdentity

newtype IdxOriginM a = IdxOriginM { unIdxOriginM :: Reader Int a }
    deriving (Functor, Applicative, Monad, MonadReader Int) via (Reader Int)

instance SubEvalM IdxOriginM where
    toEvalM iom = do
        idm <- get
        let iO = case mapLookup "⎕IO" idm of
                  Just (IdArr a)
                      | ScalarNum n <- a `at` 0 -> Prelude.floor $ n
                  Just _ -> undefined -- unexpected val for ⎕IO
                  _ -> undefined -- no val for ⎕IO
        return . (flip runReader) iO . unIdxOriginM $ iom

newtype RandAndIoM a = RandAndIoM { unRandomAndIoM :: StateTStrict.StateT StdGen (Reader Int) a }
    deriving (Functor, Applicative, Monad, MonadReader Int, MonadState StdGen) via StateTStrict.StateT StdGen (Reader Int)

instance SubEvalM RandAndIoM where
    toEvalM rm = do
        gen <- lift $ newStdGen
        toEvalM . IdxOriginM . runStateGenT_ gen $ \_ -> unRandomAndIoM rm


{- Monad Wrappers -}

mkMonFn :: SubEvalM m => FnInfoM -> (Array -> m Array) -> Function
mkMonFn i f = MonFn i (\a -> toEvalM $ f a)

mkDyadFn :: SubEvalM m => FnInfoD -> (Array -> Array -> m Array) -> Function
mkDyadFn i f = DyadFn i (\a b -> toEvalM $ f a b)

mkAmbivFn :: (SubEvalM m0, SubEvalM m1) => FnInfoA -> (Array -> m0 Array) -> (Array -> Array -> m1 Array) -> Function
mkAmbivFn ia fm fd = AmbivFn ia (\a -> toEvalM $ fm a) (\a b -> toEvalM $ fd a b)

-- (mkMonOp, ... etc.)

{- Pure Wrappers -}

pureMonFn :: FnInfoM -> (Array -> Array) -> Function
pureMonFn i f = mkMonFn i (Identity . f)

pureDyadFn :: FnInfoD -> (Array -> Array -> Array) -> Function
pureDyadFn i f = mkDyadFn i (Identity .: f)

pureAmbivFn :: FnInfoA -> (Array -> Array) -> (Array -> Array -> Array) -> Function
pureAmbivFn ia fm fd = mkAmbivFn ia (Identity . fm) (Identity .: fd)

-- (pureMonOp, ... etc.)

Selective Assignment

APL has a feature called “selective assignment” where the left-hand-side of an assignment can be an expression, so long as it only uses (pre-verified) functions that solely permute/select items of the argument array. For example:

    x ← 2 2⍴⍳4
    x
1 2
3 4
    (,⌽x) ← ⍳4 ⍝ assign ⍳4 to the ravel (,) of
    x          ⍝ the reversed (along the last axis) (⌽) x
2 1
4 3

At first glance, this seems like implementing this will require a re-implementation of each selectable function, which can be called to determine which cells of the variable are selected, and their shape. However, after making the above assumption (all selectable functions do not mutate the cells of their argument), the selected array (x, in the above example) can simply be replaced by an array of the same shape whose cells are the indices of x (⍳⍴x), then, after applying the selecting functions, the result will be some permutation/selection of the indices of (⍳⍴x), which can then be assigned to. So, for the above example, we have

    x ← 2 2⍴⍳4
    x
1 2
3 4
    ⍴x
2 2
    ⍳⍴x
┌───┬───┐
│1 1│1 2│
├───┼───┤
│2 1│2 2│
└───┴───┘
    ⌽⍳⍴x
┌───┬───┐
│1 2│1 1│
├───┼───┤
│2 2│2 1│
└───┴───┘
    ,⌽⍳⍴x
┌───┬───┬───┬───┐
│1 2│1 1│2 2│2 1│
└───┴───┴───┴───┘
    x[,⌽⍳⍴x]
2 1 4 3
    x[,⌽⍳⍴x] ← ⍳4
    x
2 1
4 3

Higher-Dimensional Arrays: It’s Just Indexing

One of the hardest aspects of implementing the built-in functions/operators was making them work on higher-dimensional arrays. The majority APL primitives are trivially implemented on vectors and scalars, but their behavior becomes much harder to understand when they operate on n-dimensional arrays.

For example, dyadic (,) ([con]catenate). Just put the two arrays together, no problem, right?

catenate :: Double -> Array -> Array -> IdxOriginM Array
catenate ax x y
    | isIntegral ax = ask >>= \iO -> let ax' = (Prelude.floor ax) - iO + 1
                                     in return $ _catenate ax'
    | otherwise = ask >>= \iO -> let ax' = (Prelude.ceiling ax) - iO
                                 in return $ _laminate ax'
    where _catenate ax'
              | ax' <= 0 || ax' > rank = throw . RankError $ "(,): invalid axis"
              | x == zilde = y
              | y == zilde = x
              | (shape'' x') /= (shape'' y') = throw . LengthError $ "(,): mismatched argument shapes"
              | otherwise = zipVecsAlongAxis ax'' ax'' ax'' (++) x' y'
              where (x', y') = _rankMorph (x, y)
                    rank = arrRank x'
                    _rankMorph (a, b)
                        | shape a == [1] && arrNetSize b > 0 = (shapedArrFromList (shape'1 b) $ Prelude.replicate (foldr (*) 1 $ shape'1 b) (a `at` 0), b)
                        | shape b == [1] && arrNetSize a > 0 = (a, shapedArrFromList (shape'1 a) $ Prelude.replicate (foldr (*) 1 $ shape'1 a) (b `at` 0))
                        | arrRank a == arrRank b = (a, b)
                        | arrRank a == arrRank b + 1 && ax' <= arrRank a = (a, b {shape = take _ax' (shape b) ++ [1] ++ drop _ax' (shape b)})
                        | arrRank a + 1 == arrRank b && ax' <= arrRank b = (a {shape = take (_ax' + 1) (shape a) ++ [1] ++ drop (_ax' + 1) (shape a)}, b)
                        | otherwise = throw . RankError $ "(,): mismatched argument ranks"
                        where _ax' = ax' - 1
                    shape'1 a = take (ax' - 1) (shape a) ++ [1] ++ drop ax' (shape a)
                    shape'' a = take (ax'' - 1) (shape a) ++ drop ax'' (shape a)
                    ax'' = if arrRank x' == arrRank x + 1 then ax' + 1 else ax'
          _laminate ax'
              | ax' < 0 || ax' > rank = throw . RankError $ "(,): invalid axis"
              | (shape x') /= (shape y') = throw . LengthError $ "(,): mismatched argument shapes"
              | otherwise = unAlongAxis (ax' + 1) [x', y']
              where (x', y') = _rankMorph (x, y)
                    rank = arrRank x'
                    _rankMorph (a, b)
                        | shape a == [1] && arrNetSize b > 0 = (shapedArrFromList (shape b) $ Prelude.replicate (arrNetSize b) (a `at` 0), b)
                        | shape b == [1] && arrNetSize a > 0 = (a, shapedArrFromList (shape a) $ Prelude.replicate (arrNetSize a) (b `at` 0))
                        | shape a == shape b = (a, b)
                        | otherwise = throw . RankError $ "(,): mismatched argument ranks"

The majority of this code is actually just edge-cases (which are difficult in their own right), but the key functions to note are zipVecsAlongAxis and unAlongAxis (which are applied after the edge-cases are resolved). All primitives functions that operate on higher-dimensional arrays can be expressed using a handful of helper functions. All of those helpers are built on top of three core functions.

alongAxis :: Int -> Array -> [Array]
alongAxis ax a
    | ax - _iO >= (length . shape $ a) = throw $ RankError "invalid axis"
    | (length . shape $ a) == 0 = []
    | arrNetSize a == 0 = []
    | otherwise = map (subarrayAt) [0..(n - 1)]
        where n = (shape a) !! (ax - _iO)
              shape' = if (length . shape $ a) == 1
                       then [1]
                       else take (ax - _iO) (shape a) ++ drop (ax - _iO + 1) (shape a)
              sz = arrNetSize a
              subarrayAt i = shapedArrFromList shape' . map (arrIndex a) $ indicesAt i
              indicesAt i =  map (\is -> take (ax - _iO) is ++ [i] ++ drop (ax - _iO) is) $ map (calcIndex) [0..(sz `div` n - 1)]
              indexMod = tail . scanr (*) 1 $ shape'
              calcIndex i = map (\(e, m) -> i `div` m `mod` e) $ zip shape' indexMod
              _iO = 1 -- axis supplied is with respect to _iO = 1, not actual ⎕IO

alongRank :: Int -> Array -> Array
alongRank r a
    | foldr (*) 1 (shape a) == 0 = zilde
    | n <= 0 = listToArr [ScalarArr a]
    | n >= (length $ shape a) = a
    | otherwise = shapedArrFromList outerShape . map (ScalarArr . shapedArrFromList innerShape) . groupsOf groupSz . arrToList $ a
        where outerShape = take n $ shape a
              innerShape = drop n $ shape a
              n = if r >= 0 then (length $ shape a) - r else -1 * r
              groupSz = foldr (*) 1 innerShape

arrReorderAxes :: [Int] -> Array -> Array
arrReorderAxes targetIdxs a
    | length targetIdxs /= (length $ shape a) = undefined
    | otherwise = shapedArrFromList shape' vals'
        where shape' = map (foldr min intMax . map snd) . groupBy (on (==) fst) . sortBy (on compare fst) $ zip targetIdxs (shape a)
              n = foldr (*) 1 shape'
              vals' = map ((a`arrIndex`) . calcIndex) [0..(n - 1)]
              calcIndex i = map ((idxList!!) . (+(-1))) targetIdxs
                  where idxList = calcIndex' i
              calcIndex' i = map (\(e, m) -> i `div` m `mod` e) $ zip shape' indexMod
              indexMod = tail . scanr (*) 1 $ shape'

The details of the implementation doesn’t matter so much as the fact that these functions only do two main things:

1. Index arithmetic
2. Manipulation of shapes (array dimensions)

That’s all it takes to work with multi-dimensional arrays.

Mimicking Dyalog

Dyalog APL is the de-facto modern implementation of APL. This project is heavily based off of Dyalog APL. All of the syntax and glyphs come directly from Dyalog, and the behavior of the functions and operators was almost entirely taken/tweaked from the Dyalog Reference Guide.

This was convenient in many ways, because it provided an oracle to test against^{, and at any point when I was uncertain of the behavior of something, it gave me a definitive answer, or at least a model which I could analyze to come to my own answer.}

However, attempting to clone Dyalog made the project harder in a lot of ways, namely

• Getting printing of arrays, function trees, and (high-precision, scientific-notation, floating-point) numbers to exactly match Dyalog
• Trying to match Dyalog’s behavior in weird edge-cases
• The sheer generality of many of the glyphs (catenate (above) is a good example of this)

I ended up making a lot of compromises between what I thought was doable (or even possible: some behavior of Dyalog was seemingly incomprehensible), what seemed the most simple^{, and what Dyalog did.}

The following is a (far from complete) laundry-list of discrepancies between my interpreter and Dyalog’s.

• Differing properties:
  • Amount of whitespace when printing arrays with non-zero rank, but with 0 ∊ shape
  • Whitespace and some number formatting when printing matrices of real-numbers
  • Printing format of arrays as leaves of function trees
  • Printing format of arrays as axis specifications
  • Printing of dfns/dops (∇)
  • Exact rules for sorting order
  • Propigation rules for function properties (i.e. identity, ability to select, axis specification) on derived functions
  • Fine-grained behavior of execute (⍎) and format (⍕)
• In Dyalog, …
  • Variables have nameclasses and weird behavior after reassignment
  • Some dops can’t be used inline
  • Dyadic operators can’t be in the right-hand-side of assignments
  • The default ⍺ can be a function in dops
• In my interpreter, …
  • Dops/dfns are not strongly short-circuited: if the condition in a guard is false, the rhs isn’t evaluated, but it is still parsed (in Dyalog, it isn’t parsed)
  • Scalars are not 0-rank: they are vectors with a single element (this approach seems more simple^{, but it causes some incompatibilities in the behavior of certain functions)}
  • Arrays with non-1 rank cannot have zero as an element in their shape (Dyalog allows this)
  • LCM, GCD, factorial, and binomial only work on integers (Dyalog allows reals and complex numbers)
  • The circle function (dyadic ○) only supports 1 2 3, ¯1, ¯2, ¯3
  • Dfns cannot modify global variables
  • ⎕IO can be any integer (not just 0 or 1)
  • Axis spec operator is more limited (several functions don’t support it (e.g. ⊂)), it also only takes singleton numbers, never vectors
  • Dyadic ⍒/⍋ is limited to vector (not higher-dimensional array) collation sequences
  • Reduce can’t take a negative or zero argument on left (window)
  • Encode only works on integers
• My interpreter does not support …
  • Complex numbers
  • Dyadic thorn (⍎) and dyadic hydrant (⍕)
  • &, ⌸, ⌺, and ⌹
  • Monadic squad (⌷)
  • I-Beam (⌶)
  • Traditional Functions
  • Array prototypes, fill elements other than 0
  • Many System Names
  • Many other Dyalog features

Haskell: the Good and the Ugly

The Good

The Compiler

I am generally a fan of the guarantees the compiler gives, and the Haskell complier has given me more guarantees ^{than any other I have used. The time I spent debugging runtime errors in Haskell was significantly smaller in proportion to imperative languages, and there were many times where I was astonished that my code worked after I fixed the compilation errors.}

That being said, runtime errors still happened, and many of them had similar nature to those in other languages (typically logic errors, or panics). Such errors grew more common and more difficult to debug as the project grew in scale^.

It was also relatively difficult to get code to compile (and writing code in general) (in comparison to in other languages). It’s hard to tell how much of this has to do with the fact that I’m new to Haskell, and how much easier it will become over time. It’s hard to gage my progress over the course of project, because the nature of the problems I’m solving (and their complexity) has fluctuated a lot. I’ve certainly become more fluent in Haskell, but I’ve continued to battle compilation errors.

The Libraries

The standard libraries have a lot of useful functions. I made frequent use of Data.List, Control.Monad, and Data.Function, among others.

Most simple operations you might want to do are often well within reach, and it’s a lot of fun using standard functions to replace boilerplate.

Currying, Combinators, Tacit

I probably used these way too much, but they’re a lot of fun.

The Ugly

The Elephant In The Room

Haskell is incomprehensible if you haven’t spent time with it (or languages like it). Functional style alone is probably a big enough gap from imperative to make it difficult^{, but combine that with all the category theory and crazy type stuff, and the learning curve becomes a cliff.}

I’m not suggesting that Haskell should be watered down – I see the utility in its more esoteric style – but this doesn’t change the fact that it makes communication (one of the most important aspects of programming) difficult in many situations.

Over-Generalization

Perhaps this is a contradiction (you can’t have your cake and eat it), since I just raved about the benefits of generality, but I found that it goes both ways: generality can be bad in excess.

My best example of this is the System.Random (and System.Random.Stateful) library: even after I felt like I had a solid grasp on monads and monad transformers, it took me several hours (and even reading some of the source) to comprehend the library ^{enough to feel comfortable using it.}

Efficiency

This goes without saying. Apparently Haskell’s performance isn’t that bad, but I don’t plan on using Haskell for anything that is remotely performance-sensitive.

Trying to optimize Haskell code does sound like an interesting problem, but it might be a lost cause.

Laziness

Generally it doesn’t matter when values are evaluated, so long as you have them when you need them, but since I made excess use of exceptions and undefined’s in this program, understanding laziness became important.

It’s funny how, when using Haskell, laziness creeps into your program where you don’t expect it.

After implementing assignment, it took me a while to realize that, if the RHS of an expression threw an error when evaluated, that error wouldn’t show itself until I tried to print the variable to which the value was given. For example:

    x ← 1 + 'c' ⍝ this statement succeeds
    1 + 2       ⍝ execution continues as normal
3
    y ← x + 1   ⍝ this is fine as well
    y           ⍝ x is only evaluated when the concrete value of y is needed for printing
DOMAIN ERROR: expected number

Funnily enough, I thought I fixed this, but after running this example, the current version of the interpreter produces the same result.

Laziness can be convenient when you want to avoid throwing errors unless absolutely necessary (which is usually the case), but when you want to deliberately throw an error, you must force execution into a single path towards that error.

This uncertainty of time of evaluation also makes catching errors difficult, because calling catch on the function that throws the error will not necessarily catch that error. Catch must be called on the function that forces evaluation on that error. This is something that is hard to trace, and something that types don’t help much with.

The solution to this is probably to use monads instead of exceptions.

Debugging

Haskell’s lazy evaluation also makes debugging much harder. Evaluation is not linear: stepping doesn’t go line-by-line: it jumps around between functions as their values are needed.

GHCi does have a built-in debugger (which is pretty impressive), but for this reason, it’s not really the most useful.

As I mentioned earlier, runtime errors are much less prevalent due to strict typing, but when they do arise, this could become an issue.