Tag Archives: Programming

New trends in programming languages

By: Nicolau Leal Werneck

Re-posted from: https://medium.com/julia-notes/new-trends-in-programming-languages-1876e879651d

In this article we implement a same program with different programming languages trying to understand what sets them apart. That’s only after we ponder a bit about what’s even the point of all these languages? We look at C++, Go, Rust, Swift, Python and Julia. Among the many aspects we might appreciate in these languages, we focus on scientific programming applications, and on what sets Julia apart. Does Julia really talk like Python and run like C?

Introduction

I love computers, compilers and programming languages. Or at least I used to, until I grew up. I believe it happened some day between college and my first job after grad school, that I became an adult. Among the many revelations that came with this, I learned that in the Real World there is a lot of negative feelings around programming languages, a lot of fear and hatred. Sincerely loving programming languages suddenly became difficult to me.

According to the scriptures, languages are a curse cast onto humanity by The Lord: “Come, let’s go down and confuse the people with different languages. Then they won’t be able to understand each other.”–God. Heaven, 2354.

The tower of Babel being assembled under the disapproving sight of the Principal Architect

Science also has something to say about languages. The Indian linguist Kanavili Rajagopalan writes that: Linguistic identity is largely a political matter and languages are flags of allegiance. This means that the instrumental view of language is fundamentally flawed. If anything, it is the pre-theoretical sense that communication is possible or desirable (…) that makes us postulate the existence of a common language.

Programmers today are often quickly and superficially labelled according to the main language they use. There are “Java programmers”, “Ruby coders”, “PHP people”, “Pythonistas” and “Haskellers”. Job ads almost always ask for proficiency in specific programming languages. Cartoons try to guess what each of these individuals should look like. Differences about languages are often emphasized in our daily lives, and only the sporadic reference to general concepts such as algorithms or design patterns allow us to transcend these differences. Professor Rajagopalan also says The Greek sense of self-identity crucially depended upon the perception that [the “Barbarians”] were just as human as the Greeks themselves, only different. How often nowadays do you consider the “barbarians” are programmers too?

Even though this pigeonholing feels like contemporary identity politics, there has always been some kind of stress between users of different programming languages. The book Hackers by Steven Levy tells in great detail how some Assembly programmers were angry with the popularization of Basic. Even the creation of the first compiled languages like Fortran suffered push-back from people who found it pointless. “What a silly waste of time, I can perfectly go on just flicking these flimsy switches forever!”

Microsoft made a fortune by sparing people from flicking switches

I invented this last quote, so let me provide an actual reference to the fact not everyone leaped into the first languages as soon as they were available: The 704 and 709 Fortrans were successful quite early — especially Fortran II — but the penetration on users, so to speak, was rather uneven. The most experienced users (…) tended to retain assembly language programming, and the newest and least sophisticated newcomers to computing were most frequently Fortran users.

Why are there always some people opposed to new programming technologies? Perhaps it’s not all just politics. First of all, it’s not always clear what is a legitimate technological advance instead of mere hype, and some healthy skepticism is a good thing. On top of that, programming is hard, and most people cannot afford the time and energy to learn new languages. If you can do your work with a language, a work that is challenging and that you are proud of, it really can sound stupid, offensive or insensitive if someone suggests you should or even might do things differently. This sense of pride in your work, and also this feeling of belonging to a community of programmers of a specific language, sharing the same values, both seem related to the idea of thumos, very well discussed in the recent book Identity by Francis Fukuyama.

The world is not frozen in time, though. While many ancestral languages like C and LISP have an impressive ability to remain alive and relevant, new languages continue to be created and adopted by programmers. Especially by beginner programmers, who can often choose indiscriminately between new or established languages as their first one. For any programmer, beginner or not, contemplating the current panorama of languages, these questions come up naturally: What’s the difference between them after all? And what language should I learn?

What follows is an attempt to provide an answer, at least one that makes sense for a certain programmer, and that may be useful to some others.

The rise of scientific Python

