Programming languages with a Lisp-like syntax extension mechanism [closed]

Question

I have only a limited knowledge of Lisp (trying to learn a bit in my free time) but as far as I understand Lisp macros allow to introduce new language constructs and syntax by describing them in Lisp itself. This means that a new construct can be added as a library, without changing the Lisp compiler / interpreter.

This approach is very different from that of other programming languages. E.g., if I wanted to extend Pascal with a new kind of loop or some particular idiom I would have to extend the syntax and semantics of the language and then implement that new feature in the compiler.

Are there other programming languages outside the Lisp family (i.e. apart from Common Lisp, Scheme, Clojure (?), Racket (?), etc) that offer a similar possibility to extend the language within the language itself?

EDIT

Please, avoid extended discussion and be specific in your answers. Instead of a long list of programming languages that can be extended in some way or another, I would like to understand from a conceptual point of view what is specific to Lisp macros as an extension mechanism, and which non-Lisp programming languages offer some concept that is close to them.

Answer 1

Scala makes this possible too (in fact it was consciously designed to support the definition of new language constructs and even complete DSLs).

Apart from higher-order functions, lambdas and currying, which are common in functional languages, there are some special language features here to enable this*:

• no operators - everything is a function, but function names can include special characters like '+', '-' or ':'
• dots and braces can be omitted for single-parameter method calls, i.e. a.and(b) is equivalent to a and b in infix form

• for single-parameter function calls you may use curly brackets instead of normal braces - this (together with currying) allows you to write things like

  val file = new File("example.txt")
  
  withPrintWriter(file) {
    writer => writer.println("this line is a function call parameter")
  }
  

  where withPrintWriter is a plain method with two parameter lists, both containing a single parameter

• by-name parameters allow you to omit empty parameter list in lambdas, allowing you to write calls like myAssert(() => x > 3) in a shorter form as myAssert(x > 3)

The creation of an example DSL is discussed in detail in Chapter 11. Domain-Specific Languages in Scala of the free book Programming Scala.

*_{I don't mean these are unique to Scala, but at least they don't seem to be very common. I am not an expert in functional languages though.}

Answer 2

Perl allows for pre-processing of its language. While this isn't often used to the extent of radically changing the syntax in the language, it can be seen in some of the... odd modules:

• Acme::Bleach for really clean code
• Acme::Morse for writing in morse code
• Lingua::Romana::Perligata for writing in Latin (for examples, nouns are variables and number, case, and declension change the type of the noun nextum ==> $next, nexta ==> @next)

There also exists a module that makes allows perl to run code that looks like it was written in Python.

A more modern approach to this within perl would be to use Filter::Simple (one of the core modules in perl5).

Note that all those examples involve Damian Conway who has been referred to as the "Mad Doctor of Perl". Its still an amazingly powerful ability within perl to twist the language how one wants it.

More documentation for this and other alternatives exists at perlfilter.

Answer 3

Haskell

Haskell has "Template Haskell" as well as "Quasiquotation":

http://www.haskell.org/haskellwiki/Template_Haskell

http://www.haskell.org/haskellwiki/Quasiquotation

These features allow users to dramatically add to the syntax of the language outside of normal means. These are resolved at compile time as well, which I think is a big must (for compiled languages at least) [1].

I have used quasiquotation in Haskell once before to create an advanced pattern matcher over a C-like language:

moveSegment :: [Token] -> Maybe (SegPath, SegPath, [Token])
moveSegment [hc| HC_Move_Segment(@s, @s); | s1 s2 ts |] = Just (mkPath s1, mkPath s2, ts)
moveSegment _ = Nothing

[1] Else the following qualifies as syntax extension: runFeature "some complicated grammar enclosed in a string to be evaluated at runtime", which of course is a load of crap.

Answer 4

Tcl has a long history of supporting extensible syntax. For example, here's the implementation of a loop that iterates three variables (until stopped) over the cardinals, their squares and their cubes:

proc loopCard23 {cardinalVar squareVar cubeVar body} {
    upvar 1 $cardinalVar cardinal $squareVar square $cubeVar cube

    # We borrow a 'for' loop for the implementation...
    for {set cardinal 0} true {incr cardinal} {
        set square [expr {$cardinal ** 2}]
        set cube [expr {$cardinal ** 3}]

        uplevel 1 $body
    }
}

