Instructions

You must complete all of these steps to receive credit.

1. Download the AT2 template.

2. Rename the file <firstname>_<lastname>_AT2.tex, filling in <firstname> and <lastname> with your first and last names, respectively.

3. Fill in the sections marked TODO (removing the TODO markings) as directed in the assignment.

4. Ask at least three questions about the lambda calculus, this assignment, or feedback in general (filling in the sections marked TODO).

5. Submit both your source file, <firstname>_<lastname>_AT2.tex, and the compiled pdf <firstname>_<lastname>_AT2.pdf to this google form by 2019-10-05 End of Day.

Help

• For help with $\mathrm{\LaTeX}$, here is the $\mathrm{\LaTeX}$ Resources Page.
• If you need help with the Lambda Calculus, there are many resources you can google. I’m working on a page to put in Chapters. Until that’s done, these seem pretty good:
  • The Wikipedia page on Lambda Calculus
  • https://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf (Just part 1, the first three and a half pages).
• If you’re still having trouble, feel free to contact me at sristic[at]seas[dot]upenn[dot]edu. Be sure to start the subject line with “BOOTS:”

Assignment

Complete all points to the best of your ability. If you get stuck and have tried everything you can think of to get unstuck, explain your thinking, demonstrate effort and time.

1. Convert these expressions from “mathematical” function notation (where $f(x, y)$), to the “lambda” function notation (where $f\ x\ y$). Give both the minimally—e.g., $f\ x\ y\ z$—and fully—e.g., $(((f\ x)\ y)\ z)$— parenthesized forms.

   $\begin{align*} a &= s(x,g(h(z))) \\ b &= f(x,f(y, z),g(h(z))) \\ c &= f(f(f(f(x, y), z), w), v) \\ d &= j(g(z),x) \end{align*}$As an example, see

   $$\begin{align*} \mathrm{example} &= f(x,g(y)) \end{align*}$$

   which has solution

   $$\begin{align*} \mathrm{example} &= \boxed{f\ x\ (g\ y)} = \boxed{((f\ x)\ (g\ y))} \end{align*}$$

   with $\mathrm{\LaTeX}$ code

    \begin{align*}
    \mathrm{example} &= f(x,g(y)) = \boxed{f\ x\ (g\ y)} = \boxed{((f\ x)\ (g\ y))}
    \end{align*}
   

   NOTE: for spaces in function application ($f\ x$ vs $fx$): with single symbol identifiers (e.g., $f, x, y, g$, as in all the problems on this assignment) it doesn’t really matter if you use spaces or not. It only matters when you have variable names that are more than one symbol, as they are in programming languages, as we’ll see, where the space is always manifested. For this assignment, therefore, you can put spaces in (as I’ve done in the example solutions), but you don’t have to. If you want to include spaces, the $\mathrm{\LaTeX}$ command is “\” (a backslash); however, you must put at least one space right after it, or it will gobble up the adjoining word (interpreting it as the name of a command), so f\x is bad, f\ x is good (and so is f \ x).

2. Using English, describe a procedure, as clearly, concisely, and completely as you can, to determine whether a triangle $ABC$ in the Cartesian ($x-y$) coordinate plane contains the origin $(0,0)$. You can assume that you are given the $A(x_A,y_A), B(x_B,y_B), C(x_C,y_C)$ coordinates of each of the vertices $A,B,C$ of the triangle and that the values of the coordinates are real numbers.

   You can describe the procedure with the help of any standard mathematical operations on real numbers (e.g., $<,>,\overset{?}=,+,\times,$ etc). Be precise enough so that, if given concrete numbers for the coordinates, it would be clear how to compute the answer.

   For example, for coordinates

   $$\begin{align*} &A(-340,495), B(-153,-910), C(835,-947) \\ &X(-175,41), Y(-421,-714), Z(574,-645) \end{align*}$$

   Triangle $ABC$ contains the origin, while triangle $XYZ$ does not.

   (Adapted from Problem 102 of Project Euler)