In the specific context of scientific and numerical programming, data analysis and machine learning the question is especially difficult right now because there is a lot going on. This is an area where, first of all, there was always this feeling that to reach the ultimate speed you would eventually have to move your code to “good old” C++ or Fortran. Before that happened, though, you would be prototyping and experimenting with more interactive and dynamic languages such as Matlab, R and Mathematica, or maybe those 90s languages like Perl, Python, Ruby, Lua and Tcl, not to mention the occasional Bash script and SQL query. And some tasks are inherently experimental and interactive. Java has also been used in this area in the past decades, although probably motivated more by its previous adoption in companies for other reasons. And apart from languages and libraries there are of course tools like Weka.

Some languages, especially Python, have been gaining attention in the past decade as a result of the growing interest in data science, and more recently in the use of deep learning for working with tasks involving complex natural signals such as images, sound and natural language. Some of the reasons Python seems so suited for the job might be:

1. The ease to inter-operate with efficient, compiled libraries.

2. The succinct, “clean” syntax resulting from features such as dynamic dispatch and garbage collection, not to mention a more sophisticated parser than most people would’ve had the patience to write until the 1980s.

3. The community. Fun and welcoming since the 1990s, Python managed to attract and retain people with different interests, from system administrators, web and game developers to a more scientific crowd such as the creators of packages like numpy, scipy, scikit and matplotlib.

It is not obvious why Python specifically has gained such popularity, though. Other dynamic languages offered something similar to Python, and some did get adopted in data science and deep learning. For instance, Perl offers arrays similar to Numpy through the PDL library, and has statistical packages on CPAN. It also has/had a large community and plenty of “batteries included”. Octave had a pretty solid offering as a free Matlab clone. For deep learning we can cite the Torch framework, based on Lua, which definitely had some traction. At a time Ruby seemed as good as Python for anything and eventually it only became big in web development, never numerical work.

The book Leaders: Myth and Reality by McChristal et al narrates the lives of a number of impressive personalities, and raises the question of how those people became great leaders. It ends up concluding that leadership does not depend so much on personality traits or anything this leader might do. While they do always work hard, a successful leadership seems to depend more on symbolism instead of actual delivered goods, on the environment the leader was in, the organizations around them, and most of all great leadership depends on the will of the leader’s followers to acclaim and follow that leader. Also luck can be a factor.

Robespierre was a great leader. Very popular, and very sure of what was the right way of doing things. He led the ostentatious “Festival of the Supreme Being” above. Only two months later he was sent to the guillotine.

What could that mean for languages? While great languages like Python or JavaScript do offer some amazing features to its users, widespread adoption might depend on more than that, or even the famous batteries. It can depend on how institutions back different languages, what the language can come to symbolize in time to different people, and it fundamentally depends on the decision of individuals to go on pick up a language. With that I mean the existence of a demand, some itch to scratch by the developers and a willingness to look for the answer in a different language. And finally, some luck might be part of everything.

Note I did not mention popularity here. It may be part of what drives some developers in some situations. In other situation it may be the exact opposite, some people may be looking precisely for a unique language. While certainly access to information and to experienced colleagues can be a factor in making a developer pick a language, no language can be popular from the start, and I think we consider popularity to be an important factor in language adoption far more often than it really matters. It’s just a simplistic and naive take on what drives people to follow a leader or to choose a programming language to learn. We are not just “sheeple”!

Rising demands in dynamical languages

Python has definitely made a formidable journey from a systems scripting language to become a big player in the area of numerical programming among Matlab and C++. While the success is clear, the language definitely has its limitations, which are understood by its users. A good job interview covering Python will touch on these topics, and some of the most important tools and techniques used in Python relate to these limitations. And some of these limitations have deep roots.

The first one has to be performance. You simply cannot expect great performance from pure Python code when doing numerical programming tasks. Python can fall behind even compared to other interpreted dynamical languages such as JavaScript . It was never meant to be an efficient language, though. Exaggerating a bit, asking for that is like demanding a great performance from a bash interpreter, for instance.

It is impressive how Python sought to overcome its performance limitations. While there were misses such as Unladen Swallow, there have also been hits such as IronPython and PyPy. And on top of that, of course, is the widely successful implementation of the Matlab-ish paradigm of running fast vector operations over arrays implemented by Numpy. This led the way to more wins with the use of Python on top of lower-level libraries such as OpenCV and TensorFlow. Apart from Python’s success as a “glue language”, projects such as Cython an Numba demonstrate that the platform can go even further.

