5 ms·

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency.

by tromp 2y ago

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP. [1] https://crypto.stanford.edu/~blynn/lambda/lisp.html https://crypto.stanford.edu/~blynn/lambda/lisp.html

notpushkin 2y ago
And IIRC, the fixed-point combinator can be defined in Haskell in a way not dissimilar to lambda’s Y combinator itself: fix :: (a -> a) -> a fix f = f (fix f) (I’d say it’s even more aesthetically pleasing, even if a bit way too simple.)
lispm 2y ago
Lisp and Haskell are programming languages. Lambda Calculus not.
- tromp 2y ago
  If you consider it lacking in I/O, then it takes very little to add conventions for those. E.g. the Binary Lambda Calculus is a programming language [1]. [1] https://www.ioccc.org/2012/tromp/hint.htm https://www.ioccc.org/2012/tromp/hint.htm
cryptonector 2y ago
Lambda calculus isn't practical for real-world programming. You have to add various types to make it practical. By then you have a LISP.
- kazinator 2y ago
  You don't have a Lisp until you add to lambda calculus a representation of its syntax using nested lists of symbols, with APIs to manipulate the lists, a way to intercept and transform the lists that are being processed as code and an eval function.
- tromp 2y ago
  By then you have a Haskell, which unlike LISP is just syntactic sugar on a typed lambda calculus.
  - cryptonector 2y ago
    Fair.
