[plt-scheme] a few questions (was: Scheme questions?)

From: Robby Findler (robby at cs.uchicago.edu)
Date: Sun Dec 4 22:21:55 EST 2005

At Sun, 4 Dec 2005 22:06:17 -0500, Hendrik Boom wrote:
> On Sun, Dec 04, 2005 at 08:51:35PM -0500, Matthias Felleisen wrote:
> > On Dec 4, 2005, at 8:19 PM, Gregory Woodhouse wrote:
> > >On Dec 4, 2005, at 5:08 PM, Matthias Felleisen wrote:
> > >
> > >>
> > >>>I don't know if the Y combinator had been devised when McCarthy was
> > >>>trying to computerize recursion theory,
> > >>
> > >>1930s.
> > >
> > >Are you sure?
> > 
> > Yes.
> > 
> > >I know lambda calculus was developed in the 1930's, but didn't Dana 
> > >Scott develop domain theory (where you get fixed points for continuous 
> > >functions) in the 1970's.
> > 
> > The Y combinator is a syntactic idea, not a semantic one. Yes, it took 
> > people some 35 years to develop the semantics of the LC but that 
> > doesn't prevent anybody from doing and using Y, the S/K stuff, and many 
> > more purely syntactic things.
> 
> Actually, the lambda calculus, from early on, had a so-called syntactic
> model where the "value" of a lambda expression was the equivalence class
> of expressions that were reduction-equicalent to it.

Folks, as amusing as it is to see Matthias being lectured on these
topics, lets not forget that he was one of the key contributors. With
various others, he is responsible for the fully abstract model of SPCF
(sequential PCF), syntactic theories of state and of control, and one
of the most widely used operational semantics formalisms (due to the
fact that it works so well for proving type soundness results, another
insight of his).

Robby



Posted on the users mailing list.