Language syntax specification

The syntax of a language can be defined by a grammar.

Backus–Naur form (BNF):
Simplified example:

Values: 
v ::= #t | #f | n 
e ::= v | (+ e1 e2)

n is a number.
::=, | are grammar meta-syntax
| separates productions
v and e are recursive (non-terminal) metavariables

We can read this in English as:
"An expression e is one of:
– Any value v
– Any addition expression (+ e e) of any two expressions

Real world example: WebAssembly

Real-world languages, such as WebAssembly, have their syntax defined via BNF.

Context for Racket

Some history:

• LISP: List Processing language, 1950s-60s, MIT AI Lab.
  • Created for artificial intelligence use cases
  • Metaprogramming and programs as data! More on this later.
• 1970s: Scheme MIT AI lab.
  • Still motivated by AI, more functional. Lexical scope (more on this later!)
• 1990s: Racket, PLT group
  • Designed for language design, education.

Examples of Racket: basic expressions, strings

See files at the end of these notes.

Structural recursion and recursive data types

Let's walk through an example of how recursive definitions can naturally occur.

How do I define my descendents?

Data structures in Racket are most commonly defined recursively. The core data structure in Racket (and LISP/Scheme before it) is a list.

A list is either:

• the empty list
• the cons of an element and a list

Note: this is similar to a linked-list in other languages.

At a high level: in memory, a special value (usually the null pointer, at a lower level) is the empty list. Cons is represented by the value adjacent to a pointer to the remainder of the list. We can think of cons cells as representing a pair of values.

In Rackets, we have:

cons : construct one cell of a list.
empty? : checks if a list is the empty list
cons? : checks if a list is a cons cell
first : the first element of a list (the first element of a cons cell)
rest : the remaining elements of a list (the second element of a cons cell)

list shorthand

Bindings

A definition binds a symbol to the value of some expression.

Racket by example

Quick example: sum a list of numbers

(define (sum l)
  (if (empty? l)
      ; base case: the empty list has size 0
      0
      ; otherwise, add the current element with the sum of 
      ; the rest of the list
      (+ (first l) (sum (rest l)))))

Group work

;; my-append : (listof number) (listof number) -> (listof number)
;; Input: two lists of numbers
;; Output: a single concatenated list of number

(define (my-append l1 l2)
 (if (empty? l1)
      ; base case: the first list is empty
      l2 
      ; otherwise, recur on the rest of the first list
      (cons (first l1) (my-append (rest l1) l2))))

In class Racket file:

#lang racket

; A list with 2 elements
(cons 1 (cons 2 empty))

; Bind the variable a to a list with 4 elements
(define a (list 1 2 3 4))

; Bind the variable b to a list with 4 elements
(define b (list 21 22 23))

; The sum of a list of numbers
(define (sum l)
  (if (empty? l)
      ; base case: the empty list has size 0
      0
      ; otherwise, add the current element with the sum of 
      ; the rest of the list
      (+ (first l) (sum (rest l)))))
      
; Example: the substring from index 1 (inclusive) to index 2 (exclusive)
(substring "wellesley" 1 2)

Some common Racket mistakes:

;;Mistake 1: Wrap leaf values in parens: (17)

(#t)

;;Mistake 2: Use operators in infix rather than prefix position

(1 + 2)

;;Mistake 3: Put arguments in parentheses with function name outside

(+ 10 avg(3 7))

;;Mistake 4: Use unexpected keywords

(if (< 1 2) then (+ 3 4) else (* 5 6))

;;Mistake 5: Omit parentheses for non-leaf node

(define (abs n)
  if (< n 0) (- 0 n) n)