Difference between revisions of "Yhc/API/Core"
NeilMitchell (talk | contribs) |
NeilMitchell (talk | contribs) |
||
(27 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
{{Yhc}} |
{{Yhc}} |
||
− | Yhc Core is a way of dumping and using the internal representation of Yhc in an external project |
+ | Yhc Core is a way of dumping and using the internal representation of Yhc in an external project. |
− | == Haddock |
+ | == Haddock documentation == |
* http://www.cs.york.ac.uk/fp/yhc/snapshot/docs/Yhc-Core.html |
* http://www.cs.york.ac.uk/fp/yhc/snapshot/docs/Yhc-Core.html |
||
− | == |
+ | == Overview == |
+ | Yhc.Core is a simple core Haskell-like language, feature case statements, let statements, top level lambda's and data values. Much of the syntactic sugar present in Haskell has gone (list comprehensions, typeclasses, overloaded names, nested lambdas) |
||
− | The following sequence of blog posts probably gives a useful introduction to Yhc Core. |
||
+ | The strengths of Yhc.Core are: |
||
− | * http://yhc06.blogspot.com/2005/12/yhc-core.html |
||
+ | |||
− | * http://yhc06.blogspot.com/2006/07/yhc-core-v2.html |
||
+ | * Simple representation of Haskell |
||
− | * http://yhc06.blogspot.com/2006/09/yhccore-api-available.html |
||
+ | * Relatively simple to relate Core to original Haskell |
||
+ | * Source locations are preseved |
||
+ | * Minimal name mangling |
||
+ | * Few syntactic forms |
||
+ | |||
+ | The weaknesses are: |
||
+ | |||
+ | * Yhc cannot compile Yhc Core files, format is write only (fix is being worked on) |
||
+ | * Types are not present (hard to fix, a lot of work) |
||
+ | |||
+ | The intended users: |
||
+ | |||
+ | * Analysis tools |
||
+ | * Compiler backends |
||
== Generating Core == |
== Generating Core == |
||
+ | Yhc Core files are stored as .ycr files in a binary format. They can be generated by passing the <code>--core</code> flag to the compiler: |
||
− | To generate Core, simply give the compiler the option <tt>-core</tt> or <tt>-corep</tt>. For example, when compiling |
||
+ | |||
+ | yhc --core Main.hs |
||
+ | |||
+ | If you want all definitions from all libraries included in then: |
||
+ | |||
+ | yhc --linkcore Main.hs |
||
+ | |||
+ | To view the Core output, <code>yhc Main --showcore</code>, with the output going to the screen in a pretty printed format. To view an existing Core file, <code>yhc --viewcore File.ycr</code>. |
||
+ | |||
+ | == The Core output == |
||
+ | |||
+ | For an example of the Core output, taking the following program: |
||
+ | |||
+ | <haskell> |
||
+ | head2 (x:xs) = x |
||
+ | |||
+ | map2 f [] = [] |
||
+ | map2 f (x:xs) = f x : map2 f xs |
||
+ | |||
+ | test x = map2 head2 x |
||
+ | </haskell> |
||
+ | |||
+ | Generates: |
||
+ | |||
+ | <haskell> |
||
+ | Sample.head2 v220 = |
||
+ | case v220 of |
||
+ | (:) v221 v222 -> v221 |
||
+ | _ -> Prelude.error Sample._LAMBDA228 |
||
+ | |||
+ | Sample._LAMBDA228 = |
||
+ | "Sample: Pattern match failure in function at 9:1-9:15." |
||
+ | |||
+ | Sample.map2 v223 v224 = |
||
+ | case v224 of |
||
+ | [] -> [] |
||
+ | (:) v225 v226 -> (:) (v223 v225) (Sample.map2 v223 v226) |
||
+ | |||
+ | Sample.test v227 = Sample.map2 Sample.head2 v227 |
||
+ | </haskell> |
||
+ | |||
+ | Note that all names have been fully qualified, there are no infix operators, all pattern matches have been converted to cases. |
||
+ | |||
+ | == Some little samples == |
||
+ | |||
+ | === Hello World, for Core === |
||
+ | |||
+ | The following snippet loads a Core file and prints it out. |
||
+ | |||
+ | <haskell> |
||
+ | import Yhc.Core |
||
+ | |||
+ | showFile :: FilePath -> IO () |
||
+ | showFile x = loadCore x >>= print |
||
+ | </haskell> |
||
+ | |||
+ | === The linker === |
||
+ | |||
+ | Since all Core programs are fully qualified, linking is really easy: |
||
+ | |||
+ | <haskell> |
||
+ | import Yhc.Core |
||
+ | |||
+ | linker :: [Core] -> Core |
||
+ | linker xs = foldr f (Core "" [] [] []) xs |
||
+ | where f (Core _ _ x1 x2) (Core _ _ y1 y2) = Core "" [] (x1++y1) (x2++y2) |
||
+ | </haskell> |
||
+ | |||
+ | Here the linker ignores the import statements and the module name, of course you can do linking driven by the import statements easily. |
||
+ | |||
+ | Note: The <code>--linkcore</code> option in Yhc does automatic linking |
||
+ | |||
+ | === SHOUT AT EVERYONE === |
||
+ | |||
+ | How do you change all strings and characters into uppercase? |
||
+ | |||
+ | <haskell> |
||
+ | import Yhc.Core |
||
+ | |||
+ | shout :: Core -> Core |
||
+ | shout core = transformCore f core |
||
+ | where |
||
+ | f (CoreChr x) = CoreChr (toUpper x) |
||
+ | f (CoreStr x) = CoreStr (map toUpper x) |
||
+ | f x = x |
||
+ | </haskell> |
||
+ | |||
+ | === The 42 counter === |
||
+ | |||
+ | How many of your functions contain the literal 42? How many times does it occur per function? |
||
+ | |||
+ | <haskell> |
||
+ | import Yhc.Core |
||
+ | |||
+ | main x = putStr $ unlines [name ++ ": " ++ show count | (name,count) <- count42 x] |
||
+ | |||
+ | count42 :: Core -> [(String,Int)] |
||
+ | count42 core = [(name, n) | func@(Func name _ _) <- coreFuncs core, |
||
+ | let n = length $ filter is42 $ universeCore func, n /= 0] |
||
+ | |||
+ | is42 :: CoreExpr -> Bool |
||
+ | is42 (CoreInt 42) = True |
||
+ | is42 (CoreInteger 42) = True |
||
+ | is42 _ = False |
||
+ | </haskell> |
||
+ | |||
+ | == Invariants == |
||
+ | |||
+ | There are many invariants that hold in a Yhc Core program, and some that usually hold but aren't actually true. This secion lists both types. |
||
+ | |||
+ | === Primitives are saturated === |
||
+ | |||
+ | Are all primitives called saturated? I don't know... |
||
+ | |||
+ | === Let ''is'' recursive === |
||
+ | |||
+ | Most of the time the <code>let</code> in Core is non recursive, for example: |
||
+ | |||
+ | <haskell> |
||
+ | main = let f True = False |
||
+ | f False = f True |
||
+ | in print $ f False |
||
+ | </haskell> |
||
+ | |||
+ | generates: |
||
+ | |||
+ | <haskell> |
||
+ | Main.main = |
||
+ | (Prelude.$) |
||
+ | (Prelude.print Prelude.Prelude.Show.Prelude.Bool) |
||
+ | (Main.Main.Prelude.195.f Prelude.False) |
||
+ | |||
+ | Main.Main.Prelude.195.f v205 = |
||
+ | case v205 of |
||
+ | Prelude.True -> Prelude.False |
||
+ | Prelude.False -> Main.Main.Prelude.195.f Prelude.True |
||
+ | </haskell> |
||
+ | |||
+ | Note how the recursive <code>let</code> has been expanded out. |
||
+ | |||
+ | However, there are a few places this isn't true - <tt>Prelude.repeat</tt> and <tt>Prelude.cycle</tt> are similar to: |
||
+ | |||
+ | <haskell> |
||
+ | repeat x = xs where xs = x : xs |
||
+ | </haskell> |
||
+ | |||
+ | And this desugars to: |
||
+ | <haskell> |
||
− | module FibMain where |
||
+ | Main.rep v212 = |
||
+ | let Main.Main.Prelude.196.xs = |
||
+ | (Prelude.:) v212 Main.Main.Prelude.196.xs |
||
+ | in Main.Main.Prelude.196.xs |
||
+ | </haskell> |
||
+ | where the <code>let</code> binding ''is'' recursive. |
||
− | main xs = pam daeh xs |
||
+ | === Oversaturation ''is'' possible in Core === |
||
− | daeh (x:xs) = x |
||
+ | Consider this Haskell code |
||
− | pam f [] = [] |
||
− | pam f (x:xs) = f x : pam f xs |
||
+ | <haskell> |
||
− | You get the output |
||
+ | let g = fst tup |
||
+ | x = g (5::Int) (6::Int) |
||
+ | </haskell> |
||
+ | This desugars to: |
||
− | $ yhc -core FibMain.hs |
||
− | ====== Human Readable Core: |
||
− | FibMain.pam v220 v221 = |
||
− | case v221 of |
||
− | Prelude.[] -> (Prelude.[]) |
||
− | Prelude.: v222 v223 -> |
||
− | (Prelude.: (YHC.Internal._apply1 v220 v222) (FibMain.pam v220 v223)) |
||
+ | <haskell> |
||
− | FibMain.daeh v224 = |
||
+ | let Bug.Bug.Prelude.217.g = -- arity = 0 |
||
− | case v224 of |
||
− | + | let v285 = Prelude.Prelude.Num.Prelude.Integer |
|
+ | in Prelude.fst (Bug.tup v285) |
||
− | _ -> (Prelude.error (LAMBDA228)) |
||
+ | in let Bug.Bug.Prelude.218.x = Bug.Bug.Prelude.217.g 5 6 -- called with 2 arguments |
||
+ | </haskell> |
||
+ | There can be two solutions to this: |
||
− | LAMBDA228 = |
||
− | (prim_STRING "FibMain: Pattern match failure in function at 7:1-7:15.") |
||
+ | * evaluate <code>g</code> as soon as it is ready (i. e. before application to <code>5 6</code>): this may eliminate some laziness |
||
− | FibMain.main v227 = (FibMain.pam FibMain.daeh v227) |
||
+ | * take care of oversaturating arguments by storing them until <code>x</code> is to be evaluated, and evaluate <code>g</code> right before <code>x</code>: this preserves laziness |
||
+ | An example how the second solution can be implemented in Javascript, see this [[Yhc/Javascript#Oversaturation|section]] of the '''ycr2js''' page. |
||
− | The <tt>-core</tt> option gives human readable Core output, in a style very similar to Haskell. The <tt>-corep</tt> option gives a <tt>deriving Show</tt> output of the Core, which can be read back in with <tt>read</tt> very easily. The machine Core also contains source code locations for statements. |
||
− | == |
+ | == See also == |
+ | * [http://www.haskell.org/ghc/docs/latest/html/users_guide/ext-core.html GHC Core] |
||
− | * '''Types''' - Yhc has none, GHC has lots. |
||
− | * '''Familiarity''' - Yhc looks like Haskell, GHC is somewhat related, but not as close. |
||
− | * '''Name mangling''' - Yhc preserves names much better. |
||
− | * '''Source locations''' - Yhc keeps these, GHC doesn't. |
||
== Users == |
== Users == |
||
− | * [http://www-users.cs.york.ac.uk/~ndm/projects/catch.php Catch] - Case |
+ | * [http://www-users.cs.york.ac.uk/~ndm/projects/catch.php Catch] - Case Totality Checker for Haskell by [[User:NeilMitchell|Neil Mitchell]]. This takes Core as an input. |
* [http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php Dr Haskell] - give hints to beginners about useful Haskell functions/idioms. |
* [http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php Dr Haskell] - give hints to beginners about useful Haskell functions/idioms. |
||
+ | * [[Yhc/Javascript|ycr2js]] - a Core to Javascript translator. |
Latest revision as of 14:20, 22 September 2007
Part of Yhc |
Yhc Core is a way of dumping and using the internal representation of Yhc in an external project.
Haddock documentation
Overview
Yhc.Core is a simple core Haskell-like language, feature case statements, let statements, top level lambda's and data values. Much of the syntactic sugar present in Haskell has gone (list comprehensions, typeclasses, overloaded names, nested lambdas)
The strengths of Yhc.Core are:
- Simple representation of Haskell
- Relatively simple to relate Core to original Haskell
- Source locations are preseved
- Minimal name mangling
- Few syntactic forms
The weaknesses are:
- Yhc cannot compile Yhc Core files, format is write only (fix is being worked on)
- Types are not present (hard to fix, a lot of work)
The intended users:
- Analysis tools
- Compiler backends
Generating Core
Yhc Core files are stored as .ycr files in a binary format. They can be generated by passing the --core
flag to the compiler:
yhc --core Main.hs
If you want all definitions from all libraries included in then:
yhc --linkcore Main.hs
To view the Core output, yhc Main --showcore
, with the output going to the screen in a pretty printed format. To view an existing Core file, yhc --viewcore File.ycr
.
The Core output
For an example of the Core output, taking the following program:
head2 (x:xs) = x
map2 f [] = []
map2 f (x:xs) = f x : map2 f xs
test x = map2 head2 x
Generates:
Sample.head2 v220 =
case v220 of
(:) v221 v222 -> v221
_ -> Prelude.error Sample._LAMBDA228
Sample._LAMBDA228 =
"Sample: Pattern match failure in function at 9:1-9:15."
Sample.map2 v223 v224 =
case v224 of
[] -> []
(:) v225 v226 -> (:) (v223 v225) (Sample.map2 v223 v226)
Sample.test v227 = Sample.map2 Sample.head2 v227
Note that all names have been fully qualified, there are no infix operators, all pattern matches have been converted to cases.
Some little samples
Hello World, for Core
The following snippet loads a Core file and prints it out.
import Yhc.Core
showFile :: FilePath -> IO ()
showFile x = loadCore x >>= print
The linker
Since all Core programs are fully qualified, linking is really easy:
import Yhc.Core
linker :: [Core] -> Core
linker xs = foldr f (Core "" [] [] []) xs
where f (Core _ _ x1 x2) (Core _ _ y1 y2) = Core "" [] (x1++y1) (x2++y2)
Here the linker ignores the import statements and the module name, of course you can do linking driven by the import statements easily.
Note: The --linkcore
option in Yhc does automatic linking
SHOUT AT EVERYONE
How do you change all strings and characters into uppercase?
import Yhc.Core
shout :: Core -> Core
shout core = transformCore f core
where
f (CoreChr x) = CoreChr (toUpper x)
f (CoreStr x) = CoreStr (map toUpper x)
f x = x
The 42 counter
How many of your functions contain the literal 42? How many times does it occur per function?
import Yhc.Core
main x = putStr $ unlines [name ++ ": " ++ show count | (name,count) <- count42 x]
count42 :: Core -> [(String,Int)]
count42 core = [(name, n) | func@(Func name _ _) <- coreFuncs core,
let n = length $ filter is42 $ universeCore func, n /= 0]
is42 :: CoreExpr -> Bool
is42 (CoreInt 42) = True
is42 (CoreInteger 42) = True
is42 _ = False
Invariants
There are many invariants that hold in a Yhc Core program, and some that usually hold but aren't actually true. This secion lists both types.
Primitives are saturated
Are all primitives called saturated? I don't know...
Let is recursive
Most of the time the let
in Core is non recursive, for example:
main = let f True = False
f False = f True
in print $ f False
generates:
Main.main =
(Prelude.$)
(Prelude.print Prelude.Prelude.Show.Prelude.Bool)
(Main.Main.Prelude.195.f Prelude.False)
Main.Main.Prelude.195.f v205 =
case v205 of
Prelude.True -> Prelude.False
Prelude.False -> Main.Main.Prelude.195.f Prelude.True
Note how the recursive let
has been expanded out.
However, there are a few places this isn't true - Prelude.repeat and Prelude.cycle are similar to:
repeat x = xs where xs = x : xs
And this desugars to:
Main.rep v212 =
let Main.Main.Prelude.196.xs =
(Prelude.:) v212 Main.Main.Prelude.196.xs
in Main.Main.Prelude.196.xs
where the let
binding is recursive.
Oversaturation is possible in Core
Consider this Haskell code
let g = fst tup
x = g (5::Int) (6::Int)
This desugars to:
let Bug.Bug.Prelude.217.g = -- arity = 0
let v285 = Prelude.Prelude.Num.Prelude.Integer
in Prelude.fst (Bug.tup v285)
in let Bug.Bug.Prelude.218.x = Bug.Bug.Prelude.217.g 5 6 -- called with 2 arguments
There can be two solutions to this:
- evaluate
g
as soon as it is ready (i. e. before application to5 6
): this may eliminate some laziness - take care of oversaturating arguments by storing them until
x
is to be evaluated, and evaluateg
right beforex
: this preserves laziness
An example how the second solution can be implemented in Javascript, see this section of the ycr2js page.
See also
Users
- Catch - Case Totality Checker for Haskell by Neil Mitchell. This takes Core as an input.
- Dr Haskell - give hints to beginners about useful Haskell functions/idioms.
- ycr2js - a Core to Javascript translator.