Lisp, the Universe and Everything

2016-09-23

The Technology Company Case

What's a Technology Company?

I'm a programmer. Obviously, this means that I have to earn money and realize my talents working for some company that employs programmers (or on my own). It's worth noting that there are several kinds of such companies.

One is traditional enterprises, like banks or government agencies, that need programmers to automate their processes and improve output. Every company needs an accountant, and, likewise, nowadays every needs a programmer.

There are also companies that provide software development and related services - the so-called consulting or outsourcing firms. They employ programmers to automate the work and improve the output of, mainly, the first breed of companies.

Then, there are also technology product companies, like Instagram or Apple, that employ engineers to build their products, services or media, which are then consumed by ordinary people.

Finally, there are truly technology companies that produce new technology that is used by all the previous three groups, as well as by the technology companies themselves. From the business standpoint, this technology may be supplied either in the form of on-the-spot consulting work, licensing or even separate products.

Every group has some percentage of technology work in its operation. This work, often called R&D, comprises of implementation of existing technology (D in R&D) and creation of the new one (R). The share of the two differs substantially between the groups. The companies from the first one may be 1 to 10% dependent on R&D work and have almost 0% of R in it, the second group is 90% R&D work, still, with mere percents of R in it, the third group is just 30-50% R&D, and the share of R in it may rise to 10-20% but rarely more, and the last group should have 90% R&D with >50% R in it.

A technology company should be a thought leader in its sphere. This means not chasing fashions in our pop-culture-like industry but setting an example justified by technological excellence instead of marketing. This means building something that will last and have an impact for a substantially longer period of time than the ever-accelerating hype cycle. This means having an ultimate goal of solving hard technical problems and not chasing profits or market share. While product companies try to change the world by producing their innovative products that merely use technology, a technology company does that by producing technology that enables more innovative products. A closed vs an open approach.

10x Programmers

There's this popular meme of 10x programmers that constantly spurs discussion and flamewars among our peers. Is it just fad, who are those 10xers, do they really exist?

Let's first consider this question from the perspective of other crafts and professions. Are there 10x painters? Well, if we compare painter productivity by the number of pieces drawn it would be hard to tell. But if you think about price, clearly, there are even 1000x ones: an ordinary painter's work may cost $1000, and a famous masterpiece will be in the millions. If we consider the number of people reached the same rule applies: maybe, thousands will see quality works of a common professional painter, and millions or even billions - the works of a master. But you may say that painting, unlike programming, is an art. What about carpentry? Well, I'd compare with professions that require mostly intellectual work. Are there 100x doctors? Surely, there are those who saved 100x more people by inventing a new operation method or treatment. Lawyers? A person who writes a law impacts orders of magnitude more than an ordinary counselor at some random firm. This list may be continued on and on.

I've compiled a book called "Interviews with 100x programmers". To some extent, the name was an exaggeration. But, as they say, every joke has some truth in it. In fact, I fully subscribe to the 10x programmer concept. Moreover, I consider that there are not only 10x ones but also 100x, 1000x... Definitely, there are hardly any 10x coders, i.e. people who produce 10x the amount of code a good professional programmer will create in the same timeframe. But there's much more to programming than merely writing program code.

To be an order of magnitude more productive means to solve problems an order of magnitude more complex than the ones considered accessible at a given point in time. Obviously, such problems exist, and there will, probably, always be an unlimited supply of them. Also, it should be clear from the short history of computing that there are some people capable of bringing a new perspective, coming up with approaches that allow solving such problems either in a much better way or just solve them at all. As Alan Kay, who's for sure one of such 100x programmers, has famously said: "A change in perspective is worth 80 IQ points."

Still, there's more to it than just solving harder problems. Another popular explanation given to the 10x thing is that such a programmer is the one who makes 10 other programmers 2x more productive. This, from my point of view, implies the one who is showing a better approach, in other words, a thought leader, and the one who implements this vision in some technology that other programmers use. In fact, we're productive in our work at our current level mostly thanks to such prolific programmers: every day I use Unix, Emacs, Lisp, git and other tools that were initially conceived and built by a handful of the 10x programmers. Their vision and impulse made thousands and even millions more productive.

Those 10x programmers are the ones I'd like to be around at work. And so, my ideal company is the one that attracts such persons. And although a significant percent of such people are loners, most of them are also highly motivated by the presence of similar colleagues.

So which one of the 4 company types mentioned above will such people choose?

The first one is mostly out of consideration because in it the programmers are not the primary value creators - on the contrary, often they are considered a cost center. I.e. they are just another service function similar to an accountant or a janitor. Surely, there are exceptions to this rule when the company leaders realize the potential that technology change bears to their company, which, basically, means that the firm is transitioning to type 3. Even in such case, it's still a much less productive environment than a type 3 firm built with the right principles in mind from the start.

What about outsourcing companies? Their advantage is that programmers are their primary asset, which means that the company will be built around them, have a substantial number of them and will do a lot to attract and hold prominent people. The nature of work, unfortunately, is usually a severely limiting factor here. First of all, in most of the cases, the customer doesn't really care about the technological excellence or innovative nature of the result. The projects are in most of the cases counter-innovative, i.e. the more mundane, reproducible, and ordinary the technological solution that achieves the desired result is the better. And it's quite reasonable from the business standpoint: innovation is risky. This means that, ultimately, such companies reward uniformity and interchangeability of their stuff and their output, especially, since it's much easier to manage and scale. Have I mentioned that managing programmers is very hard (the common metaphor used is "herding cats")?

