Modern C++ and Lisp Programming Style

https://chriskohlhepp.wordpress.com/advanced-c-lisp/convergence-of-modern-cplusplus-and-lisp/

by deepaksurti • 9 years ago

145 82 9 years ago

chriskohlhepp.wordpress.com

vvanders4• 9 years ago

The assumption is that the machine code of the C++ compiler is significantly faster than that emitted by a comparable dynamic language compiler. While this may hold true in general, it does not necessarily hold true with Lisp. Lisp is a programmable programming languages. If we are inclined to program it for speed, we can.

My Lisp-fu isn't as strong as my C++-fu so someone correct me if I'm wrong but isn't the GC an intrinsic part of Lisp? Do more modern Lisps allow you to mark value types so you can control memory access patterns(which is where the true speed of C/C++ comes from).

fiddlerwoaroof3• 9 years ago

It's possible to avoid allocations by, e.g. preallocating buffers and other such tricks.

vvanders4• 9 years ago

Allocations are only half the story, you also want to control where those allocations are located so that your cache access patterns pull in the right chunks of memory.

pjmlp4• 9 years ago

Lisp does support more than just lists as data structures.

Arrays are also available, including specialized versions that hold value types.

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node15.html

You can also stack allocate if required, via dynamic-extent, http://clhs.lisp.se/Body/d_dynami.htm

Also not all Lisps have a tracing GC, some variants had a RC with tracing GC for collecting cycles.

RAII like patterns can be achieved via the with-.... functions, or macros.

I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business.

On the other had, given the amount of money spent in C and C++ optimizers vs the lack of industry wide adoption of Lisp, probably still not as good as current leading C++ compilers.

nickpsecurity• 9 years ago

"I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business."

It might be good or just OK on modern hardware. I imagine they stayed in business for their IDE's, libraries, commercial support, and decent compilers. Batteries included. Some success stories make me think performance is really good, though.

http://www.lispworks.com/success-stories/netfonds-primetrade...

http://www.lispworks.com/success-stories/ral-siglab.html

I found those while looking for one about a real-time implementation for telecom or something. Franz's success stories are mostly about doing complicated stuff easier. There was one that looked performance-critical:

http://franz.com/success/customer_apps/finance/ravenpack.lht...

username223• 9 years ago

The last time I checked, the naive Lisp will be shorter than the typical C++, but usually much slower. Sometimes you can annotate your code to death for performance, resulting in something longer than the C++ with more parens, but you still can't trust the compiler to get it right. Fortunately, thanks to DEFMACRO, Lisp lets you write your own optimizing compiler, so as long as your implementation supports your full instruction set, you can do that and achieve better-than-C performance by generating Fortran IV's ugly cousin.

kazinator7• 9 years ago

Indeed, those with- macros.

In TXR Lisp, RAII is supported thusly:

This is GC finalization of a struct:

  This is the TXR Lisp interactive listener of TXR 172.
  Use the :quit command or type Ctrl-D on empty line to exit.
  1> (defstruct animal nil
       (:fini (me) (put-line `@me says good-bye`)))
  #<struct-type animal>
  2> (progn (new animal) nil) ;; make animal without referencing from REPL
  nil
  3> (+ 2 2)
  4
  4> (sys:gc)
  #S(animal) says good-bye
  t

OK, now with-objects macro:

   5> (with-objects ((a (new animal)))
       (prinl a))
   #S(animal)
   #S(animal) says good-bye
   #S(animal)

with-objects invokes finalizers explicitly, before objects become unreachable.

Also, what if a constructor throws? Let's derive animal to dog which bails at `new` time:

  6> (defstruct dog animal
       (:fini (me) (put-line `@me: woof woof`))
       (:postinit (me) (error "refuse to construct")))
  #<struct-type dog>
  7> (new dog)
  #S(dog): woof woof
  #S(dog) says good-bye
  ** refuse to construct
  ** during evaluation at expr-6:3 of form (error "refuse to construct")

The object instantiation logic catches exceptions and invokes finalizers on a partially constructed object (in the proper order as you can see: derived, then base).

lispm5• 9 years ago

