On this page:
A Functional Introduction To Computer Science (Part II)
8.1

A Functional Introduction To Computer Science (Part II)

(a flânerie by Prabhakar Ragde)

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Please do not post exercise solutions to any public forum or publicly-accessible software repository.

This is a complete draft of Part II. For Part I, look here.

    1 Introduction

    2 Effects in Racket

      2.1 Moving to full Racket

      2.2 Quasiquotation and pattern matching

      2.3 The memory model

      2.4 Output

      2.5 Input

      2.6 Files

      2.7 Elementary mutation: the fall from grace

      2.8 Testing

      2.9 Memoization

      2.10 Intermediate mutation

      2.11 Advanced mutation

      2.12 Adding mutation to an interpreter

      2.13 Memory and vectors

      2.14 Vectors in Racket

      2.15 Abstract data types with state

    3 SIMP: a simple imperative language

      3.1 Syntax and informal semantics

      3.2 Examples in several languages

      3.3 Formal semantics

      3.4 Proving imperative programs correct

    4 PRIMP: A primitive imperative language

      4.1 A primitive imperative language

      4.2 The PRIMP simulator

      4.3 The PRIMP assembler

      4.4 The SIMP to A-PRIMP compiler

      4.5 Static typing and typechecking

      4.6 Adding arrays to SIMP

      4.7 Adding functions to SIMP

      4.8 Adding both arrays and functions to SIMP

      4.9 Implementing lists in PRIMP

    5 FIST: a first instruction set

      5.1 A more realistic processor

      5.2 The FIST architecture

        5.2.1 Status bits and conditional execution

        5.2.2 Data processing instructions

        5.2.3 Software interrupt instructions

        5.2.4 Branch instructions

        5.2.5 Data transfer instructions

        5.2.6 Block data transfer instructions

      5.3 Towards a FIST simulator

      5.4 Towards a SIMP to FIST compiler

      5.5 Summary of the FIST architecture

    6 Implementing functional languages

      6.1 Storing primitive values

      6.2 Sharing and aliasing demystified

      6.3 Managing memory

      6.4 Structural and pointer equality

      6.5 Function application in a Racket interpreter

      6.6 Tail recursion

      6.7 Justifying the cost of Racket primitives

      6.8 Moving towards implementation in an imperative language

    7 Control

      7.1 Zippers

      7.2 A continuation-passing interpreter

      7.3 Adding back environments

      7.4 Trampolining

      7.5 Garbage collection

        7.5.1 Reference counting

        7.5.2 Mark-and-sweep

        7.5.3 Copying garbage collection

      7.6 What’s next?

    8 Continuations

      8.1 Continuation-passing style

      8.2 Exception handling

      8.3 Undelimited continuations

      8.4 Delimited continuations

      8.5 Racket’s implementation of continuations

    9 Handouts and Sources

      9.1 Handouts

      9.2 Sources