6 ms·

It’s lambdas all the way down

115 points by behnamoh 3y ago

intelVISA 3y ago
[b] Lisp claims another soul. [/b]
ignoramous 3y ago
I mean, if you look at all these SSA compilers for imperative languages, then it is indeed functional programming all the way down.
- convolvatron 3y ago
  I wonder if there is a similar factoring that would factor out mutability. a log I guess.
  - mrkeen 3y ago
    That is what SSA is: single static assignment.
    - convolvatron 3y ago
      for locally scoped variables, not for referents
Hirrolot 3y ago
> 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 3y ago
  this is true, but lambda calculus is somewhat usable by a human. how many people have written runnin code in combinators (I have, sadly)
  - fanf2 3y ago
    https://www.ioccc.org/years-spoiler.html#1998_fanf https://www.ioccc.org/years-spoiler.html#1998_fanf One of several IOCCC winners based on lazy evaluation.
  - alexisread 3y ago
    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 https://hypercubed.github.io/joy/html/forth-joy.html
- jekude 3y ago
  Came here to recommend that the author check out Combinatory Logic (SKI, Iota, Jot, etc). Although not practical, it is pretty incredible how simple/minimal systems can serve as the axiomatic foundation for essentially all of math/logic.
  - msla 3y ago
    There's also the Unlambda programming language: https://en.wikipedia.org/wiki/Unlambda https://en.wikipedia.org/wiki/Unlambda http://www.madore.org/~david/programs/unlambda/ http://www.madore.org/~david/programs/unlambda/
  - behnamoh 3y ago
    thank you, I’ll check out those!
- adrian_b 3y ago
  > Surprisingly, these particles were found decades ago by Alonzo Church, the inventor of Lambda calculus long before electronic computers even existed!! John McCarthy has introduced his lambda notation in October 1958, being inspired by the work of Alonzo Church, but it had very little to do with Lambda calculus. The essential innovation brought at that time by John McCarthy to programming languages was that, unlike in earlier programming languages like Fortran, where a function definition was a separate section of a program source file, where an identifier had to be bound to a function definition, a McCarthy function definition behaves just as a constant value, very similarly to a character string constant, integer constant or floating-point constant, so it can appear in any place where a constant can appear, it can be assigned to an identifier, but it can also be used directly as an argument in the invocation of another function. Once the new semantics of a function definition was established, the syntactic notation for it was a minor detail. A possible notation would have been to enclose any function definition in a special pair of parentheses, like a character string constant that is enclosed in quotation marks. Because this was not feasible due to the limited character set that was available, the chosen syntax was that of a LISP special form, which needs a keyword, for which the choice was "lambda". To distinguish in a function definition the parameters used for function invocation, Alonzo Church had enclosed them in a pair of special parentheses, where the leading parenthesis was a small Greek lambda character and the trailing parenthesis was a raised middle dot. This provided the inspiration for the "lambda" keyword. Perhaps McCarthy was also inspired by Church's work to change the handling of function definitions to be like that of any other values, but that is the maximum extent of the relationship between Lambda calculus and LISP. Nevertheless, the LISP "lambda" notation played an important role in attracting attention upon the work of Alonzo Church, so in the following decade there was much research in functional languages that was much more strongly influenced by Lambda calculus than LISP was.
mrwnmonm 3y ago
[dead]
behnamoh 3y ago
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.
- schemescape 3y ago
  Out of curiosity, what was the limit you hit?
  - behnamoh 3y ago
    I think it was around 10k requests.
Supermancho 3y ago
It's procedural programming all the way down (why stop at lambdas?) : https://www.youtube.com/watch?v=mrY6xrWp3Gs https://www.youtube.com/watch?v=mrY6xrWp3Gs
benburton 3y ago
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 3y ago
  Might want to check out Obsidian and Obsidian Publish
grumblingdev 3y ago
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 3y ago
  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)
