Type Theory for All: The Goal of Science is to Communicate Ideas

 

Thank you to the crew at Type Theory for All for their thoughtful and well-prepared interview.

Haskell equations, thirty-eight years later

One night, while drifting off to sleep (or failing to), I solved a conundrum that has puzzled me since 1987.

Before Haskell there was Orwell. In Orwell equations were checked to ensure order is unimportant (similar to Agda today). When an equation was to match only if no previous equation applied, it was to be preceded by ELSE. Thus, equality on lists would be defined as follows:

    (==) :: Eq a => [a] -> [a] -> Bool
    [] == []          =  True
    (x:xs) == (y:ys)  =  x == y && xs == ys
    ELSE
    _ == _            =  False

We pondered whether to include this restriction in Haskell. Further, we wondered whether Haskell should insist that order is unimportant in a sequence of conditionals, unless ELSE was included. Thus, equality on an abstract type Shape would be defined as follows:

    (==) :: Shape -> Shape -> Bool
    x == y | circle x && circle y  =  radius x == radius y
           | square x && square y  =  side x == side y
    ELSE
           | otherwise             =  False

In Orwell and early Haskell, guards were written at the end of an equation and preceded by the keyword if or the end of an equation could be labelled otherwise. (Miranda was similar, but lacked the keywords.) Here I use the guard notation, introduced later by Paul Hudak, where otherwise is a variable bound to True.

Sometime two equations or two guards not separated by ELSE might both be satisfied. In that case, we thought the semantics should ensure that both corresponding right-hand sides returned the same value, indicating an error otherwise. Thus, the following:

    plus :: Thing -> Thing -> Thing
    plus x y | zero x     =  y
             | zero y     =  x
    ELSE
             | otherwise  =  ...

would be equivalent to:

    plus :: Thing -> Thing -> Thing
    plus x y | zero x && zero y && x == y    =  x
             | zero x && zero y && x /= y    =  error "undefined"
             | zero x && not (zero y)        =  y
             | not (zero x) && zero y        =  x
             | not (zero x) && not (zero y)  =  ...

Here the code checks that if x and y are both zero then they are the same. (I will consider a refinement to the check for sameness later.) Of course, the compiler would issue code that performs the tests zero x, zero y, and x == y at most once.

We didn’t pursue this design in Haskell for two reasons. First, because we thought it might be too unfamiliar. Second, because the ELSE on a line by itself was syntactically awkward. It would be especially annoying if one ever wanted the usual cascading behaviour:

    f :: Thing -> Thing
    f x | p x  =  ...
    ELSE
        | q x  =  ...
    ELSE
        | r x  =  ...

Here each guard is tested in turn, and we take the first that succeeds.

Today, the first problem is perhaps no longer quite so strong an issue. Many applications using Haskell would welcome the extra assurance from flagging any cases where order of the equations is significant. But the syntactic awkwardness of ELSE remains considerable. It was syntax about which I had an insight while tossing in bed.

Above otherwise is a variable bound to True in the standard prelude. But say we were to treat otherwise as a keyword, and to give it the meaning that the equation applies only if no previous equation applies, and to allow it to optionally be followed by a further guard. Then our first example becomes:

    (==) :: Eq a => [a] -> [a] -> Bool
    [] == []            =  True
    (x:xs) == (y:ys)    =  x == y && xs == ys
    _ == _ | otherwise  =  False

And our second example becomes:

    (==) :: Shape -> Shape -> Bool
    x == y | circle x && circle y  =  radius x == radius y
           | square x && square y  =  side x == side
           | otherwise             =  False

And our third example becomes:

    plus :: Thing -> Thing -> Thing
    plus x y | zero x     =  y
             | zero y     =  x
             | otherwise  =  ...

If one doesn’t want to invoke the equality test in the case that both zero x and zero y hold then one would instead write:

    plus :: Thing -> Thing -> Thing
    plus x y | zero x            =  y
             | otherwise zero y  =  x
             | otherwise         =  ...

Similarly, the cascading example becomes:

    f :: Thing -> Thing
    f x | p x            =  ...
        | otherwise q x  =  ...
        | otherwise r x  =  ...

That’s it! The syntactic awkwardness is greatly reduced.

The proposed notation depends upon Paul’s clever insight to move the guard from the end of the equation to the middle, so evaluation works strictly left to right. But we’ve had guards in that position for quite a while now. Goodness knows why none of us hit upon this proposal thirty-odd years ago.