Another major limitation of Python relates to its laissez-faire type system. Python normally follows the “duck typing” approach, that basically means every function is completely generic, and as long as underlying functions exist that can accept the operator types found at run-time they will just run. This flexibility has undeniable benefits to the development experience, and is one of the main reasons for the popularity of dynamic languages. There is another side to it, though, and experienced developers know that in time it can create problems. For instance, it can be hard to figure out how to use some piece of code that is too abstract. “What are even the expected variable types??”

It is often useful to type-check an input argument to make sure there are no silent bugs happening because a function is not being used as intended. Discussion about compulsory type declarations in programming languages are at least as old as 1963, as this quote from Hoare in the Algol committee shows. While a compelling story, the Mariner I failure was actually caused by a typo in a variable name, although one may argue this mistake could also have been prevented by type-checking.

Just like with performance, the Python community saw that something could be done to improve this situation, and eventually MyPy appeared as a way to provide static type-checking to the language. Again, it is remarkable that this could be accomplished, and the fact they could pull this off says something about the Python architecture and its community.

Considering the evolution of Python and other dynamic languages in the past decades, it seems there was first a massive adoption followed by a craving for performance and a type system. Apart from Python, this can also be observed in JavaScript, where V8 brought great performance improvements first and more recently TypeScript contributed in the other front. Another language that has recently introduced an optional type system is Racket, which has also been aiming at further improving its performance by adopting Chez Scheme as a sort of compiler back-end.

Developments in the static front

Looking beyond dynamic languages, we can see a number of compiled and typed-checked languages that have been proposed in the past decade and have been gaining popularity. We can cite Swift, Rust and Go as examples. All of those have the backing of big organizations and plenty of smart people working on them. The fact they are compiled mean they might offer the desired performance for numerical applications, and the fact they are somehow “modern” means they can offer at least some usability improvements over languages such as C++ and Fortran. Can the scientific community ever favor those languages the same way as Python or Matlab?

Discussing this kind of question is often annoying because of a fundamental fact: Most programming languages can do everything. Having the potential, and even being somehow innovative doesn’t mean you can actually make it happen, though, as this webinar from last year argues. Adoption of a new language depends on the language solving some kind of problem the users feel they have. The conclusion must be that this cannot mean merely whether it is feasible to create some kind of program with the language, otherwise assembly would be “good enough” for anything, and everybody would still be just punching instruction codes into paper tapes in order to write a program. Adopting a new language must bring a productivity benefit, or some other kind of advantage to its users in order to gain traction.

Rust basically brings some of the same improvements over C and C++ that Java did in the 90s. This necessary aggiornamento for low-level, systems languages means offering features such as automatic bounds-checking for array accessing, automatic memory management through reference counting or other forms of garbage-collection, better support for immutability, and less automagical type conversions such as integer-to-boolean. —It is important to point out that this last fact is what many people mean by “strongly/weakly-typed language”, what is different from having explicit argument types at function declarations. It is also different from dynamic/static typing.

C and C++ are seen by some today as being a perfectly fine language, capable of offering all of the above. They just happen to have the wrong defaults, or require caution. This sounds like a nice argument, though it’s not very different from the point above that most languages can do everything. These “defaults” are actually what is crucial in your experience as a programmer of the language. If you are struggling to make something happen as you want, the language isn’t really helping, and you may be better off creating a whole language that outputs C code instead, such as Cython or Nim. While it may seem to help fixing the problems in C and C++ to talk about wrong defaults and warn about the necessary work and caution, these are exactly the very things that drive developers to pick up Python instead of C, Fortran instead of Assembly, etc.

Some people are often annoying under the pretext of making a joke. If you are always joking, though, this is who you are. You are actually an annoying person, it makes no difference if it is a joke. It may be possible to perform bounds checks, reference counting, enforce immutability and explicit conversions in C++. For some reason people don’t do it, this is the face of practical C++, at least for many frustrated programmers. It’s great that libraries have been created to deal with these issues. It took decades and the influence from other languages, though, and it can feel like an afterthought, similar to Python’s efforts towards performance and type safety.