tromp 3y ago
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 = λn.λf. n F (λx.f) (λx.x) where F = (λc.λn.n(c(λf.λx.n f(f x)))) For example, fac 3 evaluates as (writing Church numerals simply as 1,2...) λf. F (F (F (λx.f))) 1 = λf. 1 (F (F (λx.f)) 2) = λf. 1 (2 (F (λx.f) 3)) = λf. 1 (2 (3 ((λx.f) 4))) = λf. 1 (2 (3 f)) = 6
crawfordcomeaux 3y ago
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 3y ago
  I guess you get a combinatorial explosion for binary operators: https://en.wikipedia.org/wiki/Three-valued_logic 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 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 3y ago
> 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.`.
- lispm 3y ago
  > The code works just fine in Common Lisp It would work fine in Lisp in general, since Lisp is typically late bound and can call global functions via the symbols. Thus in a function writing a call to an undefined function is not an error. The function only needs to exist at runtime, even then in many debuggers it could added and the computation can be resumed.
bsder 3y ago
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.
- hayley-patton 3y ago
  > Lisp machines are long gone. They also had assembly and microcode (and Maclisp got scoping wrong until CL, anyway). So those weren't much better if you want to measure "purity". > Tell people to implement a Lisp down on the imperative language of the machine. ... Somehow there is no end to the difficulty of mapping an imperative language to another, as evidenced by the size of LLVM. One picks one's poison, I guess.
  - jfoutz 3y ago
    you can hack up eval, map, and apply in c without too much headache. I'd recommend int char and some sort of string representation as primitive. I'd also recommend not garbage collecting, and just malloc everything. Like, a weekend of effort for a really really bad implementation. So much magic disappears. Well, I guess this sort of assumes you know what a pointer is. If not, it's going to be a tough slog regardless. as a second pass, check out the later parts of sicp and expose some array type, and implement the gc in scheme. also I'll never pass up an opportunity to reference 3imp. http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf I know, I know, scheme is a vespa and CL is a Ferrari. For someone who learns more bottom up, the bare minimum of scheme, but all the way is amazing.
- deleted 3y ago
  [deleted]
twoodfin 3y ago
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.
- lionkor 3y ago
  The realisation that, e.g. Lisp, doesnt need structs or classes, because everything's a list, was nice
charred_patina 3y ago
Every time I read a post about the sublime nature of Lisp I end up feeling stupid. I read SICP and didn't really "get" it. I felt like it was just another language, but the structure of the language makes it a bit more obvious how scoping and closures work-- as well as being easier to compose functions of functions. Forth gave me a little bit more of an "aha" moment, but still no enlightenment. I have never used either language to actually build anything useful, so maybe that's part of it.
- Exuma 3y ago
  Try this. I didn’t really see how cool lisp was until I followed this https://docs.racket-lang.org/quick/ https://docs.racket-lang.org/quick/ It’s one thing to read it. It’s another to try it. Download the racket app and just do these fun 10 steps and that’s it.
  - charred_patina 3y ago
    Thanks, I'll give it a shot
overgard 3y ago
I think there are really two types of programming languages, "idea" languages and "practical" languages. "Idea" languages take a concept and try to build almost everything out of it. So like, lisp with lambdas, or smalltalk with message passing, or prolog with logic statements, etc. Then there are "practical" languages, which don't necessarily have a "core" idea; more likely they're defined by the domains they're useful in and have a grab bag of ideas. So like C++, typescript, etc. I think "idea" languages have their appeal because they seem elegant, and as coders, we often try to take a novel idea as far as we can. Usually, that ends up being too far. Like, if you're building a React app, and you go overboard, maybe everything becomes a reactive component even when expressing things in that way can be awkward and your component isn't really a ui "component". Or if you're writing in a functional language, all the sudden loops become recursion and you're praying that it has tail call optimization. If you're writing java, maybe you see dependency injection everywhere. I think we just have this urge to see how many nails our shiny hammer can hit, even to the point of diminishing returns. Anyway, I guess all I'm saying is that even if you can express something as turtles all the way down, you might not necessarily want to build your house out of turtles.
- rr808 3y ago
  The Bjarne Stroustrup division is very similar: "There are only two kinds of languages: the ones people complain about and the ones nobody uses"
  - agalunar 3y ago
    I've never really liked that quote. It's just a way of saying that nothing's perfect, and of course nothing is perfect, but that doesn't mean you shouldn't try to improve them. The quote has always struck me as defensive in a way that stops discussion. It's okay (in fact, more than okay) to say that a complaint is founded on an unsound premise or that a proposed change is a bad idea, but calling other languages useless or unwanted (or implying something to that effect) in response to criticisms of C++ is a bit of deflection, as if saying "well, at least people are productive in it", and I don't think particularly constructive. I think you can start a constructive comment this way, though: "despite its problems, people are still productive in C++ and I think x, y and z are reasons why, so x, y, and z ought to be kept, &c". And in some other context, I think this observation is meaningful: all the languages that are commonly used are complained about, so a complaint about C++ does not necessarily imply that it's worse than any other commonly used language.
bfung 3y ago
closures are a poor man's objects…
- solomonb 3y ago
  "At that moment, Anton became enlightened."
  - bfung 3y ago
    :)
- adrian_b 3y ago
  I am not at all convinced that it is useful to have closures in a programming language. The implementation of closures is completely unnecessary for any of the features that exist in functional languages or in any programming languages. The avoidance of closures becomes possible when the programming language includes the restriction that inside a function body the only external variables (i.e. which are neither parameters nor local variables) that are visible are those that are allocated statically, either as process-local or as thread-local. This restriction is similar with the restrictions from C or from traditional C++, but it is less constraining, because nested functions are allowed, they just cannot see the stack-allocated variables from enclosing blocks, unless they are passed as parameters. Any useful thing that can be implemented with stack-allocated variables captured inside a closure can also be done with statically-allocated variables, but in a much more efficient way and in a way that is less prone to subtle bugs. Other applications of closures in LISPy languages are just workarounds for the impossibility of defining record or structure types. In any language with user-defined data types such closure applications are not needed. The only significant difference between a language with closures and one without closures, from the programmer POV, is that in a language without closures for each variable that is accessed inside a function body without being passed as a parameter, the programmer must add an allocation-class specifier, such as "static" or "thread_local". This is a good thing in my opinion, because sometimes bugs are caused by unintentionally accessing external variables, which are automatically captured in closures. A "purely" functional program must not access inside function bodies any variables that are not passed as parameters. Avoiding to write explicit "static" annotations, in order to make closures masquerade as functions, does not change the fact that such functions are no longer pure functions, but automata, which is good, whenever this is necessary. When there are no closures, any function pointer can be just a simple pointer and any higher-order functions can have a faster implementation, which is better for any functional language. Closures add a completely unnecessary overhead.
mkw5053 3y ago
If anyone is looking for a book on lambda calculus, I really enjoyed An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson [1] [1] https://www.amazon.com/Introduction-Functional-Programming-Calculus-Mathematics/dp/0486478831 https://www.amazon.com/Introduction-Functional-Programming-C...
Exuma 3y ago
One of my all time favorites: https://tomstu.art/programming-with-nothing https://tomstu.art/programming-with-nothing
lapinot 3y ago
Church-encodings are cute but closures take space, more specifically an unbounded amount of it (for the code, unless you defunctionalize it)! Hence it is much more practical to have a primitive notion of inert data that can be inspected and which has a fixed or at least predictable size. Although there are also other more efficient lambda-encodings like Scott-encoding / Mendler-style algebras. See https://firsov.ee/efficient-lambda/ https://firsov.ee/efficient-lambda/, it's a very cool paper. But it also shows it's very tricky to give a type to these encodings. In the end you're almost always better off building "real" datatypes with records and ADTs unless your only goal is to have a minimal theory.
Etrnl_President 3y ago
Half-Life 3 confirmed.
YeGoblynQueenne 3y ago
I'm "A disciple of another sect", a Prolog programmer and I'm always a bit nonplussed when LISP adepts praise the simplicity of their preferred language for taking only (checks again) seven primitives to represent every function. That sounds like 6 primitives too many. In Prolog, there is one "primitive", the definite clause, and it is all the syntax of the language. Quickly-quickly, a logic program is a conjunction of definite clauses, a definite clause is a clause with at most one positive literal, a clause is a disjunction of literals, a literal is an atom or its negation, an atom is a predicate symbol followed by n terms, a term is a constant, a variable, or a function symbol followed by m terms, where n, m are the arities of the atom and the term. That's all you need to express any computable program. And note well that Prolog is a language created to be usable, and used in practice to write everyday programs such as the web server running the SWI-Prolog documentation website [1]; not some Turing tarpit that only exists to be studied under glass, or put on a pedestal and worshipped for its useless purity. It is not Brainfuck, it is not Haskell, it is, I dare say, the C of the non-imperative languages: simple, pragmatic, usable, to the point. Now, I understand why LISP adepts praise the abstraction and power of their language: compared to, say, Java, or, from its own time, COBOL, or FORTRAN, LISP is certainly a leap ahead in modernity, in thinking about programming as computation. And, garbage collection, of course. Yes yes yes. But - all the special syntax! Seven primitives! Why is all that necessary? Imperative languages are so exasperating to use sometimes _because_ they have all that special syntax, purportedly to "make it easy" to fulfill everyday programming tasks. But, may the gods help the unwary prorgammer who strays from the beaten path, as laid out in Stack Overflow. Special-puprose syntax is a straight-jacket, an oxymoron, an attempt to liberate the programmer by tying her hands behind her back. A language like LISP, that prides itself of being a completely different paradigm should not brag for its special purpose syntax, but try to get rid of it. Lest it become Haskell. ___________ [1] https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/http.html%27) https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...
djedr 3y ago
Another revelation: lambda calculus can be reduced down to 4 primitive operations[0]. I had this revelation after a pilgrimage into the land of Binary Lambda Calculus[1], a binary encoding of lambda calculus that represents variables with numerical (de Bruijn) indices[2] in unary. Ultimately, 0 and 1 is all we need. ;) [0] https://jevko.github.io/writing/2023-07-23-revelation.html https://jevko.github.io/writing/2023-07-23-revelation.html -- the pun in the article (I'm the author) fits perfectly into the OP ;D [1] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html [2] https://en.wikipedia.org/wiki/De_Bruijn_index https://en.wikipedia.org/wiki/De_Bruijn_index

115 points by behnamoh 3y ago

[b] Lisp claims another soul. [/b]

I mean, if you look at all these SSA compilers for imperative languages, then it is indeed functional programming all the way down.

convolvatron 3y ago
I wonder if there is a similar factoring that would factor out mutability. a log I guess.
- mrkeen 3y ago
  That is what SSA is: single static assignment.
  - convolvatron 3y ago
    for locally scoped variables, not for referents

Hirrolot 3y ago

> 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 3y ago
this is true, but lambda calculus is somewhat usable by a human. how many people have written runnin code in combinators (I have, sadly)
- fanf2 3y ago
  https://www.ioccc.org/years-spoiler.html#1998_fanf https://www.ioccc.org/years-spoiler.html#1998_fanf One of several IOCCC winners based on lazy evaluation.
- alexisread 3y ago
  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 https://hypercubed.github.io/joy/html/forth-joy.html
jekude 3y ago
Came here to recommend that the author check out Combinatory Logic (SKI, Iota, Jot, etc). Although not practical, it is pretty incredible how simple/minimal systems can serve as the axiomatic foundation for essentially all of math/logic.
- msla 3y ago
  There's also the Unlambda programming language: https://en.wikipedia.org/wiki/Unlambda https://en.wikipedia.org/wiki/Unlambda http://www.madore.org/~david/programs/unlambda/ http://www.madore.org/~david/programs/unlambda/
- behnamoh 3y ago
  thank you, I’ll check out those!
adrian_b 3y ago
> Surprisingly, these particles were found decades ago by Alonzo Church, the inventor of Lambda calculus long before electronic computers even existed!! John McCarthy has introduced his lambda notation in October 1958, being inspired by the work of Alonzo Church, but it had very little to do with Lambda calculus. The essential innovation brought at that time by John McCarthy to programming languages was that, unlike in earlier programming languages like Fortran, where a function definition was a separate section of a program source file, where an identifier had to be bound to a function definition, a McCarthy function definition behaves just as a constant value, very similarly to a character string constant, integer constant or floating-point constant, so it can appear in any place where a constant can appear, it can be assigned to an identifier, but it can also be used directly as an argument in the invocation of another function. Once the new semantics of a function definition was established, the syntactic notation for it was a minor detail. A possible notation would have been to enclose any function definition in a special pair of parentheses, like a character string constant that is enclosed in quotation marks. Because this was not feasible due to the limited character set that was available, the chosen syntax was that of a LISP special form, which needs a keyword, for which the choice was "lambda". To distinguish in a function definition the parameters used for function invocation, Alonzo Church had enclosed them in a pair of special parentheses, where the leading parenthesis was a small Greek lambda character and the trailing parenthesis was a raised middle dot. This provided the inspiration for the "lambda" keyword. Perhaps McCarthy was also inspired by Church's work to change the handling of function definitions to be like that of any other values, but that is the maximum extent of the relationship between Lambda calculus and LISP. Nevertheless, the LISP "lambda" notation played an important role in attracting attention upon the work of Alonzo Church, so in the following decade there was much research in functional languages that was much more strongly influenced by Lambda calculus than LISP was.

mrwnmonm 3y ago

[dead]

behnamoh 3y ago

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.

schemescape 3y ago
Out of curiosity, what was the limit you hit?
- behnamoh 3y ago
  I think it was around 10k requests.

Supermancho 3y ago

It's procedural programming all the way down (why stop at lambdas?) : https://www.youtube.com/watch?v=mrY6xrWp3Gs https://www.youtube.com/watch?v=mrY6xrWp3Gs

benburton 3y ago

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 3y ago
Might want to check out Obsidian and Obsidian Publish

grumblingdev 3y ago

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 3y ago
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)

tromp 3y ago

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 = λn.λf. n F (λx.f) (λx.x) where F = (λc.λn.n(c(λf.λx.n f(f x)))) For example, fac 3 evaluates as (writing Church numerals simply as 1,2...) λf. F (F (F (λx.f))) 1 = λf. 1 (F (F (λx.f)) 2) = λf. 1 (2 (F (λx.f) 3)) = λf. 1 (2 (3 ((λx.f) 4))) = λf. 1 (2 (3 f)) = 6

crawfordcomeaux 3y ago

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 3y ago
I guess you get a combinatorial explosion for binary operators: https://en.wikipedia.org/wiki/Three-valued_logic 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 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 3y ago

> 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.`.

