#commonlisp

[mirqmarq428]

Every time I want to get into CommonLisp it's smooth sailing in the theory, everything is the same as elisp but slightly better, and then I go to use it in practice and end up in the wrong namespace, with no way of discovering what namespace has the things I want to use or even how to break out.

I get several chapters into a tutorial. It's a beautiful, wonderful tutorial. I am bored since everything is as I expect. I look at the table of context. I'm on chapter 5 and namespace/package are in chapter 22.

To anyone approaching this language in $CURRENTYEAR who's familiar with Emacs, this is the MAIN DIFFERENCE between the two environments. And it's PRACTICALLY A FOOTNOTE.

[danielkvasnicka]

Using Advent of Code 2019 to rediscover Common Lisp

UPDATE: Added generic-cl as suggested on Reddit.

Before last year’s Advent of Code started I declared on Twitter that I was going to do it in Common Lisp. And so I "did" (with a couple of 2016 challenges in CL as well). Yes, quite a bit of the challenges are missing. I hope to get back to them some time 😇

This writeup will be a summary of what I liked, what I did not like and finally a set of libraries for various purposes I used and found interesting. There are a couple of lists like that on the net (especially https://awesome-cl.com/, which I have actually submitted PRs to during my work on this article) but I wanted one that would include a couple of comments based on my personal experiences -- basically I’ll be making a purely subjective list of things I don’t want to forget about and it so happens that it will be publicly available on my blog 🤓

Just so you know, the views here will be expressed from the PoV of a long time Clojure and Racket fan.

Pros & Cons

Let’s start with what I liked:

Speed -- the best CL implementations are fast, while still allowing you to maintain a very readable, high level idiomatic code. With SBCL, the most popular implementation, you are basically getting one of the fastest lispy experiences possible. We obviously need to address the elephant in the room here and that’s Cloure. Clojure, thanks to JVM, can be faster than Common Lisp. However the speed often times comes at the cost of writing a relatively ugly “C wrapped in parens” style of code and/or you need enough data to get good amortization while JITting.

Debugging and optimization -- this one kind of relates to the first point as well. Common Lisp contains very powerful debugging, introspection and optimization tools that are part of the base lang spec. It does not matter what kind of implementation you use or whether you are using the IDE everyone thinks is the coolest right now... Hell, you can even disassmble your program to see the actual ASM code that your CPU will juggle.

Stability of the language -- there are people who can express this better so I’ll just link to the appropriate section of the magnificent article Steve Losh wrote in 2018:

My advice is this: as you learn Common Lisp and look for libraries, try to suppress the voice in the back of your head that says "This project was last updated six years ago? That's probably abandoned and broken." The stability of Common Lisp means that sometimes libraries can just be done, not abandoned, so don't dismiss them out of hand.

Specification & standard (kinda applies to Scheme as well) -- This is a tricky issue that has started many flamewars in the past, not just in the Lisp world (see the Spring vs Java EE battle). Having to adhere to a spec brings limitations but there are 2 counterarguments I can think of in the case of CL:

The power of macros means you can overcome almost all cases of stalled innovation without performance penalty. Look at the loop macro and how it was essentially completely covered with zero-cost abstractions.

The myriads of Clojure-like languages all suffer from the same problem: You cannot use libraries or any of the cool tools in the ecosystem. Yet, they themselves do not have anywhere near the traction necessary to be widely used production languages. CL shows that you can have a standard and still have enough room for differentiation and innovation.

Lisp-2 -- yep, you read that right. I would have never expected to say this (and I believe I’ve actually shunned Lisp-2 on this very blog some time ago?) but I actually like that functions in Common Lisp live in a separate namespace, for a very simple reason: code is read way more ofthen than it is written. When I look at code and see that seemingly annoying funcall I know it’s not just a top level defunned function and that I need to trace its origins somewhere else. Similar principle applies for the #' prefix (also makes life easier for syntax highlighters).

Next, the annoyances:

Widespread mutability and imperativeness -- Mutability is good if used in specific cases where it makes sense and if quarantined properly. However in CL mutability is king. It's not as much a problem of the language or implementations (you don't have to write mutable code) as it is a problem of the historical baggage -- it was never customary in the CL land to look bad at code that creates a mutable collection, then puts stuff in it in an imperative cycle and returns it from a function out to the dark and cold world... Purely functional collections exist but CL is not built around them. This is where Clojure shines.

CL Sequences apparatus not being user-extensible -- Common Lisp has a concept of sequences which puts a roof over lists and vectors and allows the user to use one function for both. However this facility, for some reason, is not easily extensible. This leads to many libraries implementing various new data structures and using completely custom API to do simple things like getting the size of a collection because (defmethod length ((seq my-epic-data-structure)) ...) signals COMMON-LISP:LENGTH already names an ordinary function or a macro. Fortunately there are libraries that are trying to solve this and to be honest it is not that much of a PITA anyway, because using a different function name for a special data structure has positive readability and performance implications. This applies to Racket too, to some degree. This lack of extensibility might have technical reasons I don't know of and if that is the case I'd be curious to learn and understand them.

