CJEU landmark rulings on “credit ranking” and review of DPAs The CJEU issued two judgments with far-reaching consequences for the credit ranking business and judicial review of DPAs

When I was 10, I came out as transgender. I was a girl and I knew it.

I was one of the lucky ones.

After four painful years, I was fortunate enough to access gender-affirming health care. First testosterone blockers. Later estrogen, the stuff my peers soaked in for years while I threw myself into software development to distract from pain.

Despite being old enough to go through the wrong puberty and suffer its permanent changes, it took four years to access the medical fix. Four years of gender therapy, hard talks with doctors, and a lot of determination.

There’s a vicious myth that kids just walk into clinics and leave with hormones. Quite the opposite.

I was lucky: my parents supported me, and by then we lived near San Francisco, where a gender clinic was willing to take me as patient.

I’m 21 now. I’ll be blunt: if not for gender-affirming care, I don’t know if I would be around. If there would be FOSS graphics drivers for Mali-T860 or the Apple M1.

If I were a few years younger, lived in the wrong part of the US, that may well be the reality, because gender-affirming care is banned for minors in conservative areas across the United States. Texas, for example, would threaten to take me from my loving parents under Greg Abbott’s directive.

Even now, I’m lucky I don’t live in the wrong place: the medication I’m prescribed is banned for adults in several American states.

I fear the 2024 election. How long until there’s a ban nationwide?

In high school, I knew this day might come. I applied to Canadian universities. Canada isn’t perfect, far from it. But stripping trans rights isn’t on the ballot yet.

Growing up, we liked visiting Florida.

Now there are travel advisories against it.

One recent Florida law threatens jail time if a trans person uses the bathroom - any bathroom - in a public space. I remember in high school, arguing back against “bathroom bills” designed to marginalize trans people. They seem tame next to the vile attacks on trans people championed by Ron DeSantis.

What’s next?

Does anybody remember the Nuremberg laws?

I was raised Jewish. Growing up, we were haunted by the spectre of the Holocaust. I knew queer Germans were in the cross-hairs alongside Jews. I didn’t know that Berlin was a queer centre before Hitler came to power.

In high school, I understood if fascists came to power in the United States, I might be first to go. Nazis had a special symbol for people like me: a pink triangle superimposed on a yellow triangle. I was 16 when I wondered if one day I would be forced to wear it.

In 2020, Donald Trump used the Nazi’s symbol for political prisoners – forced to be worn in camps – to threaten leftists in a campaign ad.

Subtle.

You don’t need to like Democrats, but I need you to understand that if you vote Republican in 2024, you vote erasure. You vote oppression. You vote fascism.

Maybe you “just have some concerns” about trans kids.

I was a trans kid, and I want you to know that DeSantis, Abbott, and Trump were my nightmares. Their policies will lead to the deaths of transgender Americans. With hundreds of GOP-sponsored anti-trans bills and laws simultaneously sweeping the United States, it’s hard to believe this isn’t by design.

It doesn’t have to be that way.

The trans experience isn’t inherently defined by suffering. Not for trans kids, not for trans adults.

When treated with respect, allowed to transition, when we can access the medication we know we need, life can be great.

Personally, I have felt virtually no gender-related discomfort in years now.

I once recoiled at my reflection. Now I look in the mirror and smile at the cute woman smiling back at me. I’m surrounded by lovely friends, and we support each other. Laugh together. Cry together. Text endless stickers of cartoon sharks together. Past the shared struggle, there is immense trans joy.

When we are made to suffer – by banning our medication, arresting us for peeing, legislating our identities out of existence on the road to establishing a theocratic state – that is a policy choice.

We’re not asking for much. We don’t want special treatment. We just want respect. Life, liberty, and the pursuit of happiness.

Right now I want legislators to get the fuck out of our doctors’ office.

I’m on the board overseeing Linux graphics. Half of us are trans. If all you care about is Linux, resist the attacks on trans people.

If you have any decency, fight back.

It’s your choice.

---

Selected reading:

• May Anti-Trans Legislative Risk Map

• Why It Took Decades for LGBTQ Stories to Be Included in Holocaust History

• Facebook takes down another Trump campaign ad, this time for Nazi imagery

• NAACP Issues Travel Advisory in Florida

• Texas begins investigating parents of transgender teens for child abuse, according to a lawsuit. One parent works in the department involved in the investigations

---

I’m pleased to announce the availability of the latest release of SIMD Everywhere (SIMDe), version 0.7.6, representing more than two years of work by over 30 developers since version 0.7.2. (I also released 0.7.4 two weeks ago, but it needed a few more fixes; thanks go to the early adopters who helped me out.)

SIMDe is a permissively-licensed (MIT) header-only library which provides fast, portable implementations of SIMD intrinsics for platforms which aren’t natively supported by the API in question.

For example, with SIMDe you can use SSE, SSE2, SSE3, SSE4.1 and 4.2, AVX, AVX2, and many AVX-512 intrinsics on ARM, POWER, WebAssembly, or almost any platform with a C compiler. That includes, of course, x86 CPUs which don’t support the ISA extension in question (e.g., calling AVX-512F functions on a CPU which doesn’t natively support them).

If the target natively supports the SIMD extension in question there is no performance penalty for using SIMDe. Otherwise, accelerated implementations, such as NEON on ARM, AltiVec on POWER, WASM SIMD on WebAssembly, etc., are used when available to provide good performance.

SIMDe has already been used to port several packages to additional architectures through either upstream support or distribution packages, particularly on Debian.

What’s new in 0.7.4 / 0.7.6