Of course, the change is not backward compatible. Changes to guards could be made backward compatible (with added ugliness) by using a different symbol than ‘|’ to mark guards with the new semantics. But now the old definition of (==) should not be accepted without an otherwise, and I cannot think of how to introduce that new semantics with a backward compatible syntax.

The solution, as with so much of Haskell nowadays, is to activate the new semantics with a pragma. Manual porting of legacy code would not be hard in most cases, and it would also be easy to write a tool that adds otherwisewhenever the equations are not easily shown to be independent of order.

John Hughes suggests a further refinement to the above. Using equality to check that the value of two equations is the same may not be appropriate if the values are computed lazily. Instead, he suggests that the plus example should translates as follows:

    plus :: Thing -> Thing -> Thing
    plus x y | zero x && zero y              =  x `meet` y
             | zero x && not (zero y)        =  y
             | not (zero x) && zero y        =  x
             | not (zero x) && not (zero y)  =  ...

Here we presume a type class

    class Meet a where
      meet : a -> a -> a

which confirms that the two arguments are the same and returns a value that is the same as both the arguments. For strict data types, two arguments are the same if they are equal.

    instance Meet Integer where
      x `meet` y | x == y     =  x
                 | otherwise  =  error "undefined"

For lazy data types, we check that they are the meet lazily.

    instance Meet a => Meet [a] where
      [] `meet` []           =  []
      (x:xs) `meet` (y:ys)   =  (x `meet` y) :: (xs `meet` ys)
      meet _ _  | otherwise  =  error "undefined"

If the compiler could not verify that equations are disjoint, it would require that their right-hand sides have a type belonging to the class Meet.

In most cases, one would hope the compiler could verify that equations are disjoint, and hence would not have to resort to meet or additional checks. One might wish to allow a pragma to declare disjointness, permitting the compiler to assume, for instance, that x < y and x >= y are disjoint. An SMT solver could do much of the work of checking for disjointness.

In general, equations not separated with otherwise would be checked to ensure they are disjoint or all give equivalent results. For example,

    g :: Thing -> Thing
    g x | p x             =  a x
        | q x             =  b x
        | otherwise r x   =  c x
        | s x             =  d x
        | otherwise t x   =  e x

would be equivalent to

    g :: Thing -> Thing
    g x | p x && q x              =  a x `meet` b x
        | p x && not (q x)        =  a x
        | q x && not (p x)        =  b x
        | otherwise r x && s x    =  c x `meet` d x
        | r x && not (s x)        =  c x
        | s x && not (r x)        =  d x
        | otherwise t x           =  e x

On the other hand, if we declared that p x and q x are disjoint, and the same for s x and r x, then the first code would instead compile to something equivalent to Haskell’s current behaviour,

    g :: Thing -> Thing
    g x | p x             =  a x
        | otherwise q x   =  b x
        | otherwise r x   =  c x
        | otherwise s x   =  d x
        | otherwise t x   =  e x

One drawback of this proposal is that the source code doesn’t directly indicate when extra tests and the use of meet are required. An IDE might provide feedback to make explicit which tests are performed, or one might also add pragmas or additional syntax to reflect that information in the source.

I hope some reader might be keen to take this forward. What do you think?

How to market Haskell to a mainstream programmer

An intriguing talk by Gabriella Gonzalez, delivered at Haskell Love 2020. Based largely on the famous marketing book, Crossing the Chasm. Gonzalez argues that marketing is not about hype, it is about setting priorities: what features and markets are you going to ignore? The key to adoption is to be able to solve a problem that people need solved today and where existing mainstream tools are inadequate. Joe Armstrong will tell you that the key to getting Erlang used was to approach failing projects and ask "Would you like us to build you a prototype?" Gonzalez makes a strong case that Haskell should first aim to capture the interpreters market. He points out that the finance/blockchain market may be another possibility. Recommended to me at Lambda Days by Pedro Abreu, host of the Type Theory Forall podcast.

Help, please! Do you know any applications of my work?

When writing an application, it sometimes help if I can point out that monads and type classes, which my research contributed to, are used to process every post on Facebook. (Via Haxl. Thanks, Simon Marlow!)

Do you know of other applications of my work? If so, please email me or list them in the comments. (You can find my email at the bottom of my home page.)

Possible example: I gather Twitter uses monads and implicits in Scala (where implicits were influenced by type classes), but it's hard to find confirmation online. Do you know whether they are used, and how heavily? (It's easier to find such confirmation for The Guardian.)

Possible example: Do you make heavy use of generics in Java? I contributed to their design.

