12 ms·
Numpy Clone in Common Lisp
- gumby 7y agoNice work: not a skin over the python one but an actual, optimizable implementation.
- varjag 7y agoI concur, first rate work and good use of the language.
- pmiller2 7y agoI think this is great and interesting, but do CL compilers optimize numerical code anywhere near as well as Fortran compilers?
- gumby 7y agoI would be surprised if so for vector arithmetic given the opportunities for modern FORTRAN to tell the compiler what to do. OTOH the whole point of metasyntactic macrology and the function object abstractions is to permit such things. But modern FORTRAN compilers are very good at what FORTRAN is good for. The MACLISP compiler was as good and in some cases better than its contemporary FORTRAN competition. But FORTRAN tech has moved on since then.
- chunsj 7y agoMaybe this will need C based highly optimized backend as well, however, the code looks very clean and beautiful to me. I hope someday differentiable programming becomes possible in common lisp.
- darkpuma 7y agoBLAS/LAPACK is fortran, not C.
- stephencanon 7y agoBLAS is a set of subroutine interfaces that originated in Fortran, but can be implemented in any language; most mainstream implementations use one or more of Fortran, C, C++, assembly, and DSLs.
- darkpuma 7y agoIt's my impression that common implementations of BLAS have fortran at the core because fortran (moreso than C) lends itself to automatic vectorization.
- gh02t 7y agoThis is partially true (or at least once was, the performance gap is pretty slim nowadays), but most of the high-performance BLAS implementations like OpenBLAS or MKL have their hot path code written in hand-tuned assembler anyway.
- stephencanon 7y agoBLAS inner loops are usually explicitly hand-vectorized, so Fortran’s autovectorization advantages don’t help. I’ve written many BLAS kernels in assembly over the years.
- gnufx 7y agoNot arguing with that, but I think the jury is out on whether they need to be hand vectorized. With recent GCC, generic C for BLIS' DGEMM gives about 2/3 the performance of the hand-coded version on Haswell, and it may be somewhat pessimized by hand-unrolling rather than letting the compiler do it. The remaining difference is thought to be mainly from prefetching, but I haven't verified that. (Details are scattered in the BLIS issue tracker earlier this year.) For information of anyone who doesn't know about performance of level 3 BLAS: It doesn't come just from vectorization, but also cache use with levels of blocking (and prefetch). See the material under https://github.com/flame/blis https://github.com/flame/blis. Other levels -- not matrix-matrix -- are less amenable to fancy optimization, with lower arithmetic density to pit against memory bandwidth, and BLIS mostly hasn't bothered with them, though OpenBLAS has.
- jlarocco 7y agoSBCL is actually really good at optimizing this type of code, and I think it can even do some vectorization. If it's not not good enough, there are a few CL bindings and wrappers around BLAS and LAPACK. A good one is Matlisp, which is available in QuickLisp. http://quickdocs.org/matlisp/ http://quickdocs.org/matlisp/
- fiddlerwoaroof 7y agoSbcl has all the pieces in place for vectorization, but I don’t think anyone has actually hooked them up. However the great thing about lisps is that the compiler and optimizer are written in the language they compile, so an end user can do this sort of thing themselves: https://www.pvk.ca/Blog/2013/06/05/fresh-in-sbcl-1-dot-1-8-sse-intrinsics/ https://www.pvk.ca/Blog/2013/06/05/fresh-in-sbcl-1-dot-1-8-s...
- pjmlp 7y agoOptimizing Lisp compilers are quite good. Current generations tends to be unaware that once upon a time C compilers only generated turtle code, it was the investment into optimizing compilers and abuse of UB that made current compilers able to generate fast code.
- jstimpfle 7y agoAnother C hate post? It seems way overblown. When you compare trivial compilation of C code with optimized compilation, you would see maybe a factor of 5 in difference in code size. On today's machines, I think you can expect to get more than 50% of performance from trivial compilation, compared to optimized code. Depending on workload you it can be 80-90%. (I have a small amount of experience, based on my own very shitty compiler, to back up that claim). Even on machines from "once upon a time", where performance was more directly correlated with code size, it couldn't have been that bad, assuming the factor of 5. And also seeing the fact that C was used for systems development from the start. And that's still ignoring (or at least contradicting) the common lore that "once upon a time", LISP was comparatively more inefficient than C than it is today! And I don't believe that abuse of UB is important to generate fast code. After all, fast code doesn't necessarily contain UB.
- pjmlp 7y agoI have written plenty of them since C vs C++ on comp.lang.c were a thing. Once upon a time Common Lisp compilers were already good enough versus Fortran. https://people.eecs.berkeley.edu/~fateman/papers/lispfloat.pdf https://people.eecs.berkeley.edu/~fateman/papers/lispfloat.p... As for C's performance on the old days, "Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue.... Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels? Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities." -- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
- yarrel 7y agoIt's unlikely to need an optimized C backend :-) - http://www.iaeng.org/IJCS/issues_v32/issue_4/IJCS_32_4_19.pdf http://www.iaeng.org/IJCS/issues_v32/issue_4/IJCS_32_4_19.pd...
- _0ffh 7y agoIt's a bit sad that Lush seems to be kind of dead since YLC has moved on...
- eggy 7y agoI agree. Lush 2 was very promising. On the bright side, now Lisp is back in what seems a good fit of research and practicality.
- jxy 7y agoIBM doing Common Lisp. I wonder what this is actually used for inside IBM.
- Nrsolis 7y agoThis might be a clue: https://developer.ibm.com/recipes/tutorials/watson-iot-with-common-lisp/ https://developer.ibm.com/recipes/tutorials/watson-iot-with-...
- guicho271828 7y agoAuthor here. IBM is currently focusing on the combination of machine learning and reasoning, also called neural-symbolic AI [1], to combine the best of both worlds (noise robustness and explainability, etc.). I am from Tokyo and will join MIT-IBM lab soon to perform this line of research. I have been working on Latplan [AAAI-2018, 2,3,4,5,6], a neural-symbolic classical planning system that learns symbolic representations of noisy images and perform efficient symbolic planning in the latent space. Later, several other groups have started working in this field, like [7]. The problem with python is the lack of sequential execution speed, which is necessary for solving symbolic tasks, e.g. SAT solver, classical planning, theorem prover. At the same time, traditional languages like C++, typically used for writing solvers, are too inflexible to accommodate the workflow in machine learning. For a neural-symbolic task, personally, Lisp is best in this space (I don't try to repeat why, because there are plenty of articles on it.), with Julia being a contender. I am also interested in adding the compile time type/shape checking on the deep learning code, since python debugging is painful (just a personal opinion -- not intending to start a war here). By the way, I made the first prototype of this lib in 3 days, and am working on improving it for 3 month (for other ML projects). [1] https://medium.com/@MITIBMLab/the-shared-history-and-vision-behind-the-mit-ibm-watson-ai-lab-405ce4032013 https://medium.com/@MITIBMLab/the-shared-history-and-vision-... [2] https://github.com/guicho271828/latplan https://github.com/guicho271828/latplan [3] AAAI18 presentation at : https://asai-research-presentation.github.io/2018-2-5-aaai/ https://asai-research-presentation.github.io/2018-2-5-aaai/ [4] AAAI18 paper : Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary, https://arxiv.org/abs/1705.00154 https://arxiv.org/abs/1705.00154 [5] Follow-up papers (ICAPS2019) : https://arxiv.org/abs/1903.11277 https://arxiv.org/abs/1903.11277 [6] Follow-up papers (ICAPS2019), extension to first order logic : https://arxiv.org/abs/1902.08093 https://arxiv.org/abs/1902.08093 [7] Learning Plannable Representations with Causal InfoGAN, https://arxiv.org/abs/1807.09341v1 https://arxiv.org/abs/1807.09341v1
- noobermin 7y agoSympathetic, but as long as lisp requires one to write math as function composition it won't catch on with computational types. Of course, I imagine that sort of thing could be a set of macros away...then that would be awesome, familiar infix mathematical expressions with common lisp in the rest of the code.
- dreamcompiler 7y agoI've been doing serious math with common lisp for 30 years. For me, the convenience of having automatic bignums and complex numbers, n-ary functions, and true rationals means I can think about math rather than about the limits of computers. The prefix notation became a non-issue in about a day.
- dwheeler 7y ago"Prefix notation is a non-issue" is true for a tiny minority of software developers and mathematicians. The world has already spoken: infix is a minimum requirement for the vast majority of people doing math. Bignums, true rationals, and many other constructs are already available in Python. Numpy is too. Most importantly, infix is available in Python. The funny thing is that it's already possible to do infix in Common Lisp. My "readable Lisp" approach has been supporting infix in standard Common Lisp: https://readable.sourceforge.io/ https://readable.sourceforge.io/ It's already available in the QuickLisp libary as "readable". You can then use {1 + 2} with macros, quasiquoting, and so on.
- dtornabene 7y agothe idea that prefix notation is some kind of serious hold up for anyone thats mastered, or is even semi-competent at the kind of mathematics you would use this for is so strange to me. Programming and math are (almost) nothing if not the ability to learn new rules of syntactical manipulation in all kinds of different domains. I say this as some one who is both a lisper and has severe dyslexia. It just seems like a totally made up hangup for a programmer to have. Its also weird to say "the world has spoken" when 60 years ago there were all of three or four non-assembly programming languages, and only 30 years ago prefix was still highly represented in serious industrial and research computing. Things change. Even five years ago doing "functional" programming in javascript was the fringe of the fringe of front end web development.
- agambrahma 7y agoGood to see someone fill in this missing link! Could become a viable competitor to Julia (uniform language stack, as opposed to the Python+C combination currently being widely used).
- longemen3000 7y agoA funny situation, the Julia parser is femtolisp, so in a funny way, Julia is already a kind of numpy in lisp
- ddragon 7y agoI think it's more than a uniform language stack, after all C++ could be considered one as well but most people still use python to interface it as opposed to just using it (at least for exploratory data science). It's a combination of interactivity to experiment, conciseness to stay close to the pseudo-code/math, easy hackability since you need to stay beyond the cutting edge and performance so you're not restricted in what you can do. Common Lisp (as does Clojure and Julia to a lesser extent) has unparalleled interactivity (besides maybe smalltalk), you can make it as concise as you want, ultimate hackability and really good performance. Research (not deployment) is the one area CL could probably surpass every other, but unfortunately it lacked a concentrated effort (by a company or community) in this current AI resurgence (maybe because of the Lisp Curse). Though there will always be other opportunities.
- pmiller2 7y agoFrom the point of view of a numpy user, the stack is 100% Python. You just import it and don’t worry about it.
- zmmmmm 7y agoWonder how it compares to using something like ND4J with Clojure? That would (as I understand it) have the advantage of not sacrificing as much speed.
- fartcannon 7y agoThis is an excellent project. Is there a developer blog? I'd like to try reimplementing numpy I'm various other languages (or part of it, since it seems like it's a huge task).
- enriquto 7y agoYou can re-implement a much better interface that numpy if your purpose is doing math comfortably. Numpy has a wonky interface to ease the transition from matlab/octave (while amazingly producing a much less comfortable system).
- nemoniac 7y agoCould you point to a "much better interface" to numerics?
- taffer 7y agoMaybe something closer to APL: https://curtisautery.appspot.com/5776042744610816 https://curtisautery.appspot.com/5776042744610816
- enriquto 7y agoWell, for one, octave or scilab are perfectly accetable solutions. Or even "julia" if you pressure me. Or fortran, where there is no stupid overhead in "for" loops. Or C. Hell, or even luajit if you do not need fancy stuff. Honestly, python/numpy is possibly the slowest and less convenient way to do math (assuming that you only want to do math, and no need any strings/dictionaries and other useless data structures).
- mkl 7y agoWith the possible exception of Julia (which I don't know), all of those languages have much clunkier and more primitive numerics interfaces. Even just considering array indexing Numpy is more capable, convenient, and comfortable, and Numpy's array-wise maths operations are fast, as they're implemented in C and Fortran.
- sunshinekittie 7y ago@guicho271828 What does it mean to represent something symbolically ??