Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

woodrush.github.io

Post reply on HN
Print view View original

91–100 of 101 posts

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#91

Post by kazinator »

tromp wrote: post #90
lisper wrote: post #69

Earlier quoted context omitted.

Yes, that is why I said sufficient and not necessary . The reason CONS/CAR/CDR/COND matter is not because they are necessary. That they are not necessary was known long before 1958. The reason they matter is that they are a better impedance match to human cognition than LC. People can actually write useful programs in Lisp. Very few people can write useful code in LC. Lisp matters because it is a local maximum on the…

> People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work…

Pattern matching appeared in Lisp in the 1960's. See The COMIT Feature in LISP II, https://www.softwarepreservation.com/projects/LISP/lisp2/MIT...

Most mainstream Lisp dialects have some sort of structural pattern matching. Common Lisp has destructuring-bind, which is enough for avoiding car/cdr. Plus a number of advanced pattern matching libraries that are not just for matching lists.

Same with Scheme dialects.

Even Emacs Lisp has pattern matching: https://www.emacswiki.org/emacs/PatternMatching

Nobody needs to work without pattern matching in Lisp, save for maybe some hapless AutoCAD users.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#92

Post by Y_Y »

kazinator wrote: post #76
tromp wrote: post #62

Earlier quoted context omitted.

> That's not what a quote operator does; it does precisely nothing, This is what gives Lisp murky semantics; you need something (quote) to do nothing, while having nothing (no quote) does something (evaluate). Lisp lacks referential transparency, even without the use of variables. An evaluated term can be evaluated again, yielding something different. > Where/how does that become λ 1 again? By decoding it, which is w…

> An evaluated term can be evaluated again, yielding something different. Yes, and a Mogensen-Scott encoding can be Mogensen-Scott-encoded again, requiring two rounds of decoding, and so on. Multiple rounds of encoding and evaluation seem inescapable of you have the entanglement of homoiconicity. The quote operator in Lisp is designed exactly right. In mathematics there are literals like the number 3 or the set {}. T…

What's so special about "literals"? They must be symbols in the sense that they can be evaluated. The fact that you've defined them so that they evaluate to something indistinguishable from the unevaluated form is neat, but it doesn't seem to me fundamental. We could have a lisp where you aren't allowed to evaluate a raw number, it would just be a little more awkward.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#93

Post by invisiblerobot »

haskellandchill wrote: post #67
lisper wrote: post #2

This is one of the most mind-blowing things I have ever seen. Words fail me, so I'll appropriate some of the author's: "Lisp has been described by Alan Kay as the Maxwell’s equations of software. In the same sense, I believe that lambda calculus is the particle physics of computation. LambdaLisp may therefore be a gigantic electromagnetic Lagrangian that connects the realm of human-friendly programming to the origins…

Then what is System F?

polymorphic typed lambda calculus.

it's the theoretical basis for ML and Haskell.

https://en.wikipedia.org/wiki/System_F

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#94

Post by invisiblerobot »

haskellandchill wrote: post #67
lisper wrote: post #2

This is one of the most mind-blowing things I have ever seen. Words fail me, so I'll appropriate some of the author's: "Lisp has been described by Alan Kay as the Maxwell’s equations of software. In the same sense, I believe that lambda calculus is the particle physics of computation. LambdaLisp may therefore be a gigantic electromagnetic Lagrangian that connects the realm of human-friendly programming to the origins…

Then what is System F?

Oh I see, you were asking rhetorically :)

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#95

Post by lisper »

tromp wrote: post #90
lisper wrote: post #69

Earlier quoted context omitted.

Yes, that is why I said sufficient and not necessary . The reason CONS/CAR/CDR/COND matter is not because they are necessary. That they are not necessary was known long before 1958. The reason they matter is that they are a better impedance match to human cognition than LC. People can actually write useful programs in Lisp. Very few people can write useful code in LC. Lisp matters because it is a local maximum on the…

> People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work…

> I find programming in Haskell much more pleasant.

Sure, but that misses the point. Some people like Java. Some like Perl. Some like C++. But, none of these languages come close to Lisp's ratio of utility vs size. So the fact that some people gravitate towards Haskell means nothing in and of itself. (Also, and I mean this with the utmost respect, your brain doesn't work like most people's brains.)

> Ben Lynn's awesome work [1] shows how minimal a Haskell implementation can be...

I'm not sure what you are referring to here. There are two links on that page. One is to an entry in the obfuscated C contest and the other is to Duet. The former is impressively small but, well, it is an entry in the obfuscated C contest and so it's pretty obfuscated. Duet is not obfuscated, but it doesn't seem to me to be particularly minimal. A minimal Lisp compiler can be both readable and an order of magnitude smaller.

> Using car/cdr feels rather primitive compared to pattern matching.

But adding pattern matching to Lisp is an elementary exercise and can be done at the user level. (And surely you knew that too.)

> Haskell, which is basically typed lambda calculus with syntactic sugar on top

Yes, but Haskell's syntactic sugar is significant for two reasons. First, it's not optional. You can put all sorts of fancy syntax on top of Lisp too, but you don't have to, and empirically, most Lisp programmers try this once early in their careers and come to realize that it is a bad idea, that working directly in the AST is weird at first but that it is actually much more productive in the long run. In Haskell there is no AST exposed to the user so this is not an option. There is one syntax and you're stuck with it. And second, Haskell's syntax not well designed IMHO. I am not a particularly skilled coder, but I have worked in a lot of different languages and I find Haskell borderline impenetrable.

BTW, this is a tangent, but I feel the need to say this since you brought up pattern matching: IMHO, if you are using pattern matching in real-world code, you are doing something wrong. Pattern-matching is a way to impose some discipline on punning cons cells to hold structured data, but punning cons cells is a fundamental mistake. If you have structured data, that data should be contained in structures, not cons cells.

