Fast Arcsine in Apple
One can improve on arcsine's performance with Horner's method and then bittwiddling.
blog
Latest posts
Doubly-linked Lists in Haskell
Allison (1989) gives an example of tying the knot to build an immutable, doubly-linked list from a list. However, this does not support the usual insertion and deletion.
Python Is Truly Dynamically Typed
Robert Harper points out that dynamically typed languages are a subset of statically typed languages. To wit, we could handle J values in Haskell with something like:
Array Offsets from Indices Are Multibase Digits
J's #: (base) can be used to compute the offset of an array element as it would appear in memory. Why so? x #: y is +/w*y , where w is formed as */\.}.x,1 — w is precisely the strides of an array with dimensions x .
Universally Quantified Types Are Not Templates
Variable types (à la System F) are not templates, though one can think of them as type schemata. A template
Performance of Sharing
After paraphrasing a computation I had found in a paper , I realized I had ruined its performance.
Matching R's Performance Takes Nothing Special
Apple outperforms R in important cases.
A Proper X86 Assembler in Haskell Using the Escardó-Oliva Functional
Writing an assembler turns out to be an interesting example: one needs to calculate distances between jumps and their target labels, and the target may appear after the label. It turns out that one can write a one-pass assembler using the tardis monad or in Curry , using logic programming.
Strides Are Scans
For an array with dimensions \(n_1,n_2,\ldots n_r\) stored in column-major order, an element with indices \(a_1,a_2,\ldots a_n\) is located at offset
QuickCheck With Shape Types
One motivation for Apple was demonstrating typed array programming. Shape types are rich; we can use types as witnesses as in QuickCheck , generating test cases that are shape-correct.
Softmax in Apple As an Example of Explicit Rank
Consider a softmax layer from Aditya Srinivas Menon's tutorial :
Optimizing Array Code With Inferred Type Information
Apple , being a JIT compiler with shape types, is able to do a number of optimizations based on inferred dimension (and rank). Rank is almost always known in practice, so such optimizations are pertinent.
Lessons from Writing an Array Compiler II
I just finished adding another mid-end to my Apple JIT compiler, motivated to get rank facilities right . However, there remain significant shortfalls.
Extracting Compiler Version from Compiled Binaries Using Jacinda
Compilers and linkers put their own version information in ELF binaries; we can inspect with readelf on the .comment section, to wit:
Three Languages
One PL nihilism is "all languages are the same." This is not so—general-purpose languages have converged on procedures, but languages that differ nontrivially are used in computing.
Better Vim Tags With Jacinda
Universal ctags points the cursor to line numbers rather than the actual definition (as language servers do). Vim uses ex ( :h Ex-mode ) commands as destinations . We want to generate call cursor(line,col) for each identifier.
Laziness, A.k.a. Computer Science
An established problem in functional programming is the question of evaluation order (see Hudak , §2.2). Haskell offers seq ; which allows the programmer to magically introduce dependencies in evaluation order and thence subvert lazy evaluation. Sometimes this is necessary; see the foldl foldl' example .
Unix As an IDE II
nm shows symbols defined in an executable. GHC includes library name in symbols, so we can use this to inspect libraries that make it into the compiled binary. GHC uses z-encoding so we pipe the output of nm into an ad-hoc invocation of sed , viz.
The Unix Command-line As an IDE
GHC embeds linker flags into the final ELF binary:
Utility of AWK
I turned to my own Jacinda to view the output of otool and was pleasantly surprised.
Sed Examples in Jacinda
The GNU sed manual offers the following to join backslash-continued lines:
Num Instances for ASTs
One can define a Num instance in Haskell for ASTs of expressions, viz.
Linear Types for Manipulating Expressions in the Lambda Calculus
If we wish to preserve global uniqueness of names during \(\beta\)-reduction, we have to \(\alpha\)-rename before each substitution. Consider:
Linear Effects Handling
Haskell puts all side effects in the IO monad, which passes around the RealWorld . This is unsatisfactory for a number of reasons, and Haskellers have spilled much ink on effects systems . As I recently noted , there are distinctions in how one handles effects at the logical level: in particular, randomness is different from array writes.
C Converges to Intuitionistic Logic
C has a reputation for being a "hacker" language, in contrast to say Haskell, which is abstract with ties to logic and category theory. There is even the quip "C is a portable assembler".
Logic Programming Doesn't Work in the Real World
Logic programming fails for many reasons; interestingly it fails to integrate with imperative programming or export its constructs. Haskell's monadic I/O—explicitly passing a RealWorld —offers a nice demonstration.
Egison's Pattern-matching via Logic Programming
Egison advocates a pattern-match oriented style of programming and offers poker hands as an example:
Lessons from Writing an Array Language Compiler
My Apple compiler started as an experiment in what I would implement as compiler for an array system. Several parts did not pan out so I offer my warnings and advice to other array language implementers.
Compiling Functions to Jumps
Functions are compiled to machine by a convention of jumps and registers; one calls a function by jumping to its location in memory. These jumps are relative and particular functions (say, malloc ) may be loaded at different memory locations, so the machine code for a function cannot be pinned down and in fact is contingent on every function that it calls.
Basic Blocks À La Appel
Building a respectable compiler requires basic blocks in order for liveness analysis to be performant. Consider my own Apple compiler :
Elliptic Fourier Series in Apple
I previously wrote about typing elliptic fourier series ; my Apple compiler is now capable of computing the offsets and also the relevant coefficients.
Rosetta
To compute a 7-day moving average:
Follow-up: Typed Elliptic Fourier Series
As I wrote about previously I am working on a typed array language with the case of elliptic Fourier series as an example.
Infelicities With Traditional Compiler Architecture on X86
Compilers are written as a pipeline: in particular, instruction selection and register allocation are different phases. GHC , for instance, uses maximal munch for instruction selection and a variety of register allocators. However, on x86-64 (for instance), register allocation constrains the particular instruction encodings, which affects the cost of some instructions.
Calling System Functions in a JIT
Writing a practical JIT is somewhat complicated and in fact depends on the assembler; here I present a full example in Haskell. Notably this JIT/assembler is capable of calling procedures in system libraries (i.e. malloc , free )
Row Types in Haskell
"Typing Haskell in Haskell" makes the implementation of type systems concrete for programmers; recent developments in type theory have much to offer but are not developed to this depth even in theory. Row types are particularly juicy because one does not lose type inference ; we can use the exact same unification approach and need not resort to ordered contexts or focalization.
Typing APL: Elliptic Fourier Series As an Example
Elliptic Fourier series are a good example to kick the tires on array programming systems; J and Python , however, are both dynamically typed.
APL Is Truly Different
APL is truly different from other languages; nearly every language uses lexical scoping to express composition. Both GHC Haskell and GCC/Clang use a stack for variables across procedures because it models how variables become available (FIFO). Putatively different languages are constrained by the same fundamentals.
Imitating Cloc With Jacinda
Jacinda can imitate cloc by combining it with other command-line tools on the Unix command-line, viz.
Names in Haskell Compilers
One common oversight in Haskell compilers is failing to intern identifiers using Int s and failing to prefer IntMap s and IntSet s. The PureScript compiler , for instance, uses Map s as of writing.
Finding Cruft in Patches With Jacinda
Suppose we want to clean up all TODO s in a branch before merging. We can check for TODO s introduced with
Generating Other-extensions for Cabal Files
One would like to be able to find all language extensions in a given Haskell project in order to populate the other-extensions field of the .cabal file ( cabal-install uses this for dependency resolution).
Transparent Programming
J and APL support (and encourage) a certain form of programming without error handling or library code reuse. The alternative wisdom goes against typical programming but it works together.
Awk, Mawk, Gawk Performance
Suppose one would like to process compiler output to include span ; vim uses awk ( mve.awk ) to do this.
Deduplication on the Command Line
I am in the process of adding a deduplication builtin to my [Jacinda](https: //hackage.haskell.org/package/jacinda) language. It's something I've wanted often enough and evidently part of the reason people use awk (it is the way to deduplicate on the command line without changing order).
Generating Vim Tags With Jacinda
One can use Jacinda to generate tags files for vim. This amounts to string processing with regular expressions, which we can do in a functional style, skirting Universal Ctags .
Unix Meets APL
Suppose we wish to inspect our PATH . Then we can make it more readable using awk :
Processing Compiler Errors in Jacinda
GHC includes span information in compiler errors, but not in a format suitable for vim:
The !-modality Is a Comonad
The !-modality is a comonad . In particular, it is a functor; we can lift any function/procedure to work on perennial types with map , \( A \multimap B \vdash !A \multimap !B \).
Linting for Concatenative Programming
Concatenative languages lend themselves to rewriting because they do not bind variables and thus do not incur any confusion with renaming/scope (compositional rather than applicative).