• 40 new ARM NEON families implemented
• Initial support for ARM SVE API implementation (14 families)
• Complete support for x86 F16C API
• Initial support for MIPS MSA API
• Nearly complete support for WASM SIMD128 C/C++ API
• Initial support for the E2K (Elbrus) architecture
• Initial support for LoongArch LASX/LSX and optimized implementations of some SSE intrinsics
• MSVC has many fixes, now compiled in CI using /ARCH:AVX, /ARCH:AVX2, and /ARCH:AVX512
• Minimum meson version is now 0.54

As always, we have an extensive test suite to verify our implementations.

For a complete list of changes, check out the 0.7.4 and 0.7.6 release notes.

Below are some additional highlights:

X86

There are a total of 7470 SIMD functions on x86, 2971 (39.77%) of which have been implemented in SIMDe so far. Specifically for AVX-512, of the 5270 functions currently in AVX-512, SIMDe implements 1439 (27.31%)

Completely supported functions families

• MMX
• SSE
• SSE2
• SSE3
• SSSE3
• SSE4.1
• AVX
• AVX2
• F16C
• FMA
• GFNI
• CLMUL
• XOP
• SVML

Newly added function families

• AVX512CD: 21 of 42 (50.00%)
• AVX512VPOPCNTDQ: 18 of 18 💯%!
• AVX512_4VNNIW: 6 of 6 💯%!
• AVX512_BF16: 9 of 38 (23.68%)
• AVX512_BITALG: 24 of 24 💯%!
• AVX512_FP16: 2 of 1105 (0.18%)
• AVX512_VBMI2 3 of 150 (2.00%)
• AVX512_VNNI: 36 of 36 💯%!
• AVX_VNNI: 8 of 16 (50.00%)

Additions to existing families

• AVX512F: 579 additional, 856 total of 2660 (31.80%)
• AVX512BW: 178 additional, 335 total of 828 (40.46%)
• AVX512DQ: 77 additional, 111 total of 399 (27.82%)
• AVX512_VBMI: 9 additional, 30 total of 30 💯%!
• KNCNI: 113 additional, 114 total of 595 (19.16%)
• VPCLMULQDQ: 1 additional, 2 total of 2 💯%!

Neon

SIMDe currently implements 56.46% of the ARM NEON functions (3766 out of 6670). If you don’t count 16-bit floats and poly types, it’s 75.95% (3766 / 4969).

Newly added families

• addhn
• bcax
• cage
• cmla
• cmla_rot90
• cmla_rot180
• cmla_rot270
• cvtn
• fma
• fma_lane
• fma_n
• ld2
• ld4_lane
• mla_lane
• mlal_high_n
• mlal_lane
• mls_n
• mlsl_high_n
• mlsl_lane
• mull_lane
• qdmulh_lane
• qdmulh_n
• qrdmulh_lane
• qrshrn_n
• qrshrun_n
• qshlu_n
• qshrn_n
• qshrun_n
• recpe
• recps
• rshrn_n
• rsqrte
• rsqrts
• shll_n
• shrn_n
• sqadd
• sri_n
• st2
• st2_lane
• st3_lane
• st4_lane
• subhn
• subl_high
• xar

MSA

Overall, SIMDe implementents 40 of 533 (7.50%) functions from MSA.

What is coming next

Work on SIMDe is proceeding rapidly, but there are a lot of functions to implement… x86 alone has about 8,000 SIMD functions, and we’ve implemented about 3,000 of them. We will keep adding more functions and improving the implementations we already have.

If you’re interested in using SIMDe but need some specific functions to be implemented first, please file an issue and we may be able to prioritize those functions.

Getting Involved

If you’re interested in helping out please get in touch. We have a chat room on Matrix/Element which is fairly active if you have questions, or of course you can just dive right in on the issue tracker.

Standardizing computational reuse and portability with the Common Workflow Language.

2020 is not a year any of us will forget. The coronavirus pandemic has brought unprecedented changes to our daily lives. Sadly, many people have endured the loss of loved ones because of the pandemic. Some people suffering discrimination and persecution - including LGBT people - have felt this intensify as a result of changes in society brought about by the pandemic. In many ways, a concern for and a need to protect human rights has never felt more urgent. 

On the ECHR Sexual Orientation Blog I have tried, as always, to provide a factual and critical account of cases in the European Court of Human Rights (and wider developments in the Council of Europe) concerning sexual orientation discrimination. As usual, I have tried to provide readers with an insight into the facts of cases, a discussion of how the Court has approached them, as well as giving my own "point of view".

Below is an overview of much of the activity on the blog this year.

I want to thank everyone who stops by here from time to time to read about the Court and its cases. I have been writing this blog for 7 years now, and over that time I have made lots of new friends because of the blog - people who have contacted me via email, or on Twitter (@echrso) - and I really value that. Thank you for engaging with the material here!

I wish you all a very happy Christmas, in these difficult days, and a happy new year, in which I hope we all have brighter days. 

2020: A Year in Review

Decisions and judgments of the European Court of Human Rights

The Court issued a number of important decisions and judgments relating to sexual orientation discrimination throughout 2020...

In January, the Court issued its judgment in the case of Beizaras and Levickas v Lithuania, holding unanimously that there had been a violation of the Convention in respect of the State’s failure to protect individuals from homophobic hate speech. The judgment is important because it explicitly addresses "hateful comments", including undisguised calls for violence, made by private individuals against the gay community via social media. 

