Skip to main content

"Let's call a program elegant if no smaller program written in the same programming language has the same output."

I keep thinking back about Chaitin's Unknowable, and can't really appreciate the quote due to golfing being most often synonymous to obfuscation. But I'm also of the mind, that maybe the sort of golfing that results in obfuscation is a side-effect of the language for not being able to express meaning both concisely and explicitly at once.. 🤔

This entry was edited (1 year ago)
in reply to Devine Lu Linvega

Devine Lu Linvega
Devine Lu Linvega
• •
LISP seems like an awfully bad example to express what he's trying to say here, point-free tacit programming is probably able to do a better demonstration of his meaning than any language naming parameters and functions, because doing so inevitably leads to single-character names in the name of "elegance".
This entry was edited (1 year ago)
in reply to Devine Lu Linvega

Danger mouse
Danger mouse
• •

Maybe "smaller" isn't intended to mean "less characters" but "less complexity/structure" in this context.

That way you can still have readable variable names, even local variables to make steps more explicit.

The "LISP elegance" in the text seems a bit loosely defined.
Are we allowed to have a library of common functions?
Does every function we use count against the "size" metric?

in reply to Devine Lu Linvega

retroprom
retroprom
• •
I've been into K and think that tacit style has a rational elegance like math, while Lisp is elegant in a more academic or literary sense - sometimes.
in reply to Devine Lu Linvega

Doug Orleans
Doug Orleans
• •
reminds me of Paul Graham's measure of succinctness, based on AST node size rather that byte-length of the code. http://www.paulgraham.com/power.html

Succinctness is Power

www.paulgraham.com
in reply to Devine Lu Linvega

Jason
Jason
• •

I have a super hard time accepting programming advice from mathematicians. I've recently tried re-implementing numpy/jax stuff in other languages and their `choice` to use single letter character names and really dense functions is pure pain. As someone who's reading their referenced paper AND their code and still not able to make the connections.

Mathematicians focus on elegance has probably slowed the engineering of computers and software more than any other single cultural norm.

Unknown parent

Devine Lu Linvega
Devine Lu Linvega
• •
@eli_oat right?!
@eli_oat
in reply to Devine Lu Linvega

Tröglödÿt
Tröglödÿt
• •

that's a very weird view of elegance

this person must be horrible to watch a ballet or opera with

in reply to Devine Lu Linvega

mcc
mcc
• •
Chaitlin's constant, chaitlin's other "unknowable" conundrums, Busy Beavers / k-information are interesting because they are *objective*, there's a specific number for each of these things and it concretely exists, but you can't ever know what it is, because it's not feasible to brute-force all possibilities… there's an ocean of possible escapes all around you and it is opaque to you
in reply to mcc

mcc
mcc
• •

A related problem, maybe more directly relevant to your post:

Kolmogorov complexity / k-information is relative to a particular "programming language". You pick a language to express your turing machines in and for each basis language you'll get particular programs for particular output streams and so the k-complexity number for each output stream will be a little different… this is elementary, this by itself is a "standard" observation—

in reply to mcc

mcc
mcc
• •

When we talk about *runtime complexity*. O(n^2) and all that. There are theorems that it doesn't matter what "programming language" you pick, that all deterministic formulations of the turing machine produce exactly the same asymptotic runtimes (up to a polynomial factor for translation)…

*Has anyone ever tried to prove the same thing for k-complexity?* That is, do all "programming languages"/TM formulations produce equivalent/related program-lengths? How different can they be?

This entry was edited (1 year ago)
in reply to mcc

Devine Lu Linvega
Devine Lu Linvega
• •
@mcc The closest I've seen to this was Wolfram's centinial view of cellular automata, have you watched/read it? It's worth the detour!
@mcc
in reply to Devine Lu Linvega

mcc
mcc
• •
Yeah! I haven't read the book directly but I've read a lot of the ancillary stuff. I'm particularly fascinated by the philosophical question of "I can make this 1D rule turing complete as long as I am allowed an infinite non-repeating starting pattern". I'm literally not sure if that's legitimately a turing complete 1D rule then!
Unknown parent

Devine Lu Linvega
Devine Lu Linvega
• •
@lobo Chatin, solomonoff and the bunch are really focusing on complexity in regards to textual representation of problems, I've read this as such. But yes, ranking elegance on string length is a hard sell. But even like you said, number of forth words is not a good index either. I can imagine reducing indirection to a form that is definitely not elegant.
in reply to Devine Lu Linvega

418 I'm a Teapot
418 I'm a Teapot
• •
there is a kind of theoretical elegance to it. it is kind of a paraphrase of kolmogorov's definition of complexity -- the main difference being that, for kolmogorov, it's any language. it is a measure of information content. (it is also not computable, but it can be approximated). so, I read this ias Chaintin saying that "elegant" means "containing only information, no redundancy, to the extent possible in some language". You could relax this further and insist on meaningful names.
in reply to 418 I'm a Teapot

