what is a special form?

Discussion of Common Lisp
Post Reply
Martin Kalbfuß
Posts: 12
Joined: Fri Jul 24, 2015 5:27 am

what is a special form?

Post by Martin Kalbfuß » Thu Aug 06, 2015 3:53 am

Hi Guys,

I try to understand the the terms used in the common lisp world.

The Common Lisp HyperSpec says:
A special form is a form with special syntax, special evaluation rules, or both, possibly manipulating the evaluation environment, control flow, or both. A special operator has access to the current lexical environment and the current dynamic environment. Each special operator defines the manner in which its subexpressions are treated---which are forms, which are special syntax, etc.
What are forms with 'special syntax'?
Where is this special syntax looking at setq for example.

Finally, what's the difference between a macro and a special form?
Why is defun a macro but setq not?

Thank you in advance,

Martin

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: what is a special form?

Post by edgar-rft » Thu Aug 06, 2015 12:16 pm

A "normal" Lisp function call looks like this:

Code: Select all

(<function-name> <argument-1> <argument-2> ... )
The standard evaluation rule for Lisp functions is:
  1. First evaluate all arguments from left to right
  2. Then apply the function to the evaluated arguments
Evaluating the arguments first makes it possible to write Lisp code that looks like a tree:

Code: Select all

            (function-2 <argument-1> ... )
             |
             v
(function-1 <argument-1> <argument-2> ... )
                          ^
                          |
                         (function-3 <argument-1> ... )
The nice thing is that this simple evaluation rule already covers 90% of all Lisp function calls. This means that Common Lisp is not as big as it looks, because the basics are very simple.

But there are cases where this evaluation rule does not make sense. For example:

Code: Select all

(if <test> <then> <else>)
Here it doesn't make sense to evaluate the TEST as well as both THEN and ELSE parts first, and only afterwards decide which one of THEN or ELSE should be evaluated. This means that IF needs a "special" evaluation rule, where only the TEST argument is evaluated first, and only then one of THEN or ELSE arguments is evaluated, depending on the result of evaluating the TEST.

The same is with SETQ:

Code: Select all

(setq <symbol> <value>)
If the SYMBOL argument would be evaluated, then the VALUE would be assigned to old evaluated value of SYMBOL, not to the name of the symbol. Or even worse, an error would be signaled if the symbol doesn't exist. This means that SETQ needs a "special" evaluation rule, where only the VALUE, but not the SYMBOL argument is evaluated.

Every Lisp function that breaks the "evaluate all arguments first" rule needs its own special evaluation rule in the interpreter (or compiler). That's where the "special" comes from. Because such a function breaks the standard evaluation rule for functions, it's not a Lisp "function" anymore (at least according to the Lisp evaluation rules). In the Common Lisp specification such "functions" therefore are called "special operators", but you will also find names like "special forms" in old Lisp texts.

It's also important to know that you cannot define your own "special operators", but you can define Lisp macros if you need to break the evaluation rules. It's also possible that a "special operator" is internally defined as a macro by the Lisp implementation.

But the only important thing here is that whenever something is called "special" this means that it breaks the standard evaluation rules. There are also "special variables", which have dynamic instead of lexical scope.
Martin Kalbfuß wrote:...what's the difference between a macro and a special form?
A special operator is a simple function call with special evaluation rules. A macro additionally can perform complex syntax transformations by generating Lisp code. Macros are extensively explained in Paul Graham's On Lisp (free PDF download link after the first text section on that page).
Martin Kalbfuß wrote:Why is defun a macro but setq not?
Because DEFUN changes the syntax by generating new code:

Code: Select all

(defun add1 (x)
  (1+ x))
will generate code that looks like this:

Code: Select all

(progn
  (intern (symbol-name (quote add1)))
  (setf (symbol-function (quote add1)) (lambda (x) (1+ x))))
Many Common Lisp macros are syntactic sugar for ugly-looking code. See MACROEXPAND that will show you the code generated by Lisp macros.