Now, let's look at product companies. Are they a heaven for 10x programmers? Well, a lot of such people flock there. One reason is that such companies understand the need for talented programmers because unlike the previous 2 types they may and should face unique technological challenges, and, moreover, their leadership is able to recognize that (type 1 companies also face those challenges, but usually they just don't view them from the technology standpoint). Yet, a product company is only X% new technology and another (100-X)% other things. What is the value of X? Maybe, it's 20-30% at Google or Facebook, and even less at smaller companies with fewer resources. Why? Because, as we discussed above, the ultimate goal of most of such companies is making money by serving masses of customers. This requires huge marketing, sales, operations, and support "vehicles" that employ professionals to operate and programmers to build, maintain and develop. But have quite little interesting technical challenges. Once again, this is the right thing from the business standpoint, especially if you have to earn more and more money each year and grow your market share. But focus on earnings and market share means that technological excellence becomes secondary. Surely, the best of the leaders and managers realize its importance, but they have to make many trade-offs all the time.

That's why I have singled out "pure" technology companies. Such organizations are naturally inclined to make tech excellency their focus. There are, surely, counterexamples that are infected with the Silicon Valley "growth virus" and try to win the market as fast as possible with marketing, but it doesn't mean that it always has to work that way. In my opinion, purely technological companies are the best place for 10x programmers because they will not merely utilize their work to some other end goal but have vested interest in amplifying its influence. They are not inclined to conceal the know-hows and innovations as trade secrets, but will benefit from sharing and promoting them. They may also provide maximum freedom of choice: of approaches, tools, supporting technologies, because their primary concern is not effective scaling of the same ultimately repetitive work to many similar programmers but creating breakthroughs. Their dependence on such ultra-productive programmers is existential.

I don't consider myself to be a 10x programmer, but, surely, I'd like to reach such level someday and I also aspire to work alongside them.

A Company I'd Build

All in all, being part of a technology company seems like the best choice for me both in terms of potential impact and possibilities to have 10x programmer colleagues. Eventually, either you have to join one or create one yourself. For the last 5 years, I've been working in the so-called AI, and my experience both from product company side and individual consultant work shows that demand for research-related technology expertise here is growing much faster than the supply. I see it as a chance for new technology companies to emerge and gather those few capable people in this field to amplify their impact. So I'm seriously considering starting a technology company, and I'm looking for like-minded people who share my values and vision to join our forces.

If I were to start such company, I'd build its foundation on a few things that really matter to me personally. Some principles or, as they used to call them, values. Unfortunately, the notion of "values" has somewhat lost its original meaning in the corporate world. When you see such qualities as effectiveness or adaptability cast as values that's a sign of such misconception. Values are something that you don't compromise upon at all. Surely, it's pointless to compromise any parts of your professionalism (such as effectiveness), so professionalism is a default value not even worth discussing. Real "values", however, are those aspects of your work culture that run a real risk of conflicting with the things that are considered universally important. In business, those are profits, market share, favorable competitive position. So, being true to your values means not forfeiting them even if you're going to lose in those basic areas.

Here is a list of the values that I subscribe to:

  • Technological excellence should be a basic trait of any technology company. For me, an example of applying such value would be using Lisp as a starting point for most of the solutions despite the fact that the language is quite unpopular and underappreciated - my personal experience shows that it works very well, especially in the fields that are heavily knowledge-based. Another example is that in a technology company literally everyone should be technology-savvy: even the office manager should be programming at times.
  • Personalism is the main quality that a company has to support in its dealings with all the people it's interacting with: employees, customers, contractors and providers. This means, for example, striving to provide flexible and productive working conditions to each employee instead of trying to fit everyone in the same conditions (because management is hard). Overall, lack of management competency should never become a limiting factor. One manifestation of this is that a modern technology company should be built as a distributed organization from day 1.
  • Ahimsa is an ancient word meaning not harming anyone. It is a little bit more than our modern-day ethics, but it's worth it. Why create something if you know that it will cause misery and suffering to others? In effect, this means, for example, refusal to provide services to companies that are clearly unethical.
  • Radical openness. As they say, "information wants to be free." :) Maximal sharing and minimal secrecy makes so many things much simpler. And in our lowest-common-denominator technology world, ultimately, the risk of competitors copying and abusing your work is much less than that of brilliant people not joining your cause because they just haven't heard of it.

So... If you're interested in solving complex AI challenges out of whatever part of the world you're living in, working with 10x programmers, using Lisp and other advanced technologies in the process - drop me a line, I'd be glad to chat.

2016-05-17

Improving Lisp UX One Form at a Time

At the recent ELS, I presented a lightning talk about RUTILS and how I see it as a way of "modernizing" CL, i.e. updating the basic language elements to be simpler, clearer and more generic. Thus improving the everyday user experience and answering the complaints of outsiders about "historical cruft" in the Lisp standard. Indeed, Lisp has a lot of unrecognizable names (like mapcar and svref) or just unnecessary long ones (multiple-value-bind or defparameter), and out-of-the-box it lacks a lot of things that many current programmers are used to: unified generic accessors, generators, literal syntax for defining hash-tables or dynamic vectors etc. This may not be a problem for the people working with the language on a regular basis (or if it is they probably have a personal solution for that already), but it impedes communication with the outside world. I'd paid extra attention to that recently as I was preparing code examples for the experimental course on algorithms, which I teach now using Lisp instead of pseudocode (actually, modulo the naming/generics issue, Lisp is a great fit for that).

Unfortunately, the lightning talk format is too short for a good presentation of this topic, so here's a more elaborate post, in which I want to show a few examples from the RUTILS library of using Lisp's built-in capabilities to introduce clear, uniform, and generic syntactic abstractions that may be used alongside the standard Lisp operators, as well as replace them in the cases when we want to get more concise and understandable code.

What's cool about this problem is that, in Lisp, besides a common way to extend the language with functions and methods (and even macros/templates, which find they way into more and more languages), there are several other approaches to the problem that allow to tackle issues that can't be covered by functions and even macros. Those include, for instance, reader macros and aliasing. Aliasing is, actually, a rather simple idea (and can be, probably, implemented in other dynamic languages): duplicating functionality of existing functions or macros with a new name. The idea for such operator came from Paul Graham's "On Lisp" and it may be implemented in the following way (see a full implementation here):


