Home

A bit of Scheming

A rather amusing thread on the plt-scheme mailing list, reminded me of Wadler's paper Why Calculating is Better than Scheming from 1987, which wasn't discussed here as far as I recall.

It's a bit of a blast from the past, but still worth reading.

By Ehud Lamm at 2008-10-19 01:35 | Functional | Teaching & Learning | Type Theory | other blogs | 6734 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

nice paper, thanks.

Thanks for the link, I enjoyed this.

(I too was at a bit of a loss as to what to put into that box.)

By Andy Wingo at Sun, 2008-10-19 18:18 | login or register to post comments

It is nice to see theory and

It is nice to see theory and idealism turned into a successful practice - it offers hope for the rest of us hopeless pedants. Philip Wadler has done a lot of interesting work after writing that paper.

By dmbarbour at Mon, 2008-10-20 03:52 | login or register to post comments

Quite a few of Wadler's

Quite a few of Wadler's papers were discussed here over the years. You might be interested in checking the archives.

By Ehud Lamm at Mon, 2008-10-20 07:11 | login or register to post comments

Interesting ...

Interesting paper indeed. However, I must say some of the seemingly important arguments don't look very strong to me. The lack of pattern matching, for example, doesn't appear to be an issue since you can create the pattern matching syntax and a compiler for it in Scheme itself due to macros (hygienic or unhygienic) ... and plt-scheme does have such a match syntax.

I have to admit that (quote ...) is a wart, though. It seems to be problematic to implementations as well as programmers.

A&S's use of Scheme is just so we have the smallest set of concepts with which we can be productive as programmers.

By Srikumar Subramanian at Mon, 2008-10-20 09:24 | login or register to post comments

oops ...

I realized I might have started yet another lisp-vs-haskell kind of debate :) Hope it doesn't go there.

By Srikumar Subramanian at Mon, 2008-10-20 09:26 | login or register to post comments

Is there another way to

Is there another way to cleanly represent code without quote? You could do something like

Call(Variable("f"), [Constant(4), Variable("a")])

But this gets unwieldy fast and doesn't resemble the original (unquoted) code.

By Jules Jacobs at Mon, 2008-10-20 15:36 | login or register to post comments

SICP replacement for statically typed lazy PLs?

Although I can see why quote might be the source of some confusion in Scheme, I think it's much simpler than an explanation required for the Haskell syntax (e.g. monads would be needed for the first half of chapter 3). The confusion in Scheme over quote arises from Scheme's ability to blur the distinction between code and data. Although this might work against simplicity up front, it pays dividends in later chapters. A clear explanation of quote is a small price to pay in terms of the raw power that it affords.

The beauty of SICP is not just in exploring more prototypical programming techniques in the first 3 chapters, but in the awesomeness of wrapping up interpreters and compilers in chapters 4 and 5 - those chapters that make SICP of special interest to LtU. In spite of some of it's weaknesses, SICP remains the crown jewel in introducing an amazing number of things. Although there are some outstanding introductory texts written for Haskell, none has come close to being such a wide survey of computer science from an entry level. For everything that other PLs have an advantage, there is a sacrifice that occurs for quite a few things that are in SICP.

Scheme may not be optimal for any of the particular topics at hand. And certainly other PLs can cherry pick where they want. But until they can wrap up all the things that are contained in SICP, I don't think that SICP will be surpassed. This is not to say that SICP is the right tool for teaching a beginning course in computer science - that depends on what lessons you are actually trying to teach, and the aptitude of the teachers and students.

By Chris Rathman at Mon, 2008-10-20 15:54 | login or register to post comments

Code and data ...

The blurring of code and data is something that has been immensely useful to me in the construction of DSLs using Scheme and I'll be hard pressed to code those up without quote, so I'm not giving both up any time soon.

Once a DSL is constructed, however, quote usually starts to interfere in quite a few ways and it is difficult to explain it to DSL users and cumbersome to check for all over the implementation. I'm not saying that for a fact, its just been my experience so far.

