5 ms·

> Surprisingly, these particles were found decades ago by Alonzo Church, the inventor of Lambda calculus long before electronic computers even existed!! Lambda

> 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.
slaymaker1907 3y ago
Lambda calculus is somewhat interesting in my opinion because in addition to being really simple, it’s actually a pretty usable language. You could use it as a basic template language without much modification. The same cannot be said for Turing machines or SKI calculus (the latter in particular since it has no natural IO mechanism).
tromp 3y ago
> with only a single combinator called Iota iota is just the pair of S and K: λp.p S K = λp.p (λxλyλz. x z (y z)) (λxλy. x) The simplest possible single point combinator basis (in terms of size in bits) is this slight variant of S: A = λxλyλz. x z (y (λ_.z)) Writing S and K in terms of A is an interesting challenge, requiring more than 10 As each...
- deleted 3y ago
  [deleted]

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.

slaymaker1907 3y ago

Lambda calculus is somewhat interesting in my opinion because in addition to being really simple, it’s actually a pretty usable language. You could use it as a basic template language without much modification. The same cannot be said for Turing machines or SKI calculus (the latter in particular since it has no natural IO mechanism).

tromp 3y ago

> with only a single combinator called Iota iota is just the pair of S and K: λp.p S K = λp.p (λxλyλz. x z (y z)) (λxλy. x) The simplest possible single point combinator basis (in terms of size in bits) is this slight variant of S: A = λxλyλz. x z (y (λ_.z)) Writing S and K in terms of A is an interesting challenge, requiring more than 10 As each...

deleted 3y ago
[deleted]