read


read
or learn more

Perlis Languages

Aug 14, 2011

this is another entry in a series on programmer enrichment

A language that doesn’t affect the way you think about programming is not worth knowing. — Alan Perlis

inspired by a LtU thread and the great post Programming Achievements: How to Level Up as a Developer by Jason Rudolph1. most code samples from Rosetta Code.

The philosopher Friedrich Nietzsche believed that all interactions and interpretations of the external world occurred through the lens of individual perspective. Therefore, truth to Nietzsche was subject to interpretation. Programmers are especially prone to subjective views on their industry best-practices and valuations, often colored by their chosen2 programming languages.3 However, Nietzsche believed that in order to achieve a high-level of thinking, one should grant all perspectives equal opportunity and let them stand, or fall, on their own merits. You’ve probably experienced this approach yourself in college if a professor demanded the classic assignment whereby students write an essay taking the side of an argument that they themselves denounce. This type of exercise is potentially very powerful in that it often works to crystalize one’s own beliefs and occasionally helps to shake those beliefs to the core.

A Perlis Language is a programming language that I believe will shake one’s views on software development to the core.

Below I will enumerate4 some of my Perlis Languages and give an all-too-brief overview and just a sip of code for each.

Joy

Joy is an example of a concatenative programming language or more simply put, a stack-based language. That is, functions are never explicitly passed arguments, but instead take an implicit stack that is maintained by the programmer. This may seem totally insane, a sentiment not wholly inaccurate, but the levels of succinctness and elegance achieved via this model is stunning. The complexity in maintaining a stack is typically handled by concatenative programmers through the process of vigorous factoring of words (think functions) into smaller words. There is a whole class of purely stack-manipulation primitives that signal the need for factoring when their use becomes too pervasive. The goal is to constantly drive the code toward an expression of the domain rather than an expression of the programming language-specific expression of the domain. There are certainly better and more historically significant concatenative languages, but Joy strikes a nice chord with me — your mileage may vary.

(* Quicksort in Joy *)

DEFINE qsort ==
   [small]
   []
   [uncons [>] split]
   [swapd cons concat]
   binrec .

More information

possible substitutes: Factor, Forth, Cat, PostScript

Eiffel

Eiffel is an extremely opinionated object-oriented programming language. Like myself, many programmers today have a majority-share of “real-world” experience in one OO language or another. However, you haven’t used anything like Eiffel. That is, the bulk of Eiffel will be recognizable to most programmers, but the enlightening feature for most is the first-class support for Design by Contract. In a nutshell, DbC (or contracts programming) is an approach that allows one to specify the expectations on method results based on their required input parameters and also to define class-level invariants.5 This may seem fairly simplistic, but it’s in this simplicity that forms the basis for an extremely powerful design paradigm. In fact, contract support libraries and extensions have been created for other languages: Ruby, Clojure, C++, Java, and Groovy to name only a few.

-- Dictionary class fragment

class DICTIONARY [ELEMENT]
feature
    put (x: ELEMENT; key: STRING) is
            -- Insert x so that it will be retrievable
            -- through key.
        require
            count <= capacity
            not key.empty 
        ensure
            has (x)
            item (key) = x
            count = old count + 1
        end
invariant
    0 <= count
    count <= capacity
end

More information

possible substitutes: D, Cobra

Qi

Qi is a Lisp — big deal right? Wrong. Qi is a Lisp with skinnable types, a built-in logic engine, rewrite rules, back-tracking dispatch, built-in lexer and parser generators, and pattern matching that compiles down to highly-performant Common Lisp. The author Dr. Mark Tarver has strong opinions on the state of the software development in general and Lisp in particular (you may already have read The Bipolar Lisp Programmer) and these opinions shine in the implementation of Qi. The successor to Qi, Shen, is in active development with a release scheduled some time this summer.

\ A simple expression calculator \

