Most functional compiler

https://www.ioccc.org/2019/lynn/hint.html [www.ioccc.org]

2019-10-14 21:19

tags:
c
compiler
haskell
programming

One-letter variable names abound in IOCCC entries, and for good reason. These tiny pieces of confetti are hard to read, and leave room for more code. Then why not go further and use zero-letter variable names? That is, tacit programming or point-free style.

I had been playing with an algorithm devised by Oleg Kiselyov that effortlessly and efficiently eliminates those pesky variables, leaving behind terms composed from a small set of combinators. No need for lambda lifting or supercombinators.

By adding a handful of lines of mostly parsing code, we get a Haskell compiler, or rather, a compiler that accepts a subset of Haskell sufficiently large to self-host. You might say I wrote a tool for this contest, then ran it on itself to make an entry for it.

Also: https://crypto.stanford.edu/~blynn/compiler/ioccc.html

And more: https://www.ioccc.org/years.html#2019

source: HN

Open Season on Hylomorphisms

https://bartoszmilewski.com/2018/12/20/open-season-on-hylomorphisms/ [bartoszmilewski.com]

2018-12-23 20:00

tags:
cxx
functional
haskell
programming

This piece of code is probably unreadable to a regular C++ programmer, but makes perfect sense to a Haskell programmer.

Here’s the description of the problem: You are given a list of equal-length strings. Every string is different, but two of these strings differ only by one character. Find these two strings and return their matching part. For instance, if the two strings were “abcd” and “abxd”, you would return “abd”.

What makes this problem particularly interesting is its potential application to a much more practical task of matching strands of DNA while looking for mutations. I decided to explore the problem a little beyond the brute force approach. And, of course, I had a hunch that I might encounter my favorite wild beast–the hylomorphism.

Running from the past

http://blog.sigfpe.com/2018/10/running-from-past.html [blog.sigfpe.com]

2018-11-15 17:36

tags:
compsci
functional
haskell
math
random

Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It’s a change of perspective that can have a big impact on how we reason about our code. But it’s also a change of perspective that can be useful in mathematics and I’d like to give an example: a really beautiful technique that alows you to sample from the infinite limit of a probability distribution without needing an infinite number of operations.

source: trivium

Free Monoid from Free Algebra

https://bartoszmilewski.com/2018/07/30/free-monoid-from-free-algebra-part-1/ [bartoszmilewski.com]

2018-08-07 03:04

tags:
compsci
haskell
math

In my previous blog post I used, without proof, the fact that the initial algebra of the functor I + h \otimes - is a free monoid. The proof of this statement is not at all trivial and, frankly, I would never have been able to work it out by myself.

I worked my way through this proof, filling some of the steps that might have been obvious to a mathematician, but not to an outsider. I even learned how to draw diagrams using the TikZ package for LaTeX.

Part two: https://bartoszmilewski.com/2018/07/30/free-monoid-from-free-algebra-part-2/

Linear Haskell: Practical linearity in a higher-order polymorphic language

https://blog.acolyer.org/2018/01/24/linear-haskell-practical-linearity-in-a-higher-order-polymorphic-language/ [blog.acolyer.org]

2018-02-01 09:25

tags:
compsci
haskell
paper
programming
type-system

The paper is focused around two main use cases for linear types. The one that really catches my imagination is encoding the usage protocol of a resource (e.g., you can’t read from a file before it is opened) in types. “Here, linearity does not affect efficiency, but rather eliminates many bugs.” We’ll return to some examples of this later in this post. It seems like there’s a very nice and natural fit to protocols in distributed systems (a bit like we looked at with Disel yesterday).

The second use case is safe update in place, and the reason we’re interested in that is efficiency – if we know it’s safe to update a value in place we don’t need to worry about making copies, or mutual exclusion mechanisms.

Stalking a Hylomorphism in the Wild

https://bartoszmilewski.com/2017/12/29/stalking-a-hylomorphism-in-the-wild/ [bartoszmilewski.com]

2018-01-02 22:34

tags:
functional
haskell
programming
type-system

