19 ms·
I’ve Consed Every Pair
- sillysaurusx 7y agoArc is underrated as an information management tool. There's something to be said for having a web framework that works out of the box. Rails is probably the only other framework that makes it as easy to "just make some forms that pass data around and run some code on that data." But not quite -- I haven't seen arc's closure-storing technique used in any other web framework. The main issue that arc solves is that it gives you a full pipeline for managing "objects with properties" via the web. It's so flexible. I wrote a thread on how we're using it in production to manage our TPUs: https://twitter.com/theshawwn/status/1247570883306119170 https://twitter.com/theshawwn/status/1247570883306119170
- throwanem 7y agoYou haven't been around long enough, at least under the same name, to remember when there was an implicit time limit on the comment reply page, inflicted by those stored closures silently timing out. Having long comments so often eaten that way was actually the specific thing that annoyed me into first installing It's All Text. It's an interesting approach, as attempts to force statefulness on a stateless-by-design protocol go, but I don't know that I like how it scales.
- sillysaurusx 7y agoMy account was reset. I've been around since day two. :) You're right, it has some downfalls. But a lot of the time it simply doesn't matter. All the links at https://www.tensorfork.com/tpus https://www.tensorfork.com/tpus are dynamic, and the speed you gain by being able to whip up a feature in 10 minutes is worth the pain of an occasional dead link. On the other hand, I did some work for "deduplicating fnids": http://arclanguage.com/item?id=20996 http://arclanguage.com/item?id=20996 which the site is using, so the links possibly last much longer than the early-HN links. (Basically, we calculate the fnid key based on the lexical environment, rather than using a random ID each time the page is loaded. So each link gets a unique ID based on the code structure rather than a random ID. Meaning, instead of millions of random links to store, you end up with a few tens of thousands.)
- DonHopkins 7y agoAre fnids anything like Fnords? https://en.wikipedia.org/wiki/Fnord https://en.wikipedia.org/wiki/Fnord Or are they more like Vermicious Knids? https://roalddahl.fandom.com/wiki/Vermicious_Knids https://roalddahl.fandom.com/wiki/Vermicious_Knids
- sillysaurusx 7y agoIt's short for function ID. If you want to route requests to specific closures, you have to have some sort of ID that you can send down to the user. Arc stores closures in a hash table keyed by random ID, but we use lexical structure plus lexical values (like username) to make the key deterministic. It greatly cut down on the number of closures that needed to be stored. Basically, if you have a closure that does a certain action – e.g. editing a comment – Arc generates new a closure every page refresh. That was the root reason for the "dead link problem" during the early days of HN. I reworked it to make the closure IDs deterministic. If you walk the source code from the point of the closure up to the root, and then you stick all the local variables in a list and use that as a key, then hash that, along with the actual source code, you end up with something that (a) has a very low probability of collision, and (b) is deterministic each time the page refreshes, unless the variables' values change. (E.g. if you store the current time in a local variable, the value changes, so the fnid will change as well, since that value is captured by the closure and therefore the closure has to do something different by definition.)
- throwanem 7y agoThat sounds like a complicated fix! How many tens of minutes did it take? And how many tens of minutes did the bug cost, in effort spent on comments that got eaten instead of posted? (I know there's no way to answer that last question, but that doesn't mean its answer is equal to zero.)
- throwanem 7y ago(Ah, never mind, I see this line of thought has already been explored nearby. I've nothing to add beyond what's already been said there.)
- senderista 7y agoI think Seaside had the same issues with scaling.
- e12e 7y agoAnd I believe similar closures for keeping state?
- senderista 7y agoYes. An elegant approach with poor scalability and availability characteristics.
- dang 7y agoHN still uses it extensively for its more obscure operations—the ones that don't need to scale. We switched all the most common handlers to regular links years ago. It's hard to remember now that the most common complaint here (by far) used to be about those "Unknown or expired link" messages. In fact, you can tell from the histogram of https://hn.algolia.com/?dateRange=all&page=0&prefix=true&query=%22Unknown%20or%20expired%20link%22&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... when it was that we fixed this—six years ago—because that's when the complaints slow down to a trickle. As long as you don't use it for things that you need a lot of, it's a great approach that holds up well. The primary downside is that they all get discarded when we restart the server process. Another downside is that they don't work well with the back button. Edit: I just remembered another issue with them. Sometimes browsers pre-visit these links, which 'uses' them so that by the time the user goes to click on it, it has already expired. (Yes, this is an issue with using GET for these.)
- sillysaurusx 7y agoThe primary downside is that they all get discarded when we restart the server process. For solving this, http://arclanguage.com/item?id=20996 http://arclanguage.com/item?id=20996 has some theoretical ideas. It's way easier in elisp than in racket, but, the idea is to write out the function + the closure variables to disk. The hard part is that you'd have to fix up object references. (If two closures both capture x, and x is a hash table, then the values of x for both closures should be the same hash table after a reboot.) But it's doable. And of course, if it's possible to write the closures to disk, that means you can write them out to a database shared by multiple Arc webservers. As long as the state is also shared (perhaps the values of the variables can also be stored in the database?) then this means the technique can horizontally scale, just like any other. I spent like a year trying to brainstorm ways of showing that Arc can go toe-to-toe with any of the popular frameworks, with no downsides. "Reboots wipe the closures" implies "Arc can't scale horizontally," which would be a serious limitation in a corporate setting. But in principle I think you could write closures to disk. That would also result in a funny situation: if closures persist forever, it means that a closure could potentially be activated years after it was first stored. So it'll run with years-old code, rather than the latest version. :) But if people are using global names for functions, then it'll just call the latest versions of those functions, which will probably work fine in most cases.
- drcode 7y agoSome arc code I wrote back in the day, for generating textual descriptions from structured data using a web frontend, is still in production at a previous company of mine (as far as I know). It was indeed a useful tool. It's a shame arc didn't have persistent data structures (besides alists :-) and a native hashmap type though. For those confused, we're talking about this: http://www.paulgraham.com/arc.html http://www.paulgraham.com/arc.html
- DonHopkins 7y agoI'm sure somebody has written an ADVENTURE front-end for a LISP debugger. You are in a CONS cell. The there is a CAR to the left, leading off to another CONS, and a CDR to the right, containing NIL. The garbage collector briefly enters the CONS, marks it, quickly glances at the NIL in the CDR, smiles quietly to itself, and looking relieved, hurriedly sweeps away through the CAR. >GIVE CONS TO CDR You give the CONS cell to its CDR, creating a circular list.
- q92z8oeif 7y agoproblem with those frameworks that "just works" is that they get old pretty darn fast. it handles all your sql and auth cookies? too bad now there's an easy way every script kiddie can now login as admin or guess cookies without the security header du jour. It's all nice and all when it's being actively updated. But arc, rails, phoenix-ecto, node/react, drupal, spring, etc it all get old pretty soon when the core maintainers loose focus, and then instead of just keeping an eye on the latest best practices and implementing it yourself, you have to dive deep down into years of feature creep and bad coding practices to do the little thing you need to keep things going.
- saurik 7y ago> I haven't seen arc's closure-storing technique used in any other web framework. Apache Cocoon? https://cocoon.apache.org/2.2/core-modules/core/2.2/1373_1_1.html https://cocoon.apache.org/2.2/core-modules/core/2.2/1373_1_1...
- riffraff 7y agoI am ready to be corrected but I'm a fairly sure there have been a few other continuation-based web frameworks, Seaside in Smalltalk was the one that made the idea popular if I recall correctly. "Href considered harmful" comes from that.
- toolslive 7y agoI don't know Arc, but it seems you're referring to 'continuation based web frameworks'? They have been around since the dawn of the web. Here's criticism from 2006: http://www.interact-sw.co.uk/iangblog/2006/05/21/webcontinuations http://www.interact-sw.co.uk/iangblog/2006/05/21/webcontinua... Truth be told, the criticism is a bit unfair (you can solve the problems)
- rlander 7y agoDo you have any links to resources or blog posts explaining how to do web dev in Arc? A cursory google search turns up ArcGIS stuff.
- zem 7y agoi think seaside (a smalltalk web framework) pioneered the continuation-based technique, though it could have been around earlier. http://www.seaside.st/ http://www.seaside.st/ racket's built-in web server does it too.
- kgwgk 7y agoReferences to some previous uses: https://thelackthereof.org/docs/library/cs/continuations.pdf https://thelackthereof.org/docs/library/cs/continuations.pdf Including pg’s ViaWeb written in continuation-passing style: https://sep.yimg.com/ty/cdn/paulgraham/bbnexcerpts.txt https://sep.yimg.com/ty/cdn/paulgraham/bbnexcerpts.txt
- DonHopkins 7y agoI tried writing some of my own verses for this song, but I couldn't think of anything that rhymed with RPLACA and CDADAADR. Speaking of consing every pair, here's a previous discussion about "The Origin of CAR and CDR in Lisp (2005) (iwriteiam.nl)": https://news.ycombinator.com/item?id=16008239 https://news.ycombinator.com/item?id=16008239 http://www.iwriteiam.nl/HaCAR_CDR.html http://www.iwriteiam.nl/HaCAR_CDR.html
- dragandj 7y agoFWIW, Clojure doesn't cons every pair :)
- DonHopkins 7y agoTo its credit, Clojure is also a Sadistic Perversion Language that "Injects itself into the corporate scene, then subverts from within." https://news.ycombinator.com/item?id=22910702 https://news.ycombinator.com/item?id=22910702 https://www.youtube.com/watch?v=mZyvIHYn2zk https://www.youtube.com/watch?v=mZyvIHYn2zk https://s3-us-west-2.amazonaws.com/vulk-blog/ThePervertsGuidetoComputerProgramming-ThePaper.pdf https://s3-us-west-2.amazonaws.com/vulk-blog/ThePervertsGuid...
- floatingatoll 7y agoAlpaca, Mattered
- lonelappde 7y agoAlter kaker, coulda mattered
- dang 7y agoFunny you bring up rhymes; my brain keeps matching "I've Consed Every Pair, Man" with "Bicycle Repairman". https://www.dailymotion.com/video/x2howud https://www.dailymotion.com/video/x2howud
- pvg 7y ago
- stickydink 7y agoNow, obviously, someone has to run this through Jukebox? https://openai.com/blog/jukebox/ https://openai.com/blog/jukebox/ https://news.ycombinator.com/item?id=23032243 https://news.ycombinator.com/item?id=23032243
- blakesterz 7y agoI remember reading something someplace that was something like ... the problem with being old and full of wisdom is it's hard to share that wisdom with the people that need it most without sounding like an old condescending jerk. Plus, they won't listen anyways. The best you can hope for is that when they are old and full of wisdom they'll remember you and think "hey that old guy was right" . I know when I was 25 I was damn sure I knew better than anyone twice my age.
- gumby 7y ago> I know when I was 25 I was damn sure I knew better than anyone twice my age. This is why I've long believed voting systems should restrict the voting age to 16-28. After all, whom would you rather have voting: people wracked with doubt and who fear their own ignorance, or people who know everything?
- irrational 7y agoYou are starting too late. In my experience 10 years old is when the all-knowing really kicks in. At least that is that age when each of my children gained omniscience. Apparently.
- mirimir 7y agoI'd rather have "people wracked with doubt and who fear their own ignorance" :)
- gumby 7y agoAh, so you don't believe in experts, eh? Not even ones apparently expert on every subject?
- mirimir 7y agoAs a non-testimonial litigation consultant, I used to joke that I could pose as an expert in anything, given a couple months. But in truth, one of my favorite deposition answers goes something like this: > I'm not prepared to offer an opinion on that question.
- deleted 7y ago[deleted]
- jedberg 7y agoThe most important thing I ever learned from Professor Norvig was how to not get fat at Google. He said, "Never take a tray. If it won't fit on one plate, it's too much". A wise man. I mean I suppose some of the stuff I learned from his textbook was pretty useful too.
- gumby 7y agoWell, he does also rides his bike to work more often than he drives.
- deleted 7y ago[deleted]
- eyelidlessness 7y agoWhat advice would you give to those of us who struggle with our weight, regardless of the size of our plate, who came here to discuss lisp and not what the author of the blog post said to you one time about food portions?
- silviogutierrez 7y agoWrite down what you eat. Even if you change nothing, you'll re-consider grazing/snacking. Write it down before you eat it for extra effectiveness. Shameless plugs in my post history. But to be clear, even a sheet of paper can be tremendously helpful.
- eyelidlessness 7y agoAs a person who recalls every bite and gains weight at one meal a day with no snacking at all, this is not helpful. I'm still looking for advice on why I'm being told to count my food intake in a lisp discussion.
- jedberg 7y agoI apologize if the comment upset you, that wasn't my intention. The thread was about Lisp, Johnny Cash, and Peter Norvig, the last of whom I was quoting. It seemed perfectly relevant.
- avmich 7y agoProfessor steps one level up in awesomeness :) . Skip here comments regarding AI online courses, questions related to AIMA and PAIP books. It's not quite a good opportunity to inquire about finer points of JScheme or even ask clarifications along last September interview with Lex Fridman. The art of maintaining approachability for beginners and reference level of usefulness for advanced is not easy, but it's demonstrated - and here is flipped on another human side. Peter, thank you for your works for all of us.
- floatingatoll 7y agoParagraph one sounds like Hanahaus.
- Keyframe 7y agoThis is stupid and I love it, but come on - who sits down with Norvig and does not know his Lispen background?
- jedberg 7y agoPeople who didn’t take AI classes in college who only know him for his awesome Python work?
- wglb 7y agoFolks who answer questions that were not asked.
- DonHopkins 7y agoPeople who also think John McCarthy has no sense of decency? https://www.senate.gov/artandhistory/history/minute/Have_you_no_sense_of_decency.htm https://www.senate.gov/artandhistory/history/minute/Have_you...
- fouric 7y agoPeople who know of him by name (Coders at Work) but not by face - like me!
- chiph 7y agoMan. I miss Johnny Cash. His cover of NIИ's Hurt is so powerful. June Carter (his wife) died a few months after filming the video, and that just broke his heart. Johnny followed her less than six months later. https://www.youtube.com/watch?v=8AHCfZTRGiI https://www.youtube.com/watch?v=8AHCfZTRGiI Trent Reznor admitted that the song was no longer his after watching it.
- malkia 7y agoI like mostly metal, industrial, heh even ska, ... bust mostly death metal, but then there is Johnny Cash, and I hate country - though not Johnny - there is something about it - also Willie Nelson (and few other, probably there is more, it's just that I don't like mainstream one...)
- Gollapalli 7y agoNah, most country on the radio just doesn't have the same kinda honesty that Johnny Cash or Willie Nelson had. Nor do they have the kind of intensity that a man like Cash had. It just isn't the same. Fellow metalhead who likes ska, btw.
- coreyp_1 7y agoIf you like them, you should also consider Ray Wylie Hubbard. Slightly different style, but in the same vein of truth.
- malkia 7y agoHey thanks, just googled and found this concert - and yes, it's my thing - https://www.youtube.com/watch?v=y9_xBIuV9nE https://www.youtube.com/watch?v=y9_xBIuV9nE - wonder why country is not like this... then again even modern metal is not to my liking - so I maybe just old :) That to be said, recently discovered Ho99o9 and love them.
- DonHopkins 7y agoJohnny Cash guest starred in the best Columbo episode ever, "Swan Song": https://columbophile.com/2018/03/11/episode-review-columbo-swan-song/ https://columbophile.com/2018/03/11/episode-review-columbo-s... https://www.youtube.com/watch?v=vtLYJ4STuXY https://www.youtube.com/watch?v=vtLYJ4STuXY He was humping the pretty young girl singer, and murdered the mean old lady bible thumper in an airplane crash, then when Columbo finally (but barely) caught him, he was so remorseful he said he wanted to get caught all along.
- jiveturkey 7y agofinally. a useful post on medium.
- throwaway99AA99 7y ago> I found it ironic that this programmer seemed not to realize that I had used Lisp as my primary language for 15 years of my career. Why is that ironic?
- ggm 7y agoIf somebody is trying to school you, and if there is a reason to believe you work in a genius-factory, then its ironic that the school-er doesn't do their homework into the school-ee to understand what they might be doing. Go back to school?
- throwaway99AA99 7y agoHow did you gather all of that from the short paragraph at the beginning of the article?
- ggm 7y agoThere are about three possible choices 1) he knew he did LISP like languages and wanted to share 2) he didn't know he did LISP like languages and wanted to share 3) he was showing off. 4) the other choices. I went to 3) based on my 40 years experience in computer science.
- throwaway99AA99 7y agoMaybe he just didn't recognize his face? Or might have recognized the name but lacked knowledge about his career? Remember Hanlon's razor: "Never attribute to malice that which is adequately explained by stupidity." Or, more politely and from a different angle, don't assume that the collection of facts that you happen to be aware of is obvious to everyone.
- ggm 7y agoIronically, this is wise advice.
- 7y ago
- Waterluvian 7y agoI'll admit I don't think I've really noticed the presence of lisp online other than when people want to talk about lisp. Can someone share some practical examples of where lisp is being used? Maybe a popular open source project I never realised was written in a lisp family language?
- deleted 7y ago[deleted]
- codemonkey-zeta 7y agoI'd recommend giving Emacs a deep dive. That alone should be impressive enough, but if it doesn't satisfy you I'm not sure there are other projects that would.
- Waterluvian 7y agoThanks! I'm sure that will give me a really solid look at what a full application looks like in a lisp.
- TeMPOraL 7y agoMore than one, if you look at it. Emacs is best viewed as a Emacs Lisp runtime that ships text editor as a default application ;). That's how it ends up with extensive outliner/productivity suite, e-mail/news client, file browser and a bunch of other applications within it, and a lot more of third-party one available in the built-in package manager.
- cylinder714 7y agoTo amplify that point, these posts blew my mind, even as a life-long vi guy: https://ambrevar.xyz/emacs-everywhere/ https://ambrevar.xyz/emacs-eshell/
- downerending 7y agoIt's a little sad that it's declined so far. In a way, it's a victim of its own success--it's so easy to write a lisp system that literally dozens, if not hundreds, of variants sprang up. The community was divided, and it never quite came through. IIRC, our fearless leader PG made his zillions using Lisp.
- jakear 7y agoProbably familiar to some of you, but a song you can actually listen to along the same vein, showed to me by Sussman: https://www.bing.com/videos/search?q=god+wrote+lisp&view=detail&mid=88D1554531D6486AF6AA88D1554531D6486AF6AA&FORM=VIRE&PC=APPL https://www.bing.com/videos/search?q=god+wrote+lisp&view=det...
- DonHopkins 7y agoMaybe he's not as as mellifluous as that, but here's a recording Mitch Bradley singing the Open Firmware theme song! But at least he's more mellifluous than Richard Stallman singing the Free Software song. https://news.ycombinator.com/item?id=9844026 https://news.ycombinator.com/item?id=9844026 That same Open Firmware Forth system [1], which was developed by Mitch Bradley [2], was not only in the PowerPC Mac bios, but it was originally used for the SparcStation boot roms, and eventually in the OLPC, and it was even an IEEE Standard 1275-1994! [1] https://en.wikipedia.org/wiki/Open_Firmware https://en.wikipedia.org/wiki/Open_Firmware [2] https://en.wikipedia.org/wiki/Mitch_Bradley https://en.wikipedia.org/wiki/Mitch_Bradley In fact: the Open Firmware boot loader and plug-in card firmware interface technology, commonly used by both Sun and Apple, is the only firmware standard in existence to have its own theme song [3] !!! [3] https://web.archive.org/web/20070204145613/http://playground.sun.com/pub/1275/misc/ofwsong.au https://web.archive.org/web/20070204145613/http://playground... : OpenFirmwareSong ( - ) \ By Mitch Bradley. \ Sung to the tune of "The Flintstones". 𝄞 ." Firmware" cr ." Open Firmware" cr ." It's the appropriate technology," cr ." Features" cr ." FCode booting" cr ." Hierarchical DevInfo tree." cr ." Hack Forth" cr ." Using Emacs on the keys," cr ." Save in" cr ." NVRAM if you please." cr 𝄒 cr ." With your" cr ." Open Firmware" cr ." You can fix the bugs in no time" cr ." Bring the kernel up in no time" cr ." We'll have an FCode time!" cr 𝄒 cr \ Thank you and good night! reboot ;
- tasogare 7y agoSussman is present in that parody: https://m.youtube.com/watch?v=rdj6deraQ6k https://m.youtube.com/watch?v=rdj6deraQ6k
- talaketu 7y agoWith apologies to Geoff Mack, here's a performance by Lucky Starr: https://www.youtube.com/watch?v=dpRvAnhHfmc https://www.youtube.com/watch?v=dpRvAnhHfmc
- adrianmonk 7y agoAs long as we're doing recordings of the song, Hank Snow: https://www.youtube.com/watch?v=jet7Ue743Do https://www.youtube.com/watch?v=jet7Ue743Do
- kazinator 7y ago> While that is a sentiment with which I can wholeheartedly agree, ... ... (since, ya know, I rewrote a Lisp book to make it about Python, so if I said what I really think, there would be no end to the crow I'd have to eat), but anyway ...
- DonHopkins 7y agoPeter Norvig explained why he came to Python from Lisp in an HN posting a decade ago: https://news.ycombinator.com/item?id=1803815 https://news.ycombinator.com/item?id=1803815 >norvig on Oct 18, 2010 | parent | favorite | on: Ask PG: Lisp vs Python (2010) >Peter Norvig here. I came to Python not because I thought it was a better/acceptable/pragmatic Lisp, but because it was better pseudocode. Several students claimed that they had a hard time mapping from the pseudocode in my AI textbook to the Lisp code that Russell and I had online. So I looked for the language that was most like our pseudocode, and found that Python was the best match. Then I had to teach myself enough Python to implement the examples from the textbook. I found that Python was very nice for certain types of small problems, and had the libraries I needed to integrate with lots of other stuff, at Google and elsewhere on the net. >I think Lisp still has an edge for larger projects and for applications where the speed of the compiled code is important. But Python has the edge (with a large number of students) when the main goal is communication, not programming per se. >In terms of programming-in-the-large, at Google and elsewhere, I think that language choice is not as important as all the other choices: if you have the right overall architecture, the right team of programmers, the right development process that allows for rapid development with continuous improvement, then many languages will work for you; if you don't have those things you're in trouble regardless of your language choice. Kenny Tilton (smuglispweeny) tells this story, that ced posted a link to in the same discussion: https://news.ycombinator.com/item?id=1803627 https://news.ycombinator.com/item?id=1803627 >ced on Oct 18, 2010 | parent | favorite | on: Ask PG: Lisp vs Python (2010) >That reminds me of a cool story, in Norvig's talk about Python... >When he finished Peter [Norvig] took questions and to my surprise called first on the rumpled old guy who had wandered in just before the talk began and eased himself into a chair just across the aisle from me and a few rows up. >This guy had wild white hair and a scraggly white beard and looked hopelessly lost as if he had gotten separated from the tour group and wandered in mostly to rest his feet and just a little to see what we were all up to. My first thought was that he would be terribly disappointed by our bizarre topic and my second thought was that he would be about the right age, Stanford is just down the road, I think he is still at Stanford -- could it be? >"Yes, John?" Peter said. >I won't pretend to remember Lisp inventor John McCarthy's exact words which is odd because there were only about ten but he simply asked if Python could gracefully manipulate Python code as data. >"No, John, it can't," said Peter and nothing more, graciously assenting to the professor's critique, and McCarthy said no more though Peter waited a moment to see if he would and in the silence a thousand words were said. http://smuglispweeny.blogspot.com/2008/02/ooh-ooh-my-turn-why-lisp.html http://smuglispweeny.blogspot.com/2008/02/ooh-ooh-my-turn-wh...
- nickburlett 7y agoReminds me of CS 314, the musical http://captainchang.com/cs314-musical.html http://captainchang.com/cs314-musical.html > Think in hex, think in hex > Look around you, who needs dec? > You can do anything in base sixteen or I'll go to my rest!
- Optimal_Persona 7y agoHaha! I love Medeski Martin & Wood's version of "Let's Go Everywhere" with Col. Bruce Hampton on vocals: https://www.youtube.com/watch?v=7WMzDRtU0wU https://www.youtube.com/watch?v=7WMzDRtU0wU
- MichaelMoser123 7y agocons lists are kind of slow because they don't play well with CPU caches. Are there any ideas how to adapt Lisp (or LISP) so that it plays well with current CPU architectures?
- psykotic 7y agoClojure uses persistent vectors which are essentially trees of array chunks (I think 32 elements per array chunk) that support structure sharing and a version of cons called conj that runs in order log32(n) time. But the language isn't really designed for high performance in practice despite some of the early marketing. Anyway, caches are only part of the problem with linked lists. The root problem is that they inhibit out of order execution. Work out the data dependencies and scheduling of a simple summation loop for an array compared to a linked list. Assume everything fits in L1. The out-of-order core goes to town with the array code and overlaps the fetches for subsequent iterations of the loop. But the linked list code is serialized with almost no instruction-level parallelism; you can overlap the summation of an element into the accumulator with the start of the deref of the next pointer, but that only saves you one cycle per iteration compared to what an in-order core would do with the same code. Now suppose the data is in L2. In that case the out-of-order core can overlap the loads of the subsequent array elements and the throughput is only diminished by a little if at all compared to the L1 case. The linked list code, on the other hand, works the same as before but because it cannot overlap the fetches for sequential elements due to the dependent loads, you go from say 5 cycles per iteration to 15 cycles per iteration. If you have to go out to L3 or DRAM the chasm dramatically widens even further. More obviously, linked structures also increase pressure on cache capacity since they have to store their links explicitly. Yet another factor is that modern caches will expend bandwidth on speculative prefetches to reduce latency. This can help for both flat and linked data structures. For example, if you have an AST you should linearly allocate the nodes in the anticipated traversal order to get help from the prefetcher. (And please slim down those fat AST nodes.) If you did that for our linked-list summation example, you'd pay the 15 cycles for the first iteration but then you'd pay 5 cycles for the remaining entries in the same cacheline and also 5 cycles for all remaining entries in other cachelines since the prefetcher will have kicked in. So aside from the startup latency, you're back to running at the same speed as when the list started out in L1. But you're still losing out on the out-of-order execution for the L1 fetches: 4 cycles on a modern core is an opportunity cost of 16 instructions. You're reducing your core to a souped up 486. By the way, for this particular toy example you should go beast mode with SIMD instructions for the array case which will net you another factor of 4x to 32x depending on the element size and the width of your vector unit and then you parallelize across your cores to get another factor of 4x. While those particulars might not generalize to less simple problems, it illustrates that the major issue with linked structures is that they force serial processing.
- nathell 7y agoIn the genre of Lisp songs, I love “God wrote in Lisp”, by Julia Ecklar. Touted as a parody, but it actually has beautiful lyrics. https://www.gnu.org/fun/jokes/eternal-flame.html https://www.gnu.org/fun/jokes/eternal-flame.html
- lihaciudaniel 7y ago>I love “God wrote in Lisp”, by Julia Ecklar. Would bet to be HolyC or "I might be wrong"
- pantalaimon 7y agohttps://xkcd.com/224/ https://xkcd.com/224/
- StavrosK 7y agoHuh, that actually is beautiful, I didn't expect that.
- aidenn0 7y agoLovely voice. With the folk-guitar accompaniment reminds me a bit of Mary Travers.
- dang 7y agoI feel like there were other things like this that people like Guy Steele wrote in the heyday of things like this. More serious people with better memories will be able to say.
- hprotagonist 7y agoAh, filk. Never die.
- microcolonel 7y agoBut peter, don't be fooled, those are not pairs, that's a seq!
- gambiting 7y agoCan someone explain what this means? What is this "consed" he is talking about? I'm a c++ programmer, "consed every pair" means nothing to me.
- simongray 7y agoCons cells are the traditional Lisp data structure making up the nodes of a linked list. It comes from the cons function which is short for "construct". Ironically, Clojure doesn't use cons cells, although it does have a cons function.
- junke 7y agoAdditionally, "to cons" more broadly means "to allocate memory".
- DonHopkins 7y agoAnd remember, that's "CONS" not "CON"! Don't confuse CONS ARTISTS: https://en.wikipedia.org/wiki/Category:Lisp_people https://en.wikipedia.org/wiki/Category:Lisp_people With CON ARTISTS: https://en.wikipedia.org/wiki/List_of_con_artists https://en.wikipedia.org/wiki/List_of_con_artists
- dunefox 7y ago"He is the cons man of the operation."
- zshrdlu 7y agoFrom the Common Lisp Hyperspec: cons n.v. 1. n. a compound data object having two components called the car and the cdr. 2. v. to create such an object. 3. v. Idiom. to create any object, or to allocate storage.
- abdulhaq 7y agoIs Peter waving or drowning? If a pair is consed in a forest, and no one observes it, did it really happen?
- daly 7y agoThat depends> Did you look before or after GC?
- PaulAJ 7y agoMy first thought looking at the title was to wonder if he had Climbed Every Mountain.
- MhMRSATORI 7y agoHave you read your SICP today‽
- dowakin 7y agoPeter Norvig is the most inspiring genius in my coding world. I met(virtually) him via AI course in Udacity and since that time I enjoy all reading/watching from him. His book AI programming(Lisp version) is a gem that I enjoy reading. I've finish a book a few times already - but every time I read I find something new that I missed previous time.
- TurboHaskal 7y agoIt's not ironic once you realise that most Clojure developers are converts from other languages and new to Lisp.
- mark_l_watson 7y agoPeter tech-reviewed the second edition of my Java AI book and made the comment that Java was half as good as Common Lisp for AI and that was probably good enough (we had both written Common Lisp books). He then went to Google and I had lunch with him; I was surprised that he was using Python. I like his poem in the article! A little off topic, but I retired (that is a bit of a joke) and at the age of 69, this year I decided that for maximum programming enjoyment I would only use Lisp languages (linking in Python and TensorFlow on occasion). I am approaching 40 years using Common Lisp and using the language is so much fun. I bought a license for LispWorks and using it for developing a semantic web app.
- thanksforfish 7y agoYou may also enjoy: https://github.com/hylang/hy https://github.com/hylang/hy
- mark_l_watson 7y agoI wrote a short book on Hy last year. A very cool language and just about perfect for using TensorFlow (or PyTorch) in a Lisp language. I am working on a second edition, adding examples converted from my recent work using Common Lisp.
- thanksforfish 7y agoOh cool. I'll link the book for anyone interested: https://leanpub.com/hy-lisp-python https://leanpub.com/hy-lisp-python
- theboywho 7y agoOut of curiosity, what are your thoughts on Clojure ? Also have you heard of Janet* ? what are your thoughts on such an approach ? * https://janet-lang.org https://janet-lang.org
- mark_l_watson 7y agoFor a few years, most of my consulting gigs used Clojure and I donated financial support in the early days. Great community around Clojure. That said, I like Common Lisp and Scheme better. I had not heard of Janet, thanks for the link.
- balthasar 7y agoMaybe the most cringy thing I have read on here.
- dang 7y agoThat's part of the tradition it belongs to.
- daly 7y agoIs this set to music somewhere? I've been writing in lisp since using Lisp 1.5 in college; nearly 50 years.
- evanb 7y agoThere's a great hack showing the Johnny Cash original version of the song, http://www.johnnycashhasbeeneverywhere.com/ http://www.johnnycashhasbeeneverywhere.com/
- hangonhn 7y agoThis may be the opposite song to "I've Consed Every Pair": "Write in C": http://www.poppyfields.net/filks/00259.html http://www.poppyfields.net/filks/00259.html Someone apparently made a YouTube video too: https://www.youtube.com/watch?v=wJ81MZUlrDo https://www.youtube.com/watch?v=wJ81MZUlrDo
- zerr 7y agoI bet he hasn't used LISP 2.
- masonic 7y agothis Johnny Cash song Cash made it popular in the USA, but it was composed by Australian Geoff Mack.
- dang 7y agoMy inner Canadian asks me to point out that Hank Snow made it popular in the USA.
- deleted 7y ago[deleted]