lispm 3y ago
> The code works just fine in Common Lisp It would work fine in Lisp in general, since Lisp is typically late bound and can call global functions via the symbols. Thus in a function writing a call to an undefined function is not an error. The function only needs to exist at runtime, even then in many debuggers it could added and the computation can be resumed.

bsder 3y ago

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.

hayley-patton 3y ago
> Lisp machines are long gone. They also had assembly and microcode (and Maclisp got scoping wrong until CL, anyway). So those weren't much better if you want to measure "purity". > Tell people to implement a Lisp down on the imperative language of the machine. ... Somehow there is no end to the difficulty of mapping an imperative language to another, as evidenced by the size of LLVM. One picks one's poison, I guess.
- jfoutz 3y ago
  you can hack up eval, map, and apply in c without too much headache. I'd recommend int char and some sort of string representation as primitive. I'd also recommend not garbage collecting, and just malloc everything. Like, a weekend of effort for a really really bad implementation. So much magic disappears. Well, I guess this sort of assumes you know what a pointer is. If not, it's going to be a tough slog regardless. as a second pass, check out the later parts of sicp and expose some array type, and implement the gc in scheme. also I'll never pass up an opportunity to reference 3imp. http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf I know, I know, scheme is a vespa and CL is a Ferrari. For someone who learns more bottom up, the bare minimum of scheme, but all the way is amazing.