That would then be used like this:

loopCard23 a b c {
    puts "got triplet: $a, $b, $c"
    if {$c > 400} {
        break
    }
}

This sort of technique is used extensively in Tcl programming, and the key to doing it sanely are the upvar and uplevel commands (upvar binds a named variable in another scope to a local variable, and uplevel runs a script in another scope: in both cases, the 1 indicates that the scope in question is the caller's). It's also used a lot in code that couples with databases (running some code for each row in a result set), in Tk for GUIs (for doing binding of callbacks to events), etc.

However, that's only a fraction of what is done. The embedded language doesn't even need to be Tcl; it can be virtually anything (as long as it balances its braces — things get syntactically horrible if that's not true — which is the enormous majority of programs) and Tcl can just dispatch to the embedded foreign language as necessary. Examples of doing this include embedding C to implement Tcl commands and the equivalent with Fortran. (Arguably, all Tcl's built-in commands are done this way in a sense, in that they're really just a standard library and not the language itself.)

Answer 5

This is partly a question of semantics. The basic idea of Lisp is that the program is data that can itself be manipulated. Commonly-used languages in the Lisp family, like Scheme, don't really let you add new syntax in the parser sense; it's all just space-delimited parenthesized lists. It's just that since the core syntax does so little, you can make almost any semantic construct out of it. Scala (discussed below) is similar: the variable-name rules are so liberal that you can easily make nice DSLs out of it (while staying within the same core syntax rules).

These languages, while they don't actually let you define new syntax in the sense of Perl filters, have a sufficiently flexible core that you can use it to build DSLs and add language constructs.

The important common feature is that they let you define language constructs that work as well as built-in ones, using features exposed by the languages. The degree of support for this feature varies:

• Many older languages provided built-in functions like sin(), round(), etc., without any way to implement your own.
• C++ provides limited support. For example some built-in keywords like casts (static_cast<target_type>(input), dynamic_cast<>(), const_cast<>(), reinterpret_cast<>()) can be emulated using template functions, which Boost uses for lexical_cast<>(), polymorphic_cast<>(), any_cast<>(), ....
• Java has built-in control structures (for(;;){}, while(){}, if(){}else{}, do{}while(), synchronized(){}, strictfp{}) and doesn't let you define your own. Scala instead defines an abstract syntax that lets you call functions using a convenient control-structure-like syntax, and libraries use this to effectively define new control structures (e.g. react{} in the actors library).

---

Also, you might look at Mathematica's custom syntax functionality in the Notation package. (Technically it is in the Lisp family, but has some extensibility features done differently, as well as the usual Lisp extensibility.)

Answer 6

Rebol sounds almost like what you're describing, but a bit sideways.

Rather than define specific syntax, everything in Rebol is a function call - there are no keywords. (Yes, you can redefine if and while if you truly desire to). For example, this is an if statement:

if now/time < 12:00 [print "Morning"]

if is a function that takes 2 arguments: a condition and a block. If the condition is true, the block is evaluated. Sounds like most languages, right? Well, the block is a data structure, it's not restricted to code - this is a block of blocks, for example, and a quick example of the flexibility of "code is data":

SomeArray: [ [foo "One"] [bar "Two"] [baz "Three"] ]
foreach action SomeArray [action/1: 'print] ; Change the data
if now/time < 12:00 SomeArray/2 ; Use the data as code - right now, if now/time < 12:00 [print "Two"]

As long as you can stick to the syntax rules, extending this language is, for the most part, going to be nothing more than defining new functions. Some users have been backporting features of Rebol 3 into Rebol 2, for example.

Answer 7

Ruby has a quite flexible syntax, I think it's a way of "extend the language within the language itself".

An example is rake. It's written in Ruby, it is Ruby, but it looks like make.

To check some possibilities you can look for the keywords Ruby and metaprogramming.

Answer 8

Extending the syntax the way you're talking about allows you to create domain specific languages. So perhaps the most useful way to rephrase your question is, what other languages have good support for domain specific languages?

Ruby has very flexible syntax, and a lot of DSLs have flourished there, such as rake. Groovy includes a lot of that goodness. It also includes AST transforms, which are more directly analogous to Lisp macros.

R, the language for statistical computing, allows functions to get their arguments unevaluated. It uses this to create a DSL for specifying regression formula. For example:

y ~ a + b

means "fit a line of the form k0 + k1*a + k2*b to the values in y."

y ~ a * b

means "fit a line of the form k0 + k1*a + k2*b + k3*a*b to the values in y."

And so on.

Answer 9

Converge is another one non-lispy metaprogramming language. And, to some extent, C++ qualifies too.

Arguably, MetaOCaml is quite far from Lisp. For a totally different style of syntax extensibility, but yet quite powerful, take a look at CamlP4.

Nemerle is another extensible language with a Lisp-style metaprogramming, although it is closer to languages like Scala.

And, Scala itself will soon become such a language too.

Edit: I forgot about the most interesting example - JetBrains MPS. It is not only very distant from anything Lispish, it is even a non-textual programming system, with an editor operating directly on an AST level.

Edit2: To answer an updated question - there is nothing unique and exceptional in the Lisp macros. In theory, any language can provide such a mechanism (I even did it with plain C). All you need is an access to your AST and an ability to execute code in compilation time. Some reflection might help (querying about the types, the existing definitions, etc.).

Answer 10

Prolog allows defining new operators which are translated to compound terms of the same name. For example, this defines a has_cat operator and defines it as a predicate for checking if a list contains the atom cat:

:- op(500, xf, has_cat).
X has_cat :- member(cat, X).

?- [apple, cat, orange] has_cat.
true ;
false.

The xf means that has_cat is a postfix operator; using fx would make it a prefix operator, and xfx would make it an infix operator, taking two arguments. Check this link for more details about defining operators in Prolog.

Answer 11

The evaluation Mathematica is based on pattern matching and replacement. That allows you to create your own control structures, change existing control structures or change the way expressions are evaluated. For example, you could implement "fuzzy logic" like this (a bit simplified):

fuzzy[a_ && b_]      := Min[fuzzy[a], fuzzy[b]]
fuzzy[a_ || b_]      := Max[fuzzy[a], fuzzy[b]]
fuzzy[!a_]           := 1-fuzzy[a]
If[fuzzy[a_], b_,c_] := fuzzy[a] * fuzzy[b] + fuzzy[!a] * fuzzy[c]

This overrides the evaluation for the predefined logical operators &&,||,! and the built-in If clause.

You can read these definitions like function definitions, but the real meaning is: If an expression matches the pattern described on the left side, it's replaced with the expression on the right side. You could define your own If-clause like this:

myIf[True, then_, else_] := then
myIf[False, then_, else_] := else
SetAttributes[myIf, HoldRest]

SetAttributes[..., HoldRest] tells the evaluator that it should evaluate the first argument before the pattern matching, but hold evaluation for the rest until after the pattern has been matched and replaced.

This is used extensively inside the Mathematica standard libraries to e.g. define a function D that takes an expression and evaluates to its symbolic derivative.

Answer 12

TeX is totally missing from the list. You all know it, right? It looks something like this:

Some {\it ``interesting''} example.

… except that you can redefine the syntax without restrictions. Every (!) token in the language can be assigned a new meaning. ConTeXt is a macro package which has replaced curly braces with square braces:

Some \it[``interesting''] example.

The more common macro package LaTeX also redefines the language for its purposes, e.g. adding the \begin{environment}…\end{environment} syntax.

But it doesn’t stop there. Technically, you could just as well redefine the tokens to parse the following:

Some <it>“interesting”</it> example.

Yes, absolutely possible. Some packages use this to define small domain-specific languages. For instance, the TikZ package defines a concise syntax for technical drawings, which allows the following:

\foreach \angle in {0, 30, ..., 330} 
  \draw[line width=1pt] (\angle:0.82cm) -- (\angle:1cm);

Furthermore, TeX is Turing complete so you can literally do everything with it. I have never seen this used to its full potential because it would be pretty pointless and very convoluted but it’s entirely possible to make the following code parseable just by redefining tokens (but this would probably go to the physical limits of the parser, due to the way it’s built):

for word in [Some interesting example.]:
    if word == interesting:
        it(word)
    else:
        word

Answer 13

Boo lets you customize the language heavily at compile-time through syntactic macros.

Boo has an "extensible compiler pipeline". That means the compiler can call your code to do AST transformations at any point during the compiler pipeline. As you know, things like Java's Generics or C#'s Linq are just syntax transformations at compile time, so this is quite powerful.

Compared to Lisp, the main advantage is that this works with any kind of syntax. Boo is using a Python-inspired syntax, but you could probably write an extensible compiler with a C or Pascal syntax. And since the macro is evaluated at compile time, there's no performance penalty.

Downsides, compared to Lisp, are:

• Working with an AST is not as elegant as working with s-expressions
• Since the macro is invoked at compile time, it doesn't have access to runtime data.

For example, this is how you might implement a new control structure:

macro repeatLines(repeatCount as int, lines as string*):
    for line in lines:
        yield [| print $line * $repeatCount |]

usage:

repeatLines 2, "foo", "bar"

which then gets translated, at compile time, to something like:

print "foo" * 2
print "bar" * 2

(Unfortunately, Boo's online documentation is always hopelessly outdated and doesn't even cover advanced stuff like this. The best documentation for the language I know is this book: http://www.manning.com/rahien/)

Answer 14

Metalua is a language and a compiler compatible with Lua that provides this.

• Full compatibility with Lua 5.1 sources and bytecode: clean, elegant semantics and syntax, amazing expressive power, good performances, near-universal portability. - A complete macro system, similar in power to what's offfered by Lisp dialects or Template Haskell; manipulated programs can be seen
  as source code, as abstract syntax trees, or as an arbitrary mix
  thereof, whichever suits your task better.

• A dynamically extensible parser, which lets you support your macros with a syntax that blends nicely with the rest of the language.

• A set of language extensions, all implemented as regular metalua macros.

Differences with Lisp:

• Don't bother developers with macros when they aren't writing one: the language's syntax and semantics should be best suited for those 95% of the time when we aren't writing macros.
• Encourage developers to follow the conventions of the language: not only with "best practices rants" nobody listen to, but by offering an API that makes it easier to write things the Metalua Way. Readability by fellow developers is more important and more difficult to achieve than readability by compilers, and for this, having a common set of respected conventions helps a lot.
• Yet provide all the power one's willing to handle. Neither Lua nor Metalua are into mandatory bondage and discipline, so if you know what you're doing, the language won't get in your way.
• Make it obvious when something interesting happens: all meta-operations happen between +{...} and -{...}, and visually stick out of the regular code.

An exemple of application is the implementation of ML-like pattern matching.

See also : http://lua-users.org/wiki/MetaLua

Answer 15

If you're looking for languages that are extendable, you ought to take a look at Smalltalk.

In Smalltalk, the only way to program is to actually extend the language. There is no difference between the IDE, the libraries or the language itself. They're all so entwined that Smalltalk is often referred to as an environment rather than as a language.

You don't write stand-alone applications in Smalltalk, you extend the language-environment instead.

Check out http://www.world.st/ for a handful of resources and information.

I'd like to recommend Pharo as the dialect of entry to the world of Smalltalk: http://pharo-project.org

Hope it helped!

Answer 16

There are tools that allow making custom languages without writing a whole compiler from scratch. For example there is Spoofax, which is a code transformation tool: you put in input grammar and transformation rules (written in a very high level declarative way), and then you can generate Java source code (or other language, if you care enough) from a custom language designed by you.

So, it would be possible to take grammar of language X, define grammar of language X' (X with your custom extensions) and transformation X'→X, and Spoofax will generate a compiler X'→X.

Currently, if I understand correctly, the best support is for Java, with C# support being developed (or so I heard). This technique could be applied to any language with static grammar (so, e.g. probably not Perl) though.

Answer 17

Forth is another language that is highly extensible. Many Forth implementations consist of a small kernel written in assembler or C, then the rest of the language is written in Forth itself.

There are also several stack-based languages that are inspired by Forth and share this feature, such as Factor.

Answer 18

Funge-98

Funge-98's fingerprint feature allows could be done to allow a complete restructuring of the entire syntax and semantics of the language. But only if the implementor supplies a fingerprint mechanism that allowed the user to programmatically alter the langauage (this is theoretically possible to implement within normal Funge-98 syntax and semantics). If so, one could literally make the rest of the file (or whatever parts of the file) act as C++ or Lisp (or whatever he wants).

http://quadium.net/funge/spec98.html#Fingerprints

Answer 19

To get what you're looking for you really need those parentheses and a lack of syntax. A few syntax-based languages may come close, but it is not quite the same thing as a true macro.