Also in January, the Court issued its judgment in Alekseyev and Others v Russia which concerned 77 applications made to the Court between November 2015 and June 2018 that primarily related to the ban, imposed by Russian authorities, on holding LGBT public assemblies. The Court found violations, but declared applications by Nikolay Alekseyev inadmissible as an abuse of the right of individual application (which I wrote about, in connection with an earlier case, here).

In June, the Court published its decision in the case of Carl Jóhann Lilliendahl v Iceland, in which it unanimously declared the application, by a 74-year-old man concerning a conviction in Iceland for anti-gay expression, inadmissible. The most striking aspect of the Court's decision was the clarification it contained regarding its approach to considering the expression of "hatred" against people on the grounds of sexual orientation. 

In October, the Court issued its judgment in the case of Aghdgomelashvili and Japaridze v Georgia. The case concerned discriminatory ill‑treatment by the police on the grounds of sexual orientation and gender identity, and the absence of an effective domestic investigation of this ill-treatment. The violations found by the Court make an important contribution to its evolving jurisprudence on the interplay between Article 3 and Article 14 of the Convention in respect of acts of hatred (both physical and speech acts) against LGBT people.

In November, the Court issued its judgment in Sozayev and Others v Russia. The case concerned the arrest and conviction of five applicants, in 2013, after they participated in a public assembly in front of the State Duma in Moscow in response to the legislative ban on the "promotion of non-traditional sexual relations among minors". In finding violations of the Convention the judgment addressed restrictions on the right to freedom of peaceful assembly generally, and the right to peacefully assemble to object to homophobic and transphobic laws.

Also in November, the Court issued its judgment in B and C v Switzerland, which concerned the case of a gay man (in a same-sex relationship) challenging his deportation to a country (The Gambia) where he would be at risk of ill-treatment because of his sexual orientation. For the first time in its history, the Court held that returning an applicant to a non-European state where they would be at risk of ill-treatment on the grounds of their sexual orientation amounted to a violation of Article 3 (prohibition of torture) of the Convention. 

And again in November, the Court issued its judgment in Honner v France in which it held that the refusal to award contact rights to the applicant in respect of the child which had been born to her former partner in Belgium using assisted reproductive techniques, while the two women were a couple, did not violate the Convention. 

In December, the Court issued its judgment in Berkman v Russia. The case concerned the failure of police officers to ensure that an LGBTI event disrupted by counter-demonstrators proceeded peacefully, and the unlawful arrest of the applicant at the event. Finding violations of the Convention, the judgment was a further reiteration of the Court's now established principle that domestic authorities are under a positive obligation to ensure that LGBT+ people can exercise their right to freedom of peaceful assembly in circumstances free from homophobic hatred. 

Communicated cases

The Court communicated a range of new cases concerning sexual orientation discrimination throughout 2020, many of which I wrote about on the blog. I detailed...

Cases against Russia concerning employment discrimination, failure of the police to investigate violent hate crime, the deportation of a gay man to a country where he would be at risk, and "homosexual propaganda" laws.

A case against the United Kingdom concerning refusal to supply a gay man with a commercial service. 

A case against Romania brought by eight same-sex couples concerning the lack of legal recognition of their relationships.

Cases against Lithuania concerning anti-gay hate speech, and restrictions placed on a book for children.

Seven new cases against Poland concerning different aspects of sexual orientation discrimination. 

A case against France concerning access to a child.

A case against Greece, brought by 162 same-sex couples, concerning lack of relationship recognition. 

And a case against Croatia concerning lack of access to a fair trial in respect of an allegation of sexual orientation discrimination.

Anniversaries

There were a number of anniversaries this year connected to the Convention, and to sexual orientation discrimination, that I wrote about...

In January, the UK celebrated the 20th anniversary of the ban on gay people serving in the armed forces being lifted. The ban came to an end on 12th January 2000 and this was the direct result of judgments by the Court in 1999. 

In November, the Convention had its 70th birthday.

Also in November, the UK celebrated the 20th anniversary of the legislation that brought about an equal "age of consent", which was significantly encouraged by litigation under the Convention. I summarised the legal history in a piece for Openly (which can be heard as a short podcast).  

December brought the 65th anniversary of the very first case brought under the Convention concerning sexual orientation discrimination. 

Other entries on the blog

In January, I wrote a piece about UK universities, freedom of speech, and trans issues. 

In June, I detailed an article that I wrote in the European Human Rights Law Review about "gender critical" beliefs.

In September, I wrote a piece about why LGBT people in the UK should prepare to defend their human rights, and this was discussed by Naomi Wolf.

In October, I made available an updated chapter that aims to provide a comprehensive but condensed assessment of the historical development and current state of human rights protection offered to LGBT people by the Council of Europe and, importantly, identify the gaps that currently exist in that protection. 

Also in October, I made available a draft of a new research article, written with Silvia Falcetta, which examines faith-based objections to the inclusion of LGBT content in "relationships education" in primary schools in England.

Blog readership

In the last year, the blog has been visited 51,500 times:

Previously: Rewriting the Technical Interview.

Aisha’s hands rattle you. They float gently in front of her shoulders, wrists cocked back. One sways cheerfully as she banters with the hiring manager—her lacquered nails a cyan mosaic over ochre palms. They flit, then hover momentarily as the two women arrange lunch. When the door closes, Aisha slaps her fingertips eagerly on the pine-veneer tabletop. Where have you seen them before?

But she is giggling and glad to finally meet you, and her hair bounces in loose ringlets around the shoulders of her yellow sundress, and you like her, this thirty-something engineer who has worked here three years (even if you don’t understand what it is, exactly, that she does for Mineral Analytics, Limited), who heard you were on the market, and just had to interview you personally. She tells you about the yogurt bar, and the yoga studio, and how important work-life balance is to the company. Then she asks you to balance a binary tree.

Even after all these centuries, you still have trouble grafting limbs. “I’m sorry, you’ll have to give me a moment,” you stall. “I can never keep the transformation rules straight.”

Plead with the demigoddess Andréka to intercede on your behalf.

vidrun@bamse ~> swipl

Aisha smirks. You suspect she knows something.

“Remind me, Aisha—we need to make sure that both branches have the same height? Or differ by just one?”

“At every level.” She folds her arms and offers you a break. “Would you like me to get us started?”

Release the cryptographic wards on two of your xterms, and slide the machine over.

eval_prim(Exp, _, Exp) :- Exp = nil ; Exp = [] ; number(Exp).

“We’ll start with terminals. Nils, empty lists, and numbers—that should be a good start, don’t you think?”

This seems reasonable enough.

“And you know we’re gonna need equality constraints. Addition too, for tree heights.”

:- use_module(library(reif)). eval_prim([eq, A, B], Env, R) :- eval_exp(A, Env, ARes), eval_exp(B, Env, BRes), if_((ARes = BRes), R = true, R = nil). eval_prim([plus, A, B], Env, R) :- eval_exp(A, Env, AR), eval_exp(B, Env, BR), R is AR + BR. eval_exp(Exp, Env, R) :- eval_prim(Exp, Env, R), !.

Clock! She pops her tongue at the cut, startling you. Consider asking about Env, but decide against it: she clearly knows where she’s going.

Aisha gives you a very knowing look over the top of her glasses, then summons a list from the void.

eval_prim([first, List], Env, R) :- eval_exp(List, Env, ListR), if_(([] = ListR), R = nil, [R|_] = ListR). eval_prim([rest, List], Env, R) :- eval_exp(List, Env, ListR), ((ListR = [], R = nil) ; (ListR = [_|R])). eval_prim([cons, Head, Tail], Env, R) :- eval_exp(Head, Env, HeadR), eval_exp(Tail, Env, TailR), if_((nil = TailR), TailL = [], TailL = TailR), R = [HeadR | TailL].

Without moving anything else, raise a single eyebrow two centimeters.

“I’ve read your work! You couldn’t walk into a bodega without conjuring a shopping list from thin air.”

She has read you, hasn’t she?

?- eval_exp([cons, 2, [cons, 1, nil]], {}, R). R = [2, 1].

You’re ready to take it from here, but Aisha continues, nails clacking against the keycaps.

eval_each([], _, []). eval_each([X | More], Env, [XR | MoreR]) :- eval_exp(X, Env, XR), eval_each(More, Env, MoreR).

“Aisha, I–”

Her hands flash and flourish, slapping out a polyrhythm you remember.

type(X, R) :- (atom(X), R = atom) ; (number(X), R = number) ; ([] = X , R = list) ; (functor(X, '[|]', _), R = list), ! ; (compound_name_arity(X, λ, _), R = function), ! ; (compound_name_arity(X, ⴷ, _), R = macro), ! ; (compound_name_arity(X, Type, _), R = Type). eval_prim([type, X], Env, R) :- eval_exp(X, Env, XR), type(XR, R).

Fy Faen! You see it now!

Snap your fingers, recalling your laptop to your hands. The instrument flies from her grasp, and you are already on your feet, anchoring yourself to the ethernet, Aisha standing in one fluid swooping motion as you cross-step back for space, one hand outstretched to seize—

—thin air.

Your laptop hovers in the air between you, screen blushing rose to iris. Aisha, yawning, checks her nails. Faint bangles of non-printable control characters encircle her wrist in glowing rings, impossible to see directly.

“Oh honey.” Her voice acquires a familiar, husky resonance.

You know her you know her you know–

She sighs in exasperation. “You’re old, not senile!”

Remember 1921: the salt-wind scoring your forehead as the bow of the Kovno cut through the cold Atlantic night. The icy pit of the Gardnos Stone, wrapped in burlap, weighing your bag as if seeking to drown the whole ship. It refused flight, warmth, comprehension. The coven had sent you in search of answers: to Antwerp, to Victorieplaats—all masonry and copper, gold figures gleaming atop the mercantile houses of the bustling diamond-hive.

You’d sought a specialist. You found Aligaz.

A eager scion of the Semien stone-mages, cast from rocky fingertips at a time of cosmopolitan awakenings, he had set up shop in an alley just south of the plaza. Géomancien, Aligaz had explained, giggling at the word, and gestured to the glittering shelves: crystals and milky stones in every color, charged by the steady glow of gaslight. All swish and charm, he had whisked the Stone from your bag and informed you, in lilting French, that you needed to lighten up. “Ces suédois!” You’d bristled at the insult… but he had, in the end, been right.

You had traded spells and languages, huddled under the rain-roaring copper roof of Aligaz’s attic. Worked together to uncover the mystery of Gardnos, and one another. Aligaz, endlessly inventive, had outmatched you at every turn: constructing puzzles within puzzles, locks which everted, became their own keys. He had wondered at your tales of the fjords, and you, in turn, had planned to travel south with him, to see the Ethiopian landscapes he so lovingly recalled—but the coven recalled you to Skjækra. That he could stand before you now, after so many years…

“… Aisha?” You ask, tentative.

“After my aunt.” She smiles fondly.

“What a beautiful name!” It suits her well. “When did—”

“Harlem. After the war.” And here she trails off; lost, perhaps, in her own private recollection.

You are happy for Aisha, of course. To claim one’s true self is the right of all people, and the most powerful of all magics. But you have so many questions!

“What became of the Stone? How did you know? What are you doing here, of all places?”

“Vidrun, this is a geological surveying company. Of course I’m here. The question is why are you applying?”

You pause for a moment.

Why are you here?

“You summoned me!”

“I didn’t know for sure,” she admits. “But rumors spread, and your style is distinctive. How could I pass over the chance to challenge you once more?”

Now the meaning of her spell becomes clear: a trap laid not to ensnare, but to evince. She has offered you a gift. Return the laptop to her, and accept the invitation with grace.

bind(K, V, Env, Env2) :- atom(K), Env2 = Env.put(K, V).

“I bind you, Vidrun,” she intones. Her voice now carries the weight of the Semien, of the Alps, of the Sierra Nevada. A century has grounded her.

“I bind you head and tail.”

bind([], _, Env, Env). bind([K|Ks], Vs, Env, Env3) :- (K = &(K2), bind(K2, Vs, Env, Env3), !) ; ([] = Vs, bind(K, nil, Env, Env2), bind(Ks, [], Env2, Env3)); ([V1|V1s] = Vs, bind(K, V1, Env, Env2), bind(Ks, V1s, Env2, Env3)).

Your breath catches in your throat.

“You shall see only that which is shown,” she continues.

eval_var(Var, Env, R) :- atom(Var), get_dict(Var, Env, R).

“You may speak without speaking,”

eval_prim([quote, R], _, R).

“And within these bounds, you may choose your own path.”

eval_prim([cond], _Env, nil). eval_prim([cond, Default], Env, R) :- eval_exp(Default, Env, R). eval_prim([cond, Test, Branch | More], Env, R) :- eval_exp(Test, Env, TestR), if_((nil = TestR), eval_prim([cond | More], Env, R), eval_exp(Branch, Env, R)).

A Lisp, then. Murmuring softly, you offer a prayer to McCarthy. Hopefully Aisha does not expect you to reinvent lambdas from scratch.

“What you let, will become.”

eval_prim([let, [], Body], Env, R) :- eval_exp(Body, Env, R). eval_prim([let, [K, V | More], Body], Env, R) :- eval_exp(V, Env, VR), bind(K, VR, Env, Env2), eval_prim([let, More, Body], Env2, R).

Well, that’s something, at least. Serial assignment, too—a luxury. But Aisha is not finished. She clacks her heels firmly onto the industrially-sealed concrete, and opens her arms wide. Her palms are ruddy laterite, her upturned eyes glinting magnetite under halogen stars.

evoke(Vars, Args, Body, Env, R) :- bind(Vars, Args, Env, Env2), eval_exp(Body, Env2, R). eval_application([Fun | Args], Env, R) :- eval_exp(Fun, Env, FunR), FunR = λ(Vars, Body, Env2), eval_each(Args, Env, ArgsR), evoke(Vars, ArgsR, Body, Env2, R).

The Church. The lambda calculus. The gay agenda. It has known a thousand names, a thousand forms. Aisha slams her palms together, and with the crash of mountains, summons the thousandth-and-first.

eval_prim([lambda, Args, Body], Env, R) :- R = λ(Args, Body, Env.put(recur, R)).

The conference room twists, folds somehow. Outside, the rows of desks and office furniture rush away to the horizon, replaced by a featureless expanse of evenly-lit pine. On the tabletop, a miniature cube of glass and concrete inflates from nothing to a tiny, modernist dollhouse. You lean over to look inside, notice the light outside the conference room abruptly dim, and think better of it.

eval_exp(Exp, Env, R) :- eval_var(Exp, Env, R), ! ; eval_prim(Exp, Env, R), ! ; eval_application(Exp, Env, R), !.

Aisha takes a deep breath and regains her composure. You sense her spell is near complete.

Whisper softly, so as not to disturb her work. “Macros?”

She glares sidelong, eyes wide. “Really?”

“It’ll be fun.”

eval_prim([gensym, Prefix], _Env, R) :- atom_concat(Prefix, '__auto__', Sym), gensym(Sym, R). eval_prim([macro, Args, Body], Env, R) :- R = ⴷ(Args, Body, Env). eval_application([Fun | Args], Env, R) :- eval_exp(Fun, Env, FunR), ((FunR = λ(Vars, Body, Env2), eval_each(Args, Env, ArgsR), evoke(Vars, ArgsR, Body, Env2, R)) ; (FunR = ⴷ(Vars, Body, Env2), evoke(Vars, Args, Body, Env2, Code), eval_exp(Code, Env, R))).

“One more thing,” you request. “Some kind of product type.”

“Ma'am, this is a Wendy’s.”

“Do you really want to watch me reinvent a dynamic type system on top of bare lists?”

Aisha considers the possibility—somewhat sadistically, you think—but this is not that kind of interview.

“Fine. But that’s ALL you’re getting.”

eval_prim([struct, Type | Fields], Env, R) :- eval_each(Fields, Env, FieldsR), compound_name_arguments(R, Type, FieldsR). eval_prim([destruct, Type, Struct], Env, R) :- eval_exp(Struct, Env, StructR), compound_name_arguments(StructR, Type, R).

Your hair charges with static as Aisha seals the spell. Her nails flare in the light, leaving cyan trails in the air above the keyboard. As she executes the final command, you feel your connection with Andréka severed. You are locked in Aisha’s calculus now.

“I knew exactly where you were going with this, Vidrun. You couldn’t remember how to balance a binary tree, so you thought you’d define the transformational invariants and have Prolog solve them for you.”

“So you’re trapping me in a Lisp instead.”

