Good day, I'm trying to find a way to program a lambda expression generator in java with this context-free grammar, and I would want to ask ; what would be the best way to tackle this problem and be able to manipulate them with basic lambda calculus functions such as beta reduction, alpha conversion, etc.?

I tried doing this with Strings, but was advised to discontinue because using strings will limit me to what I can do.

Here's the Context Free Grammar I got over the internet:

 <expr>   ::=  <var>
             | <func> <arg>              # This is an application.
             | lambda <var> . <expr>     # This is an abstraction. 
 <func>   ::=  <var>
             | (lambda <var> . <expr>)    
             | <func> <arg>
 <arg>    ::=  <var>
             | (lambda <var> . <expr>) 
             | (<func> <arg>) 
 <var>    ::= a| b| .... | Z
  • 4
    Java 8 already has lambda's. Are you trying to write a compiler? If so, say so in your question. Sep 12 '16 at 7:32
  • I'm actually trying to create a program which generates/prints Lambda Expressions, not utilizing it as a tool or something. Sep 12 '16 at 11:35
  • So you are trying to produce examples of expressions that conform to this grammar, for example lambda f . f (g x)? Like a reverse parser? Do you want to turn a data structure describing the expression into a string, or do you want to generate randomly chosen examples?
    – amon
    Sep 12 '16 at 13:20
  • I want to turn a data structure describing the expression into a string, yeah. on that latter, what do you mean? choose from a list or something? Sep 14 '16 at 17:02

The simplest approach would be to use a parser generate (perhaps antlr) to make a parser that produces a parse tree. You can then perform your reductions and conversions on the parse tree, rather than on a string, which should make them much simpler.

  • And, may I know what I should then do with the parse tree? Sorry kind of ignorant to this -.- Sep 15 '16 at 9:52
  • I actually find the notion that somebody is familiar with terms like "beta reduction" but not parse trees extremely surprising! I'd suggest looking at an online tutorial for writing a lambda calculus evaluator (e.g. cs.cornell.edu/courses/cs6110/2014sp/handouts/sestoft.pdf gives examples of different approaches to reductions and variable substitutions using a tree structure in ML; if you're not familiar with ML you may have to search for something similar in a language you are fimiliar with). Sep 15 '16 at 14:05
  • Actually we were taught this, but not as extensively as you might expect. We were taught how to create these stuff, but were not taught how to apply them. Which, as a result, made us forget these things so quickly.. Our professor on Lambda suggests that we weren't given enough exposure to Data Structures that we need to actually apply them. Sucks, sorry for my ignorance though - maybe it's just me. EDIT: BTW the link on the pdf pointing to an example is dead Sep 15 '16 at 16:46
  • After the latest comment by the OP on the question itself, it sounds to me like he rather wants to write the inverse of a parser, aka "unparser" aka "pretty printer". Sep 16 '16 at 1:17
  • @JörgWMittag - good point, although he does also say he "needs to manipulate them with beta reduction, alpha conversion, etc". Sep 16 '16 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.