Go is quite different from Rust because apart from trying to offer the “right defaults”, it offers a kind of asceticism that some programmers seem to be craving for. This is epitomized by its lack of parametric polymorphism. The asceticism is not an explicit wish, though. The creators of Go state their goal to be mostly reducing compilation time, and to deliver overall simplicity. Knowingly or not, the design of Go seems to be exploiting the paradox of choice somehow. Whatever they are trying to do, the project seems to have attained success at it. The cost of these constraints seems to change a lot among different programmers, meaning there are some people who will just not be able to use the language, while there does seem to be a large public who is happy with it. Even very happy. It is questionable whether it can please some niches, though, including scientific programmers.

While Rust started backed by the Mozilla Foundation and Go by Google, Swift was created by Apple to be the official language for iOS development, replacing Objective-C —whose name indicates some sort of inspiration. Swift seems to retain some baggage from its predecessor, what should be expected. It does offer something new, though, maybe the main thing being the fact its compiler is based on LLVM, just like Rust and unlike Go.

Swift was not considered a disruptive language in the webinar we cited, maybe because at first it only sought to replace Objective-C, catering to the same audience. Recently, though, some people have been proposing Swift as a language that might offer something to scientific programmers. Central to this idea is the Swift for TensorFlow project.

The timeline goes a bit like this: in the early 2000s Chris Lattner created LLVM at UIUC, with which Clang was developed, and later many other projects. Lattner was later hired by Apple, where he created Swift based on LLVM (and some of that Objective-C baggage). Now he works at Google and is building on top of his successes with the Swift for TensorFlow project.

One of the core developers of Swift for TensorFlow was Richard Wei, who followed Lattner’s steps working at the same UIUC group, Apple and then Google. The seed for Swift for TensorFlow seems to be his graduation project, discussed in this presentation at the 2017 LLVM developers meeting. Apart from the support from Google, the project has been receiving some external appraise too, conspicuously by the Silicon Valley-based fast.ai.

The project seems to exert a natural attraction force to anyone interested in developing iOS apps with deep learning near San Francisco. S4TF does much more than collect the right bag of buzzwords, though. One big reason for its success may be that similar approaches in other modern compiler languages have actually been tried, and simply dropped. Other languages just don’t seem to be adequate for it.

This blog here is a nice illustration of the difficulties that can be faced by anyone trying to integrate TensorFlow with either Go or Rust, and also how even Swift itself was challenging. Swift, by the way, also had its own bumpy ride going from something strictly used for iOS apps to turn into something that might be used in the server or for scientific programming.

The latest bump in the Swift ride is perhaps Richard Wei announcing last month that he’s leaving the project. Although the project remains with a strong institutional backing, some important questions about whether it all could be really integrated in Swift were never answered. It remains unclear what is the potential of S4TF as a practical tool, and not just a well-working prototype that demonstrate many of the things contemporary scientific programmers are looking for.

Building a tool for the job

From S4TF, Python and even C, we have been repeatedly talking here about languages that are being used for scientific programming as an afterthought. This contrasts with languages built with this purpose in mind from the start, such as Mathematica, R, Matlab, Fortran or APL. It doesn’t mean the first languages cannot be good, and it doesn’t mean the second languages are intrinsically better: they do face challenges when moving from prototyping to commercial applications, for instance.

One of the most interesting language alternatives available for scientific programming today was developed on top of LLVM, with an explicit goal of allowing top performance to be achievable. It was also designed with all the benefits seen in modern languages that allow for comfortable prototyping, with a type system that can be as flexible or strict as you wish, and also advanced language features that enable the implementation of techniques such as source-to-source automatic differentiation.

This language is Julia. It started at MIT, which provides an institutional backing. It has been in development for many years already, and version 1.0 released last year was an important landmark. The maturity reached by the core language is complemented by some great tools such as a package system and a debugger, not to mention many packages that help developers working with differential equations and image processing all the way to writing an HTTP server or scripts to run external processes.

While Julia’s dynamic features paired with its close integration with LLVM allows Julia to solve the so-called “two language problem”, Julia also offers great integration with other languages, including Python and C. It has a community with a strong academic background, with some quite active online resources such as a forum and a Slack workspace. It also has a great conference, and many its talks are available on YouTube.

JuliaCon attendees in Baltimore, USA, 2019.

Experiments

This article begins with a promise of an experiment looking into different languages. While it was a long ride to get here, we will finally deliver it!