deleted 3y ago
[deleted]

twoodfin 3y ago

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.

lionkor 3y ago
The realisation that, e.g. Lisp, doesnt need structs or classes, because everything's a list, was nice

charred_patina 3y ago

Every time I read a post about the sublime nature of Lisp I end up feeling stupid. I read SICP and didn't really "get" it. I felt like it was just another language, but the structure of the language makes it a bit more obvious how scoping and closures work-- as well as being easier to compose functions of functions. Forth gave me a little bit more of an "aha" moment, but still no enlightenment. I have never used either language to actually build anything useful, so maybe that's part of it.

Exuma 3y ago
Try this. I didn’t really see how cool lisp was until I followed this https://docs.racket-lang.org/quick/ https://docs.racket-lang.org/quick/ It’s one thing to read it. It’s another to try it. Download the racket app and just do these fun 10 steps and that’s it.
- charred_patina 3y ago
  Thanks, I'll give it a shot

overgard 3y ago

I think there are really two types of programming languages, "idea" languages and "practical" languages. "Idea" languages take a concept and try to build almost everything out of it. So like, lisp with lambdas, or smalltalk with message passing, or prolog with logic statements, etc. Then there are "practical" languages, which don't necessarily have a "core" idea; more likely they're defined by the domains they're useful in and have a grab bag of ideas. So like C++, typescript, etc. I think "idea" languages have their appeal because they seem elegant, and as coders, we often try to take a novel idea as far as we can. Usually, that ends up being too far. Like, if you're building a React app, and you go overboard, maybe everything becomes a reactive component even when expressing things in that way can be awkward and your component isn't really a ui "component". Or if you're writing in a functional language, all the sudden loops become recursion and you're praying that it has tail call optimization. If you're writing java, maybe you see dependency injection everywhere. I think we just have this urge to see how many nails our shiny hammer can hit, even to the point of diminishing returns. Anyway, I guess all I'm saying is that even if you can express something as turtles all the way down, you might not necessarily want to build your house out of turtles.

