I've written a Lambda Calculus evaluator, available in the archives; it's based on the Spreadsheet app that comes with the Prime. The spreadsheet is used as a dictionary of Lambda Calculus terms (using De Brujin indices, instead of normal notation, for now) and simple identifiers. These identifiers are used to reference the lambda expression on the Symb page. The Symb page supports evaluating the application of one function to another (and then to a third, optionally).

Screenshots and instructions are included, as well as a variety of terms in the dictionary/spreadsheet. Church Numerals are recognized automatically.

Future versions will support standard notation, using De Brujin indices only behind-the-scenes, as well as free-form entry of terms to be evaluated.

If interested in this sort of thing, let me know your thoughts.

I see there's some interest in programming the HP Prime in this forum. I'll follow up with a description of this version of the application's code.

It looks awesome, even though I'm not quite sure what applications this is for, in the math world. I'm sure someone, somewhere out there really appreciates the effort!

And yes, we definitely have some people here very very interested in tackling the Prime as a programming platform!

Very cool - do you do any tricky compilation/optimization stuff before evaluating, or is it a pretty straightforward interpreter?

It's definitely an interpreter.

Lambda calculus is all about substitution and pattern matching. I took advantage of the HP Prime's List data type. Lists can contain any data type, including other lists. Lambda expressions are created in Lists from the Strings in the dictionary/spreadsheet with Paranthesized sections becoming a nested list. In this format, it's straightforward to examine each list, recursively examining nested lists, when performing the substitutions a 'function application' entails, when looking for more possible betareductions, and even when examining an expression to see if it's a Church Numeral.

This app actually uses the global list variables, L0-L9. L0 is always populated with the result of the last evaluation. The View key has an option to perform a single betareduction on L0, if you want to step through something.

The other thing that is a little extraordinary is the use of De Brujin indices. Normal notation for lambda expressions uses small letters to represent variables/functions like "λnfx.f(nfx)". De Brujin notation indexes each variable with a number indicating how many lambda-scopes exist between it's location and the lambda it belongs to. So, the above Successor function would appear in De Brujin notation as "λλλ2(321)". De Brujin wrote rules for increasing and decreasing numbers as substitutions are made; so I simply implemented his notation.

To really look into λ-Calculus...
http://en.wikipedia.org/wiki/Lambda_calculus

λ-Calculus has been called the "assembly language of math". It all boils down to pattern matching and substitution of abstract functions. If you agree that certain functions mean certain things, like the Church Numeral expressions represent the natural numbers, you can devise functions that manipulate the expressions in a logical way.

One such function, for instance, finds the successor/next Church numeral. Going from there, it's trivial to create a PLUS expression that takes two parameters and returns the result of their addition. A multiplication function isn't that much more difficult. The Predecessor function is a bit tricky to figure out from scratch, but with it one can create a Subtraction function. Division is pretty tricky. But these and more are all possible, without any math rules.

Predicate logic can also be recreated with λ-Calc, with only pattern matching and substitution.

That's a summary of why I found λ-Calculus so intriguing.

Typically, studies of λ-calculus are about 'thinking about' λ-calculus and proving various theories about functions, as opposed to being about the actual λ-calculus, itself. But the actual λ-calculus, not 'theories about λ-calculus', was very influential on the notion of computer programming, in general. Turing proved λ-calc is Turing Complete; it's able to express any algorithm. John McCarthy implemented the actual λ-calc as LISP, which is why LISP retains the keyword LAMBDA for creating an anonymous function.

This little programming project is mainly for fun and part of the experience (for me) includes learning new things like the above.

This single fact already makes me want to further explore the BASIC language on the HP Prime. That flexibility is entirely missing from TI-BASIC, Casio BASIC, and every interpreted language I've used on a graphing calculator to date. Is it also true of HP's older calculators, or is that something new for the Prime? By the way, very nice job on this program, and thank you for uploading it to the Cemetech Archives. I hope you'll keep us abreast of your latest and greatest Prime projects.

To widen the pool of users and potentially get some comments about optimization from seasoned HP calculator developers who don't attend Cemetech, I suggest you post your program to MoHPC (hpmuseum.org) as well

Yes -- for sure as far back as the HP48, and possibly even the HP28S. The objects for these RPL calculators were distinguishable based on their prologue. A list was simply a collection of objects surrounded by a prologue called DOLIST and an "end" indicator (called SEMI). You either had atomic objects or composite objects (objects composed of atomic objects or other composite objects).