5 ms·

I don't think there are any LLVM APL compilers or I would definitely look. I think both Dyalog, J, and K use regular C as the VM. Arthur Whitney is said to have

I don't think there are any LLVM APL compilers or I would definitely look. I think both Dyalog, J, and K use regular C as the VM. Arthur Whitney is said to have written the first K compiler in only a few (like 3-5) pages of C. Do you think it'd be easier to start with using a custom C VM over LLVM? I have a little C experience and no LLVM, but I see it being used for a lot these days (Julia, D, Rust, Swift, Crystal...etc).

i_don_t_know 9y ago
I think APL/J/K are typically implemented as interpreters rather than compilers, because the languages contain some ambiguity that you might not always be able to resolve statically. See for example: http://t3x.org/klong/ambiguity.html http://t3x.org/klong/ambiguity.html The J Incunabulum provides a glimpse of a toy interpreter and of Arthur Whitney's style: http://code.jsoftware.com/wiki/Essays/Incunabulum http://code.jsoftware.com/wiki/Essays/Incunabulum I've found it quite interesting in terms of data structures, parsing, evaluation and how the primitives are implemented. I reformatted it into a more readable style (more readable to me). Memory management is through reference counting I think (maybe not in this example, but I vaguely remember reading that somewhere). Interpreters for array languages are quite efficient because the primitives operate on arrays and you tend to not have explicit loops in the scripts themselves. The loops are "hidden" inside the optimized primitives in the interpreter. You can add further optimizations by recognizing certain idioms like +/ for "sum" and providing a special optimized implementation. Obviously that doesn't work for user-defined functions. I don't know if K etc can optimize those as well. Another thing to consider is how you represent intermediate values. If you're operating on large arrays, you don't want to create a lot of large intermediate arrays that you'll throw away immediately. You can probably detect situations where you can modify arrays in-place. This papers provides as different solution: http://dl.acm.org/citation.cfm?id=512761 http://dl.acm.org/citation.cfm?id=512761 Unfortunately I don't know if there's a free copy available anywhere, so I haven't actually read the paper. I'd be interested to know if there's a free legal copy available somewhere. It might be similar to stream fusion for lists in Haskell: http://fun.cs.tufts.edu/stream-fusion.pdf http://fun.cs.tufts.edu/stream-fusion.pdf Or how you might optimize SQL/relational queries for databases by pushing down projections through selects and joins to reduce the amount of data that you need to retrieve and work on. These approaches might also allow you to optimize user-defined functions. Finally, Timothy Budd implemented a compiler for a slightly modified version of APL and documented the result: http://www.springer.com/de/book/9780387966434 http://www.springer.com/de/book/9780387966434 Again, I don't know if there's a free legal PDF anywhere, so I haven't read the book. I'd be interested in a free legal copy of this book as well.
- throwaway7645 9y ago
  I knew there had to be some kind of catch to not see some form of successful compiler in the wild. Your comment was quite helpful!
