Lambda Calculus and Lisp, part 1

tosh

The Byte magazine referenced in the article:

Byte Magazine Volume 04 Number 08 - LISP

https://archive.org/details/byte-magazine-1979-08

codr7

I certainly appreciate the theoretical beauty of lambda calculus, but I do wonder what the point is from an modern implementation perspective.

Most hobby Lisps I run into seem to be more of a lambda calculus rite of passage than aiming for practical use.

I've implemented several Lisp interpreters myself in different languages, very much focused on practical use, and they don't look anything like this.

https://github.com/codr7/eli

gryfft

An argument from Justine Tunney's LC implemetation [1]:

> Programs written in the binary lambda calculus are outrageously small. For example, its metacircular evaluator is 232 bits. [...] Something like this could have practical applications in compression formats, which need a small busy beaver that can produce large amounts of data. It's also just downright cool.

> For example, if you built a compression tool you could have it encode a file as a lambda expression that generates it. Since it's difficult to introduce a new compression format that most people haven't installed, you could prefix the compressed file with this 383 byte interpreter to get autonomous self-extracting archives that anyone can use.

I partway expect @tromp to show up in this thread, but see his excellent site[2] for discussion of the algorithmic information theoretical applications of LC, exploration of Kolmogorov complexity, etc.

  1. https://justine.lol/lambda/
  2. https://tromp.github.io/cl/cl.html

sgarland

Every time I read anything by jart, I am reminded that there is a level of intellect so far above most that it doesn’t even make sense.

“I shall write a brainfuck interpreter in Lambda Calculus for fun.” Sure, sure, as one does.

codr7

Very interesting, thank you!

codr7

Downvotes?

HN never ceases to surprise me!

Traubenfuchs

I remember having memorised lambda calculus solving techniques to pass my CS exams on paper where the 2-forearm wide lines had to be wrapped multiple times.

And now, just like a decade ago, my eyes glaze over when I read about this.

I can easily reason about functions that return functions that return functions but this just completely goes over my head.

lincpa

[dead]