NOTE: I've joined broken lines in the below, and probably therefore invalidated the e-mail's encoding. Or maybe not. Return-Path: X-Original-To: granitemon@computer.csc.calpoly.edu Delivered-To: granitemon@computer.csc.calpoly.edu Received: by computer.csc.calpoly.edu (Postfix, from userid 505) id F24E226FF0C9; Fri, 11 Mar 2011 12:01:59 -0800 (PST) X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on computer.csc.calpoly.edu X-Spam-Level: X-Spam-Status: No, score=-3.2 required=5.0 tests=AWL,BAYES_00, RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.2.5 Received-SPF: Pass (sender SPF authorized) identity=mailfrom; client-ip=74.125.82.43; helo=mail-ww0-f43.google.com; envelope-from=eval.apply@gmail.com; receiver=clements@brinckerhoff.org Received: from mail-ww0-f43.google.com (mail-ww0-f43.google.com [74.125.82.43]) by computer.csc.calpoly.edu (Postfix) with ESMTP id E923826FF0C4 for ; Fri, 11 Mar 2011 12:01:50 -0800 (PST) Received: by wwb17 with SMTP id 17so3152766wwb.24 for ; Fri, 11 Mar 2011 12:01:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:in-reply-to:references:from :date:x-google-sender-auth:message-id:subject:to:content-type :content-transfer-encoding; bh=CetBZL8djgLAHC0cy4jB+bAzOCG36+hGFYGwAcAtQVQ=; b=aDXVlwKLdpLJu4WXiMcXqynBC5HD/arZ4udcc37ed+ixaJcQJlIpX01EtDZLtoV+Tt Ow+e1bjbLCH6HDEnQ7Yz53CgH4ISeEUex+Tyw6XIlpF6XoqsOTwlEoYbvH/j00brFn1f i5qWUF6Mj9k+isKyJtNBOvNQ4rz/RRM/avcBM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:content-type :content-transfer-encoding; b=f2XPlagVvLKLH8fSSFtuvZOd2XImfs8Mr2KgS2fNaXpCbcEPRSm+EHA4AHUIh4+XJE Sv1rzqBdtOPuQHZN62agM2bnJl3u6aem6SCgQ6MbxLWfPFgYXLkODjpefWp4LOorc2Ru unNcRZj03SAokLoiLHAExU7mdfgJ2IXGxD7K0= Received: by 10.227.151.5 with SMTP id a5mr4732875wbw.124.1299873709084; Fri, 11 Mar 2011 12:01:49 -0800 (PST) MIME-Version: 1.0 Sender: eval.apply@gmail.com Received: by 10.227.152.75 with HTTP; Fri, 11 Mar 2011 12:01:29 -0800 (PST) In-Reply-To: References: From: Joe Marshall Date: Fri, 11 Mar 2011 12:01:29 -0800 X-Google-Sender-Auth: yiWdKvOhwu2_H7YRhhwrOoRCqH0 Message-ID: Subject: Re: [racket-dev] Wikipedia on macros... sigh To: John Clements Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Thu, Mar 10, 2011 at 11:24 PM, John Clements wrote: > Wikipedia's page on macros had really no history on it at all. I added some, including > references to Kohlbecker and Clinger. =C2=A0If anyone wants to make it better (or correct > the terrible guesses I made about FEXPRs), take a look at it: > > http://en.wikipedia.org/wiki/Macro_%28computer_science%29#Lisp_.2F_S-expression_macros ``The earliest Lisp macros took the form of FEXPRs, function-like operators whose inputs were not the values computed by the arguments but rather the syntactic forms of the arguments, and whose output were syntactic fragments to be used in place of the FEXPR's use.'' The arguments to a FEXPR were definitely *not* the syntactic forms, but were instead the literal list structure of the source code as returned by `read'. The `output' of a FEXPR is used as the return value of the expression that invoked the FEXPR. The difference is subtle but critical. It hinges on the implementation details of LISP I. LISP I was not simply an implementation of a language definition. It was an implementation of a *meta-circular* language definition. In a language with a meta-circular component, we can partition functions into two classes: those that are `normal' and those that are `level crossing'. In the LISP I implementation, a name could be bound to an EXPR or SUBR, which is simply a first-class procedure (the difference being simply that an EXPR was a procedure implemented via a recursive evaluation while a SUBR was a procedure implemented by direct execution in the underlying platform (IBM 704 assembly). A SUBR was either a primitive or a chunk of compiled code.) But there were analogous level-crossing versions of these called FEXPRs and FSUBRs. A FEXPR was a level-crossing procedure implemented via recursive evaluation and an FSUBR was a level-crossing procedure implemented by direct execution. But FEXPRs and FSUBRs were not meta-syntactic operators that worked on programs via reification and reflection, but rather meta-implementation operators that relied on the meta-circular definition of EVAL (that is, a FEXPR or FSUBR runs at the semantic level of meta-EVAL, not EVAL.) This distinction was not lost on McCarthy et al. FEXPRs were *designed* around the fact that the language had a meta-circular definition that was implemented via recursive descent of list structure. Most, if not all, of the people agitating for the reconsideration of FEXPRs do not understand this distinction. A macro is a program that performs rewrites at a syntactic level. It is abstracted away from the concrete representation of the program it operates on. A FEXPR, on the other hand, is a program that is deliberately *not* abstracted away from the concrete representation. It is as intimately tied to that representation as EVAL. > In later Lisps, FEXPRs were replaced by DEFMACRO, a system that > allowed programmers to specify source-to-source transformations that > were applied before the program is run. FEXPRs (and FSUBRs) weren't actually `replaced'. FEXPRs and FSUBRs were never intended as source->source transforms. The macro facility was added as a separate, unrelated feature. The problem with FEXPRs is that they are far too powerful and place too many constraints on the implementation. It was discovered that certain idiomatic uses of FEXPRs were `safe' (with well-defined, intuitive semantics) whereas other uses were `unsafe' (with vague semantics that rely on the existence of meta-circular fixed points (yikes!) and were difficult to reason about). One cannot effectively program with `unsafe' FEXPRs, so they fell out of favor really quickly. `Safe' FEXPRs turn out to be the subset of FEXPRs that can be understood as source->source translations. Since macros provided that same power without the attendant problems, they quickly became the preferred way to meta-program. With FEXPRs no longer necessary, meta-circularity is no longer necessary and EVAL no longer needs to operate on list structure. Another way to look at it is this: the denotational semantics of a language have a function `Big-E' that maps `expressions' to `values'. If we wish, we can define a function Big-P (for parse) that maps `list structure' to `expressions' and Big-P^-1 that maps them back. LISP I defines Big-E[[ ]] =3D apply( Big-E[[ car (Big-P^-1 [[]])]], map (lambda (arg) Big-P^-1 [[ eval arg ]]) (cdr (Big-P^-1 [[]])) (or something like that). The point is that the semantic definition of Big-E is defined via the isomorphism between code and list structure and is inextricably linked to it. A FEXPR manipulates objects on both sides of the isomorphism (yuck), so Big-P and Big-P^-1 cannot be factored out of the semantics. A macro, however, only manipulates objects on one side, allowing Big-P to be factored out and hidden as a syntactic transform. This greatly simplifies the definition of Big-E (in essence, it allows us to define Big-E over a simple Scott domain rather than a reflective one). --=20 ~jrm