Matt Might's website has taught me so much over the years, going all the way back to ... I want to say 2008-2009? From programming languages to Unix-fu to a huge amount of topics in-between. I'm super glad to see his writing still being shared. One of my favorite corners of the web.
IMHO this and building an ALU with LEDs and logic gates should be part of ... well honestly any curriculum, even if you don't want to be study CS. Only doing that once in your life is enough to understand you could do it.
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.
EForth and Subleq can be though too as a systems emerging from axioms (Subleq operations).
From twenty macro instructions in EForth it can write the core Subleq code and them bootstrap itself.
This is a statement vs expression thing. It works as an expression. Try:
f = function (v) { return e ; }
or
(function (v) { return e ; })
Javascript doesn't allow (nameless) function expressions (using the function keyword) where a function statement would work.
(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.
It's meant as an example. The function receives something, which we call v, and returns something else, which we call e. It's not meant to be taken literally as the variable names - otherwise, you are right, e is undefined in that example.
He is just showing how the syntax of a Scheme function corresponds to the structure of a JavaScript function.
I think it is a lovely experience just because it forces you to think about which abstractions are the correct ones. I think many people have had the feeling that they would love to change one (or many) aspects of a programming language.
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.
> Alonzo Church developed the lambda calculus in 1929.
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))
Matt Might's website has taught me so much over the years, going all the way back to ... I want to say 2008-2009? From programming languages to Unix-fu to a huge amount of topics in-between. I'm super glad to see his writing still being shared. One of my favorite corners of the web.
IMHO this and building an ALU with LEDs and logic gates should be part of ... well honestly any curriculum, even if you don't want to be study CS. Only doing that once in your life is enough to understand you could do it.
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.
"Implement lambda calculus in languages that are pretty much lambda calculus"
How large would implementation be in more usual languages?
One of the smallest implementations is my heavily obfuscated https://www.ioccc.org/2012/tromp/ :
while a less obfuscated and highly performant implementation https://github.com/tromp/AIT/blob/master/uni.c based on combinatory graph reduction takes 446 lines.Here are some starting points for exploration:
http://t3x.org/lfn/
http://t3x.org/klisp/
http://t3x.org/klisp/22/
EForth and Subleq can be though too as a systems emerging from axioms (Subleq operations). From twenty macro instructions in EForth it can write the core Subleq code and them bootstrap itself.
But the Lisp way it's far more elegant.
> "If you've programmed in JavaScript, this form is equivalent to: function (v) { return e ; } "
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?
This is a statement vs expression thing. It works as an expression. Try:
or Javascript doesn't allow (nameless) function expressions (using the function keyword) where a function statement would work.(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...
It's meant as an example. The function receives something, which we call v, and returns something else, which we call e. It's not meant to be taken literally as the variable names - otherwise, you are right, e is undefined in that example.
He is just showing how the syntax of a Scheme function corresponds to the structure of a JavaScript function.
Its just an example. It doesn't matter what the function name is. And it doesn't matter where e comes from. No need to include it
I think it is a lovely experience just because it forces you to think about which abstractions are the correct ones. I think many people have had the feeling that they would love to change one (or many) aspects of a programming language.
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.
Yes?
https://www.t3x.org/clc/code.html
> Alonzo Church developed the lambda calculus in 1929.
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
in De Bruijn notatation, with lambda diagram [3] 10 times smaller than the 7 lines of R5RS Scheme > This code will read a program from stdin, parse it, evaluate it and print the result.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
which allows a list of bits like "1110" (the code for de Bruijn index 3) to index the environment by simply applying it to the environment.[1] https://www.mdpi.com/1099-4300/28/5/494 "The Largest Number Representable in 64 Bits"
[2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
[3] https://tromp.github.io/cl/diagrams.html
[4] https://github.com/tromp/AIT/blob/master/ait/int.lam
This has been my Twitter / X banner for at least 10 years :)
https://x.com/pchapuis/header_photo