Yhc

-- do memory and zapping analysis - · Part of the Yhc Manual

darcs get http://www.cs.york.ac.uk/fp/darcs/yhc/
-
darcs get http://www.cs.york.ac.uk/fp/darcs/yhc-devel/
-
$ Makefile yhc
-$ Makefile yhi
-$ Makefile yht
-$ Makefile test 98
-
chmod +x configure   # because darcs does't record the executable bit
-./configure
-make
-
LD_LIBRARY_PATH=/sw/lib    # for dylibs
-LIBRARY_PATH=/sw/lib       # for static linking
-CPATH=/sw/include          # for header files
-
-data Module = Module {objects :: [Object]}
-
-data PackageVer = PackageVer {version :: [Int], name :: String}
-data ModuleName = ModuleName PackageVer {name :: String}
-data Import = Import ModuleName {name :: String, arity :: Int}
-data Export = Export {name :: String, obj :: Object, arity :: Int}
-
-data Object = Function Arity ConstTable HufByteCode
-            | Constructor Arity TagNo
-
-type ConstTable = [Const]
-
-type HufByteCode = [HufBC]
-
-data GraphNode = ...
-data LabeledJumps = ...
-
-instance Show GraphNode
-instance Show ByteCode
-instance Show ByteCodeHuf
-instance Show ...
-
-graphToByteCode :: GraphNode -> ByteCode
-byteCodeToGraph :: ByteCode -> GraphNode
-byteCodeCompress :: ByteCode -> ByteCodeHuf
-byteCodeInflate :: ByteCodeHuf -> ByteCode
-
-writeModule :: Module -> FilePath -> IO ()
-readModule :: FilePath -> IO Module
-
--- do memory and zapping analysis
-memAnalysis :: a -> a
-
--- peep hole optimisations
-peephole :: a -> a
-
darcs send
shackell -AT- cs -DOT- york -DOT- ac -DOT- uk
ndmitchell -AT- gmail -DOT- com
yhc -AT- haskell -DOT- org
  struct HbcFile {
-    Header          header;
-    StringTable     strings;
-    QualifId        moduleName;
-    ObjectTable     objects;
-  };
-
  struct Header {
-    Char           magic[4];        /* 'H' 'S' 'B' 'C' */
-    UShort         majorVersion;
-    UShort         minorVersion;
-    UShort         zero;            /* 0 */
-    UShort         numObjects;      
-  };
-
  struct StringTable {
-    UShort         numStrings;
-    String         strings[numStrings];
-  };
-
  struct String {
-    UShort         length;
-    Char           data[length];
-  };
-
  struct ObjectTable {
-    Object         objects[numObjects];
-  };
-
  struct Object {
-    QualifId      name;
-    UShort        length;
-    Char          data[length];
-  };
-
  'F'            function object (FunObj)
-  'C'            constructor object (ConObj)
-  'P'            primitive object (PrimObj)
-  'X'            external object (ExtObj)
-
  struct FunObj {
-    Char        type;                 /* 'F' */
-    UByte       arity;
-    UShort      stack;
-    ConstTable  consts;
-    UShort      codeLength;
-    UByte       code[codeLength];
-  };
-
  struct ConstTable {
-    UShort     numConsts;
-    Constant   consts[numConsts];
-  };
-
  struct Constant {
-    Char      type;
-    Char      constData[??];
-  };
-
  Type   Name      ConstData         Desc