Julia seems to be accomplishing something that almost sounds like a paradox. In the two histories we discussed before, we saw what we called “dynamical” languages struggling to offer some features from “static” languages, especially high performance and static type-checking, while these “static” languages were following a different path, slowly incorporating features such as polymorphism, meta-programming or dynamic dispatch.

This distinction between these groups of languages can make it seem there’s some natural compromise between them. As if a language can be either fast and reliable to run, or convenient and pleasant to write. As soon as a “dynamic” language is offering static analysis as with MyPy or a form of run-time compilation such as a TensorFlow graph, or when C++ starts offering native dynamic dispatch and a template system that effectively allows you to do “duck typing”, does the nomenclature still make sense?

There is no paradox, really. We believe there is just a natural evolution of programming languages, and the specific limitations we see are casual.

Our experiment hypothesis is that Julia allows you to write code that is very similar to Python, a high standard in syntax quality, while also delivering the performance of C++, a high standard in code efficiency. It is not easy to come up with a good objective assessment of these things, though we believe trying it out is better than just waving your arms and leave you without any kind of practical argument to support all the many words already spent in this article!

Show me the code

We implemented the “change-making problem” in multiple languages, and the code is available at: https://gist.github.com/nlw0/04ec031eaa839d5e358d7ad0d194c497

We offer these numbers as a performance evaluation, solving the problem for the number 907 with coins denominations {11,10,1}.

C++: 3.775 ms

Julia: 3.315 ms

Python: 15.098 ms

It seems safe to say Julia can achieve the same performance as C++. In this case here it even surpassed a little bit, a difference that is most probably related to some small implementation change that a diligent programmer might be able to find. Python, on the other hand is at least 4 times slower than either Julia or C++. Actually quite a good performance, Python can be way slower in other cases.

Regarding syntax similarity, we performed a test utilizing diff. The script can be found on the gist above, and all the pairwise similarity results can be also found on the gist. Here are the similarities only relative to Python:

Python: 1.0
Julia: 0.61
JavaScript: 0.55
Swift: 0.46
Go: 0.33
Rust: 0.30
C++: 0.30

The fact JavaScript scored high while C++ scored low should support this measurement of language similarity. And notably, Julia scored highest in this “Pythonicity” test compared to all other languages.

Conclusion

The importance of programming languages in our lives has only increased since their creation, and they have shown to be very enduring entities. While great transformations have happened in computer technology, from processors to networks, some programming languages seem able to live forever after reaching a certain level of popularity. Languages play a role in our lives that goes beyond their strictly technical purpose. They form a rallying point for the formation of programmer communities, and learning specific programming languages is often conflated with learning other general topics, including computer science.

In the first decades of programming language existence different paradigms were investigated, and the many initiatives showed us what is even possible to do with them. Modern programming languages are being created in a different context, and improvements in software development as a whole makes it easier every day for programming languages to offer new features that in the past would tend to remain exclusive to the languages where they were first created. Among these technological improvements we can cite the LLVM in especial as one important tool that has enabled many of the most interesting languages created in the past decade or so. The JVM has also had a similar effect, not to mention GCC.

Modern scientific programming has been pushing the limits of languages in many ways, requiring solutions for high-performance, distributed and GPU programming, interactive and exploratory work, and also demanding more powerful abstractions. This is exemplified by the need to handle large and complex data pipelines and models, that we want to evaluate, modify, and take all imaginable derivatives along the way!

The great flexibility in program language development today means many languages can offer more or less the same thing, and inter-operation has been becoming easier with time too. It’s not really all the same, though, and differences can be subtle and annoying things to talk about. One can go crazy looking at all the differences in our example code and trying to say why the syntax from one language is better than the other. We did our best not to fall into this trap in this blog. When debating programming languages, we live emphasizing small differences, unless it seems convenient to admit a “common language”. Then the difference between languages become a silly detail, and the barbarians became people too…

This article started with the intention of advocating the Julia language. Many Julia programmers are scientists and academics, though, and by following this nature, this became a scientific-y text. And it turns out that advocating a language may be something strictly rhetorical, though.

If we try to find very compelling objective reasons to use Julia, we will probably always perform experiments similar to what we showed before. We can show good running times, and if there is such a thing as a good test for a “clean syntax”, it seems the language can stand up to it. It can also definitely deliver modern needs such as running on GPUs and performing automatic differentiation. It checks many boxes.

