sdiehl / write-you-a-haskell Goto Github PK
View Code? Open in Web Editor NEWBuilding a modern functional compiler from first principles. (http://dev.stephendiehl.com/fun/)
License: MIT License
Building a modern functional compiler from first principles. (http://dev.stephendiehl.com/fun/)
License: MIT License
The data types given for the example abstract syntax:
type Name = String
data Expr
= Var Name
| Lit Name
| Op PrimOp [Expr]
| Let Name [Name] Expr
data Lit
= LitInt Int
does not match the value given later:
Let "f" ["x"] (Op Add [Var "x", Lit (LitInt 1)])
Specifically Lit (LitInt 1)
.
Thank you for your great work :-)
The following line's "λ" can be displayed in HTML, but can not be displayed correctly in PDF.
(Please ignore if my environment dependent)
003_lambda_calculus.md, line 358 (at pdf p.50):
maybe
The following lines' "λ" and "≡" can be displayed in HTML, but can not be displayed correctly in PDF.
005_evaluation.md, line 84 (at pdf p.69)
(\x. \y. y x) (2 + 2) λx. x + 1
005_evaluation.md, line 173 (at pdf p.71)
=> (\y.y (2 + 2)) λx. x + 1
006_hindley_milner.md, line 1286 (at pdf p.101)
λ: main
007_path.md, line 272-277 (at pdf p.109)
λ> id (1+2)
3
λ> :type (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b
λ> :set -ddump-rn
λ> :load test.fun
007_path.md, line 1235 (at pdf p.126)
f <=< g ≡ \x -> g x >>= f
(Because not yet been able to environment, sorry in this way)
I have just started reading it, but noticed that there have been no new commits since October. I would absolutely love to see this book completed!
I'm not sure if it
is a feature or an implementation artefact, but the user can find it with :browse
and using it leads to trouble:
Poly> 1
1 : Int
Poly> :browse
it : Int
Poly> it+it
4 : Int
Poly> it==it
poly: Pattern match failure in do expression at Eval.hs:39:5-11
In the Parsing section, http://dev.stephendiehl.com/fun/parsers.html, you write "Recall that in Haskell in the String type is itself defined to be a list of Char values...", but you write it as a list of String values. That section should have single quotes instead:
"1+2*3"
['1','+', '2', '*', '3']
l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$ stack build
write-you-a-haskell-0.1.0.0: build (exe)
Preprocessing executable 'write-you-a-haskell' for
write-you-a-haskell-0.1.0.0...
Cabal-simple_mPHDZzAJ_1.22.5.0_ghc-7.10.3: can't find source for Main in .
-- While building package write-you-a-haskell-0.1.0.0 using:
/home/l/.stack/setup-exe-cache/x86_64-linux-nopie/Cabal-simple_mPHDZzAJ_1.22.5.0_ghc-7.10.3 --builddir=.stack-work/dist/x86_64-linux-nopie/Cabal-1.22.5.0 build exe:write-you-a-haskell --ghc-options " -ddump-hi -ddump-to-file"
Process exited with code: ExitFailure 1
l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$
In the Lambda Calculus chapter, under Substitution, there's first an explanation that in ((\x.e)a)
x
is replaced by a
in e
, also written as [x/a]e
.
This is immediately followed by (\a.e)x -> [x/a]e
which seems like the reverse of what's above to me.
Assuming the second notation is correct (so [x/a]e
means 'occurrences of a
in e
are substituted by x
', or ((\a.e)x)
), the next example seems not to be in line: [y/x](\y.yx)
would be 'occurrences of x
in (\y.yx)
are substituted by y
, or (\y.yy)
, unlike the text which says (\x.xx)
, which is equivalent but could be confusing.
Overall: it might be just me but I believe there might be some inconsistencies in those paragraphs. I'd love to send a PR to fix, but I don't know what the proper fix would be.
Although a strong familiarity with monads, monad transformers ...
The Evaluation chapter contains this sentence:
We will use the evaluation technique Ly extensively
What does this Ly
refer to?
This is not parsed in the expected way in poly and poly_constraints:
(\f -> f 0 + f 1)
(\f -> if f 0 then f 1 else f 2)
It works with parens around the function applications.
Add test cases to test.ml
for pathological cases on pull request #40 issue
I am working through your wonderful "Write you a Haskell" tutorial, thanks a lot for creating it in the first place.
I have downloaded and compiled the code for chapter 4 (the untyped lambda calculus).
Contrary to the explanations in the text, SKK does not reduce to I in my case, instead I get:
Untyped> (\x y z. x z (y z)) (\x y . x) (\x y . x)
=> \x y z . (x z (y z))
=> \x y . x
=> \x y z . (x z (y z)) (\x y . x)
=> \x y . x
<<closure>>
Untyped>
Recall, that according to the text on page 50 I should see something along the lines of:
Untyped> (\x y z. x z (y z)) (\x y . x) (\x y . x)
=> \x y z . (x z (y z))
=> \y z . ((\x y . x) z (y z))
=> \x y . x
=> \y . z
=> z
=> \z . z
\z . z
I wonder what's going on? Cannot be a huge thing, as the data structures / code base
is relatively small at this point.
Nevertheless, as SKK=I is supposed to be a kind of litmus test, I would like to
get this fixed.
A few more explanations for what's going on in detail in Eval.hs would also be nice
(VClosure, Scope, type Eval = WriterT [Step](State EvalState) a, inc, red, etc)
Thanks.
Chapter 6 in the section "Polymorphism" claims that it is impossible to write a function of type (a -> b) -> f a -> f b
that doesn't satisfy forall f g. fmap f . fmap g = fmap (f . g)
. But this is false:
data F a = A a | B a
bad_fmap f (A x) = B (f x)
bad_fmap f (B x) = A (f x)
A result you do get from the free theorem for fmap
is that fmap id = id <==> forall f g. fmap f . fmap g = fmap (f . g)
; that is, if your fmap
satisfies one of the two functors laws then it necessarily satisfies the other one too. The above example satisfies neither.
I guess the text is formally correct (although it can be more precise) but the example is completely misleading: capture might happen if we do substitution under a lambda but in the example substitution comes from the beta-reduction and after the reduction lambda is gone! There is actually nothing bad to have that x in \FV{a}, for example: (\x. x) x -> x. On the other hand, bad things still might happen even if we check x \notin \FV{a}, for example: (\x. \y. xy) y -> \y. yy (capture!).
In fact, our substitution is defined to be capture-avoiding in the first place (condition in the last line of the definition ensures that), we probably just need an explanation that if the condition is not met it's always possible to alpha-convert the term such that substitution will be possible.
In the Parsers chapter, under Lexer, lexer
is defined as Tok.makeTokenParser emptyDef
. Shouldn't this be Tok.makeTokenParser langDef
, using the definition of langDef
given above it?
MacOS Catalina 10.15.5, GHC-8.8.3, Stack-2.3.1, current LaTeX (MacTeX-2020):
$ stack exec make
pandoc -c css/style.css --filter includes.hs --template template.html -s -f markdown -t html --standalone --toc --toc-depth=2 --mathjax="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" --highlight-style pygments -o 000_introduction.html 000_introduction.md
includes.hs:6:1: error:
Could not find module ‘Text.Pandoc’
Perhaps you meant Text.Parsec (from parsec-3.1.14.0)
Use -v (or `:set -v` in ghci) to see a list of the files searched for.
|
6 | import Text.Pandoc
| ^^^^^^^^^^^^^^^^^^
includes.hs:10:1: error:
Could not find module ‘Text.Pandoc.JSON’
Use -v (or `:set -v` in ghci) to see a list of the files searched for.
|
10 | import Text.Pandoc.JSON
| ^^^^^^^^^^^^^^^^^^^^^^^
includes.hs:11:1: error:
Could not find module ‘Text.Pandoc.Walk’
Use -v (or `:set -v` in ghci) to see a list of the files searched for.
|
11 | import Text.Pandoc.Walk
| ^^^^^^^^^^^^^^^^^^^^^^^
Error running filter includes.hs:
Filter returned error status 1
make: *** [000_introduction.html] Error 83
$ stack --version
Version 2.3.1, Git revision de2a7b694f07de7e6cf17f8c92338c16286b2878 (8103 commits) x86_64 hpack-0.33.0
$ pandoc --version
pandoc 2.9.2.1
Compiled with pandoc-types 1.20, texmath 0.12.0.2, skylighting 0.8.4
Default user data directory: /Users/ur20980/.local/share/pandoc or /Users/ur20980/.pandoc
Copyright (C) 2006-2020 John MacFarlane
Web: https://pandoc.org
This is free software; see the source for copying conditions.
There is no warranty, not even for merchantability or fitness
for a particular purpose.
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.8.3
It would be great if you could help getting this book compiled/built. Thanks!
Rewrite poly text to reflect changes made in pull request #37
The Substitutable
instance for Type
is currently defined as follows:
instance Substitutable Type where
apply _ (TCon a) = TCon a
apply s t@(TVar a) = Map.findWithDefault t a s
apply s (t1 `TArr` t2) = apply s t1 `TArr` apply s t2
I believe the TVar
case is incomplete. Consider the following substitution:
x <- y
y <- Int
If we apply this substitution to type variable x
, we obtain y
, when we should obtain Int
. I think this case should instead recursively apply the substitution to the type found in the map.
I dont think this typechecks
https://github.com/sdiehl/write-you-a-haskell/blob/master/004_type_systems.md#small-step-semantics
-- Evaluate a single step.
eval1 :: Expr -> Maybe Expr
eval1 expr = case expr of
Succ t -> Succ <$> (eval1 t)
Pred Zero -> Just Zero
Pred (Succ t) | isNum t -> Just t
Pred t -> Pred <$> (eval1 t)
IsZero Zero -> Just Tr
IsZero (Succ t) | isNum t -> Just Fl
IsZero t -> IsZero <$> (eval1 t)
If Tr c _ -> Just c
If Fl _ a -> Just a
If t c a -> (\t' -> If t' c a) <$> eval1 t
_ -> Nothing
I think the expression variables and type variables have been mistakenly exchanged
This project is great. Is there any say I can show my gratitude (such as gratipay.com).
Hello!
I'm improving my knowledge in Haskell as the tutorial goes.
I followed the chapter 3 and looked the source in the repo.
The Main.hs file has a call to a function called ppexpr
, that is defined in Pretty.hs.
The Pretty.hs
has this line of code:
import Type
When I try to build it, GHC give me this error:
Could not find module `Type'
It is a member of the hidden package `ghc-7.8.3'.
By the name, it seems like it is some module WE would create, not a GHC Type
module, but anyway, in my .cabal file, I added the line ghc >= 7.8.3
, and everything blew up:
Warning: This package indirectly depends on multiple versions of the same
package. This is highly likely to cause a compile failure.
package ghc-7.8.3 requires transformers-0.3.0.0
package mtl-2.2.1 requires transformers-0.4.2.0
package haskeline-0.7.1.3 requires transformers-0.4.2.0
package Compiler-1.0.0.2 requires transformers-0.4.2.0
Seems like GHC wants a different version of the package. This is strange...
How could I solve this?
Great job anyway! If someday I complete the whole tutorial, if I have time, I could translate it to Portuguese ;)
Hi, I've just manually converted the pdf into Ebook + AZW3 formats.
It's not using the script but there seemed to be interest to these formats so wondered if I should make adjustments to the menu and add 2 extra links?
but I assume you wouldn't want the file living on the repo as they are about 3mb in total! 🤔
Here is a zip of them both
edit: the Epub version was the wrong one! (reuploaded)
Thank you for you excellect book.
Could you generate an epub version of the book, that will be really helpful for portability ;)
I think the chapter on Hindley-Milner type inference needs to be pushed, the website has this code:
newtype TypeEnv = TypeEnv (Map.Map Var Scheme)
Whereas the chapter in git has this:
newtype TypeEnv = TypeEnv (Map.Map Name Scheme)
Thanks!
When attempting to run the type checker on the example given in the repo with factorial, I run into a typechecker error:
Poly> let fact = fix (\fact -> \n -> if (n == 0) then 1 else ( n * ( fact (n-1) ) ) )
Cannot unify types:
Int
with
Int -> d
According to the book this should spit out the correct type.
The Evaluation chapter says
This value will be passed off to Haskell and reified into real world effects.
I believe this is somewhat confusing. In my understanding, that value is not reified into real world effects. On the contrary, it is a reification of real world effects, which can then be interpreted to actually cause those effects.
Or am I misunderstanding the concept of reification?
l@DESKTOP-82FI76C:/mnt/c/Users/zhiwei/Documents/write-you-a-haskell$ stack exec make epub
pandoc --filter includes.hs -f markdown --standalone --toc --toc-depth=2 --mathjax="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" --highlight-style pygments --epub-cover-image=img/cover-kindle.jpg -o WYAH.epub title.md 0*.md
pandoc: Error running filter includes.hs
includes.hs: createProcess: runInteractiveProcess: exec: does not exist (No such file or directory)
Makefile:49: recipe for target 'epub' failed
make: *** [epub] Error 83
In the process of implementing my own compiler, I found an inconsistency between the implementation of type inference between the poly and poly_constraints compilers in chapter 7.
I believe it has to do with the constraint generation around the "let" construct. In particular, let polymorphism doesn't seem to behave consistently.
A simple term that exhibits the problem is
let f = let add = \a b -> a + b in add
"poly" reports the type of "f" as "int -> int -> int," as it should be
"poly_constraints" reports it has type "forall a b c. a -> b -> c", which is too general.
It looks like the RSS feed for this book is incomplete.
I've only recently learned sufficiently not-hand-wavy meaning of the word "powerful", which is if X is more powerful than Y then you can do some things with X that are not possible with Y.
However, it looks like I don't yet understand the meaning of the word "general". I would guess that "Applicatives are strictly less general than monads" means that there are more monads out there than applicatives, but the opposite is the case. Could you clarify?
In the Introduction, under 'Functional Compilers', the pipeline graphic says 'Compliation', which should be 'Compilation'.
I intended to send a simple PR for this, but the sources seems to be missing from this repository?
write-you-a-haskell/chapter3/parsec.hs
Lines 27 to 28 in ae73485
write-you-a-haskell/chapter3/parsec.hs
Line 34 in ae73485
Consider following expressions:
let const = \x -> (\y -> x);
let y = \y -> (let f = \x -> if x then True else False in const (f y) y;
The accurate type of f
is Bool -> Bool
but forall a . a -> Bool
was given by poly_constraints. The reason is that poly_constraints doesn't substitute type variables in constraints set when instantiate a type scheme with fresh variables. (i.e. there are still some constraints with a
although forall a . a -> a
has been instantiated by other fresh variables)
I think #90 from @jeffreyrosenbluth introduced a bug. At least, I think it was that commit.
Prior to this commit (ie. using #1e609fb), you can do something like the following:
Poly> 2 + 3
5 : Int
Now, I get the following:
Poly> 2 + 3
Cannot unify types:
Int
with
Int -> a
Weirdly, it works for the *
operator, but fails only for +
and -
:
I suspect there's something weird going on in the parser because:
Poly> 2 + x
"<stdin>" (line 1, column 5):
unexpected "x"
expecting digit
Poly> 2 * x
4 : Int
Paragraph 2, sentence 1 of http://dev.stephendiehl.com/fun/type_systems.html#type-systems
Fix poly inference for If/Op per comments in pull request #33 .
Poly> let not x = if x then False else True
Poly> \x -> if (not x) then x else (x+1)
<<closure>> : Int -> Int
Poly> let b2i x = if x then 1 else 0
Poly> \x -> (b2i x) + x
<<closure>> : Int -> Int
Poly> (\x -> (b2i x) + x) 0
poly: Pattern match failure in do expression at Eval.hs:58:5-12
My platform:
Ubuntu: 14.04
GHC: 7.8.4
cabal: 1.22.0.0
pandoc: 1.13.2
And all haskell related packages are installed with nix package manager.
When I tried to build the project, pandoc reported that
pandoc: Error running filter includes.hs fd:4: hPutBuf: resource vanished (Broken pipe) make: *** [000_introduction.html] Error 83
Please may the proprietary license be switched to one which respects the freedom of the readers?
In the REPL section of the Parsers section, there's a rather strange sentence (to me at least):
When the user pressed enters a EOF or sends a SIGQUIT to input, getInputLine will yield Nothing and can handle the exit logic.
I believe the first part, "the user pressed enters a EOF", needs some tweaking.
In chapter 4 the substitution application is written before the expression [x/a]e
except in the section titled "Conversion and Equivalences".
Really enjoying this, thanks for the hard work!
There's a typo in the lambda typing rule in Ch04 for the simply-typed LC. The types and the terms have been mixed up in the implication.
It reads
Γ, x : τ1 ⊢ e : τ2
-------------------
Γ ⊢ λx.τ2 : e1→e2
You probably meant
...
-------------------
Γ ⊢ λx.e : τ1→τ2
I was excited to see the introduction to modern Haskell as I find that it's very confusing to enter Haskell these days as many or most introductions doesn't actually match current practices (Text vs. String, cabal vs. plain GHC, etc). However, I was bewildered when the Cabal & Stack section didn't mention Stack. Is this merely waiting for someone to write it? At the very least, we should be able to toss in a paragraph with a pointer? (I haven't used it yet, so I'm a bad candidate to write it).
You ever going to finish this? I've been waiting for this for years.
Perhaps I'm doing something dumb, but I can't build any of the code (here is chapter7/poly but others don't build as well)
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.4
$ cabal --version
cabal-install version 1.22.0.0
using version 1.22.0.0 of the Cabal library
$ cabal install
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: poly-0.1.0.0 (user goal)
next goal: base (dependency of poly-0.1.0.0)
rejecting: base-4.7.0.2/installed-bfd... (conflict: poly => base>=4.6 && <4.7)
rejecting: base-4.7.0.2, 4.7.0.1, 4.7.0.0, 4.6.0.1, 4.6.0.0, 4.5.1.0, 4.5.0.0,
4.4.1.0, 4.4.0.0, 4.3.1.0, 4.3.0.0, 4.2.0.2, 4.2.0.1, 4.2.0.0, 4.1.0.0,
4.0.0.0, 3.0.3.2, 3.0.3.1 (global constraint requires installed instance)
Dependency tree exhaustively searched.
Note: when using a sandbox, all packages are required to have consistent
dependencies. Try reinstalling/unregistering the offending packages or
recreating the sandbox.
Is there a greater reason for not supporting GHC 7.8?
I'll preface this by saying that my knowledge of Haskell is intermediate at best, but the discussion on recursion seems to fall somewhere between misleading and wrong. Many recursive functions are not tail-recursive - the factorial example isn't, for instance. It's possible to transform function to be tail-recursive, but I would be surprised if such transformations are the default behavior of any Haskell compiler at -O0. I especially would hesitate to speculate on the implementation of recursion due to Haskell's laziness.
As a side note, the mutually recursive examples have extraneous semicolons.
Poly> let x=0 in x
"<stdin>" (line 1, column 11):
unexpected reserved word "in"
expecting letter or digit
Poly> (let f x = x in f 0)
"<stdin>" (line 1, column 8):
unexpected "x"
expecting "="
Poly> (let rec x = x in x)
Not in scope: "x"
fix
is a special syntactic form that has to be applied to an expression, I expected g fix x
not to parse. Instead, it is parsed as g (fix x)
.poly> 1 + 5
Cannot unify types:
Int
with
Int -> a
I think that the plus operator is not parsed correctly.
Stephen, wonderful work here!
The Untyped chapter includes a section on pretty printing but some of the material relating to pretty printing appears earlier, at the end of the Reduction section, and seems out of order.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.