# Mathematical Foundations for Programming Languages

## Roadmap

1. Concepts of Programming Language: (SF(2018) |TOPL | PFPL) > EOPL(2014) & CSAPP(2016) & CTMCP(2018)
2. Mathematical Foundation: COPL(2019)
3. Type Systems & Type Theory: TAPL(2019) & Advanced TAPL(2020) & HoTT(2019)
4. Formal Semantics: LCISS(2019) & FSPL(2020) & FFPL(2019)
5. Abstract Algebra: Abstract Algebra, The Basic Graduate Year(2019)
6. Category Theory: Category Theory A Gentle Introduction(2019)
7. Lambda Calculus: LCISS(2019) > PLLC(2022) | LCAC
8. Process Algebra: ITPA(2020)
• Pi-Calculus： An Introduction to the pi-Calculus
• CPS：Communicating Sequential Processes
9. Recursive Theory and Recursive Functions: Theory of Formal Systems & COMPUTABILITY, An introduction to recursive function theory(2019)

### Practise:

Personal Answers to Exercises

## Chapter 1

• eq?, eqv?, equal? and = in scheme
• = : numerical equal
• eq? : whether two parameters represent the SAME OBJECT.
the result for two primitive values like 2 and “a” depends on the implementation.
• eqv? : whether same object.
#t if two paramters are identical primitive values.
• equal? : can be used to data structures (lists, vectors) whether they have same elements.
• Conclusion:
= for numbers; eqv? for non-numeric values; equal? for vectors, lists, etc.; DON’T use eq? unless you know exactly what you’re doing.

### Chapter 2

#### 2.1

1. Data abstraction -> interface, implementation
2. Representation-independent
3. Example: nonnegative integers.
Interface:
Constant: zero
Procedures: iszero?, succ, pred
4. Opague <-> Transparent

#### 2.2

1. Kinds of data types:
• aggregate: contains values of other types, e.g. array, record
• union: values are of one or the other of multiple given types.
• discriminated union: contain a value of one of the union’s types and a tag indicating which type the value are belongs to.
1. ENVIRONMENT:
• associates values with variables.
1. Variables may be represented by: symbols, strings, references into a hash table or even numbers.
2. Environment interface:
``````   (empty-env)
(apply-env env var)
(extend-env var val env)
``````

#### 2.3

Designing an interface for a recursive data type

1. Include one constructor for each kind of data in the data type.
2. Include one predicate for each kind of data in the data type.
3. Include one extractor for each piece of data passed to a constructorof the data type.

#### 2.4

1.

``````   (define-datatype
<type-name>
<type-predicator-name>
(<variant-name>                           ; 1+ variants
(<field-name> <predicator>)           ; 0+ fields
...)
...)
``````

2.

``````   (case
<typename>
<expression>
(<variant-name>
(<field-name> ...)
<consequent>)
...)
(else <default>)
``````

#### 2.5

1. Abstract Syntax Tree
2. Parse and un-parse

Content