The main reasons anyone will pick up Julia, though, or any other language, are probably not very scientific in nature. Programming is actually a very social activity, what seems at odds with the very technical and impersonal nature of the problems programmers often concern themselves with. Technical reasons may not be enough to convince anyone to try a new language. It’s more like: if you liked this article, you should probably try the language. Join the community, ask your friends, read more about it, I hope you like it.

Our final conclusion must be that you probably don’t need to hear a scientist telling you why to choose a language, but a poet instead. The Brazilian writer Clarice Lispector once wrote:

Surrender, as I surrendered. Immerse yourself in what you do not know how I dove. Do not bother to understand, live passes all understanding.

Try Julia out today!


New trends in programming languages was originally published in Julia Notes on Medium, where people are continuing the conversation by highlighting and responding to this story.

Evaluating Arbitrary Precision Integer Expressions in Julia using Metaprogramming

While watching the Mathologer masterclass on power sums

I came across a challenge to evaluate the following sum
1^{10}+2^{10}+\cdots+1000^{10}

This can be easily evaluated via brute force in Julia to yield

function power_cal(n)
  a=big(0)
  for i=1:n
    a+=big(i)^10
  end
  a 
end
 
julia> power_cal(1000)
91409924241424243424241924242500

Note the I had to use big to makes sure we are using BigInt in the computation. Without that, we would be quickly running in into an overflow issue and we will get a very wrong number.

In the comment section of the video I found a very elegant solution to the above sum, expressed as

