What are syntax-case pattern variables?

I asked here:

syntax-case takes a syntax object as an argument and destructures it via pattern matching into pattern variables.

What are pattern variables composed of?

syntax takes a template, and the pattern variables in it, to produce a syntax object that has the same lexical scoping as that of the pattern variable, so where does that lexical scope get stored?

and then Ryan explained:

The short answer is that syntax objects store scoping information and
that pattern variables have nothing to do with it.

Here’s a longer answer:

A pattern variable is essentially bound to an ellipsis-depth n and syntax object(s). If the pattern variable doesn’t have ellipses after it, then n is 0 and the pattern variable refers to a single syntax object. If it has one ellipsis after it, then n is 1 and there is a list of syntax objects. And so forth.

The ‘syntax’ form is like ‘quasiquote’, except that there is no explicit ‘unquote’; rather, pattern variables are automatically substituted, and the rest of the template becomes syntax object literals (via ‘quote-syntax’) that remember the bindings in scope where they occurred.

So pattern variables, while convenient, are not necessary for writing macros. You could do just the same with ‘quote-syntax’, ‘syntax-e’, ‘datum->syntax’, ‘car’, etc.

Lexical scoping is managed by the syntax objects. The macro arguments already have their lexical contexts embedded in them, and that is preserved as the macro takes them apart and puts them together with new syntax. This new syntax mostly comes from syntax literals.

The essence of the algorithm is explained in “Syntactic Abstraction in Scheme” by Dybvig et al.

Unhygienic macros inside of unhygienic macros are difficult

In this post; Ryan explains why unhygienic macros inside of unhygienic macros are often difficult.

;; the working if-it & when-it

