[HN Gopher] As Lovely as a Tree
___________________________________________________________________
As Lovely as a Tree
Author : adityaathalye
Score : 45 points
Date : 2024-06-15 09:59 UTC (1 days ago)
(HTM) web link (tblm.substack.com)
(TXT) w3m dump (tblm.substack.com)
| 082349872349872 wrote:
| Poetry involves a specific choice of words (perhaps with some
| thought to metre or rhyme), so if anything, we should expect
| programs to be as beautiful as poem.
|
| (would there then be algorithms as beautiful as an argument, or
| functions as beautiful as an idea?)
| deadbabe wrote:
| Binary heap
| labster wrote:
| Here, have some Perl poetry:
| https://en.wikipedia.org/wiki/Black_Perl
| adityaathalye wrote:
| Also the fact that 93% of paint splatters are valid Perl
| programs (2019) (mcmillen.dev)
| https://news.ycombinator.com/item?id=40197013
|
| And riffing off poetry in prog langs, Dylan Beattie's
| _Rockstar_ comes to mind: https://codewithrockstar.com/
| 082349872349872 wrote:
| Difficult to mention Beattie without also mentioning his
| musical work, eg "Bug in the Javascript" https://www.youtube.
| com/watch?v=jxi0ETwDvws&list=PLw0jj21rhf...
| adityaathalye wrote:
| Oh my, I haven't seen this one before... grinning like
| silly. I referenced his talk "The Art of Code" in my essay
| (I'm OP), a personal favourite.
|
| Watching "Dylan Beattie's Tech Parodies" seems like a nice
| way to goof off this Sunday... brb.
| 082349872349872 wrote:
| Cool, speaking of rock stars, "You Give REST a Bad Name"
| is a bit heavier; since you're OP, maybe the next one
| could be "Is there a program that rocks as hard as...?"
|
| I still remember a particular moment in the early 1980s.
| I was working through K&R, and temperature conversion
| (SS1.2) had been mid, but the RPN calculator (SS4.3) was
| lit, and having typed it in, then figured out its
| principles of operation, I just _knew_ I wanted to become
| a programmer. He heard one guitar, just
| blew him away He saw stars in his eyes, and the
| very next day *
|
| From then on, I was destined for a life of Hex, Bugs, and
| Rock&Roll.
|
| * https://www.youtube.com/watch?v=Ic02W1bWeFU
| bostik wrote:
| I remember when Perl poetry was a thing. Mates in university
| combined it with code golfing, and came up with some pretty
| wacky results.
|
| Being bad at both poetry and golf, I went with brevity instead:
| require clue;
| Turing_Machine wrote:
| The Fast Fourier Transform.
| tucnak wrote:
| Tedious, inobvious, trickish. Might do it for some people, but
| not for me. Double for-loop substring search tells so much
| more! Oh, pain, oh, obscenity.
| __loam wrote:
| FFT probably prevented a nuclear war.
| creaktive wrote:
| The real beauty lies in the SLOW discrete Fourier transform.
| Such simplicity; but what's really going on there? Highly
| recommend grokking DST for the transcendental beauty.
| avmich wrote:
| http://archive.vector.org.uk/art10500390
|
| ...Roger Hui: In the year 2033 Earth was discovered by Survey
| Fleet MCXII of the Galactic Empire. The Emperor ordered Earth to
| send a representative to the court, with strict instructions to
| "bring something beautiful".
|
| Emperor What beautiful things does Earth have?
|
| Earth Representative Your excellency, our...
| avmich wrote:
| Server went down (?), so the full text here:
|
| 49. Bring Something Beautiful
|
| +/(1+[?][?]) _-s -- x //1-([?][?][?])_-s
|
| The following e-mail exchange took place on 2010-06-24 during a
| discussion on numeric representation.
|
| Morten Kromberg: And... I shall fight against adding any form
| of NaN/Infinity -- to the death! They will horribly complicate
| our implementation and don't help users do anything useful.
|
| Roger Hui: In the year 2033 Earth was discovered by Survey
| Fleet MCXII of the Galactic Empire. The Emperor ordered Earth
| to send a representative to the court, with strict instructions
| to "bring something beautiful".
|
| Emperor What beautiful things does Earth have?
|
| Earth Representative Your excellency, our
| mathematician Euler proved in our year 1737 that
| +/(1+[?][?])*-s -- x//1-([?][?][?])*-s
|
| Emperor What is the [?] symbol?
|
| Earth Rep. [?]i is the i-th prime.
|
| Emperor And what is [?]? Does it do anything
| useful?
|
| Earth Rep. It denotes infinity, your
| excellency.
|
| Emperor (ponders equation for a minute or two)
| Respect!
|
| Emperor Neat notation you have there. Tell me
| more.
|
| Earth Rep. Your excellency, it's called APL. It
| was invented by the Canadian Kenneth E. Iverson ...
| bee_rider wrote:
| Well, I don't think it is the point of the article, but we might
| as well list the most beautiful algorithms we can think of,
| right?
|
| Mergesort is quite beautiful I think. There's something beautiful
| in the simplicity of just merging the sorted lists. Stable. No
| pathological cases. Nice access patterns.
| 082349872349872 wrote:
| IIRC, Knuth said Tarjan's SCC had a certain beauty in that
| exactly when each node is visited, the relevant information has
| just been calculated.
| adastra22 wrote:
| Evolution by natural selection is the most beautiful algorithm
| imho.
| dumpsterdiver wrote:
| I was looking for a word earlier that describes when it
| slowly dawns on a person how profound a thing is that's been
| right in front of their eyes most of their life. The word I
| settled on was revelation, and one of the revelations I
| revisit as I grow older is the menacing terror presented by
| evolving lifeforms.
|
| If you press the fast forward button as a theoretical
| "survivor in the game of life", the creatures that were
| benign when they were static now become terrifying,
| constantly morphing organisms which gain and lose all manner
| of sharp and venomous appendages.
|
| Like those early Deep Dream videos that always had creepy
| eyes and teeth everywhere on inanimate objects... that truly
| is what evolution looks like. It inspires instinctive fear of
| all the bad things, because that is exactly how it manifests.
|
| When you release the fast forward button though and come back
| to the present, what was creepy and terrifying before
| suddenly becomes magnificent. A living representation of
| localized perfection.
| adastra22 wrote:
| Only in niches that get locked in an evolutionary arms
| race, as does sometimes happen but is not the norm. There's
| also prokaryotic life out there chilling and doing the same
| thing it's been doing for billions of years.
| tux3 wrote:
| We owe everything to it, and yet it is twisted and wrong.
|
| Every day that passes, medicine weakens it. I thank medicine.
| ajuc wrote:
| Medicine isn't weakening natural selection any more than
| birds' nests, bees' hives or beavers' dams are. It's all
| part of the optimized function.
| 082349872349872 wrote:
| You can spot social Darwinists by hand-wringing that the
| "unfit" might paradoxically be outbreeding the "fit".
| adastra22 wrote:
| What a succinct summary of the problem, thank you.
| adastra22 wrote:
| Who invented medicine? The product of natural selection,
| that's who.
| octopoc wrote:
| > and yet it is twisted and wrong
|
| Have you seen the movie Idiocracy? IMO it's a way more
| likely dystopia than 1984 or Brave New World, and it's
| explained here[1]. I would argue that _that_ future is
| twisted and wrong, and is partly enabled by (mis)use of
| medicine.
|
| Now I do think that nature's approach, while extremely
| robust, does result in a lot of collateral damage--e.g. the
| fit don't always survive (most of us know people who died
| young due to no genetic conditions and due to no fault of
| their own), and the unfit don't have to die, they just need
| to not reproduce.
|
| [1] https://www.youtube.com/watch?v=ZTMybQuRZ6E
| bjornsing wrote:
| Euclid's algorithm [1] for finding the greatest common divisor
| of two numbers probably belongs on the list. As the name
| implies it was first described by Euclid, in 300 BC(!). It's
| still widely used today.
|
| 1. https://en.m.wikipedia.org/wiki/Euclidean_algorithm
| zem wrote:
| the shunting yard algorithm is beautiful. I also love flood
| fill, especially with a nice visualisation.
| andrewflnr wrote:
| Speaking of poems, algorithms, and trees:
| https://courses.cs.washington.edu/courses/cse461/14sp/lectur...
| adityaathalye wrote:
| Feels like a riff on "Trees" by Joyce Kilmer
| https://www.poetryfoundation.org/poetrymagazine/poems/12744/...
| 082349872349872 wrote:
| See also http://mercury.lcs.mit.edu/~jnc/humour/lisp.tree
| (GLS "quux")
| adityaathalye wrote:
| I find it hard to disagree
|
| That only LISP Can Make a Tree
|
| :D
| MrVandemar wrote:
| I may be misremembering, but I saw a 'C' strcpy that looked
| concise and elegant, and seemed like a kind of poetry to me at
| the time. while(*s1++ = *s2++);
| saghm wrote:
| It's certainly concise, but two post-evaluation assignments
| inside another assignment evaluated as a boolean condition
| feels more like the code equivalent of an Lovecraftian eldritch
| horror than a beautiful sunset.
| ajuc wrote:
| This is code golf, not algorithmic beauty tho. I'd say it's
| like a limeric - short and witty, but not deeply moving.
|
| But I admit I also remember this :)
| proc0 wrote:
| Haskell (and some other pure FP langs) produces a lot of code
| that is basically technical poetry, at the cost of performance.
|
| just look at the fib example:
|
| >> fib = 1 : 1 : [a + b | (a, b) <- zip fib (tail fib)]
| Sharlin wrote:
| Also the two-line "quicksort": qsort [] = []
| qsort pivot : xs = qsort [x <- xs, x < pivot] : pivot : qsort
| [x <- xs, x >= pivot]
| tromp wrote:
| I prefer fib = f 0 1 where f a b = a : f b
| (a+b)
|
| which needs neither zip nor tail.
| fanf2 wrote:
| I like this paper on the sieve of Eratosthenes in Haskell
| https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf by Melissa
| O'Neill (of PCG fame)
| 082349872349872 wrote:
| a moldy oldy (in the tradition of Dijkstra and Euclid):
| proc gcd(n,m): do n>m = n:=n-m m>n = m:=m-n od; return max(n,m)
|
| EDIT: note the different levels of abstraction: this is a
| _program_ which implements a particular GCD _algorithm_ , in a
| manner attempting to reflect the symmetry of the _function_ which
| that algorithm calculates.
| __loam wrote:
| FFT
| creaktive wrote:
| Discrete Fourier Transform alone is transcendental, IMHO.
| yazaddaruvala wrote:
| Im a huge fan of iterative Quickselect and also iterative dfs.
|
| I find especially all their slight variations to be quite poetic.
| remoquete wrote:
| Especially when you're coding poems using english-lang:
| https://github.com/theletterf/english-lang
| FartyMcFarter wrote:
| Minimax search. Such a simple algorithm, but it perfectly solves
| chess and similar games.
| tromp wrote:
| Alpha beta search solves games more efficiently...
| JohnKemeny wrote:
| lx.(lx.f(xx))(lx.f(xx))
| tromp wrote:
| That ignores its first argument x.
|
| You mean the fixpoint combinator lf.(lx.f(x x))(lx.f(x x)), or
| lf.(lx.x x)(lx.f(x x)), or as a lambda diagram:
| ----+---- +-+ +-+-+ +-+ | +-+ | +-+
| +-+
| tromp wrote:
| I would say the combinator \x\y\z.x z (y (\t.z)) is more
| poetic than Y, since it forms a basis for combinatory logic
| all by itself. Not only can you make Y from it, but every
| other combinator as well. And it's the smallest term with
| that property.
| Simon_ORourke wrote:
| It depends, are you talking about W.B. Years here, or some bozo
| from a hip-hop outfit not going three words without saying b*ch?
| defrost wrote:
| > you talking about W.B. Years here
|
| Oh Simon, we're talking both _Yeats_ as in doesn 't rhyme with
| Keats _and_ the Sleaford Mods et al.
|
| You might need an IRL friend to school you on the good bars.
|
| addendum: Humphrey B. Flaubert covers W.B.'40' Years
| https://www.youtube.com/watch?v=oGxDVXGRQpY
| 082349872349872 wrote:
| Some bozo from a hip-hop outfit not going three words without
| cutting glass: https://www.youtube.com/watch?v=mG2zN9xuGVw
|
| (it's the XXI, you can type bitch now, but note that apart from
| a notable hapax, Mr B prefers to refer to ladies)
| ajuc wrote:
| Algorithms can certainly be elegant. A greedy algorithm with a
| lot of special cases added to force it to work feels yucky. A
| simple algorithm that does the minimal amount of work to get the
| job done and handles all the special cases without case-specific
| code feels good. Like a well-crafted, reliable tool. It might not
| be beauty yet, but it's close.
|
| What makes it beautifull in my mind is the same thing that makes
| some poems beautifull - the fact that it seems simpler than the
| problem it solves, and yet it solves it well. If it evokes that
| surprising feeling of "That's it? That's enough?" - then it's
| beautifull, like a poem which expresses complex feeling in a few
| short verses.
|
| For me Floyd-Warshall is one example.
| tromp wrote:
| There's a universal algorithm (l 1 1) (l (lll 1
| (l 1 (l 4 (lll 3 1 (2 (l 2)))) (4 (l 5 (l 5 (2 1)))))) (1 1)) (l
| 1)
|
| (in de-Bruijn notation) which, given a list of input bits, parses
| the encoding of an arbitrary algorithm (as a combinator over the
| minimal single point basis lxlylz.x z (y (lt.z))) from this bit
| stream, and runs that algorithm on the remaining input.
| _nalply wrote:
| For me, tree traversal is beautiful.
| traverse(node): if node: [
| ...traverse(node.left), ...traverse(node.right),
| node.value, ]
|
| The pseudo-code recursively produces a list of the node values in
| post-order.
| amomchilov wrote:
| Huffman encoding
| gumby wrote:
| The author even quoted Sussman but neglected to include Guy
| Steele's version:
|
| I think that I shall never see
|
| A matrix lovely as a tree.
|
| Trees are fifty times as fun
|
| As structures a la PL/I
|
| (Which Dijkstra claims are too baroque).
|
| And SNOBOL's strings just can't compare
|
| With all the leaves a tree may bear,
|
| And COMIT strings are just a joke.
|
| Vectors, tuples too, are nice,
|
| But haven't the impressive Hair
|
| Of trees to which a LISP is heir.
|
| A LISPer's life is paradise!
|
| Many people think that JOSS
|
| And others, too, are strictly boss;
|
| And there are many BASIC fans
|
| Who think their favorite language spans
|
| All that would a user please.
|
| Compared to LISP they're all a loss,
|
| For none of them gives all the ease
|
| With which a LISP builds moby trees.
|
| RPG is just a nurd
|
| (As you no doubt have often heard);
|
| The record layouts are absurd,
|
| And numbers packed in decimal form
|
| Will never fit a base-two word
|
| Without a veritable storm
|
| Of gross conversions fro and to
|
| With them arithmetic to do.
|
| And one must allocate the field
|
| Correct arithmetic to yield
|
| And decimal places represent
|
| Truncation loss to circumvent:
|
| Thus RPG is second-rate.
|
| In LISP one needn't allocate
|
| (That boon alone is heaven-sent!)
|
| The scheme is sheer simplicity:
|
| A number's just another tree.
|
| When numbers threaten overflow
|
| LISP makes the number tree to grow,
|
| Extending its significance
|
| With classic tree-like elegance.
|
| A LISP can generate reports,
|
| Create a file, do chains and sorts;
|
| But one thing you will never see
|
| Is moby trees in RPG.
|
| One thing the average language lacks
|
| Is programmed use of push-down stacks.
|
| But LISP provides this feature free:
|
| A stack -- you guessed it -- is a tree.
|
| An empty stack is simply NIL.
|
| In order, then, the stack to fill
|
| A CONS will push things on the top;
|
| To empty it, a CDR will
|
| Behave exactly like a pop,
|
| A simple CAR will get you back
|
| The last thing you pushed on the stack;
|
| An empty stack's detectable
|
| By testing with the function NULL,
|
| Thus even should a LISPer lose
|
| With PROGs and GOs, RETURNs and DOs,
|
| He need his mind not overtax
|
| To implement recursive hacks:
|
| He'll utilize this clever ruse
|
| Of using trees as moby stacks.
|
| Some claim this method is too slow
|
| Because it uses CONS so much
|
| And thus requires the GC touch;
|
| It has one big advantage, though:
|
| You needn't fear for overflow.
|
| Since LISP allows its trees to grow,
|
| Stacks can to any limits go.
|
| COBOL input is a shame:
|
| The implementors play a game
|
| That no two versions are the same.
|
| And rocky is the FORTRAN road
|
| One's alpha input to decode:
|
| The FORMAT statement is to blame,
|
| But on the user falls the load.
|
| And FOCAL input's just a farce-
|
| But all LISP input comes pre-parsed!
|
| (The input reader gets its fame
|
| By getting storage for each node
|
| From lists of free words scattered sparse.
|
| Its parses all the input strings
|
| With aid of mystic mutterings;
|
| From dots and strange parentheses,
|
| From zeros, sevens, A's and Z's,
|
| Constructs, with magic reckonings,
|
| The pointers needed for its trees.
|
| It builds the trees with complex code
|
| With rubout processing bestowed;
|
| When typing errors do forebode
|
| The rubout makes recovery tame,
|
| And losers then will oft exclaim
|
| Their sanity to LISP is owed --
|
| To help these losers is LISP's aim.)
|
| The flow-control of APL
|
| And OS data sets as well
|
| Are best described as tortured hell.
|
| For LISPers everything's a breeze;
|
| They neatly output all their trees
|
| With format-free parentheses
|
| And see their program logic best
|
| By how their lovely parens nest.
|
| While others are by GOs possessed,
|
| And WHILE-DO, CASE, and all the rest,
|
| The LISPing hackers will prefer
|
| With COND their programs to invest
|
| And let their functions all recur
|
| When searching trees in maddened quest.
|
| Expanding records of fixed size
|
| Will quickly programs paralyze.
|
| Though ISAM claims to be so wise
|
| In allocating overflow,
|
| Its data handling is too slow
|
| And finding it takes many tries.
|
| But any fool can plainly see
|
| Inherent flexibility
|
| In data structured as a tree.
| qazxcvbnm wrote:
| On trees - how could we neglect the Succinct trees?
|
| Succinctness - expressing trees with as little bits as
| entropically possible. The representation is as simple as it
| could be - simply write down nested parentheses whose abstract
| syntax tree is your given tree. Practically all tree operations
| in logarithmic or constant time. How it works - recursively with
| range-min trees and range-max trees - simple and elegant number
| theory.
|
| A primer - https://arxiv.org/pdf/0905.0768
___________________________________________________________________
(page generated 2024-06-16 23:02 UTC)