(datatype arith-expr

    X : number;
    ====================
    [num X] : arith-expr; 

    if (element? Op [+ - * /])
    X : arith-expr; Y : arith-expr;
    ===============================
    [X Op Y] : arith-expr;)

 (define do-calculation
  {arith-expr --> number}
  [X + Y] -> (+ (do-calculation X) (do-calculation Y))
  [X - Y] -> (- (do-calculation X) (do-calculation Y))
  [X * Y] -> (* (do-calculation X) (do-calculation Y))
  [X / Y] -> (/ (do-calculation X) (do-calculation Y))
  [num X] -> X)

More information

possible substitutes: Pure

Clojure

Clojure is a fantastic language, but let’s just say that I have some skin in this game. Take this entry with a grain of salt. So instead…

Kernel

Kernel is also a Lisp, but it differs in that it completely eliminates the line separating compile-time and runtime via fexprs. In short, fexprs are functions that do not evaluate their arguments until explicitly called on to do so. Kernel achieves this seemingly impossible behavior by treating environments as first class objects that serve as the evaluation context. This handling of environments also helps to make Kernel evaluation hygienic since the evaluation context of any symbol or combination is fully controlled. Needless to say this is voodoo of the highest order, but the rules of the language are simple and consistent and it’ll blow your mind to see how its underpinnings start at a deeper and more abstract position than even McCarthy’s original.

;; The implementation of apply in Kernel
;; This is typically a Lisp primitive

($define! apply
   ($lambda (appv args)
      (eval (cons (unwrap appv) args)
            (make-environment))))

More information

via Manuel Simoni and Patrick Logan

possible substitutes: newLISP

Mozart/Oz

Oz is truly a “my language has more paradigms than yours” kind of language.6 Oz (like many hyper-multi-paradigm languages) is unfortunately relegated to the “educational language” category, but regardless its influence pervades a lot of the thinking in distributed and dataflow computation (Akka for instance is deeply influenced by Oz). As an added bonus, the canonical book on Oz, Concepts, Techniques, and Models of Computer Programming is in my top ten must read list for developers. It’s apt that a mind-bending language should couple with a likewise mind-bending book.

%% Towers of Hanoi in Oz

