Over the years we have been gradually replacing the Annotation feature with the Keyword field feature. In release 0.43.0 the final step has been made by replacing the semantics of annotations with a "not implemented" error message with a Quick Fix suggestion. This feature removal went through the following stages to make for a smooth transition:

1. 2009-2013 only annotations implemented (syntax and semantics).
2. 2013-2019 both annotations and keyword fields implemented (syntax and semantics), but never at the same time on the same node.
3. 2019-2026 annotations simulated by keyword fields (both the syntactical features use semantics of keyword fields); Tree@\loc is simulated by Tree.src.
4. 2026-.... annotations not implemented anymore (only syntax), everything is a keyword field. anno loc Tree@\loc is replaced by data Tree(loc src=|unknown:///|) in the ParseTree module.

We are now past step 4. Every use of a syntactic construct related to annotations will produce:

1. an error message by the checker.
2. a Quick Fix suggestion to remove any and all uses of annotation syntax in the current project and replace them by the respective keyword field feature.
3. a static error by the interpreter.

Note that:

• If you don't fix the code, it will not run anymore and you will get static exceptions by the interpreter.
• After you have fixed the code, it may not run properly on older versions of Rascal anymore, because older versions always come with their own version of the ParseTree module.

For your convenience we list the differences in syntax and semantics here:

In stage 3, annotations took the semantics of keyword fields for declaration, assignment and matching, and equality while for projection still the old NoSuchAnnotation was thrown. This is the stage you have probably been using. The hard change was between stages 2 and 3.

The Quick Fix for stage 4 produces an arbitrary default for well known types, i.e. int age = 0, while for more complex type an exception is thrown by the default expression. It is advised to review the defaults manually.

Finally, the Quick Fix may open and rewrite a large group of files for the current project. You have to save and close each of them manually to write the result to disk. This would also be a good time to review the generated defaults.

If you get stuck, please contact Jurgen Vinju or Davy Landman for help.

In Rascal 0.42.0 we've removed the lib:/// resolver, and in Rascal 0.43.0 we removed the std:/// resolver. These schemes could be used to refer to library dependencies. However, since it was not always clear where locations with these schemes resolve to exactly, we have been working towards their replacement. For example, what if you click a |std:///IO.rsc| link in a Rascal Terminal, which version of that file should VS Code open?

std would be used to refer to modules in the Rascal standard library, for example std:///IO.rsc for IO. The lib scheme would be used to refer to files in other library dependencies (like lib://typepal or lib://rascal-lsp). In either case, it was not always clear to which instance of a library such a URI would resolve, or what the version of that library was. For example, depending on where it was used, std:///IO.rsc could resolve to a version of Rascal in the Maven repository, the Rascal that was shipped with the VS Code extension, or the standalone JAR that a REPL was started from.

These schemes have been removed. Any use of source locations with these schemes needs to be rewritten, since using these schemes will lead to an exception. The following replacements can be used.

• Where lib:// is used to refer to a project that is open in the VS Code workspace, replace it with project://.

• Where lib:// or std:// is used to refer to a dependency from the POM, compute the path config from the POM and find it in there.

  pcfg = getProjectPathConfig(<pom-root>);
  if (lib <- pcfg.libs, /--mylib--/ := lib.authority) {
    ; // do something with lib
  }
  

  Note for rascal and rascal-lsp: if they are not yet present in the POM, follow the instructions here.

  For experiments, a direct mvn:// URI can also be used. Note that this divert from the POM when the version in the POM is changed.

• In other cases, findResources can help.

In this post we report on important changes to dependency resolution and project configuration in Rascal 0.43.0 and Rascal LSP 2.23.0.

Since some time, Rascal projects have been gradually moving away from the manifest-based project configuration towards Maven's POM. Library depencies need to be specified in the POM. These libraries are resolved (and, if needed, downloaded) in the local Maven repository and used by Rascal tools like the VS Code extension (IDE features) and the Maven plugin (mvn compile).

However, the rascal and rascal-lsp dependencies were treated differently. In many cases, it was not even necessary to explicitly specifiy them in the POM, because they were implicitly added. And even if specified, their version would often be ignored in the IDE, due to implementation constraints.

Not anymore! In the past year, we have reworked many parts of Rascal and the VS Code extension. This allows the extension (and the maven plugin) to follow the POM more closely, leading to predictable and transparent dependency versions in Rascal projects (also enabled by the removal of library schemes). REPLs in VS Code and type-checks in the IDE will now use the Rascal standard library version from the POM, and language servers registered using registerLanguage will run with the specified Rascal and LSP versions.

In order to work with the newest release of the VS Code extension, new and existing projects should be set up with the proper dependencies. Rascal language projects might require code changes as well. Note that the VS Code extension will both inform you about this, and often offer a quick-fix for the problem.

Modifying existing Rascal projects​

Any new or existing project requires an explicit dependency on Rascal 0.43.0 in the POM:

<dependencies>
    <dependency>
        <groupId>org.rascalmpl</groupId>
        <artifactId>rascal</artifactId>
        <version>0.43.0</version>
    </dependency>
    <!-- other dependencies -->
</dependencies>

Modifying existing language projects​

Language projects are projects that use the util::LanguageServer library and/or use registerLanguage in the REPL. These projects require additional changes. First of all, they need a POM dependency on the newly released version of Rascal LSP, since this dependency is not implicitly derived from the development environment anymore.

<dependencies>
    <dependency>
        <groupId>org.rascalmpl</groupId>
        <artifactId>rascal-lsp</artifactId>
        <version>2.23.0</version>
    </dependency>
    <!-- other dependencies -->
</dependencies>

In any call to registerLanguage, the parameter should now contain a complete path config. This path config can be obtained by util::Reflective::getProjectPathConfig with the interpreter_external mode. This mode ensures that the the path config will be strictly based on the POM.

import util::LanguageServer;
import util::Reflective;

void main() {
    PathConfig pcfg = getProjectPathConfig(|project://my-project|, mode=interpreter_external());
    registerLanguage(language(pcfg, ....));
}

Under the hood, each registered language will run in a dedicated process. Languages are thus completely isolated in case of a crash, improving the robustness of the language server, especially when registering multiple languages. As a consequence, the memory of the extension might increased in case multiple languages are registered in parallel.

Vallang (https://github.com/usethesource/vallang) is a highly integrated and mostly-closed collection of mutually recursive fundamental data-types on the Java Virtual Machine:

• locations represented by URIs: |java+class://java/lang/String| and |file:///tmp/HelloWorld.java|
• integers of arbitrary size: 1,2,3, 134812345123841234
• reals of arbitrary size, precision and scale: 1., 1.0, 1e10
• rational numbers: 1r1, 1r7
• unicode strings: "hello 🌐"
• lists: [1,2, 1.0, "hello 🌐"], []
• sets: {1,2, 1.0, "hello 🌐"}, {}
• maps: (1:0, "a":"b"), ()
• n-ary tuples with named fields: <1,2,"a",1.0>, <>
• n-ary relations (represented as sets of n-ary tuples): {<1,2,"a",1.0>, <>}
• tree nodes: "myNode"(1,2,3)
• many-sorted algebraic terms, acting as typed tree nodes: myNode(1,2,3).
• keyword fields or properties to tree nodes and algebraic data-types: "myNode"(name="Winston"), myNode(age=12)

Operations on these data-types are too many to list here. A selection is listed below, but you should expect the features to be pretty low level; i.e. directly accessing and manipulating the data rather than providing analysis algorithms. Algorithms in the library are added only if programming them below the abstraction layer of vallang provides a major efficiency benefit or it can factors out highly common client code into a reusable feature. More on this design decision later.

• relational calculus operators such as transitive (reflexive) closure, query and projections, compositions and joins
• generic tree traversal and primitives for implementing pattern matching

Vallang has a type system based on type systems in functional programming, but note that each value has a most specific dynamic type associated always at run-time. More on the design of the type system below, but here is a list of vallang types:

• void - the bottom type with no values
• value - the top type for all values
• loc - the type for URI locations
• int, real, rat are all sub-types of the aggregate type num
• tuple[t1,...,tn] and tuple[t1 l1, ..., tn ln] to represent tuples of fixed but arbitrary arity
• list[t], set[t], map[t1,t2] as incomparable alternative collection types.
• node for trees
• user-defined many-sorted mutually recursive algebraic data-types, acting as grammars for instances of tree nodes: data MyADT = myNode(int a, int b, int c, int age=...)
• alias types for short-handed type equivalences
• rel[t1, ..., tn] is an alias for set[tuple[t1,...tn]]
• open type parameters with upper bounds, &T <: node, can be used to type parameterize composite types (used in type aliases) and to construct higher-order abstract algebraic datatypes.

Sub-typing is co-variant for the container types list, map, set and tuple. Otherwise these rules define the entire type system:

• value is a strict supertype of all other types other than itself
• node is the common supertype of all algebraic data-types
• each algebraic constructor is a strict sub-type of its abstract sort
• void is the sub-type of all types
• num is the supertype of rat, int and real
• an alias alias X = Y is a type equivalence
• constructor types are sub-types if they have the same name and arity, and they are comparable in their argument types.
  • Within a single abstract sort no two alternative constructors may be sub-types of each other.

There exists an extension mechanism for adding type kinds and their associated value kinds to the vallang system. Rascal, for example, uses this to represent functions and co-routines at run-time. The extension mechanism works by declaring a bi-directional transformation between the extensions and a symbolic representation of choice (chosen freely from the core representation mechanisms of vallang). This bidirectional mapping is mostly used when serializing and deserializing values (see below).

The types of vallang in Java are represented by a Composite design pattern with maximally shared instances of (the otherwise opaque) abstract class Type. These types expose fast implementations of sub-type and type equivalence for implementing fast pattern matching.

The values of vallang are all instances of IValue and sub-interfaces thereof. For every kind of value there is an interface, e.g. ISet, IList, ITuple and IConstructor but they are not type-parametrized because Java's type system can not represent the aforementioned co-variant sub-typing rules we require.

Why does Vallang exist?​

vallang is a UseTheSource project recently renamed from rascal-values, which was known earlier as pdb.values.

The project started as a part of the IDE metatooling platform in 2007 as a generic library for representing symbolic facts about source code, for use in the construction of IDE services in Eclipse, then it continued to form the basis of the run-time system for Rascal starting 2009, and finally was renamed to vallang to serve a wider scope.

We designed of vallang based on experience with and studying the ATerm library and ASF+SDF, but also by learning from RSF (Rigi Standard Format), Rscript and GXL and S-expressions. Perhaps JSON and YAML have also had a minor influence.

The main purpose of vallang is to provide a flexible and fully typed collection of symbolic representations of data, specifically "ready" to represent facts about software systems but amenable to basically any form of symbolic data analysis purposes.

This purpose aligns with the mission of the Rascal metaprogramming language which is made to analyze and manipulate exactly such symbolic representations. Therefore vallang is the run-time environment for both interpreted and compiled Rascal programs.

Note that while vallang is a great fit for symbolic data analysis, it is currently not the best fit for numerical data analysis as it features only a uniform symbolic represetation of numbers of arbitrary precision and size (ints, reals, rationals). In other words, the numbers and collections of numbers in vallang are optimized for storage size, clarity and equational reasoning rather than optimal computational efficiency. This also means that indirect numerical encodings of data (i.e. using numerical vectors and matrices), which are often used in symbolic analyses to optimize computational efficiency are not the right strategy when using vallang: it's better to stick with a more direct symbolic representation and let vallang maintainers optimize them.

Next to the maintainers of Rascal, the main users of vallang are currently programmers who write data acquisition and (de)serialisation adapters for the Rascal ecosystem:

• connecting open-compiler front-ends to Rascal
• providing external data-sources such as SQL and MongoDB databases
• connecting reusable interaction and visualization front-ends to Rascal

Nevertheless vallang is a generic and Rascal-independent library which may serve as the run-time system for other programming languages or analysis systems, such as term rewriting systems, relational calculus systems, constraint solvers, model checkers, model transformations, etc.

The latter perspective is the reason for the re-branding of rascal-values to vallang. You might consider vallang as a functional replacement for ECore, an alternative to the ATerm library on the JVM, or an alternative to JSON-based noSQL in-memory database systems, or a way of implementing graph databases.

Finally, vallang is a JVM library because that is where we needed it for Rascal and the Eclipse IDE Metatooling Platform. We hope other JVM programmers will also benefit from it and we have no plans of porting it at the moment to any other technological space.

What are the main design considerations of Vallang?​

Vallang values are symbolic and immutable.​

We think software analysis is complex enough to be confusing to even the most experienced programmers. Manipulating huge stores of hierarchical and relational data about softwar easily goes wrong; trivial bugs due to aliasing and sharing data between different stages of an analysis or transformation can take weeks to resolve, or worse: will never even be diagnosed.

Since our goal is to provide many more variants of all kind of software analyses, we wish to focus on the interesting algorithmic details rather than the trivial mistakes we make. Therefore, vallang values are immutable. Sharing of values or parts of values is allowed under-the-hood but is not observable. The library is implemented using persistent and/or maximally shared data structures for reasons of efficiency.

Users of vallang freely share references to their data to other parts of an analysis because they know the data can not change due to an unforeseen interaction. We also believe that the immutable values can be shared freely between threads on the JVM, but there are not enough tests yet to make such a bold claim with full confidence.

Vallang values are generated via the AbstractFactory design pattern and do not leak implementation representations​

The reason is that client code must abstract from the implementation details to arrive at the mathematical precision of symbolic reasoning which vallang should provide.

This also serves a maintenance and evolution purpose for implementations of the library. We can plug in a new implementation of the library without affecting client code.

Note that for efficiency reasons values produced from different implementations of an abstract value factory (different implementations of IValueFactory) are not required to interact correctly.

Vallang values uniquely deserialize/serialize from/to a standard and simple expression language​

The general rule is that for any two JVM object reference o and p to any vallang object the following rule holds: o.toString().equals(p.toString) <==> o.equals(p)

We currently random test this rule and it sometimes fails due to a deprecated feature called "annotations" which we are removing to make the above contract true.

The intended effects of the toString/equals contract of vallang are the following:

• What-you-see-is-what-you-get: debugging values by printing them means that you get as a programmer full disclosure about the meaning of the object
• Structural equality and equational reasoning: the context in which values are created can not have any influence on their identity
• Sharing is safe
• Serialisation and deserialisation is never lossy
• The sub-type relation for types of values coincides exactly with sublanguage concept of the set of sentences for all values of the given types.

The latter point is one of the main reasons why vallang is called a language. The result of anyValue.toString() is a members of a precisely defined textual languages. The full textual language is generated from the value type, and sub-languages are generated from the respective sub-types. void is the empty language. In this manner the types of vallang act like non-terminals of a precise context-free grammar. The vallang language as defined above is a strict sub-language of the Expression sub-language of Rascal.

The other reason why vallang is names as a language is because the implementations of the IValue interface and its sub-interfaces are seen as a closed combinator language for computations on the values, and their implementations are interpreters for this language.

Vallang values always know their most-precise concrete ad-hoc run-time type​

• This is nice for debugging purposes, the types are descriptions of values and if matching or equality checking fails then the type abstraction usually explains why without having to go into reading the entire value.
• Types may be computed lazily or eagerly, cashed or not. This is not functionally observable but it may affect run-time efficiency
• Having precise run-time types for every (nested) value, and having efficient access to this, is a prerequisite for building fast and type-safe rank-2 polymorphic higher order functional computations. Or in functional terms: you need this to make folds and maps work on heterogenous recursive and open data-types. Or in simpler terms: using this we can build statically type-safe data traversal and daya transformation features into Rascal.

Vallang values include both trees and relations​

Even though both trees and relations are generic enought to represent any data, sometimes a graph or table is more natural than a tree and sometimes the other way around.

• trees are nice for abstract and concrete syntax representations
• trees are nice for abstract symbolic domains, such as terms for constraint variables and binary constraints
• relations are nice for graph-like unstructred data, such as project dependencies, call graphs, etc.
• relations are nice for access to external data stored in spreadsheets and databases
• trees are nice for access to web data stored in HTML, XML, JSON formats etc.
• trees are good for transformation purposes, where we parse something, rewrite it and unparse it again
• relations are good for analysis purposes, where we extract facts, elaborate on them and finally report the result.

Rascal is a language which can be used to easily switch between different representations of the same information, using pattern matching, querying, comprehensions, etc. From vallang you should not expect any help in this regard: the choice of representation for any information is a key design decision for the user of vallang.

Who contributed to Vallang?​

• Robert M. Fuhrer (IBM TJ Watson)
• Jurgen J. Vinju (IBM TJ Watson and Centrum Wiskunde & Informatica)
• Arnold Lankamp (Centrum Wiskunde & Informatica)
• Michael Steindorfer (Centrum Wiskunde & Informatica and TU Delft)
• Davy Landman (Centrum Wiskunde & Informatica and SWAT.engineering)
• Paul Klint (Centrum Wiskunde & Informatica)

and occasional contributions from others please see github's factual overview

What is in the near future for Vallang?​

1. Removal of the "annotations" feature, which is completely replaces by the "keyword fields" feature. The main differences between these features are:
   • While they both offer extensibility to the set of names and typed fields of nodes and constructors, annotations can never influence equals() while keyword fields always do.
   • Syntactically the notation for keyword fields is more compact: f()[@myAnno=1] versus f(myField=1)
2. Further integration of the capabilities of Capsule for persistent and optimized immutable collections under the hood of IMap, ISet, IRelationAlgebra:
   • Reflexive relations with two indices (for both columns)
   • Heterogeneous collections of numbers (unboxing down to primitive types to safe space)
   • Smooth and incremental transitions from map to multimap representations
3. IBag, the bag[&T] type

Helping PHP developers using Rascal-based code analysis.

@inproceedings{hillsicpc2016,
  author = "Mark Hills",
  title = "Navigating the WordPress Plugin Landscape",
  fulltext = "http://www.cs.ecu.edu/hillsma/publications/icpc-plugins-2016.pdf",
  booktitle = "Proceedings of the 2015 {IEEE} 23rd International Conference on Program
               Comprehension"
  year = 2016,
  location = Austin,
  month = may,
}

WordPress includes a plugin mechanism that allows user-provided code to be executed in response to specific system events and input/output requests. The large number of extension points provided by WordPress makes it challenging for new plugin developers to understand which extension points they should use, while the thousands of existing plugins make it hard to find existing extension point handler implementations for use as examples when creating a new plugin. In this paper, we present a lightweight analysis, supplemented with information mined from source comments and the webpages hosted by WordPress for each plugin, that guides developers to the right extension points and to existing implementations of handlers for these extension points. We also present empirical information about how plugins are used in practice, providing guidance to both tool and prospective plugin developers.

This paper won a Best Paper award at ICPE 2016 in Delft.

@inproceedings{icpe2016-steindorfer,
 author = {Michael Steindorfer and Jurgen J. Vinju.},
 title = {Performance Modeling of Maximal Sharing},
 booktitle = {7th ACM/SPEC International Conference on Performance Engineering (ICPE)},
 year = 2016,
 fulltext = "http://homepages.cwi.nl/~jurgenv/papers/ICPE16.pdf"
}

It is noticeably hard to predict the effect of optimization strategies in Java without implementing them. “Maximal sharing” (a.k.a. “hash-consing”) is one of these strategies that may have great benefit in terms of time and space, or may have detrimental overhead. It all depends on the redundancy of data and the use of equality. We used a combination of new techniques to predict the impact of maximal sharing on existing code: Object Re- dundancy Profiling (ORP) to model the effect on memory when sharing all immutable objects, and Equals-Call Profil- ing (ECP) to reason about how removing redundancy impacts runtime performance. With comparatively low effort, using the MAximal SHaring Oracle (MASHO), a prototype pro- filer based on ORP and ECP, we can uncover optimization opportunities that otherwise would remain hidden. We report on the experience of applying MASHO to real and complex case: we conclude that ORP and ECP combined can accurately predict gains and losses of maximal sharing, and also that (by isolating variables) a cheap predictive model can sometimes provide more accurate information than an expensive experiment can.

Check out these two related articles on the empirical relation between the CC and SLOC source code metrics.

@ARTICLE{jsep2015-landman,
  author = { Davy Landman and Alexander Serebrenik and Eric Bouwers and Jurgen J. Vinju },
  title = { {Empirical analysis of the relationship between CC and SLOC in a large corpus of Java methods and C functions} },
  journal = { Journal of Software: Evolution and Process },
  year = { 2015 },
  doi = { 10.1002/smr.1760 },
  fulltext  = "http://homepages.cwi.nl/~landman/docs/Landman2015-ccsloc-jsep2015-preprint.pdf",
  datalink = { http://homepages.cwi.nl/~landman/jsep2015/ },
}

@INPROCEEDINGS{Landman2014,
  author = { Davy Landman and Alexander Serebrenik and Jurgen J. Vinju },
  title = { {Empirical analysis of the relationship between CC and SLOC in a large corpus of Java methods} },
  booktitle = { 30th IEEE International Conference on Software Maintenance and
  Evolution, ICSME 2014 },
  year = { 2014 },
  datalink = { http://homepages.cwi.nl/~landman/icsme2014/ },
  fulltext= "http://homepages.cwi.nl/~landman/docs/Landman2014-ccsloc-icsme2014-preprint.pdf"
}

Measuring the internal quality of source code is one of the traditional goals of making software development into an engineering discipline. Cyclomatic Complexity (CC) is an often used source code quality metric, next to Source Lines of Code (SLOC). However, the use of the CC metric is challenged by the repeated claim that CC is redundant with respect to SLOC due to strong linear correlation.

We conducted an extensive literature study of the CC/SLOC correlation results. Next, we tested correlation on large Java (17.6 M methods) and C (6.3 M functions) corpora. Our results show that linear correlation between SLOC and CC is only moderate as caused by increasingly high variance. We further observe that aggregating CC and SLOC as well as performing a power transform improves the correlation.

Our conclusion is that the observed linear correlation between CC and SLOC of Java methods or C functions is not strong enough to conclude that CC is redundant with SLOC. This conclusion contradicts earlier claims from literature, but concurs with the widely accepted practice of measuring of CC next to SLOC.

Hash-tries are the data-structure under Rascal's sets, maps and relations. These papers explain how they work and how we make them lean and fast on the JVM. Others have blogged about these results as well. The code can be found in the Capsule project.

@inproceedings{oopsla2015,
  title = {Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections}
  author = {Michael Steindorder and Jurgen J. Vinju}.
  year = 2015,
  booktitle = {Proceedings of the Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA)},
  editor = {Patrick Eugster},
  fulltext = "http://michael.steindorfer.name/publications/oopsla15.pdf",
}

@inproceedings{gpce14,
 author = {Steindorfer, Michael J. and Vinju, Jurgen J.},
 title = {Code Specialization for Memory Efficient Hash Tries},
 booktitle = {Proceedings of the 2014 International Conference on Generative Programming: Concepts and Experiences},
 series = {GPCE 2014},
 year = {2014},
 pages = {11--14},
 numpages = {4},
 doi = {10.1145/2658761.2658763},
 publisher = {ACM},
 fulltext = "http://michael.steindorfer.name/publications/gpce14.pdf"
} 

The data structures under-pinning collection API (e.g. lists, sets, maps) in the standard libraries of programming languages are used intensively in many applications. The standard libraries of recent Java Virtual Machine languages, such as Clojure or Scala, contain scalable and well-performing immutable collection data structures that are implemented as Hash-Array Mapped Tries (HAMTs). HAMTs already feature efficient lookup, insert, and delete operations, however due to their tree-based nature their memory footprints and the runtime performance of iteration and equality checking lag behind array-based counterparts. This particularly prohibits their application in programs which process larger data sets. In this paper, we propose changes to the HAMT design that increase the overall performance of immutable sets and maps. The resulting general purpose design increases cache locality and features a canonical representation. It outperforms Scala’s and Clojure’s data structure implementations in terms of memory footprint and runtime efficiency of iteration (1.3– 6.7 x) and equality checking (3–25.4 x).

Rascal features immutable data, but at the same time a number of language constructs which are a lot like "traditional" structured imperative programming: while, if, etc. Without going into the full power of these constructs in Rascal (featuring lexically scoped backtracking, for example) in this post we go into how in the same language we can program imperatively and functionally at the same time.

The reason Rascal features these two styles is that we want to make it easy for programmers who are used to the imperative paradigm to step into the language. More importantly, we want to make it easy to type classical textbook examples of program analysis and transformations pseudocode rather directly into Rascal syntax.

A story about even numbers​

Let's write a function that generates all the even numbers in a list up to a certain maximum. We will do it in a few alternative ways: from very imperative to very declarative and some steps in between.

list[int] even0(int max) {
  list[int] result = [];
  for (int i <- [0..max])
    if (i % 2 == 0)
      result += i;
  return result;
}

Now lets remove the temporary type declarations:

list[int] even1(int max) {
  result = [];
  for (i <- [0..max])
    if (i % 2 == 0)
      result += i;
  return result;
}

To make the code shorter, we can inline the condition in the for loop:

list[int] even2(int max) {
  result = [];
  for (i <- [0..max], i % 2 == 0)
    result += i;
  return result;
}

In fact, for loops may produce lists as values, using the append statement:

list[int] even3(int max) {
  result = for (i <- [0..max], i % 2 == 0)
    append i;
  return result;
}

So now, the result temporary is not necessary anymore:

list[int] even4(int max) {
  return for (i <- [0..max], i % 2 == 0)
           append i;
}

This code is actually very close to a list comprehension already:

list[int] even5(int max) {
  return [ i | i <- [0..max], i % 2 == 0];
}

And now we can just define even using an expression only:

list[int] even6(int max) = [i | i <- [0..max], i % 2 == 0];

Or, perhaps we like a set instead of a list:

set[int] even7(int max) = {i | i <- [0..max], i % 2 == 0};

What just happened?​

In summary:

• We went from 5 lines of code to 1
• We went from 3 control flow constructs (for, if, return) to 0
• We introduced a list comprehension
• All expressions have remained equal
• Intermediate temporary variables dissappeared

What did not happen is any magic. The code still executes the same "algorithm" if you will. The functional programming style in Rascal can be seen as a shorter notation for a more bloated use of imperative control flow constructs.

The usefulness of imperative control flow constructs​

Up front, Rascal's control flow constructs are more powerful than general purpose programming languages control flow constructs. They feature lexically scoped backtracking, lists of conditions, etc.

Even without those advanced features, it is sometimes very handy to split a computation in parts without having to introduce another function abstraction. While exploring a new algorithm, temporary variables can be printed and inspected at debug time, etc.

In Rascal, people often use imperative control flow to explore solutions or copy them from text books, and when they are happy with the algorithm they try and improve the formulation by finding the right functional abstractions.

The benefit of functional abstraction over imperative control flow​

The real benefits, above brevity and elegance, of the functional style over the imperative style are reusability and extensibility. Smaller functional abstractions are easier to reuse and easier to override. Also, using Rascal's dynamic dispatch using pattern matching (a.k.a. term rewriting) adding new options to algebraic data types can be complemented with adding new cases for functions. In the imperative style such an extension would imply editing existing code, while in the functional style this would not be necessary. See also this other post.

This post dives into some of the design decisions regarding the manipulation of parse trees and abstract syntax trees in Rascal using concrete syntax notation.

Definitions​

What we call concrete syntax is a notation for syntax trees that is embedded into the expression notation of meta programming languages. This notation should be equal, or mostly equal, to the surface syntax of the language that is represented by the syntax trees, and the expressions are still syntactically and statically checked for correctness. As far as notations for syntax trees go, concrete syntax is a clear winner. Let's compare some expressions representing a piece of C code.

Concrete syntax​

if (a && b) { 
  println("a and b"); 
}

Lisp S-expressions​

(if ((and (id "a") (id "b")) 
    (block 
      ((call (id "println") (args (strconst "a and b")))
    )
)

XML​

<if>
  <and>
    <id>a</id>
    <id>b</id>
  </and>
  <block>
    <call>
      <id>println</id>
      <args>
        <strconst>a and b</strconst>
      </args>
    </call>
  </block>
</if>

YAML/JSON​

if:
  - and:
     - id: a
     - id: b
  - block:
     - call:
        - id: println
        - args:
          - strconst: a and b 

For the degenerate case of a single node with no children, of course any abstract notation wins. As soon as we have nesting, even marginally interesting code snippets, however, concrete syntax wins by landslide in terms of brevity and cognitive overload.

Meta Variables​

The above examples showed only literal program fragments. One distinguishing feature, however, of concrete syntax is ...

History​

The concrete syntax feature appeared first, as far as I know and please correct me if I am wrong, in the early 1980's in experimental meta programming systems and algebraic specification systems. There was a concept of mix fix operator syntax where algebraic operators would not only be exclusively prefix, postfix or infix, but all at the same time. This would allow, for example, to define readable algebraic operators with arity larger than two such as if _ then _ else _. Some systems started to use BNF to define mix fix functions, and concrete syntax was born. In extreme cases, such as ASF+SDF any context-free grammar rule was allowed to be an operator, while in other systems more restrictions could apply.

If you are interested in what this all looked like, also in the years after that, the following is a list of names of systems that used or use mixfix operators or concrete syntax in some form or another:

• ASF+SDF
• TXL
• StrategoXT
• Maude
• ELAN
• OBJ
• Smarttools
• Repleo
• SugarJ
• K

People that I know by heart who published on the concrete syntax feature are Annika Aasa, Kent Petersson, Dan Synek, Chris Verhoef, Paul Klint, Eelco Visser, Peter Borovansky, Jan Rekers, Martin Bravenboer, Rob Vermaas, Radu Mereuta, Dorel Lucanu, Jeroen Arnoldus, and yours truly. There must be more.

Concrete syntax should not be confused with string or file templates, such as found in PHP-like template expanders. The difference is that such templates are flat strings that are not statically checked or parsed. With concrete syntax you can not write a pattern that will never match, and you can not write a pattern that will construct a syntactically incorrect output.

Concrete syntax is also strongly related to the older concept of syntax macros (1970's). The similarity is that with syntax macros the user can also define the syntax of functions. The difference is that syntax macros are always expanded into the host language, while with concrete syntax the objects can be manipulated in an arbitrary way, often not to expand into the host language but rather to output a transformed output form.

So, concrete syntax is not new or novel in any way. It is a good idea nevertheless, and it comes with interesting language usability trade-offs.

Quotes​

Types​

Rascal​