I don't know the actual performance of commercial Lisps like Allegro Common Lisp and LispWorks, but I imagine it is quite good, given that they stay in business.

Performance is not one easy number. Applications have different performance requirements. In many benchmarks for typed or type inferred code SBCL tends to be slightly faster with less programming effort.

Fast can mean for example:

* fastest possible execution of optimized code

Then one might not care about code size, code safety, robustness, threading capability, interrupts, .

* fast execution of non-optimized robust, flexible, reflective, debuggable code.

Allegro CL and LispWorks integrate a lot of features. These features are provided over some amount of platforms, with only few restrictions. They provide relatively good performance of a native code compiler. Some robustness is needed for commercial applications, thus I would expect an advantage there.

jlarocco• 9 years ago

Well, modern C++ discourages the programmer from doing manual memory management. There's a very strong push to use vector and string instead of arrays and C strings, references instead of pointers, or, if you really need them, smart pointers instead of raw pointers, etc. Any book or article on modern C++ will tell you to let the compiler and language run-time handle memory management. It's not quite GC, but it's similar.

On the other hand, the default in Lisp is always to let the compiler handle memory, but Common Lisp in particular gives the programmer a lot of flexibility and control over types, memory management, and other optimizations. It's been fighting the "Lisp is slow" stereotype for a long time, so there's been a lot of work done to optimize it and give the programmer optimization options.

For your specific question about memory access patterns, Common Lisp does allow some control over that via the "dynamic-extent" declaration: (declare (dynamic-extent variable-name)). It tells the compiler (or interpreter) that a variable in an inner scope (of a loop, for example) can be allocated once and the space reused each iteration instead of allocating fresh memory each time. It's not full blown C style control of memory, but it's similar and can have a big impact in some situations. The book "Common Lisp Recipes" has a section on it, and so does the hyperspec: http://www.lispworks.com/documentation/HyperSpec/Body/d_dyna...

The recently published "Common Lisp Recipes" is a great book that covers a ton of topics in this area. I think a lot of people would be surprised just how much control and flexibility is available in Common Lisp.

I wouldn't say Common Lisp is faster than C++ in general, and certainly not by default, but with a bit of work it's possible to get pretty close. Importantly, the optimized code will still look and feel like more or less idiomatic Lisp.

vvanders4• 9 years ago

Yup, you don't want to be doing manual memory management until you've done the profiling and found your hot-paths.

However, the set of problems I can tackle is going to be bounded by the escape-hatches that are available to me. Much like Rust has `unsafe {}`, being able to drop down to the bare metal is an important tool to be used at the appropriate time.

turnipping• 9 years ago

What is Stepanov's beef with AI's week foundation?

leshow• 9 years ago

I don't see the relation to Lisp, if anything that quote about noticing the semigroup property of parallel fold algorithms speaks to Haskell or ML more than anything else.

sedachv3• 9 years ago

A lot of early research into parallel algorithms and exploiting associativity for parallelism started at Thinking Machines, a Lisp supercomputer company. Hillis and Steele's 1986 paper in CACM is still one of the best introductions to the subject: http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...

lispm5• 9 years ago

There was quite a lot research into parallel, concurrent and distributed Lisps beginning in the 80s. Thinking Machines with its SIMD computer was just one approach. At some point in time there was a lot of money available for that stuff, including custom hardware. In the US the DoD paid and you can bet that some military/intelligence applications were based on exotic multiprocessor machines running Lisp.

http://www.softwarepreservation.org/projects/LISP/parallel

Often parallel computers had also a Lisp implementation. Much more than listed above.

Parallel Computation and Computers for Artificial Intelligence http://link.springer.com/book/10.1007/978-1-4613-1989-4

Parallel Lisp: Languages and Systems http://link.springer.com/book/10.1007/BFb0024148

Parallel Symbolic Computing: Languages, Systems, and Applications http://link.springer.com/book/10.1007/BFb0018643/page/1

cjhanks• 9 years ago