declare
  proc {TowersOfHanoi N From To Via}
     if N > 0 then
        {TowersOfHanoi N-1 From Via To}
        {System.showInfo "Move from "#From#" to "#To}
        {TowersOfHanoi N-1 Via To From}
     end
  end
in
  {TowersOfHanoi 4 left middle right}

More information

possible substitutes: Erlang, Prolog, Mercury, Alice

RCA COSMAC 1802 Assembly

RCA’s 8-bit Cosmac processor was shot into space as a main component7 of the Galileo spacecraft, but it’s novelty lies in its bizarro architecture. For example, while the processor did not support a CALL instruction, it did support subroutines through the fact that any of its 16 16-bit registers could serve as the program-counter. Likewise the 1802 did not have a stack, but clever register usage was often the cure for this “deficiency”. In addition it had a very simple I/O port that hackers used to maximum effect. While not the fastest CPU ever made (nor even in its time), the stark simplicity of the processor and its assembly code will make for a mind-bending experience. Coupled with a visual emulator (see link below), it’s fun to see the consequences of each instruction.

... stack push
GHI R3
STXD
GLO R3
STXD

... stack pop
IRX
LDXA
PLO R3
LDX
PHI R3

More information

possible substitutes: MIX, The Art of Assembly Language Programming

Frink

Frink is a programming language that is generally known for its ability to handle and convert between a bevy of units of measure consistently throughout calculations. For anyone who has created a complex system (or even a simple one for that matter) that needed to juggle varying units of measure, the complexity of the problem that Frink handles seamlessly is staggering.

// Levenshtein distance is a built-in
println[editDistance["kitten","sitting"]]

// Convert feet to meters
38 feet -> meters

More information

possible substitutions: none

APL

I will be honest. I have never used APL and as a result find it impenetrable. However, my inclusion in this list is entirely predicated on the strength of the amazing book A Programming Language by Kenneth Iverson. That is, the best programming language books infuse a strong sense of design8 into the narrative. The strength of this approach is that not only are you learning a programming language, but you’re also learning how to think in that language, and the very why of the language itself. Iverson’s book elucidates the motivating forces behind the design of APL (the need for a universal notation for computation to name a primary) and systematically builds the rationale for APL and the realizing language incrementally. This book is not for the squeamish, and you will likely not fully understand APL by simply reading it (although I may be projecting here), but it’s worth the effort.

⍝ John Conway's "Game of Life" in APL
life←{                                  
    ↑1 ⍵∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵
}

More information

possible substitutes: J, K

Haskell

Haskell is my mind-bending language of choice at the moment, but if you’re not prepared to be humbled you may not find it as agreeable. That is, before learning Haskell you will think that you know a lot about:

  1. Static typing
  2. Laziness
  3. Purity

But Haskell will laugh at your knowledge and show you otherwise. It’s that simple — and to learn more about these topics when you think you’ve learned all there is to know is a slap in the face — but the good kind — the kind that wakes you from your dogmatic slumber.

-- Sierpinski triangle in Haskell

sierpinski 0 = ["*"]
sierpinski n = map ((space ++) . (++ space)) down ++
               map (unwords . replicate 2) down
    where down = sierpinski (n - 1)
          space = replicate (2 ^ (n - 1)) ' '

main = mapM_ putStrLn $ sierpinski 4

More information

possible substitutions: ML, OCaml, Agda, Scala

I hope that this list9 will motivate you to explore one or more (or all) of the languages herein. I think you’ll find the effort worthwhile should you approach the task with an open mind.

What are your Perlis Languages?

:F


  1. My modifications to Jason’s original list can be viewed at https://gist.github.com/1138647

  2. Or those that chose them in most cases. 

  3. Programming language favoritism is just one of many prejudices that infect programmer thinking, but I choose to focus on it for the puposes of this post. 

  4. In no particular order. 

  5. I realize there is more to DbC than that, but this post is already overlong. 

  6. I sometimes poke good-natured fun at Scala about this, but sheesh they don’t even have a builtin logic engine. ;-) 

  7. Although it seems to have been chosen by default since there were very few (if any) radiation-resistant microprocessors at the time. 

  8. I have a draft of a post about books of this type… one day I’ll complete it. 

  9. There are others that I could have (should have?) mentioned. Others like: Squeak, Scheme, Common Lisp, Prolog, and even more still… but I felt that others might like to talk about these and any others I’ve missed instead. 

