[HN Gopher] It's lambdas all the way down
___________________________________________________________________
It's lambdas all the way down
Author : behnamoh
Score : 46 points
Date : 2023-08-20 19:03 UTC (3 hours ago)
(HTM) web link (itsbehnam.com)
(TXT) w3m dump (itsbehnam.com)
| ignoramous wrote:
| I mean, if you look at all these SSA compilers for imperative
| languages, then it is indeed functional programming all the way
| down.
| convolvatron wrote:
| I wonder if there is a similar factoring that would factor out
| mutability. a log I guess.
| mrkeen wrote:
| That is what SSA is: single static assignment.
| convolvatron wrote:
| for locally scoped variables, not for referents
| behnamoh wrote:
| Thanks everyone for showing interest in my article. the traffic
| quickly exceeded my cloudflare account limits, resulting in it
| being inaccessible for a while. I've upgraded my plan now and the
| link works.
| Hirrolot wrote:
| > Surprisingly, these particles were found decades ago by Alonzo
| Church, the inventor of Lambda calculus long before electronic
| computers even existed!!
|
| Lambda calculus is not the simplest computational device based on
| functions; with SKI calculus, you only need to define two
| combinators (S and K) to perform any conceivable computation.
| Going further, you can define the full SKI calculus with only a
| single combinator called Iota, so in fact, you only need one
| function to perform any computation. Yes, Turing tarpits exist,
| why that should be a revelation? Practical programming languages
| (both functional and imperative and object-oriented) tend to find
| a compromise between a minimal core and ergonomics, otherwise the
| result will be disastrous.
| convolvatron wrote:
| this is true, but lambda calculus is somewhat usable by a
| human. how many people have written runnin code in combinators
| (I have, sadly)
| alexisread wrote:
| Well, anyone who has written in Forth kinda has, though it's
| interesting that few projects take it further (Factor).
|
| Joy has a great set of pages explaing it's SKI basis
| https://hypercubed.github.io/joy/html/forth-joy.html
| fanf2 wrote:
| https://www.ioccc.org/years-spoiler.html#1998_fanf
|
| One of several IOCCC winners based on lazy evaluation.
| mrwnmonm wrote:
| [dead]
| Supermancho wrote:
| It's procedural programming all the way down (why stop at
| lambdas?) : https://www.youtube.com/watch?v=mrY6xrWp3Gs
| crawfordcomeaux wrote:
| Maybe off topic....what emerges when we don't go down to boolean
| as atomic and instead have a multivariate logical foundation that
| contains uncertainty?
| alexisread wrote:
| I guess you get a combinatorial explosion for binary operators:
| https://en.wikipedia.org/wiki/Three-valued_logic
|
| That's not to say that you can't get some value out of it. SQL
| is probably the closest language currently to implement TVL,
| and there have been recent works on datalog as well:
| https://arxiv.org/pdf/2202.01718.pdf
|
| Datalog has generally better defined reasoning than SQL, and
| can kinda serve duty for typechecking, formal verification.
| It's worth noting that many languages have the (disjointed)
| concept of uninitialised values which are equivalent to TVL
| (Also note nullable types in eg. C#). As such, from a practical
| perspective, TVL is pushed out as much as possible from code, I
| suspect it's of more use for data.
| Jtsummers wrote:
| > He made an error in the code: evcon. and evlis. should come
| before eval..
|
| A note: That's not an error. The code works just fine in Common
| Lisp because CL doesn't care about the order of definitions so
| long as the definitions are made prior to execution. Given that
| both `evcon.` and `evlis.` also call `eval.`, there is no way to
| create a canonical linear ordering of the three functions aside
| from aesthetic preference. You will get similar warnings if you
| put them before or put them after `eval.`.
| intelVISA wrote:
| [b] Lisp claims another soul. [/b]
| grumblingdev wrote:
| Just started getting into Lisp.
|
| I realized that when I call a bunch of functions one after the
| other, I want to be able to reference them. I would have to put
| them in an array.
|
| Then I thought why do I have to make this choice case by case. If
| only everything was a list...
|
| I now want to see how I can shoehorn this into TypeScript. Maybe
| with macros or transpilation or something.
|
| Then I want to see what cool things I can now do.
|
| The only thing that gives me pause is that the language is insane
| to read and when you look at the implementation of Lisp defun and
| defmacro the code gets pretty wacky.
|
| Figuring out what is a primative and what is just lists is very
| difficult.
|
| I wonder if there is a less purist Lisp out there that looks
| nicer.
| convolvatron wrote:
| this comes up alot. Dylan did this. I guess the curse and the
| salvation is that you get used to it pretty quickly. I really
| don't think syntax is all that fundamental - its all fine up to
| a point (lookin at you perl)
| bsder wrote:
| No, it's not lambdas all the way down. Lisp machines are long
| gone.
|
| I really wish people would stop teaching the "metacircular" stuff
| so early. _McCarthy_ even missed metacircularity. It took a
| genuine genius on the level of Stephen Russell to "get it" and
| convert everything to a functional programming language.
|
| Tell people to implement a Lisp down on the imperative language
| of the machine. Suddenly, you will _get it_. Mutability is a pain
| in the ass. Recursion has issues. Garbage collection isn 't
| optional--it's _required_ because all of your "lambda"
| shenanigans are beating the hell out of the allocator and cons-
| ing up trash like a victim of "Hoarders".
|
| Once you see the guts, suddenly metacircularity makes sense. It
| also isn't particularly interesting anymore.
| benburton wrote:
| Unrelated to the content of this post... this looks to be hosted
| on Notion. Is that a reasonable option for a personal blog? I do
| a lot of writing in Notion for work and I would love to
| transition into something more public. I don't really want to
| mess around with Jekyll, Medium, or Substack. Public Notion feels
| sort of compelling.
| rcarr wrote:
| Might want to check out Obsidian and Obsidian Publish
| twoodfin wrote:
| I distinctly remember the moment 25 years ago, at around 2:00 am
| in bed in my dorm, the semester I was taking SICP:
|
| "cons doesn't need to be a special form! Closures are general
| purpose data structures!"
|
| I raced (all of 6 feet) to my... hmm at that point must have been
| the old Gateway 2000 with an AMD K5 brain transplant... and spun
| up the Edwin environment to confirm my hypothesis.
|
| Up there with getting married and having kids as the great life
| events of all time.
| tromp wrote:
| This article uses the factorial function on Church numerals as
| motivation for discussing recursion and the Y-combinator. Yet
| Church numerals have enough recursion "built-in" to compute
| factorials directly: fac = ln.lf. n F (lx.f)
| (lx.x) where F = (lc.ln.n(c(lf.lx.n f(f x))))
|
| For example, fac 3 evaluates as (writing Church numerals simply
| as 1,2...) lf. F (F (F (lx.f))) 1 = lf.
| 1 (F (F (lx.f)) 2) = lf. 1 (2 (F (lx.f) 3)) =
| lf. 1 (2 (3 ((lx.f) 4))) = lf. 1 (2 (3 f)) = 6
___________________________________________________________________
(page generated 2023-08-20 23:00 UTC)