It was a "nerd" exploration few decades ago but nowadays so many of the things we do, from buying croissant to voting, is based on hardware and software. People should have a sense that yes it's complex but it's also NOT magic.
How large would implementation be in more usual languages?
Int L[A],m,b,*D=A,
*c,*a=L,C,*U=L,u;s
(_){u--&&s(a=*a);}
char*B,I,O;S(){b=b
--?b:m|read(0,&I,1
)-1;return~I>>b&1;
}k(l,u){for(;l<=u;
U-L<A?*U++=46^l++[
"-,&,,/.--/,:-,'/"
".-,-,,/.-,*,//..,"
]:exit(5));}p(Int*m){
return!*U?*m=S()?U++,!S
()?m[1]=p(++U),2:3:1,p(U)
:S()?U+=2:p(U[1]++),U-m;}x(
c){k(7*!b,9);*U++=b&&S();c&&x
(b);}d(Int*l){--l[1]||d(l[d(*l),
*l=B,B=l,2]);}main(e){for(k(10,33
),a[4]-=m=e-2&7,a[23]=p(U),b=0;;e-2
?e?e-3?s(D=a),C=a [3],++1[a=a[2]],d(
D):c?D=c,c=*D,*D= a,a=D:exit(L[C+1])
:C--<23?C=u+m&1?O =O+O|C&1,9:write(m
||(O=C+28),&O,1)+ 1:(S(),x(0<b++?k(0,
6),U[-5]=96:0)):( D=B?B:calloc(4,X))
?B=*D,*D=c,c=D,D[ 2]=a,a[++D[1]]++,D
[3]=++C+u:exit(6) )e=L[C++],u=L[C];}
But the Lisp way it's far more elegant.
function (v) { return e ; } -> Uncaught SyntaxError: Function statements require a function name
function a (v) { return e ; } a() -> Uncaught ReferenceError: e is not defined
Am I missing something?
f = function (v) { return e ; }
(function (v) { return e ; })
(and that particular function can also be written v => e)
As for the e being undefined when you execute the function, you should see it as a free variable [1], supposed to be defined elsewhere or replaced with something else.
[1] https://en.wikipedia.org/wiki/Free_variables_and_bound_varia...
He is just showing how the syntax of a Scheme function corresponds to the structure of a JavaScript function.
I have been playing with an s-expr based language that compiles to f sharp, and it has made me realize how much I think Rich Hickey made some very lovely choices for clojure. I have never written clojure more than just for fun, but the more in think about my own toy language, the more highly I think of Rich Hickey. Many times because of the choices he made, but even more because of how he compromised to be able to interop with java.
His first publication that showed the elements of the lambda calculus was the 1932 paper "A set of postulates for the foundation of logic", as I cited in my recent paper [1]. It's quite possible he worked on it prior to 1932, but I don't know of any credible evidence on that (would be very interested to learn about any).
> Wait! How the heck is this a "programming" language? > At first glance, this simple language seems to lack both recursion and iteration, not to mention numbers, booleans, conditionals, data structures and all the rest. How can this language possibly be general-purpose?
What most stops lambda calculus from being a programming language is that it doesn't directly support I/O. However, one can adopt some very simple conventions for representing bits, lists of bits (bytes), and lists of bytes, and for letting a lambda term operate on these [2] which make the so-called Binary Lambda Calculus (BLC) a programming language.
And a very expressive language it is too: a BLC self interpreter [4] can be as small as the 170-bits
01000110100001000
00001100000010111
00110000111111100
00101110011111110
00000111100000010
11101110011011110
01111111100001111
11110000101111010
01110100101111101
00101101010011010
which encodes the term
(λ11)(λ(λλλ1(λλ2(1(λ6(λ2(6(λλ3(λλ23(14))))(7(λ7(λ31(21)))))))(41(111))))(11))
┬─┬ ────────────────────────────────────────────┬─┬
└─┤ ──────┬───────────────┬──────────────────── ├─┘
│ ──────┼───┬───────────┼─┬─────────┬──────── │
│ ┬─────┼───┼───────────┼─┼─────────┼──────── │
│ │ ┬───┼───┼───────────┼─┼─────────┼──────── │
│ │ ┼─┬─┼───┼───────────┼─┼─────────┼─┬─┬─┬─┬ │
│ │ │ │ ┼─┬─┼───────────┼─┼──────── └─┤ └─┤ │ │
│ │ │ │ │ ┼─┼─┬─────────┼─┼─┬────── │ ├─┘ │
│ │ │ │ │ │ │ ┼───────┬ │ ┼─┼───┬── ├───┘ │
│ │ │ │ │ │ │ ┼───┬───┼ │ │ ┼─┬─┼─┬ │ │
│ │ │ │ │ │ │ │ ┬─┼───┼ │ │ └─┤ ├─┘ │ │
│ │ │ │ │ │ │ │ ┼─┼─┬─┼ │ │ ├─┘ │ │
│ │ │ │ │ │ │ │ └─┤ ├─┘ │ ├───┘ │ │
│ │ │ │ │ │ │ │ ├─┘ ├─┘ │ │
│ │ │ │ │ │ │ ├───┘ │ │ │
│ │ │ │ │ │ ├─┘ │ │ │
│ │ │ │ │ └─┤ │ │ │
│ │ │ │ │ ├───────────┘ │ │
│ │ │ │ ├───┘ │ │
│ │ │ ├─┘ │ │
│ │ └─┤ │ │
│ │ ├───────────────────────────────┘ │
│ └───┤ │
│ ├───────────────────────────────────────┘
└─────┘
(define (eval e env) (cond
((symbol? e) (cadr (assq e env)))
((eq? (car e) 'λ) (cons e env))
(else (apply (eval (car e) env) (eval (cadr e) env)))))
(define (apply f x)
(eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))
(display (eval (read) '())) (newline)
Except that it leaves all the actual parsing to the "read" library function.
In contrast, the BLC code does all parsing itself. One of the neatest tricks is how it represents the environment as a list built with
cons' = \x\y\zx\zy. zx x (zy y)
[1] https://www.mdpi.com/1099-4300/28/5/494 "The Largest Number Representable in 64 Bits"
[2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
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.
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/
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.
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.
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.
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.
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
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
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
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)
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.
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.
Though... now that I think about it, maybe it does fit - it's all about the question "practical usability for what?"
I suppose that if what you actually want to do is model and reason about theoretical computability, then most things that make languages convenient to implement things in actually are accidental complexity!
e.g. pretty good for config files or basic serialization
Case in point which suits well for config files; EDN - https://github.com/edn-format/edn