LOOP -- I hate loop. Fortunately, this is an issue only if you have to deal with legacy code. The iteration story in CL is so good that you'll basically never have to write a single line of loop if you don't want to. My favourite comment on the topic is this one.

Destructuring not being 1st class citizen (enough) -- CL has macros with annoyingly long names to do destructuring and does not have the concept built-in deep enough for it to be ubiquitous in e.g. function definitions like you can see in JS or Clojure. Fortunately -- you guessed it -- libraries solve this issue satisfactorilly.

Interesting tools and libraries

What follows is a set of libraries that I tried and found useful -- libraries that helped me make a lot of annoyances (almost) irrelevant. I'll include one or two libraries that I have not used yet but would like to as they seem cool to me:

Platform tools

Quicklisp -- primary source of packages for CL. There is also Ultralisp, which is a faster-moving package distro.

Roswell -- this became my go-to tool for managing implementations and also packages. It can install packages from Quicklisp as well as GitHub repos in a manner similar to how go get works for example.

Qlot -- project-local dependencies manager that works well with Roswell. Think npm for Common Lisp. Can get dependencies from other Git repos, not just GitHub.

General purpose

Alexandria -- this is the utilities library in the CL world. It's so widespread that it's almost a standard thing.

Serapeum -- the Serapeum of Alexandria was an ancient Greek temple; referred to as the daughter of the Library of Alexandria. You get the idea ;) As you can see, the library is massive and I include it in most programs I write.

rutils (API) -- another impressive assortment of functions and macros. I would especially like to point out the with macro in the rutils.bind package, which is a kind of an extensible über-let.

metabang-bind -- another let on steroids. Unlike with it can bind arrays/vectors out of the box but is a little bit more chatty (and probably not as actively maintained).

cl-losh -- this is a library that its author explicitly does not want you to use. Sorry, Steve :) Your library is way too good for me to abide by your orders. What I found especially useful is the library of extensions for iterate, the de-facto replacement for LOOP we'll discuss later.

CL21 (and its very recent revival named 20XX) -- very interesting attempt at refreshing some of the more antiquated aspects of CL. It can be used as a library only to cherry-pick good stuff but it's probably less painfull to go all in and write programs "in" CL21 if it makes sense for a particular package.

cl-str -- Modern, simple and consistent Common Lisp string manipulation library.

Iteration & sequence procesing

iterate -- IMHO overall the best of iteration libraries for Common Lisp. A significantly lispier alternative to LOOP. Allows for very idiomatic, concise and understandable iteration code, is extensible and widely accepted and extended.

series -- the original transducers library (yes, those transducers). When used in tandem with taps (see my fork with a bugfix as well) it allows the programmer to write very succinct "top level" code (e.g. the main driver of a program that reads from a stream and delegates work to other parts of the code), or complex pipelines in general.

for -- another extensible LOOP replacement, this time a bit closer to Racket's ecosystem of for comprehensions.

gmap -- this is probably one of the most underrated/under-popularized pieces of gear I've come across in the Common Lisp land (tracing its origins back to 1980!). Combines mapping, filtering and reducing into a neat transducer-ish extensible construct and has a built-in support for FSet, a functional collections library we'll talk about later. The same Lisp project also contains new-let ...guess what is it supposed to be 😉 Yeah, let is the new loop.

generic-cl -- provides a generic function wrapper over various functions in the Common Lisp standard, such as equality predicates and sequence operations. An answer to on of my critical points above (defines generics that overlay CL builtins).

You can also find many small iteration helper tools scattered across the general purpose libraries we discussed in the previous section. Mapping from X to Y, reducing all kinds of things etc...

Math

cl-geometry -- 2D computational geometry library, which made work on Day 3 of AoC 2019 very enjoyable for me.

Data structures

FSet -- functional library of sets, maps and bags that has a natural and clean API and as we already mentioned, it comes with the added bonus of being written by the same guy who wrote gmap.

cl-containers -- a massive collection of (mostly tree-based) data structures and algorithms, useful when you need stuff like sorted map etc.

graph-utils -- graph data structure and algorithms

sycamore -- fast purely functional data structures

random-access-lists -- useful library for when you need a listy data structure and you don't want to pay O(n) when accessing elements in it.

array-operations -- library for concisely expressing operations on (multidimensional) arrays. Being used to the Racket array library it took me a while to get used to some of the specifics but it indeed is very powerful and fast.

Static typing & contracts

Apart from the built in tools for specifying types statically you can also use these to strenghten your safety net:

defstar -- Macros for easy inclusion of type declarations for arguments in lambda lists. Can replace defun, defmethod, defgeneric and others.

cl-algebraic-data-type -- a library for defining algebraic data types in a similar spirit to Haskell or Standard ML, as well as for operating on them

