This blog post details the development of an APL (A Programming Language) interpreter written in Haskell, emphasizing the author's learning journey and the technical challenges encountered. The project showcases APL's compact, array-centric syntax and the shift in mindset required for array programming. The author chose Haskell for its functional paradigm, which, while elegant for parsing, presented difficulties with state management, data structures, and performance.
The interpreter's architecture follows standard interpreter design (lexing, parsing, evaluation). A significant portion is dedicated to the evolution of the parser, from a context-free approach to one incorporating context and leveraging Haskell's monadic and applicative features for conciseness. Evaluation complexities, such as handling functions as first-class data, implementing selective assignment, and operating on higher-dimensional arrays through index arithmetic, are explored. The project aims to mimic Dyalog APL's behavior, leading to challenges in replicating precise syntax, edge cases, and numerical formatting, resulting in a detailed list of discrepancies. Finally, the author reflects on the "good" (compiler guarantees, robust libraries) and "ugly" (steep learning curve, performance, laziness-related debugging difficulties) aspects of programming in Haskell.
Summarizing the APL Interpreter Blog Post:
Why APL?
APL is an array programming language known for its incredibly compact and expressive syntax, using single Unicode symbols for functions and operators.
Learning APL requires a different mindset, encouraging high-level, global operations over low-level recursion, which provides broader programming insights.
Why Haskell?
The project became a deep dive into learning Haskell, which was the hardest aspect.
Haskell was chosen for its elegance in parsing and function combination, despite challenges with state management, data structures, and performance for an array language interpreter.
The interpreter is a learning project, not intended as a replacement for existing ones.
Interpreter Architecture:
Follows a standard interpreter structure: Read input, Lex/Scan, Parse into Syntax Tree, Evaluate, Print result, Repeat.
Maintains and updates an interpreter state (variable name to value mapping).
Parsing Evolution:
The parser was built from scratch, initially using MatchFn (token list to Maybe (a, [Token])).
Version 1 (Context-Free): Used helper functions like matchOne, matchAll, matchMax, matchT2 (for tuples) to combine MatchFns.
Version 2 (+Context): Modified MatchFn to (IdMap, [Token]) -> Maybe (a, [Token]) to handle APL's context-sensitive grammar (variable values). Only terminal match- functions and helpers needed changes.
Version 3 (+Monads): Replaced custom chaining functions (chFst, mchFst) with monadic functions (fmap, >>=, do-notation) by defining MatchFn as a Monad Transformer stack (StateT [Token] (MaybeT (Reader IdMap)) a). This simplified parseDerFn which previously struggled with IdMap access.
Version 4 (+Applicative): Leveraged Applicative Functors (<*>, <*, *>) to further condense the parser code, reducing it by over 100 lines.
Evaluation Nuances:
Functions as Data: APL's natural function composition (e.g., "trains") means functions are stored as primitive Haskell functions (e.g., FuncM, FuncD), not syntax trees, after evaluation.
Practical Typeclasses (SubEvalM): Used a custom typeclass SubEvalM and wrapper functions (mkMonFn, mkDyadFn) to convert constrained monadic functions to the universal EvalM monad, allowing for clearer type definitions while handling impure operations.
Selective Assignment: Implemented by applying selection/permutation functions to an array of indices (⍳⍴x) instead of the data itself, then mapping the result back to the original array.
Higher-Dimensional Arrays: Primitives like catenate are implemented by operating on conceptual "slabs" of arrays through core helper functions (alongAxis, alongRank, arrReorderAxes) that primarily perform index arithmetic and shape manipulation.
Mimicking Dyalog APL:
The project heavily based its syntax and behavior on Dyalog APL, using it as an oracle for testing and behavior definition.
Challenges: Exact matching of printing formats (arrays, function trees, numbers), replicating weird edge cases, and the sheer generality of many APL glyphs (e.g., catenate).
Discrepancies: A detailed list is provided, including differing printing properties, variable nameclasses, operator usage, short-circuiting behavior, scalar representation (vectors with single element vs. 0-rank), array shapes, specific primitive function limitations (LCM, GCD, factorial, circle, encode), axis spec operator limitations, and non-support for complex numbers, I-Beam, traditional functions, and many system names.
Libraries: Standard libraries (Data.List, Control.Monad, Data.Function) are rich and facilitate concise, boilerplate-free code.
Currying, Combinators, Tacit: Found enjoyable and powerful for compact expressions.
The Ugly:
Incomprehensibility: Steep learning curve due to functional style, category theory concepts, and complex type signatures, hindering communication.
Over-Generalization: Can lead to overly complex library interfaces (e.g., System.Random), even for seemingly simple tasks.
Efficiency: Concerns about performance, noting potential optimization as a "lost cause" without deeper understanding.
Laziness: Creates uncertainty in evaluation timing, making error handling and debugging challenging, as errors appear only when values are forced (e.g., for printing), and catch must be on the forcing function.
The Hacker News discussion around the APL interpreter in Haskell covers various aspects of both languages, programming paradigms, and community interactions.
APL Styles and Innovation:
Commenters highlight the diverse programming styles possible in APL, beyond the point-free functional style demonstrated in the blog post, including pointed declarative, imperative, object-oriented, and data-parallel approaches.
APL is praised as an underrated language innovator, particularly for its coexisting lexical and dynamic scope.
Haskell Challenges and Optimizations:
The author's observation on difficulties with imprecise exceptions and lazy evaluation is discussed, with clarification that synchronous exceptions cannot be thrown by pure Haskell code.
Debate arises regarding the author's performance remarks, with some pointing out common beginner mistakes (e.g., foldl causing space leaks, inappropriate use of foldr with lists) that can impact Haskell's performance. Suggestions for better alternatives like foldl' and specific Array/Vector types are provided.
One user calls out a "toxic" community attitude regarding beginner mistakes, while another defends against "FUD" (Fear, Uncertainty, Doubt) spreading by inexperienced users.
APL Implementation and Readability:
A request for a "readable" C implementation of an APL-like language (~1000 LoC) prompts discussion about the inherent complexity of APL's core primitives compared to simpler languages like LISP or FORTH.
Some suggest that APL's focus on conciseness and a rich primitive set means a truly "minimal" and "useful" C implementation is difficult, but point to existing K (a related array language) implementations like ksimple (Arthur Whitney's) and ngn/k (partially expanded C source) as examples, though their readability is debated.
BQN, a modern array language, is mentioned as a good candidate for minimal VMs due to its self-hosted primitives and compiler.
Learning APL and High-Level Logic:
A significant pain point for APL learners is identified: how to apply APL for high-level application logic beyond basic tutorials and puzzles.
Suggestions include organizing application state as "global database of inverted tables" and normalizing them for concise APL expressions carrying domain semantics.
Discussion connects APL's matrix operations and boolean logic to parallelizable, cache-friendly queries, contrasting with more linear approaches in other languages.
Haskell Onboarding and Tooling:
Newcomers to Haskell struggle with installation and build/package systems (Stack vs. Cabal), with ghcup and cabal init/run/repl recommended as modern solutions.
Resources like exercism.org, Brent Yorgey's course, "Haskell Programming from First Principles" book, and typeclasses.com/phrasebook are suggested for learning.