A Meta-Circular Evaluator for Julia

March, 2024

1 Introduction

A meta-circular evaluator is an excellent tool for experimentation in language design. In its simplest

form, a meta-circular evaluator for languageLis a program written in languageLthat takes an

expression written in languageLand computes its meaning.

During the Advanced Programming course, we studied the implementation of a meta-circular

evaluator for the programming language Scheme, which we then easily extended to experiment

with different evaluation rules, including dynamic scope, lexical scope, short-circuit evaluation,

and non-deterministic evaluation, among others.

2 Goals

The goal of this project is to develop a meta-circular evaluator for a subset of the Julia programming

language named MetaJulia. More specifically, the evaluator needs to support the evaluation of

untyped but correct Julia programs, i.e., Julia programs that do not include type declarations and

that do not throw exceptions, with all the syntatical forms demonstrated below.

You must also implement a Julia function namedmetajulia_replthat starts a Julia’s REPL

(with a>>prompt) that allows testing of the evaluator. To simplify your task, you might want to

use theMeta.parsefunction but, obviously, you cannot use Julia’s predefinedevalfunction.

Below, we present examples of evaluations using the MetaJulia language that you might want

to use as tests of your own evaluator.

Boolean values are useful in conditional expressions, which happen to have two different syn-

taxes:

>> 3 > 2? 1 : 0

1

>> 3 < 2? 1 : 0

0

The language also supports blocks, again, with two different syntaxes:

>> (1+2; 2*3; 3/4)

0.

MetaJulia supports theletform, with lexical scope:

Theletform also allows function definitions:

MetaJulia also supports assignments, which implicitly creates definitions if necessary:

MetaJulia also deals with higher-order functions:

Obviously, it also supports anonymous functions:

Special care must be taken to support the following semantics, which illustrates the use of the

globalkeyword to create (or update) binding on the global scope:

Logical operators have the typical short-circuit evaluation semantics:

So far, MetaJulia is a strict subset of Julia. What makes MetaJulia different from Julia (and

from most other languages) is its different take on reflection and metaprogramming.

2.1 Reflection

Theevalfunction is usually considered an important feature in languages that have reflective

capabilities. This function takes an expression as argument and computes its value. This means

that the use ofevalrequires the ability to reify the expression that will be evaluated.

Like Julia, MetaJulia has native support for reifying expressions. That is achieved using the

quote form and its support for interpolation, as demonstrated in the following examples:

Regarding the implementation ofeval, it is important to note that it is difficult to support

evalin lexically scoped languages, as the evaluation of an expression typicaly depends on free

variables that are not accessible from the scope whereevalis being used. There are different ways

to solve this problem: one is to restrictevalso that it can only use the global scope, as this scope

is always accessible, and another is to also reify scopes, so that we can explicitly provide theeval

function with the scope where a given expression should be evaluated.

MetaJulia does not use any of these approaches. Instead, MetaJulia only makesevalaccessible

inside a fexpr. A fexpr is a function that does not evaluate its arguments, meaning that, when

called, the function receives the actual expressions that were provided as arguments. In MetaJulia,

a fexpr is defined just like a normal function but using the:=operator instead of the=operator

used to define functions. Here is an example that compares a function with a fexpr :

As can be seen in the final expression, instead of receiving the value of the expression1 + 2as

argument,identity_fexprreceived the actual expression1 + 2as argument and then returned

it.

Just like it happens in languages that supporteval, when a fexpr wants to evaluate an expres-

sion, it can use theevalfunction, which is lexically bound inside the fexpr. This behavior can be

seen in the following interaction:

Note an important detail in the use ofevalby a fexpr : its argument is evaluated in the scope

of the call to the fexpr and not in the scope where the fexpr was defined nor in the scope of the

body of the fexpr itself. Here is an example that demonstrates this:

For a more extreme example, consider the following:

Historically, the fexpr idea became popular because it allowed programmers to extend the

programming language with new control structures that were harder to achieve using functions.

For example:

For a more sophisticated example, consider:

Using fexprs andevalallows us to access local scopes without requiring their reification, as

demonstrated by the following example:

Despite all their expressiveness, fexprs made compilation very difficult and they ended up being

replaced by macros , a metaprogramming-based approach that, despite being harder to master,

allowed compilers to generate very efficient code.

2.2 Metaprogramming

MetaJulia also supports metaprogramming through the use of macros. Differently from Julia, these

macros are not defined using Julia’smacroform and they are not called using Julia’s@syntax.

Instead, they look like functions but are defined using the$=operator. Here is an example:

As an example of use, consider the following definition of theabsfunction written in an im-

perative style, usingwhenand assignment:

As macros can replace most of the uses of fexprs andeval, it is not surprising to verify that

they can implementrepeat_until:

It is important to note that the previous macro definition is not entirely correct, as is visible

in the following example:

This strange behavior is the result of a name conflict involving thelooplocal variable in

the above expression, and thelooplocal function that results from the macro expansion, which

shadows the previous variable. To fix the problem, we need to use thegensymfunction, which

generates a symbol that is unique, in the sense that it does not clash with any other symbol:

2.3 Extensions

You can extend your project to further increase your final grade. Note that this increase will not

exceed two points.

Examples of interesting extensions include:

Be careful when implementing extensions, so that the extra functionality does not compromise

the functionality asked in the previous sections.

3 Code

Your implementation must work in Julia 1.10 but you can also use more recent versions.

The written code should have the best possible style, should allow easy reading, and should

not require excessive comments. It is always preferable to have clearer code with few comments

than obscure code with lots of comments.

The code should be modular, divided into functionalities with specific and reduced responsibil-

ities. Each module should have a short comment describing its purpose.

4 Presentation

For this project, a full report is not required. Instead, a presentation is required. This presentation

should be prepared for a 10-minute slot, should be centered on the architectural decisions taken,

and may include all the details that you consider relevant. You should be able to “sell” your

solution to your colleagues and teachers.

Note that the presentation needs to be recorded and the recording must be submitted along

with the presentation slides.

5 Format

Each project must be submitted by electronic means using the Fénix Portal. Each student must

submit a single compressed file in ZIP format, namedproject.zip. Decompressing this ZIP file

must generate a folder containing:

The only accepted format for the presentation slides is PDF. This PDF file must be named

presentation.pdf. The only accepted format for the recording of the presentation is MPEG-4.

This MPEG-4 file must be namedrecording.mp4.

6 Evaluation

The evaluation criteria include:

In case of doubt, the teacher might request explanations about the inner workings of the

developed project, including demonstrations.

7 Plagiarism

It is considered plagiarism the use of any fragments of programs that were not provided by the

teachers. It is not considered plagiarism the use of ideas given by colleagues (or ChatGPT) as long

as the proper attribution is provided.

This course has very strict rules regarding plagiarism. Any project where plagiarism is detected

will receive a grade of zero.

These rules should not prevent the healthy exchange of ideas between colleagues.

8 Final Notes

Don’t forget Murphy’s Law.

9 Deadlines

The code must be submitted via Fénix, no later than 23:00 of March , 27. Similarly, the presen-

tation must be submitted via Fénix, no later than 23:00 of March , 27.