At one point, I was considering whether quote should behave as though ''''(blah bling foo) is equivalent to '(blah bling foo) and to (eval '(blah bling foo)) and require an explicit unquote operator to remove it. That will be more predictable and make '(blah bling foo) behave exacty like, say, 1, or "hello" which evaluate to themselves no matter how many times you call eval on them.

By Srikumar Subramanian at Tue, 2008-10-21 05:11 | login or register to post comments

an algebra ...

Here is an "algebra" for such a quote -

''(x y ...) = '(x y ...) = ('x 'y ...)
(cons 'x '(y ...)) = '(x y ...)
(first '(x y ...)) = 'x
(rest '(x y ...)) = '(y ...)
(eval 'x) = 'x
(eval '(x y ...)) = '(x y ...)
(unquote '(x y ...)) = (list x y ...)

The most suspicious consequence seems to be '(x '(y z)) = ('x ('y 'z)), but maybe that doesn't pose a limitation.

By Srikumar Subramanian at Tue, 2008-10-21 05:26 | login or register to post comments

Eval does nothing? Quote is

Eval does nothing?
Quote is not confusing if you write (quote ...) instead of '..., or if you remember that ' is a shortcut for quote.

By Jules Jacobs at Tue, 2008-10-21 10:54 | login or register to post comments

eval ..

yup it does nothing on quoted stuff. (eval (unquote '(x y ..))) should get you what you expect - i.e (x y ...).

By Srikumar Subramanian at Wed, 2008-10-22 15:22 | login or register to post comments

So there are two worlds: the

So there are two worlds: the normal world and the quote world. Things in these worlds are the same (for car, cdr, etc) except for eval, which executes normal sexps and treats quoted sexps as self-evaluating. Wouldn't you need an operation that converts a normal sexp to a quoted sexp? Like this:

(quoted (list 'print 'x)) => '(print x)

By Jules Jacobs at Wed, 2008-10-22 16:53 | login or register to post comments

not really ..

I mentioned above that '(x y) = ('x 'y) and that would mean (list 'x 'y) = '(x y) = ('x 'y) as well. The one problem is that this scheme breaks a one-one relationship between notation and list structure - for all practical purposes, '(x y) and ('x 'y) become indistinguishable and therefore an issue of an appropriate internal representation arises that preserves this equivalence.

By Srikumar Subramanian at Thu, 2008-10-23 06:56 | login or register to post comments

The confusion about quote is

The confusion about quote is not the notation itself, but what it means. ' and quote are both fine, but the confusion comes from the multiple levels of quoting allowed in lisps/schemes today ... I think.

By Srikumar Subramanian at Thu, 2008-10-23 06:58 | login or register to post comments

escaping generally sucks

i think escaping of any form quickly becomes a usability burden. take basic string escaping with e.g. the backslash character. as soon as you have more than one layer which does un/escaping, you get into really painful debugging imho.

i don't know what else to do about it. i wish somebody could come up with something really clever :-)

By raould at Thu, 2008-10-30 17:16 | login or register to post comments

Reflection and Semantics in LISP

This is the approach that Brian Cantwell Smith advocated [ACM] — that eval (or rather, normalisation) should be designation preserving. For example, (+ 2 3) and 5 both designate the value 5, whereas '(+ 2 3) designates a piece of code. So reducing '(+ 2 3) to (+ 2 3) changes the interpretation of the term, which is bad. An explicit unquote operation seems much better.

(I don't know a non-ACM link for that paper, sorry.)

By Neil M at Tue, 2008-10-21 14:31 | login or register to post comments

Reflection for the Masses

A more readable paper (both in terms of content and typesetting) describing the same concepts with a non-ACM link: Reflection for the Masses.

By drobilla at Tue, 2008-10-21 18:10 | login or register to post comments

I don't really think (quote

I don't really think (quote form) is complicated - I think (eval form) is what is complicated.

Pretend eval didn't exist at all and that everything was expanded at read time and compiled at a compile time prior to evaluation - and quote doesn't seem very complicated at all.

By scottmcl at Fri, 2008-10-24 01:24 | login or register to post comments

Confused by (quote

I remember finding quote confusing when I read SICP. Then I happened upon Wadler's paper and I felt better - I thought, if the Professor of Computing at Edinburgh University says it's confusing then I'm entitled to be confused myself. In an odd way it was very encouraging.

By Mike Smith at Thu, 2008-10-30 14:44 | login or register to post comments

Bleah: misunderstanding the difference between write and display

As far as I can tell, the part of the paper that people here are commenting on is fundamentally misinformed, in that it confuses "write" with "display". In particular, it's a mistake to try to infer a reduction semantics from the characters that appear on stdout.

For instance, in Scheme, (display "abc") results in the display of the characters a, b, and c on stdout. Does this mean that a semantics for Scheme should have (display "abc") reduce to abc? No. It's a similar mistake to see
>'(a b c)
(a b c)
>

... and infer that '(a b c) reduces to (a b c). Going down this path makes your life yucky and unpleasant. (In fact, DrScheme prints values such as this differently, for precisely this reason.)

In particular, this paper says:

Now, consider using the substitution model to explain the evaluation of the term
( list (list 1 2) nil) :

(list (list 1 2) nil)
--> (list (1 2) nil)
--> (list (1 2) ())
--> ((1 2) ())

AFAICT, this is just pure misunderstanding: (list 1 2) does not reduce to (1 2), and this has nothing at all to do with substitution, unless you're trying to infer something from the way that certain scheme implementations display values.

In fact, I think that Wadler himself corrects himself in a later paper on XML, where he does in fact refer to s-expressions as being "self-quoting."

There are lots of other things in this paper; I think it's a mistake to focus on this section.

Also, the thread that this item links to probably does a better job than I do of elucidating the underlying issues.

By jbclements at Fri, 2008-10-31 20:50 | login or register to post comments