5 ms·

How to design co-programs

104 points by matt_d 8y ago

dfee 8y ago
Ads on the blog but you’re too cheap to move to your own TLD. I don’t know why I find great humor in this, but the advertisement “Casinos hate this site...” made me laugh (and hate your site -> and swipe back to HN). Sorry, I’m away from my house and so there’s no pi-hole enabled.
- dfee 8y ago
  As a follow-up, I think the humor is that I imagine this blog might have valuable information, but you’re turning off your target audience with low-brow ads.
  - jer_gib 8y ago
    For the record, the ads are all Wordpress's doing, not mine. I have no control over them, and derive no benefit from them (on the contrary, they put me off too!).
- ishansharma 8y ago
  I'm pretty sure the ads are not put up by the author by WordPress.com. According to their pricing page[1], they "sometimes" display ads on blogs to cover costs. https://wordpress.com/pricing/ https://wordpress.com/pricing/
bmc7505 8y ago
A Mathematical Theory of Codesign: https://arxiv.org/pdf/1512.08055.pdf https://arxiv.org/pdf/1512.08055.pdf
smadge 8y ago
The intermediate representation of the binary tree for QuickSort in this article was a “eureka” moment for me. I think algorithm and data structure curriculums should take this approach.
- cryptonector 8y ago
  No kidding. This is very nice. I might be taking some liberties here, but the point about the shape of the output driving the shape of the program reminds me of using schema information in SQL (think of declared foreign keys) to generate queries: the schema tells you the shape of the data in more ways than just tables and columns, and this in turn tells you about the queries you might want. If you enrich a relational schema with more metadata, then you can generate even more queries. Think of declaring the set of all relations that define authorization data, not just group memberships, but access controls that refer to groups, define ownership, and so on. So, for example, 'give me all the authorization-relevant entities "to the right" of this entity' might be a query that, given enough schema metadata, can generate a much more complex SQL query. But that abstract query itself becomes an obvious query given the shape of the data (i.e., the schema). A more concrete example is "what can this user do?" and "who can do what to this resource?", "what groups is this user a member of?", "what are all the members of this group?" (note: these are not trivial if groups nest) which are instantiations of "what are all the entities to the {left, right} of this entity, using the set {name} of relations?". In terms of SQL these are all JOINs or LEFT JOINs (depending on declared relation NULLability, or relation cardinalities), with RECURSIVE queries using UNION (not UNION ALL, to avoid infinite recursion in the presence of circular relations) for "nesting" relations (from a table to itself, perhaps crossing relations on other tables in the process). SQL is extremely powerful and expressive, but we can make these queries pithier and more obvious with a more abstract language that takes advantage of schema metadata. Indeed, graph databases are such a language. SQL needs a richer schema definition language (extensions will do) by which to formally describe more of the shape of the data.
- agumonkey 8y ago
  Something I've seen in most Xavier Leroy (of Ocaml) slides. It makes things so clear to me.
- pwm 8y ago
  Completely agree. Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. Not sure why... If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).
emmanueloga_ 8y ago
Funny how the author gave this talk in honor of Felleisen's on his 60th birthday. "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". I started reading HTDP long ago but at the time I made the huge mistake of taking a detour to learn Racket, and later Scheme... HTDP provides small languages just to save students from the herculean effort of having to learn a whole programming language and environment. Way to miss the point. Anyway, there's some associated documentation on the Racket site about a library called "2htdp/universe" [1]. The architecture described is very close to the so called "ELM architecture" [2] or even Redux [3]. Probably (maybe?) there's no relation though, since coming to this architecture appears to be really natural when working with functional programming languages. 1: https://docs.racket-lang.org/teachpack/2htdpuniverse.html#%28part._world._interactive%29 https://docs.racket-lang.org/teachpack/2htdpuniverse.html#%2... 2: https://guide.elm-lang.org/architecture/ https://guide.elm-lang.org/architecture/ 3: https://redux.js.org/ https://redux.js.org/
- geezerjay 8y ago
  > "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". ...or, you know, that old "standing on the shoulders of giants" thing.
  - guest2143 8y ago
    Newton's "..standing on the shoulders of giants..." was a dig at Hook (who was short). It's Isaac being an arrogant jerk, which he was in spades. (Even if he revolutionized thinking in a number of areas.) It's not a statement of humbleness..
    - emmanueloga_ 8y ago
      I don't know, I heard this interpretation before but honestly the phrase makes sense when interpreted the other way around too, so way not just take the first meaning. The dig at Hook is a fun knowledge nugget anyway, that silly Isaac. :-p
    - 8y ago
atopos 8y ago
Nice article! Something along these lines is still present, I think, in HtDP, at least in the Chapter about abstractions (16.1, 16.5, and 16.6). Basically, when designing a function one can use existing abstractions (or, I would add, design her own abstraction) whose whole signature, output included, matches the purpose and signature of the function to be designed. So, if the problem at hand is to design a function that takes a natural number and produces a list, that calls for using the built-in `build-list`, whose signature is `N [N -> X] -> [List-of X]`. Or if the output of a function on lists is a Boolean value, one has to keep an eye on `ormap`/`andmap`, etc. So the output is also essential to choose the suitable abstraction.
- nuclx 8y ago
  This reminds me of type-driven programming as in Idris using the Type-Define-Refine workflow as described by Brady.

104 points by matt_d 8y ago

dfee 8y ago