-
-  'A'    CAF       FullyQualifId     Reference to a CAF node
-  'F'    FUN       FullyQualifId     Reference to a FInfo
-  '0'    FUN0      FullyQualifId     Reference to a zero arity FInfo
-  'C'    CON       FullyQualifId     Reference to a CInfo
-  'Z'    ZCON      FullyQualifId     Reference to a zero arity constructor node
-  'P'    PRIM      FullyQualifId     Reference to a primitive function (XInfo)
-  'X'    EXT       FullyQualifId     Reference to an external function (XInfo)
-  'i'    INT       Int               Int constant
-  'l'    INTEGER   Integer           Integer constant
-  'f'    FLOAT     Float             Float constant
-  'd'    DOUBLE    Float             Double constant
-  's'    STRING    String            String constant
-
  struct ConObj {
-    Char      type;          /* 'C' */
-    UByte     size; 
-    UByte     tag;        
-  };
-
  struct PrimObj {
-    Char           type;         /* 'P' */
-    FullyQualifId  name;
-  };
-
  struct ExtObj {
-    Char          type;          /* 'X' */
-    String        cName;         
-    UShort        arity;
-  };
-
  struct FullyQualifId {
-    QualifId     module;
-    QualifId     item;
-  };
-
  struct QualifId {
-    UByte       length;
-    UShort      stringIndexs[length];
-  };
-
  struct Integer {
-    SByte      length;
-    UByte      data[abs(length)];
-  };
-
  struct Float {
-    Integer   mant;
-    Short     exp;
-  };
-
PUSH n         s_1 .. s_n : ss  ==> 
-         s_n : s_1 .. s_n : ss
-
      PUSH n ; ZAP_STACK (n+1)
-
   PUSH_ARG n ; ZAP_ARG n
-
  MK_AP n        s_1 .. s_m : ss ==>
-                          a : ss                 
-
-  where
-  a is the new application of the given function to the arguments s_1 .. s_m  
-  m is the arity of the function described by constant table item n.
-
  MK_PAP n m    s_1 .. s_m : ss ==>
-                         a : ss
-
  APPLY n      a : s_1 .. s_n : ss ==>
-                            b : ss
-
  _apply(app,arg):
-     NEED_HEAP_32
-     PUSH_ZAP arg
-     PUSH_ZAP app
-     EVAL
-     APPLY 1
-     RETURN_EVAL
-
  MK_CON n    s_1 .. s_m : ss ==>
-                       a : ss
-  where
-  a is the application to the constructor given by constant table item n
-  m is the arity of the constructor
-
  UNPACK            a : ss ==>
-           c_1 .. c_m : ss 
-  where
-  c_1 .. c_m are the arguments of the constructor application a
-  m is the arity of the application a
-
  SLIDE n   s : s_1 .. s_n : ss ==>
-                         s : ss
-
  POP n      s_1 .. s_n : ss ==>
-                          ss
-
  ALLOC n                ss ==>
-            a_1 .. a_n : ss
-  where
-  a_1 .. a_n are 'blackhole' applications.
-
repeat x = xs
-  where
-  xs = x : xs
-
 repeat(x):                      []
-   ALLOC 1                       [ hole ]
-   PUSH 0                        [ hole, hole ]
-   PUSH_ZAP_ARG x                [ x, hole, hole ]
-   MK_CON (:)                    [ x : hole, hole ]
-   UPDATE 0                      [ x:x:x:... ]
-   PUSH_ZAP 0                    [ x:x:x:..., ZAP ]
-   RETURN
-
  UPDATE n         a : s_1 .. s_n : ss ==>
-                       s_1 .. s_n : ss
-
-  where
-  the application at s_n is overwritten with an indirection to a
-
  UNPACK ; PUSH_ZAP n ; RETURN_EVAL
-
  EVAL ; RETURN 
-
  STRING                    s : ss ==>
