Prompts for “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” and “Brief Introduction to F#”

Due on Monday, October 15 by 10pm

Read “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I”, pp. 184–188 and pp. 191–193 up to the end of 4c. Also read “Brief Introduction to F#”.

Commit your response as a PDF to your short responses repository. You are encouraged (but not required) to use LaTeX to typeset your response. You will also submit a small amount of code to your reading response repository for the last question.

1. McCarthy discusses the definitions of a few functions (“S-functions”) of S-expressions in Lisp on p. 188:

    car[(m_1, m_2, ..., m_n)] = m_1
    cdr[(m_1, m_2, ..., m_n)] = (m_2, ..., m_n)
    cdr[(m)] = NIL
    cons[m_1; (m_2, ..., m_n)] = (m_1, m_2, ..., m_n)
    cons[m_1; NIL] = (m)
   

   These functions bear a striking resemblance to a set of functions you recently implemented in C. What are the meaning of car, cdr, and cons in terms of those C functions?

2. The algorithm described on pp. 192-193 in part 4c was the first of its kind and spawned an entirely new area of research in computer science. This algorithm is still essentially in use today in many real-world programming languages. What is McCarthy talking about and why is it so important?
3. Create the “hello world” program described in the tutorial and commit it to your repository.