3 ms·

Isn't this just implementing Lisp in Lisp, somehow? Also maybe I'm just not a very good programmer, but I've never seen the point of lambda calculus. Everythin

Isn't this just implementing Lisp in Lisp, somehow? Also maybe I'm just not a very good programmer, but I've never seen the point of lambda calculus. Everything written in Lisp or Scheme just seems to be an obfusc and contrarian way of writing something that would be much simpler in almost any other language.

embedding-shape 6mo ago
> Everything written in Lisp or Scheme just seems to be an obfusc and contrarian way of writing something that would be much simpler in almost any other language. Probably just a "familiar with you know" thing, since me and others have the straight up opposite experience, anything not s-expressions seems needlessly obfuscated with lots of special characters and syntax all over the place, instead of just one syntax for everything, making programs so much simpler. But you're hardly alone with that sentiment, just like I'm also not alone, so either just "brain wired that way" or something similar. The discussion is as old as the internet, highly subjective and impossible to measure, so around we go.
- ErroneousBosh 6mo ago
  So what kind of things do you use s-expressions for? Is there something they're really good at that I don't know about yet?
  - embedding-shape 6mo ago
    Everything? The full projects are in lisp syntax (s-expressions), not Algol-like syntax (C-like syntax) that most people are familiar with. Personally I mostly use Clojure, but lots of lisp-like languages offer the same (simpler) experience of programming.
  - mbac32768 6mo ago
    probably the best use of s-expressions is as an alternative to json which you can implement in 50 lines of code e.g. pretty good for config files or basic serialization
    - embedding-shape 6mo ago
      > pretty good for config files Case in point which suits well for config files; EDN - https://github.com/edn-format/edn https://github.com/edn-format/edn
mattmight 6mo ago
Original article author here. One of the interesting things about the lambda calculus is its universality: by itself, it's a complete foundation for computation. Here's a different old post of mine showing how to build the rest of the programming language, all in a miniscule subset of Python that is the pure lambda calculus: https://matt.might.net/articles/python-church-y-combinator/ https://matt.might.net/articles/python-church-y-combinator/ You can even extract recursion out of the Y combinator or the more primitive U combinator -- out of nothing but lambdas! So, it's lambdas all the way down. Another interesting thing about the lambda calculus is that it wasn't intended to be a programming language. When Alonzo Church created it, there were no computers to program. Alonzo Church was trying to solve problems in the foundations of mathematics. But, untyped lambda calculus has a "bug" that makes it problematic for mathematics -- the self application that enables recursion is a problem if you're a logician who cares about soundness, but it's fantastic if you're a programmer. I don't think of functional languages as obfuscating. I think of them as terse and expressive. They let me most directly encode the model in my head as running code.
- ErroneousBosh 6mo ago
  Thanks, I'll dig into that post later! I think what I don't get is a mental model of what they do, and how that maps onto problems I write code to solve. It's possible it's just that s-expressions are good at solving a problem I don't have and don't really understand.
klibertp 6mo ago
You should be familiar with the terms "essential" and "accidental complexity", right? Lambda calculus, primitive recursion, Brainf*ck (Turing machine) are all models that discard all of the accidental complexity - all of it: syntax, higher-level constructs, abstractions, etc. What's left is the bare computation itself, amenable to analysis. It's not meant to be practical - it's a research vehicle that shows what's possible and what's not possible in the realm of ideas, without looking at any real-world constraints (you would, in practice, want to see the result of your computation in less than 100 years - that's not the consideration when using one of the models). So yeah, it's not something you use, it's something you learn to arm your brain with tools that will help you debug and write complex code that works. It's really worth spending a year or two deep-diving into these "pure theory CS" things; considering that you're going to be writing code for 20+ years (AI allowing), spending 10% of that time learning the foundations on which everything else rests is not that big of a task.
- brazzy 6mo ago
  I'm not sure the concepts of accidental vs. essential complexity really applies here. Is it really "accidental complexity" that is being removed when the result is harder to understand and less practically usable?
  - klibertp 6mo ago
    "Essential" here means something that cannot, in any way, be further removed from consideration. In this view, things that simplify the understanding and make the program more practical are not essential - they are add-ons on top of the most primitive computational model(s). You can drastically simplify the reading of the lambda calculus by giving it direct support for integers, for example - however, you now polluted the model with an additional element that you need to describe and always keep in mind. Using Church encoding lets you get integers without introducing any new elements to the model, keeping the model simpler - but yes, the implementations of programs within that model will get much more complex to read.
    - brazzy 6mo ago
empath75 6mo ago
Lambda calculus is a mathematical formalism that captures a lot of what we care about in terms of computation with a few primitives and some rewrite rules. It is not a programming language, by itself.
- t0mpr1c3 6mo ago
  It's Turing complete. What else do you want?
  - empath75 6mo ago
    There are many things which are Turing complete which are not programming languages.