mhh__ 9y ago
Are you implying writing one's own JIT? This would involve either writing a new LLVM backend or implementing the same optimizations. Easier to start with, yes: This doesn't really justify the design decision. (In short: Easier != Better) You could compile to C, then use Clang or GCC to compile to a final executable: This should, if possible, be avoided as it limits what you can (C is not a good IR for a compiler). I suspect this is what you meant by "use regular C as the VM". As these things go, LLVM is fairly sane/clean. The point of using LLVM would be to produce an optimized executable, rather than bytecode to be run on a VM. Also, LLVM is C++ (Complex C++, in fact). If you don't already, I thoroughly recommend reading about optimizing compilers work (It's either very useful or fascinating, depending on whether you're the kind of person to find this stuff interesting). Using LLVM is, after getting over the C++ build times, actually quite simple (Take a look at http://llvm.org/docs/tutorial/ http://llvm.org/docs/tutorial/)
- throwaway7645 9y ago
  Thanks for the explanations and advice. APL isn't as fast as I'd like, so I thought LLVM would be nice, but then you lose REPL functionality I believe which is vital for this kind of language. Julia JITs every expression to LLVM (I think)which is how it has a REPL, so that seems like a good choice to get said REPL. So maybe just the Julia route would be smart. It appears to be taking off in the areas that APL, J, Matlab, Numpy, Octave, Mathematica have typically reigned supreme in.
  - mhh__ 9y ago
    If the compiler is fast enough, then one could make a REPL out of it (by modifying it slightly). LLVM also has interpreters. The trick would be finding a consistent way of representing high level state in the REPL (You can't just lob bits of LLVM IR together), unless you can manage without (of course).

i_don_t_know 9y ago

I think APL/J/K are typically implemented as interpreters rather than compilers, because the languages contain some ambiguity that you might not always be able to resolve statically. See for example: http://t3x.org/klong/ambiguity.html http://t3x.org/klong/ambiguity.html The J Incunabulum provides a glimpse of a toy interpreter and of Arthur Whitney's style: http://code.jsoftware.com/wiki/Essays/Incunabulum http://code.jsoftware.com/wiki/Essays/Incunabulum I've found it quite interesting in terms of data structures, parsing, evaluation and how the primitives are implemented. I reformatted it into a more readable style (more readable to me). Memory management is through reference counting I think (maybe not in this example, but I vaguely remember reading that somewhere). Interpreters for array languages are quite efficient because the primitives operate on arrays and you tend to not have explicit loops in the scripts themselves. The loops are "hidden" inside the optimized primitives in the interpreter. You can add further optimizations by recognizing certain idioms like +/ for "sum" and providing a special optimized implementation. Obviously that doesn't work for user-defined functions. I don't know if K etc can optimize those as well. Another thing to consider is how you represent intermediate values. If you're operating on large arrays, you don't want to create a lot of large intermediate arrays that you'll throw away immediately. You can probably detect situations where you can modify arrays in-place. This papers provides as different solution: http://dl.acm.org/citation.cfm?id=512761 http://dl.acm.org/citation.cfm?id=512761 Unfortunately I don't know if there's a free copy available anywhere, so I haven't actually read the paper. I'd be interested to know if there's a free legal copy available somewhere. It might be similar to stream fusion for lists in Haskell: http://fun.cs.tufts.edu/stream-fusion.pdf http://fun.cs.tufts.edu/stream-fusion.pdf Or how you might optimize SQL/relational queries for databases by pushing down projections through selects and joins to reduce the amount of data that you need to retrieve and work on. These approaches might also allow you to optimize user-defined functions. Finally, Timothy Budd implemented a compiler for a slightly modified version of APL and documented the result: http://www.springer.com/de/book/9780387966434 http://www.springer.com/de/book/9780387966434 Again, I don't know if there's a free legal PDF anywhere, so I haven't read the book. I'd be interested in a free legal copy of this book as well.

throwaway7645 9y ago
I knew there had to be some kind of catch to not see some form of successful compiler in the wild. Your comment was quite helpful!

mhh__ 9y ago

Are you implying writing one's own JIT? This would involve either writing a new LLVM backend or implementing the same optimizations. Easier to start with, yes: This doesn't really justify the design decision. (In short: Easier != Better) You could compile to C, then use Clang or GCC to compile to a final executable: This should, if possible, be avoided as it limits what you can (C is not a good IR for a compiler). I suspect this is what you meant by "use regular C as the VM". As these things go, LLVM is fairly sane/clean. The point of using LLVM would be to produce an optimized executable, rather than bytecode to be run on a VM. Also, LLVM is C++ (Complex C++, in fact). If you don't already, I thoroughly recommend reading about optimizing compilers work (It's either very useful or fascinating, depending on whether you're the kind of person to find this stuff interesting). Using LLVM is, after getting over the C++ build times, actually quite simple (Take a look at http://llvm.org/docs/tutorial/ http://llvm.org/docs/tutorial/)

throwaway7645 9y ago
Thanks for the explanations and advice. APL isn't as fast as I'd like, so I thought LLVM would be nice, but then you lose REPL functionality I believe which is vital for this kind of language. Julia JITs every expression to LLVM (I think)which is how it has a REPL, so that seems like a good choice to get said REPL. So maybe just the Julia route would be smart. It appears to be taking off in the areas that APL, J, Matlab, Numpy, Octave, Mathematica have typically reigned supreme in.
- mhh__ 9y ago
  If the compiler is fast enough, then one could make a REPL out of it (by modifying it slightly). LLVM also has interpreters. The trick would be finding a consistent way of representing high level state in the REPL (You can't just lob bits of LLVM IR together), unless you can manage without (of course).