Ads on the blog but you’re too cheap to move to your own TLD. I don’t know why I find great humor in this, but the advertisement “Casinos hate this site...” made me laugh (and hate your site -> and swipe back to HN). Sorry, I’m away from my house and so there’s no pi-hole enabled.

dfee 8y ago
As a follow-up, I think the humor is that I imagine this blog might have valuable information, but you’re turning off your target audience with low-brow ads.
- jer_gib 8y ago
  For the record, the ads are all Wordpress's doing, not mine. I have no control over them, and derive no benefit from them (on the contrary, they put me off too!).
ishansharma 8y ago
I'm pretty sure the ads are not put up by the author by WordPress.com. According to their pricing page[1], they "sometimes" display ads on blogs to cover costs. https://wordpress.com/pricing/ https://wordpress.com/pricing/

bmc7505 8y ago

A Mathematical Theory of Codesign: https://arxiv.org/pdf/1512.08055.pdf https://arxiv.org/pdf/1512.08055.pdf

smadge 8y ago

The intermediate representation of the binary tree for QuickSort in this article was a “eureka” moment for me. I think algorithm and data structure curriculums should take this approach.

cryptonector 8y ago
No kidding. This is very nice. I might be taking some liberties here, but the point about the shape of the output driving the shape of the program reminds me of using schema information in SQL (think of declared foreign keys) to generate queries: the schema tells you the shape of the data in more ways than just tables and columns, and this in turn tells you about the queries you might want. If you enrich a relational schema with more metadata, then you can generate even more queries. Think of declaring the set of all relations that define authorization data, not just group memberships, but access controls that refer to groups, define ownership, and so on. So, for example, 'give me all the authorization-relevant entities "to the right" of this entity' might be a query that, given enough schema metadata, can generate a much more complex SQL query. But that abstract query itself becomes an obvious query given the shape of the data (i.e., the schema). A more concrete example is "what can this user do?" and "who can do what to this resource?", "what groups is this user a member of?", "what are all the members of this group?" (note: these are not trivial if groups nest) which are instantiations of "what are all the entities to the {left, right} of this entity, using the set {name} of relations?". In terms of SQL these are all JOINs or LEFT JOINs (depending on declared relation NULLability, or relation cardinalities), with RECURSIVE queries using UNION (not UNION ALL, to avoid infinite recursion in the presence of circular relations) for "nesting" relations (from a table to itself, perhaps crossing relations on other tables in the process). SQL is extremely powerful and expressive, but we can make these queries pithier and more obvious with a more abstract language that takes advantage of schema metadata. Indeed, graph databases are such a language. SQL needs a richer schema definition language (extensions will do) by which to formally describe more of the shape of the data.
agumonkey 8y ago
Something I've seen in most Xavier Leroy (of Ocaml) slides. It makes things so clear to me.
pwm 8y ago
Completely agree. Maybe it’s because CS curricula tends to teach searching/sorting algorithms before data structures, specifically BSTs. Not sure why... If you think about it a BST defines order and a sorting algorithm achieves it so naturally the output of a sort can be seen as a BST (flattening it to a list is somewhat irrelevant).

emmanueloga_ 8y ago

Funny how the author gave this talk in honor of Felleisen's on his 60th birthday. "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". I started reading HTDP long ago but at the time I made the huge mistake of taking a detour to learn Racket, and later Scheme... HTDP provides small languages just to save students from the herculean effort of having to learn a whole programming language and environment. Way to miss the point. Anyway, there's some associated documentation on the Racket site about a library called "2htdp/universe" [1]. The architecture described is very close to the so called "ELM architecture" [2] or even Redux [3]. Probably (maybe?) there's no relation though, since coming to this architecture appears to be really natural when working with functional programming languages. 1: https://docs.racket-lang.org/teachpack/2htdpuniverse.html#%28part._world._interactive%29 https://docs.racket-lang.org/teachpack/2htdpuniverse.html#%2... 2: https://guide.elm-lang.org/architecture/ https://guide.elm-lang.org/architecture/ 3: https://redux.js.org/ https://redux.js.org/

geezerjay 8y ago
> "Hi, to honor you I'll talk about how one of your better known works is incomplete and only shows half of the picture". ...or, you know, that old "standing on the shoulders of giants" thing.
- guest2143 8y ago
  Newton's "..standing on the shoulders of giants..." was a dig at Hook (who was short). It's Isaac being an arrogant jerk, which he was in spades. (Even if he revolutionized thinking in a number of areas.) It's not a statement of humbleness..
  - emmanueloga_ 8y ago
    I don't know, I heard this interpretation before but honestly the phrase makes sense when interpreted the other way around too, so way not just take the first meaning. The dig at Hook is a fun knowledge nugget anyway, that silly Isaac. :-p
  - 8y ago

atopos 8y ago

Nice article! Something along these lines is still present, I think, in HtDP, at least in the Chapter about abstractions (16.1, 16.5, and 16.6). Basically, when designing a function one can use existing abstractions (or, I would add, design her own abstraction) whose whole signature, output included, matches the purpose and signature of the function to be designed. So, if the problem at hand is to design a function that takes a natural number and produces a list, that calls for using the built-in `build-list`, whose signature is `N [N -> X] -> [List-of X]`. Or if the output of a function on lists is a Boolean value, one has to keep an eye on `ormap`/`andmap`, etc. So the output is also essential to choose the suitable abstraction.

nuclx 8y ago
This reminds me of type-driven programming as in Idris using the Type-Define-Refine workflow as described by Brady.