Recursive Functions of Symbolic Expressions Computation by Machine (1960) | Hacker News Reader

Recursive Functions of Symbolic Expressions Computation by Machine (1960)

www-formal.stanford.edu

65 pointsabrax314113 comments

I wish my formal math was stronger. I've been programming for 30 years but once a paper I'm reading starts using math notation I can't parse 90% of it and I'm lost.

The notation used is almost all explicitly defined or can be trivially derived by reading the descriptions provided, aside from cardinality e.g. |x^2 - a| which is assumed to be common knowledge.

Everything else is very simple pseudocode albeit with use of a few Greek letters or symbols, so I could hardly call this inaccessible to somebody who has been programming for 30 years...

So, you're arguing that this: https://www-formal.stanford.edu/jmc/recursive/img242.png and this https://www-formal.stanford.edu/jmc/recursive/img66.png

are accessible with common knowledge to someone with programming experience but without a background in mathematics?

The first one isn't really math-heavy, but it is symbol heavy (and there seem to have been some typos in the LaTeX or errors in generation, some subscripts are borked). The actual translation of the first image to Python-esque code is:

  def r(some_params):
    if predicate_11(some_params): return s(f1(some_params))
    else: return s(f2(some_params))
  def s(some_params):
    if predicate_21(some_params): return r(some_params)
    else: return t(f3(some_params))
  def t(some_params):
    if predicate_31(some_params): return f4(some_params)
    elseif predicate_23(some_params): return r(some_params)
    else: return t(f3(some_params))

I've replaced pi with `predicate` and xi with `some_params`.

The second one, structurally, can also be understood without knowing math but what's actually executed does require some familiarity with math. It's, like above, using a conditional expression described earlier and the lambda notation for defining anonymous functions (to be clear, he also uses it as an example of something that's not quite valid since the name `sqrt` will not be bound inside the lambda, but we can approximate it, invalid multi-line Python lambda incoming):

  sqrt = lambda a, x, epsilon: if abs(x*x - a) < epsilon: return x        # that is, we've found a close-enough approximation
                               else: return sqrt(a, (x+a/x)/2, epsilon)   # get a closer approximation to the square root

The previous line of code in that section (no lambda) is equivalent to a Python def:

  def sqrt(a,x,epsilon):
    if abs(x*x-a) < epsilon: return x
    else: return sqrt(a, (x+a/x)/2, epsilon)

(NB: All the extra `return`s have to be added because Python is not an expression-oriented language. The language McCarthy is describing is so each expression produces a new value without the need for explicit returns.)

Both of those are there to motivate the introduction of the label form at the bottom of that section.

Yes, you need to not run away as soon as a non-alphanumeric symbol is used. That's hardly even mathematical notation.

It’s 100% mathematical notation

Just build a rosetta stone; e.g.

  (x < y) ∧ (b = c)       ....   (x < y) && (b == c)

  (p1 → e1, ... pn → en)  ....    return (p1 ? e1
                                             : p2 ? e1
                                                  : ...
                                                       pn ? en
                                                          : NULL)

Wow, so much less cryptic!

Hope this helps.

At the same time (1960) there was already a Programmer‘s Manual for Lisp 1. Lisp then had a real implementation with a lot novel stuff like garbage collection, resumeable memory images, code as data, etc.

http://bitsavers.org/pdf/mit/rle_lisp/LISP_I_Programmers_Man...

always wonder where is part II.

I'm sure one of his other AI Memos could be considered that. For example: https://dspace.mit.edu/handle/1721.1/6099

Per his homepage it “never appeared”. Which would mean never finished, I guess.

> Part II, which never appeared, was to have had some Lisp programs for algebraic computation.

This text, with minor, mostly typographical, differences had been previously published internally as "MIT AI Lab. AI Memo No. 8" in March 1959.

Two other earlier publications by McCarthy include various very important innovations, e.g. the conditional expressions in "AI Memo No. 1" (September 1958) and the "select" expressions (i.e. what are now named as "case" or "switch") in "AI Memo No. 4" (October 1958).

The text published in CACM in 1960 is the conclusion of the memos written by McCarthy between 1958-09 and 1959-03, when most of the ideas on which LISP is based have been conceived.

The "cond" and "select" expressions and the McCarthy "and" and McCarthy "or" expressions (i.e. C language && and ||) were not only new at that time, but they were much more convenient than the means used for expressing conditional execution in most later programming languages, which had various weird restrictions or peculiar syntax, for no good reason.

Thanks, this is great!

Reply on news.ycombinator.com