rr808 3y ago
The Bjarne Stroustrup division is very similar: "There are only two kinds of languages: the ones people complain about and the ones nobody uses"
- agalunar 3y ago
  I've never really liked that quote. It's just a way of saying that nothing's perfect, and of course nothing is perfect, but that doesn't mean you shouldn't try to improve them. The quote has always struck me as defensive in a way that stops discussion. It's okay (in fact, more than okay) to say that a complaint is founded on an unsound premise or that a proposed change is a bad idea, but calling other languages useless or unwanted (or implying something to that effect) in response to criticisms of C++ is a bit of deflection, as if saying "well, at least people are productive in it", and I don't think particularly constructive. I think you can start a constructive comment this way, though: "despite its problems, people are still productive in C++ and I think x, y and z are reasons why, so x, y, and z ought to be kept, &c". And in some other context, I think this observation is meaningful: all the languages that are commonly used are complained about, so a complaint about C++ does not necessarily imply that it's worse than any other commonly used language.

bfung 3y ago

closures are a poor man's objects…

solomonb 3y ago
"At that moment, Anton became enlightened."
- bfung 3y ago
  :)
adrian_b 3y ago
I am not at all convinced that it is useful to have closures in a programming language. The implementation of closures is completely unnecessary for any of the features that exist in functional languages or in any programming languages. The avoidance of closures becomes possible when the programming language includes the restriction that inside a function body the only external variables (i.e. which are neither parameters nor local variables) that are visible are those that are allocated statically, either as process-local or as thread-local. This restriction is similar with the restrictions from C or from traditional C++, but it is less constraining, because nested functions are allowed, they just cannot see the stack-allocated variables from enclosing blocks, unless they are passed as parameters. Any useful thing that can be implemented with stack-allocated variables captured inside a closure can also be done with statically-allocated variables, but in a much more efficient way and in a way that is less prone to subtle bugs. Other applications of closures in LISPy languages are just workarounds for the impossibility of defining record or structure types. In any language with user-defined data types such closure applications are not needed. The only significant difference between a language with closures and one without closures, from the programmer POV, is that in a language without closures for each variable that is accessed inside a function body without being passed as a parameter, the programmer must add an allocation-class specifier, such as "static" or "thread_local". This is a good thing in my opinion, because sometimes bugs are caused by unintentionally accessing external variables, which are automatically captured in closures. A "purely" functional program must not access inside function bodies any variables that are not passed as parameters. Avoiding to write explicit "static" annotations, in order to make closures masquerade as functions, does not change the fact that such functions are no longer pure functions, but automata, which is good, whenever this is necessary. When there are no closures, any function pointer can be just a simple pointer and any higher-order functions can have a faster implementation, which is better for any functional language. Closures add a completely unnecessary overhead.

