HNHacker News
TopNewBestAskShowJobs

xgk

74 karma · joined August 28, 2016

submissionscomments
xgk··on Interview with Xavier Leroy
> to separate specification from verification

Exactly.

Program logics are superior in this regard: the encourage rather than inhibit separation of concerns. (Not to mention: program logics are more developed and cover a large class of computing paradigms, while dependent types have not grown much beyond the pure functions ghetto.)

I put forward this point to dependent types luminaries all the time. Its difficult to get more than polite silence in response.

      * * *
It's partly a social problem: The community working on dependently typed languages and tools typically have most of their programming experience with pure functional languages. Exaggerating only a bit, here is the typical trajectory of a formal methods researcher:

- As an undergraduate writes a lambda-calculus interpreter in Lisp/Scheme/Racket/Haskell

- As a PhD Student writes their own pure language with wacky typing system, and demonstrate its usefulness by embedding a lambda-calculus interpreter in it.

- As a postdoc verifies a lambda-calculus interpreter in Coq/Agda.

- As an assistant professor writes their own Curry-Howard-based interactive prover in some dependently typed language and demonstrate its usefulness by verifying a lambda-calculus interpreter in it.

- After tenure, gets their students to do the above.

2018's POPL has a type-theory in type-theory paper, but none on how programming language theory can improve SAT solving ...

It's an echo chamber. I recently reviewed a grant proposal by some of the more famous dependent types researchers. They proposed using HoTT to verify computational effects. The grant proposal claimed (1) that there is currently no known way to verify effectful languages and (2) that embedding generalisations of effect monads in HoTT is the way to overcome this problem. It seems like these people have not ever heard of program logics?

   * * *
A second reason is more serious: the real problem of formal verification is not this-language/that-logic. In day-to-day verification, it doesn't really matter that much whether you are using this/that approach. You need to set up the right definitions and invariants. That's the hard part. Whether you express them in some program logic or dependently typed system doesn't matter much, you can usually transliterate between them.

The real problem is automation.

Better autmation means dramatically better SAT solvers (modern SMT solvers are heavily reliant of SAT solvers). It's just unclear where 10x, 100x, 1000x speedups in SAT solvers should come from. We don't even know how to parallelise SAT solvers well. In the absence of dramatic progress in SAT solvers, what can we do other than tinkering with dependently typed languages and their relatives?

xgk··on When Beethoven Met Goethe

   melody, harmony, and rhythm [...] timbre
You are missing the fifth and most important: meaning!

To be fair meaning is extra-musical, and varies between listeners.

Other than that, you are absolutely correct: timber is the focus of modern electronic music. All previous genres simply lacked the instruments to do much of interest in the way of timber.

xgk··on When Beethoven Met Goethe
Beethoven and Goethe worked in a specific artistic context which is radically incompatible with industrial production that is characteristic of modern pop-music and marketing. Hence a facile quip like "Beethoven would be making techno in Rotterdam" is misleading and does not really engage with the subject matter. Yet, pointing this out and triggering an interesting debate gets reprimanded as "curmudgeonly" when the discussion was specifically about pop-music.

May I ask what is on-topic on HN these days?

xgk··on When Beethoven Met Goethe

   what it is they have against 
   repetition
    
They find it boring.

Would you come to HN every day if the linked articles never changed?

I'm quite enamoured with Schmidthuber's theory of creativity [1, 2] Schmidhuber develops a theory of artificial curiosity and creativity for an autonomous agent. The agent is equipped with an adaptive predictor trying to predict future events from the history of previous events and actions. A reward-maximising, reinforcement learning, adaptive controller is steering the controller and gets curiosity reward for executing action sequences that improve the predictor. (I term this "Pattern Recognition as Pleasure".) This discourages the agent from executing actions leading to boring outcomes that are either predictable or totally unpredictable. Instead the controller is motivated to learn actions that help the predictor to learn new, previously unknown regularities in its environment, thus improving its model of the world, which in turn can greatly help to solve externally given tasks. Schmidhuber claims that his corresponding formal theory of creativity explains essential aspects of art, science, music, and humor.