(1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 – 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000 = 91409924241424243424241924242500

If I try to plug this into the Julia, I get

julia> (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + r1000^5-(1/2) * 1000^3 + (5/66) * 1000
-6.740310541071357e18

This negative answer is not surprising at all, because we obviously ran into an overflow. We can, of course, go through that expression and modify all instances of Int64 with BigInt by wrapping it in the big function. But that would be cumbersome to do by hand.

The power of Metaprogramming

In Julia, metaprogramming allows you to write code that creates code, the idea here to manipulate the abstract syntax tree (AST) of a Julia expression. We start to by “quoting” our original mathematical expressing into a Julia expression. In the at form it is not evaluated yet, however we can always evaluate it via eval.

julia> ex1=:((1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000)
:((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000)
 
julia> dump(ex1)
Expr
  head: Symbol call
  args: Array{Any}((3,))
    1: Symbol +
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol -
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol +
            2: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol -
                2: Expr
                3: Expr
            3: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol ^
                2: Int64 1000
                3: Int64 5
        3: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol *
            2: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol /
                2: Int64 1
                3: Int64 2
            3: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol ^
                2: Int64 1000
                3: Int64 3
    3: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol *
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol /
            2: Int64 5
            3: Int64 66
        3: Int64 1000
 
julia> eval(ex1)
-6.740310541071357e18

The output of dump show the follow AST in all its glory (…well almost the depth is a bit truncated). Notice that here all our numbers are interpreted as Int64.
Now we walk through the is AST and change all occurrences of Int64 with BigInt by using the big function.

function makeIntBig!(ex::Expr)
  args=ex.args
  for i in eachindex(args)
       if args[i] isa Int64
          args[i]=big(args[i])
       end
       if args[i] isa Expr
          makeIntBig!(args[i])
       end
   end
end
 
julia> ex2=copy(ex1)
:((((((1 / 11) * 1000 ^ 11 + (1 / 2) * 1000 ^ 10 + (5 / 6) * 1000 ^ 9) - 1000 ^ 7) + 1000 ^ 5) - (1 / 2) * 1000 ^ 3) + (5 / 66) * 1000)
 
julia> makeIntBig!(ex2)
 
julia> eval(ex2)
9.14099242414242434242419242425000000000000000000000000000000000000000000000014e+31

We see an improvement here, but the results are not very satisfactory. The divisions yield BigFloat results, which had a tiny bit of floating point errors. Can we do better?
Julia has support for Rational expressions baked in. We can use that improve the results. We just need to search for call expressions the / symbol and replace it by the // symbol. For safety we just have to makes sure the operands are as subtype of Integer.

function makeIntBig!(ex::Expr)
    args=ex.args
    if ex.head == :call && args[1]==:/ && 
              length(args)==3 && 
              all(x->typeof(x) <: Integer,args[2:end]) 
        args[1]=://
        args[2]=big(args[2])
        args[3]=big(args[3])
    else 
        for i in eachindex(args)
           if args[i] isa Int64
              args[i]=big(args[i])
           end
           if args[i] isa Expr
              makeIntBig!(args[i])
           end
        end
    end
end
 
julia> ex2=copy(ex1);
 
julia> makeIntBig!(ex2)
 
julia> eval(ex2)
91409924241424243424241924242500//1

Now that is much better! We have not lost any precision and we ended us with a Rational expression.

Finally, we can build a macro so the if we run into such expressions in the future and we want to evaluate them, we could just conveniently call it.

macro eval_bigInt(ex)
   makeIntBig!(ex)
   ex
end

and we can now simply evaluate our original expression as

julia> @eval_bigInt (1/11) * 1000^11 + (1/2) * 1000^10 + (5/6) * 1000^9 - 1000^7 + 1000^5-(1/2) * 1000^3 + (5/66) * 1000
91409924241424243424241924242500//1

A Collection of Jacobian Sparsity Acceleration Tools for Julia

By: Christopher Rackauckas

Re-posted from: http://www.stochasticlifestyle.com/a-collection-of-jacobian-sparsity-acceleration-tools-for-julia/

Over the summer there have been a whole suite of sparsity acceleration tools for Julia. These are encoded in the packages:

The toolchain is showcased in the following blog post by Pankaj Mishra, the student who build a lot of the Jacobian coloring and decompression framework. Langwen Huang setup the fast paths for structured matrices (tridiagonal, banded, and block-banded matrices) and also integrated these tools with DifferentialEquations.jl. Shashi Gowda then setup a mechanism for automatically detecting the sparsity of Julia programs (!!!).

A tutorial using this workflow together is described in the SparseDiffTools.jl README. In summary, to use the tools you have the following flow:

  1. Find your sparsity pattern, Jacobian structure (i.e. Jacobian type), or automatically detect it with SparsityDetection.jl.
  2. Call `matrix_colors(A)` from SparseDiffTools.jl to get the `colorvec` for A. This is the vector that the differentiation tools need to have to exploit sparsity and reduce the total cost of generating the Jacobian.
  3. When calling `forwarddiff_color_jacobian` from SparseDiffTools.jl for sparse AD or `finite_difference_jacobian` from DiffEqDiffTools.jl for sparse finite differencing, pass the `colorvec` and `sparsity` (the sparsity pattern by either passing the sparse matrix or the structured matrix), then the differentiation tools will automatically accelerate to be fast for that kind of matrix
  4. When building the ODEFunction for the DifferentialEquations.jl ODE solver, pass the `colorvec` and `jac_prototype` and all internal functions will automatically specialize on the sparsity pattern and accelerate. If you pass a structured matrix, like a BandedMatrix, the color vector will be determined automatically, making those accelerations free.

Thus together the chain is: get the sparsity, get the colorvec, pass it to packages and boom you’re faster!

The Math of Sparsity

If you’re interested in how this all works, please take a look at the lecture notes for my course 18.337:

  1. Forward-Mode AD via High Dimensional Algebras (necessary backstory)
  2. Solving Stiff Ordinary Differential Equations (which explains the sparse AD story)

Additionally, take a look at this paper for an explanation of how you can do automatic sparsity detection of Julia packages.

Conclusion

It will be interesting to see how having an integrated platform for acceleration via sparsity effects a high level language, especially the automatic sparsity detection. It is fitting for Julia to have these tools since, given the focus on performance, this is the piece of math that is required to make your performance work really matter! This is a pervasive mechanism which lets you accelerate differentiation on your own, or directly give the differential equation solvers these to utilize (and it works with ODEs, SDEs, DAEs, DDEs, hybrid equations, etc.). We hope to integrate this with NLsolve.jl, and get the Hessian tools finished for Optim.jl and JuMP.jl. Also, JuMP.jl is getting a new and improved NLP interface which will utilize a lot of this behind the scenes automatically. Stay tuned.

The post A Collection of Jacobian Sparsity Acceleration Tools for Julia appeared first on Stochastic Lifestyle.