:::warning
**Announcements**
- Assignment 0 due 11:59pm Thursday.
- For this week: (all L037)
- My help hours 6:30-8:30pm tonight (Monday), 11am-12pm Thursday.
- Grace 3:30-5pm Tuesday
- Emily 3-5pm Friday
:::

:::info
**Agenda**
- Why study functional languages?
- Syntax vs. semantics
- Defining language syntax
- Introducing Racket, DrRacket
- Data in Racket:
- Bools, numbers, cons, lists, oh my!
:::

# Why study functional languages?

Why should we study these languages, when the many popular programming languages are primarily imperative?

Functional languages:
- I would be personally sad if you only saw Python and a bit of Java in your Wellesley degree :(. Seeing more flavors of languages helps you pick up new languages in the future!
- Are easier to work with, because they are more like math. In particular, they are easier to implement, as you will start doing on Homework 3!
- They help you practice important skills like:
- Avoiding mutation (one example of a *side effect*).
- Recursion

These skills are important because (1) they are less error prone in many cases, (2) they can lead to performance improvements, e.g., by enabling parallel code, and (3) some data and tasks are much easier to use recursion on, but you have had less practice with it (e.g., graph algorithms like depth first search).

# What is a PL? Syntax + semantics

## Syntax

A programming language’s syntax defines its form.

Syntax tells us:
- What are the valid expressions in the PL?
- How can we compose them to make bigger expressions?
- Concrete syntax: style choices (e.g., { } versus white space)

## Semantics
A programming language’s semantics defines its meaning.

- Semantics tells us:
- How do we evaluate expressions in the PL?
- How will this program behave?
- What values does it produce?
- What "side-effects" does it have?
- Are expressions well-typed?
- What is the scope of a variable? More on this Thursday.

### Syntax vs semantics example in English

Good syntax, bad semantics:

`colorless green ideas sleep furiously`

# Language syntax specification

:::success
How are languages *informally* defined? For example, how did you first understand what "Python" is?
:::

:::spoiler Think, then click!

The languages you've learned so far have likely been via informal definitions!

For example:
- Seeing examples of Python in CS111, Java in CS230.
- Possibly grouped by feature, examples of syntactic forms.
- By providing programmers an implementation that yells at them if a provided program does not satisfy the expected syntax.

:::

The syntax of a language can also be defined formally (that is, precisely and unambiguously) by a *grammar*.

For the field of PL, grammars are usually given in [Backus–Naur form (BNF)](https://en.wikipedia.org/wiki/Backus–Naur_form):

We'll start with a very simplified language (a tiny subset of Racket), given by a BNF grammar:

Values:
v ::= #t | #f | n

Expressions:
e ::= v | (+ e1 e2)

`n` is a number. We could specify this as `n` $\in \mathbb{Z}$ or by specifying a [regular expression](https://en.wikipedia.org/wiki/Regular_expression) of digits.
`#t`, `#f` are boolean values, corresponding to *true* and *false*.
`::=`, `|` are grammar *meta-syntax*: they are part of the description of the language, rather than part of the language itself.
`|` separates _productions_
`v` and `e` are recursive (non-terminal) metavariables. `e1` and `e2` recursively refer to `e`.

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

### Expressions vs. values

**Expressions**: well-defined snippets of the language (as defined by the grammar).

Examples of expressions: `1` `(+ 1 2)` `(+ 1 (+ 2 3))`

We typically _do not_ consider snippets of incomplete/invalid syntax to be an expression:
`(+ 1`, `)`, `+ 2 3` are **not** valid expressions in this simple grammar.

**Values**: expressions that cannot be reduced/evaluated any further _in their current form_.

Examples of values in this simple grammar: `#t`, `#f`, `5`

### Syntax does not define semantics

In our example BNF grammar, nothing stops us from writing the following "good" expression syntax that tries to add a number and a boolean:

`(+ 1 #f)`

The grammar allows this as valid *syntax*, but does not specify the *semantics* of whether this should be a meaningful program in the language.

### Real world example of a grammar: WebAssembly

Real-world languages, such as WebAssembly, have their syntax defined [via BNF](https://webassembly.github.io/spec/core/_download/WebAssembly.pdf).

# Context for Racket

Like our simple example grammar above, Racket also uses parentheses `()` to group expressions, uses `#t`/`#f` for booleans, and uses pre-fix operator notation.

:::info
The Racket syntax is weird! I'm sorry!
Parenthesis for almost everything: `((()))`

You'll get used to it over time. :)
:::

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, "fixed" some rough spots of LISP. In particular, switched to lexical scope (more on this next week!)
- 1990s: Racket, PLT group
- Designed for language design, education.

# Racket by example

Basic arithmetic expressions have the same syntax as our example grammar, with the operator as a prefix and parens grouping expressions.

See the files at the end of these notes for examples.

## Basic bindings in Racket

A definition binds a symbol (the variable name) to the value produced by some expression.

(define x 1)

## Basic Racket expressions avoid side effects

A side effect is when an expression does something *other than* producing a value.

## Structural recursion and recursive data types

Often we want programs to process data, but functional programming doesn't emphasize loops with mutable loop indices. Instead,
canonical functional programming uses *structural recursion*, instead of mutation.

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

:::success
How do I as a human define the descendants in my family tree?
:::

:::spoiler Think, then click!

Recursively!

Base case: me.
Recursive case: the child of my descendant.

:::

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: `empty` (also can be written as `null`)
- the `cons` of an element and a list.

:::success
Have you seen definitions similar to this for data structures in other languages? Which ones?
:::

:::spoiler Think, then click!

This is a similar definition to linked-lists in other languages.

It is *not* the same as arrays in many other languages, like Python and Java. Why not? Arrays have contiguous memory, are primarily being accessed by indices, and don't have the same concept of an empty/null base case.
:::

At a high level: in memory, a special value (usually the null pointer) is the **empty list**.

A `cons` cell is represented by a pair: the value of the element itself, adjacent to a pointer to the remainder of the list.

In Racket, we have:

`empty`: constructs an empty list.
`cons` : constructs one cell of a list.
`empty?` : checks if a list is the empty list
`cons?` : checks if a list is a cons cell
`first` : accesses the first element of a list (the first element of a `cons` cell). Historically, called `car`.
`rest` : accesses the remaining elements of a list (the second element of a `cons` cell). Historically, called `cdr`.

The `list` shorthand can be used to construct a `list` without rewriting `cons` each time:

The following all produces the same value:

(cons 1 (cons 2 (cons 3 empty)))
(list 1 2 3)
'(1 2 3)

Note the quote symbol `'` stops evaluation, turning things inside the parens into values.

`'(+ 1 2)` is a value, if we try to evaluate it in the current form, we get back the same thing.
`(+ 1 2)` (without the quote) is not a value, if we try to evaluate it in the current form, we get `3`, which is a value.

# Racket by example

Let's try to write our first interesting program: summing a list of numbers. We'll assume we take a single argument, a well-formed `cons` list.

Note that `if` expressions in Racket have the form: `(if e1 e2 e3)`.

; Assume the list is all numbers, valid formed list
;;    Parens after the define tell us this is a function
;;    named sum, with one arg named l
(define (sum l)
  (if
      ; This is my condition, checking for the base case
      (empty? l)
      ; This is the consequent/then case
      ; Here, our base case.
      0    ; if I had parens (0) this would give an error
      ; This is my alternate/else case
      ; Here, the recursive
      ; The list is NOT empty, the first of the list is a num
      ; We combine that with the partial computation on
      ; the rest of the list via +
      (+ (first l) (sum (rest l)))))

:::info
Student question from class: when we just write 0, what does that do?
:::

:::spoiler Think, then click!
You'll notice that Racket has no `return` keyword! Instead, functions just "evaluate to" their result.

`0` on its own, in this position within the `if` expression, tells us that in the base case, the function evaluates to `0`. We don't need to write `return`.
:::

# Group work: `my-append`

;; my-append : take two lists, produce the list that
;;             appends them
;; Input: two lists
;; Output: a single concatenated list
;; Tip: it may help to draw out the two lists as linked
;;     lists.

;; Example:
;; (my-append (list 1 2) (list 3 4))
;;   evaluates to value
;;   '(1 2 3 4)


(define (my-append l1 l2)
 (if (empty? l1)
      ; Base case: the first list is empty
      l2
      ; Otherwise, use a cons cell, recur on the rest
      ; of the first list
      (cons (first l1) (my-append (rest l1) l2))))

# More Racket examples

:::danger
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)

Another example we'll go over *next class*, but you optionally can read over if you'd like to simplify your `if` expressions on Assignment 0.

Write a function that returns 0 if numbers are equal, 1 if a > b, -1 if a < b.

(define (compare a b)
  (if (= a b)
      0
      (if (> a b)
          1
          -1)))

As we'll see next class, we can also use the `cond` syntax form to do something similar to if-elseif-else blocks in other languages:

(define (compare a b)
  (cond
    ((= a b) 0)
    ((> a b) 1)
    (else -1)))