mkw5053 3y ago

If anyone is looking for a book on lambda calculus, I really enjoyed An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson [1] [1] https://www.amazon.com/Introduction-Functional-Programming-Calculus-Mathematics/dp/0486478831 https://www.amazon.com/Introduction-Functional-Programming-C...

Exuma 3y ago

One of my all time favorites: https://tomstu.art/programming-with-nothing https://tomstu.art/programming-with-nothing

lapinot 3y ago

Church-encodings are cute but closures take space, more specifically an unbounded amount of it (for the code, unless you defunctionalize it)! Hence it is much more practical to have a primitive notion of inert data that can be inspected and which has a fixed or at least predictable size. Although there are also other more efficient lambda-encodings like Scott-encoding / Mendler-style algebras. See https://firsov.ee/efficient-lambda/ https://firsov.ee/efficient-lambda/, it's a very cool paper. But it also shows it's very tricky to give a type to these encodings. In the end you're almost always better off building "real" datatypes with records and ADTs unless your only goal is to have a minimal theory.

Etrnl_President 3y ago

Half-Life 3 confirmed.

YeGoblynQueenne 3y ago

I'm "A disciple of another sect", a Prolog programmer and I'm always a bit nonplussed when LISP adepts praise the simplicity of their preferred language for taking only (checks again) seven primitives to represent every function. That sounds like 6 primitives too many. In Prolog, there is one "primitive", the definite clause, and it is all the syntax of the language. Quickly-quickly, a logic program is a conjunction of definite clauses, a definite clause is a clause with at most one positive literal, a clause is a disjunction of literals, a literal is an atom or its negation, an atom is a predicate symbol followed by n terms, a term is a constant, a variable, or a function symbol followed by m terms, where n, m are the arities of the atom and the term. That's all you need to express any computable program. And note well that Prolog is a language created to be usable, and used in practice to write everyday programs such as the web server running the SWI-Prolog documentation website [1]; not some Turing tarpit that only exists to be studied under glass, or put on a pedestal and worshipped for its useless purity. It is not Brainfuck, it is not Haskell, it is, I dare say, the C of the non-imperative languages: simple, pragmatic, usable, to the point. Now, I understand why LISP adepts praise the abstraction and power of their language: compared to, say, Java, or, from its own time, COBOL, or FORTRAN, LISP is certainly a leap ahead in modernity, in thinking about programming as computation. And, garbage collection, of course. Yes yes yes. But - all the special syntax! Seven primitives! Why is all that necessary? Imperative languages are so exasperating to use sometimes _because_ they have all that special syntax, purportedly to "make it easy" to fulfill everyday programming tasks. But, may the gods help the unwary prorgammer who strays from the beaten path, as laid out in Stack Overflow. Special-puprose syntax is a straight-jacket, an oxymoron, an attempt to liberate the programmer by tying her hands behind her back. A language like LISP, that prides itself of being a completely different paradigm should not brag for its special purpose syntax, but try to get rid of it. Lest it become Haskell. ___________ [1] https://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/http.html%27) https://www.swi-prolog.org/pldoc/doc_for?object=section(%27p...

djedr 3y ago

Another revelation: lambda calculus can be reduced down to 4 primitive operations[0]. I had this revelation after a pilgrimage into the land of Binary Lambda Calculus[1], a binary encoding of lambda calculus that represents variables with numerical (de Bruijn) indices[2] in unary. Ultimately, 0 and 1 is all we need. ;) [0] https://jevko.github.io/writing/2023-07-23-revelation.html https://jevko.github.io/writing/2023-07-23-revelation.html -- the pun in the article (I'm the author) fits perfectly into the OP ;D [1] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html [2] https://en.wikipedia.org/wiki/De_Bruijn_index https://en.wikipedia.org/wiki/De_Bruijn_index