33 Comments, Comment or Ping

  1. I don’t know if it shook my beliefs as much as making me refine them further with a much greater emphasis on fault tolerance, concurrency and distribution. The language which has impacted my thoughts for the best in the recent years has been erlang.

  2. Siniša

    The Haskell example is missing an argument to the sierpinski fucntion in main.

  3. fraya

    The Qi example shows a calculator using a label (or constructor function) to mark out the numbers within an arith-expr (used in SML family of PL). With this implementation an arith-expr for adding 2 and 3 should be [[num 2] + [num 3]]. It can be easier with verified objects (see http://www.lambdassociates.org/Book/page165.htm of “Functional Programming in Qi (second edition)”), just changing the first condition of the datatype with:

    (number? X) : verified >> X : number;

    and the last line of do-calculation with:

    X -> X where (number? X)

    Now we can use [2 + 3] like arith-expr.

  4. Glen Stampoultzis

    I really need to look further into Haskell. I’m having too much fun with Clojure at the moment however.

  5. @fraya

    Wonderful! Thank you for the additional information and modification.

  6. @Siniša

    Thank you for the correction. Fixed.

  7. @Dhananjay

    That’s the beauty of Perlis languages — they’re relative. These were mine and I think they have an advantage of providing features (for the most part) not generally represented in the mainstream. However, someone else might know all of these and instead find a completely different Perlis set.

  8. Parnell Springmeyer

    I have to second the comment mentioning Erlang – Erlang, like Haskell and many of the other languages in this list has taken me 3 years to “grok” and it has truly changed not just how I program but also how I think.

    What’s also cool about Erlang is it’s industrial application too – Haskell and the others do have examples of industrial application, but probably no where near as widespread as Erlang’s. This language both bends your mind and provides a feature set/tool set that can be applied to solve real world problems other languages cannot.

    Great article though! +1 for good and original descriptions of the languages.

  9. Very nice list — hits at least a few that I had forgotten, disregarded (in the personal sense) or just not really given much thought to. I’m curious though, in regards to CTM, you mention a top-ten list, but a link to said list is noticeably absent (hint, hint). ;)

  10. I’m still craving for a little bit of time to experiment with it but I think that Bondi: http://bondi.it.uts.edu.au has a promising future for a “Perlis” language. With Bondi (and the underlying pattern calculus), you have ways to make your code generic as never before. It’s next on my list!

  11. I’m starting to play around with dependently typed languages. I’ve been reading up on both Coq and Agda. They’re very impressive.

    On the concatenative side, Cat is something that I’ve wanted to try out for a while now. I hope I’ll eventually get around to it.

  12. Greg

    its a shame you didnt mention the JML/Contract Library/Spec# compile time proving systems when talking about DBC … its night and day when contracts are proved at compile time.

  13. Nelson

    I’m no Oz expert, but it seems like there are unmatched curly braces on the last line?

    I was happy to see Frink get some props twice in the last week. A team using Frink won a programming competition at DEFCON last week. (Teams could use any language they wanted. I think they won all the problems, except maybe the last one, in which they were given a harder problem than everyone else!) I’ve been using Frink since high school and I can’t tell you how many times that people have thought me to be some sort of physics genius because of some quick calculations I did with Frink. It honestly makes me effectively smarter.

  14. rmxz

    Curl.

    People often say that XML is kinda like s-expressions; and that markup-languages have different strengths than programming languages.

    IMHO Curl proved the former true and the latter false.

    With code like “Hello {bold Bold} World {+ 1 1} {raytrace world}” able to be the equivalent of “

    Hello Bold World 2

    ” it blended the best of HTML with the best of LISP.

    http://groups.csail.mit.edu/cag/curl/wwwpaper.html

    http://en.wikipedia.org/wiki/Curl_%28programming_language%29

    http://en.wikibooks.org/wiki/Curl

  15. rmxz

    (hmm – my HTML equivalent example didn’t render right – sorry for the confusion, but the links explain it better than my example anyway.

  16. manu

    Nice post.

    I had great fun at understanding (the basics for) both Common Lisp and Haskell through the great works of Mr Barski: http://www.lisperati.com/ He uses very concrete examples in a fun way to progressively build a complex but moreover idiomatic solution.

  17. For me Ruby was a Perlis-Language. It change my thinking about typing 6 years ago. I was a strong proponent for static typing before. Now I prefer dynamic typing (in form of duck typing) in combination with unit tests/specs in most situations.

  18. prakash

    Terrific list.

    [CTM] in my top ten must read list for developers.

    Where is this list, Mr. Fogus? Is that a post in the making? The closest match I found on your site is: (Building) The 7 Books of a Highly Effective Programmer [http://blog.fogus.me/2009/03/11/seven-books/]

    Thanks.

  19. Jason

    If you’re more hardware inclined, check out http://greenarraychips.com/ for a mind-expanding chip architecture. It’s a clockless massively-parallel stack-based (Forth) chip that also takes an unusual approach to I/O (e.g. the ADC is a VCO that feeds into a counter).

  20. I note your Kant reference with relish.

    APL appears to be a perplexing language. I can’t blame you for not using it.

  21. For me it wasn’t any particular language that altered the way I think about programming in a fundamental way. I don’t think of programming languages as anything more than tools. Some are certainly better to use than others for various applications or personal preferences of course. However I don’t think picking up a shiny new hammer is going to change the way I think about carpentry (although it may make it more pleasurable).

    What really changed the way I think about programming on a fundamental level was reading The Little/Reasoned/Seasoned Schemer books. That the language they use in those books is Scheme is almost trivial. The really mind-blowing moment for me was the build-up to a “proof” (if you can call it that) of the Y-Combinator. Up until that point I had only read dry descriptions of what it was, but had not seen a demonstration of its significance. Once I understood that concept a whole slew of disparate knowledge became highly connected in my mind. I think I experienced something akin to a paradigm-shift.

    What convinced me that it wasn’t necessarily Scheme that altered this thinking, but the concept demonstrated in the language of Scheme was that it was applicable to a wide range of languages I have used and never used. No single language laid claim to the Y-Combinator as a feature; yet so many were built upon it or implemented it in some fashion. Without even knowing what it was I was able to create programs just fine. After having only read descriptions of it in various forms I could appreciate it on some level but thought of it as irrelevant in terms of practical usefulness (ie: it just seemed academic). However, with a thorough understanding of it I could see patterns in many languages that I hadn’t seen before.

    So I have since become convinced that learning how to write programs in a particular language whether it is obscure and foreign or quite comfortable and easy to understand is not terribly important. It only scratches the surface. I am now convinced that there are fundamental concepts of computing that once understood will certainly change the way you think about the tools you use.

  22. Isaac

    I would also recommend looking at OMeta. It puts Lisps’ “programmable language” concept to shame. :-)

  23. @Isaac

    I’ve heard too many times that OMeta is another Perlis Language… its drawn is very strong.

  24. The Pure language, while somewhat intriguing, is no substitute for Qi :

    “Pure is based on term rewriting rather than the lambda calculus.”

    “Pure is dynamically typed.”

    “Pure doesn’t attain the execution speed of compiled, statically typed languages, and because of its dynamic typing it probably never will.”

    http://code.google.com/p/pure-lang/wiki/FAQ#Why_Pure?

  25. David Cabana

    If you find that APL is a bit perplexing, here’s a suggestion. Take a few months to work through and really understand a good book on linear algebra (I like Strang’s ‘Linear Algebra and its Applications’). It will help a lot with the APL, and you’ll learn some very useful math.

  26. You have written yet another thought provoker. Thanks.

    In a sea of 4GL and Perl, I look forward to finding Clojure applications in our production environment. I’ve already found one, tax bill address verification.

  27. @drcabana

    Thanks for the advice. I might just do that.

  28. @JustinGrant

    You’re correct of course. Pure is no substitute and most likely deserves to stand on its own. Thanks for reading.

  29. Alvin George

    just knowing about non deterministic languages, have added one more perspective for me. http://en.wikipedia.org/wiki/Esoteric_programming_language#Nondeterministic_language

  30. William H. Mitchell

    I’d say that SNOBOL4 and Icon belong on the list. SNOBOL4 has a pattern matching facility that recognizes unrestricted grammars. Gimpel’s “Algorithms in SNOBOL4″ is a remarkable exploration of the strange and beautiful.

    Perhaps the most striking feature of Icon is that expressions in any context can produce 0, 1, or many results.

  31. Robert Goldman

    I am glad you listed APL in your list of Perlis languages, since that’s the language I took introductory programming in — from Alan Perlis!

    I may be wrong about the precise period, but if I recall correctly, it was only after the midterm that we were allowed to write programs with variables and assignment. Until then, we wrote one-liners that used the applicative nature of APL to compute quite complex functions in very elegant ways.

  32. Jav Gamero

    Delightful lecture about an enjoyable subject: programming languages.

    Beautiful languages, Clojure, Factor, Haskell, Icon, etc. I like a lot to programm in APL, in fact my more comfortable language is J (close relative to APL). APL is so beautiful and challenging. I have to say I continue enjoying a bit of relax using a modern BASIC (some of them are superb), ironically it can “change” your mind coming back to “simple” and effective ways to do things.

    Thanks a lot!

Reply to “Perlis Languages”