Possible example: I gather protocols in Swift are in part inspired by type classes, but it is hard to find confirmation online. Can you point me to confirmation?

There are many other possibilities. I hope you know some I haven't dreamed of!

Many thanks for your help. Answers are welcome at any time, but would be most useful if they can be provided by 2 September 2022.

Haskell in Production

 

Serokell has a series of posts on Haskell in Production. Spotted by Alex Wasey. Thanks, Alex!

Programming language to the stars

TIL that my students can choose among about forty different firms interested in hiring Haskell programmers. Among them is Co-Star, a firm that provides horoscopes to millions of users, which has put up a page detailing why they choose Haskell over other languages. Thanks to Alex Wasey and Dylan Thinnes for the pointer. 

The Plutus team is hiring

IOG, formerly known as IOHK, is hiring two new members for the Plutus team, currently led by Manuel Chakravarty and Michael Peyton-Jones. One of the posts is for a new leader, but don't worry, Manuel and Michael are both staying; the other post is someone to work on developer relations and communications. People working with the Plutus team include myself, Simon Thompson, and John Hughes. Plutus is a library for Haskell that provides smart contracts for Cardano. Ada, the coin of Cardano, is (as of last week) the fourth-largest cryptocurrency by market capitalisation, at USD$32 billion.

Details below. Let me know if you have any questions. 

Software Engineering Lead - Plutus

We are searching for a Software Engineer to lead our Plutus team. The Plutus team is building the core of Cardano’s smart contract functionality on the bedrock of functional programming languages. We are an interdisciplinary team who do original R&D and turn it into production systems.

In the past few years, the Plutus team has:

• Published five peer-reviewed papers with top academic researchers
• Designed and implemented three programming languages
• Formalized the semantics of two of those languages using Agda
• Helped to improve the ability of Agda to generate usable Haskell output
• Created novel compilation techniques for data types
• Written a GHC proposal, which is now being taken into implementation work
• Implemented a compiler for a subset of Haskell as a GHC plug-in
• Used statistical modeling to infer evaluation cost models
• Participated in the design and implementation of the Cardano ledger extensions to support smart contracts.

Such a heady and complex mixture of research, development, and design work needs a competent leader to keep it all working well. If that sounds like fun to you, drop us a line!

https://apply.workable.com/io-global/j/DC4A9703F1/

Developer Relations Specialist - Plutus

The Cardano ecosystem is expanding and software developer interest is increasing rapidly, so we are looking for a Developer Relations Specialist for the Plutus smart contract programming platform. You will help build, nurture and manage new relationships within established blockchain and smart contract development communities, especially Ethereum.

This role will put you at the forefront of an exciting developer ecosystem at a crucial time in its development, winning and onboarding partners, feeding any requirements and proposals back into the business, and helping rapidly expand a healthy, productive Cardano developer base.

To enjoy this role you will be someone who is passionate about blockchain technologies and the real problems they can address. You will have a proactive, problem-solving attitude, and enjoy working with customers and representing IOG at conferences, meetups, podcasts, etc.

https://apply.workable.com/io-global/j/965433F163/ 

Don't Stop ICFP

The ICFP music video is out! Thank you to Youyou Cong and Jose Calderon for putting this together. They've done the community a great service.

Haskell, Then and Now. Got Questions? Ask them here!

IOHK Cardano Virtual Summit continues. Today's sessions include:

16.00 Fri 3 Jul Haskell, then and now: What is the future for functional programming languages? Prof Simon Peyton-Jones, Prof John Hughes, Prof Philip Wadler, Dr Kevin Hammond, Dr Duncan Coutts.

You can submit questions via Reddit. Register for the summit here. You can log in with your registered username and password here.

Cardano Virtual Summit 2020

I'm participating in four sessions at Cardano Virtual Summit 2020, and there are many other sessions too. All times UK/BST.

16.00 Thu 2 Jul An overview of IOHK research Prof Aggelos Kiayias, Prof Elias Koutsoupias, Prof Alexander Russell, Prof Phil Wadler.

18.30 Thu 2 Jul Architecting the internet: what I would have done differently... Vint Cerf, Internet pioneer and Google internet evangelist, Prof Aggelos Kiayias, panel moderated by Prof Philip Wadler.

20.00 Thu 2 Jul Functional smart contracts on Cardano Prof Philip Wadler, Dr Manuel Chakravarty, Prof Simon Thompson.