- edgar

Martin Kalbfuß
Posts: 12
Joined: Fri Jul 24, 2015 5:27 am

Re: what is a special form?

Post by Martin Kalbfuß » Thu Aug 06, 2015 1:57 pm

Thanks for the explanation, edgar!

I sumarize:

Before a function is called, all its arguments ar evaluated.
A special form doesn't follow this rule. Some arguments may get evaluated, some not.
A macro generates code wich gets evaluated after applying some transformations. A macro can be used to block evaluation of some of its arguments, quoting them. As a consequence, a macro may be used to implement the behaviour of a special form.

Is this correct so far?

I still have some questions.

How is the intermediate result the transformed code of a macro called? Is this a form, too?
If yes, what is a form?
I recognize things like lists, numbers, strings, etc as forms. Is a serie of them also a form?

When using the GNU Common Lisp comiler the code

Code: Select all

(defun setq ())
leads to the error message
ERROR "SETQ, a special form, cannot be redefined."
Is this behaviour enforced by the standard? Is it not allowed to redefine a special form?

Best regards,
Martin

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: what is a special form?

Post by edgar-rft » Thu Aug 06, 2015 3:20 pm

Martin Kalbfuß wrote:Before a function is called, all its arguments ar evaluated.
Yes.
Martin Kalbfuß wrote:A special form doesn't follow this rule. Some arguments may get evaluated, some not.
Yes.
Martin Kalbfuß wrote:A macro generates code wich gets evaluated after applying some transformations. A macro can be used to block evaluation of some of its arguments, quoting them.
In contrast to functions, macros do not evaluate their arguments. Therefore in the body of a macro definition a COMMA (see Section 2.4.6, Backquote syntax) must be explicitely used whenever an argument shall be evaluated.
Martin Kalbfuß wrote:As a consequence, a macro may be used to implement the behaviour of a special form.
In principle every special operator can be implemented as a macro. But special operator evaluation rules can be hard-coded in the evaluator of the Lisp interpreter or compiler, while a macro expansion needs code analysis what is potentially slower. For example in a Lisp compiler, macros therefore are expanded at compile-time, not at run-time.
Martin Kalbfuß wrote:How is the intermediate result the transformed code of a macro called?
It's usually called "the expanded macro form".
Martin Kalbfuß wrote:I recognize things like lists, numbers, strings, etc as forms. Is a serie of them also a form?
The term "form" comes from the very old days where Lisp was modeled after Alonzo Church's "Lambda Calculus". It's an abbreviation of math's "formula". In principle a Lisp "form" is everything that can be evaluated in one piece. From simple self-evaluating data types like numbers or strings up to complex function or macro calls.
Martin Kalbfuß wrote:ERROR "SETQ, a special form, cannot be redefined."
The error message is misleading. What it means is that "The symbol SETQ in the COMMON-LISP package cannot be redefined", where the standard says that no symbol in the COMMON-LISP package can be redefined, whether it is a function, macro, special form or variable doesn't matter.

For example, if you define your own package you can shadow Common Lisp's SETQ with your own definition without any error:

Code: Select all

CL-USER> (defpackage :my-package (:use :common-lisp) (:shadow :setq))
#<PACKAGE "MY-PACKAGE">

CL-USER> (in-package :my-package)
#<PACKAGE "MY-PACKAGE">

MY-PACKAGE> (defun setq (&rest args)
              (declare (ignore args))
              "Surprise: This is not what you have expected.")
SETQ

MY-PACKAGE> (defparameter *x* 0)
*X*

MY-PACKAGE> (setq *x* 1)
"Surprise: This is not what you have expected."
- edgar

Martin Kalbfuß
Posts: 12
Joined: Fri Jul 24, 2015 5:27 am

Re: what is a special form?

Post by Martin Kalbfuß » Fri Aug 07, 2015 3:18 am