quid-pro-quo -- A contract programming library for Common Lisp in the style of Eiffel’s Design by Contract

Testing

These are the two testing libraries I tried out. I prefer parachute, the API feels more natural to me. There are others and it's getting worse 😉

rove

parachute

OOP

In addition to the following libraries you should check CLOS-related sections of almost all of the general purpose util libraries we discussed above. They contain stuff to help make CLOS a bit less verbose.

defclass-std -- a macro that atempts to give a very DRY and succint interface to the common DEFCLASS form. The goal is to offer most of the capabilities of a normal DEFCLASS, only in a more compact way.

sheeple -- prototype-based OOP in Common Lisp? 😱 Because we can!

Verdict

So is CL my new favorite language that I'll be using for everything from now on? No, not really. But in my book it's moving from a language that I wasn't really taking very seriously to a language that has a fixed place on my toolbelt. One scenario where I can see it shine is situations where I don't want (need?) to use Clojure but Racket / Scheme does not have the right libraries.

[hydralisk98]

LibreVastServitor computing stack designs 1/?

Just a quick reminder here, this is a customized computing stack manifestation game where I simply write what I desire and then let the wider universe manifest it for me whatever way that means, including personal efforts of mine. Boils down from customizing and adapting research material into a actionable series of items to manifest.

Ashur dream specifications

(mid-tower personal workstation computer)

2+ 2560x1440p monitors (one vertical, one or more horizontal)

Intel Core i5-4690 @ 3.5 GHz with its 4-cores (hoping forward to upgrade the RISC-V + OpenPOWER like processor for something decent with ~12-cores & much more open design) central processor unit

32GB of RAM

Some recent mid-range AMD GPU

64 GB Linux swap partition (mostly for virtual machines and RAMdisk partitions)

4TB+ SSD storage

Bluray burner

Floppy drive

Cassette / datasette drive

Themed GRUB bootloader

S6 init system

Arch-like package manager and software ecosystem

Customized alternative Linux kernel between Linux Libre & Zen kernel ( XanMod + Liquorix )

ZealOS, Parade, OpenBSD, OpenIndiana...

CLADO, DIS, Venera, Perseus, Maskoch, Synod, Monad, Valenz, Constans?

KDE Plasma with Liquid shell as desktop environment, complete with custom ricing, dot files & all the KDE desktop environment utilities;

Bash + Fish, Tmux, Astro-Neo-Vim with LSP, Emacs, LibreOffice Suite, Calligra, Bottles, Wine, WineTricks, QGIS, Firefox, LibreWolf, Dolphin, Konsole, Inkscape, Karbon, OpenStreetMap, GPlates, GProjector, Itch, Steam, GOG Galaxy, Lutris, Cyberpunk 2077, Ken Silverman's, FreeBASIC, Common Lisp, Godot + Qodot, VLC, MPV, .ogg / .ogv media player, musical tracker, 'Landchad.net', Brasero, K3B, FloppyFormatter, LibreCAD, AutoCAD, Blender, Kate, Qt, Nim, MUSL, C compiler, assembly monitor, HxD debugger, Rust, Swift, Kotlin, F#, C#, GNU make, NASM, Sweet Home 3D, some digital audio workstation software, Audacious, FFMPEG, Wayland, Morevna OpenToonz, some HTTP(S) web server suite, MongoDB, Hexo, Netlify CMS, RSS feed reader + generator, Pomodoro, Calendar, timely Tracker, Notion-like service, Tape, Gollum, some level editors, FreeCiv, The Sims 2, SimCity 4, Quake 1, Doom 1 & Doom 2, Markdown / Argdown, Konqueror, some WYSISYG rich media editor, some Raycaster engine, Daggerfall Unity, Portal 2, Source (1 & 2) Engine modding, some VirtualTableTop software, some remote desktop control software like VNC, OpenSSH, some distributed share storage software, Trenchbroom, StableDiffusionXL, ChatGPT open source alternative, DAO, Krita, GIMP, G'MIC & its plugins, PaintDotNet, CataclysmDDA, CataclysmBDA, Evennia, Python 3, Firefox for KDE (Developer Edition), Perl, PHP, MariaDB, lighttpd, Apache, Nginx, Themix Oomox GTK+ theme editor, Falkon, ...

Custom shell scripts, interactive REPL programming languages, some GUI programs, command aliases and dot file configurations;

?

Venera (computation "deque" project)

Original components:

RISC-V + OpenPOWER = LibreVast (tribble word-based open hardware architecture designed for daily use & tinkering developer purposes)

Tropix + OGAS = Nucleus (optimized distributed processing micro-kernel, like 'Inferno' & 'Plan9')

RedSeaFS + Parade = CLADOgram (direct-access rich media agentive filesystem & file server suite)

KDE + POSIX-compilant CDE = VUE (lightweight desktop environment with profound customization options)

CommonLisp w/ CLOS + Nim = Pan-Lisp (both low-level and high-level REPL programming language)

