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
Improve this question
4
  • 4
    Java 8 already has lambda's. Are you trying to write a compiler? If so, say so in your question.
    – candied_orange
    CommentedSep 12, 2016 at 7: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
    CommentedSep 12, 2016 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
    CommentedSep 12, 2016 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
    CommentedSep 14, 2016 at 17:02

1 Answer 1

Reset to default
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.

Improve this answer
6
  • And, may I know what I should then do with the parse tree? Sorry kind of ignorant to this -.-
    – nathan De Guia
    CommentedSep 15, 2016 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).
    – Periata Breatta
    CommentedSep 15, 2016 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
    CommentedSep 15, 2016 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
    CommentedSep 16, 2016 at 1:17
  • @JörgWMittag - good point, although he does also say he "needs to manipulate them with beta reduction, alpha conversion, etc".
    – Periata Breatta
    CommentedSep 16, 2016 at 6:30

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.