The differences between the mathematical notation and BNFC stem from the following observations. The reason for writing `Exp ::= Exp Exp1` instead of the simpler `Exp ::= Exp Exp` is the same why we wrote `Exp ::= Exp " " Exp1` instead of `Exp ::= Exp " " Exp` when defining a grammar for arithmetic expressions. But `\` is a special character that needs to be escaped, so writting `\\` in the BNF grammar has the effect that you can write `\` in the programs. Accordingly, we would have liked to write, in the first line, `Exp ::= "\" Id "." Exp`. Since $\lambda$ is not an ASCII character, we write `\` instead. **Remark:** Most of the notation has been explained before. **Definition 2:** The lambda calculus is the language defined by the folloing BNFC grammar Each rule gets a name and goes on a separate line. In BNFC, we write down the same definition slightly differently. This is achieved, as in the example of arithmetic expressions in the previous lecture, by putting this information directly into the grammar. In particular, we need to be more precise about the rules that allow us to drop parentheses. So we need to complicate notation in order to tell the machine precisely how to transform a string into a tree. But programs are meant to be read by humans and by machines. **Remark:** For a human reader it is fine to think of the grammar as describing trees. (x y z))) ((a b) c)$ without changing the tree denoted by the expressions. **Exercise:** Use the convention on parentheses described in the previous remark in order to eliminate as many parentheses as possible from $(\lambda x. For example, we can abbreviate $(a b) c$, but not $a (b c)$, to $a b c$. To make writing and reading easier on the eye there are additional rules that allow us to drop parentheses. We add parenthesis if we want to disambiguate a string as in $$(\lambda x. **Remark:** The grammar $\ e ::= \lambda x.e \mid e e \mid x$ defines the syntax of lambda expressions as trees. In other words, the variables of lambda calculus are not memeory cells. In particular, there will be no assignment of values to variables. The only operation we will use on names will be testing whether two names are equal or not. In other words, we juxtapose (write next to each other) the function and its argument. (Function Application.) In a C-like language we would write function application as In other words, the meaning of $\lambda x.e$ does not depend on $x$, the name $x$ has been abstracted. We will see later what to do about the ` 1`.įunction definition is called abstraction since in the same way as the definitionsĭenote the same function if $e'$ arises from $e'$ by replacing every occurrence of $x$ by $y$. No types, that is, `plus_one(x)` which we write as $\lambda x. If we compare this with a C-like language (Function definition.) $\lambda x.e$ is a function. **Remark:** We will comment on the three clauses in turn. What are the advantages of the shorter notation? **Exercise:** Compare the three bullet points above with $\ e ::= \lambda x.e \mid e e \mid x\. Where $x$ ranges over an infinite set, the elements of which are called variables. **Definition 1:** The $\lambda$-calculus is the language defined by the grammar In textbooks and articles, one often finds the following Recall from the () how to use define a language using BNF. ![]() **Variables:** The basic programs are just the variables. **Application:** If $e_1$ and $e_2$ are programs then $$ e_1 e_2$$ is the program which applies the function $e_1$ to the argument $e_2$. We will explain this in more detail below. This is called abstraction, because the program $\lambda x.e$ does not depend on $x$ anymore, $x$ is abstracted away. $$\lambda x.e$$ is the program (or function), which has as a formal parameter $x$. **Abstraction:** If $e$ is a program (also called an expression in lambda calculus), possibly containing a variable $x$, then Recall from the (), that lambda calculus has only three programming constructs: To this end we first have to give a grammar, which specifies all the legal programs that can be written in lambda calculus. We will use what we learned in our () in order to define our first programming language, the ***$\lambda$-calculus*** or ***lambda calculus***. ![]() Let me know if you have questions about them. **Warning:** Parsing and Lambda Calculus may well be the most difficult concepts we will meet in the course. "legal program" or "well-formed program" for emphasis. But we sometimes say "syntactically correct program" or **Remark:** A program is by definition syntactically correct (otherwise it is not a program in the first place). construct the abstract syntax tree of a lambda calculus program, check that a string is a lambda calculus program, **Learning Outcomes:** After having worked through the exercises and homework, students will be able to ![]() ![]() If you are accessing this file in GitHub, read instead ().
0 Comments
Leave a Reply. |