Existing components:

Fish, Tmux, Vim, Konsole, Flatpak, Git

KDE Plasma w/ Liquid shell alternative

Konqueror, LibreWolf

GIMP w/ G'MIC & Krita w/ G'MIC

Hexo (flat blog self-hosting web server), MariaDB, "Landchad.net" stuff

QEMU, Wine, Wine-tricks, Proton, Bottles, Lutris

Trenchbroom, Godot w/ Qodot

Kate, KDevelop, Okteta, Mousepad, Notepadqq

[...]

[dailyumwelt]

todays garnish

[kaygun]

Irreducible Dyck Words

Description of the problem:

A sequence of equal number of 0's and 1's is called a Dyck word if tracing from left to right, the number of 1's do not exceed the number of 0's preceeding it. For example "$ 0 0 1 1 0 1 $" is a Dyck word but "$ 0 1 1 0 1 0 $" is not.

Notice that if we concatenate two Dyck words we get another Dyck word. I will call a Dyck word reducible if it is such a concatenation of two Dyck words, otherwise I will call it irreducible. Today, I will write a lisp function that generates all irreducible Dyck words of a given length.

A simplicification

All Dyck words start with a 0 and they all end with a 1. Assume we have a Dyck word of length $2n$ with $n\geq 2$. If this word's beginning 0 were to be followed by a 1, then it would be reducible since the subsequence 1 were to be preceeded by 0 it would have been irreducible. So, all such irreducible Dyck words are of the form $$ 0 0 a_1 \cdots a_k 1 1 $$ where $k\geq 0$, and "$0 a_1 \cdots a_k 1$" is itself is a Dyck word.

An implementation

I already have an implementation that yields the collection of all Dyck words of a given length from an earlier post.

(defun dyck-words (n &optional (a 0) (b n) (acc (list nil))) (labels ((insert (i xs) (mapcar (lambda (x) (cons i x)) xs))) (if (= a n) (mapcar (lambda (x) (append (loop repeat b collect 0) x)) acc) (union (dyck-words n (1+ a) b (insert 1 acc)) (if (> a 0) (dyck-words (1- n) (1- a) (1- b) (insert 0 acc)))))))

DYCK-WORDS

One warning, the parameter is $n$ but the function returns all Dyck words of length $2n$. We just modify it:

