Sunday, April 28, 2019
Manuscript of Interest: Write You a Haskell
Write You a Haskell
Building a modern functional compiler from first principles.
Author: Stephen Diehl
Abstract:
In 2014 I wrote a short tutorial about building a small imperative language in Haskell that compiled into LLVM. I was extremely happy with the effect the tutorial seemed to have, and the warm response I got from so many people was very encouraging.
I've done a great bit of thinking about what the most impactful topic I could write about in 2015 could be; and decided throughout this year I will follow up with a large endeavor for another project-based tutorial on building a simple functional programming language from first principles.
This is a nontrivial topic and is unfortunately very much underserved, the knowledge to build such a modern functional language is not widely disseminated among many programmers. The available resources most often discuss language theory in depth while completely glossing over the engineering details. I wished to write a project-based tutorial that included the engineering details and left the reader with a fully functional toy language at the end that could be extended for further projects.
We will build a small functional language called Fun which is a partial Haskell 2010 toy language; complete with a parser, type inference, datatypes, pattern matching, desugaring, typeclasses, higher-kinded types, monadic IO, arbitrary-rank polymorphism, records, Core language, STG intermediate language, lazy evaluation, interpreter, native code generator, a runtime, and several optimization passes.
As with most of my writing, this is the pre-edited rough cut version, which I will refine over time.
Project of Interest: Aweigh (Offline Navigation System)
Aweigh
Aweigh is an open navigation system that does not rely on satellites: it is inspired by the mapping of celestial bodies and the polarized vision of insects. Ancient seafarers and desert ants alike use universally accessible skylight to organize, orient, and place themselves in the world. Aweigh is a project that learns from the past and from the microscopic to re-position individuals in the contemporary technological landscape.
Networked technolgies that we increasingly rely on undergo changes that are often beyond our control. Most smartphone users require government-run satellites to get around day by day, while consequences of Brexit are calling into question the UK’s access to the EU’s new satellite system, Project Galileo. Aweigh is a set of tools and blueprints that aims to open modern technologies to means of democratization, dissemination, and self-determination.
These tools were designed to depend only on publicly available materials and resources: digital fabrication machines, open-source code, packaged instructions, and universally accessible sky light. Aweigh is inspired by ancient navigation devices that use the process of taking angular measurements between the earth and various celestial bodies as reference points to find one’s position. Combining this process with the polarization of sunlight observed in insect eyes, the group developed a technology that calculates longitude and latitude in urban as well as off-grid areas.
All of Aweigh’s development resources are made public via free online distribution, in conjunction with a downloadable manual, schematics for a custom PCB, templates, and several device variations. These variations provide multiple methods of implementation at each step of construction for a spectrum of user skill levels. Aweigh is a project that shows a future where individuals have a voice in the power structures driving their technologies.
Aweigh is an open navigation system that does not rely on satellites: it is inspired by the mapping of celestial bodies and the polarized vision of insects. Ancient seafarers and desert ants alike use universally accessible skylight to organize, orient, and place themselves in the world. Aweigh is a project that learns from the past and from the microscopic to re-position individuals in the contemporary technological landscape.
Networked technolgies that we increasingly rely on undergo changes that are often beyond our control. Most smartphone users require government-run satellites to get around day by day, while consequences of Brexit are calling into question the UK’s access to the EU’s new satellite system, Project Galileo. Aweigh is a set of tools and blueprints that aims to open modern technologies to means of democratization, dissemination, and self-determination.
These tools were designed to depend only on publicly available materials and resources: digital fabrication machines, open-source code, packaged instructions, and universally accessible sky light. Aweigh is inspired by ancient navigation devices that use the process of taking angular measurements between the earth and various celestial bodies as reference points to find one’s position. Combining this process with the polarization of sunlight observed in insect eyes, the group developed a technology that calculates longitude and latitude in urban as well as off-grid areas.
All of Aweigh’s development resources are made public via free online distribution, in conjunction with a downloadable manual, schematics for a custom PCB, templates, and several device variations. These variations provide multiple methods of implementation at each step of construction for a spectrum of user skill levels. Aweigh is a project that shows a future where individuals have a voice in the power structures driving their technologies.
Paper of Interest:
Paper of Interest: "Seven Sketches in Compositionality: An Invitation to Applied Category Theory"
Authors: Brendan Fong, David I. Spivak
The purpose of this book is to offer a self-contained tour of applied category theory. It is an invitation to discover advanced topics in category theory through concrete real-world examples. Rather than try to give a comprehensive treatment of these topics—which include adjoint functors, enriched categories, proarrow equipments, toposes, and much more—we merely provide a taste. We want to give readers some insight into how it feels to work with these structures as well as some ideas about how they might show up in practice. The audience for this book is quite diverse: anyone who finds the above description intriguing. This could include a motivated high school student who hasn’t seen calculus yet but has loved reading a weird book on mathematical logic they found at the library. Or a machine learning researcher who wants to understand what vector spaces, design theory, and dynamical systems could possibly have in common. Or a pure mathematician who wants to imagine what sorts of applications their work might have. Or a recently-retired programmer who’s always had an eerie feeling that category theory is what they’ve been looking for to tie it all together, but who’s found the usual books on the subject impenetrable.
Authors: Brendan Fong, David I. Spivak
The purpose of this book is to offer a self-contained tour of applied category theory. It is an invitation to discover advanced topics in category theory through concrete real-world examples. Rather than try to give a comprehensive treatment of these topics—which include adjoint functors, enriched categories, proarrow equipments, toposes, and much more—we merely provide a taste. We want to give readers some insight into how it feels to work with these structures as well as some ideas about how they might show up in practice. The audience for this book is quite diverse: anyone who finds the above description intriguing. This could include a motivated high school student who hasn’t seen calculus yet but has loved reading a weird book on mathematical logic they found at the library. Or a machine learning researcher who wants to understand what vector spaces, design theory, and dynamical systems could possibly have in common. Or a pure mathematician who wants to imagine what sorts of applications their work might have. Or a recently-retired programmer who’s always had an eerie feeling that category theory is what they’ve been looking for to tie it all together, but who’s found the usual books on the subject impenetrable.
Paper of Interest: Asymptotically Efficient Quantum Karatsuba Multiplication
Asymptotically Efficient Quantum Karatsuba Multiplication
Craig Gidney
(Submitted on 15 Apr 2019)
We improve the space complexity of Karatsuba multiplication on a quantum computer from O(n1.427) to O(n) while maintaining O(nlg3) gate complexity. We achieve this by ensuring recursive calls can add their outputs directly into subsections of the output register. This avoids the need to store, and uncompute, intermediate results. This optimization, which is analogous to classical tail-call optimization, should be applicable to a wide range of recursive quantum algorithms.
Explanatory Article:
A New Approach to Multiplication Opens the Door to Better Quantum Computers
Craig Gidney
(Submitted on 15 Apr 2019)
We improve the space complexity of Karatsuba multiplication on a quantum computer from O(n1.427) to O(n) while maintaining O(nlg3) gate complexity. We achieve this by ensuring recursive calls can add their outputs directly into subsections of the output register. This avoids the need to store, and uncompute, intermediate results. This optimization, which is analogous to classical tail-call optimization, should be applicable to a wide range of recursive quantum algorithms.
Explanatory Article:
A New Approach to Multiplication Opens the Door to Better Quantum Computers
Book of Interest: Structure and Interpretation of Classical Mechanics
Structure and Interpretation of Classical Mechanics
From Chapter 1:
The subject of this book is motion and the mathematical tools used to describe it.
Centuries of careful observations of the motions of the planets revealed regularities in those motions, allowing accurate predictions of phenomena such as eclipses and conjunctions. The effort to formulate these regularities and ultimately to understand them led to the development of mathematics and to the discovery that mathematics could be effectively used to describe aspects of the physical world. That mathematics can be used to describe natural phenomena is a remarkable fact.
Classical mechanics describes the motion of a system of particles, subject to forces describing their interactions. Complex physical objects, such as juggling pins, can be modeled as myriad particles with fixed spatial relationships maintained by stiff forces of interaction.
The motion of a system can be described by giving the position of every piece of the system at each moment. Such a description of the motion of the system is called a configuration path; the configuration path specifies the configuration as a function of time. The juggling pin rotates as it flies through the air; the configuration of the juggling pin is specified by giving the position and orientation of the pin. The motion of the juggling pin is specified by giving the position and orientation of the pin as a function of time.
The path-distinguishing function that we seek takes a configuration path as an input and produces some output. We want this function to have some characteristic behavior when its input is a realizable path. For example, the output could be a number, and we could try to arrange that this number be zero only on realizable paths. Newton’s equations of motion are of this form; at each moment Newton’s differential equations must be satisfied.
However, there is an alternate strategy that provides more insight and power: we could look for a path-distinguishing function that has a minimum on the realizable paths—on nearby unrealizable paths the value of the function is higher than it is on the realizable path. This is the variational strategy: for each physical system we invent a path-distinguishing function that distinguishes realizable motions of the system by having a stationary point for each realizable path.1 For a great variety of systems realizable motions of the system can be formulated in terms of a variational principle.2
Mechanics, as invented by Newton and others of his era, describes the motion of a system in terms of the positions, velocities, and accelerations of each of the particles in the system. In contrast to the Newtonian formulation of mechanics, the variational formulation of mechanics describes the motion of a system in terms of aggregate quantities that are associated with the motion of the system as a whole.
From Chapter 1:
The subject of this book is motion and the mathematical tools used to describe it.
Centuries of careful observations of the motions of the planets revealed regularities in those motions, allowing accurate predictions of phenomena such as eclipses and conjunctions. The effort to formulate these regularities and ultimately to understand them led to the development of mathematics and to the discovery that mathematics could be effectively used to describe aspects of the physical world. That mathematics can be used to describe natural phenomena is a remarkable fact.
Classical mechanics describes the motion of a system of particles, subject to forces describing their interactions. Complex physical objects, such as juggling pins, can be modeled as myriad particles with fixed spatial relationships maintained by stiff forces of interaction.
The motion of a system can be described by giving the position of every piece of the system at each moment. Such a description of the motion of the system is called a configuration path; the configuration path specifies the configuration as a function of time. The juggling pin rotates as it flies through the air; the configuration of the juggling pin is specified by giving the position and orientation of the pin. The motion of the juggling pin is specified by giving the position and orientation of the pin as a function of time.
The path-distinguishing function that we seek takes a configuration path as an input and produces some output. We want this function to have some characteristic behavior when its input is a realizable path. For example, the output could be a number, and we could try to arrange that this number be zero only on realizable paths. Newton’s equations of motion are of this form; at each moment Newton’s differential equations must be satisfied.
However, there is an alternate strategy that provides more insight and power: we could look for a path-distinguishing function that has a minimum on the realizable paths—on nearby unrealizable paths the value of the function is higher than it is on the realizable path. This is the variational strategy: for each physical system we invent a path-distinguishing function that distinguishes realizable motions of the system by having a stationary point for each realizable path.1 For a great variety of systems realizable motions of the system can be formulated in terms of a variational principle.2
Mechanics, as invented by Newton and others of his era, describes the motion of a system in terms of the positions, velocities, and accelerations of each of the particles in the system. In contrast to the Newtonian formulation of mechanics, the variational formulation of mechanics describes the motion of a system in terms of aggregate quantities that are associated with the motion of the system as a whole.
Paper of Interest: QuaterNet: A Quaternion-based Recurrent Model for Human Motion
QuaterNet: A Quaternion-based Recurrent Model for Human Motion
Dario Pavllo, David Grangier, Michael Auli
(Submitted on 16 May 2018 (v1), last revised 31 Jul 2018 (this version, v2))
Deep learning for predicting or generating 3D human pose sequences is an active research area. Previous work regresses either joint rotations or joint positions. The former strategy is prone to error accumulation along the kinematic chain, as well as discontinuities when using Euler angle or exponential map parameterizations. The latter requires re-projection onto skeleton constraints to avoid bone stretching and invalid configurations. This work addresses both limitations. Our recurrent network, QuaterNet, represents rotations with quaternions and our loss function performs forward kinematics on a skeleton to penalize absolute position errors instead of angle errors. On short-term predictions, QuaterNet improves the state-of-the-art quantitatively. For long-term generation, our approach is qualitatively judged as realistic as recent neural strategies from the graphics literature
Implementation
Sunday, April 21, 2019
Person of Interest: Nathaniel Schutta
Nathaniel Schutta
About:
Nathaniel T. Schutta is a software architect focused on cloud computing and building usable applications. A proponent of polyglot programming, Nate has written multiple books and appeared in various videos. Nate is a seasoned speaker regularly presenting at conferences worldwide, No Fluff Just Stuff symposia, meetups, universities, and user groups. In addition to his day job, Nate is an adjunct professor at the University of Minnesota where he teaches students to embrace dynamic languages. Driven to rid the world of bad presentations, Nate coauthored the book Presentation Patterns with Neal Ford and Matthew McCullough. Nate recently published Thinking Architecturally available as a free download from Pivotal.Site of Interest: Distill
Person of Interest: Micael Nielsen
Michael Nielsen
At the moment Michael says
Distill
At the moment Michael says
Linked workI'm a scientist, writer, and programmer.I work on ideas and tools that help people think and create, both individually and collectively.I'm a Research Fellow at Y Combinator Research. I'm also a member of the Steering Committee for the journal Distill, and write an occasional column for Quanta Magazine.Want to hear about my projects as they're released? Please join my mailing list.
Distill
Recalled to Life
Yes, Dickens. I won't bore you with explanations: suffice it to say I stopped and now I've started again, save with a different purpose. I need a tumble log. I think I'll write it here. Maybe not. We'll see.
Subscribe to:
Posts (Atom)