If we were to take Schmidhuber's approach seriously, then that that which we enjoy as great art (as creative) would be that which is on the edge of the observer's ability to compress/understand. Note that this is highly observer dependent! What I have been comprehending for a long time and dismiss as boring, might be extremly interesting for somebody else, and vice versa.

In my own life this was born out: I used to enjoy pop-music so much and didn't worry about repetition -- in fact I didn't notice it. I loved pop-music so much that I learned how to make it. This lead to my disenchantment with pop-music: when I was finally able to produce decent pop-music (I was able to compress it into a few rules), I lost interest, and sought novelty elsewhere.

   never heard of trance
I've certainly read Gilbert Rouget's Music and trance [3]. The upshot of this book is that trance is not really tied to any musical quality, but a social effect where we copy other's behaviours.

[1] J. Schmidhuber, Formal Theory of Creativity, Fun, and Intrinsic Motivation. http://people.idsia.ch/~juergen/creativity.html

[2] J. Schmidhuber, Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity & Creativity. https://arxiv.org/abs/0709.0674

[3] https://books.google.co.uk/books/about/Music_and_Trance.html...

xgk··on When Beethoven Met Goethe

   And course the reply:
I found Aphex Twin's reply disappointing.

Like a petulant child he essentially negated Stockhausen's points, without engaging with them. It seems to me that Stockhausen was trying to be helpful -- after all he had been a music teacher for nearly 1/2 century with academic offspring like Kraftwerk and Can. Aphex Twin seemingly was unable/unwilling to see that there are other approaches to music than the orthodoxy of 1990s dance music. Aphex Twin's main musical criterion seems to be dancablility:

    you can't dance to. Do you 
    reckon he can dance? You could 
    dance to   Song of the Youth, but 
    it hasn't got a groove in it, 
   there's no bassline."
I would argue to the contrary: dance music -- whatever its merits for dancing -- cannot be interesting as art music. Why? Because dancing, specially dancing well, is itself demanding: most brain capacity is used for moving the body along to the music in the right way, and that capacity is missing for listening to and analysind the fine points of the music.

   Reich, Glass et al. might disagree.
Of course the art music tradition of American mimimalism that you refer to, does change tempi and changing rhythms quite a great deal. It does so in novel ways that had not been explored in previous classical traditions. That's the main novelty that American mimimalism gave to the world.

   Periodicity is what ...
I agree with that, and add that modern pop-music errs on the side of too much periodicity, which renders it uninteresting as art-music, but useful as aural background and for dancing.
xgk··on When Beethoven Met Goethe
I'm not really pushing any specific notion of genius, but was challenging the claim that B. would be making techno today.

I agree, "there's got to be something convincing", but it's unlikely to be musical. Most musicians who have a hit at all have but one hit, and then fade away. Most of the few musicians who persist (eg Rolling Stones) have a massive and well-capitalised marketing department behind them. To a pretty good approximation no musician without major backing (which is expensive) has ever been widely and/or long-term successful. To understand the nature of hits, you need to understand the music industry.

Coincidentally, the music industry follows the SV VC model: fund 100, expect 99 to fail and the one unicorn who makes it big recoups (more than) the cost of the 99 failures.

xgk··on When Beethoven Met Goethe
I don't see pop-music as vile. For me it's a social tool. It gets me & friends into a certain shared mood: relax, unwind, get drunk, etc etc. But it's not artistic: pop-music is surprise-free, it's conventional, it doesn't make me think "wow, I've never though of this". Au contraire. And that's why it works for setting shared social moods. It could not serve its social function if it was too original, too intellectually demanding.

If it's Saturday night 2am "in the club" everybody's intoxicated the music needs to 'hit' everybody straightaway. Everybody needs to know when to raise their hands ... and that means it must be extremely predicable.

xgk··on When Beethoven Met Goethe
I wish you had elaborated this comment into something substantial that readers could learn from.

Here is an interesting comment that a classical composer -- possibly the most influential one in the 20th century through his students -- on Aphex Twin and similar artists:

http://www.synthtopia.com/content/2010/10/15/karlheinz-stock...

xgk··on When Beethoven Met Goethe
That is a controversial point and depends on your concept of art. There are conceptions of art where novelty is an integral part of the very definition of artwork.