C++ programmers using a lot templates have a lot in common with Haskell programmers. Often I will write static methods like..

    template<typename Scalar, typename Functor>
    auto
    DoSomething(Scalar value, std::size_t k) -> decltype(Functor(Scalar(0))
    { 
      ...
      Functor(value / Scalar(k));
      ...
    }

Even though it will probably only be used once. Simply because I don't know what types I am going to need yet... but I know it might need a few operators `+`, `-`, `*`, `/`. Once I figure that out, the code is ready to go and is as fast as anything hand written.

If somebody could ever write a great 'Haskell for C++ MetaProgrammers' book describing how you are supposed to understand binary layout, IO, and wtf those hundreds of operators mean... you would probably have a bunch of programmers saying "Oh, I guess I know Haskell".

It's also no surprise that a bunch of the STL algorithms structures were easily made parallel in C++17. A lot of developers using the STL correctly could basically change a few lines of code and switch their program from sequential to parallel.

hellofunk• 9 years ago

Are you referring to adding an execution policy to many of the STL fn calls?

Animats3• 9 years ago

"Modern C++ has shifted focus from an emphasis on type (objects) which accommodate algorithm to an emphasis on algorithms parametrized over types."

That may be a bug, not a feature. The Boost crowd won the battle, making extremely complex templates an essential part of the language. But they may have lost the war, as C++ loses market share.

LISP backed into typing, and it shows. Both typed variables and objects are painful in LISP. By the time LISP got both, the era of LISP was over. LISP is really dead now; there hasn't been a release of GNU Common LISP ("clisp") in 7 years.

sedachv3• 9 years ago

Please quit trolling.

    Allegro CL 10.0 released on 2015-10-05
    ABCL 1.4.0 released on 2016-10-08
    CCL 1.11 released on 2015-11-06
    ECL 16.1.3 released on 2016-12-19
    Lispworks 7.0 released on 2015-05-05
    MKCL 1.1.10 released on 2017-01-18
    SBCL 1.3.15 released 2017-02-28

e40• 9 years ago

And the Allegro CL 10.1 release is imminent.

papaver• 9 years ago

except clojure is one of the most powerful languages around atm? which is a lisp??

hughw5• 9 years ago

I recently came back to write a small experiment in C++. I programmed it professionally for a decade, ending in 2002, and was pretty good at it. After the last 16 years working in Java, Scala, Clojure, and Javascript, I have two observations on C++ 11:

a) Grateful for the extensive access to algorithms, lambdas, type inference;

b) Astounded at the complexity of template meta programming.

I imagine I'll get better at it with practice. But I'm operating at about 15% of the time efficiency of, say, Scala.

AstralStorm• 9 years ago

Why do you really need to do template metaprogramming?

Generally that is not required even in performance sensitive code. Perhaps a few conditionals a'la enable_if or direct use of SFINAE... but most everything else, not really.

sqeaky5• 9 years ago

There is a simple trick to using complex template meta-programming techniques correctly: Leave it up to library authors.

It sounds tongue in cheek, but I am serious. In the std library, boost and other sophisticated libraries there are tons of template shenanigans and there is little to be gain for most application developers. The single thing complex template meta-programs buy you is compile time evaluation for things in the middle of algorithms and classes.

Which is useful, but usually for things like deciding how many object should be allocated at once or how big a working set is to keep everything in cache. These are usually the performance optimizations you care about after all the algorithmic ones have been dealt with and often save only a constant number of instructions. When this seemingly insane level of optimization makes sense the author of a library will often accept the needed data as a parameter.

With constexpr things like lookup tables can easily be computed at compile with much more sane code.

coldtea• 9 years ago

LISP is really dead now; there hasn't been a release of GNU Common LISP ("clisp") in 7 years.

Lisp might be dead, but this sentence is a non sequitur.

lgas• 9 years ago

Cars really are dead now; there hasn't been a release of the Model T since 1927.

lispm5• 9 years ago

GNU Common Lisp and CLISP are two different things.

GNU Common Lisp : https://www.gnu.org/software/gcl/

GNU CLISP : http://clisp.org

CLISP hasn't had a release in a few years, but the repository has a lot of activity these days:

https://sourceforge.net/p/clisp/clisp/ci/e4aba2ecdcf71968053...

there hasn't been a release of GNU Common LISP ("clisp") in 7 years.

CLISP had a beta release a few days ago.

