The claim. Work scales as evaluation. Write it as math — terms, equations, substitution that preserves meaning — and run it on a runtime: agent, record, checks. Scale is then specification quality, not headcount.
That is the breakthrough. It is already running. A stranger can check it; they do not have to take an opinion. The commercial name is compliance that compiles.
The unit is not a company and not an industry. It is an endeavor — a firm, a case, a raise, a move, a life’s work. Wherever the substance is bits, paper, money, or law, the method is the same.
Scaling through people is the historical default. That is not a theory. It is what you do when the interpreter cannot evaluate.
The intersection point on this graph is the end of the world as we know it.
The security of the internet based on existing cryptography that we’ve had since day one will be permanently over.
Military, banking, private messaging, identity, medical and legal records all exposed. Only post-quantum encryption algorithms will save us.
Still no solid plan for this from any major corporation or institution let alone any government.
Recently I took a fresh at look at the Go programming language after having last taken a look at it before version 1.0 was released back in 2009. What I’ve found in just a few days is shocking in a really really good way.
The questionable widespread technical interview process has it’s roots in a cold war era approach that was pioneered by a public proponent of eugenics. Minorities suffer the most from the industry continuing to use this long disproved ritual of conformity.
First, thank you for reaching out. People like you help other people make a living by matching them with companies and opportunities.
If you got a link to this post from me that means that I read your email and find it irrelevant for my profile. This is usually the case because:
Your role does not fit my experience. In many of my roles I led a team of engineers, managers and product managers. Is the scope you offer me similar? How do you think that being a front-end engineer in your team matches my current level and experience?
Your compensation is off. If you are trying to recruit top talent from a FAANG company you should be aware about their compensation expectations. Levels.fyi can give you an idea of what is expected in each level. Can this company offer a similar (or higher) pay to L6-7/M1-2 on Facebook/Google/Amazon? Also, while I’m sure your startup is about to take over the world- I’m not looking to get paid in virtual money stocks.
I don’t do meetings My time is important. Yours too. Time is the only currency we have. From reading your message I can see that there’s a low chance for a match so let’s save time and skip the meeting.
How can you do better next time? Invest more in research before reaching out. Spend most of your time on it. Don’t send generic messages to every engineer in your LinkedIn filter list. First, it will probably piss them off, second you will end up in the spam folder. Read about each potential candidate, evaluate their experience and only if you’re 80% sure there’s a match send them an email. The email should be catered towards their experience, showing how it can match this new role. Also do some homework on compensation and make sure the company can match the pay for the talent you are targeting. I do believe that a personalized message will get you a better response rate with the candidates you approach. Even if it will not be a fit, you will establish a good relationship with them. This can be very useful for the future.
Most #ShitCoin consensus algorithms are based on Proof Of Stake. This is no coincidence. This allows for centralized control of what are essentially just digital fiat currencies and enable the same fraud we’ve seen in most economies that have their paper fiat currency gamed by banks and government.
The loudest voices on blockchain tech know the least. Proof Of Stake chains rest on circular logic fallacies and a misunderstanding of fungibility and forks. Fatal flaws that will not be fixed by rearranging security deposits. The deck chairs on the Titanic were very neatly organized.
The Golden 20s of the 20th century began with the end of WW1 and ended with the stock market crash of 1929. It was considered the decade that was the calm before the storm. However, it was a decade of sweeping technological change and innovation that transformed industrial productivity, life in general and in turn the world economy. It improved the general well-being of many. Electricity, the internal combustion engine and radio changed everyday life forever.Still, a lot has changed in a hundred years since then. The invention of the transistor happened over 70 years ago and the Internet has been in the mainstream for 25 years now. Commodity cloud computing has been around for over 15 years, thanks AWS. Looking back at the 2010s though there have not been any earth-shattering technological inventions. Don’t get me wrong, there have been numerous incredible improvements to existing technology in cost, speed and pervasiveness. The focus has been more horizontal than vertical. My predictions for the 20s are that we are going to see some major changes technologically. Why ? There are just too many forcing functions that can no longer be ignored in the tech industry. Corporations that sell user data, corporations that ignore data security are all losing market share and quickly at that. Internet-enabled cyber-crime estimates from the FBI put the growing cost at around $10 billion for the 2010s and that number will only continue to rise. The rapid growth of IoT devices compounds this issue.
The sooner a language is formally specified and standardized the better. I don’t want to see Rust go the way of languages like Ruby(which eventually got a spec) or Clojure (still does not have one).
Without this and the longer it’s delayed, external libraries spring up to solve problems that should be fully or partially addressed in the core of the language. A formal language spec along with standardization would also potentially inform much higher quality crate design while also allowing quicker progress on many fronts due to less ambiguity. It also would allow for multiple tool-chain implementations e.g. compilers.
TLDR; This problem has been solved for 40 years but the software development industry is still very fashion-oriented.
In both Common Lisp and Smalltalk error handlers can resume the computation that raised it, restart it, or refuse to handle it while the error handling code itself can be separated out from where it is caught i.e. into re-usable functions. Without unwinding the stack and losing the context of why/where the error occurred.
Ada (previously) is a time-tested, safe, secure programming software-engineering language with a 40-year record of success in mission-critical applications such as…
Air Traffic Management Systems
Desktop and Web Applications
Commercial Aviation
Banking and Financial Systems
Railway Transportation
Information Systems
Commercial Rockets
Commercial Shipboard Control Systems
Commercial Imaging Space Vehicles
Television/Entertainment Industry
Communication and Navigational Satellites and Receivers
Medical Industry
Data Communications
General Industry
Scientific Space Vehicles
Military Applications
How good is Ada though for something that most programmers might work on in their day to day ? Something like building a REST service ?
Well here’s the hello-world of a REST service in Ada.
The Raspberry Pi 4 is a leap forward not just for the Pi but for single-board computers across the board. It’s a great light-weight desktop replacement. It’s even surprised me as a viable Rust / Ada development environment.
@@HOLD0@@
My setup includes a Raspberry Pi 4 FLIRC case which is basically a giant aluminum heat sink. This allows for a completely silent setup running at an average of 54’C. During extended code-compiles that tops out around 65’C which is more than enough cooling and completely worth the silence when compared with a fan.
Ada is the only pragmatic language that is still growing in a healthy way that meets the Steelman language requirements (created by US DoD circa 1978). Ada is rare among programming languages in that it is one of the few that was designed up-front according to a years-long well defined specification. Rust, at least aspires to meeting some of these requirements, even if not intentionally.
*Crucial in the Steelman requirements were: *
A general, flexible design that adapts to satisfy the needs of embedded computer applications.*
Reliability*. The language should aid the design and development of reliable programs.*
As I’ve been spending a lot of time with Arm hardware lately as my primary desktop and server platform I missed using my secure messenger app of choice. I was able to cook up builds for both armv7l/armhf/GNU Linux (32-bit) and arm64/aarch64/GNU Linux (64-bit).
These are unofficial but fully working builds of Signal Desktop for Linux on Arm processors. Enjoy !
Here are some initial thoughts on Rust in the almost two years since I last looked at it along with some implementations of merge and quick sort. (These are just my opinions so please don’t panic !)
Cargo is awesome for managing package dependencies and building projects.
A few months back I took a look at Elixir. More recently I’ve been exploring F# and I’m very pleased with the experience so far. Here is the ring probabilities algorithm implemented using F#. It’s unlikely that I will ever use Elixir again because having a powerful static type system provided by F# at my disposal is just too good.
letreccalcStateProbs(prob:float,i:int,currProbs:float[],newProbs:float[])=ifi<0thennewProbselseletmaxIndex=currProbs.Length-1// Match prev, next probs based on the fact that this is a
// ring structure.
let(prevProb,nextProb)=matchiwith|iwheni=maxIndex->(currProbs.[i-1],currProbs.[0])|0->(currProbs.[maxIndex],currProbs.[i+1])|_->(currProbs.[i-1],currProbs.[i+1])letnewProb=prob*prevProb+(1.0-prob)*nextProbArray.setnewProbsinewProbcalcStateProbs(prob,i-1,currProbs,newProbs)letcalcRingProbsparsedArgs=// Probs at S = 0.
// Make certain that we are positioned at only start location.
// e.g. P(Start Node) = 1
letstartProbs=Array.concat[[|1.0|];[|for_in1..parsedArgs.nodes-1->0.0|]]letendProbs=List.fold(funprobs_->calcStateProbs(parsedArgs.probability,probs.Length-1,probs,Array.createprobs.Length0.0))startProbs[1..parsedArgs.states]endProbs
I’ve been hearing more about Elixir lately so I thought I’d take it for a spin.
*“Elixir is a functional, meta-programming aware language built on top of the Erlang VM. It is a dynamic language that focuses on tooling to leverage Erlang’s abilities to build concurrent, distributed and fault-tolerant applications with hot code upgrades.”
I’ve never really spent any time with Erlang but always been curious about it and the fact that it’s one of the best kept ‘secrets’ in many startups these days. I’ve heard for years how easy it is to ‘scale out’ compared with many other languages and platforms.
It looks like it might be coming sooner than I thought. I’m sure Shenturions everywhere will find this news incredibly exciting for the future of Shen. I can’t wait to see how things progress.
In computer science, a Selection sort is a sorting algorithm, specifically an in-placecomparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
(A functional implementation of selection sort is however, not an in-place sort.)
Kuksi is famous for his Baroque-influenced assemblages that seem to splinter out like sculptural fractals, each component fused to another object or detail even smaller and intricate
Replaced the use of Data.Vector with the persistent Data.Sequence which has O(logN) worst case time complexity on updates.
A Haskell version of the previous code using the more efficient(access and update) persistent Data.Sequence type so that the desired time complexity is maintained for the union operation.
-- Disjoint set data type (weighted and using path compression).-- O((M+N)lg*N + 2MlogN) worst-case union time (practically O(1))-- For M union operations on a set of N elements.-- O((M+N)lg*N) worst-case find time (practically O(1))-- For M connected(find) operations on a set of N elements.dataDisjointSet=DisjointSet{count::Int,ids::(SeqInt),sizes::(SeqInt)}deriving(Read,Show)-- Return id of root objectfindRoot::DisjointSet->Int->IntfindRootsetp|p==parent=p|otherwise=findRootsetparentwhereparent=index(idsset)(p-1)-- Are objects P and Q connected ?connected::DisjointSet->Int->Int->Boolconnectedsetpq=(findRootsetp)==(findRootsetq)-- Replace sets containing P and Q with their unionquickUnion::DisjointSet->Int->Int->DisjointSetquickUnionsetpq|i==j=set|otherwise=DisjointSetcntridsrsizeswhere(i,j)=(findRootsetp,findRootsetq)(i1,j1)=(index(sizesset)(i-1),index(sizesset)(j-1))(cnt,psmaller,size)=(countset-1,i1<j1,i1+j1)-- Always make smaller root point to the larger one(rids,rsizes)=ifpsmallerthen(update(i-1)j(idsset),update(j-1)size(sizesset))else(update(j-1)i(idsset),update(i-1)size(sizesset))
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
CODEBREAKER tells the story of one of the most important people of the 20th century. Alan Turing set in motion the computer age and his World War II codebreaking helped save two million lives. Yet few people have heard his name, know his tragic story, or understand his legacy. In 1954, Turing committed suicide at age 41 after being forced to undergo hormone therapy to “fix” his sexual orientation. He left behind a lasting legacy and lingering questions about what else he might have accomplished if society had embraced his unique genius instead of rejecting it. 100 years after his birth, an international production team takes viewers on a journey to rediscover the man and the mystery.
“… historian Richard C. Carrier proposes Bayes’s theorem as a solution to the problem of establishing reliable historical criteria. He demonstrates that valid historical methods—not only in the study of Christian origins but in any historical study—can be described by, and reduced to, the logic of Bayes’s theorem. Conversely, he argues that any method that cannot be reduced to Bayes’s theorem is invalid and should be abandoned.”
Kay: Yeah. But the thing that traumatized me occurred a couple years later, when I found an old copy of Life magazine that had the Margaret Bourke-White photos from Buchenwald. This was in the 1940s — no TV, living on a farm. That’s when I realized that adults were dangerous. Like, really dangerous.
The lack of interest, the disdain for history is what makes computing not-quite-a-field.
This is Ayn Rand’s challenge to the prevalent philosophical doctrines of our time and the “atmosphere of guilt, of panic, of despair, of boredom, and of all-pervasive evasion” that they create. One of the most controversial figures on the intellectual scene, Ayn Rand was the proponent of a moral philosophy–and ethic of rational self-interest–that stands in sharp opposition to the ethics of altruism and self-sacrifice. The fundamentals of this morality–“a philosophy for living on Earth”–are here vibrantly set forth by the spokesman for a new class, For the New Intellectual.
Ted Nelson‘s latest video series called “Computers for Cynics” calls it like it is. How refreshing in contrast with the pervasive garbage called ‘information’ that we get fed in the second decade of the 21st century.
Eccerobot
At the [swissnex San Francisco](http://swissnexsanfrancisco.org//) conference earlier this year, scientists from Switzerland and the US discussed their research on humanoid robots, cognitive robotics, and artificial intelligence (AI). Talk revolved around how some robots self-reflect, self-improve, and adapt to new circumstances, and whether it’s possible for robots of the future to possess the same cognitive characteristics as humans.
From the website: John was a legendary computer scientist at Stanford University who developed time-sharing, invented LISP, and founded the field of Artificial Intelligence.* In March 2011 John launched Project JMC with the objective to make his work more approachable and accessible. The Project JMC team is continuing to help realize his objective. In this site you will find all John’s work, including his social commentary, and acknowledgements of his outstanding contributions and impact. Additional comments, suggestions, stories, photographs and videos on John and his work are very welcome. Please send them to the Project JMC team. His old website is here.
After watching some of Tim Roughgarden’s videos on sorting algorithms, I thought I’d post an implementation of quick sort in Common Lisp as an example of a sorting algorithm implemented in CL. It’s a simple enough example(at < 20 LOC) that demonstrates one non-imperative approach to algorithm implementation. The complete code can be found here.
This got me thinking more about functional programming languages and how they could be a future casualty in a similar way that we currently see the intentional limitation/crippling of turing machines.
Sold out attendance marked this being the second premiere conference for Clojure. What I realized is just how great the people are in this community. No, seriously. There’s far less ego than with many other communities. This is a great sign for the future of Clojure. Particularly because Rich is such a great guy. He even gave a public apology for something or other that he said(on a mailing list) which he felt was not in the spirit of the Clojure community.
In this video Sam Aaron gives a fast-paced introduction to a number of key live programming techniques such as triggering instruments, scheduling future events and synth design. Finally, the viewer is shown how a simple musical sequence may be composed and then converted into an intricate Reich phase. The main body of the video was recorded in one take and features an Emacs buffer (using the Live Coding Config (is.gd/live_coding_emacs) for editing text and communicating with Overtone (is.gd/overtone), an expressive Clojure front-end to SuperCollider. Clojure is a state-of-the-art functional lisp emphasising immutability and concurrency (clojure.org).
The first publicly available version of Shen/Kl has been released.
The Shen mission is to develop an ultra-portable version of Qi that can run under a wide variety of platforms and which incorporates missing features in Qi such as streams. The targeted platforms are CL, Clojure, NewLisp, Emacs Lisp, ECL, Scheme, Javascript and Python as well as C/C++, DVM, CLR or the JVM. This approach involved rewriting and redesigning Qi to fit within the smallest feasible instruction set.
Update : bug-fix when hull was being incorrectly calculated due to there being duplicate points generated in the random set.
ClojureScript looks like a solid approach to building applications that target JavaScript VMs. It’s built on top of Google’s Closure Compiler/Library which is very intruiging and is the best approach that they could have taken (now that I’ve a played with it a little). Being new to both Closure and ClojureScript I was curious about what it might feel like to build an application using these tools. I’ve mostly despised programming in JavaScript for browsers no matter what hyped-up library is available (this includes JQuery which is the best of a bad bunch in my opinion). So I decided to write a ClojureScript application that runs in the browser based on a previous Clojure implementation of a Convex Hull algorithm with heuristics.
In this second post in this series we look at an implementation of the always useful Fast Fourier Transform.
(FFT) An algorithm for computing the Fourier transform of a set of discrete data values. Given a finite set of data points, for example a periodic sampling taken from a real-world signal, the FFT expresses the data in terms of its component frequencies. It also solves the essentially identical inverse problem of reconstructing a signal from the frequency data.
This is the first in a series of posts that will demonstrate the implementation of many well-known(and less known) data structures and algorithms using a purely functional approach.
We will use Qi as our implementation language for a number of reasons :
It’s a Lisp : macros, EVAL, hash-tables, property-lists, meta-programming etc.
Minsky argues that emotions are different ways to think that our mind uses to increase our intelligence. He challenges the distinction between emotions and other kinds of thinking. His main argument is that emotions are “ways to think” for different “problem types” that exist in the world. The brain has rule-based mechanism (selectors) that turns on emotions to deal with various problems. The book reviews the accomplishments of AI, what and why is complicated to accomplish in terms of modeling how human beings behave, how they think, how they experience struggles and pleasures. (Wikipedia)
It is Lisp with many great features such as pattern-matching, a turing complete static type system (even more powerful than Haskell’s type system) and many others.
So in the spirit of PI day, here’s an implementation that calculates PI using Machin’s formula.
Programming language wars don’t have to be religious based wars. Programming languages should be rooted in philosophy. The more a programming language is rooted in sound philosophy the more value it has.
Over the years, many of the posts on this blog have been regarding some programming language, algorithm or technology. Some posts have highlighted why Lisp is the most powerful and useful programming language paradigm available to man at this point in the history of computer science.
Artificial Intelligence was born in Computer Science departments, and inherited their value sets including Correctness. This mindset, this necessity to be logical, provable, and correct has been a fatal roadblock for Artificial Intelligence since its inception. The world is Bizarre, and Logic can not describe it. Artificial Intuition will easily outperform Logic based Artificial Intelligence for almost any problem in a Bizarre problem domain. From the very beginning, Artificial Intelligence should have been a soft science.
“In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.”
First let’s define a simple node struct and create a tree :
The implementers of existing Ruby VMs have gone the way of C, C++ and Java.
There is another possibility. Why not implement Ruby in Common Lisp ?
Ok, let’s take the first shot and implement a subset of the Ruby language. Just enough to run some simple contrived numeric benchmarks. The following pseudo BNF describing a minimal subset of Ruby should do (taken from the rubydocs here).
These days there just can’t be enough said to counter the hype that comes with STM. The following paper is an eye opening read(it measures actual peformance of STM). Hopefully some of the STM faithful will re-consider their fanatic beliefs.
“In this article, we explore the performance of a highly optimized STM and observe the overall performance of TM is much worse at low levels of parallelism, which is likely to limit the adoption of this programming paradigm.”
// pi_spigot.s - calculates Pi using a spigot algorithm
// as an array of n digits in base 10000.
// http://mathworld.wolfram.com/SpigotAlgorithm.html
//
// x86-64/SSE3 with for Linux, Intel, gnu assembler, gcc
//
// assemble: as pi_spigot.s -o pi_spigot.o
// link: gcc -o pi_spigot pi_spigot.o
// example run: ./pi_spigot 100
// output: 3.14159265358979323846264338327950288419716939937510582097494459230 ...
// ... 78164062862089986280348253421170679
//
.section.rodata.LC0:.string"%d.".LC1:.string"%04d".text.globlprint.typeprint,@functionprint:.LFB0:.cfi_startprocpushq%rbp.cfi_def_cfa_offset16movq%rsp,%rbp.cfi_offset6,-16.cfi_def_cfa_register6subq$32,%rspmovq%rdi,-24(%rbp)movl%esi,-28(%rbp)movq-24(%rbp),%raxaddq$2,%raxmovzwl(%rax),%eaxmovzwl%ax,%edxmovl$.LC0,%eaxmovl%edx,%esimovq%rax,%rdimovl$0,%eaxcallprintfmovl$2,-4(%rbp)jmp.L2.L3:movl-4(%rbp),%eaxcltqaddq%rax,%raxaddq-24(%rbp),%raxmovzwl(%rax),%eaxmovzwl%ax,%edxmovl$.LC1,%eaxmovl%edx,%esimovq%rax,%rdimovl$0,%eaxcallprintfaddl$1,-4(%rbp).L2:movl-28(%rbp),%eaxsubl$1,%eaxcmpl-4(%rbp),%eaxjg.L3movl$10,%edicallputcharleaveret.cfi_endproc.LFE0:.sizeprint,.-print.globlmain.typemain,@functionmain:.LFB1:.cfi_startprocpushq%rbp.cfi_def_cfa_offset16movq%rsp,%rbp.cfi_offset6,-16.cfi_def_cfa_register6pushq%rbxsubq$56,%rspmovl%edi,-52(%rbp)movq%rsi,-64(%rbp)cmpl$1,-52(%rbp)jle.L6.cfi_offset3,-24movq-64(%rbp),%raxaddq$8,%raxmovq(%rax),%raxmovq%rax,%rdicallatoiaddl$3,%eaxleal3(%rax),%edxtestl%eax,%eaxcmovs%edx,%eaxsarl$2,%eaxaddl$3,%eaxjmp.L7.L6:movl$253,%eax.L7:movl%eax,-20(%rbp)movl-20(%rbp),%eaxcltqaddq%rax,%raxmovq%rax,%rdicallmallocmovq%rax,-40(%rbp)movl-20(%rbp),%eaxcltqleaq(%rax,%rax),%rdxmovq-40(%rbp),%raxmovl$0,%esimovq%rax,%rdicallmemsetmovq-40(%rbp),%raxaddq$2,%raxmovw$4,(%rax)cvtsi2sd-20(%rbp),%xmm0movsd.LC2(%rip),%xmm1mulsd%xmm1,%xmm0cvttsd2si%xmm0,%eaxmovl%eax,-24(%rbp)jmp.L8.L13:movl$0,-32(%rbp)movl-20(%rbp),%eaxsubl$1,%eaxmovl%eax,-28(%rbp)jmp.L9.L10:movl-28(%rbp),%eaxcltqaddq%rax,%raxaddq-40(%rbp),%raxmovzwl(%rax),%eaxmovzwl%ax,%eaximull-24(%rbp),%eaxaddl%eax,-32(%rbp)movl-28(%rbp),%eaxcltqaddq%rax,%raxmovq%rax,%rbxaddq-40(%rbp),%rbxmovl-32(%rbp),%ecxmovl$1759218605,%edxmovl%ecx,%eaximull%edxsarl$12,%edxmovl%ecx,%eaxsarl$31,%eaxmovl%edx,%esisubl%eax,%esimovl%esi,%eaximull$10000,%eax,%eaxmovl%ecx,%edxsubl%eax,%edxmovl%edx,%eaxmovw%ax,(%rbx)movl-32(%rbp),%ecxmovl$1759218605,%edxmovl%ecx,%eaximull%edxsarl$12,%edxmovl%ecx,%eaxsarl$31,%eaxmovl%edx,%ecxsubl%eax,%ecxmovl%ecx,%eaxmovl%eax,-32(%rbp)subl$1,-28(%rbp).L9:cmpl$0,-28(%rbp)jns.L10movl$0,-44(%rbp)movl-44(%rbp),%eaxmovl%eax,-48(%rbp)movl$0,-28(%rbp)jmp.L11.L12:movl-24(%rbp),%eaxaddl%eax,%eaxleal1(%rax),%edxmovl-28(%rbp),%eaxcltqaddq%rax,%raxaddq-40(%rbp),%raxmovzwl(%rax),%eaxmovzwl%ax,%ecxmovl-44(%rbp),%eaximull$10000,%eax,%eaxleal(%rcx,%rax),%eaxmovl%edx,%esimovl%eax,%edicalldivmovq%rax,-48(%rbp)movl-28(%rbp),%eaxcltqaddq%rax,%raxaddq-40(%rbp),%raxmovl-48(%rbp),%edxmovw%dx,(%rax)addl$1,-28(%rbp).L11:movl-28(%rbp),%eaxcmpl-20(%rbp),%eaxjl.L12movq-40(%rbp),%raxaddq$2,%raxmovq-40(%rbp),%rdxaddq$2,%rdxmovzwl(%rdx),%edxaddl$2,%edxmovw%dx,(%rax)subl$1,-24(%rbp).L8:cmpl$0,-24(%rbp)jg.L13movl-20(%rbp),%edxmovq-40(%rbp),%raxmovl%edx,%esimovq%rax,%rdicallprintmovl$0,%eaxaddq$56,%rsppopq%rbxleaveret.cfi_endproc.LFE1:.sizemain,.-main.section.rodata.align8.LC2:.long3161095930.long1076532084
This one had been sitting on my bookshelf for almost a year.
“Let Over Lambda is one of the most hardcore computer programming books out there. Starting with the fundamentals, it describes the most advanced features of the most advanced language: COMMON LISP. The point of this book is to expose you to ideas that you might otherwise never be exposed to.”
One popular interview question that never dies : write some code to reverse a singly linked-list.
Now understanding the problem for interviewees is one thing but getting it right in an imperative language seems to be quite a feat based on my experience as an interviewer. Most take 15-20 minutes to get this completely correct and sometimes even longer.
Here’s a quick solution that took me 10 minutes (in C) :
;; Calculates the convex hull of a set of points using the Graham scan;; algorithm.(ns i27.geom.convex-hull(:use[i27.geom.misc:only(anglecross-product)]))(defn presort-points[pts]"Presorts the cartesian points in descending order by angle.
The point with lowest y value is last in the vector."(let [pts(distinct pts)];; must be distinct or else errors ...(letfn[(find-start[[x1y1:aspt1][x2y2:aspt2]](cond (< y1y2)pt1(= y1y2)(if (< x1x2)pt1pt2)truept2))](let [pt(reduce find-startpts)npts(remove (fn [[xy:ascpt]](and (= (first pt)x)(= (last pt)y)))pts)](conj (apply vector(sort (fn [pt1pt2](> (angleptpt1)(angleptpt2)))npts))pt)))))(defn convex-hull"Calculates the convex hull given a set of points in the cartesian plane.
Uses the Graham scan algorithm. Performance is O(n lg n) time."[pts](when (>= (count pts)3)(let [start(apply vector(reverse (subvec pts(- (count pts)3)(count pts))))other(reverse (subvec pts0(- (count pts)3)))](letfn[(popstack[stkpt](if (not (> (cross-product(last (pop stk))(last stk)pt)0))stk(recur(pop stk)pt)))(scan[respt](conj (popstackrespt)pt))](reduce scanstartother)))))(defn elim-points"Prepare data with Aki-Toussaint heuristics before passing to convex hull function.
Performance is O(n) time regardless of the convex hull algorithm used."[pts](when (>= (count pts)4)(letfn[(find-quad[[[x1y1:aspt1][x3y3:aspt3][x2y2:aspt2][x4y4:aspt4]:asquad][xcyc:ascpt]][(if (> x1xc)cptpt1)(if (> y3yc)cptpt3)(if (< x2xc)cptpt2)(if (< y4yc)cptpt4)])](let [poly(distinct (reduce find-quad(take 4pts)pts));; generate the line segments that form the convex polygonlines(conj (reduce (fn [linespt](conj lines[(last (last lines))pt]))[[(first poly)(second poly)]](rest (rest poly)))[(last poly)(first poly)]);; filter out all points that fall inside the convex polygonpts(filter(fn [tpt](not (reduce (fn [bv](and b(neg? v)))true(map (fn [pt](cross-producttpt(first pt)(last pt)))lines))))pts)]pts))))
“If we make an unbiased examination of the accomplishments made by mathematicians to the real world of computer programming, we are forced to conclude that, so far, the theory has actually done more harm than good. There are numerous instances in which theoretical “advances” have actually stifled the development of computer programming, and in some cases they have even made it take several steps backward!”
Here’s a molecule viewer using OpenGL in Clojure. Implemented so that I could compare this type of development with Common Lisp (and also with using OpenGL development in C). OpenGL with Clojure can be really fun using Zach Tellman’s Penumbra. Coming at OpenGL from a more functional angle (e.g. not mutating global vars etc.) can be a little different but not difficult for anyone who has done enough functional programming.
// pi_x64.s - calculates Pi using the Leibniz formula.
// Each iteration prints a closer approximation to 50 digits.
// This is not an optimal implementation and it runs forever.
//
// x86-64/SSE3 with for Linux, Intel, gnu assembler, gcc
//
// assemble: as pi_x64.s -o pi_x64.o
// link: gcc -o pi_x64 pi_x64.o
// run: ./pi_x64
// output: 3.14159264858204423376264458056539297103881835937500
// 3.14159265108366625440794450696557760238647460937500
// 3.14159265191852199450295302085578441619873046875000
// 3.14159265233600137889879988506436347961425781250000
// .... and on forever ...
.section.data.align16denom:.double1.0,3.0numer:.double4.0,-4.0add4:.double4.0,4.0zero:.double0.0,0.0msg:.string"%1.50fn".section.text.globlmain.typemain,@function.align64main:pushq%rbpmovq%rsp,%rbpmovdqa(numer),%xmm2movdqa(denom),%xmm6movdqa(add4),%xmm3movdqa%xmm2,%xmm4movdqa(zero),%xmm5movq$100000000,%r12loop:divpd%xmm6,%xmm2addpd%xmm2,%xmm5movdqa%xmm4,%xmm2addpd%xmm3,%xmm6subq$1,%r12jnzloopmovq$100000000,%r12movdqa%xmm5,%xmm0movdqa%xmm6,%xmm1haddpd%xmm0,%xmm0movq$1,%raxmovq$msg,%rdicallprintfmovdqa(add4),%xmm3jmploopmovq$0,%raxpopq%rbpret
THIS IS A LANGUAGE RANT. DO NOT READ IF YOUR BPF* IS LESS THAN 0.37.
SIDE EFFECTS MAY INCLUDE SEVERE CONFUSION, UNJUSTIFIED ANGER, GASSY DISCHARGE,
INCOMPREHENSIBLE DIALOG, ERRATIC DEGRADATION OF CHARACTER AND POSSIBLY A
COMPLETE EMOTIONAL MELTDOWN.
Performance is one important aspect that people might want in a language. One language that continually surprises me in this regard is Haskell. Seriously, it’s simply amazing. But performance is only one important consideration when using a language. Abstraction is another.
Update 2009-12-27 * Using lists instead of vectors brings the Clojure version down from around 20x to 10X slower than the CL version. One reader correctly stated that when doing performance comparisons between languages and implementations you want the code and data structures to be as identical as possible.
**
“A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction (the adjustment of punctuation and spaces between words is generally permitted.”
“This is a personal story of the educational process at one of the world’s great technological universities. Pepper White entered MIT in 1981 and received his master’s degree in mechanical engineering in 1984. His account of his experiences, written in diary form, offers insight into graduate school life in general—including the loneliness and even desperation that can result from the intense pressure to succeed—and the purposes of engineering education in particular. The first professor White met at MIT told him that it did not really matter what he learned there, but that MIT would teach him how to think. This, then, is the story of how one student learned how to think.”
Many learners will move into a variety of different, possibly unrelated fields over the course of their lifetime.
Informal learning is a significant aspect of our learning experience. Formal education no longer comprises the majority of our learning. Learning now occurs in a variety of ways – through communities of practice, personal networks, and through completion of work-related tasks.
The previous Common Lisp and Haskell functions to generate the digits of PI where only accurate between 10000 and 20000 digits. The algorithm uses an approximation where we discard a certain number of ‘guard’ digits to get an accurate result. Some background regarding how the number of guard digits is calculated : There is ‘wobble’ in the number of contaminated digits depending on the number of input digits. When only the order of magnitude of rounding error is of interest, ulps(units in the last place) and ε (machine precision) may be used interchangeably, since they differ by at most a factor of β (the ‘wobble’ in the number of contaminated digits). For example, when a floating-point number is in error by n ulps, that means that the number of contaminated digits is about logβn. [1] [2]
(defunmachin-pi(digits)"Calculates PI digits using fixed point arithmetic and Machin's formula with double recursion"(labels((arccot-minus(xsqnxpower)(let((term(floorxpowern)))(if(=term0)0(-(arccot-plusxsq(+n2)(floorxpowerxsq))term))))(arccot-plus(xsqnxpower)(let((term(floor(/xpowern))))(if(=term0)0(+(arccot-minusxsq(+n2)(floorxpowerxsq))term))))(arccot(xunity)(let((xpower(floor(/unityx))))(arccot-plus(*xx)1xpower))))(let*((unity(expt10(+digits10)))(thispi(*4(-(*4(arccot5unity))(arccot239unity)))))(floorthispi(expt1010)))))
The first 10000 digits again.
* (time (machin-pi 10000))
Evaluation took:
0.662 seconds of real time
0.634038 seconds of total run time (0.495454 user, 0.138584 system)
[ Run times consist of 0.233 seconds GC time, and 0.402 seconds non-GC time. ]
95.77% CPU
1,491,387,858 processor cycles
109,530,592 bytes consed
31415926535897932384626433832795028841971693993751058209749445923078164062862089 ...
Algorithmic optimizations would take us much further. For example the Gauss–Legendre or Salamin–Brent formula.
And here’s a longer version(but faster and more precise) using Machin’s formula with fixed point arithmetic to x digits.
(defunmachin-pi(digits)"Calculates PI digits using fixed point arithmetic and Machin's formula with double recursion"(labels((arccot-minus(xsqnxpower)(let((term(floor(/xpowern))))(if(=term0)0(-(arccot-plusxsq(+n2)(floor(/xpowerxsq)))term))))(arccot-plus(xsqnxpower)(let((term(floor(/xpowern))))(if(=term0)0(+(arccot-minusxsq(+n2)(floor(/xpowerxsq)))term))))(arccot(xunity)(let((xpower(floor(/unityx))))(arccot-plus(*xx)1xpower))))(let*((unity(expt10(+digits10)))(thispi(*4(-(*4(arccot5unity))(arccot239unity)))))(floor(/thispi(expt1010))))))
* (time (mapconcat 'identity *mylist* "-"))
Evaluation took:
2.805 seconds of real time
2.746358 seconds of total run time (2.736834 user, 0.009524 system)
[ Run times consist of 0.004 seconds GC time, and 2.743 seconds
non-GC time. ]
97.90% CPU
6,324,642,149 processor cycles
17,734,520 bytes consed
"0-1-2-3-4-5-6-7-8-9-10- ... "
The previous article had some serious traffic yesterday and today.
Due to abuse of the moderation system on some sites I’ve been forced to present my response here separately.
To the SBCL contributor : Relax, SBCL is still a great Lisp compiler. It always has been and I’m sure it always will be. Your work on the compiler is appreciated. It’s unfortunate that you seem to fit the pontificating arm-chair theoretician stereo-type. You do have a few valid points to share in spite of your mostly incorrect presumptions regarding the Lisp code. The single worthwhile and correct contribution that you made to the discussion was your suggestion on type declarations in the critical path of the code. Thanks for that, you were one of only two people that has actually addressed the performance of the code so far. I posed a challenge to you because of your claims of being able to easily bring the code within under 3x the slowness of the C version. Your dismissive refusal to substantiate your claims with any real evidence speaks volumes to a wide ranging audience now.
(The same holds true for its dialects and derivatives.)
Its ‘bizarre’ syntax, its alleged ability to stand up to low level language performance, the unique and powerful abstractions awarded the programmer who even dares to attempt its almost vertical cliff face of learning. Or so it seemed back then. With its more recent popularity there’s been much hype surrounding its capabilities and especially so in contrast to other languages.
For those that are unhappy about this not being a Symbolic Integration example then please read Norvig’s “Paradigms of Artificial Intelligence Programming – Case Studies in Common Lisp”, Chapter 8 – Symbolic Mathematics : A Simplification Program, 8.6 – Integration, page 252.
(defparameter*small-dx*0.0001)(defunintegrate(fab)"integrate a function f from a to b"(defunintegrate-gen(fxbdxsum)"the generalized inner function for tail-recursion.
integrate a function f from x to b"(if(>xb)sum(integrate-genf(+xdx)bdx(+sum(*(funcallfx)dx)))))(integrate-genfab*small-dx*0))(let((f1(lambda(x)1))(f2(lambda(x)(exptx2)))(f3(lambda(x)(*x(exp(exptx2))))))(print(integratef105))(print(integratef301)))
Before I go any further : let me state upfront that knowing Lisp has changed me as a programmer for the best. It’s been an invaluable experience that I’ve carried into every corner of my career and every other language that I’ve coded with.
Now that we have that out of the way let’s move on…
There are a number of problems with Common Lisp that go unmentioned in the community. The fact that a prominent member of the CL community has recently highlighted these(at ILC 2009 no less) could be viewed as a break-through for the language in itself. The show-stoppers in my opinion from personal experience and which I’ve faced in trying to write code that performs acceptably in time and space :
“Whatever problems I may have, an unwillingness to learn new things is not one of them. I love to learn new things. That’s one of the reasons I hate Java, because learning Java didn’t teach me anything except how truly brain-damaged a language can be. (I’ve never learned Perl, but I’ve never learned how to run the deep fryer at a McDonalds either. I like learning new things, but life is short and there are some things I’m content not to know.)”
Brave New World – Aldous Huxley : Re-reading but not from any paradise-engineering paranoia perspective. Simply insightful, focused and a great style. First covered this in high school decades ago. It’s ironic and deviously cool that this was actually course mandated at my high school ! (Have yet to finish Island.)
Plenty of social psychology observations that should be common sense if you’re paying attention to the world around you. Read it on recommendation thanks to Scott Adams.
**Neil Gaiman’s “American Gods” – **
Yea yea, it’s nothing new but got through it last year and realize why his books morph fairly quickly into Hollywood scripts. Not much else to say about it.
If anyone wants to test Firefox 3.0 BETA 2 on FreeBSD then then here’s a static build. (I’ve only tried it on 6.2 let me know if you have a different version)
I couldn’t find a 3.0b2 build for FreeBSD on the Mozilla site. Pretty normal though I’m guessing most FreeBSD folks just wait for newer versions to show up in Ports.
A movie with a cast including Ray Kurzweil(as himself), Marvin Minsky, self-help guru Anthony Robbins, Alvin Toffler, Mitch Kapor, Bill Joy, Aubrey de Gray and more.
*… the commercial software community has developed one particular response to resource limitation: a fevered, workaholic approach to software development—error prone, hectic, family-destroying, health-degrading, night-haunting. If you are undermanned by a factor of 2, add a second 8-hour workday per physical day. If you are operating under a schedule 50% too short, add in another 32 hours per week by working weekends. Then pray for luck or push back on features and quality.
Some Haskell fans seem impressed with better performance for a fibonacci function compared with similar implementations in Ruby and Python. They should be. I may be turning into a Haskell fan myself actually. Here’s why …
According to this telegraph article : “an Ipswich-based businessman invented a £190 bottle that makes foul-smelling water drinkable in seconds.”
That’s about US$380 over here. Each bottle can filter 4000 or 6000 liters without changing the filter.
Also the bottle can make fecal matter safe to drink because it filters anything longer than 15 nanometres. This means that bacteria which are smallest at 200 nanometres(filterable by conventional water filters) and even viruses which are usually smallest at 25 nanometers can be filtered.
I’ve ranted previously about Python and made promises of future posts about why Ruby is so much cooler. It really is and the topic of this article covers one of the common idioms used by most Ruby folks who may have taken a shot at their own domain specific language in Ruby. The following is one of the really useful idioms but apparently not a very well understood or well explained one for Ruby coders.
The previous post was pretty grumpy about Python/Django and I was going to write a follow-up about why Ruby is a better language (unfortunately not the platform’s performance just yet but that is soon to change with YARV).
For this post to appear more fair about Ruby/Python than the last let’s look at one reason where these don’t come close to Lisp. This is something mentioned less often(but still important) when comparing Lisp with other languages which usually focus on macros and s-exprs.
The Regressive Imagery Dictionary (RID) is a coding scheme for text analysis that is designed to measure ‘primordial’ and conceptual content. Primordial thought is the kind of free-form, associative thinking involved in fantasy and dreams. Like Freud’s id, I guess. Conceptual (or secondary) thought is logical, reality-based and focused on problem solving.
RID contains about 3,000 words grouped into categories that are themselves classified as primary, secondary, and emotional. A piece of text is classified by what percentage of its words fall into each category.
‘Being John Malkovich’ is a 1999 film written by Charlie Kaufman and directed by Spike Jonez.
The movie stars John Cusack, John Malkovich, Cameron Diaz, Catherine Keener, Charlie Sheen, Orson Bean and Mary K. Place.
warning – mini spoiler below *
The film centers around Craig Schwarz(John Cusack) who finds a portal into John Malkovich’s subconscious. He exploits this to win the affection of Maxine(Catherine Keener) who he is in love with but has no interest in Craig.
‘A train wreck is a project where everyone assumes things are going well, progress is being made, and it appears that everything will turn out well. In reality, the train is barreling down the tracks at good speed until it hits the bridge that is out and then crashes spectacularly into the valley. No one is actually driving the train and all anyone sees is out the side windows, so the illusion of progress is great.’
“THE DALLES, Ore., June 8 — On the banks of the windswept Columbia River, Google is working on a secret weapon in its quest to dominate the next generation of Internet computing. But it is hard to keep a secret when it is a computing center as big as two football fields, with twin cooling plants protruding four stories into the sky.”
An early look at artificial Intelligence. Guests includes Edward Feigenbaum of Stanford University, Nils Nilsson of the AI Center at SRI International, Tom Kehler of Intellegenetics, Herb Lechner of SRI, and John McCarthy of Stanford. Featured demonstrations include Inferential Knowledge Engineering and the programming language LISP. Originally broadcast in 1984.
AND
Daniel G Bobrow: Common LISP Object Standard (1987)
Regarding the role of Lisp and game development (specifically on the PS2), Andy Gavin has this to say…
“Lisp was just the best solution for this job,” comments Gavin. “With leading edge game systems like ours, you have to deal with complicated behaviors and real-time action. Languages like C are very poor with temporal constructs. C is just very awkward for a project like this. Lisp, on the other hand, is ideal.”
*“To me the most demoralizing aspect of the traditional office is that you’re supposed to be there at certain times. There are usually a few people in a company who really have to, but the reason most employees work fixed hours is that the company can’t measure their productivity.
The basic idea behind office hours is that if you can’t make people work, you can at least prevent them from having fun. If employees have to be in the building a certain number of hours a day, and are forbidden to do non-work things while there, then they must be working. In theory. In practice they spend a lot of their time in a no-man’s land, where they’re neither working nor having fun.
Recently I took a fresh at look at the Go programming language after having last taken a look at it before version 1.0 was released back in 2009. What I’ve found in just a few days is shocking in a really really good way.
The questionable widespread technical interview process has it’s roots in a cold war era approach that was pioneered by a public proponent of eugenics. Minorities suffer the most from the industry continuing to use this long disproved ritual of conformity.
“It looks like a plane but will it fly ?”
Something very interesting has happened early on in the Summer of 2020 while quietly very disturbing for Apple.
or The Complexity of the Dollar
Saintly Man? - That Mitchell & Webb Look - BBC Two
