WebHome
- Education Page
- Literature
- Schedule
- Assignments

Center
Master Program
EHCTo Clean Core

Eifl
---+  %RED% <center><u>Project abandoned</u></center> %ENDCOLOR%


---++++ [[Students.NielsVanDerVelden][Niels van der Velden]] and Nuno Constantino Castro

---++ Assignment description
The goal of this assignment is to implement code generation for the [[Ehc.WebHome][EH compiler]] to Clean's ABC machine

---++ Planning
| *week*         | *date*           | *what*                                                                 |
|   13-19 sep    | Read part of _Functional Programming and Parallel Graph Rewriting_ about the ABC machine ||
|   20-26 sep    |    Thu 23 sep    | <strike>Present basic stuff about the ABC-machine</strike>             |
|                |    Fri 24 sep    | Meeting at KUN 13:00, toernooiveld 1, room A-4008                      |
|                |    Zat 25 sep    | put online information gathered from the meeting Fri 24 sep.           |
|                |    Sun 26 sep    | look through .c files to better understand code generation and         |
|                |                  | ultimately extracting (simple/naive) compilation schemes               |
| 27 sep - 3 okt |    Tue 28 sep    | Present our findings so far, report our activity (problems, etc.)      |

---++ Log
The generation of ABC from a certain Clean program proceeds as follows;
   * Clean program gets parsed etc into an abstract syntax tree (ast), representing the program in the Clean Core language. (this language is undocumented)
   * Multiple Calls are made to a C-library that is responsible for the generation of the ABC-code.
So the frontend of the compiler is written in the Clean language itself, but the code generation is done by a clump of c-code.

---++++ <u>Our first approach:</u>
   * Try to mimic what this code generation library is doing and formalize this in the form of compilation schemes for the EH language.
This proved a very difficult task since the only documentation about how this translation from Clean to ABC-code proceeds, is in the form of tenthousands lines of c-code. Even for the smallest program thinkable in EH (namely the program consisting of one integer) produced a significant file with abc-instructions. There was too little documentation available (even about these instructions since a lot of them aren't mentioned in the book (Plasmeijer, M.J. and van Eekelen, M.C.J.D. __Functional Programming and Parallel Graph Rewriting__)) to be able to derive compilation schemes. Another thing that made this approach of deriving schemes even harder was the fact that the generated ABC-code by the clean compiler was highly optimized. There was no easy way of turning off this optimization and force the compiler to generate dumb code (only strictness analysis could be turned off *partially*). We depended on the following workmethod;
   * make an EH example program
   * make an equivalent Clean program
   * let the clean compiler produce ABC-code for this ABC example
   * look at the ABC file to try to understand the translation process.
Looking at the c-files which do this translation turned out to be __no__ option since this generation was spread out over 4/5 files containing tenthousands lines of code (there was 'no' logical seperation in multiple files so a lot of code calling to different files, etc, etc.)

---++++ <u>Our second approach:</u>
Instead of mimicing the translation process hidden in the c-library, we decided to look at an alternative route. Clean actually uses foreign functions to call this c-library and generate the code. I should note that there is an intermediate language above the ABC-code (which are basically stack manipulating instructions), called the Clean Core. This probably resembles a core lambda calculus with sugar like lets etc. We are not sure, because this language (Clean Core) is totally undocumented. Of course there has to be some Clean source files that contain the data definition of this language, but that is the only 'documentation' that exist about this language. The Clean program has to be shipped to the library at some point (in this Clean Core format). So we had to look at a couple of points;
   * Interfacing with a c-library from Haskell.
   * Find out how to instrument the code generating library.
   * Find out the form of the abstract syntax tree (AST) this library expects (the Clean Core language)
   * Make a translation from EH AST's to Clean Core AST's

*Interfacing with a c-library*
When using foreign entities in Haskell there are a couple of scenario's;
   * call a foreign function
   * access a foreign datastructure
   * make a haskell function available in the foreign context
   * make haskell data available in the foreign context
When calling a foreign function and providing a function as argument for example, the foreign context could make a callback. This requires more work since the calling of functions are done in two directions.
Let's first look at the simple scenario where we just call a c-function (which is our foreign context) from Haskell assuming no callback takes place. This is what you have to do to make it work;

*Haskell code*
<verbatim>
module Main where

import Foreign.C.Types(CDouble)

foreign import ccall "math.h sin" foreign_sin :: CDouble -> CDouble

main = do (putStr . show . foreign_sin) 0.0
</verbatim>

*compiling/linking process*
<verbatim>
$ ghc -fffi -c Main.hs
$ ghc -fffi Main.o -lm
$ ./a.out
</verbatim>

This shows how to call a c-function from Haskell. A couple of things are remarkable. There has to be a mapping from Haskell types to C-types. Thats why in the Foreign module there are numerous types like CInt, CDouble, which are Haskell counterparts of Int and Double in C.

*Interfacing with the code generating library*

Since we now know how to call c-functions from Haskell. We have to look at how to instrument this specific c-library that generates code. There exists a .h file which associates Clean function types with C function prototypes. Then there is an actual Clean file that contains the code for all these Clean functions that basically call the C equivalents. The only difference and difficulty is that the Clean equivalent functions have more arguments. This makes it somewhat more difficult to understand whats going on.
We found out that *backendinterface.icl* contains a lot of calls to the foreign functions. The main things where the compilation is done is *compiler.icl* which uses the function *backEndInterface* from *backendinterface.icl*. This function generates the code in a couple of steps.

---++ Repository
We exported the [[https://svn.cs.uu.nl:12443/repos/EHC/][EHC repository]] and imported it into a new repository for this project. This way we can change source files and fully enjoy the benefits of a version management system, without having to commit to the original [[https://svn.cs.uu.nl:12443/repos/EHC/][EHC repository]]. If necessary we can always checkout the original [[https://svn.cs.uu.nl:12443/repos/EHC/][EHC repository]] and merge it with our code if there are really critical updates in the original repository.

[[https://svn.cs.uu.nl:12443/repos/EHC_ABC/][Our repository URL]]

---++ Literature
   * Plasmeijer, M.J. and van Eekelen, M.C.J.D. __Functional Programming and Parallel Graph Rewriting__, Addison-Wesley Publishing Company, 1993.
   * __The Haskell 98 Foreign Function Interface 1.0; An Addendum to the Haskell 98 Report__
   * Daan Leijen. <nop>PhD Thesis, __The &#955; Abroad  A Functional Approach to Software Components__, November 2003.

-- [[Students.NielsVanDerVelden][Niels van der Velden]] - 14 Sep 2004