Just installed it on my Mac: this is GNU CLISP 2.49.50 from 2017-03-19.

   $ clisp
      i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
      I I I I I I I      8     8   8           8     8     o  8    8
      I  \ `+' /  I      8         8           8     8        8    8
       \  `-+-'  /       8         8           8      ooooo   8oooo
        `-__|__-'        8         8           8           8  8
            |            8     o   8           8     o     8  8
      ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

    Welcome to GNU CLISP 2.49.50 (2017-03-19) <http://clisp.org/>

    Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
    Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
    Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
    Copyright (c) Bruno Haible, Sam Steingold 1999-2000
    Copyright (c) Sam Steingold, Bruno Haible 2001-2010

    Type :h and hit Enter for context help.

    [1]> (lisp-implementation-version)
    "2.49.50 (2017-03-19) (built 3699208367) (memory 3699208818)"

Doesn't look dead to me...

GNU Common Lisp is currently a bit less active: http://git.savannah.gnu.org/cgit/gcl.git/log/

Other 'free/open source' implementations are currently more interesting, especially ECL, Clozure CL and SBCL.

I have on my 32bit ARM under Linux the following implementations: GCL, ECL, LispWorks, SBCL, CCL, ABCL. LispWorks, CCL and SBCL are native compilers. I'd say that's enough choice.

LISP is really dead now

Not more than usual.

Animats3• 9 years ago

clisp.org says:

Current version: 2.49 (2010-07-07).

Two people are still making source checkins, but there hasn't been a new release since 2010. It's nice to know that someone is still working on it, but they're not making it to a release version.

agumonkey• 9 years ago

I wish I was as dead as lisp. The thing is still malleable and performing into the top 10 languages despite being completely out of mainstream and big guns radar. Meanwhile most mainstream languages (c11, js, python, ...) have bended towards closures as a central paradigm. Not to mention advanced python talks that are mostly CLOS MOP, and humm perl6 which allows to hack as much as CL. Lisp as a product is dead, but the genetic line is still flowing; mostly because of its origin as proto AI recursive logic vehicle.

kazinator7• 9 years ago

There has to be a law. Any time someone criticizes some FOSS project for not making a new release in seven years, that's an indicator that it just happened two or three days ago.

nkozyra• 9 years ago

“Yes. STL is not object-oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence.“

Is hoax a placeholder for "hype" or am I missing something?

sqeaky5• 9 years ago

That confused me too, both clearly work unless there is some definition of work that excludes things which have earned many people many billions of dollars. Hoaxes don't create sustainable businesses.

zwieback• 9 years ago

The quote is probably 20 years old now, at the time people were pretty disillusioned about AI and OO was a craze. Stepanov had other ideas. Here's more context:

http://www.stlport.org/resources/StepanovUSA.html

_delirium• 9 years ago

If you're thinking of the recent boom in machine learning specifically, there are plenty of people in ML, even people making lots of money from it, who think the concept of "artificial intelligence" is a recurring hoax, or at best an overselling aimed at people who've read more sci-fi than science. Of course plenty of people think otherwise, too, but it's not a rare view within the field.

emmelaich• 9 years ago

STL is clearly expressly not object oriented and is actually orthogonal to object oriented.

pjmlp4• 9 years ago

Algorithms, no.

Data structures and allocators, surely yes.

rurban2• 9 years ago

I cannot say much about the C++ code, but the lisp examples are very bad style. One does not write like this.

One writes ordinary generic functions, and then optimized typed methods in lisp like this:

    (defgeneric xplusone (x) (1+ x))
    (defmethod xplusone ((x integer)) (1+ x))
    (defmethod xplusone ((x double-float)) (1+ x))

The sbcl compiler (called python) even creates the typed methods by itself, so mostly the defgeneric line is enough. The type hints for args and return types are purely optional, as the compiler figures it out by itself.

He is right that algorithms, methods, trump data structures, objects. You always write methods with specializations on objects. Not the other way round, classes with specific methods.

xrange• 9 years ago

(defgeneric xplusone (x) (1+ x))
The sbcl compiler (called python) even creates the typed methods by itself, so mostly the defgeneric line is enough.

Is this some new SBCL extension you are talking about? That `defgeneric` line is an error in CLOS.

nuntius• 9 years ago

Very much a part of the standard. i.e. not specific to SBCL.

Think of defgeneric as the function signature and defmethod as the template specialization. Not sure why you say this is an error in CLOS. Looks fine to me.

That said, most implementations try to auto-infer the generic function metaobject when you use defmethod without defgeneric. SBCL raises a warning.

Good reads on the topic:

http://www.gigamonkeys.com/book/object-reorientation-generic...

https://mitpress.mit.edu/books/art-metaobject-protocol

http://mop.lisp.se/

psyc• 9 years ago

Unless I'm missing something, generic algorithms that work across types, and algos that work on type internals are just two separate things. And the latter probably still wants to be encapsulated in the type.

lorenzhs• 9 years ago

The addone function in C++14 would look something like this:

    auto addone = [](auto x) { return x+1; };

That monstrosity at the top of the article is needlessly complex because C++11 didn't support generic lamdbas.

photon-torpedo2• 9 years ago

For terseness, it's probably hard to beat Julia:

    addone1(x) = x+1

Completely generic with type inference, and compiles to optimal machine code. But it also suffers from the "latent type errors deferred to the user" that the article discusses. Calling it with a type that does not support adding 1 will raise an error for a non-existing "+" method:

    addone1("0")
    ERROR: MethodError: no method matching +(::String, ::Int64)

This is pretty understandable in this case, but we may prefer annotating the addone function so that it can only be called with types that support adding 1. Using the (very conservative) notion that only numbers can have 1 added to them, we could use Julia's type hierarchy to restrict the types for which addone may be called:

    addone2(x::T) where T<:Number = x+1

Calling it with an incompatible type now properly points to the outer level:

    addone2("0")
    ERROR: MethodError: no method matching addone2(::String)

But this type of dispatch restrictions rely on a type hierarchy, causing similar problems as class hierarchies in OO languages. For example, the user might have defined their own type that supports addition but not multiplication. Using addone on this type makes sense, but the type shouldn't be a subtype of Number. Such more flexible dispatch scenarios can be achieved with traits. Although Julia currently doesn't have direct language support for traits, they can be implemented inside the language, with macros for syntactic sugar. With traits, the previous example becomes:

    using SimpleTraits
    @traitdef CanAddOne{T}
    @traitimpl CanAddOne{T} <- issubtype(T,Number)
    @traitfn addone3{T; CanAddOne{T}}(x::T) = x+1

Still relatively straight-forward to write and read, and the trait-restricted addone has the same performance as the original one. For incompatible types, the error message still points to the outer level:

    addone3("0")
    ERROR: MethodError: no method matching addone3(::Type{SimpleTraits.Not{CanAddOne{String}}}, ::String)

Importantly, the user can extend the CanAddOne trait (with additional @traitimpl lines) to cover their own type, without being forced to make it a subtype of Number.

deckiedan2• 9 years ago

Haskell:

    add1 = (+1)

    > add1 23
    24

    > add1 2.01
    3.01

    > add1 "0"
    No instance found...

But that error is at compile time.

vkazanov• 9 years ago

Can't say Common Lisp is intuitive but in comparison with C++ it looks... Cleaner.

cassowary• 9 years ago

As I was reading some of the illustrations, I began to wonder why anyone would prefer to use Lisp instead of Haskell. Can anyone mention a few advantages? Mostly, I find Haskell attractive because of the fantastic type system which allows me to write code that will fail when I'm writing or changing code. But I worry that I'm overlooking something because I can't understand why some people prefer Lisp.

keymone• 9 years ago

Ever since i learned lisp i feel very annoyed by languages having so much syntax. Just yesterday i was looking at tiny piece of Haskell code and it gave me headaches. Once you realize how much more productive you can be without cognitive load of juggling dozens of syntactic constructs in your head - it's hard to go back. and then you have benefits of homoiconicity on top of that.

ue_• 9 years ago

I personally find macros and metaprogramminv nicer and more powerful than Template Haskell. I like the regularity of all the syntax too.

Modern C++ and Lisp Programming Style

Related Stories