Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Simplified λ-evaluations
Description Lambda calculus is the main theoretical core of functional languages. It is based on evaluating A The occurrences of variable ‹ Evaluation of - Constant is evaluated to itself,
- Function definition evaluates to itself,
- Function application (‹
*function*›)‹*argument*› is evaluated as follows: first, the ‹*function*› is evaluated to*L*‹*var*›.‹*body*› or something else. In the latter case, the ‹*argument*› is evaluated, and the whole function application evaluates to (‹*evaluated function*›)‹*evaluated argument*›. If the ‹*function*› evaluates to*L*‹*var*›.‹*body*›, the ‹*argument*› is not evaluated, but all unbound occurrences of variable ‹*var*› inside of the expression ‹*body*› are directly replaced by (substituted with) the argument ‹*argument*›. The result of the whole evaluation of function application is then the evaluated ‹*body*›, after the substitution was performed.
We limit the expressions to contain a single-character lowercase ( Here are some examples of evaluation of simple
Note that the scope of the variable next to
The body of the
Finally note that our evaluation is simplified as compared to the real
The Department of Programming Languages decided to implement a new functional language. However, they first need a core engine that will evaluate Input The input contains set of Output The output should contain the result of evaluation of the expressions on the input in the same order as they appear in the input including the last line. If the expression leads to more than 1000 function applications, the line should contain single word “ Sample Input Lq.q ((Lx.Ly.(x)y)Lz.z)Lq.q (Lx.x)x ((((Lm.Ln.Lf.Lx.((m)f)((n)f)x)Lo.Lt.(o)t)Lu.Lv.(u)(u)v)a)b (Lx.(x)x)Lx.(x)x (q)(Lx.Lx.x)z z Sample Output Lq.q Lq.q x (a)(a)(a)b unterminated (q)Lx.x z Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator