Yggdrasil

The Background to Yggdrasil

Shen is a multiplatform functional programming language that is written in itself. It is fundamentally defined from a list of 46 system functions written in a microLisp called Kλ. Shen incorporates the features of a modern functional programming language, including pattern-directed data handling, partial applications and currying. It incorporates a Prolog and a compiler-compiler Shen-YACC. It inherits from Lisp the idea of programs as data and macros. It adds the power of sequent calculus to define types and for all these reasons Shen is par excellence a power tool for exploring ideas in computer science.

Between 2011 and 2018, Shen was ported to many platforms; Common Lisp (SBCL, CLisp), Wasp Lisp, Emacs Lisp, Clojure, Scheme, Python, Javascript, Ruby, Go, C, C++, and the JVM. This was an historical achievement which has not been matched in any other language community. Shen has established itself as not just a programming language, but the closest thing that computer science has produced to a universal high-level medium that transcends the boundaries between programming languages.

In order to leverage this power, it is necessary to take the next logical step, which is to create the power to turn any Shen program into an executable stand-alone application that is coded in the native code of the platform under which Shen runs. Hence it should be possible to generate an executable Python program from Shen running under Python. The trick is creating a program that extracts from the Shen kernel, just that code that is needed to make the application run.

Yggdrasil

In programming parlance, this is called a tree-shaker ; a program that traces the call tree structure of a program and eliminates all code that cannot be called from the top level. Because Shen compiles into a Lisp, Kλ, it is easy to treat this code as data and traverse the Kλ call tree to derive the needed code. This is the heart of a fundamental program which we call Yggdrasil .

Yggdrasil was the world tree which, in Viking mythology, supported the nine realms of existence. In our picture, the roots of Yggdrasil is the language Kλ which underpins Shen and the branches extend into the other programming worlds. By extracting the needed Kλ and using the existing compilers to map the Kλ to native code, we create a system in which programmers can realise their ideas in any mainstream programming medium by simply writing the Shen program and using Yggdrasil to generate the executable.

Downloading Yggrasil and the Documentation

Yggdrasil can be downloaded from here. The documentation is available here.

How Yggdrasil is Implemented

There are 14 implementations of Shen in different languages. Originally each implementation was supposed to reflect the others. For lovers of philosophy, this is the structure of Leibniz's cosmology of monads which although independent reflect each other by a preprogrammed similarity in form. Geometrically this would be represented by a tetradecagon where every vertex would be connected to every other vertex.

This architecture would require that each implementation was kept up to date with the latest standard. However many implementations have fallen behind and only one, the Common Lisp version, is currently (2021) kept up to date of which SBCL/Shen is the best. It is not feasible with a voluntary project to bring all these implementations up to the latest standard. Moreover expecting programmers to mirror the latest patches throughout 14 languages is not feasible either. In addition the load of maintaining the 196 connections displayed in the above diagram is beyond the resources of the project.

However there is a different architecture which allows Yggdrasil to work to the latest standard on all platforms even though only one of them is fully up to date. This architecture will allow Yggdrasil to generate the latest standard object code on all platforms. This architecture works by placing the S31 SBCL/Shen port at the centre of the tetradecagon and connecting each port to the S31 SBCL/Shen port. By reaching out into the internals of each port using a remote web connection from the centre, we can systematically harness the work done and maintain the system using only 14 connections and not 196.

What Yggdrasil Means for Computing

Shen offers a degree of power and security found in few existing languges and no language has as many certified ports into other computer languages. A program written in Shen can be verified as type secure using the resources of mathematical logic and we can choose into what language to transpile this program. The resulting program from Yggdrasil inherits all the security and power of the Shen program. This has huge implications for the production of software in safety critical areas like flight, space research and medicine.

Listen to our 6 minute video explaining the Yggdrasil project.

LATEST NEWS

The support page for the text Logic, Proof and Computation is established.