6720번 - Simplified λ-evaluations 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1 | 0 | 0 | 0.000% |
문제
Lambda calculus is the main theoretical core of functional languages. It is based on evaluating λ-expressions.
A λ-expression is a string of characters consisting either of 1) a single constant (for example t), or 2) a function definition written as L<var>.<body>, where L denotes λ, <var> is always some variable (for example x) that can occur in the <body>, which is again some λ-expression, or 3) an application of some <function> (for example f) to an <argument> (for example x), in our case written as (f)x, both <function> and <argument> are λ-expressions.
The occurences of variable <var1> in an expression E are called bound, if they are inside of the <body> of some sub-expression L<var1>.<body> of E. Variable occurences that are not bound are called unbound.
Evaluation of λ-expression results in another λ-expression and is performed using the following rules:
- 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 occurences 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 (a ... z) variables and constants only. Sometimes the evaluation never stops. Your program should perform at most 1000 function applications when evaluating any λ-expression. During all evaluation steps, the evaluated λ-expression will not exceed 10000 characters.
Here are some examples of evaluation of simple λ-expressions (shown in several steps, the text behind ; is a comment):
1.
(Lx.x)y ; x <- y
y
2.
((Lx.Ly.(x)y)Lz.z)Lq.q ; x <- Lz.z
(Ly.(Lz.z)y)Lq.q ; y <- Lq.q
(Lz.z)Lq.q ; z <- Lq.q
Lq.q
Note that the scope of the variable next to λ covers only the body of the lambda expression, and the same variable can occur at other places of the expression, for example:
3.
((Lx.x)(Ly.y)Lx.x)x
((Ly.y)Lx.x)x
(Lx.x)x
x
The body of the λ-expression can contain unbound variables - constants:
4.
(((Lx.Ly.q)Lz.t)r)u ; x <- Lz.t
((Ly.q)r)u ; y <- r
(q)u
Finally note that our evaluation is simplified as compared to the real λ-calculus: when the argument is substituted for all unbound occurences of some variable during function application, some of the variable occurences in the argument that were previously unbound can become bound... This is normally solved by renaming all the variables in the argument before the function application, and keeping track of correct substitutions. In this problem, you don't need to take care of this.
5.
((Ly.Lx.y)x)w ; y <- x
(Lx.x)w
w
The Department of Programming Languages decided to implement a new functional language. However, they first need a core engine that will evaluate λ-expressions. Write a program that will read a set of expressions from the input and output their evaluations.
입력
The input contains set of λ-expressions, one per line. Only the last line contains the expression consisting of a single constant z. You can assume that the input is correct.
출력
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 “unterminated".
예제 입력 1
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
예제 출력 1
Lq.q Lq.q x (a)(a)(a)b unterminated (q)Lx.x z
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호