“Would you have preferred an Algolem?” Aisha smirks. You would not.

Very well. Sprinkle salt, as is tradition, in the protective form of two parentheses. No—you wipe the salt clear—square brackets. Test the forms of this new plane.

?- eval_exp([let, [list, [lambda, [&(args)], args]], [list, 1, 2, 3]], e{}, R). R = [1, 2, 3].

It’s not much, but it’s a start. Aisha watches you expectantly; you need to do something. Stall for time by summoning an algebra.

and, [macro, [a, b], [list, [quote, cond], a, b]], or, [macro, [a, b], [let, [a_, [gensym, a]], [list, [quote, let], [list, a_, a], [cond, a_, a_, b]]]], not, [lambda, [x], [cond, x, nil, [quote, true]]],

Aisha makes a show of yawning. Bore her with type predicates.

is_null, [lambda, [x], [or, [eq, x, []], [eq, x, nil]]], is_list, [lambda, [x], [eq, [type, x], [quote, list]]], is_pair, [lambda, [x], [and, [not, [is_null, x]], [is_list, x]]], is_fn, [lambda, [x], [eq, [type, x], [quote, function]]],

You think you’re getting the hang of this—though you haven’t used your comma key this much in years. It’s all so excitingly verbose.

second, [lambda, [coll], [first, [rest, coll]]], map, [lambda, [f, coll], [cond, [is_null, coll], [], [cons, [f, [first, coll]], [recur, f, [rest, coll]]]]], find, [lambda, [f, coll], [cond, [is_pair, coll], [let, [x, [first, coll]], [cond, [f, x], x, [recur, f, [rest, coll]]]]]], fold, [lambda, [f, init, coll], [cond, [is_null, coll], init, [recur, f, [f, init, [first, coll]], [rest, coll]]]], rev, [lambda, [coll], [fold, [lambda, [list, elem], [cons, elem, list]], [], coll]], [rev, [list, 1,2,3]] R = [3, 2, 1].

Smile, wistfully. That had been a good interview.

syntax_quote_fn, [lambda, [expr], [cond, [is_null, expr], expr, [is_list, expr], [let, [f, [first, expr]], [cond, [eq, f, [quote, unquote]], [second, expr], [cons, [quote, list], [map, recur, expr]]]], [list, [quote, quote], expr]]], syntax_quote, [macro, [expr], [syntax_quote_fn, expr]],

“Honestly!” Aisha mutters. “I don’t know what you wanted macros for in the first place. Is this really necessary for balancing a tree?”

Keep your expression as enigmatic as possible. She may have cut you off from the Goddess Andréka, but you can will your own deities into existence.

lvar, [lambda, [num], [struct, lvar, num]], is_lvar, [lambda, [x], [eq, [quote, lvar], [type, x]]], lvar_num, [lambda, [x], [first, [destruct, foo, x]]],

Aisha’s jaw drops as she grasps your scheme. “You have got to be kidding.”

“Kiselyov, Friedman, Byrd”, you incant. “I call upon you, triune, though you have never dwelt within these forms. May you walk this plane as well!”

walk, [lambda, [u, subs], [let, [pr, [and, [is_lvar, u], [find, [lambda, [v], [eq, u, [first, v]]], subs]]], [cond, pr, [recur, [rest, pr], subs], u]]],

“May all merge within your reasoned embrace!”

ext_s, [lambda, [x, v, subs], [cons, [cons, x, v], subs]], unify, [lambda, [u, v, subs], [let, [u, [walk, u, subs], v, [walk, v, subs]], [cond, [eq, u, v], subs, [is_lvar, u], [ext_s, u, v, subs], [is_lvar, v], [ext_s, v, u, subs], [and, [is_pair, u], [is_pair, v]], [let, [subs, [recur, [first, u], [first, v], subs]], [and, subs, [recur, [rest, u], [rest, v], subs]]]]]],

Aisha locks eyes with you. Inside each of you, something shifts, merges, becomes bound.

mzero, [],

“M'Zero,” she quips, and you share a giggle.

“Absolute unit,” you respond.

unit, [lambda, [state], [cons, state, mzero]],

Demand equality. Some would call this a constraint, but you know it to be foundational.

eql, [lambda, [u, v], [lambda, [st], [let, [subs, [unify, u, v, [first, st]]], [cond, subs, [unit, [cons, subs, [rest, st]]], mzero]]]],

“May this space be open to newcomers,” you declare.

call_fresh, [lambda, [f], [lambda, [st], [let, [c, [rest, st]], [[f, [lvar, c]], [cons, [first, st], [plus, 1, c]]]]]],

“And may their futures weave a beautiful tapestry.” You forsee threads of execution racing ahead, taking turns, alternating and combining.

mplus, [lambda, [a, b], [let, [mplus, recur], [cond, [is_null, a], b, [is_fn, a], [lambda, [], [mplus, b, [a]]], [cons, [first, a], [mplus, [rest, a], b]]]]], bind, [lambda, [stream, goal], [let, [bind, recur], [cond, [is_null, stream], mzero, [is_fn, stream], [lambda, [], [bind, [stream], goal]], [mplus, [goal, [first, stream]], [bind, [rest, stream], goal]]]]],

Imbue the triune with its own algebra.

disj, [lambda, [g1, g2], [lambda, [state], [mplus, [g1, state], [g2, state]]]], conj, [lambda, [g1, g2], [lambda, [state], [bind, [g1, state], g2]]]

Moving carefully, you follow a thread of that tapestry to its first few knots.