16.00 Fri 3 Jul Haskell, then and now: What is the future for functional programming languages? Prof Simon Peyton-Jones, Prof John Hughes, Prof Philip Wadler, Dr Kevin Hammond, Dr Duncan Coutts.

Haskell Love

I am speaking at Haskell Love, 31 July--1 August 2020,  a virtual event.

PhD position in Certifying Compilation of Smart Contracts

Wouter Swierstra at Utrecht and my IOHK colleague Manuel Chakravarty are looking for someone to undertake a PhD to build a certifying compiler for our smart contract language, Plutus.

This project aims to develop a certifying compiler for Plutus Tx, a subset of the purely functional language Haskell that is used to implement smart contracts for the Cardano blockchain. The Plutus smart contract framework is being developed by IOHK for Cardano and the present project is a joint effort of IOHK and Utrecht University. The Plutus Tx compiler is based on the GHC Haskell compiler and adds a translation step from GHC Core to a minimal lambda calculus. Programmes in this lambda calculus are executed during transaction validation in a sandboxed execution environment in a manner that is crucial to the security of the blockchain. The aim of this project is to formalise the semantics of the languages involved in a proof assistant such as Coq, to reason about the transformation and optimisation steps that the compiler performs, and finally, to generate a proof object certifying the correctness of the generated code together with that code.

IOHK is hiring!

The Plutus team at IOHK is headed by Manuel Chakravarty and consists of a small but strong team of developers; I work on it as a consultant. We are designing a smart contract language, based on Haskell (for both offchain and onchain user-level programming) and System F (as the core code that runs onchain, the equivalent of the EVM for Ethereum). IOHK, unlike any other firm I know, is committed to building on peer-reviewed research, so publication is encouraged. We are hiring!

As a Functional Compiler Engineer at IOHK you will work closely with our programming language theory and cryptography researchers, our formal methods team, and our engineering team throughout the smart contracts development programme involving design, coding, testing and integrating of new smart scripting languages into our blockchain technology. This also includes the design and implementation of relevant domain specific languages (DSLs). You will have a strong understanding of programming language design, type systems, operational semantics, interpreters, and compiler implementation techniques.

Applications from folk who will increase our diversity are encouraged. Details here.

Two weeks of teaching in Ethiopia

I just returned from teaching a class of twenty-two women in Addis Ababa, courtesy of IOHK. Rounding off eight weeks of Haskell, taught by Lars Brünjes and Polina Vinogradova, I spent two weeks teaching IOHK's smart contract languages Plutus and Marlowe. It was an amazing experience. I thank IOHK and my students for the opportunity, and I look forward to repeating it someday.

Here is IOHK's announcement prior to the course, and an analysis from an outsider.

Thank you to my students for introducing me to injera!

With Wanda, Lars, and Polina in traditional dress at the graduation ceremony.

All the students in traditional dress for graduation. They wear it well!

Plutusfest

Plutus is the smart contract language for Cardano, the proof-of-work blockchain developed by IOHK. It is based on Haskell, and developed by a team led by Manuel Chakravarty and myself. IOHK will be premiering Plutus to the world at Plutusfest in Edinburgh, this coming Tuesday. You are invited! Details at plutusfest.io.

Haskell Team Up

I suggested a team-up, and, lo, it appears!

Lambdaman meets Spider-Moy

I was delighted and gobsmacked to hear from Moises Vazquez, a university teacher from Mexico who has a penchant for dressing up as Spider-Man. Reuters reports:

"I do the same job as anyone else, I don't think it's the best class in the world just because I put on a suit. But I assure you I want to be the most honest and dedicated there is, I just want to make the classroom a better place," he said.

I am blown away by his costume, with amazing detail such as Barendregt's lambda cube on the back and categorical arrows for webbing. Time for a superhero team-up?

Papers We Love: John Reynolds, Definitional Interpreters for Higher-Order Languages, now in Haskell

I suggested at Papers We Love that someone might like to recode John Reynolds's definitional interpeter, and I'm pleased to say that Rein Henrichs has done so.

First Paul, now John

Two years ago we lost Paul Hudak to cancer. Today I was saddened to learn that we have lost his close collaborator, John Peterson, to a climbing accident. Both will be missed.

LFCS 30 and WadlerFest

I feel shy, humble, and honoured announcing this, but it's been pointed out to me that readers of this blog may find the following event of interest: LFCS 30 and WadlerFest. It looks like a fantastic line up. (I can say that because I've had nothing to do with it.) Many, many thanks to the organisers and contributors, and special thanks to Janne Irgens for the illustration above.