path: root/report/esoteric_project_report.tex

\documentclass[a4paper, oneside, 11pt]{report}
\usepackage{epsfig,pifont,float,multirow,amsmath,amssymb}
\newcommand{\mc}{\multicolumn{1}{c|}}
\newcommand{\mb}{\mathbf}
\newcommand{\mi}{\mathit}
\newcommand{\oa}{\overrightarrow}
\newcommand{\bs}{\boldsymbol}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
\usepackage{mathtools}
\topmargin = 0pt
\voffset = -80pt
\oddsidemargin = 15pt
\textwidth = 425pt
\textheight = 750pt

\begin{document}

\begin{titlepage}
\begin{center}
\rule{12cm}{1mm} \\
\vspace{1cm}
{\large  CMP-6048A / CMP-7009A Advanced Programming Concepts and Techniques}
\vspace{7.5cm}
\\{\Large Project Report - 15 December 2021}
\vspace{1.5cm}
\\{\LARGE Esoteric Compiler / Interpreter Project}
\vspace{1.0cm}
\\{\Large Group members: \\ Eden Attenborough, Alfie Eagleton, Aiden Rushbrooke, Chris Sutcliffe}
\vspace{10.0cm}
\\{\large School of Computing Sciences, University of East Anglia}
\\ \rule{12cm}{0.5mm}
\\ \hspace{8.5cm} {\large Version 1.0}
\end{center}
\end{titlepage}


\setcounter{page}{1}
%\pagenumbering{roman}
%\newpage


\begin{abstract}
ABSTRACT INCOMPLETE
\end{abstract}

\chapter{Introduction}
\label{chap:intro}
For this project we have decided to create an Esolang interpreter in Java so that we can write code, craft Boolean expressions and calculate Math. We plan to research, design and implement an esoteric language while also understanding fundamental advanced programming concepts.

\section{Functional Requirements}
After some discussion, we decided that our goals for this project are to create grammar for a language and form a lexical analysis algorithm. After this, we may develop a parser or interpreter so that we can convert our high level code into bytecode which can be read more easily by the JVM.

\section{Non-functional Requirements}
Our code should be well tested, and be capable of handling edge cases. It should be modular and scalable so that functionality can easily be added without undue difficulty. It would be good if our interpreter could calculate mathematical functions and have good performance with well optimized code.

\section{Technology}
We are looking at coding Java in IntelliJ, and potentially using GNU Bison to parse.