kazinator 2y ago
> lack of referential transparency This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope. In Common Lisp, or a similar dialect, we can pose this question: (let ((x 42)) (mystery-macro x)) can mystery-macro be written so that the enclosed x is other than 42? The answer is yes. To have referential transparency, we have to take away this power. Referential transparency is not a "cool feature" we can add to a language, so then we can express new kinds of things. It just refers to something we are not allowed to do.
- tromp 2y ago
  Referential transparency is a big feature in that it hugely aids in reasoning about your program. I agree that it takes away the power of making your code hard to reason about:-)
  - kazinator 2y ago
    All you need is compiler diagnostics about variable shadowing to make this academic issue entirely go away: 1> (defmacro mystery-macro (form) ^(let ((x 73)) ,form)) mystery-macro 2> (with-compile-opts () (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-2:2: warning: let: variable x unused #<sys:vm-desc: a0db560> 3> (with-compile-opts (:warn shadow-var) (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-3:2: warning: let: variable x shadows local variable ** expr-3:2: warning: let: variable x unused #<sys:vm-desc: a0fd0f0> 4> (with-compile-opts (:error shadow-var) (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-4:2: let: variable x shadows local variable ** during evaluation of form (compile-toplevel '(let ((x 42)) (mystery-macro x))) ** ... an expansion of (progn (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** ... an expansion of (with-compile-opts (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** which is located at expr-4:1 Moreover, this is a problem that mainly affects densely nested code. If you write small functions that are not nested beyond a couple of lexical levels or so, referentially opaque smells have nowhere to hide. Example with macro generating code that unhygienically relies on list, which is redefined around the macro: 1> (defmacro mac (x) ^(list ,x)) mac 2> (with-compile-opts (:warn shadow-fun) (compile-toplevel '(labels ((list ())) (mac 1)))) ** expr-2:2: warning: sys:lbind: redefining list, which is a built-in defun ** expr-2:2: warning: sys:lbind: function list shadows global function ** expr-2:2: warning: list: too many arguments: max 0, given 1 #<sys:vm-desc: 9d0e4a0> 3> (with-compile-opts (:error shadow-fun) (compile-toplevel '(labels ((list ())) (mac 1)))) ** expr-3:2: warning: sys:lbind: redefining list, which is a built-in defun ** expr-3:2: sys:lbind: function list shadows global function ** during evaluation of form (compile-toplevel '(labels ((list ())) (mac 1))) ** ... an expansion of (progn (compile-toplevel '(labels ((list ())) (mac 1)))) ** ... an expansion of (with-compile-opts (compile-toplevel '(labels ((list ())) (mac 1)))) ** which is located at expr-3:1 The concept of referential transparency is meaningless if there is no shadowing. If an expression which refers to a certain binding is moved around in the program, it either continues to refer to that same binding, or at worst becomes a free reference (easily diagnosable). If there is no shadowing, constructs cannot surreptitiously intercept bindings.
codethief 2y ago
Wow, this link sent me down a rabbit hole! What a great website! Thanks so much!

by tromp 2y ago

notpushkin 2y ago

And IIRC, the fixed-point combinator can be defined in Haskell in a way not dissimilar to lambda’s Y combinator itself: fix :: (a -> a) -> a fix f = f (fix f) (I’d say it’s even more aesthetically pleasing, even if a bit way too simple.)

lispm 2y ago

Lisp and Haskell are programming languages. Lambda Calculus not.

tromp 2y ago
If you consider it lacking in I/O, then it takes very little to add conventions for those. E.g. the Binary Lambda Calculus is a programming language [1]. [1] https://www.ioccc.org/2012/tromp/hint.htm https://www.ioccc.org/2012/tromp/hint.htm

cryptonector 2y ago

Lambda calculus isn't practical for real-world programming. You have to add various types to make it practical. By then you have a LISP.

kazinator 2y ago
You don't have a Lisp until you add to lambda calculus a representation of its syntax using nested lists of symbols, with APIs to manipulate the lists, a way to intercept and transform the lists that are being processed as code and an eval function.
tromp 2y ago
By then you have a Haskell, which unlike LISP is just syntactic sugar on a typed lambda calculus.
- cryptonector 2y ago
  Fair.

kazinator 2y ago

> lack of referential transparency This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope. In Common Lisp, or a similar dialect, we can pose this question: (let ((x 42)) (mystery-macro x)) can mystery-macro be written so that the enclosed x is other than 42? The answer is yes. To have referential transparency, we have to take away this power. Referential transparency is not a "cool feature" we can add to a language, so then we can express new kinds of things. It just refers to something we are not allowed to do.

tromp 2y ago
Referential transparency is a big feature in that it hugely aids in reasoning about your program. I agree that it takes away the power of making your code hard to reason about:-)
- kazinator 2y ago
  All you need is compiler diagnostics about variable shadowing to make this academic issue entirely go away: 1> (defmacro mystery-macro (form) ^(let ((x 73)) ,form)) mystery-macro 2> (with-compile-opts () (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-2:2: warning: let: variable x unused #<sys:vm-desc: a0db560> 3> (with-compile-opts (:warn shadow-var) (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-3:2: warning: let: variable x shadows local variable ** expr-3:2: warning: let: variable x unused #<sys:vm-desc: a0fd0f0> 4> (with-compile-opts (:error shadow-var) (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** expr-4:2: let: variable x shadows local variable ** during evaluation of form (compile-toplevel '(let ((x 42)) (mystery-macro x))) ** ... an expansion of (progn (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** ... an expansion of (with-compile-opts (compile-toplevel '(let ((x 42)) (mystery-macro x)))) ** which is located at expr-4:1 Moreover, this is a problem that mainly affects densely nested code. If you write small functions that are not nested beyond a couple of lexical levels or so, referentially opaque smells have nowhere to hide. Example with macro generating code that unhygienically relies on list, which is redefined around the macro: 1> (defmacro mac (x) ^(list ,x)) mac 2> (with-compile-opts (:warn shadow-fun) (compile-toplevel '(labels ((list ())) (mac 1)))) ** expr-2:2: warning: sys:lbind: redefining list, which is a built-in defun ** expr-2:2: warning: sys:lbind: function list shadows global function ** expr-2:2: warning: list: too many arguments: max 0, given 1 #<sys:vm-desc: 9d0e4a0> 3> (with-compile-opts (:error shadow-fun) (compile-toplevel '(labels ((list ())) (mac 1)))) ** expr-3:2: warning: sys:lbind: redefining list, which is a built-in defun ** expr-3:2: sys:lbind: function list shadows global function ** during evaluation of form (compile-toplevel '(labels ((list ())) (mac 1))) ** ... an expansion of (progn (compile-toplevel '(labels ((list ())) (mac 1)))) ** ... an expansion of (with-compile-opts (compile-toplevel '(labels ((list ())) (mac 1)))) ** which is located at expr-3:1 The concept of referential transparency is meaningless if there is no shadowing. If an expression which refers to a certain binding is moved around in the program, it either continues to refer to that same binding, or at worst becomes a free reference (easily diagnosable). If there is no shadowing, constructs cannot surreptitiously intercept bindings.

codethief 2y ago

Wow, this link sent me down a rabbit hole! What a great website! Thanks so much!