Devine Lu Linvega
Devine Lu Linvega
• •
@chainik absolutely, I always have a photo of kolmogorov in my talks when complexity index arises. solomonoff narrowed AIT to string-based representation, and chaitin brings this into exploring halting/incompleteness problems, but still with solomonoff's string based approach.
@418 I'm a Teapot
in reply to Devine Lu Linvega

acb
acb
• •
That might apply to algorithms, but IMHO, for anything involving architectural decisions, the most elegant program would be one in which some space had been committed to a reasonably modular structure/good cable management.
in reply to Devine Lu Linvega

WimⓂ️
WimⓂ️
• •
That is to my mind an awful definition of elegance. For me, elegance is about expressing an idea in a beautiful way. Being succinct can be a part of this, but does not have to be.
in reply to WimⓂ️

Adrian Cochrane
Adrian Cochrane
• •

Usually I find disagreements over the concept of "elegance" comes down to disagreements over goals.

Defining it in terms of outputs helps get around that to have a definition that is more objective, but still: You might simpler software with different outputs.

Unknown parent

Devine Lu Linvega
Devine Lu Linvega
•
@chainik No wait, don't! It's not a good book. Chaitin is a pretencious asshole, half the book is annectodes about how he's so smart. Not worth the time beyond the first 2-3 chapters when he does a sort of rundown of cantor's work, which I enjoyed.
@418 I'm a Teapot
Unknown parent

Devine Lu Linvega
Devine Lu Linvega
• •
@peregrine It's the first time I hear about numpy, but I've come across the mirror view where FP would say that von neueman arch has equally delayed the advancement of compsci, due to their lack of mathematical elegance.
@Jason
Unknown parent

Devine Lu Linvega
Devine Lu Linvega
•
@chainik Maybe something inbetween? To Mock A Mocking Bird.
@418 I'm a Teapot
in reply to Devine Lu Linvega

Capital
Capital
• •

:: I feel like trying to define a grand over arching definition of "elegance" is like trying to define the mean of True Happiness. For some people the terseness of functional programming is elegant. Others find simple procedural programming to be elegance.

A group of friends I'm in tend to find Factor code baffling and impenetrable. Elegant code should be what you find best express you intent.

in reply to Capital

Devine Lu Linvega
Devine Lu Linvega
• •
@CapitalEx there might be a component in appreciating elegance that is familiarity, or understandability or context too ;)
@Capital
in reply to Devine Lu Linvega

Jason
Jason
• •
this is 100% an argument as old as humans have been arguing. The perfect solution that is hard to communicate/execute will lose out to the worse solution thats easier to communicate/execute. The JS ecosystem is the easiest example. ONE exception to this is extreme scenarios like war, the inventor of the turbine engine had the most efficient/complex engine ever built but couldn't get a buyer, even after he put it in a boat and ran circles around steam engines, WW2 changed that.
in reply to Jason

Devine Lu Linvega
Devine Lu Linvega
• •
@peregrine Haha, yes and it transcends programming like you said. I can think of a lot of sailing related examples >__>), sorry to hear you had a rough week btw.
@Jason
in reply to Devine Lu Linvega

Jason
Jason
• •
its all relative, thanks though! I wish I was smart enough to hold all of this in my head and reason about it, but so it goes, they write the code for them, not me.
Unknown parent

WimⓂ️
WimⓂ️
• •
@chainik We write source code precisely because it has to be read by humans. With that "run only" criterion, the program+compiler combo resulting in the fastest running machine code should win. My personal experience is that that kind of code often looks hideous.
@418 I'm a Teapot
Unknown parent

418 I'm a Teapot
418 I'm a Teapot
• •

@wim_v12e aha. i agree. i guess chaitin explicitly excludes that, basically saying: programs are meant to be run, not read (by humans).

@neauoire

@Devine Lu Linvega @WimⓂ️
in reply to Devine Lu Linvega

Jencel Panic
Jencel Panic
• •
Don't have context, but I think it alludes to the concept of Kolmogorov complexity:
"Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output."
in reply to Devine Lu Linvega

Romain Delamare
Romain Delamare
• •

my first reaction was to strongly disagree, mainly for the reasons you explain.

But I kept thinking about it and I realized the reason I like #rustlang so much is that the most explicit way of doing something is often the most concise and has better performance (e.g., https://doc.rust-lang.org/book/ch13-04-performance.html).

I still think that it's a very tricky thing to do with a general purpose language. For a DSL though, I think that's something one should strive for.

Comparing Performance: Loops vs. Iterators - The Rust Programming Language

doc.rust-lang.org
#rustlang
in reply to Devine Lu Linvega

Rob Landley
Rob Landley
• •

I wrote about the tradeoffs between size, speed, features, and simplicity on the toybox design page more than 10 years ago:

https://landley.net/toybox/design.html#goals

Seriously, the smallest code, simplest code, and easiest to understand code are not always the same thing. You've got to sort of 80/20 all of them at once. (I learned that maintaining busybox coming up on 20 years ago now. Wow I'm old...)

The design of toybox

landley.net

Lo, thar be cookies on this site to keep track of your login. By clicking 'okay', you are CONSENTING to this.

⇧