anthk 6mo ago
Simpler? Obfuscated? Lisp can be self-defining: https://www.t3x.org/zsp/index.html https://www.t3x.org/zsp/index.html Half of CS and discrete math (sets, permutation...) becames self-evident with simple code. From TCL/Tk I had nightmares with simple code with upvar. See this book? https://discrete.openmathbooks.org/dmoi3/dmoi.html https://discrete.openmathbooks.org/dmoi3/dmoi.html With Zenlisp or any other you could basically do all the exercises as if it were a walk, making the definition of the functions self-evident as if they were bricks. A classical factorial example in Zenlisp, as numbers are not actual 'numbers' but Lisp lists: (require 'nmath) (define (fac n) (fi '#1 '#1 n)) (define (fi a b n) (or (and (> b n) a) (fi (* a b) (+ b '#1) n))) (fac '#10) '#3628800 Here '#3628800 it's just (3 6 2 8 8 0 0), as Zenlisp it's written almost from the ground up to teach you how everything can be built from Peano axioms or very close (set theory and the like). After tracing the 'fi' function, this is how it works on recursive basis: + (fi #1 #1 #10) + (fi #1 #2 #10) + (fi #2 #3 #10) + (fi #6 #4 #10) + (fi #24 #5 #10) + (fi #120 #6 #10) + (fi #720 #7 #10) + (fi #5040 #8 #10) + (fi #40320 #9 #10) + (fi #362880 #10 #10) + (fi #3628800 #11 #10) In every iteration, the input values for fi are: a = a * b b = b +1 n = always 10. When b hits 11, 11 is bigger than 10, so it returns 'a'. So, the factorial function: 10! = 109!, 109*8!... and so on. Read the nmath.l and you'll discover how can you do arithmetics (and far more) with the basics. Imath.l implements complex numbers with just atoms (core units in Lisp). Rmath.l operates in the whole R domain.
andoando 6mo ago
Imagine you went back 100 years and someone was like "Come up with a mathematical system that can express any sequences of logical steps" do you imagine what you would deliver is a few primitives and a few simple rules and said "here you go!, this is fully complete". Its actually quite remarkable that Church/Turing didn't start off from primitives like if statements, loops, etc. Lambda calculus is from the 1930s and predates computers, its point is that it is bare bones model of computation. It doesn't make much sense to compare it to modern languages in efficacy, as that seems to imagine someone came up with lambda calculus in 2010 along Java, C, Python, etc. The super cool thing about it is that it is capable of expressing ALL the computation you know today, from the few primitives. An "If" statement for example is λb.λx.λy. b x y
- anthk 6mo ago
  You can simulate a trivial 'cond' with 'or' and 'and'.
mbac32768 6mo ago
Lisp actually kind of sucks and the community is insufferable but a lot of good things in computer science are unachievable without lambda calculus. Compilers, type inferencing, Rust's borrow checker, some parts of React, async/await desugaring all flow from monk-like practice of the lambda calculus. You could possibly invent these things as a Turing machinist but it'd be by stumbling backwards into them and likely doing a shitty job.

embedding-shape 6mo ago

> Everything written in Lisp or Scheme just seems to be an obfusc and contrarian way of writing something that would be much simpler in almost any other language. Probably just a "familiar with you know" thing, since me and others have the straight up opposite experience, anything not s-expressions seems needlessly obfuscated with lots of special characters and syntax all over the place, instead of just one syntax for everything, making programs so much simpler. But you're hardly alone with that sentiment, just like I'm also not alone, so either just "brain wired that way" or something similar. The discussion is as old as the internet, highly subjective and impossible to measure, so around we go.

ErroneousBosh 6mo ago
So what kind of things do you use s-expressions for? Is there something they're really good at that I don't know about yet?
- embedding-shape 6mo ago
  Everything? The full projects are in lisp syntax (s-expressions), not Algol-like syntax (C-like syntax) that most people are familiar with. Personally I mostly use Clojure, but lots of lisp-like languages offer the same (simpler) experience of programming.
- mbac32768 6mo ago
  probably the best use of s-expressions is as an alternative to json which you can implement in 50 lines of code e.g. pretty good for config files or basic serialization
  - embedding-shape 6mo ago
    > pretty good for config files Case in point which suits well for config files; EDN - https://github.com/edn-format/edn https://github.com/edn-format/edn

mattmight 6mo ago

Original article author here. One of the interesting things about the lambda calculus is its universality: by itself, it's a complete foundation for computation. Here's a different old post of mine showing how to build the rest of the programming language, all in a miniscule subset of Python that is the pure lambda calculus: https://matt.might.net/articles/python-church-y-combinator/ https://matt.might.net/articles/python-church-y-combinator/ You can even extract recursion out of the Y combinator or the more primitive U combinator -- out of nothing but lambdas! So, it's lambdas all the way down. Another interesting thing about the lambda calculus is that it wasn't intended to be a programming language. When Alonzo Church created it, there were no computers to program. Alonzo Church was trying to solve problems in the foundations of mathematics. But, untyped lambda calculus has a "bug" that makes it problematic for mathematics -- the self application that enables recursion is a problem if you're a logician who cares about soundness, but it's fantastic if you're a programmer. I don't think of functional languages as obfuscating. I think of them as terse and expressive. They let me most directly encode the model in my head as running code.

