The distinction between discovery and invention is somewhat arbitrary. Yes, it would be weird to talk about people inventing a new species (except in synthetic biology), but people talk about "discovering" a mathematical concept, so why not a family of programming languages?
There's this mythical belief that programmers like to tell themselves: "I'm as good at math as I am programming."
It turns out that for many, this idea is far from the truth. The similarities are superficial. The notation is abstract artifice. Math is not programming. Programming is not math.
If you try to take what you know, and instictively use in one context, and try to walk it over to the other, and directly reapply it, you'll surprise yourself at the amount of disappointment experienced.
I know it seems like one of those Lispers' idiosyncrasies--"discovered" instead of "invented".
I first heard it explained by Philip Wadler, and upon reflection it was one of those "enlightenment" moments that Lispers always go on about: Lambda calculus is a discovery, and should we ever encounter an alien space-faring species, we could read their programs in spite of their alien processing architectures (given that they use a functional language, but let's face it, they have the tech to cross space, they know what they are doing, i.e. they're in the functional camp)
Yes, there's a real reason for using the word discovered instead of invented. Depends on how webbed in you are intellectually to people around you. Which is often highly dependent on language, logic, and math.
Lambda calculus. Enlightenment. Discovered, not invented. If it already exists somewhere... Everything coming together in the same patterns. Influence.
More like mathematics: the iron laws of points, lines, angles, and triangles existed -- and were used by the Egyptians -- long before Pythagoras gave them succinct expression. So it is with Lisp. Representing algorithms as ordered n-tuples of functions with their arguments is such a trivial transformation of ordinary mathematical practice that it hardly merits consideration as a novel invention on its own. The rest is deriving rules that apply to these transformed expressions.
Attitudes may change, of course; had Nathan Myhrvold discovered Lisp, he'd have it locked up in patents till well after 32-bit time_t's overflow.
I think this is a mischaracterisation of Lisp and the history of mathematics.
Saying that lisp is all about writing (function arguments...) misses the point. One can write function application in ML in this way too. The key things are approximately that all syntax could be written as sexps, including things like let and lambda which in other languages require special syntax; and that the semantics (somewhat) corresponds to the lambda-calculus and so includes lambdas.
I would not say that Lisp is fantastically succinct. There are many ways to express things and the main advantage of lisp is that you can choose how to do this, so long as you express things in sexps.
Yes the (very) ancient Egyptians sort-of knew about Pythagoras’ theorem, although I would perhaps say that the babylonians knew it better. I don’t know whether it is known if they knew that it held for right triangles both ways or just that one could make a right triangle from a^2+b^2=c^2. However I wouldn’t say that Pythagoras made it succinct. For one thing he likely didn’t exist. Also the main contribution of the Greeks to this would be the notion and formalisation of proof (which evolved over time in Greece), rather than the theorem itself. Indeed I would say that the modern expression of the theorem is more succinct than the one one will find in eg Elements
McCarthy thunk up a beautiful self-evaluating eval function for lambda calculus and wrote it down. (The page-long "Maxwell's equations".) Then he showed it to someone (I forget who) who said, "I can implement that." and did. Suddenly: LISP.
Same pattern with Smalltalk: Alan Kay thought it up and someone wrote a little VM in C and suddenly Smalltalk was a thing in the world.
I came up with the Smalltalk half-pager because John McCarthy had shown how to do it -- and because message-passing OOP can be a not too crazy perspective on Lisp (especially a variant of "apply", and especially if you use the FEXPR and closure ideas).
(OMGOMGOMG Dude, Dr. Kay, sir, your excellency, sir! I'm a huge fan! HUGE! You have made my day. I'm going to be telling random strangers in the street "Alan Kay responded to m'comment on the intertubes today!" and whistling and dancing on lampposts. Okay, deep breath, calming down...)
Apologies for my glibness, I meant no disrespect. I knew it was someone I should remember. (He of BitBlt fame, damn I'm getting old and forgetful!)
- - - -
So... "discovered" or "invented"?
FWIW, I think the point turns on one's metaphysics. Is there some Platonic realm where e.g. each of the "Turing Drawings" ( https://maximecb.github.io/Turing-Drawings/ ) has always existed, just waiting to be discovered? Or did Maxime Chevalier-Boisvert invent them? All of them? What is the ontological status of the vast set of TDs that have never (yet) been seen by any eye, or that have never been run on any real machine?
For "discovered" vs "invented" I think you have to posit your definition of "exist". This puzzled Russell, Whitehead, Wittgenstein, etc.
The Peano axioms describe constraints for instances within a set. Is something already "there" just because we can test the constraints after it appears, or use them to make it?
The foundations of OMeta go way way back (starting with Meta II by Val Schorre ca 1964 -- and in the context of the many different approaches to parsing in the 60s). The modern addition to help make OMeta was the packrat parsing idea. It wouldn't be surprising if some Prolog lore wafted its way in, but I don't recall that any of the many parsing schemes that Prolog has been used for were in the conversations. One of the Ur-centers that most parsing theory has to contend with is "Earley Parsing". However, the idea that a dynamic proof can be used to parse goes very far back.
I pretend to be a strict constructivist, except on cloudless nights far from the city lights. When I see the stars I can believe in infinitudes.
I've been an avid reader of VPRI's papers and reports. Incredible work. It deserves to be more widely known.
Someone on a forum somewhere pointed out the similarity between DCGs and OMeta, I didn't notice it myself.
I'm working to complete a project directly inspired by your work (and Ted Nelson's "Dream Machines" book) that should culminate in a system that approaches the "20,000 lines of code" ... "from the end‐user down to the metal" limit. I'm using Prolog and Joy programming languages and targeting the RISC that Prof. Wirth developed for Project Oberon. I have a simple modeless UI modeled on Oberon OS and Jef Raskin's "Humane Interface". If anything comes of it I'll probably try to show it to you someday.
Sounds interesting. Has anyone used the approach/stack described in the book and can report on pros and cons? Edit: I'd be especially interested in hearing opinions about ParenScript.
We are using a slightly different set of libraries. CL-WHO for generating HTML and XML for sure. AllegroServe for the webserver (with zacl, a new Allegro CL compatibility layer, for non Allegro CLs).
I'm doing dynamic web apps on a different stack but dabbled with doing web apps in Lisp and found the tradeoffs to be quite similar.
Pro: rapid prototyping and development, excellent debugging capabilities (both for your web app and network requests... can be extended to browser-side with effort), your app can have capabilities that are difficult to implement with static languages/frameworks
Con: small user community which results in limited selection of frameworks all having their own quirks/limitations, when things break you're often on your own, in dynamic languages performance often won't scale as easily or as far vertically (the recommended approach is often to be sure your design can scale horizontally)
Please do, there is sadly not enough stuff related to lisp, specially valuable stuff from people that were working during the AI boom. I for one would more than welcome any thorough project/info from your perspective
Well for me, I'm super curious about compiler development, and I think, in the topic of this thread, maybe a chapter on writing a recursive descent parser for JS? building a transpiler? or using lisp as a intermediary with LLVM IR? somewhere where either DSL || "Code is data" and the true advantages of lisp shine through, and I would love that from an experienced lisper. Also if you could go into some use cases for tunable compilers that is seldom elaborated when that is mentioned as a huge lisp advantage! Thanks for giving the community your time in advance!
36 comments
[ 3.8 ms ] story [ 45.0 ms ] threadMcCarthy was deep in the Amazon when suddenly out of nowhere...
https://english.stackexchange.com/questions/16768/discover-o...
It turns out that for many, this idea is far from the truth. The similarities are superficial. The notation is abstract artifice. Math is not programming. Programming is not math.
If you try to take what you know, and instictively use in one context, and try to walk it over to the other, and directly reapply it, you'll surprise yourself at the amount of disappointment experienced.
I first heard it explained by Philip Wadler, and upon reflection it was one of those "enlightenment" moments that Lispers always go on about: Lambda calculus is a discovery, and should we ever encounter an alien space-faring species, we could read their programs in spite of their alien processing architectures (given that they use a functional language, but let's face it, they have the tech to cross space, they know what they are doing, i.e. they're in the functional camp)
"Propositions as Types" by Philip Wadler, Strange Loop. (https://youtu.be/IOiZatlZtGU?t=1678)
I do agree that lisp being super tiny and quite mathematical at heart is probably less a social invention than the rest.
Lambda calculus. Enlightenment. Discovered, not invented. If it already exists somewhere... Everything coming together in the same patterns. Influence.
Attitudes may change, of course; had Nathan Myhrvold discovered Lisp, he'd have it locked up in patents till well after 32-bit time_t's overflow.
Saying that lisp is all about writing (function arguments...) misses the point. One can write function application in ML in this way too. The key things are approximately that all syntax could be written as sexps, including things like let and lambda which in other languages require special syntax; and that the semantics (somewhat) corresponds to the lambda-calculus and so includes lambdas.
I would not say that Lisp is fantastically succinct. There are many ways to express things and the main advantage of lisp is that you can choose how to do this, so long as you express things in sexps.
Yes the (very) ancient Egyptians sort-of knew about Pythagoras’ theorem, although I would perhaps say that the babylonians knew it better. I don’t know whether it is known if they knew that it held for right triangles both ways or just that one could make a right triangle from a^2+b^2=c^2. However I wouldn’t say that Pythagoras made it succinct. For one thing he likely didn’t exist. Also the main contribution of the Greeks to this would be the notion and formalisation of proof (which evolved over time in Greece), rather than the theorem itself. Indeed I would say that the modern expression of the theorem is more succinct than the one one will find in eg Elements
McCarthy thunk up a beautiful self-evaluating eval function for lambda calculus and wrote it down. (The page-long "Maxwell's equations".) Then he showed it to someone (I forget who) who said, "I can implement that." and did. Suddenly: LISP.
Same pattern with Smalltalk: Alan Kay thought it up and someone wrote a little VM in C and suddenly Smalltalk was a thing in the world.
https://en.wikipedia.org/wiki/Steve_Russell_(computer_scient...
I came up with the Smalltalk half-pager because John McCarthy had shown how to do it -- and because message-passing OOP can be a not too crazy perspective on Lisp (especially a variant of "apply", and especially if you use the FEXPR and closure ideas).
Apologies for my glibness, I meant no disrespect. I knew it was someone I should remember. (He of BitBlt fame, damn I'm getting old and forgetful!)
- - - -
So... "discovered" or "invented"?
FWIW, I think the point turns on one's metaphysics. Is there some Platonic realm where e.g. each of the "Turing Drawings" ( https://maximecb.github.io/Turing-Drawings/ ) has always existed, just waiting to be discovered? Or did Maxime Chevalier-Boisvert invent them? All of them? What is the ontological status of the vast set of TDs that have never (yet) been seen by any eye, or that have never been run on any real machine?
- - - -
Er, on a tangent, may I make bold to ask you, did you know that Prolog Discrete Clause Grammar rules are very similar to the OMeta parser generators? https://en.wikipedia.org/wiki/Definite_clause_grammar
The Peano axioms describe constraints for instances within a set. Is something already "there" just because we can test the constraints after it appears, or use them to make it?
The foundations of OMeta go way way back (starting with Meta II by Val Schorre ca 1964 -- and in the context of the many different approaches to parsing in the 60s). The modern addition to help make OMeta was the packrat parsing idea. It wouldn't be surprising if some Prolog lore wafted its way in, but I don't recall that any of the many parsing schemes that Prolog has been used for were in the conversations. One of the Ur-centers that most parsing theory has to contend with is "Earley Parsing". However, the idea that a dynamic proof can be used to parse goes very far back.
I've been an avid reader of VPRI's papers and reports. Incredible work. It deserves to be more widely known.
Someone on a forum somewhere pointed out the similarity between DCGs and OMeta, I didn't notice it myself.
I'm working to complete a project directly inspired by your work (and Ted Nelson's "Dream Machines" book) that should culminate in a system that approaches the "20,000 lines of code" ... "from the end‐user down to the metal" limit. I'm using Prolog and Joy programming languages and targeting the RISC that Prof. Wirth developed for Project Oberon. I have a simple modeless UI modeled on Oberon OS and Jef Raskin's "Humane Interface". If anything comes of it I'll probably try to show it to you someday.
Pro: rapid prototyping and development, excellent debugging capabilities (both for your web app and network requests... can be extended to browser-side with effort), your app can have capabilities that are difficult to implement with static languages/frameworks
Con: small user community which results in limited selection of frameworks all having their own quirks/limitations, when things break you're often on your own, in dynamic languages performance often won't scale as easily or as far vertically (the recommended approach is often to be sure your design can scale horizontally)
https://github.com/rongarret/BWFP
If there's enough interest I'll pick it back up again.
I will try to find some time to write more. Anything in particular you'd like to see in the next chapter?
Though the 45-page book was finished in 2015, according to https://leanpub.com/lispweb.