(define-syntax (if-it stx)
  (syntax-case stx ()
    ((if-it test? then else)
     (with-syntax ((it (datum->syntax #'if-it 'it)))
       #'(let ((it test?))
           (if it then else)))))) 

(define-syntax (when-it stx)
  (syntax-case stx ()
    ((~ test? exp exp2 ...)
     (with-syntax ((it (datum->syntax #'~ 'it)))
       #'(let ((it test?)) (when it exp exp2 ...))))))

;; the non-working cond-it 
(define-syntax (cond-it stx)
  (syntax-case stx (else)
    ((cond-it (else exp exp2 ...))
     #'(begin exp exp2 ...))
    ((cond-it (test? exp exp2 ...))
     #'(when-it test? exp exp2 ...))
    ((cond-it (test? exp exp2 ...) cond1 cond2 ...)
     #'(if-it test? (begin exp exp2 ...)
              (cond-it cond1 cond2 ...)))))

When ‘cond-it’ expands and produces an ‘if-it’ expression, the ‘if-it’ is marked by the macro expander as coming from a macro. That means its lexical context is different from the ‘it’ variables in the branches. That means that the ‘it’ variable binding produced by ‘if-it’ does not capture the ‘it’ references in the branches.

— Ryan

One reason for hygiene

You need hygiene because:

Only superstars on their highest alert level [while writing macros] get things right all the time.

–Matthias

That said, hygiene alone isn’t a cure-all for writing predictable macros. If you don’t understand what you are doing, thoroughly; you will screw up eventually. “Thar be dragons here” as someone once warned on the PLT list.

(via PLT)

Automata via Macros

Last year I asked a question about Automata via Macros to the PLT Discussion List. The paper is about an extended example of a problem posed by Shriram Krishnamurthi at the Lightweight Languages 1 conference. I was trying to understand how one might use the same FSA language to generate different outputs. Many folks explained how that would work and the thread finished. It didn’t finish for me, though. To say my understanding of the solution was superficial would be an overstatement. I knew I didn’t “get it”, and kept it on my list to revisit once I had a better grasp on things. That was a year and a half ago.

Over my holiday I revisited the paper and found, for lack of a better way to say it, that it “made sense”. In the past year I’ve tried to: read a lot, write a lot of code, read other people’s code, and most importantly do so with some discipline and attention to detail that I had not applied before. That seems to have paid off; as it felt like I was reading the paper with brand new eyes.

This time around, I also listened to a recording of the presentation itself and watched the PowerPoint that went along with it. This was especially valuable because it drew attention to various tidbits that appeared in the paper but were much easier to delineate by virtue of Shriram pointing them out in context of the presentation. It was those comments, along with what I had learned in the past year that really got me thinking about things again.

In a conversation with Aaron Hsu, he once said something to the effect that “Scheme is hard because it is subtle.”, and that sort of rang true with my intuition, but I had a difficult time verbalizing exactly why I thought that to be true. Outwardly Scheme appears to be “simple”, but the more you learn about it and the deeper you dig, you start to see that it is Deceptively Simple.

Scheme seems to take only a few days to learn, but a few years to master; but why? I don’t know yet, but what I do know is that some of the ideas and topics presented in this paper and presentation are surely some of the aforementioned “subtleties” that serve as landmarks on this multi-year path towards understanding Scheme. For my own reference, and for others who may be studying Scheme and wondering exactly why “Subtlety is hard”, perhaps this paper will serve to shed some light on things.

My advice: read LAMBDA: The Ultimate Imperative and LAMBDA: The Ultimate GOTO first.

Abstract

Lisp programmers have long used macros to extend their language. Indeed, their success has inspired macro notations for a variety of other languages, such as C and Java. There is, however, a paucity of effective pedagogic examples of macro use. This paper presents a short, non-trivial example that implements a construct not already found in mainstream languages. Furthermore, it motivates the need for tail-calls, as opposed to mere tail-recursion, and illustrates how support for tail-call optimization is crucial to support a natural style of macro-based language extension.

Key notes from the audio

These are mostly my notes and summaries for some key points that rang true with me. The ideas that they represent may or may not be contained within my summary as it would be too far outside the scope of this blog post to address them. Such work is better done by other papers and presentations.

  • 09:00: Without the hidden gems, syntax, macros, and tail calls, it all falls apart.
  • 11:16: What you generate must fit well into the language.
  • 18:00: It is really tail-transfer (tail-calls) that matter, not tail-recursion.
  • 21:00: Scheme is really an indentation based language.
  • 23:00: Macro languages belong in modules; you can use your data (DSL) where you wish.
  • 25:30: If you claim to be smart, leverage the work of others.
  • 26:10: Scheme is subtle. Takes years to understand what is beautiful. You can look at a book but you won’t notice. The language hides it jewels.
  • 26:45 If you don’t get tail calls, you don’t get it.

Key notes from the paper

  • P2P3: “A macro gives the programmer a consistent, representation-independent means of describing the datum
    while still resolving the representation before compilation.”
  • P7P4: Macros are likely to be used to optimize the abstraction that the data represents.
  • P8P3: Scheme’s macro system could be called “a lightweight compiler API”.
  • P9P2: Tail-calls ought to be called tail-transfer per Steele. I wonder why they didn’t push that definition more.
  • P9P3: Here is a good explanation of tail calls.
  • P9P5: “languages represent the ultimate form of reuse, because we get to reuse everything from the mathematical (semantics) to the practical (libraries), as well as decades of research and toil in compiler construction (Hudak, 1998).”
  • P13P2: “it shows how features that would otherwise seem orthogonal, such as macros and tail-calls, are in fact intimately wedded together; in particular, the absence of the latter would greatly complicate use of the former.”

The automaton language

; An automaton that recognizes the language c(ad)*r
(define m 
  (automaton init
             (init : 
                   (c → more))
             (more : 
                   (a → more)
                   (d → more)
                   (r → end))
             (end : accept)))

Scheme is mysophobic

Here is an interesting post about hygiene and its sociological impact on the two Lisp groups of Schemers and Common Lispers.

While the post itself is a troll, the author:

  1. Uses a very accessible analogy.
  2. Quite clearly communicates a number of differences between Scheme and Common Lisp when it comes not only to hygiene but also language design.

The interesting thing about this post is that the only difference between this post being a troll and an educational article is how the content was delivered. If you remove the cruddy name-calling, whining, and complaining; it would have been a really good post on the difference between the languages. That is wild!

(reference mysophobic)

Anaphoric Macros

Does the convenience that anaphoric macros provide justify breaking hygiene? In that chapter of On Lisp, the author stated that:

This chapter will show that variable capture can also be used constructively. There are some useful macros which couldn’t be written without it.

My evaluation of that claim is that while the former is true, anaphoric macros are not evidence of such a case as they only save you a variable binding. The latter claim is interesting because it begs the question of whether or not they should be written as macros at all. It made me wonder how anaphoric macros might look in Scheme, how they might look as functions, and whether one is clearly superior to the other.
Continue reading “Anaphoric Macros”

Companies using DSLs with Functional Programming Languages

One of the questions that has been lingering in the back of my mind for a long time is “When should a company use a DSL?”. My stock answer has always been “When it makes sense.”

Perhaps a better way is to answer that question is to look at how companies are actually using them today, rather then to simply guess!

Have a look at the “case studies” section in this presentation on ContractML to see how companies are using DSLs today.

(via cufp)

Code Generation and DSLs in Scheme

Over the years, I have heard some pretty outrageous and tantalizing claims made about the programming language Lisp. For example, “It will change you, forever.” and “You write code that writes code.”. Sadly, no further explanation is ever provided. Perhaps it is impossible to capture the essence of that to which these statements allude? This air of mystery around Lisp is both a blessing and a curse. Some folks will find this aura repugnant; others magical. For me, it was the latter. I wanted in on the secret!

Continue reading “Code Generation and DSLs in Scheme”