-          (c:_primCString s') : ss
-
-  where
-  c is the first character of s
-  s' is the StringNode of the rest of the characters in s
-
  _primCString(s):
-     NEED_HEAP_32
-     PUSH_ZAP_ARG s
-     STRING
-     RETURN
-
  PUSH_ARG_0 ; EVAL
-
   +----------+----------+ . . +----------+
-   |  header  |  arg 0   |     |  arg n   |
-   +----------+----------+ . . +----------+
-
   n                     2    0 
-   +---------------------+----+
-   |  info ptr           | fl | 
-   +---------------------+----+
-
  0 0    IND     This node is an indirection, 'info ptr' points to the result.
-  0 1    NORMAL  This is a normal node, 'info ptr' points to the info table.
-  1 0    GC      This flag has special meaning to the garbage collector (see ["Yhc/RTS/Gc"])
-  1 1    HOLE    This is a heap node which is currently under evaluation, 'info ptr' points to info table.
-
  struct _Info {
-    UShort    tag;
-  };
-
  * CINFO      information about a constructor (node is a CON)
-  * PINFO      information about an application (node is THUNK/PAP)
-  * FINFO      information about a function (no node will have this info directly, it'll be a PAP instead)
-  * XINFO      information about an external function (again, no node will have this info directly)
-
  struct CInfo {
-    UShort       tag;     /* 'inherited' from Info */
-    UShort       size;    /* number of arguments to the constructor */
-    Char*        name;    /* name of the constructor */
-    UShort       number;  /* tag number: e.g. 0 for False, 1 for True, etc. */
-    UShort       flags;   /* flags controlling GC */
-  };
-
   CI_NO_PTRS      the arguments of the constructor do not contain pointers (so don't follow them in GC).
-   CI_INTEGER      this is actually an integer (and thus variably sized).
-   CI_ARRAY        this is actually an array (and thus also variably sized).
-   CI_FOREIGN_PTR  this is a foreign ptr (and so requires special treatment in the 'mark' phase).
-
  struct PInfo {
-    UShort          tag;   /* inherited from Info */
-    UByte           size;  /* the number of arguments does this application has */
-    UByte           need;  /* the number of arguments this application is missing */
-  };
-
{ 
-     +-----------------+
-     | PInfo   0 / n   |            size 0, need n
-     +-----------------+
-     | PInfo   1 / n-1 |            size 1, need n-1
-     +-----------------+
-             ...
-     +-----------------+
-     | PInfo   n / 0   |            size n-1, need 0
-     +-----------------+
-     | FInfo   ....    |            function info table
-     .                 .
-     .                 .
-
  struct FInfo {
-    UShort       tag;        /* inherited from Info */
-    PInfo*       papTable;   /* pointer back to the first item in the paptable for this function */
-    FInfo*       link;       /* used by the GC */
-    UShort       arity;      /* function arity */
-    UShort       stack;      /* unused - formely function stack usage */
-    Char*        name;       /* function name */
-
-    CodePtr      code;       /* pointer to the bytecode instructions for this function */
-    UShort       numConsts;  /* number of constants in the constant table */
-    UByte*       constTypes; /* pointer to a table of constant table type information */
-    ConstItem*   constTable; /* constant table constants */
-  };     
-
  f = g (1 : [])
-
  +------------>-----------<----------+
-  | heap->     |           |  <-stack |
-  +------------>-----------<----------+
-  a            b           c          d
-
 ===================
-  |   frame 0     |
-  +---------------+
-  :  stack data   :
-  +---------------+
-  |   frame 1     |
-  +---------------+ 
-  |   frame 2     |     <- fp
-  +---------------+     
-  :  stack data   :
-  :...............:
-  :  stack data   :     <- sp
-  :---------------:
-
  struct Frame {
-    Frame*     fp;     /* saved value of the fp register */
-    CodePtr    ip;     /* saved value of the ip register */
-    Node*      vapptr; /* saved value of the vapptr register */
-  };
-
=========== File HelloWorld.hs ===============
-
-module Main where
-
-main = putStrLn "Hello, World!\n"
-
-==============================================
-
$ yhc HelloWorld
-$ yhi HelloWorld
-Hello, World!
-
-
--- first stage, lexing!
-data Pos = Pos {file :: FileName, line :: Int, pos :: Int}
-data Lex = {- Lexemes -} | InlineComment String | MultilineComment String | WhiteSpace String
-type LexPos = (Lex, Pos)
-
-lex :: String -> [LexPos] -- lex Haskell bits
-lexAll :: String -> [LexPos] -- also lex white space and comments
-
-
-output :: ParseTree -> [LexPos] -> String
-
--- QUESTION:
--- should the standard lexer just lex white space, and pass it onwards
--- what about moving to BLG?
--- that will handle bracketing first, then lexing
--- you can always run the BLG in Lex only mode, just not do it that way for the compiler
--- or offer to dump the bracketed version out before higher merging has been done
-
--- ONE OPTION:
--- lexOnly - not used by the compiler at all, using the lex phase plus some additional rules?
---           maybe entirely separate, just distribute a stadalone lexer if people want it?
--- bracketLex - first step, as the compiler does it - a bracketLex tree, possibly with comments/spaces
-
--- Group should not be run when spaces and comments are in the source!
--- would anyone ever want the source with just lexing, i.e. before bracketing?
-
--- we want round tripping, converting from input to output, can that be done?
-
-
-
-
-
-data ParseTree = ... | Position Pos ParseTree
-
-data Lex = ... | Comment String
-
-data Pos = Pos String Int Int
-
--- maybe with an annotation mechanism
-data ParseTree x = ... | ParseAnnotation x (ParseTree x)
-
-
-parse :: FilePath -> IO ParseTree
-lexer :: FilePath -> IO [(Pos, Lex)]
-
-dependancies :: ParseTree -> IO [FilePath]
-
-typeCheck :: ParseTree -> TypedParseTree
-
-desugar :: ParseTree -> ParseTree
-
-desugarCase :: ParseTree -> ParseTree
-desugarListComprehension :: ParseTree -> ParseTree
-
-
-bytecode :: ParseTree -> ByteCode
-
--- we were gonig to have a separate bytecode manip library, maybe put that in here?
-
-
//Load a module from an array of bytes
-Module loadModule(const char* Data, int Length);
-
-//Load a module from a file
-Module loadModuleFromFile(const char* FileName);
-
-data Console = Console {
-    stdout :: Char -> IO (),
-    stderr :: Char -> IO (),
-    stdin  :: IO Char
-  }
-
-runMain :: Module -> Console -> IO ()
-
-runMainThread :: Module -> Console -> IO () -> IO (IO ())
-
--- result is an action that when applied aborts the computation.
--- There is also an IO that is evaluated when the program terminates cleanly.
-
-

Yhc - York Haskell Compiler

Yhc Manual

License

Yhc Pages

Yhc - Building

Requirements

Getting the Code

Building on Windows

Building on Linux/Unix

Building on Mac OS X

ByteCode API

Module

Bytecode

Yhc FAQ

In relation to nhc98

Portability

Yhc - Hacking

Picking what to hack on

Developer Documentation

Sending your patches

Yhc - Heap Profiling

Lag, drag, void, use

Crazy ideas for Yhc

Have a via C generator

Proof of concept port to Cell architecture

Yhc Introduction

Yhc Porting

Requirements

Steps

Compile yhi

Finished

Yhc - Ports

Documentation for Yhc's Runtime System

Overall Layout

Yhc .hbc Bytecode File Format

Header

StringTable

ObjectTable

Object types

FunObj

Constant Types

ConObj

PrimObj

ExtObj

FullyQualifId

QualifId

Integer

Float

Yhc Bytecode Instructions

END_CODE

NEED_HEAP

PUSH

ZAP_STACK and PUSH_ZAP

PUSH_ARG

ZAP_ARG and PUSH_ZAP_ARG

PUSH_INT and PUSH_CHAR

PUSH_CONST

MK_AP

MK_PAP

APPLY

MK_CON

UNPACK

SLIDE

POP

ALLOC

UPDATE

SELECT

RETURN

EVAL

RETURN_EVAL

TABLE_SWITCH

LOOKUP_SWITCH and INT_SWITCH

JUMP_FALSE

JUMP

STRING

FROM_ENUM

PRIMITIVE

SELECTOR_EVAL

arithmetic

comparison