1

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
nathan De Guia
  • 41
  • 4
  • 4
    Java 8 already has lambda's. Are you trying to write a compiler? If so, say so in your question. – candied_orange Sep 12 '16 at 07:32
  • I'm actually trying to create a program which generates/prints Lambda Expressions, not utilizing it as a tool or something. – nathan De Guia 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? – nathan De Guia Sep 14 '16 at 17:02

1 Answers1

3

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.

Periata Breatta
  • 962
  • 4
  • 8
  • And, may I know what I should then do with the parse tree? Sorry kind of ignorant to this -.- – nathan De Guia Sep 15 '16 at 09: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. http://www.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). – Periata Breatta 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 – nathan De Guia 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". – Jörg W Mittag Sep 16 '16 at 01:17
  • @JörgWMittag - good point, although he does also say he "needs to manipulate them with beta reduction, alpha conversion, etc". – Periata Breatta Sep 16 '16 at 06:30
  • I just searched google, and yeah I think I need an unparser. But I can't manipulate on it right? – nathan De Guia Sep 21 '16 at 12:22