ErroneousBosh 6mo ago
Thanks, I'll dig into that post later! I think what I don't get is a mental model of what they do, and how that maps onto problems I write code to solve. It's possible it's just that s-expressions are good at solving a problem I don't have and don't really understand.

klibertp 6mo ago

You should be familiar with the terms "essential" and "accidental complexity", right? Lambda calculus, primitive recursion, Brainf*ck (Turing machine) are all models that discard all of the accidental complexity - all of it: syntax, higher-level constructs, abstractions, etc. What's left is the bare computation itself, amenable to analysis. It's not meant to be practical - it's a research vehicle that shows what's possible and what's not possible in the realm of ideas, without looking at any real-world constraints (you would, in practice, want to see the result of your computation in less than 100 years - that's not the consideration when using one of the models). So yeah, it's not something you use, it's something you learn to arm your brain with tools that will help you debug and write complex code that works. It's really worth spending a year or two deep-diving into these "pure theory CS" things; considering that you're going to be writing code for 20+ years (AI allowing), spending 10% of that time learning the foundations on which everything else rests is not that big of a task.

brazzy 6mo ago
I'm not sure the concepts of accidental vs. essential complexity really applies here. Is it really "accidental complexity" that is being removed when the result is harder to understand and less practically usable?
- klibertp 6mo ago
  "Essential" here means something that cannot, in any way, be further removed from consideration. In this view, things that simplify the understanding and make the program more practical are not essential - they are add-ons on top of the most primitive computational model(s). You can drastically simplify the reading of the lambda calculus by giving it direct support for integers, for example - however, you now polluted the model with an additional element that you need to describe and always keep in mind. Using Church encoding lets you get integers without introducing any new elements to the model, keeping the model simpler - but yes, the implementations of programs within that model will get much more complex to read.
  - brazzy 6mo ago

empath75 6mo ago

Lambda calculus is a mathematical formalism that captures a lot of what we care about in terms of computation with a few primitives and some rewrite rules. It is not a programming language, by itself.

t0mpr1c3 6mo ago
It's Turing complete. What else do you want?
- empath75 6mo ago
  There are many things which are Turing complete which are not programming languages.

anthk 6mo ago

Simpler? Obfuscated? Lisp can be self-defining: https://www.t3x.org/zsp/index.html https://www.t3x.org/zsp/index.html Half of CS and discrete math (sets, permutation...) becames self-evident with simple code. From TCL/Tk I had nightmares with simple code with upvar. See this book? https://discrete.openmathbooks.org/dmoi3/dmoi.html https://discrete.openmathbooks.org/dmoi3/dmoi.html With Zenlisp or any other you could basically do all the exercises as if it were a walk, making the definition of the functions self-evident as if they were bricks. A classical factorial example in Zenlisp, as numbers are not actual 'numbers' but Lisp lists: (require 'nmath) (define (fac n) (fi '#1 '#1 n)) (define (fi a b n) (or (and (> b n) a) (fi (* a b) (+ b '#1) n))) (fac '#10) '#3628800 Here '#3628800 it's just (3 6 2 8 8 0 0), as Zenlisp it's written almost from the ground up to teach you how everything can be built from Peano axioms or very close (set theory and the like). After tracing the 'fi' function, this is how it works on recursive basis: + (fi #1 #1 #10) + (fi #1 #2 #10) + (fi #2 #3 #10) + (fi #6 #4 #10) + (fi #24 #5 #10) + (fi #120 #6 #10) + (fi #720 #7 #10) + (fi #5040 #8 #10) + (fi #40320 #9 #10) + (fi #362880 #10 #10) + (fi #3628800 #11 #10) In every iteration, the input values for fi are: a = a * b b = b +1 n = always 10. When b hits 11, 11 is bigger than 10, so it returns 'a'. So, the factorial function: 10! = 109!, 109*8!... and so on. Read the nmath.l and you'll discover how can you do arithmetics (and far more) with the basics. Imath.l implements complex numbers with just atoms (core units in Lisp). Rmath.l operates in the whole R domain.

andoando 6mo ago

Imagine you went back 100 years and someone was like "Come up with a mathematical system that can express any sequences of logical steps" do you imagine what you would deliver is a few primitives and a few simple rules and said "here you go!, this is fully complete". Its actually quite remarkable that Church/Turing didn't start off from primitives like if statements, loops, etc. Lambda calculus is from the 1930s and predates computers, its point is that it is bare bones model of computation. It doesn't make much sense to compare it to modern languages in efficacy, as that seems to imagine someone came up with lambda calculus in 2010 along Java, C, Python, etc. The super cool thing about it is that it is capable of expressing ALL the computation you know today, from the few primitives. An "If" statement for example is λb.λx.λy. b x y

anthk 6mo ago
You can simulate a trivial 'cond' with 'or' and 'and'.

mbac32768 6mo ago

Lisp actually kind of sucks and the community is insufferable but a lot of good things in computer science are unachievable without lambda calculus. Compilers, type inferencing, Rust's borrow checker, some parts of React, async/await desugaring all flow from monk-like practice of the lambda calculus. You could possibly invent these things as a Turing machinist but it'd be by stumbling backwards into them and likely doing a shitty job.