(defmacro abbr (short long &optional lambda-list)
  `(progn
     (cond
      ((macro-function ',long)
       (setf (macro-function ',short) (macro-function ',long)))
      ((fboundp ',long)
       (setf (fdefinition ',short) (fdefinition ',long))
       ,(when lambda-list
          `(define-setf-expander ,short ,lambda-list
             (values ,@(multiple-value-bind
                           (dummies vals store store-form access-form)
                           (get-setf-expansion
                            (cons long (remove-if (lambda (sym)
                                                    (member sym '(&optional &key)))
                                                  lambda-list)))
                         (let ((expansion-vals (mapcar (lambda (x) `(quote ,x))
                                                       (list dummies
                                                             vals
                                                             store
                                                             store-form
                                                             access-form))))
                           (setf (second expansion-vals)
                                 (cons 'list vals))
                           expansion-vals))))))
      (t (error "Can't abbreviate ~a" ',long)))
     (setf (documentation ',short 'function) (documentation ',long 'function))
     ',short))

As you may have noticed, it is also capable of duplicating a setf-expander for a given function if the lambda-list is provided. Using abbr we can define a lot of shorthands or alternative names, and it is heavily used in RUTILS to provide more than 50 alternative names; we'll see some of them in this post. What this example shows is the malleability of Lisp, which allows approaching its own improvement from different angles depending on the problem at hand and the tradeoffs you're willing to make.

Introducing generic element access

One of the examples of historic baggage in CL is a substantial variety of different methods to access elements of collections, hash-tables, structures, and objects with no generic function unifying them. Not to say that other languages have a totally uniform accessor mechanism. Usually, there will be two or three general-purpose ways to organize it: dot notation for object field access, something square-braketish for array and other collections access, and some generic operator like get for all the other cases. And occasionally (e.g. in Python or C++) there are hooks to plug into the built-in operators. Still, it's a much smaller number than in Lisp, and what's more important, it's sufficiently distinct and non-surprising.

In Lisp, actually, nothing prevents us from doing even better — both better than the current state and than other languages — i.e. from having a fully uniform and extensible solution. At first approximation, it's just a matter of defining a generic function that will work on different container types and utilize all the existing optimized accessor functions in its methods. This interface will be extensible for any container object. In RUTILSX (a part of RUTILS where any experiments are allowed) this function is called generic-elt:


(defgeneric generic-elt (obj key &rest keys)
  (:method :around (obj key &rest keys)
    (reduce #'generic-elt keys :initial-value (call-next-method obj key))))

One important aspect you can see in this definition is the presence of an :around method that allows to chain multiple accesses in one call and dispatch each one to an appropriate basic method via call-next-method. Thus, we may write something like (generic-elt obj 'children 0 :key) to access, for instance, an element indexed by :key in a hash-table that is the first element of a sequence that is the contents of the slot children of some object obj.

The only problem with this function is its long name. Unfortunately, most of good short element access names, like elt and nth are already taken in the Common Lisp standard, while for RUTILS I've adopted a religious principle to retain full backward compatibility and don't alter anything from the standard. This is a critical point: not redefining CL, but building on top of it and extending it!

Moreover, element access has two features: it's a very common operation and it's also not a usual function that does some computation, so ideally it should have a short but prominent look in the code. The perfect solution occurred to me at one point: introduce an alias ? for it. Lisp allows to name operations with any characters, and a question mark, in my opinion, matches very well the inner intent of this operation: query a container-like object using a certain key. With it, our previous example becomes very succinct and cool: (? obj 'children 0 :key).

Additionally to element reading, there's also element write access. This operation in Lisp, like in most other languages, has a unified entry point called setf. There's a special interface to provide specific "methods" for it based on the accessor function. Yet, what to do when an access function is polymorphic? Well, provide polymorphic setter companion. (defsetf generic-elt generic-setf). Like generic-elt, generic-setf defers work to already defined specific setters:


(defmethod generic-setf ((obj list) key &rest keys-and-val)
  (setf (nth key obj) (atomize keys-and-val)))

And it also supports key chaining, so you can write: (setf (? obj 'children 0 :key) new-value).

Having this unified access functionality is nice and cool, but some people may still linger for the familiar dot object slot access syntax. We can't blame them: habits are a basis of good UX. Unfortunately, this is contrary to the Lisp way... But Lisp is a pro-choice and future-proof language: if you want something badly, even something not in the usual ways, almost always you can, actually, find a clean and supported means of implementing it. And this case is not an exception. If you can tolerate an small addition — a @-prefix to the object reference (that's also an extra prominent indicator of something unusual going on) — when accessing its slots you can define a reader macro that will expand forms @obj.slot into our (? obj 'slot) or a standard (slot-value obj 'slot). With it, we can write something like (? tokens @dep.govr.id), which is much more succinct and, arguably, readable than (elt tokens (slot-value (slot-value dep 'govr) 'id)).

Still, one issue remains unsolved in this approach: the preferred Lisp slot-access method is not via slot-value, but with an accessor method that is exported. And one of the reasons for it is that slot-names, which are usually short and can clash, are kept private to the package where they are defined. It means that in most cases @obj.slot will not work across packages. (Unlike the OO-languages in which every class is its own namespace, in Lisp, this function is not "complected" within the OO-system, and packages are a namespacing method, while objects serve for encapsulation and inheritance.)

There are two ways to tackle this problem. As I said, Lisp is future-proof: being thoroughly dynamic and extensible, CLOS defines a method that is called when there's a problem accessing an object's slot — slot-missing. Once again, we can define an :around method that will be a little smarter (?) and try to look up slot-name not only in the current package, but also in the class' original package.


(defmethod slot-missing :around
    (class instance slot-name (operation (eql 'slot-value)) &optional new-value)
  (declare (ignore new-value))
  (let ((class-package (symbol-package (class-name (class-of instance)))))
    (if (eql class-package (symbol-package slot-name))  ;; to avoid infinite looping
        (call-next-method)
        (if-it (find-symbol (string-upcase slot-name) class-package)
               (slot-value instance it)
               (call-next-method)))))

This is a rather radical way and comes at a cost: two additional virtual function calls (of the slot-missing method itself and an additional slot-value one). But in most of the cases it may be worth paying it for convenience's sake, especially, since you can always optimize a particular call-site by changing the code to the most direct (slot-value obj 'package::slot) variant. By the way, using slot accessor method is also costlier than just slot-value, so we are compensating here somewhat. Anyway, it's cool to have all the options on the table: beautiful slow and ugly fast method that our backward-compatibility approach allows us. As usual, you can't have a cake and eat it too...

Though, sometimes, you can. :) If you think more of this it becomes apparent that slot-value could be implemented this way from the start: look up the slot name in the class'es original package. As classes or structs are defined together with their slots it is very rare if not almost impossible to see slot-names not available in the package where their class is defined (you have to explicitly use a private name from another package when defining a class to do such a trick). So, slot-value should always look for slot names in the class'es package first. We can define a "smart" slot-value variant that will do just that, and with our nice generic-elt frontend it can easily integrated without breaking backward-compatibility.


(defun smart-slot-value (object slot-name)
  (slot-value object
              (or (find-symbol (string-upcase slot-name)
                               (symbol-package (class-name (class-of instance))))
                  slot-name)))

Unifying variable binding with with

Almost everything in functional variable definition and binding was pioneered by Lisp at some point, including the concept of destructuring. Yet, the CL standard, once again, lacks unification in this area. There are at least 4 major constructs: let and let*, destructuring-bind and multiple-value-bind, and also a few specialized ones like with-slots or ppcre:register-groups-bind. One more thing to mention is that parallel assignment behavior of plain let can be implemented with destructuring-bind and multiple-value-bind. Overall, it just screams for uniting in a single construct, and already there have been a few attempts to do that (like metabang-bind). In RUTILS, I present a novel implementation of generic bind that has two distinct features: a more plausible name — with — and a simple method-based extension mechanism. The implementation is very simple: the binding construct selection is performed at compile-time based on the structure of the clause and, optionally, presence of special symbols in it:


(defmacro with ((&rest bindings) &body body)
  (let ((rez body))
    (dolist (binding (reverse bindings))
      (:= rez `((,@(call #'expand-binding binding rez)))))
    (first rez)))

A very short number of methods covering the basic cases are defined:

  • the first one expands to let or multiple-value-bind depending on the number of symbols in the clause (i.e. for multiple values you should have more than 2)
  • the second group triggers when the first element of the clause is a list and defaults to destructruing-bind, but has special behaviors for 2 symbols ? and @ generating clauses for our generic element access and smart slot access discussed in the previous section

(defun expand-binding (binding form)
  (append (apply #'bind-dispatch binding)
          form))

(defgeneric bind-dispatch (arg1 arg2 &rest args)
  (:method ((arg1 symbol) arg2 &rest args)
    (if args
        `(multiple-value-bind (,arg1 ,arg2 ,@(butlast args)) ,(last1 args))
        `(let ((,arg1 ,arg2)))))
  (:method ((arg1 list) (arg2 (eql '?)) &rest args)
    `(let (,@(mapcar (lambda (var-key)
                       `(,(first (mklist var-key))
                         (? ,(first args) ,(last1 (mklist var-key)))))
                     arg1))))
  (:method ((arg1 list) (arg2 (eql '@)) &rest args)
    (with-gensyms (obj)
      `(let* ((,obj ,(first args))
              ,@(mapcar (lambda (var-slot)
                          `(,(first (mklist var-slot))
                            (smart-slot-value ,obj ',(last1 (mklist var-slot)))))
                        arg1)))))
  (:method ((arg1 list) arg2 &rest args)
    `(destructuring-bind ,arg1 ,arg2)))
In a sense, it's a classic example of combining generic-functions and macros to create a clean and extensible UI. Another great benefit of using with is reduced code nesting that can become quite deep with the standard operators. Here's one of the examples from my codebase:

(with (((stack buffer ctx) @ parser)
       (fs (extract-fs parser interm))
       (((toks :tokens) (cache :cache)) ? ctx))
  ...)
And here's how it would have looked in plain CL:

(with-slots (stack buffer ctx) parser
  (let ((fs (extract-fs parser interm)))
        (toks (gethash :tokens ctx))
        (cache (gethash :cache ctx)))
    ...))

Implementing simple generators on top of signals

One of my friends and a Lisp enthusiast, Valery Zamarayev, who's also a long-time Python user, once complained that the only thing that he misses in CL from Python is generators. This feature is popular in many dynamic languages, such as Ruby or Perl, and even Java 8 has introduced something similar. Sure, there are multiple ways to implement lazy evaluation in Lisp with many libraries for that, like SERIES, pygen or CLAZY. We don't have to wait for another version of the spec (especially, since it's not coming 8-)

In RUTILS I have discovered, I believe, a novel and a very clean way to implement generators — on top of the signal system. The signal or condition facility is, by the way, one of the most underappreciated assets of Common Lisp that often comes to rescue in seemingly dead ends of control flow implementation. And Kent Pitman's description of it is one of my favorite reads in Computer Science. Anyway, here's all you need to implement Python-style generators in Lisp:


(define-condition generated ()
  ((item :initarg :item :reader generated-item)))

(defun yield (item)
  (restart-case (signal 'generated :item item)
    (resume () item)))

(defmacro doing ((item generator-form &optional result) &body body)
  (with-gensyms (e)
    `(block nil
       (handler-bind ((generated (lambda (,e)
                                   (let ((,item (generated-item ,e)))
                                     ,@body
                                     (invoke-restart (find-restart 'resume))))))
         ,generator-form)
       ,result)))

The doing macro works just like dolist, but iterating the generator form instead of an existing sequence. As you can see from this example, restarts are like generators in disguise. Or, to be more correct, they are a more general way to handle such functionality, and it takes just a thin layer of syntactic sugar to adapt them to a particular usage style.

And a few mischiefs

We have seen three different approaches to extending CL in order to accommodate new popular syntactic constructs and approaches. Lastly, I wanted to tread a little in the "danger zone" that may be considered unconventional or plain bad-style by many lispers — modifying syntax at the reader level. One thing that Clojure (following other dynamic languages before it), I believe, has proven is the importance of shorthand literal notation for popular operations. CL standard has predated this understanding: although it has specific print representations for various important objects, and even a special syntax for static arrays. Yet, the language is really future-proof in this respect, because it provides a way to hook into the reader mechanism by modifying the readtables. It was further smoothed and packaged by the popular NAMED-READTABLES library, which allows to treat readtables similar to packages. In RUTILS I have defined several extended readtables that implement a few shortcuts that are used literally in every second function or macro I define in my code. These include:

  • a shorthand notation for zero-, one- or two-argument lambda functions: ^(+ % %%) expands into (lambda (% %%) (+ % %%))
  • a literal syntax for hash-tables: #h(equal "key" "val") will create a EQUAL-hash-table with one key-value pair
  • a syntax for heredoc-strings: #/this quote (") shouldn't be escaped/# (which, unfortunately, doesn't always work smoothly in the repl)

Overall, I have experimented a lot with naming — it was sort of my obsession in this work to find short and obvious names for new things, many of which substitute the existing functionality, under the constraints of not altering what's already in the standard. For this sake, I've ventured into non-character symbols and even the keyword package — a major offence, I reckon... And here are a few of the findings I wanted to share (besides ? and with mentioned previously):

  • call is a new alias for funcall — I suppose, in the 70's it was a really fun experience to call a function hence the name, but now its too clumsy
  • get#, set#, and getset# are aliases and new operations for #-tables (when you can't or won't use ? for that)
  • finally, the grandest mischief is := (alongside :+, :-, :*, :/), which is an alias for setf (and, you've guessed it, incf etc). The justification for this is that everyone is confused about the -f, that setting a variable is a very important operation that we should immediately notice in our clean and functional code ;), and that := is a very familiar syntax for it even used by some languages, such as Pascal or golang. It may be controversial, but it's super-convenient.

The only thing I failed to find a proper renaming for so far is mapcar. It is another one of those emblematic operations that should be familiar to everyone, yet -car creates confusion. For now, I resist the temptation to rename map into map-into and make map smarter by using the first sequence's type for the result expression. However, there's no plausible alternative variant I was able to find even among the zoo of other language's naming of this concept. Any thoughts?

PS. Those were a few prominent examples, but RUTILS, in fact, has much more to offer. A lot of stuff was borrowed from other utility projects, as well as implemented from scratch: anaphoric operators, the famous iter — a replacement for loop, Clojure-style threading macros, a new semantic pair data type to replace cons-cells, lots of utilities to work with the standard data structures (sequences, vectors, hash-tables, strings) making them truly first-class, iteration with explicit indices etc etc. With all that in the toolbox, there's now no ground to claim that Lisp is in any aspect inferior in terms of day-to-day UX compared to some other language, be it Haskell, Ruby or Clojure. Surely, I'm not talking about the semantic differences here.

2016-05-10

European Lisp Symposium 2016

The last two days, I'm at the ELS2016. So far, it's being a great experience - I've actually forgotten the joy of being in one room with several dozens of Lisp enthusiasts. The peculiarity of this particular event is that it's somewhere in the middle between a scientific conference, like ACL, that I had a chance to attend in the recent years thanks to my work at Grammarly, and a tech gathering: it employs the same peer reviewed approach and a scientific presentation style you will find at the research conferences, but most of the topics are very applied and engineering-related.

Anyway, the program was really entertaining with several deep and insightful presentations (here are the proceedings). The highlights for me were the talks on the heterogenous sequences type-checker implementation based on the Lisp declare facility (that I'm growing more and more fond) by Jim Newton and a presentation of an image-processing DSL that's an excellent example of the Lisp state-of-the-art approach in DSL design by Kai Selgrad. Other things like a description of the editor buffers protocol, local variables preservation technic were also quite insightful. And other good stuff is coming...

It's also great to hear new people bringing fresh ideas alongside old-timers sharing their wisdom and perspective - one of the things I appreciate in the Common Lisp community.

Near the end, I'm going to present a lightning talk about RUTILS and how I view it as a vehicle for evolving the Common Lisp user experience.

2016-01-03

КПИ no more

Это последний год, который я читаю в КПИ курс "Операционные системы". Пролистав архив переписки, я сделал вывод, что начал это делать в 2009 году, т.е 6 лет назад, и за это время через меня прошло более 500 студентов. Выходит, я проработал преподавателем уже больше, чем проучился в институте, иными словами мой долг перед альма матер можно считать исполненным :)

В этом тексте я хочу описать свой опыт и ответить на вопрос, почему решил уйти. Начнем с конца: потому что, кроме меня, это, по большому счету, никому не нужно. А у меня с каждым годом все меньше и меньше времени делать никому не нужные вещи.

А теперь по порядку.

Шесть лет назад я начинал создавать этот курс с чистого листа. Что мне нравилось, это то, что был полный карт-бланш для экспериментов и выбора методик преподавания, и это дало возможность попробовать много всего и понять, что работает (для меня), а что нет. Для студентов это не всегда было благоприятно, т.к. далеко не все эксперименты были успешными, но, все же, я считаю, что это лучше, чем то, что было у нас, когда этот курс просто спускался на тормозах (это, собственно, и была моя изначальная мотивация прийти читать его). Каждый год я ставил себе условную оценку за проделанную работу, и если вначале это была твердая двойка, то сейчас, я считаю, что это минимум 4 или 4+ (в прошлом году я также попросил студентов поставить мне оценку, и у них тоже в среднем вышла четверка).

В целом, курсом я преследовал такие цели:

  • ввести студентов в парадигму системного программирования, показать ее интересные стороны и задачи
  • дать им альтернативный взгляд на разработку ПО (а не только ООП и C#, которые являются основными на нашей кафедре)
  • научить работать с Unix-средой и консолью
  • научить не боятся ассемблера и, вообще, низкоуровневых вещей
  • чуть-чуть познакомить с новыми языками прогарммирования, которые актуальны для системной разработки
  • познакомить с опен-сорсом
Не все из этих целей я достигал в рамках курса в тот или иной год: иногда получалось лучше что-то одно, иногда другое, но, думаю, что все они акутальны. Кроме того, если задаться целью, то на основе этого курса легко можно сделать продвинутое продолжение — "Разработка ОС" (аналог MIT Operating System Engineering). За 6 лет удалось собрать достаточно материала, который доступен в виде конспекта и заданий (а также исходников к ним). Более того, в качестве побочного продукта я разработал небольшую систему публикации материалов (свой leanpub), а также тестирования теории. Единственное, до чего так и не дошли руки — это система автоматического тестирования лабораторных. Если придумать, как эффективно масштабировать такую штуку, то это был бы, действительно, золотой грааль, но, к сожалению, основная работа тут, кажется, все равно будет заключаться в написании ручных тестов. А главный закон преподавателя: ручная проверка практических работ — самый большой убийца мотивации...

Почему это никому не нужно в КПИ?

Четыре года назад я написал колонку на ДОУ "Украинский Стенфорд", в которой изложил свой ограниченный взгляд на проблемы, вызовы и возможности нашего высшего технического образования. С тех пор ситуация конкретно в КПИ скорее ухудшилась: ушли многие из старых профессоров, многие из хороших молодых преподавателей также по разным причинам не задержались, так что еще лет 5 и на ФИВТе преподавать, похоже, останутся только люди, не имеющие особого отношения ни к индустрии, ни к науке. Впрочем, это не значит, что такая ситуация везде: мне кажется, сейчас достаточно 1-2 ориентиованных на модернизацию людей в руководстве какого-то факультета или кафедры, чтобы организовать там вполне качественное обучение (все остальное, в принципе, есть). Иными словами, с моей точки зрения основным тормозом изменений университета сейчас является его руководство (на всех уровнях). В связи с этим интересно посмотреть, как будет развиваться ситуация в ХНУРЕ, куда ректором пришел Эдуард Рубин...

Что также интересно, внешне КПИ меняется в лучшую сторону. Хорошо развивается кампус, причем в этот процесс активно включились студенты с такими проектами, как БелкаВежа или Радио КПИ. Много движения в культурной и социальной жизни (вопреки инерции системы). Отличная инициатива — Летняя школа, которая проходит уже 10 лет и в которой я участвовал последние 2 года. В прошом году мы даже провели TEDxKPI! Обычно, такие позитивные внешние проявления следуют за изменением внутренних процессов, но тут имеет место несколько иная динамика: университет — это по определению открытая система, которая постоянна испытывает приток новой крови, и среди этой новой крови действуют те же тренды, что и по всей стране ("бери и делай"). Но, в то же время, с такой же легкостью, с которой новая энергия прибывает сюда, она здесь и надолго не задерживается: активным студентам почти нет стимула оставаться в аспирантуре, а для многих преподавателей это, фактически, волонтерство (например, моя зарплата в КПИ более чем в десять раз меньше тех денег, которые я могу заработать в индустрии), которое почти всегда не стабильно. Именно поэтому я говорю о том, что при ситуацию можно было бы поменять при правильной ориентации руководства: на улучшение качества студентов (за счет их количества), поддержку новых инициатив, уменьшение бюрократии.

Однако, к сожалению, стратегического видения развития университета нет.

С моей точки зрения, есть 2 рабочих модели высшего образования:

  • элитарная, когда отбирается небольшое количество самых талантливых и мотивированных студентов и преподаватель работает с ними индивидуально (к ней есть хороший "анекдот" про астрофизика, который читал свой курс в какой-то далекой обсерватории только для двух студентов, оба из которых потом стали Нобелевскими лауреатами)
  • массовая, когда набирается большая группа студентов и их всех подтягивают до какого-то базового уровня

Очевидно, что КПИ реализовывает второй подход: на последнем потоке второго курса, которому я читал, учится около 100 человек. И таких потоков по направлению компьютерных наук в университете несколько. Но чтобы массовая система работала, она должна быть действительно системой (в которой нет слабых звеньев). В первую очередь, студенты должны быть мотивированы. По принципу кнута и пряника.

Позитивной мотивацией должно быть желание получить современную и перспективную специальность, а в процессе делать интересные и прикольные штуки, а негативной — реальная возможность вылететь. К сожалению, в КПИ обе эти мотивации недоразвиты. По большому счету, в наших реалиях на первом и втором курсе нужно выгонять минимум 20% студентов (примерно столько людей у меня на курсе вообще ничего не делает по ходу семестра и начинают пытатся что-то сдать в лучшем случае к его концу, если не к сессии). Но систематической политики выгонять нет, скорее, наоборот, есть вялое сопротивление тем, кто пытается это делать.

Что до позитивной мотивации, то в КПИ ее перебивает передающаяся из поколения в поколения совковая традиция этого университета, который можно выразить несколькими популярными у студентов мемами:

  • главное — это сдать зачет/сессию/получить диплом (и для этого хороши все способы, в том числе обман)
  • то, чему нас учат, никогда не понадобиться в реальной жизни
  • лучший друг студента — это шара
Но хорошая новость в том, что спрос на качественное техническое образование есть и он никуда не денется, и чем больше будут деградировать существующие институции, тем больше места будет открываться для новых начинаний и форм. Я думаю, что в течение ближайших 5 лет у нас появится минимум 1 технический "университет" нового образца, в котором можно будет получить образование на мировом уровне (как я написал, для этого, в принципе, есть всё, кроме некоторой доли лидерства). Я также надеюсь, что сам смогу чем-то помочь в этом. Но, чтобы начать что-то новое, нужно сначала завершить старое. Жаль только, буду скучать за парком КПИ, тополями и каштанами...

2015-06-26

Running Lisp in Production at Grammarly


We have written a blog post describing almost 3 years of our Lisp in production experience at Grammarly. Here's a small abstract for it.

At Grammarly, the foundation of our business, our core grammar engine, is written in Common Lisp. It currently processes more than a thousand sentences per second, is horizontally scalable, and has reliably served in production for almost 3 years.

We noticed that there are very few, if any, accounts of how to deploy Lisp software to modern cloud infrastructure, so we thought that it would be a good idea to share our experience. The Lisp runtime and programming environment provides several unique, albeit obscure, capabilities to support production systems (for the impatient, they are described in the final chapter).

Continue to the full text »

2015-04-14

Announcing SHOULD-TEST


Once upon a time, it occurred to me that all sound software should be slightly self-ironic. That is how this library's name came into being: yes, you should test even Common Lisp code sometimes. :) But that's not the whole irony...

So, y u makes YATF?

Testing software always fascinated me because it is both almost always necessary and at the same time almost always excessive - it's extremely hard to find the right amount of resources you should allocate to it. You will most likely end up fearing to change your system either because you have too few tests, and some of the important scenarios aren't covered, or too many tests and you need to be constantly re-writing them. Surely, in Lisp the problem is not so drastic because in many cases you can rely on the REPL to help, but it's not a one-fit-all solution. There's also too much dogma in the space of general error handling in programming (that I addressed a little bit in this post). So, to find out how to test properly, around 7 years ago I had written my first test framework, which was called NUTS (non-unit test suite). It worked ok, and I used it in a couple of projects including the huge test suite of CL-REDIS that I'm really proud of. However, it was the first version, and you always have to re-write the first version. :) This is how MUTEST (microtest) appeared. In it, I was aiming at making a tool with the smallest footprint possible. It was also partially inspired by RT, which I consider to be the simplest (with a positive connotation) Lisp test framework (before ST). But both of them, MUTEST and RT, are not lispy because they are not extensible, and it's a shame to not have extensibility in Lisp, which provides excellent tools for building it in.

Well, "version 2 always sucks, but version 3..." So, SHOULD-TEST is version 3, and I'm really happy with it. It's truly minimal and intuitive to the extreme: like in the popular BDD approach you just write (in Yodaspeak, obviously): should be = 1 this-stuff and then st:test. And it's extensible - you can add specialized assertion strategies to the provided 3 basic ones: normal testing, exception catching, and capturing output streams.

I wasn't content with the existing Lisp test frameworks because they aren't concerned first and foremost with the things I care about:

  • intuitive defining and running arbitrary tests
  • testing from the REPL and ease of analyzing the test output
  • piping the test output to upstream systems like CI (by supporting common protocols, such as xUnit and TAP)

These are the 3 things that SHOULD-TEST should do the best.

Over more than a year, I have written or re-written with it the whole test suites for the main open-source libraries I support - RUTILS, CL-REDIS, and CL-NLP (which doesn't yet have an extensive test coverage). And I also use it for all my in-house projects.

Working with ST

Here's a quick overview of the SHOULD-TEST workflow.

Test are defined with deftest:

(deftest some-fn ()
  (should be = 1 (some-fn 2))
  (should be = 2 (some-fn 1)))

Being run, the defined test returns either T or NIL as a primary value. Secondary and third values in case of NIL are lists of:

  • all failed assertions returned by individual assertions
  • and all uncaught errors signaled inside assertions

should is a macro that takes care of checking assertions. If the assertion doesn't hold should signals a condition of types should-failed or should-erred which are aggregated by deftest. Also, should returns either T or NIL and a list of a failed expression with expected and actual outputs as values.

Under the hood, should calls the generic function should-check and passes it a keyword produced from the first symbol (in this case, :be), a test predicate (here, '=), and a tested expression as thunk (here it will be e.g. (lambda () (some-fn 1))), and expected results if any. If multiple expected results are given, like in (should be eql nil #{:failed 1} (some-other-fn :dummy)), it means that multiple values are expected. As you see, the keyword and test predicate are passed unevaluated, so you can't use expressions here.

The pre-defined types of assertions are be, signal, and print-to. They check correspondingly.

deftest and should write the summary of test results to *test-output* (by default bound to *standard-output*). The var *verbose* (default T) controls if the summary contains full failure reports or just test names.

Tests are defined as lambda-functions attached to a symbol's test property, so (deftest some-fn ... will do the following:

(setf (get some-fn 'test)
      (lambda () ...))
One feature that is pending implementation is establishing dependencies between tests while defining them, i.e. specifying the partial order in which they should be run. However, I haven't seen heavy demand for it in my test code so far.

To run the tests, use test. Without arguments, it runs all the tests in the current package. Given a :package argument it will do the same for that package, and given a :test argument it will run that individual test. In case of individual test's failure, it will return NIL and a list of failed assertions and a list of assertions, which triggered uncaught errors. In case of failed test of a package, it will return NIL and 2 hash-tables holding the same lists as above keyed by failed test's names.

As you see, the system uses a somewhat recursive protocol for test results:

  • at the lowest level should returns T or NIL and signals information about the failed assertion
  • this information is aggregated by deftest which will return aggregate information about all the failed assertions in the hash-table
  • at the highest level test will once again aggregate information over all tests

So, the structure of the summary, returned from test, will be the following:

#{
  failed-test-1 ((failed-assertion-1 expected actual)
                 (failed-assertion-2 ...
  failed-test-2 ...
 }

There's also :failed key to test that will re-test only tests which failed at their last run.

Usage patterns

As SHOULD-TEST is agnostic, it doesn't impose any restrictions on how each project organizes its tests. Yet, having established patterns and best-practices never hearts. Below is the approach I use...

There's no restriction on naming tests. Though, it seems like a good approach to name them the same as functions they test. As for generic functions, I have different tests for different methods. In this case, I add some suffix to the test's name to indicate which method is tested (like transform-string for one of the methods of gf transform that is specialized for the string class of arguments).

As for code organization, I use the following directory structure of the typical project:

/project-root
 |----src
 |    `----module
 |         `-----file.lisp
 `----test
      |----some-general-tests.lisp
      `----module
           `-----file-test.lisp

I also usually place the tests in the same package as the code they test but protect them with #+dev guard, so that in production environment they are not compiled and loaded altogether.

ASDF provides a way to define the standard for testing a system that can be invoked with asdf:test-system. The easiest way to hook into this facility is to define the following method for asdf:test-op somewhere either in package.lisp or in some common file in the test module (in the example above: some-general-tests.lisp):

(defmethod asdf:perform ((o asdf:test-op)
                         (s (eql (asdf:find-system <your-system>))))
  (asdf:load-system <your-system>)
  (st:test :package <your-package>))
  t)

There's also a minimal test suite defined in src/self-test.lisp. The test suite is also hooked to asdf:test-op for the should-test system - just as described above :)
Finally, there's an idea that ST will provide useful connector facilities that are mostly lacking in the existing Lisp test frameworks, to be able to integrate into the general testing landscape (primarily, CI systems). As a start, xUnit support was implemented by us (most of the thanks go to Maxim Zholoback). As it often happens, it was, actually, almost impossible to find the proper xUnit spec, but this SO answer saved the day for us. test-for-xunit generates appropriate XML string to *test-output*. I also plan on implementing TAP support some day (this should be pretty easy, actually), but I'm not in a hurry.

Well, if SHOULD-TEST proves useful to some of you, I'd be glad. Enjoy the hacking!

2015-04-07

Креш-курс по Лиспу - кому он будет интересен


В июле должен состояться мой мастер-класс введение в практическую разработку на Common Lisp. По этому случаю меня попросили написать статью в блог компании SmartMe, которая проводит это мероприятие. В ней я попытался ответить на вопрос, кому и зачем сейчас может быть интересно разобраться с Лиспом.

Лисп — один из самых старых и, пожалуй, самый загадочный из современных языков программирования. Также бытует мнение, что он не просто стар, а устарел. Почему это не так и где его ниша, я попробую ответить в этой статье.

Лисп — пожалуй единственный динамический системный язык программирования. И среди динамических языков он остается непревзойденным выбором благодаря следующими свойствам:
  • реальной мультипарадигменности, дающей возможность элегантно совмещать процедурный, объектно-ориентированный, функциональный и другие стили
  • уникальной поддержке метапрограммирования
  • легендарной интерактивной среде разработки
  • железобетонному стандарту языка, за которым стоит многолетняя работа мегаумов МИТа, Xerox PARC, CMU и других подобных мест, оплаченная DARPA
  • обширному набору реализаций (компилятор и среда исполнения), коих разработано за его историю около 25, до 10 из которых активно поддерживаются и развиваются
На самом деле, современное положение Лиспа как языка, который обычно не рассматривают для серьезной разработки, обуcловленно отнюдь не техническими причинами, а лишь исторической случайностью — язык сильно опередил свое время,— и человеческим фактором: он и не выбор по-умолчанию (как С++, Java или JavaScript), и не модная новая технология (как Scala, Go или Ruby), и не имеет за собой какую-либо серьезную организацию или сообщество, которые бы продвигали его использование (как C#, Swift или Rust). Тем не менее, миф о непрактичности Лиспа опровергает как мой опыт использования его в ядре Grammarly и предыдущих моих коммерческих проектах (уже более 7 лет), так и опыт поисковика авиабилетов ITA Software, купленной Гуглом за миллиард долларов, или же португальской Siscog, разработчика решений для железных дорог, в которой работает более полусотни Лисп-программистов. А адепты теории о необходимости его модернизации могут почитать Changelog SBCL (лидирующей open source реализации) :)

Конечно, у Лиспа есть и недостатки — помимо небольшого сообщества, представленного в основном энтузиастами, это:
  • непривичный синтаксис
  • часто непривичные подходы и способы разработки
  • отсутствие библиотек для взаимодействия с остальной средой (проект Quicklisp давно доказал обратное :)
Таким образом, еще раз можно повторить, что язык и экосистема Common Lisp не имеет серьезных технических недостатков при ряде бесспорных преимуществ, но он слишком непривычен и нетипичен, поэтому страдает от проблемы курицы и яйца: отсутствие Лисп-программистов не позволяет начинать на нем серьезные проекты, а отсутсвие импульса в сообществе не приводит в него новых программистов. Поэтому, Лисп вряд ли будет в ближайшее время серьезно использоваться в индустрии разработки. В чем же тогда его ниша сегодня? Если оставить за скобками тренды, то я бы сказал, что в первую очередь, это системы, которые пишутся на годы и должны постоянно эволюционировать: в этом плане он находится в точке золотой середины между классическими системными языками, типа C++ и Java, и их динамическими конкурентами, предоставляя невероятно гибкую и, в то же время, достаточну производительную (как в отношении скорости исполнения, так и скорости разработки) среду. Особенно, если такие системы должны иметь средства представления и обработки большого количества знаний. Как раз про них 10-е правило Гринспена:
Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
Однако, очень мало кто решится писать сейчас такие проекты на Лиспе. Более актуально другое его применение — быстрое прототипирование и среда для экспериментов. В этой нише у Лиспа много конкурентов, таких как Python или же специализированные языки, типа R и MatLab, но преимущество Лиспа в том, что удачный протип можно со временем довести до продакшн системы. Однако, самое важное значение Лиспа для меня — это полная свобода творчества, которую он предоставляет. Кроме шуток, доступ к такой среде дает возможность программисту развиваться не просто набором опыта использования каких-либо инструментов и фреймворков, а через решение нестандартных задач пытаясь найти для этого наиболее удачный способ независимо от случайных ограничений, налагаемых текущими обстоятельствами и принятыми нормами.