(defun irreducible-dyck-words (n) (cond ((< n 1) nil) ((= n 1) '((0 1))) (t (mapcar (lambda (xs) (append '(0) xs '(1))) (dyck-words (- n 1))))))

IRREDUCIBLE-DYCK-WORDS

Let us check:

(irreducible-dyck-words 5)

((0 0 0 0 1 1 1 0 1 1) (0 0 0 1 0 1 1 0 1 1) (0 0 1 0 0 1 1 0 1 1) (0 0 1 0 1 0 1 0 1 1) (0 0 0 1 1 0 1 0 1 1) (0 0 0 1 1 0 0 1 1 1) (0 0 1 0 1 0 0 1 1 1) (0 0 1 0 0 1 0 1 1 1) (0 0 0 1 0 1 0 1 1 1) (0 0 0 0 1 1 0 1 1 1) (0 0 0 0 1 0 1 1 1 1) (0 0 0 1 0 0 1 1 1 1) (0 0 1 0 0 0 1 1 1 1) (0 0 0 0 0 1 1 1 1 1))

Let us count them too.

(mapcar #'length (loop for i from 1 to 14 collect (irreducible-dyck-words i)))

(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900)

Unsurprisingly, these are the first 14 Catalan numbers since there is a 1-1 correspondence between Dyck words and paranthesizations of words.

[masaa-ma]

gibo - プロジェクト用の.gitignoreを生成

from http://www.moongift.jp/2019/06/gibo-%e3%83%97%e3%83%ad%e3%82%b8%e3%82%a7%e3%82%af%e3%83%88%e7%94%a8%e3%81%ae-gitignore%e3%82%92%e7%94%9f%e6%88%90/

Gitでソースコードを管理する際、必ず必要になるのが.gitignoreでしょう。これがないと余計なビルドファイルやログファイル、OSの隠しファイルなどが入り込んでしまいます。かといって、.gitignoreの設定をプロジェクトごとに個別に設定するのは面倒なものです。

そこで使ってみたいのがgiboです。プログラミング言語に合わせた.gitignoreを生成してくれます。

giboの使い方

giboはdumpコマンドを使って出力します。言語や環境は複数指定できます。

$ gibo dump Swift Xcode ### https://raw.github.com/github/gitignore//Swift.gitignore # Xcode # # gitignore contributors: remember to update Global/Xcode.gitignore, Objective-C.gitignore & Swift.gitignore ## Build generated build/ DerivedData/ ## Various settings *.pbxuser !default.pbxuser *.mode1v3 !default.mode1v3 *.mode2v3 !default.mode2v3 *.perspectivev3 !default.perspectivev3 xcuserdata/

Javaの場合はこんな感じ（途中で省略しています）。

$ gibo dump Java ### https://raw.github.com/github/gitignore/310f125d232a837c93f482bc8b8703227b312419/Java.gitignore # Compiled class file *.class # Log file *.log # BlueJ files *.ctxt

gibo��対応している言語、フレームワークです。

$ gibo list Actionscript Magento2 Backup Octave Julia ROS Ada Pimcore Bazaar Otto KiCad Ruby Agda ThinkPHP BricxCC Patch Kohana Rust Android Puppet Calabash PSoCCreator Kotlin Sass AppceleratorTitanium JupyterNotebooks Cloud9 PuTTY LabVIEW Scala AppEngine Nikola CodeKit Redcar Laravel Scheme ArchLinuxPackages Racket CVS Redis Leiningen SCons Autotools Red DartEditor SBT LemonStand Scrivener C++ Splunk Diff SlickEdit Lilypond Sdcc C Xilinx Dreamweaver Stata Lithium SeamGen CakePHP Composer Dropbox SublimeText Lua SketchUp CFWheels Concrete5 Eclipse SVN Magento Smalltalk ChefCookbook Coq EiffelStudio SynopsysVCS Maven Stella Clojure CraftCMS Emacs Tags Mercury SugarCRM CMake CUDA Ensime TextMate MetaProgrammingSystem Swift CodeIgniter D Espresso TortoiseGit Nanoc Symfony CommonLisp Dart FlexBuilder Vagrant Nim SymphonyCMS Bazel Delphi GPG Vim Node Terraform InforCMS DM Images VirtualEnv Objective-C TeX Kentico Drupal JDeveloper Virtuoso OCaml Textpattern Phoenix Eagle JEnv VisualStudioCode Opa TurboGears2 AtmelStudio Elisp JetBrains WebMethods OpenCart Typo3 IAR_EWARM Elixir Kate Windows OracleForms Umbraco Exercism Elm KDevelop4 Xcode Packer Unity Hugo EPiServer Lazarus XilinxISE Perl UnrealEngine JBoss4 Erlang LibreOffice Go Perl6 VisualStudio JBoss6 ExpressionEngine Linux Godot Phalcon VVVV Cordova ExtJs LyX Gradle PlayFramework Waf Meteor Fancy macOS Grails Plone WordPress Nuxt Finale MATLAB GWT Prestashop Xojo NWjs ForceDotCom Mercurial Haskell Processing Yeoman Vue Fortran MicrosoftOffice Idris PureScript Yii Snap FuelPHP ModelSim IGORPro Python ZendFramework Logtalk Gcov Momentics Java Qooxdoo Zephir Bitrix GitBook MonoDevelop JBoss Qt CodeSniffer Anjuta NetBeans Jekyll R Drupal7 Ansible Ninja JENKINS_HOME Rails Magento1 Archives NotepadPP Joomla RhodesRhomobile

giboはプログラミング言語はもちろんのこと、フレームワークやソフトウェアにも多数対応しています。GitHubが生成してくれる.gitignoreはプログラミング言語向けですが、giboと組み合わせることでより強力な指定ができそうです。

giboはShellスクリプト製のオープンソース・ソフトウェア（Public Domain）です。

simonwhitaker/gibo: Easy access to gitignore boilerplates

[ivanpierre]

RT @ioa_27: Calling all lispers of all dialects! Tomorrow is the first of the new series online-lisp-meets, organised by Michał "phoe" Herda. Join us at 18:00 CEST. Info: https://t.co/SWaTZqPIj2 #lisp #scheme #racket #commonlisp #clojure #elisp #dylan #picolisp #acl2 and all the lisps! 🥰

Calling all lispers of all dialects! Tomorrow is the first of the new series online-lisp-meets, organised by Michał "phoe" Herda. Join us at 18:00 CEST. Info: https://t.co/SWaTZqPIj2#lisp #scheme #racket #commonlisp #clojure #elisp #dylan #picolisp #acl2 and all the lisps! 🥰

— Ioanna M. Dimitriou H. (@ioa_27) May 11, 2020

from Twitter https://twitter.com/ivanpierre May 11, 2020 at 10:31PM via IFTTT

[dailyumwelt]

ironing out painpoints in the cffi layer

[zblisp]

Lisp stuff on YouTube

If you want to see some neat videos, subscribe to dto, Baggers, and WarWeasle on YouTube. They all regularly post neat graphical stuff done in Common Lisp.

If you know any more people I should follow on YouTube, let me know.

[phoe-krk]

LispFurcProxy in action.

Freshly finished. Still warm.

[kaygun]

Prüfer Encoding/Decoding of a Tree in Common Lisp

Description of the problem:

Given a tree, or a simple graph, the standard way of describing it is giving the set of vertices and edges. However, there are myriad different ways of encoding a tree. Pruefer encoding is one of them. Today, I am going to write two functions: one to write the Prüfer code of a given tree as a list of edges, and another to write a list of edges from a Prüfer code.

The algorithm

The encoding algorithm is pretty simple:

Function Encode: Input: A tree T as a list of edges Output: An ordered list rs of vertices with repetitions Begin Let rs be the empty list While T contains two or more vertices do Find the leaf x (vertex of degree 1) in T with the minimal label Let y be the other end of the edge connected to x Remove x and the edge xy connected to x from T Append y to rs End Return rs End

Let me show how this works over an example: Let T be the tree

0 -- 1 -- 2 -- 3 -- 4 | | 5 6

In the first pass we pick 0 but add 1 to the Prüfer code, and we remove the edge 01. In the second pass, 4 is the smallest label and we add 3 to the code before we remove 43. Next is 5, we add 1 again and remove 15. Next is 1, we add 2 to the code and remove the edge 12. Next is 2, we add 3 to the code and remove the edge 23. And then we stop since we only have two vertices 3 and 6. The Prüfer code for the tree above is 13123.

The decoding algorithm is a little more complex

Function Decode: Input: An ordered list rs of vertices with repetitions Output: A tree T as a list of edges Begin Let n be length(rs) Do Let x be the first element of the list rs Let y be the vertex with the minimal label that does not appear in rs Add the edge xy to T Remove x from rs Append y to the end of rs Until T contains n edges Let x and y be the only vertices not in rs Add xy to T Return T End

Let us decode the code we obtained above: The code was 13123 and n is set to 5. In the first pass x is 1, and y is 0. So, we add the edge 01 to T. The code is now 31230. In the next pass x is 3, y is 4. We add 34 to T and the code becomes 12304. Next, we get x is 1, y is 5 and we add 15 to T while the code is updated to 23045. Then x is 2, y is 1, the code becomes 30451 and we add 12 to T. In the final pass x is 3, y is 2 and we add 23 to T while the code becomes 04512. The only two vertices that are not in the code are 3 and 6. So T is given by the list of edges: 01, 34, 15, 12, 23, 36.

An implementation in common lisp

Before we write the code for the encoding part, I am going to need few utility functions for graph related calculations. I got hooked on to the following macro from clojure:

(defmacro ->> (x &rest forms) (dolist (f forms x) (if (listp f) (setf x (append f (list x))) (setf x (list f x)))))

->>

The macro makes the code below more readable. Next,

(defun neighbors (G x) "Returns the set of neighbors of a vertex x in G." (remove x (->> G (remove-if-not (lambda (ys) (member x ys))) (reduce (lambda (us vs) (append us (remove x vs))))))) (defun degree (G x) "Returns the degree of a vertex x in G." (length (neighbors G x))) (defun vertices (G) "Returns the set of vertices of a graph G." (remove-duplicates (reduce #'append G))) (defun delete-vertex (G x) "Deletes a vertex x all edges adjacent to x from G." (remove-if (lambda (edge) (member x edge)) G))

NEIGHBORS DEGREE VERTICES DELETE-VERTEX

Now that we are done with generic graph operations, let us move on to the specific function we need. First is for finding the leaf with minimal label.

(defun min-leaf (G) "Find the leaf in G with the minimal label." (->> (vertices G) (remove-if-not (lambda (y) (= 1 (degree G y)))) (reduce #'min)))

MIN-LEAF

Now, we can implement the encoding function as follows:

(defun prufer-encode (G &optional xs) "Returns the Prüfer encoding of a tree given as a list of edges." (if (= 1 (length G)) (nreverse xs) (let* ((x (min-leaf G)) (y (car (neighbors G x)))) (prufer-encode (delete-vertex G x) (cons y xs)))))

PRUFER-ENCODE

Let us test:

(prufer-encode '((0 1) (1 2) (2 3) (3 4) (1 5) (3 6)))

(1 3 1 2 3)

The decode function strangely is more straightforward to implement:

(defun prufer-decode (xs) "Returns the tree as a list of edges from a given Prüfer code." (let* ((n (+ 2 (length xs))) (ys (loop for i from 0 below n collect i))) (labels ((helper (code k G) (let ((zs (sort (set-difference ys (remove-duplicates code)) #'<))) (if (= k 2) (append G (list zs)) (helper (append (cdr code) (list (car zs))) (1- k) (append G (list (list (car code) (car zs))))))))) (helper xs n nil))))

PRUFER-DECODE

And we test it:

(prufer-decode '(1 3 1 2 3))

((1 0) (3 4) (1 5) (2 1) (3 2) (3 6))

Now, let me test the algorithm on a larger random tree:

(defun random-tree (n) (loop for i from 1 below n collect (list (random i) i))) (defun straighten (G) (mapcar (lambda (xs) (sort xs #'<)) G))

RANDOM-TREE STRAIGHTEN

OK. I am going to test the algorithm on a random tree on 50 vertices: The code below should return nil:

(defvar G (straighten (random-tree 50))) (set-difference G (straighten (prufer-decode (prufer-encode G))) :test #'equal)

G NIL

[meseta035]

Common Lisp独習の環境構築

書籍

実践Common Lisp

原題のPractical（実践）をそのまま訳したのが悪かった。この本のタイトルが「入門Common Lisp」でなかった為に僕は怖気づいて読むことが出来なかった事をことに後悔しております。 Google Booksでは、無料でページの半分くらいが歯抜けながらも読める。オンラインで読み、気に入れば書籍購入を。入門書、最初の一冊としては最高。原著者と訳者に感謝。

実行環境、IDE

Lispbox

いちから環境を構築しようとして、慣れないEmacsに挫折するぐらいなら多少バージョンは古くてもすぐ動く設定でEmacs + SLIME + Clozure CL が入っているパッケージから始めよう。Windows環境では多分いちばん簡単にCommon Lisp開発環境が手に入る筈。Macはバージョンが古いEmacsが最初から入っているけど、まず動かさなければ始まらない。

Emacsについては、僕は'90年代後半にASCII刊「入門Mule」を読んで、Linuxで動かして多分コピー＆ペーストぐらいの操作で「やってられるか」となり疎遠になったのだけど、GUI環境で動くEmacsを使ってその辺りはごまかし、またはcommand-x,c,vが使えるMac環境なら、あえてEmacsの「正式の作法」を覚えなくてもいいんじゃないか。この辺、Controlキーを多用するWindowsは、同じくControlキー多用文化のUNIX��キーバインディングが被ってしまい、損です。

Emacsから M-x slime でSLIMEなるLisp IDEを起動したら、プロンプトから適当に足し算でもすれば動作確認完了。

CL-USER> (+ 1 2) ;=>3

Clozure CL.app

Emacsの操作に躓いてしまうと、肝心のCommon Lisp入門前に挫折してしまう事態になりかねません。Mac OS Xユーザー限定ですが、GUIから操作できるClozure CLを使って入門するのも賢い方法です。 僕は実際に触ったことがありませんが、商用Common Lisp処理系もおおむねローカルOSのGUI環境に対応しているようで、Emacsが分からなければLispを語るな、という感じではない。

[hiyosi]

Common Lispでオブジェクト指向プログラミング

Common LispにはCLOS(Common Lisp Object System)がある。 今回はCommon Lispでオブジェクト指向プログラミングの方法を整理します。わかりやすいようにRubyでの例も書いてみます。

クラス定義

Common Lispにおけるクラス定義はDEFCLASSマクロを使って定義します。

(defclass name (direct-superclass-name*) (slot-specifier*))

変数の定義はスロット指定子を使って定義します。(slot-specifier*) 実際に定義してみるとこんな感じ。

Common Lisp

(defclass city () (id name country-code district population))

Ruby

class City attr_accessor :id, :name, :coutry_code, :district, :population @id @name @country_code @district @population end

これでid, name, country-code, district, population のスロットを持つ、cityクラスが定義できた。 クラスは定義できたので、インスタンス化してみたいと思います。

Common Lisp

(make-instance 'city) (defparameter *city* (make-instance 'city))

Ruby

City.new city = City.new

これでクラスの定義と定義したクラスをインスタンス化できた。 インスタンス化したオブジェクトのスロットに値を入れるには

Common Lisp

(setf (slot-value *city* 'id) 1) (setf (slot-value *city* 'name) "Tokyo") (setf (slot-value *city* 'country-code) "JPN") (setf (slot-value *city* 'district) "Tokyo-to") (setf (slot-value *city* 'population) 7980230)

Ruby

city.id = 1 city.name = 'Tokyo' city.country-code = 'JPN' city.district = 'Tokyo-to' city.population = 7980230

とこんな感じになるんですが、Common Lispのほうはちょっと長くて面倒だし、直接スロットにアクセスしちゃってるじゃんと思われたかもしれません。

ここでちょっとClass定義に話を戻すと、Ruby側ではインスタンス変数へのアクセスに対してアクセサを定義しないと値を入れられなかったので、アクセサを定義していました。 実はCommon Lispにもアクセサがあります。先程のクラス定義をアクセサ関数を使って書き直してみます。

(defclass city () ((id :accessor id) (name :accessor name) (country-code :accessor country-code) (district :accessor district) (population :accessor population)))

そうすると、スロットに値を入れるのは以下のようになります。ずいぶんすっきりしたと思います。

(setf (id *city*) 1) (setf (name *city*) "Tokyo") (setf (country-code *city*) "JPN") (setf (district *city*) "Tokyo-to") (setf (population *city*) 7980230)

これは以下のような対比になります。 (メソッド名 オブジェクト名) となっているんですね。

(id *city) ; Common Lisp city.id # ruby

また、Rubyでいうinitialize、Javaでのコンストラクタを使って初期値を指定したい場合はどうなるかというと、:initarg を付けてやればよいです。

(defclass city () ((id :initarg :id :accessor id) (name :initarg :name :accessor name) (country-code :initarg :country-code :accessor country-code) (district :initarg :district :accessor district) (population :initarg :population :accessor population)))

:initargで スロットの初期値を指定するときに使う引数マークシンボルを指定してあります。実際にインスタンス生成の際に初期値を与えてみると

(defparameter *city* (make-instance 'city :id 1 :name "Tokyo" :country-code "JPN" :district "Tokyo-to" :population 7980230))

こうなります。さらにはデフォルト値を指定するときはこうなります。

Ruby

def initialize(id = 0, name = "none", country_code = "none" distcirt = "none" population = 0) @id = id @name = name @coutry_code = coutry_code @district = district @population = population end

Comon Lisp

(defclass city () ((id :initarg :id :initform 0 :accessor id) (name :initarg :name :initform "none" :accessor name) (country-code :initarg :country-code :initform "none" :accessor country-code) (district :initarg :district :initform "none" :accessor district) (population :initarg :population :initform 0 :accessor population)))

メソッド定義

次はCommon Lispでのメソッド定義について整理していきます。 こちらでは以下のように書いてありました。

メソッドは特定のクラス（データ型）と結びついた関数です。 メソッドの特徴は、同じ名前のメソッドをいくつも定義することができ、引数のデータ型によって、その中から実際に呼び出すメソッドを自動的に選択することです。 該当するメソッドが見つからない場合はエラーとなります。CLOS では同一名のメソッドの集まりを「総称関数 (generic function) 」と呼びます。この総称関数がＣ++や Java などのオブジェクト指向とはちょっと違う CLOS の特徴です。

Common Lispではメソッドをクラスの中に定義しません。総称関数に定義して呼び出された時に引数の型によって、 総称関数から適切なメソッドが選択されることになります。 総称関数 defgeneric を明示的に実行していない場合は、暗黙のうちに総称関数が定義されるとのこと。

まずメソッド定義関数は以下です。

(defmethod メソッド名 ((仮引数名 データ型) or 引数 ... ) Ｓ式 ...

ここからメソッドの説明を簡単に書いていきたいのですが、いい説明が見つからない。 ちょっとややこしくなるかもしれませんが、前述のcityクラスはMySQLのサンプルDBであるworldを元に定義していますので、cityをモデルクラスと見做して、DBから値を取得する行為をメソッドにしてみたいと思います。 (dbiのあたりのコードも含めて最後にまとめて掲載します。)

(defmethod get-city-by-id ((c city) id) (let* ((query (dbi:prepare *db-connection* (concatenate 'string "SELECT * FROM CITY WHERE ID = '" id "'"))) (result (dbi:execute query)) (raw (dbi:fetch result))) (dbi:disconnect *db-connection*) (set-city-slot c raw))) (defun set-city-slot (city raw) (setf (id city) (getf raw :ID)) (setf (name city) (getf raw :|Name|)) (setf (country-code city) (getf raw :|CountryCode|)) (setf (district city) (getf raw :|District|)) (setf (population city) (getf raw :|Population|)) city)

上のようにメソッドを定義しましたので、呼び出してみたいと思います。

CL-USER> (defparameter city-500 (get-city-by-id (make-instance 'city) "500")) CITY-500 CL-USER> (format t "~a ~a ~a ~a ~a" (id city-500) (name city-500) (country-code city-500) (district city-500) (population city-500)) 301 Embu BRA São Paulo 222223

ちゃんと動いているみたいです。 とまあ、こんな感じで、後はメソッド結合とか総称関数とか書きたかったんですけ、時間切れなので一旦この辺で。 たぶん次回に書くと思います。

最後の今回書いたコードを貼り付けておきます。

[wickedsource-blog]

Let's play evolution in my imaginary console world! 

[ubikation]

How I Learned to Stop Worrying and Love ABCL Interop with Akka

So this blog is kind of my way of posting about what I'm thinking about and working on so that I'll actually complete it.

Right now I'm really interested in Akka. I don't really pay that much attention to the Scala world outside of checking Typesafe announcements every now and then... but Akka really stands out.

What is Akka?

Akka is a message passing system that scales over cores and in a distributed manner. Basically... it brings async data manipulation to a whole new level, and makes it something anybody on the JVM can use.

---

What do I want to do with Akka?

I want to create decent bindings to Akka for ABCL.

This shouldn't be that difficult... as in I don't think there are any real unknowns here. There is another actor library called Common-Lisp-Actors by Naveen Sundar G. at https://github.com/naveensundarg/Common-Lisp-Actors as well as the basic API for Akka, so I should be able to cobble something together given enough time.I'm still trying to wrap my head around stuff... but I think I'd like to try and see how to integrate the distributed factor of Akka if I get a chance.

---

Where am I stuck? Right now I am stuck trying to recreate the Hello World Akka Java demo... but I think I'm almost there. Time will tell of course!

After that I would like to create a simple benchmark as well. You can't control what you don't measure, right?