I agree that pop-music is precisely about creating "feeling and atmosphere", but I would extend it by saying: "easily, quicly and widely accessible shared feeling and atmosphere". And it is precisely this requirement of easy/quick access to the shared feeling and atmosphere that makes it important for pop-music to be conventional, to be repetition of previous pop-music. Surprise is anti-thetical to the purpose of pop-music.

Pop-music is acoustic wall-paper that is intended reliably to create a certain atmosphere.

You can gauge the conventional nature of pop-music from the fact that you can reliably determine the genre (e.g. House/Techno, Rap, Metal, Folk etc) by sub-1-second snippets. All successful genres have signature sounds for enabling quick identification. You can think of this as an aural version of branding. This is very well-known by professional producers, musicians and music marketing.

xgk··on When Beethoven Met Goethe
Why would a "link" be interesting or relevant? My point that modern pop-music is extremely generic stands/falls whether I have "tracks" or not.

It's hard to deny that modern pop-music is to an extremely good approximation all in the 4/4 time signature for example, so to an extremely good approximation all modern pop-music has less rhythmic variety e.g. many/most single classical pieces.

xgk··on When Beethoven Met Goethe

   Beethoven would be making techno
Why? Given that making techno, or modern pop music in general, is basically trivial. Just spin up Ableton, press a few buttons ... boom, 10 minutes later you've got a competitive techno-track that doesn't sound all that different (apart from mastering maybe) from what's being played in the clubs. There is no art left in pop-music -- trivial and generic.

A genius would be horrified by the trivial repitition of the same that is modern pop-music.

xgk··on The Kolmogorov option
It's hard not to be reminded of Mao's Hundred Flowers Campaign (百花运动) [1] and Anti-Rightist Movement (反右运动) [2].

[1] https://en.wikipedia.org/wiki/Hundred_Flowers_Campaign

[2] https://en.wikipedia.org/wiki/Anti-Rightist_Movement

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
One of my PhD students will soon have to learn an interactive prover. I was to recommend Isabelle/HOL because it's got the best automation, but maybe I should consider Lean (and learn it along with him).

I worry slightly about Lean being immature, and lacking a big library eco-system in 2017. OTOH, it's also good to be at the cutting edge.

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   calling context
In compositional verification, you generally want to prove as much as possible about the piece of code at hand -- irrespective of calling context.

   spec very similar to this
Yes, I was using something similar. Note that this is right only in a purely sequential setting ...

   I recently verified a JIT compiler,
That sounds exciting. That must have been a major piece of work. Anything published yet?

With JIT compilers the issue of self-modification becomes pertinent. I know that Magnus Myreen has verified a small JIT compiler a few years back but I don't remember exactly what theorem he proves. IIRC he was using a tailor-made Hoare logic for x86 code that basically moved some of the complexity of the spec into the logic.

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
Thanks for the link to the paper.

De Moura is giving a talk tomorrow in Cambridge at the workshop in computer aided proofs called "Metaprogramming with Dependent Type Theory". I wanted to go, but won't be able to attend. I guess that talk will mostly be about the content of the paper. Now I don't feel so bad for being unable to attend.

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   Depending on the programming 
   language being proved
That's true, GCed languages are simpler in this regard. But for low-level languages you have to do this 'by hand', and it can be complicated.

   not had the concept of null
That doesn't make the problem go away, you just have another case in the destructors (e.g. pattern matching) that you need to account for logically. Just kicking the can down the road.

   would love to read more 
   about it
Nothing published. Long story. I'll tell you in person, should we meet some day.
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
Yes. Mostly.

But in practise, you need to specify what sortedness means, and in a generic sorting algorithm that means axiomatising the comparison predicate, including its side-effects. Note for example the C standard library implementation of Quicksort does take an arbitrary predicate, which may not be transitive, may have arbitrary side effects etc. The behaviour of sorting becomes pretty complicated in this scenario.

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

    there is only a "theorem" datatype 
You mean that there is NOT only a "theorem" datatype? In contrast to Curry/Howard provers, the LCF approach forgets proofs, it guarantees soundness by giving you access to proof rules only through the "theorem" datatype (which is the key trusted computing base). To be sure the "theorem" datatype may internally maintain a proof object (e.g. for the purposes of program extraction), but that's not necessary.
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   The latter ones can 
   be all incorrect for 
   all you care
