12 ms·
Not Lisp again (2009)
- auggierose 6y agoEvery few years I see this great story popping up. I love it! A lot of things seem complicated, but are not, if you just approach it the right way, and if you don't get bogged down in up-front technical optimisations which you feel are necessary, but might not be.
- caslon 6y agoPast threads in reverse-chronological order: https://news.ycombinator.com/item?id=18308721 https://news.ycombinator.com/item?id=18308721 (236 comments) https://news.ycombinator.com/item?id=14247269 https://news.ycombinator.com/item?id=14247269 (263 comments) https://news.ycombinator.com/item?id=504667 https://news.ycombinator.com/item?id=504667 (39 comments)
- lisper 6y agoA lisp interpreter including lexical closures and a parser in 114 lines of Python code: http://flownet.com/ron/lisp/l.py http://flownet.com/ron/lisp/l.py
- etaioinshrdlu 6y agoI feel like this is a lot less impressive nowadays that first-class functions are common. It might as well be Python: dx = .0001 def deriv(f): def f_prime(x): return (f(x+dx) - f(x)) / dx return f_prime
- vitus 6y agoPython does not do tail recursion, though! def f(n): if n <= 0: return n return f(n-1) f(1000) will blow out your stack. Meanwhile, scheme@(guile-user)> (define (f n) (if (<= n 0) n (f (- n 1)))) scheme@(guile-user)> (f 1000000) $1 = 0 Also bear in mind that this was lesson 1 of an intro programming course that culminates in writing a Scheme interpreter in Scheme. There's something to be said about the simplicity / consistency of a language's syntax such that a first-year undergrad can implement it.
- taeric 6y agoThe truly mind blowing one, to me, is it is one of the first handful of lessons that they go over symbolic derivatives.
- spekcular 6y agoBut this is not symbolic differentiation, it's numerical differentiation. A true symbolic integrator would not give 48.00120000993502 when asked for the value of 3x^2 at 4. This kind of approximation exercise is given to calculus students all the time ("Use the definition of derivative to approximate the derivative of f(x) at 3 by taking dx=.001," etc.). edit: I misread! See reply below.
- taeric 6y agoRight, I was referencing later lessons. Section 2.3 of the book. Surprisingly early. Granted Knuth's work also did symbolic rather early. A bit harder to work with in his. Edit: To be fair, I could have worded that first post more clearly! :D
- simias 6y agoI must admit that I never understood what these particular examples had to do with Lisp being such a great programing language given that you can implement exactly the same logic in basically any programing language, including for instance C (although you'd have to cheat a bit for the `deriv` function, admittedly): #include <stdio.h> #define DX 0.0001 #define DERIV(_f) float deriv_##_f(float x) { return (_f(x + DX) - _f(x)) / DX; } float cube(float x) { return x * x * x; } DERIV(cube) int main(void) { printf("%f\n", deriv_cube(2)); printf("%f\n", deriv_cube(3)); printf("%f\n", deriv_cube(4)); } Any language supporting closures or generics could get rid of the unsexy DERIV macro. What sets Lisp apart is its "code as data" approach which lets the coder write incredibly powerful macro (and also incredibly hard to understand code). The rest can easily be emulated in other languages. I do like this naive approach mind you, there's a certain Zen to be found reimplementing these mathematical concepts from first principles, I just really fail to see what makes Lisp so remarkable in this context.
- Turing_Machine 6y agoWell, the major difference here is that your C method requires that all this stuff be defined at compile time, while the Scheme deriv works with even functions that are dynamically defined at run time, anonymous functions, etc. I'm not sure how you would do that in C, other than by Greenspunning up an implementation of first-class functions.
- xirbeosbwo1234 6y agoYou can get most of the way there with function pointers. float deriv(float (*f)(float), float x) { return (f(x + DX) - f(x)) / dx; } I can't think of a way to make a deriv function that returns the derivative, only one that returns the derivative at one particular point.
- whatshisface 6y agoIn C you would normally do this with functions that accepted function pointers, not a #define.
- 6y ago
- yudlejoza 6y ago- I don't get lisp's (lisp-2) dynamic scoping (a big reason I haven't switched from vim to emacs). I'm much more comfortable with the lexical scoping of scheme (lisp-1). - I don't get big schemes (like R6RS). For a while, I thought of my own implementation of R5RS. But I've heard R7RS is pretty much R5RS with improvements. So R7RS it is. - But I'd like to have macros. I wonder if R7RS has macros. - Mainly interested in crazy metaprogramming and logic/relational experiments using Friedman/Byrd school of thought (reasoned schemer, minikanren, constraint kanren, that sort of stuff). - Finally instead of rolling my own from scratch, I've heard I could use something like chibi as a starting point (additional points since chibi is implemented in C). Comments?
- dustingetz 6y agoDynamic scope in Clojure is a key way to model supervised local side effects (side reads and side mutations) in a tightly controlled way while ensuring that the expression as a whole remains referentially transparent and the effect behaviors are late bound. If you are into crazy metaprogramming, this is pretty important imo. The only other way to model effects that I know of is monads which involve lots of opaque closures, which block metaprogramming. Code-as-data captures a lot of static information about your program which monads lose.
- yudlejoza 6y agoI have very little interest in the ML family (well, let's just say that my interest in ML is in a different part of my brain that I don't want interfering with my thinking/exploration about systems like lisp/scheme and what kind of metaprogramming can be done with them). I guess I'll have to think about dynamic-scoping a little more.
- gugagore 6y agoIs an "opaque closure" a kind of closure, or do you mean that the alternative to using closures is less opaque?
- dustingetz 6y ago
- FeepingCreature 6y agoYeah but none of those are inherent advantages of Lisp... I really don't get this sort of "Lisp is cool" article touting advantages the Author was impressed by during their childhood that have long since been overtaken by technical advancements in other languages.
- caslon 6y agoThe author was an adult when he was impressed by this. Note that he was taking one of the most critically-acclaimed courses at MIT.
- FeepingCreature 6y agoRight, but that really doesn't address my point.
- iainctduncan 6y agoExcept in most of the other languages, it just comes out so FUGLY. I have done metaclass hacking in Python, and you can do it sure, you can make it do some cool stuff even. But ugh, it burns the eyeballs to implement. Manipulating the AST is just so elegant in Scheme compared to anything else I've seen.
- FeepingCreature 6y agoI'll give you directly rewriting the source tree as a list, that is pretty cool. But about 70% of the coolness of macros can in principle be done in a C-like. (I'm doing it!) It just comes out a bit ugly cause C-like parse trees are inherently ugly, imo, cause the language imposes a more diverse structure. Pattern matching would probably help a ton for destructuring - being able to take "$a + $b" and decompose "2 + 3" into "a=2, b=3", but that's kind of difficult. There's ways you could do it cleanly, like imposing a very predictable structure on your AST nodes, but they end up sort of reinventing Lisp through the backdoor. Luckily you don't need that for most macros, afaict.
- 6y ago
- augusto-moura 6y agoThe class mentioned in the article was actually made available under Creative Commons by the MIT OpenCourseWare[1], you can see the entirely of the course in Youtube. I watched and cannot recommend it enough, even for seasoned programmers [1]: https://www.youtube.com/watch?v=-J_xL4IGhJA&list=PLE18841CABEA24090 https://www.youtube.com/watch?v=-J_xL4IGhJA&list=PLE18841CAB...
- caslon 6y agoIt's also a freely-available book from MIT: https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book.html https://mitpress.mit.edu/sites/default/files/sicp/full-text/... Texinfo version (recommended) and pretty PDF version: https://github.com/sarabander/sicp-pdf https://github.com/sarabander/sicp-pdf
- xxyzz 6y agoYou can run all the code from the book and do all the exercises in Racket(https://racket-lang.org https://racket-lang.org) with minimal modification.
- caslon 6y agoOr, ideally, use mit-scheme, and have zero modification.
- xxyzz 6y agoBut drracket is more easier to use.
- caslon 6y agoNo, not really. $ mit-scheme MIT/GNU Scheme running under GNU/Linux Type `^C' (control-C) followed by `H' to obtain information about interrupts. Copyright (C) 2014 Massachusetts Institute of Technology This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Image saved on Friday January 4, 2019 at 11:17:34 PM Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116 1 ]=>
- EdwardCoffin 6y agoPeople who like this might also like Is Scheme Faster than C by Jonathen Sobel [1] [1] https://web.archive.org/web/20100310163003/https://www.cs.indiana.edu/%7Ejsobel/c455-c511.updated.txt https://web.archive.org/web/20100310163003/https://www.cs.in...
- DNied 6y agoThe syntax of those defines sure looks weird. In what dialect does the name of the function being defined appear as the CAR of a list, followed by the parameters?
- harry8 6y agoIt's a lovely blog series, worth delving into other bits and pieces. This one is particularly relevant. Tail-call optimsiation _not_ implemented and why. Usually the sort of thing that is not mentioned when celebrating all the good fun of lisp. https://funcall.blogspot.com/2009/04/lmi-flashback.html https://funcall.blogspot.com/2009/04/lmi-flashback.html
- ph2082 6y agoThe first version of factorial in SBCL takes less time and processor cycle, CL-USER> (time (fact 5)) Evaluation took: 0.000 seconds of real time 0.000002 seconds of total run time (0.000001 user, 0.000001 system) 100.00% CPU 1,550 processor cycles 0 bytes consed 120 compared to second version of factorial CL-USER> (time (fact2 5)) Evaluation took: 0.000 seconds of real time 0.000027 seconds of total run time (0.000027 user, 0.000000 system) 100.00% CPU 64,240 processor cycles 0 bytes consed 120 How it works for other lisp implementation. However when I reach for bigger number things looks different. CL-USER> (time (fact 10000)) Evaluation took: 0.044 seconds of real time 0.045335 seconds of total run time (0.036745 user, 0.008590 system) [ Run times consist of 0.021 seconds GC time, and 0.025 seconds non-GC time. ] 102.27% CPU 111,336,538 processor cycles 69,739,552 bytes consed CL-USER> (time (fact2 10000)) Evaluation took: 0.021 seconds of real time 0.021083 seconds of total run time (0.020312 user, 0.000771 system) [ Run times consist of 0.003 seconds GC time, and 0.019 seconds non-GC time. ] 100.00% CPU 51,983,719 processor cycles 78,751,760 bytes consed I wonder some kind of compiler magic kicks in, for higher number.
- bjoli 6y agoLook at the disassemble of it. I think the first example is the surprising bit. SBCL does TCO, and the the tail-calling version should always be faster. Maybe SBCL is inlining and unrolling the first version for small numbers.
- junke 6y agoYou don't really have a precise measure when the time is 0.000002 seconds, there are other factors that can fudge the timings. But, there is indeed a better performance for "fact" on the small input. Notice that I have to make a loop and make sure the result from the function is used: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 3.208 seconds of real time 3.208269 seconds of total run time (3.208269 user, 0.000000 system) 100.00% CPU 10,241,019,690 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) USER> (time (loop repeat 100000000 for f = (fact 5) finally (return f))) Evaluation took: 2.972 seconds of real time 2.971409 seconds of total run time (2.971409 user, 0.000000 system) 99.97% CPU 9,484,980,134 processor cycles 0 bytes consed 120 (7 bits, #x78, #o170, #b1111000) I think the additional local functions might add a bit of overhead that is noticeable on small inputs. So I added (declare (inline i)) in fact2 (i is iter), recompiled it, and I had a warning: note: *INLINE-EXPANSION-LIMIT* (50) was exceeded while inlining I Then, the timing for fact2 was faster: USER> (time (loop repeat 100000000 for f = (fact2 5) finally (return f))) Evaluation took: 1.900 seconds of real time 1.897450 seconds of total run time (1.897450 user, 0.000000 system) 99.84% CPU 6,056,874,280 processor cycles 0 bytes consed And if I look at the disassembly for fact2, there is a lot of repetition, and it does look like it was inlined recursively. --- edit Here is a loop fact3: (defun fact3 (x) (declare (type integer x) (optimize (speed 3))) (loop for n of-type integer = x then (- n 1) for a of-type integer = 1 then (* n a) while (> n 0) finally (return a))) USER> (time (loop repeat 100000000 for f = (fact3 5) finally (return f))) Evaluation took: 1.636 seconds of real time 1.635138 seconds of total run time (1.635138 user, 0.000000 system) 99.94% CPU 5,219,556,544 processor cycles 0 bytes consed It could be faster but here this supports big integers. Also, please not that this is a micro benchmark, there is a ridiculous amount of iteration needed to have 2-3 seconds of run time.
- iainctduncan 6y agoWhen I read this I feel like I do when my older friends talk about seeing Miles Davis or Bill Evans in New York or some such. Man, to be there... then. At the feet of legends. Damn.
- hazbo 6y agoI was able to write something similar in chez-scheme (define deriv (lambda (f) (let ((dx .0001)) (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))))
- 1f60c 6y agoI'm impressed that the author could remember a lecture from, at the time, well over 25 years ago.