(The only exception to this rule is a macro expander, where you have no choice but to deal with cons cells because that is what is handed to you by the reader. But if you are writing a lot of macro expanders then that too is an indication that you are doing something wrong.)

IMHO of course.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#96

Post by haskellandchill »

invisiblerobot wrote: post #94
haskellandchill wrote: post #67

Earlier quoted context omitted.

Then what is System F?

Oh I see, you were asking rhetorically :)

Ha yes, I see it more as a candidate for a maxwell's equations of software engineering than the metacircular interpreter.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#97

Post by kazinator »

lisper wrote: post #95
tromp wrote: post #90

Earlier quoted context omitted.

> People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work…

> I find programming in Haskell much more pleasant. Sure, but that misses the point. Some people like Java. Some like Perl. Some like C++. But, none of these languages come close to Lisp's ratio of utility vs size. So the fact that some people gravitate towards Haskell means nothing in and of itself. (Also, and I mean this with the utmost respect, your brain doesn't work like most people's brains.) > Ben Lynn's aweso…

I agree with everything you wrote, except: adding pattern matching that hits even the lower rungs of good quality is sweating bullets. (So good thing users of Lisps don't have to.)

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#98

Post by kazinator »

anderskaseorg wrote: post #80
kazinator wrote: post #74

Earlier quoted context omitted.

> The situation with Lisp is exactly the same. No it isn't, because the Lisp code is already understood to have an encoding. So we don't have to play any Gödel-numbering-like games to get the code to be able to talk about code. That battery is included. > gives us a more convenient syntax for the latter, in the form of the quote macro The ' in (cons 'lambda ...) is an instance of quote! You must write (cons (intern "…

Yes, I was clear above that I know ' means quote. My experiment is to compare Lisp to a restriction of Lisp where quote only works on symbols. This restriction doesn’t make it any harder to write a self-interpreter. > If we have quote, we can make the additional step in the documentation that all code has the representation produced by quote, even when quote is not being used. When lambda is seen in code, that is act…

We can analyze lexical scoping through quote. Here is TXR Lisp doing it:

  1> (defmacro free-vars (expr :env e)
       (if-match (quote @qexp) expr  ;; unwrap quote if it occurs
         (set expr qexp))
       (tree-bind (expansion free-vars free-funs . rest) (expand-with-free-refs expr e)
         ^(quote ,free-vars)))
  free-vars
  2> (let ((a 42)) (free-vars '(lambda () (+ a b))))
  (b)
Roughly speaking, this is the basis for doing things like back-referencing against an existing lexical variable in pattern matching:

  3> (let ((x 1))
       (match (@x @y) '(1 2) y))
  2
  4> (let ((x 1))
       (match (@x @y) '(2 2) y))
  ** match: (@x @y) failed to match object (2 2)
match is nothing but a macro; application code could supply an equivalent, depending only on what is publicly documented.

Syntactically, the variable terms in (@x @y) are in the same category. Yet x is interpreted by the pattern matcher as a bound variable, whose value matches the corresponding object; whereas y is interpreted as a free variable to be lexically bound to the corresponding object.

You just need a macro system with environment parameters, and a defined API into them.

With help from the macro system, we could write an interpreter such that (let ((a 1) (b 2)) (interpret '(list a b))) will yield (1 2). interpret can't be a function; it has to be a macro which analyzes the argument for variables and creates a bridge between those variables and the surrounding lexicals at the point where interpret finds itself. The interpret macro transforms the code somehow and then hands it to an interpreter function.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#99

Post by lisper »

Y_Y wrote: post #92
kazinator wrote: post #76

Earlier quoted context omitted.

> An evaluated term can be evaluated again, yielding something different. Yes, and a Mogensen-Scott encoding can be Mogensen-Scott-encoded again, requiring two rounds of decoding, and so on. Multiple rounds of encoding and evaluation seem inescapable of you have the entanglement of homoiconicity. The quote operator in Lisp is designed exactly right. In mathematics there are literals like the number 3 or the set {}. T…

What's so special about "literals"? They must be symbols in the sense that they can be evaluated. The fact that you've defined them so that they evaluate to something indistinguishable from the unevaluated form is neat, but it doesn't seem to me fundamental. We could have a lisp where you aren't allowed to evaluate a raw number, it would just be a little more awkward.

One could also have symbols that evaluate to themselves rather than some bound value. In fact, Common Lisp has exactly that: keywords.

Re: Show HN: LambdaLisp – A Lisp interpreter that runs on lambda calculus

#100

Post by kazinator »

lisper wrote: post #95
tromp wrote: post #90

Earlier quoted context omitted.

> People can actually write useful programs in Lisp. I find programming in Haskell much more pleasant. Using car/cdr feels rather primitive compared to pattern matching. > Lisp matters because it is a local maximum on the ratio of real-world utility to the size of the formalism. I feel that role is better served by Haskell, which is basically typed lambda calculus with syntactic sugar on top. Ben Lynn's awesome work…

> I find programming in Haskell much more pleasant. Sure, but that misses the point. Some people like Java. Some like Perl. Some like C++. But, none of these languages come close to Lisp's ratio of utility vs size. So the fact that some people gravitate towards Haskell means nothing in and of itself. (Also, and I mean this with the utmost respect, your brain doesn't work like most people's brains.) > Ben Lynn's aweso…

> If you have structured data, that data should be contained in structures, not cons cells.

There is pattern matching on structures. If you switch from conses to structures, the relevance of pattern matching doesn't go away.

Types divide the data into categories, but the categories don't capture all the variation among the instances.

Pattern matching in functional languages is mostly done on algebraic types.

Post reply on HN