Good point. Maybe we can call this the TSP (trusted specification base)?

In my experience the TSP is subtle and contains most of the intermediate definitions too. A few years back I had a very large Isabelle/HOL proof invalidated because of some small mistake in an obscure part of the specification that I never though could be important. It required a redesign from scratch of almost all of the proof.

   only have to specify "after 
   running the function sort() 
   on an array,
I'm afraid that's not enough in practise: you will also have to specify (and verify) things like: the implementation does not touch memory except the array to be sorted (and some auxiliary variables). If you don't, it will typically be difficult to use the proof of the sorting function in the context of the verification of a larger program.

   all the way down 
   to the machine code
No, that's an orthogonal dimension.
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
This is interesting. It will take me some time to digest this paper.

As an aside: is there a terse description of Lean's type-theory? Also: Lean is Curry/Howard based, it's not an LCF-style architecture?

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
ITTs like Lean are more expressive as logics than HOL, but I doubt that Certigrad needs even a fraction of HOL's power. So anything you need that you express as types in Lean you should be able to express as theorem in HOL. Presumably that is inconvenient (= technical debt), but why?
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   A specification is usually 
   a lot simpler, because ...
I used to think that too, but after verifying some algorithms, I have become sceptical of that belief. Instead I conjecture that on average the full specification of an algorithm is at best proportional in length to the algorithm itself. There are two main issues:

- Most verification does not tackle the full specification, but rather some aspect.

- Verification needs many intermediate specifications (e.g. induction hypotheses in proofs), which need to be accounted for.

I'm happy to be convinced otherwise.

   prove that a sorting 
   algorithm is 
I produced the full verification of Quicksort (probably the first), and I needed to produce a large amount of intermediate specifications for auxiliary lemmas. The full specification was much longer than the algorithm.
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   Can this be done with Coq?
This can be done with any prover.

Simplifying a bit, an algorithm is a function of type A -> B. If you have two implementations, f1 :: A -> B and f2 :: A -> B, say one slow and simple (f1), one fast and complicated (f2), then you can verify that f2 does what it is supposed to do in two steps:

1. Show that for all a in A we have f1 a == f2 a.

2. Show that f1 meets the specification.

If you trust that f1 does what it is supposed to do, then you can skip (2).

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
I second this.

Isabelle/HOL has much better proof automation than any prover based on Curry/Howard. That's primarily because HOL is a classical logic, while Curry/Howard is constructive (yes, I know we can do classical proofs inside constructive logic, e.g. with proof irrelevance). Almost all automated provers are also classical. Having comparably powerful proof automation to Curry/Howard based systems is an open research problem.

   weird extra quotes
That's because Isabelle is not a prover, but a 'meta-prover' used for implementing provers, e.g. Isabelle/HOL. In practise HOL is the only logic implemented in Isabelle with enough automation to be viable, so we don't really use Isabelle's 'meta-prover' facilities in practise.
xgk··on Certigrad: bug-free machine learning on stochastic computation graphs

   specification is a lot 
   smaller than the code
I doubt that this is the case in general.

How can the (full) specification of a program be smaller than the program? This would mean we can always compress a program into a smaller program (after all a specification can be seen as another program -- alternatively a program can be seen as its own specification).

xgk··on Certigrad: bug-free machine learning on stochastic computation graphs
Could this problem have been (partly) avoided by going for an LCF-based prover such as HOL or Isabelle/HOL, rather than a system based on the Curry-Howard correspondence?
xgk··on Modelling Homogeneous Generative Meta-Programming
Our model can be used as a basis to implement any approach to hygiene that is of interest.
xgk··on Modelling Homogeneous Generative Meta-Programming
We have an implementation in Nominal Isabelle/HOL, but it's not used in the paper.
xgk··on Modelling Homogeneous Generative Meta-Programming
Hygiene is deliberately omitted.

Why? Because there are various different ways of handling hygiene, including not providing hygiene at all. A foundational model of MP should not 'hard-code' any specific approach towards hygiene.

xgk··on Modelling Homogeneous Generative Meta-Programming
Coauthor of the "Modelling ..." paper here. Happy to answer questions!
← PreviousPage 2 of 3Next →