[HN Gopher] Recursive Functions of Symbolic Expressions Computat...
___________________________________________________________________
Recursive Functions of Symbolic Expressions Computation by Machine
(1960)
Author : abrax3141
Score : 60 points
Date : 2022-10-04 16:29 UTC (2 days ago)
(HTM) web link (www-formal.stanford.edu)
(TXT) w3m dump (www-formal.stanford.edu)
| rluoy wrote:
| always wonder where is part II.
| jart wrote:
| I'm sure one of his other AI Memos could be considered that.
| For example: https://dspace.mit.edu/handle/1721.1/6099
| adrian_b wrote:
| 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.
| kragen wrote:
| Thanks, this is great!
| Jtsummers wrote:
| 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.
| lispm wrote:
| 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...
| user3939382 wrote:
| 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.
| [deleted]
| quesomaster9000 wrote:
| 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...
| user3939382 wrote:
| 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?
| bidirectional wrote:
| Yes, you need to not run away as soon as a non-alphanumeric
| symbol is used. That's hardly even mathematical notation.
| Jtsummers wrote:
| 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.
___________________________________________________________________
(page generated 2022-10-06 23:01 UTC)