\section{MoSCoW Analysis}
We thought about what our interpreter may or may not have so that we have a clear understanding of our priorities when coding. We decided that our software \emph{must} read and interpret commands immediately from a command line. The language \emph{must} be Turing complete, and be capable of detecting syntax and runtime errors. It \emph{should} be able to read from file and execute a script. It also \emph{should} be able to optimize source code during runtime. The interpreter \emph{could} be able to implement functions and procedures with return values, and be able to handle memory allocation and disposal. Our program \emph{won't have} a graphical or web-based interface, since it would take up too much development time and is not entirely needed for the scope of this project. It also will not implement object-oriented programming features.

\section{Report structure}
Breifly describe what you will cover in the remainder of the report, chapter by chapter.

\chapter{Research of Similar Systems}

\section{Compilers vs Interpreters}
Within the field of computer programming languages, there are two main types: compiled languages and interpreted languages. Both of these styles have distinct advantages and disadvantages. Compilers and interpreters both convert code written in human readable higher-level languages to instructions that a computer can execute. 

In the case of compiler, code is converted from high level program code to assembly language then to machine language. This process can be slow, especially when there is a large amount of code to compile, but execution is fast as only the instructions directly executed are required to be kept in memory. 

In contrast to this, Interpreter directly runs the code given to it, or in other words, an interpreter is a separate program that reads and executes the instructions itself, rather than converting them into the assembly language of that particular architecture being run on. The principal advantage of this is that a computationally expensive compilation process does not have to be run every time, therefore leading to faster startup times. However, this approach carries with it a big disadvantage, namely that because every line has to be interpreted, execution is slower than the equivalent instructions run in a compiled language.   

\section{Interpreted Programming Languages}
There are a number of prominent interpreted languages in use today, including Python, Matlab, Perl, Ruby and PHP. All of these languages have interpreters that are written in C or C++, which are compiled languages. The interpreters for each language are loaded into memory, along with an instruction that they then interpret.  

\section{Esoteric Languages (Esolangs)}
Esolangs are programming languages designed to be jokes or proof of concept languages, rather than those to be used in actual programming tasks. Typically, the reason they are created is for fun rather than any serious desire to solve a particular programming problem, and so most languages aim to be funny, to be as difficult to use as possible or to have few features while still being Turing complete.   

\section{Example - Shakespearian Programming Language}
The Shakespeare Programming Language is esoteric code parodied on extracts from Romeo and Juliet. Here, code is written so it reads like how a script would, such as \texttt{[Enter Juliet]} where \texttt{Juliet} may be a variable name. Other examples include using \texttt{Acts} or \texttt{Scenes} as GOTO statements, where the interpreter can jump to a certain point in the code and read from there. Otherwise, these are ignored similar to the title or character descriptions. Other examples include LOLCODE, Hodor or White Space. This serves the purpose of writing code in a different manner to usual, sometimes for humour. The aim is to replace typical language features so that it can still be read by a compiler or interpreter but also look and read very differently by the user.  

\chapter{The Structure of our Programming Language}
\section{The Lexar (Lexical Analysis)} 
In the field of linguistics or computer programming language design, lexical analysis is the process of converting a sequence of characters (such as a computer program) into a sequence of tokens. 
This process is also known as tokenisation, particularly in the field of natural language processing (NLP).
When designing a programming language, the task of lexical analysis or tokenisation is performed by a lexer. 
The actual matching of tokens is often performed using regular expressions, defined in the design stage in order to reliably match all tokens in the language. 


\chapter{Grammar}


\section{Introduction to Language Grammar}
\begin{verbatim}

Work in progress currently

\end{verbatim}
Context free grammars – something = something else 

Context free because there is no rule or context about where this grammar belongs, only where it goes

Rewrite rules:
S $\rightarrow$ DET N
Were first invented by Panini %Pāṇini
 who worked on Sanscrit grammar rules
 
Port Royal Grammer by Antoine Arnauld and Claude Lancelot in 1660 who worked at Port-Royal-des-Champs

then Ferdinand de Saussure (19th century)

then Chomsky with Chomsky hierarchy.


BNF form (Backus Naur form)  is a meta language for grammars
Named after the people who invented it simultaneously 
example:
\begin{verbatim}<program> ::= <sequence>? 
\end{verbatim}
This means a program consists of a sequence of allowable grammars followed by question mark
Can be read as “program consists of a sequence of things followed by question mark”


Grammar consists of a series of rewrite rules
Grammar is a quadruple. It is a set of:
\begin{itemize}
	\item Terminal symbols
	\item Non terminal symbols
	\item Set of rules
	\item Start symbol (one of the non-terminal symbols)	
\end{itemize}


Any regular grammar can be recognised by regular expressions (refer to regular grammar in Chomksy hierarchy)

After Chomsky came Backus and Naur – BNF 

Niklaus Wirth – Pascal language

Dijkstra – programming without goto (gotoless programming)


\section {Why we chose FORTRAN}

asdf

\begin{table}[h!]
	\begin{center}
		
		\begin{tabular}{|l|r|}
			\hline
			\textbf{Token} & \textbf{Replaces}\\
			\hline
			! & \slash\slash \\
			\hline
			PROGRAM x & public class x \{ \\
			\hline
			END PROGRAM & \} \\
			\hline
			INTEGER & int \\
			\hline
			LOGICAL & boolean \\
			\hline
			.FALSE. & false \\
			\hline
			.TRUE. & true \\
			\hline
			CHARACTER(LEN=x) & String \\
			\hline
			:: & = \\
			\hline
			IF (x) THEN & if(x) \{ \\
			\hline
			ELSE & else \\
			\hline
			END IF & \} \\
			\hline
			SELECT CASE (x) & switch(x) \{ \\
			\hline
			CASE (x) & case x: \\
			\hline
			CASE DEFAULT & default: \\
			\hline
			END SELECT & \} \\
			\hline
			x & x; \\
			\hline
			DO x = y, z & for(x = y, x < z; x++) \{ \\
			\hline
			END DO & \} \\
			\hline
			PRINT *, x & System.out.println(x); \\
			\hline
			SUBROUTINE x & static void x() \{ \\
			\hline
			END SUBROUTINE & \} \\
			\hline
			CALL x & x(); \\
			\hline
		
		\end{tabular}
		\label{tab:table1}
		\caption{Grammar table for Fortran}
	\end{center}
\end{table}

\clearpage
\chapter{BNF form}

\cite{davie1982recursive} talk about bnf form here


\begin{table}[h!]
	\begin{center}
		
		\begin{tabular}{|l|r|}
			\hline
			\textbf{Abbreviation} & \textbf{Term}\\
			\hline
			$<$program$>$ ::= & $<$sequence$>$ \\
			\hline
			$<$statement$>$ ::= & $<$assignment$>$ $|$ \\
			 & IF $|$ \\
			 & WHILE \\
			\hline
			$<$sequence$>$ ::= & $<$assignment$>$ $|$ $<$sequence$>$ $|$ \\
			& $<$clause$>$ $|$ $<$sequence$>$ $|$ \\
			&$<$empty$>$ \\
			\hline
			$<$clause$>$ ::= & IF $|$ \\
			& DO $|$ \\
			& PRINT $|$ \\
			& FUNCTION \textbar \\
			& SUBROUTINE \\
			\hline
			$<$assignment$>$ ::= & CHARACTER $<$string$>$ = $<$expression$>$ $|$ \\
			& LOGICAL $<$string$>$ = $<$expression$>$ $|$ \\
			& COMPLEX $<$string$>$ = $<$expression$>$ $|$ \\
			& REAL $<$string$>$ = $<$expression$>$ $|$ \\
			& INTEGER $<$string$>$ = $<$expression$>$ \\
			\hline
			PRINT ::= & PRINT format [ , output\textunderscore item\textunderscore list ] \\
			\hline
			FUNCTION ::= & FUNCTION $<$string$>$ [ , output\textunderscore item\textunderscore list ] \\
			& $<$sequence$>$ \\
			& RETURN END FUNCTION \\
			\hline
			IF ::= & IF $<$expression$>$ THEN $<$statement$>$ END IF $|$\\
			 & IF $<$expression$>$ THEN $<$statement$>$ ELSE $<$statement$>$ END IF \\
			\hline
			DO ::= & DO  $<$label$>$ $<$identifier$>$ = $<$expression$>$, \\
			 & $<$expression$>$ $<$statement$>$ continue $|$\\
			 & DO  $<$expression$>$ $<$expression$>$ = $<$expression$>$, \\
			 & $<$expression$>$, $<$expression$>$ $<$statement$>$ continue \\
			\hline
			
			
			CHARACTER ::= & any character in ascii table\\
			\hline
			
			LOGICAL ::= & TRUE\textbar FALSE \\
			\hline
			
			COMPLEX ::= & a combination of real and imaginary numbers e.g. $3i$ where $i = \sqrt{-1}$\\
			\hline
			
			REAL ::= & INTEGER\textbar RATIONAL\textbar IRRATIONAL\\
			\hline
			
			RATIONAL :: = & any fractional number e.g. 1/3 or 0.333 \\
			\hline
			
			IRRATIONAL ::= & $\pi$ \textbar  $\sqrt{2} $ etc. \\ 
			\hline
			
			
			INTEGER ::= & 0\textbar1\textbar2\textbar3\textbar4\textbar5\textbar6\textbar7\textbar8\textbar9 \\
			
			\hline
		\end{tabular}
		\label{tab:table1}
		\caption{Grammar table for Fortran}
	\end{center}
\end{table}

\chapter{Methodology}\label{MethLab}

Describe here various methods that will be used in your project. Use different sections for distinctly different subjects and use subsections for specific details on the same subject. Only use subsubsections or paragraphs (which are not numbered) if you believe this is really necessary. Since implementation will happen in sprints, this section may need several updates with parts being added and deleted across the project.

\section{Method 1}
\subsection{Method 1 specific detail 1}
In case you need maths, here is an example to write an equation:
\begin{equation}\label{weak_form}
\int_{\Omega_0} \delta u \frac{\partial \mathbf{P}}{\partial X}d\Omega_0 + \int_{\Omega_0} \delta u \mathbf{b} d\Omega_0 + \int_{\Omega_0} \delta u  \rho_0\mathbf{\ddot u} d\Omega_0 = 0
\end{equation}
And here we show how to write a matrix equation:
\begin{equation}\label{Jacobian}
 \mathbf{X}  \frac{\partial N}{\partial e_c} =  \left[  \begin{array}{cccc} x_1 & x_2 & x_3 & x_4 \\  y_1 & y_2 & y_3 & y_4 \\  z_1 & z_2 & z_3 & z_4 \end{array} \right] \left[  \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0& 1 \\  -1 & -1 &  -1  \end{array} \right] 
\end{equation}


\subsection{Method 1 specific detail 2}
blablabla

\paragraph blablabla

\section{Method 2}

\subsection{Method 2 specific detail 1}

\section{Etc.}

\subsection{Etc.}

\chapter{Implementation}\label{Impl}

In this chapter you cover the actual implementation of your project. Implementation will be done in sprints so you may wish to use different sub-sections for each sprint and then dedicate a section to your final deliverable. Section \ref{Figures} with figures  should not remain in the final report.

The long string following the sprint number is the git commit at the point in the git repository at which the tests were conducted.

\section{Early sprints}
\subsection{Sprint 1 - \texttt{cb29252f1e0d29d555fb232f39d343930fc76105}}
The first functional program version was a simple lexical analyser. At this stage no calculations were done. For example:

\begin{verbatim}
Code: 3-1+2
\end{verbatim}
Produces the output:
\begin{verbatim}
NUMBER 3 3.0
MINUS - null
NUMBER 1 1.0
PLUS + null
NUMBER 2 2.0
\end{verbatim}
A more complex example:
\begin{verbatim}
Code: (36/2 + 45.2) * 3
\end{verbatim}
Produces the result:
\begin{verbatim}
LEFT_PAREN ( null
NUMBER 36 36.0
SLASH / null
NUMBER 2 2.0
PLUS + null
NUMBER 45.2 45.2
RIGHT_PAREN ) null
STAR * null
NUMBER 3 3.0
\end{verbatim}

\subsection{Sprint 2 - \texttt{69b0ad07bac30beca1397ff187468e7597203c44}}
This version added simple variable declaration and assignment, as well as a simple calculator. It also added reading from files. For example, running \texttt{java Interpreter.Language example2.txt} where \texttt{example2.txt} is the following:

\begin{verbatim}
var :: a
a=5
a=a+1
print a
\end{verbatim}
Produces the result:
\begin{verbatim}
6.0
\end{verbatim}
Testing involved making sure the program worked with the rules of left-associativity; for example, the program:
\begin{verbatim}
var :: a
a=3-1+2
print a
\end{verbatim}
Produces the result \texttt{4.0}.
We also tested BIDMAS rules by using complex expressions:
\begin{verbatim}
var :: a
a=(36/2 + 45.2) * 3
print a
\end{verbatim}
Returns \texttt{189.60000000000002}, which is correct considering the inaccuracy of floating points in computers. Finally, a test of a more complex program:
\begin{verbatim}
var :: a
a=5
a=a+1
print a

a=7
a=a*2
print a

var :: b
b = 10
print a+b
\end{verbatim}
Produces the result:
\begin{verbatim}
6.0
14.0
24.0
\end{verbatim}
You can test the error handling in several ways. For example the program
\begin{verbatim}
a=3
print a
\end{verbatim}
Uses an undefined variable \texttt{a}. The output of running this is:
\begin{verbatim}
An error was encountered
Variable undefined
\end{verbatim}
You can also try and run a program with a syntax error, for example:
\begin{verbatim}
var :: a
a=3+
print a
\end{verbatim}
Produces:
\begin{verbatim}
An error was encountered
Expected Expression
\end{verbatim}
This is how it reacts to using an undefined token:
\begin{verbatim}
var :: a
a=3
pprint a
\end{verbatim}
Produces:
\begin{verbatim}
An error was encountered
Undefined Variable
\end{verbatim}

\subsection{Sprint 3 - \texttt{a12094123dcacee41a7472031db6fe6027b083a7}}
This version added full compilation to a binary by translating to a C program and using gcc to compile it straight away. It also added strings as lists of characters, and simple if statements. For example running \texttt{java Compiler.Language example.txt} where \texttt{example.txt} is the program:
\begin{verbatim}
character (len=10)::hello
hello="hello"
if 5==5 then
hello="goodbye "
endif
print *,hello,6," test" endprint
\end{verbatim}
Produces, in the \texttt{build/} folder, \texttt{example.c}:
\begin{verbatim}
#include <stdio.h>
#include <string.h>
int main(){
char hello[11];
strcpy(hello,"hello");
if(5==5){
strcpy(hello,"goodbye ");
}
printf("%s%d%s",hello,6," test");
}
\end{verbatim} 
It also compiles this file automatically, checking for errors during the process, and produces the executable binary \texttt{example.exe} in windows, or \texttt{./example} if run in a distribution of GNU+Linux. It then runs the binary straight away, checking for runtime errors. The output of running this binary is:
\begin{verbatim}
goodbye 6 test
\end{verbatim}
Here's an example of a program which produces a runtime error:
\begin{verbatim}
character (len=3)::hello
hello="hello"
if 5==5 then
hello="goodbye "
endif
print *,hello,6," test" endprint
\end{verbatim}
It produces a runtime error since the character string is too short. When it's run, it says:
\begin{verbatim}
An error was encountered
Runtime Error
\end{verbatim}
This version also added better error messages. For example \texttt{hello="hello} produces:
\begin{verbatim}
An error was encountered
Strings must end with "
\end{verbatim}
Moreover, the program
\begin{verbatim}
character (len=10)::hello
hello="hello"
if 5==5 then
hello="goodbye "
print *,hello,6," test" endprint
\end{verbatim}
Produces the error message:
\begin{verbatim}
An error was encountered
endif missing
\end{verbatim}
Finally, lets test if statements with another program:
\begin{verbatim}
character (len=10)::hello
hello="hello"
if 4==5 then
hello="goodbye "
endif
print *,hello,6," world" endprint
\end{verbatim}
Produces the result:
\begin{verbatim}
include <stdio.h>
#include <string.h>
int main(){
char hello[11];
strcpy(hello,"hello");
if(4==5){
strcpy(hello,"goodbye ");
}
printf("%s%d%s",hello,6," world");
}

hello6 world
\end{verbatim}

\subsection{Sprint n}


\section{Final implementation}

\section{Figures, tables, etc.}
\label{Figures}

The purpose of this section is to just show you how to integrate figures, tables, etc.\ and should disappear in the final report. Figures and tables should be distributed across the document wherever they are needed but you should use an appendix if they are many figures/tables of the same kind. Fig.\ \ref{Pelvis_BVH} shows a bony pelvis.

\begin{figure}[htb]
%\begin{center}
\caption{The bony pelvis model with octree based AABBs (Axis Aligned Bounding Boxes).}
\label{Pelvis_BVH}
%\end{center}
\end{figure}

Fig.\ \ref{class} shows a UML class diagram (class, sequence and state diagrams are the most frequently used UML diagrams):

\begin{figure}[htb]
%\begin{center}
\caption{A UML class diagram.}
\label{class}
%\end{center}
\end{figure}

Algorithms can be either used in this chapter or alternatively in Chapter \ref{MethLab} if it is a more generic algorithm:

\begin{algorithm}[th]
\caption{ The projection based contact method algorithm }
\begin{algorithmic}[1]
\STATE Retrieve current node displacement $u$
\\ \texttt{float3 u = m\_U\_new[nodeIndex].xyz;}
\STATE Retrieve constraint plane equation
\\ \texttt{float4 plane = m\_constraintMagnitude[nodeIndex];}
\STATE Calculate dot product with plane normal
\\ \texttt{float d = dot(u, plane.xyz);}
\STATE Find node penetration into the plane's negative half-space
\\ \texttt{float penetration = plane.w - d;}
\IF {penetration is greater than zero}
	\STATE Find projection onto the plane surface
	
	\texttt{float3 proj = u + plane.xyz * penetration;}
	\STATE Prescribe new nodal position to be on the surface
	
	\texttt{m\_U\_new[nodeIndex] = (float4)(proj, 0.0f);}
\ENDIF
\end{algorithmic}
\end{algorithm}

Tables such as Table \ref{Res01} can also be useful here or in Chapter \ref{MethLab}.

\begin{table}[h]
\caption[]{Original diameters and diametral strains as reported by
  Sorbe and Dahlgren \cite{Sorbe:1983} (columns 1-2), from a previous 
  experiment by Lapeer and Prager and reported in \cite{Lapeer:2001}
  (columns 3-4), and from the current experiment (columns 5-6).}
\begin{center}
\begin{tabular}{|l|c|c||c|c||c|c|}\hline
& \multicolumn{2}{c||}{S-D} & \multicolumn{2}{c||}{L-P old} & \multicolumn{2}{c|}{L-P new} \\ \hline
Diameter & length & strain & length & strain & length & strain \\ \hline
$\mi{MaVD}$ & 140.5 & +1.90 & 129.3 & +0.30 & 129.3 & +1.43 \\
$\mi{OrOD}$ & 131.4 & +0.10 &   -   &  -    & 119.9 & +1.85 \\
$\mi{OrVD}$ & 126.9 & +2.20 & 119.3 & +0.25 & 119.3 & +1.24 \\
$\mi{OFD}$  & 134.0 & +0.40 &  -    &   -   & 119.7 & +1.82 \\ 
$\mi{SOFD}$ &  -    &   -   &  -    &   -   & 113.2 & -0.85 \\
$\mi{SOBD}$ & 117.1 & -1.70 &  88.7 & -1.07 &  88.7 & -2.52 \\
$\mi{BPD}$  & 105.0 &  0.00 &  89.7 & -0.21 &  89.7 & -0.83 \\ \hline
\end{tabular}
\label{Res01}
\end{center}
\end{table}

Note that code snippets or lists of crucial programming code or large UML diagrams should go in the Appendix/Appendices.


\chapter{Testing}

Describe various experiments you designed to test your software product. This could be subdivided to be in line with the Sprints in Chapter \ref{Impl}. In case you have protocols which cover various pages, please put them in an appendix (e.g. Appendix A) instead.

\chapter{Discussion, conclusion and future work}

Briefly discuss and conclude your achievements and put them in perspective with the MoSCoW analysis you did early on. Be honest by declaring for example `S' categorised objectives which did not make it to the final deliverable rather than reversely modifying your MoSCoW in Chapter \ref{chap:intro}! Also discuss future developments and how you see the deliverable improving if more time could be spent. Note that this section should not be used as a medium to vent frustrations on whatever did not work out (pandemic, group partners, etc.) as there are other means for this (labs, e-mail MO, ...) that should be used well before any such problems become an issue.


\bibliographystyle{unsrt}
\bibliography{References}

\chapter*{Contributions}

State here the \% contribution to the project of each individual member of the group and describe in brief what each member has done (if this corresponds to particular sections in the report then please specify these).

\chapter*{Appendix A}

Put in tables of data or protocols (e.g. for testing) or code listings or UML diagrams which may take up several pages and do not sit well in the main body text.

\end{document}