Syntax 1

Students should be able to:

• Give examples of syntax-related language design choices,
• Given some example programs, propose a grammar,
• Given a grammar, write some programs.

When you build a language, the first thing that your language users will see is the syntax; the way that programs are written down.

We need to figure out how to specify what strings correspond to valid programs.

• The form of programs–how programs can be written as text
• There is a rich literature about syntax, and lots of tools for manipulating it
  • See lexing, parsing, formal languages, grammars
  • Unfortunately, a lot of this literature exists because we have good formalisms for thinking about syntax, so it's a case of looking where there is light

• We'll start thinking about syntax by looking at some of the options that language designers have when building a syntax for their language.
• Here's a recursive factorial program written in Python¹:

def factorial(n):
  if n == 0:
    return 1
  return n * factorial(n - 1)

• And here's the same program written in C:

int factorial(int n) {
  return n == 0 ? 1 : n * factorial(n - 1);
}

• These two programs have different runtime behavior of course, but what do you notice about their syntax? What are some of the design choices that differ between the two languages?
  • Python uses whitespace to denote nesting and C uses curly brackets.
  • C requires semicolons to end lines; Python requires the programmer to add a linebreak.
  • In C, we're using a ternary if-then-else and in Python we're using a block based if-then.
  • C requires us to write down types for the function inputs and output, but we'll skip over that for now.
• What are some of the similarities?
  • Both languages use infix operators for comparison and arithmetic.
  • Function calls are written \(f(x)\) and require parentheses around the arguments.
• Why might we prefer one syntax over the other?
  • People often describe Python syntax as "readable" or "natural." Do you find one of these programs to be more readable? Which one?
• Here's a factorial program written in Fortran. Are its syntactic choices more similar to C or to Python?

INTEGER RECURSIVE FUNCTION FACTORIAL(X) RESULT(ANS)
  INTEGER, INTENT(IN) :: X

  IF (X == 0) THEN
    ANS = 1
  ELSE
    ANS = X * FACTORIAL(X-1)
  END IF
END FUNCTION FACTORIAL

• I would say C, because it uses delimiters to define blocks, but it's using a block-based if-then-else construct that looks a bit like our Python code.
• What are some of the new syntactic choices that we can see in this code?
  • We have a new way to delimit blocks: using keywords like END IF. We also have to write the name of the function after END FUNCTION.
  • We have a new way to return from functions: using designated return parameters. In this case, we return a value from the function by assigning it to ANS.
  • We now have to explicitly call out that our function is recursive.
• Moving a little farther afield, this version is written in Common Lisp:

(defun factorial (n)
  (if (= n 0) 1 (* n (factorial (1- n))))

• We have a ternary if-then-else that looks a bit like the C version. We're using parentheses to delimit everything—blocks, function calls, expressions.
• We're using prefix notation instead of infix notation for our arithmetic operators. That is, instead of writing x + 1, we write (+ x 1).
• Look closely at the recursive call. The argument might look like 1 - n, but it isn't! 1- is actually a unary decrement operator! This hints at another syntactic choice: Common Lisp is very flexible about letting us write function and variable names that have symbols in them.
  • Was this a good decision for Common Lisp? On one hand, it's potentially confusing to have symbols in variable names. On the other hand, maybe we should try to give programmers as much flexibility as possible.
• Finally, let's look at a Haskell example:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * (factorial $ n - 1)

• This looks pretty different from the other programs that we've seen so far. What are some of the key differences?
• We're splitting the program definition into multiple clauses. Instead of the if-then-else structure that we saw in the other programs, we have one clause that handles the \(n = 0\) case and one clause that handles \(n \neq 0\).
• Function applications look pretty different. We don't need parentheses around the arguments anymore, and we have this strange $ operator in there. The $ operator means "apply," so f $ x should be read as "apply function f to argument x." (We could also write factorial $ n - 1 as factorial (n - 1), which looks a lot more like the function call syntax we're used to.)
• Although it's not visible in this example, Haskell has Python-like significant whitespace, so indentation is an important part of the program structure.

One issue we will run into when designing syntax is ambiguity. A grammar is ambiguous when there are multiple ways to parse a phrase; that is, there are multiple possible syntax trees for a given program. This is a problem when parsing, as parsing deterministic grammars is much more efficient than parsing nondeterministic ones. It's also a problem for the semantics of the language, if the different syntax trees lead to different ASTs and then to different program semantics.

We'll discuss a few common ways that ambiguity arises in programming language syntax.

• https://cs.lmu.edu/~ray/notes/syntax/
• https://cs.lmu.edu/~ray/notes/syntaxdesign/