Trying to improve my Haskell coding skills, I decided to test myself at solving the 2017 Advent of Code problems. It’s been a lot of fun and a great learning experience. One problem in particular stood out for me because, for the first time, it let me apply, in anger, the ideas I learned from category theory. But I’m not going to talk about category theory this time, just about programming.

Although saying “just programming” may be a bit modest.

Writing a Formally-Verified Porn Browser in Coq and Haskell

http://www.michaelburge.us/2017/08/25/writing-a-formally-verified-porn-browser-in-coq.html [www.michaelburge.us]

2017-08-27 01:12

tags:
compsci
development
functional
haskell
programming
type-system

Hopefully this example shows that there’s nothing really stopping anyone from using Coq in their Haskell programs today.

source: L

Writing a SAT Solver

http://andrew.gibiansky.com/blog/verification/writing-a-sat-solver/ [andrew.gibiansky.com]

2017-06-21 20:29

tags:
compsci
haskell
programming

In this post, we’ll look at how to teach computers to solve puzzles. Specifically, we’ll look at a simple puzzle that can be expressed as a boolean constraint satisfaction problem, and we’ll write a simple constraint solver (a SAT solver) and mention how our algorithm, when augmented with a few optimizations, is used in modern SAT solvers.

source: danluu

Escaping Hell with Monads

https://philipnilsson.github.io/Badness10k/posts/2017-05-07-escaping-hell-with-monads.html [philipnilsson.github.io]

2017-05-21 15:57

tags:
haskell
intro-programming
type-system

Could be some other solutions not mentioned, but a decent comparative demonstration.

source: L

Linear types make performance more predictable

http://blog.tweag.io/posts/2017-03-13-linear-types.html [blog.tweag.io]

2017-03-14 18:49

tags:
beta
compiler
compsci
food
haskell
paper
perf
programming
type-system

Linear logic had two of everything: two ways of building conjunctions and disjunctions, two notions of truth, falsehood and two ways to negate. It’s a strange system, but perhaps not moreso than the zoo of cute names and symbols Girard conferred to every construct. For the purposes of this post, we’ll only need one new symbol from this zoo: ⊸, which reads lollipop

source: L

Applicative Functors

https://bartoszmilewski.com/2017/02/06/applicative-functors/ [bartoszmilewski.com]

2017-02-07 14:50

tags:
compsci
haskell
type-system

Unlike monads, which came into programming straight from category theory, applicative functors have their origins in programming.

But are otherwise equally nonsensical...

Haskell Pitfalls

http://lorepub.com/post/2016-12-17-Haskell-Pitfalls [lorepub.com]

2016-12-21 00:35

tags:
development
haskell
programming

Don’t use the bad functions.

Concurrency and Node

https://www.fpcomplete.com/blog/2016/12/concurrency-and-node [www.fpcomplete.com]

2016-12-08 18:55

tags:
concurrency
haskell
javascript
perf
programming

The short version is that despite concurrent IO, JavaScript remains single threaded, limiting computation. Haskell does things differently.

GHC optimization and fusion

https://www.stackbuilders.com/tutorials/haskell/ghc-optimization-and-fusion/ [www.stackbuilders.com]

2016-11-30 20:13

tags:
haskell
perf

Rewrite critical bits in C.

^ Not actually a fair summary.

Monads: Programmer's Definition

https://bartoszmilewski.com/2016/11/21/monads-programmers-definition/ [bartoszmilewski.com]

2016-11-23 00:53

tags:
functional
haskell
programming
series
type-system

Programmers have developed a whole mythology around monads.

What they do vs what they are.

Haskell's Missing Concurrency Basics

http://www.snoyman.com/blog/2016/11/haskells-missing-concurrency-basics [www.snoyman.com]

2016-11-16 21:53

tags:
concurrency
functional
haskell
programming

The midnight Monad

http://www.lambdacat.com/the-midnight-monad-a-journey-to-enlightenment/ [www.lambdacat.com]

2016-11-16 03:02

tags:
functional
haskell
intro-programming
type-system

Functor, Applicative, Monad, Enlightenment. It’s all about the fame.