| title | slug | description | authors | published | cover | language | links | difficulty | pricing | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Introduction to Functional Programming and the Structure of Programming Languages using OCaml |
intro-to-fp-and-structure-of-pl |
This text teaches functional programming and the structure of programming languages to beginning students. It is written for the Programming 1 course for computer science students at Saarland University. We assume that incoming students are familiar with mathematical thinking, but we do not assume programming experience.
|
|
2022-04-05 |
books/intro-to-fp-and-structure-of-pl.jpg |
|
|
beginner |
free |
This text teaches functional programming and the structure of programming languages to beginning students. It is written for the Programming 1 course for computer science students at Saarland University. We assume that incoming students are familiar with mathematical thinking, but we do not assume programming experience. The course is designed to take about one third of the first semester's study time.
As it comes to functional programming, we cover higher-order recursive functions, polymorphic typing, and constructor types for lists, trees, and abstract syntax. We emphasise the role of correctness statements and practice inductive correctness proofs. We also cover asymptotic running time considering binary search (logarithmic), insertion sort (quadratic), merge sort (linearithmic), and other algorithms.
As it comes to the structure of programming languages, we study the different layers of syntax and semantics at the example of the idealised functional programming language Mini-OCaml. We describe the syntactic layers with grammar and the semantic layers with inference rules. Based on these formal descriptions, we program recursive descent parsers, type checkers and evaluators.