6
\$\begingroup\$

The lambda calculus is a system of functional programming. Lambda calculus consists of variables, abstractions, and applications.

A variable is simply a name denoting a function parameter. It is a single letter. An abstraction is a "function literal" of sorts, it consists of a backslash \ followed by a variable name, and then an expression, which is the function body. For example, the function \x.x is a function which takes an argument x and returns x, a.k.a. the identity function. Abstractions can also return other abstractions. For example, \x.\y.x is a function which takes an argument x and returns a new function that returns x.

There is also application. In application, you remove the header on the first value and substitute all instances of the function's argument with the value it is applied to. For example, to apply \x.xx to \y.y, substitute all x's with \y.y's, yielding (\y.y)(\y.y) (Parenthesis may need to be added for clarification.) Applications are denoted in an expression by writing the two values next to each other, where the first is the function to apply and the second is the argument to apply to. For example, you can write xy to apply x to y. However, you may need parenthesis (for example in a(bcd) or y(\x.xx).

The first lambda calculus notation is the one I just described.

\f.(\x.xx)(\x.f(xx))

The second lambda calculus notation does not need parenthesis. It matches the following grammar:

<expression> ::= <variable> || <abstraction> || <application>
<abstraction> ::= "\" <variable> <expression>
<application> ::= "`" <expression> <expression>

Here, a <variable> can be any uppercase or lowercase letter. This is an example of an expression in the second notation:

\f`\x`xx\x`f`xx

Your task is to write a program that takes a lambda calculus expression in the first notation and outputs it rewritten in the second notation.

Specifications

  • Every variable name is 1 letter.
  • Abstractions in the first notation go as far as possible, and application goes left to right: d(abc) -> `d``abc.
  • You do not have to deal with free/bound variables and scoping.

Test Cases

\a.a                                  -> \aa
(\x.xx)(\x.xx)                        -> `\x`xx\x`xx
\x.\y.\z.xz(yz)                       -> \x\y\z``xz`yz
(\S.\K.SKK)(\x.\y.\z.xz(yz))(\p.\q.p) -> ``\S\K``SKK\x\y\z``xz`yz\p\qp
\$\endgroup\$
  • 6
    \$\begingroup\$ You might need to explain what lambda calculus is. You say "the standard, human readable one", but I don't know what it means. Or if that's not important to the challenge, at least explain the format(s). (What's an "abstraction"?, what are free bounds and scoping?, what is "application"?) You make a lot of assumptions about what people know/understand. \$\endgroup\$ – mbomb007 Feb 14 '17 at 16:21
3
\$\begingroup\$

Haskell, 211 197 186 bytes

(Saved 10 bytes by using interact as suggested by @Challenger5, and one more by not having a final newline.)

m(')':r)=([],r)
m s|(a,u)<-e s,(b,v)<-m u=(a:b,v)
f s|(a,r)<-m s=(tail(a>>"`"):a>>=id,r)
e('\\':v:_:s)|(a,r)<-f s=('\\':v:a,')':r)
e('(':s)=f s
e(v:s)=([v],s)
main=interact$fst.f.(++")")

Initially I had a function to perform the whole transformation, but now that is inlined into the main function which makes it a complete program. Dealing with a complete program instead of using a function String -> String at the interpreter also avoids the need to type and read double backslashes. The other functions follow the (simplified) pure functional parsing pattern of returning a parsing result and the unparsed rest of the string. f parses a list of expressions (possibly a multiple application) . It uses a helper function m that also parses a list of expressions and has a list of parses as result. e handles the remaining cases: lambdas, parenthesized expressions, and variables. Instead of generating a parsing tree, we directly generate the desired output.

Try it online!

Using interact ruined clean I/O behaviour. If you don't use the TIO link but run it at the command line of your computer, you have to make sure that there is no trailing whitespace, it would be treated like a variable. You can do something like echo -n '\f.(\x.xx)\x.f(xx)' | ./prog. Alternatively, you could replace the last line by the previous version main=getLine>>=putStrLn.fst.f.(++")").

\$\endgroup\$
  • \$\begingroup\$ I think you can use interact instead of getLine and putStrLn. \$\endgroup\$ – Esolanging Fruit Sep 18 '17 at 4:34
  • \$\begingroup\$ That would (usually) give me an additional \n that I'd need to take care of, and I think I wanted a "normal" input ending with return instead of EOF. \$\endgroup\$ – Christian Sievers Sep 18 '17 at 10:13
  • \$\begingroup\$ I/O without a newline is fine with me. \$\endgroup\$ – Esolanging Fruit Sep 19 '17 at 1:49
  • \$\begingroup\$ And I thought it would need explanation, which I wanted to avoid. I've done it now. \$\endgroup\$ – Christian Sievers Sep 19 '17 at 10:42

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.