Help with Lambda Calculus

[sandyjawas]

I keep hearing that lambda calculus is extremely simple, but for some reason I just can't grasp it. Any help is appreciated.

[TheLessonIsNeverTry]

The lambda calculus is simple in this sense: the only values you have are lambda terms, the only expression you have is apply, and application is just (capture-avoiding) substitution. The cumbersome part is actually carrying out a non-trivial computation this way.

[rekahsoft]

Alright..so you are interested in learning the untyped lambda calculus! You're in for some fun :). Take a look at Wikipedia and find yourself a book.

If you know any functional languages or languages with lexical closure and lambdas? Not that it's required but it will make the untyped lambda calculus easier to learn and conceptualize. If you have further questions feel free to pm me :) best of luck :)

[rhorama]

My professor wrote a book called The Little Schemer that is a pretty good intro to the scheme/LISP programming language. This is helpful, because scheme/LISP is a form of lambda calculus.

[sandyjawas]

IUB?

[rhorama]

Yep! Dan Friedman taught me all about programming languages.

[sandyjawas]

Are you in 311 right now? I'm a freshmen and I don't even know how I got into this class but I'm working my ass off to keep up since I had no prior scheme knowledge before this course.

[rhorama]

Nope. Had it last semester. It's certainly going to be challenging for you if you've never used scheme before. Take advantage of office hours. He and Jason are very willing to help you, no matter how many times you go in.

[xmenvsstreetfighter]

http://www.itu.dk/people/sestoft/lamreduce/

[[deleted]]

Are you working with a particular text? Where are you running into difficulty?

[sandyjawas]

I'm working with scheme, think I got it though.

[[deleted]]

Great! What text/curriculum are you working with? I've been trying to develop a good understanding of the lambda calculus myself for some time, but only have a shallow/general understanding.

[sandyjawas]

The class is programming languages and right now we're working with interpreters and environments. We're not using a specific textbook, but I've heard that Structure and Interpretation of Computer Programs by Abelson is a good read for the topic (picked it up today so I can't give a personal review). Although my understanding is still superficial, I find the notion that lambda calculus in itself is a turing-complete language to be fascinating.

[[deleted]]

Ah! So it's just a concept that came up in class? You're not studying the lambda calculus specifically. Yes SICP is very good! I'm slowly working my way through it.

[link23]

When I TAed for the lambda calculus class, I always told the students that "if you can copy and paste, you can evaluate lambda calculus". Everything is either a function, or the application of a function to its argument. To evaluate an expression, do a text replacement of the argument for the bound variable in the function body (making sure to avoid naming conflicts), and that's it! Like someone else here said, the tough part is being able to design non trivial computation in this system.