Thanks again!

What still bugs me, is that I can redefine the + operator with the GNU Common Lisp Compiler. All I get is a warning. Are you sure about the following...
The error message is misleading. What it means is that "The symbol SETQ in the COMMON-LISP package cannot be redefined", where the standard says that no symbol in the COMMON-LISP package can be redefined, whether it is a function, macro, special form or variable doesn't matter.
If that's true then the GNU Common Lisp Compiler is not standard conform. I would really like to have the standard here. Looks like I have to buy it.

Best regards
Martin

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: what is a special form?

Post by edgar-rft » Fri Aug 07, 2015 6:23 am

Martin Kalbfuß wrote:What still bugs me, is that I can redefine the + operator with the GNU Common Lisp Compiler. All I get is a warning.
This is definitely a bug in GNU Common Lisp. There are tricks to make it possible to redefine built-in Common Lisp functions, but this should not be enabled by default. I will try to find the page in the Hyperspec where the constraints on the Common Lisp package are defined.
Martin Kalbfuß wrote:If that's true then the GNU Common Lisp Compiler is not standard conform.
I think that GNU Common Lisp (GCL) is a Common Lisp implementation of very questionable quality. Bill Shelter had started GCL because he needed a Common Lisp implementation that runs on MS-Windows for the Maxima computer algebra system. Unfortunately Bill Shelter died in 2001 when GCL was still unfinished. Since then GCL had been nearly unmaintained for more than ten years until it was resurrected by Camm Maguire in 2013. There had been some new releases since then and I don't want to insult anybody who ever worked on GCL, but I think that there is still a lot of work to do until GCL will be standard conform.

A comparison of the different Common Lisp implementations:
Martin Kalbfuß wrote:I would really like to have the standard here. Looks like I have to buy it.
Don't pay money for the printed ANSI Common Lisp standard, they will send you poor and crappy copies of very old documents. The Hyperspec contains the full text of the ANSI standard and there is a dpANS3 book.pdf, which is the last version of the ANSI Common Lisp standard before the offficially printed document. According to Kent Pitman (maintainer of the Hyperspec) there are only a few spelling corrections difference between dpANS3 and the official ANSI Common Lisp standard. The dpANS3 TeX sources can be found here: http://quimby.gnus.org/circus/cl/

- edgar
Last edited by edgar-rft on Fri Aug 07, 2015 9:50 am, edited 2 times in total.

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: what is a special form?

Post by edgar-rft » Fri Aug 07, 2015 8:06 am

Here is what I've found so far:
I'm not a Common Lisp language-lawyer but here is how I understand the constraints on the COMMON-LISP package as defined by the ANSI standard, what is admittedly a bit different of what I wrote above.

In Section 11.1.2.1.2 it is not said that it is forbidden, but "the consequences are undefined" if a function of the COMMON-LISP package is redefined. This means that a program that redefines the + function of the COMMON-LISP package is a non-conforming program and the result of the redefinition is not predictable if the program runs on different Common Lisp implementations, but the implementation itself is not required to forbid the redefinition.

Every Common Lisp implementation I have worked with so far signaled an error as soon as I tried to redefine a function in the COMMON-LISP package.

The following examples are from the Common Lisp implementations that are currently happen to be installed on the computer I'm working right now, they are not necessarily representative for all existing Common Lisp implementations.

GNU CLISP:

Code: Select all

[1]> (defun + () nil)

** - Continuable Error
DEFUN/DEFMACRO(+): #<PACKAGE COMMON-LISP> is locked
SBCL (Steel Bank Common Lisp):

Code: Select all

* (defun + () nil)

debugger invoked on a SYMBOL-PACKAGE-LOCKED-ERROR:
  Lock on package COMMON-LISP violated when setting fdefinition of + while in
  package COMMON-LISP-USER.
Package locks are implementation-defined, they are not part of the ANSI Common Lisp standard.

- edgar

Post Reply