pull, [lambda, [stream], [cond, [is_fn, stream], [recur, [stream]], stream]], take, [lambda, [n, stream], [cond, [eq, 0, n], [], [let, [stream, [pull, stream], state, [first, stream]], [cond, state, [cons, state, [recur, [plus, n, -1], [rest, stream]]], []]]]], run_raw, [lambda, [n, goal], [take, n, [goal, [cons, [], 0]]]],

The work complete, you let go a sigh. Your godhead takes its first tottering steps.

?- eval([run_raw, 3, [call_fresh, [lambda, [x], [disj, [eql, x, [quote, aisha]], [eql, x, [quote, vidrun]]]]]], R = [[[[lvar(0)|aisha]]|1], [[[lvar(0)|vidrun]]|1]].

“You absolute madwoman,” Aisha chortles. “You can’t remember how to balance a binary tree, but you memorized µKanren?”

“It comes in handy!” You stammer. “And honestly, it’s shorter.” Offer her a reifier by way of apology.

“Fine. Fine!” Aisha throws up her hands in mock exasperation. “I’ve let you get away with it this far!”

walkr, [lambda, [v, subs], [let, [v, [walk, v, subs], walkr, recur, w, [lambda, [v2], [walkr, v2, subs]]], [cond, [is_lvar, v], v, [is_pair, v], [cons, [w, [first, v]], [w, [rest, v]]], v]]], reify, [lambda, [states], [map, [lambda, [state], [walkr, [lvar, 0], [first, state]]], states]]

“Only with respect to the first variable,” you explain. “But it still makes things easier to read.”

eval([reify, [run_raw, 3, [call_fresh, [lambda, [x], [disj, [eql, x, [quote, aisha]], [eql, x, [quote, vidrun]]]]]]], R). R = [aisha, vidrun].

Aisha has the look of a woman who has realized, six hours into her shift, that she has left the oven on. “That’s why you wanted macros. You wanted syntax for this rickety-ass interpreter.”

Reward her insight by entering the metatrance of creation, and let the forms spill from your fingertips.

zzz, [macro, [g], [let, [state_, [gensym, state]], [syntax_quote, [lambda, [[unquote, state_]], [lambda, [], [[unquote, g], [unquote, state_]]]]]]], conjall, [macro, [&(gs)], [let, [[g, &(gs)], [rev, gs]], [fold, [lambda, [form, goal], [syntax_quote, [conj, [zzz, [unquote, goal]], [unquote, form]]]], [list, [quote, zzz], g], gs]]], disjall, [macro, [&(gs)], [let, [[g, &(gs)], [rev, gs]], [fold, [lambda, [form, goal], [syntax_quote, [disj, [zzz, [unquote, goal]], [unquote, form]]]], g, gs]]], conde, [macro, [&(clauses)], [cons, [quote, disjall], [map, [lambda, [goals], [cons, [quote, conjall], goals]], clauses]]], fresh, [macro, [vars, &(goals)], [fold, [lambda, [form, var], [syntax_quote, [call_fresh, [lambda, [[unquote, var]], [unquote, form]]]]], [cons, [quote, conjall], goals], [rev, vars]]], run, [macro, [n, vars, &(goals)], [syntax_quote, [reify, [run_raw, [unquote, n], [unquote, [cons, [quote, fresh], [cons, vars, goals]]]]]]]

Crack your knuckles, and enjoy the series of pops which fizzle from somewhere under your keyboard. “Would you like to do the honors?”

Aisha, half-amused, half exasperated, draws a shining hair from her scalp. Fingers deft, she ties a knot in it for zero.

succ, [lambda, [n], [cons, [quote, 'S'], n]], n0, [list, 0], succo, [lambda, [n, next], [eql, [succ, n], next]],

You draw one of your own, and align them, side by side.

lesso, [lambda, [lesser, greater], [let, [lesso, recur], [fresh, [g], [succo, g, greater], [conde, [[eql, lesser, g]], [[lesso, lesser, g]]]]]], maxo, [lambda, [a, b, max], [conde, [[eql, a, b], [eql, max, a]], [[lesso, a, b], [eql, max, b]], [[lesso, b, a], [eql, max, a]]]], approxo, [lambda, [a, b], [conde, [[eql, a, b]], [[succo, a, b]], [[succo, b, a]]]],

Aisha reaches into her purse, and withdraws a single gleaming seed. This she sets gently upon the table, and waits for you to draw it to fruition.

leaf, [lambda, [x], [list, [quote, leaf], x]], branch, [lambda, [left, right], [list, [quote, branch], left, right]],

A maple tree in miniature, no more than 4 inches high, rises from the tabletop. Outside, in the vast expanse of tabletop, its twin—writ large—swells to full size.

Aisha recognizes the form you have chosen, and raises a spell of translation around it.

tree, [lambda, [t], [cond, [is_list, t], [let, [[left, right], t], [branch, [recur, left], [recur, right]]], [leaf, t]]], untree, [lambda, [[type, a, b]], [cond, [eq, type, [quote, branch]], [list, [recur, a], [recur, b]], [eq, type, [quote, leaf]], a]],

With a flick of your hands, the tree shimmers, reforms.

[tree, [quote, [1, [2, 3]]]] R = [branch, [leaf, 1], [branch, [leaf, 2], [leaf, 3]]].

You measure along each leaf, each branch, and find the height thereof.

heighto, [lambda, [t, h], [let, [heighto, recur], [conde, [[fresh, [x], [eql, t, [leaf, x]], [eql, h, n0]]], [[fresh, [left, right, left_height, right_height, max_height], [eql, t, [branch, left, right]], [heighto, left, left_height], [heighto, right, right_height], [maxo, left_height, right_height, max_height], [succo, max_height, h]]]]]],

Pause a moment, and look to Aisha. A balanced tree: each branch of roughly the same height. Each branch, in turn, a balanced tree itself. Speaking slowly, then faster, in unison, recite:

balancedo, [lambda, [t, h], [let, [balancedo, recur], [conde, [[fresh, [x], [eql, t, [leaf, x]]]], [[fresh, [left, right, left_height, right_height], [eql, t, [branch, left, right]], [balancedo, left], [balancedo, right], [heighto, left, left_height], [heighto, right, right_height], [approxo, left_height, right_height]]]]]],

With all the delicacy you can muster, you peel boughs from trunks, rearrange, then press the limbs gently together. Aisha leans in and blows; the warmth of her breath speeding the healing process.

rot_lefto, [lambda, [t1, t2], [fresh, [a, b, c], [eql, t1, [branch, a, [branch, b, c]]], [eql, t2, [branch, [branch, a, b], c]]]],

Aisha folds her hands together, whispers an incantation, and unfolds them. The maple peels apart into mirrored copies.

rot_botho, [lambda, [t1, t2], [conde, [[rot_lefto, t1, t2]], [[rot_lefto, t2, t1]]]],

Following her lead, you thrust your hands forth and split your fingers in twos, then fours. The tree flickers, expanding into a small forest of copies–each different in exactly one way.

roto, [lambda, [t1, t2], [let, [roto, recur], [conde, [[rot_botho, t1, t2]], [[fresh, [t1l, t1r, t2l, t2r], [eql, t1, [branch, t1l, t1r]], [eql, t2, [branch, t2l, t2r]], [conde, [[eql, t1r, t2r], [roto, t1l, t2l]], [[eql, t1l, t2l], [roto, t1r, t2r]]]]]]]],

Aisha snaps, and with a thwap, unfurls a ludicrously oversized hand-fan from thin air. You ask her where she summoned it from, and how did she ever get Turing to sign it—but she simply bats her eyes and fans herself, looking incredibly smug.

rotso, [lambda, [t1, t2], [let, [rotso, recur], [conde, [[eql, t1, t2]], [[fresh, [t], [roto, t1, t], [rotso, t, t2]]]]]],

The tabletop is filled with trees; outside the conference room, an infinite forest of golden leaves shimmers. Aisha’s fan waves, and a thousand branches whisper in wind-dappled light.

When she refurls the fan, the forest folds with it. Only a solitary tree remains.

It is an act of extraordinary beauty, and for a moment, you are back in the Victorieplaats attic: sunset cast through time-warbled windows, each amber shaft holding sparkling motes of dust which blaze into light, drift briefly, and then go dim again: not lost, merely out of view, and Aisha is whispering an incantation to you, her words unfolding a map within a map within your mind, and you wonder, had you not been recalled, what more you might have become…

“Vidrun. Almost there.”

You take her offered hand in yours, and voices evenly matched, complete the spell.

balanceo, [lambda, [tree, balanced], [conde, [[rotso, tree, balanced], [balancedo, balanced]]]]

Measuring carefully and whispering to herself, Aisha encodes the tree in front of you, and asks for its balanced form:

[map, untree, [run, 1, [t], [balanceo, [tree, [quote, [[0,1],[[2,[3,4]],5]]]], t]]] R = [[[[0, 1], 2], [[3, 4], 5]]].

The tree shifts, blurs, and for an instant you perceive a forest of its balanced siblings, each one possible, but this one yours, and there it is: golden leaves arranged exactly as they were before, but supported by new, more even branches. As her spell unwinds, and the conference room re-attaches to reality, Aisha beams.

“I knew you couldn’t do anything the easy way.”

“Never have,” you admit. “Thank you, Aisha.”

“Any time,” she smiles, and from the tabletop, into your outstretched palms, delivers you a gleaming maple seed.

---

With sincerest thanks to Taber Bain, Zyle Cook, Brad Greenlee, Coda Hale, Duretti Hirpa, Moishe Lettvin, Dan Mess, Kit Patella, and Emily St, who contributed research, story suggestions, and feedback on initial drafts.

This work was inspired by Andréka and Németi’s 1978 The Generalized Completeness of Horn Predicate Logic as a Programming Language, which shows that logic programs are Turing-complete, as well as McCarthy’s 1955 Lisp paper which defines a Lisp evaluator (including recursive lambdas!) in terms of a handful of basic functions: car, cdr, cons, cond, and so on. It also draws on Steele Jr & Sussman’s The Art of the Interpreter. I designed several Prolog metacircular interpreters based on both of these papers, but ultimately wrote the (much more complex) interpreter here in search of concision and execution speed. The µKanren implementation is directly taken from µKanren: A Minimal Functional Core for Relational Programming, by Hemann & Friedman, though Vidrun invokes Friedman, Byrd, and Kiselyov for their work on The Reasoned Schemer. An earlier version of this work followed Byrd, Holk, and Friedman in using miniKanren to generate quines: Vidrun was to escape a trap by constructing interpreters which interpreted themselves. This approach seemed too derivative, and balancing a binary tree was an interview question which I personally bombed in 2010; it felt nice to revisit the problem with Aisha & Vidrun at the helm.

You can find a fully commented and expanded version of Aisha & Vidrun’s program here. This version includes (do ...) expressions, side effects, stacktraces, additional literals, eval, and a partial dynamic type system. In addition to balancing binary trees, it includes a tiny lambda-calculus interpreter: a sort of lisp-in-minikanren-in-lisp-in-prolog.