Lisplog

Blogging in Lisp

Search

Feed Aggregator Page 668

Rendered on Wed, 21 Jul 2021 18:59:21 GMT  newer latest older 

Micha Herda: Current Common Lisp IRC situation

via Planet Lisp by on Tue, 01 Jun 2021 12:19:21 GMT

Because of the upheaval at Freenode, I've migrated to Libera Chat along with a bunch of other Lisp programmers. We have used that as a chance to make some small changes to the channel structure:

  • #commonlisp is the on-topic Common Lisp channel (formerly #lisp),
  • #lisp is the somewhat on-topic discussion about all Lisp dialects (formerly ##lisp),
  • the rest of the channel names should work the same.

The first two lines of the above were mentioned because #lisp on Freenode used to have a non-trivial volume of people asking questions about Scheme or Emacs Lisp due to the too-generic channel name. Naming the Common Lisp channel #commonlisp resolves this issue, at the cost of sacrificing a lucrative and attractive five-character channel name.

Quicklisp news: May 2021 Quicklisp dist update now available

via Planet Lisp by on Mon, 31 May 2021 18:12:00 GMT

 New projects: 

  • adopt-subcommands — Extend the Adopt command line processing library to handle nested subcommands. — MIT
  • cl-cerf — Lisp wrapper to libcerf — Public Domain
  • cl-cxx-jit — Common Lisp Cxx Interoperation — MIT
  • cl-form-types — Library for determining types of Common Lisp forms. — MIT
  • cl-incognia — Incognia API Common Lisp Client — MIT
  • cl-info — A helper to an answer a question about OS, Lisp and Everything. — BSD
  • cl-mimeparse — Library for parsing MIME types, in the spirit of http://code.google.com/p/mimeparse/, with a Common Lisp flavor. — MIT
  • cl-opencl — CFFI for OpenCL and Lisp wrapper API — Public Domain
  • cl-schedule — cl-schedule is a cron-like scheduling library in common-lisp. It subsumes and replaces traditional cron managers thanks to richer expressiveness of Lisp. — MIT
  • cl-vorbis — Bindings to stb_vorbis, a simple and free OGG/Vorbis decoding library — zlib
  • claw-olm — Thin wrapper over OLM — MIT
  • context-lite — A CLOS extension to support specializing methods on special/dynamic variables. — MIT
  • defmain — A wrapper around net.didierverna.clon which makes command line arguments parsing easier. — BSD
  • defrest — defrest: expose functions as REST webservices for ajax or other stuff — BSD
  • doc — Documentation generator, based on MGL-PAX. Allows to put documentation inside lisp files and cross-reference between different entities. — MIT
  • ec2-price-finder — Quickly find the cheapest EC2 instance that you need across regions — BSD-3-Clause
  • file-notify — Access to file change and access notification. — zlib
  • fresnel — Bidirectional translation with lenses — MIT
  • log4cl-extras — A bunch of addons to LOG4CL: JSON appender, context fields, cross-finger appender, etc. — BSD
  • mnas-package — Система @b(mnas-package) предназначена для подготовки документации, извлекаемой из asdf-систем. @begin(section) @title(Мотивация) Система @b(Codex) является достаточно удобной для выполнения документирования систем, написанных с использованием @b(Common Lisp). Она позволяет получить на выходе документацию приемлемого вида. К недостатку сустемы @b(Codex) можно отнести то, что формирование шаблона документации не выполняется автоматически. Указание на включение разделов документации, относящихся к отдельным сущностям к которым можно отнести: @begin(list) @item(системы;) @item(пакеты;) @item(классы;) @item(функции, setf-функции;) @item(обобщенные функции,методы, setf-методы;) @item(макросы;) @item(и т.д., и т.п.) @end(list) приходится формировать вручную. Этот проект пытается устранить данный недостаток системы @b(Codex) за счет определения функций и методов позволяющих: @begin(list) @item(формировать код, предназначенный для передачи в систему @b(Codex);) @item(формировать представление отдельных частей системы в виде графов.) @end(list) @end(section) — GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
  • mnas-string — Система @b(mnas-string) предназначена для: @begin(list) @item(парсинга вещественного числа;) @item(разделения строки на подстроки;) @item(замены всех вхождений подстроки в строке;) @item(замены множественного вхождения паттерна единичным;) @item(подготовки строки в качестве аргумента для like запроса SQL;) @item(обрамления строки префиксом и постфиксом;) @item(вывода представления даты и времени в поток или строку;) @item(траслитерации строки.) @end(list) — GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
  • osmpbf — Library to read OpenStreetMap PBF-encoded files. — MIT
  • plot — Plots for Common Lisp — MS-PL
  • scheduler — Extensible task scheduler. — BSD-2-Clause
  • speechless — A dialogue system language implementation. — zlib
  • stumpwm-sndioctl — Interface to OpenBSD's sndioctl for StumpWM. — ISC
  • vellum — Data Frames for Common Lisp — BSD simplified
  • vellum-clim — Simplistic vellum data frames viewer made with mcclim. — BSD simplified
  • vellum-csv — CSV support for Vellum Data Frames — BSD simplified
  • vellum-postmodern — Postgres support for Vellum Data Frames (via postmodern). — BSD simplified
  • vk — Common Lisp bindings for the Vulkan API. — MIT
  • wasm-encoder — Library for serializing WebAssembly modules to binary .wasm files — MIT

Updated projects: adopt, agutil, also-alsa, anypool, april, architecture.builder-protocol, async-process, audio-tag, bdef, bnf, burgled-batteries.syntax, caveman, chirp, cl+ssl, cl-ana, cl-argparse, cl-async, cl-collider, cl-covid19, cl-cuda, cl-data-frame, cl-data-structures, cl-environments, cl-forms, cl-gamepad, cl-glfw3, cl-gserver, cl-kraken, cl-liballegro, cl-liballegro-nuklear, cl-markless, cl-mixed, cl-naive-store, cl-num-utils, cl-patterns, cl-pdf, cl-prevalence, cl-rfc4251, cl-sendgrid, cl-slice, cl-smt-lib, cl-ssh-keys, cl-steamworks, cl-str, cl-tiled, cl-typesetting, cl-utils, cl-webkit, clack, clack-pretend, clath, clavier, clog, closer-mop, cmd, coleslaw, common-lisp-jupyter, configuration.options, consfigurator, croatoan, cytoscape-clj, damn-fast-priority-queue, data-frame, dataloader, defconfig, definitions, deploy, dfio, diff-match-patch, dissect, djula, dns-client, doplus, dufy, duologue, easy-routes, eclector, erudite, file-attributes, flare, fmt, functional-trees, gendl, generic-cl, golden-utils, gute, harmony, herodotus, hu.dwim.presentation, hunchenissr, hunchensocket, hunchentoot-errors, iterate, kekule-clj, lack, language-codes, lichat-protocol, lisp-stat, literate-lisp, magicffi, maiden, math, mcclim, messagebox, mnas-graph, mnas-hash-table, multiposter, mutility, named-readtables, nibbles, nodgui, numcl, numerical-utilities, nyaml, nyxt, overlord, parseq, pathname-utils, plump-sexp, plump-tex, portable-threads, postmodern, pzmq, qlot, qt-libs, rpcq, sb-cga, sc-extensions, screamer, sel, serapeum, shadow, shop3, specialized-function, spinneret, split-sequence, static-dispatch, static-vectors, stumpwm, sxql, ten, tfeb-lisp-hax, trivial-indent, trivial-timer, trivial-with-current-source-form, trucler, uax-15, vgplot, wild-package-inferred-system, with-c-syntax.


To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Pavel Korolev: :claw honing - Beta milestone and alien-works

via Planet Lisp by on Sun, 30 May 2021 00:00:00 GMT

Long time no see my C++ autowrapping rants. But several bindings later, :claw has reached the stage where it is ready to leave a garage and see the outside world. Since my last post, some approaches were revised, though the autowrapping process is still not fully cemented yet. I wouldn't expect :claw to be out of beta for at least a year. That doesn't mean it is unusable, but rather I cannot guarantee a stable interface and a trivial procedure for setting it up.

In other big news, :alien-works system got all required foreign libraries wrapped and integrated, including some complex and peculiar C++ ones (Skia 👀). Next step is to write a game, based on :alien-works framework, to see how much lispification of autowrapped systems is possible without loosing any performance and what is required for a solid game delivery.

Joe Marshall: Stupid Y operator tricks

via Planet Lisp by on Fri, 21 May 2021 22:07:00 GMT

Here is the delta function: δ = (lambda (f) (f f)). Delta takes a function and tail calls that function on itself. What happens if we apply the delta function to itself? Since the delta function is the argument, it is tail called and applied to itself. Which leads again to itself being tail called and applied to itself. We have a situation of infinite regression: the output of (δ δ) ends up being a restatement of the output of (δ δ). Now in this case, regression is infinite and there is no base case, but imagine that somehow there were a base case, or that somehow we identified a value that an infinite regression equated to. Then each stage of the infinite regression just replicates the previous stage exactly. It is like having a perfectly silvered mirror: it just replicates the image presented to it exactly. By calling delta on delta, we've arranged our perfectly silvered mirror to reflect an image of itself. This leads to the “infinite hall of mirrors” effect.

So let's tweak the delta function so that instead of perfectly replicating the infinite regression, it applies a function g around the replication: (lambda (f) (g (f f))). If we apply this modified delta function to itself, each expansion of the infinite regression ends up wrapping an application of the g around it: (g (f f)) = (g (g (f f))) = (g (g (g (f f)))) = (g (g (g (g … )))). So our modified delta function gives us a nested infinite regression of applications of g. This is like our perfectly silvered mirror, but now the reflected image isn't mirrored exactly: we've put a frame on the mirror. When we arrange for the mirror to reflect itself, each nested reflection also has an image of the frame around the reflection, so we get a set of infinitely nested frames.

An infinite regression of (g (g (g (g … )))) is confusing. What does it mean? We can untangle this by unwrapping an application. (g (g (g (g … )))) is just a call to g. The argument to that call is weird, but we're just calling (g <something>). The result of the infinite regression (g (g (g (g … )))) is simply the result of the outermost call to g. We can use this to build a recursive function.

;; If factorial = (g (g (g (g … )))), then
;; factorial = (g factorial), where

(defun g (factorial)
  (lambda (x)
    (if (zerop x)
        1
        (* x (funcall factorial (- x 1))))))
The value returned by an inner invocation of g is the value that will be funcalled in the altenative branch of the conditional.

Y is defined thus:

Y = λg.(λf.g(f f))(λf.g(f f))

A straightforward implementation attempt would be
;; Non working y operator
(defun y (g)
  (let ((d (lambda (f) (funcall g (funcall f f)))))
    (funcall d d)))
but since lisp is a call-by-value language, it will attempt to (funcall f f) before funcalling g, and this will cause runaway recursion. We can avoid the runaway recursion by delaying the (funcall f f) with a strategically placed thunk
;; Call-by-value y operator
;; returns (g (lambda () (g (lambda () (g (lambda () … ))))))
(defun y (g)
  (let ((d (lambda (f) (funcall g (lambda () (funcall f f))))))
    (funcall d d)))
Since the recursion is now wrapped in a thunk, we have to funcall the thunk to force the recursive call. Here is an example where we see that:
* (funcall (Y (lambda (thunk)
                (lambda (x)
                  (if (zerop x)
                      1
                      (* x (funcall (funcall thunk) (- x 1)))))))
           6)
720
the (funcall thunk) invokes the thunk in order to get the actual recursive function, which we when then funcall on (- x 1).

By wrapping the self-application with a thunk, we've made the call site where we use the thunk more complicated. We can clean that up by wrapping the call to the thunk in something nicer:

* (funcall
    (y (lambda (thunk)
         (flet ((factorial (&rest args)
                  (apply (funcall thunk) args)))

           (lambda (x)
             (if (zerop x)
                 1
                 (* x (factorial (- x 1))))))))
      6)
720
And we can even go so far as to hoist that wrapper back up into the definiton of y
(defun y1 (g)
  (let ((d (lambda (f) (funcall g (lambda (&rest args) (apply (funcall f f) args))))))
    (funcall d d)))

* (funcall
    (y1 (lambda (factorial)
          (lambda (x)           
            (if (zerop x)
                1
                (* x (funcall factorial x))))))
    6)
720
y1 is an alternative formulation of the Y operator where we've η-expanded the recursive call to avoid the runaway recursion.

The η-expanded version of the applicative order Y operator has the advantage that it is convenient for defining recursive functions. The thunkified version is less convenient because you have to force the thunk before using it, but it allows you to use the Y operator to define recursive data structures as well as functions:

(Y
  (lambda (delayed-ones)
    (cons-stream 1 (delayed-ones))))
{1 …}

The argument to the thunkified Y operator is itself a procedure of one argument, the thunk. Y returns the result of calling its argument. Y should return a procedure, so the argument to Y should return a procedure. But it doesn't have to immediately return a procedure, it just has to eventually return a procedure, so we could, for example, print something before returning the procedure:

* (funcall (Y (lambda (thunk)
                (format t "~%Returning a procedure")
                (lambda (x)
                  (if (zerop x)
                      1
                      (* x (funcall (funcall thunk) (- x 1)))))))
         6)
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
720
There is one caveat. You must be able to return the procedure without attempting to make the recursive call.

Let's transform the returned function before returning it by applying an arbitrary function h to it:

(Y (lambda (thunk)
     (h (lambda (x)
          (if (zerop x)
              1
              … )))))
Ok, so now when we (funcall thunk) we don't get what we want, we've got an invocation of h around it. If we have an inverse to h, h-1, available, we can undo it:
(y (lambda (thunk)
      (h (lambda (x)
           (if (zerop x)
               1
               (* (funcall (h-1 (funcall thunk)) (- x 1))))))))
As a concrete example, we return a list and at the call site we extract the first element of that list before calling it:
* (funcall (car (y (lambda (thunk)
                     (list (lambda (x)
                             (if (zerop x)
                                 1
                                 (* x (funcall (car (funcall thunk)) (- x 1))))))))
           6)
720
So we can return a list of mutually recursive functions:
(y (lambda (thunk)
    (list
      ;; even?
      (lambda (n)
        (or (zerop n)
            (funcall (cadr (funcall thunk)) (- n 1))))

      ;; odd?
      (lambda (n)
        (and (not (zerop n))
             (funcall (car (funcall thunk)) (- n 1))))
      )))
If we use the η-expanded version of the Y operator, then we can adapt it to expect a list of mutually recursive functions on the recursive call:
(defun y* (&rest g-list)
  (let ((d (lambda (f)
             (map 'list (lambda (g)
                          (lambda (&rest args)
                            (apply (apply g (funcall f f)) args)))
                  g-list))))
     (funcall d d)))
which we could use like this:
* (let ((eo (y* (lambda (even? odd?)
                  (declare (ignore even?))
                  (lambda (n)
                    (or (zerop n)
                        (funcall odd? (- n 1)))))

                (lambda (even? odd?)
                  (declare (ignore odd?))
                  (lambda (n)
                    (and (not (zerop n))
                         (funcall even? (- n 1))))))))
     (let ((even? (car eo))
           (odd?  (cadr eo)))
       (do ((i 0 (+ i 1)))
           ((>= i 5))
         (format t "~%~d, ~s ~s"
                 i
                 (funcall even? i)
                 (funcall odd? i)))))))
                 
0, T NIL
1, NIL T
2, T NIL
3, NIL T
4, T NIL
Instead of returning a list of mutually recursive functions, we could return them as multiple values. We just have to be expecting multiple values at the call site:
(defun y* (&rest gs)
  (let ((d (lambda (f)
             (apply #'values
                    (map 'list
                         (lambda (g)
                           (lambda (&rest args)
                             (apply (multiple-value-call g (funcall f f)) args)))
                         gs)))))
    (funcall d d)))

MIT Scheme used to have a construct called a named lambda. A named lambda has an extra first argument that is automatically filled in with the function itself. So during evaluation of the body of a named lambda, the name is bound to the named lambda, enabling the function to call itself recursively:

(defmacro named-lambda ((name &rest args) &body body)
  `(y1 (lambda (,name)
         (lambda ,args
           ,@body))))

* (funcall (named-lambda (factorial x)
            (if (zerop x)
                1
                (* x (funcall factorial (- x 1)))))
         6)
720
This leads us to named let expressions. In a named let, the implicit lambda that performs the let bindings is a named lambda. Using that name to invoke the lambda on a different set of arguments is like recursively re-doing the let.
* (named-let fact ((x 6)) (if (zerop x) 1 (* x (funcall fact (- x 1)))))

720

In Scheme, you use letrec to define recursive or mutually recursive procedures. Internal definitions expand into an appropriate letrec. letrec achieves the necessary circularity not through the Y operator, but through side effects. It is hard to tell the difference, but there is a difference. Using the Y operator would allow you to have recursion, but avoid the implicit side effects in a letrec.

Oleg Kiselyov has more to say about the Y operator at http://okmij.org/ftp/Computation/fixed-point-combinators.html

Joe Marshall: β-conversion

via Planet Lisp by on Sat, 15 May 2021 17:51:00 GMT

If you have an expression that is an application, and the operator of the application is a lambda expression, then you can β-reduce the application by substituting the arguments of the application for the bound variables of the lambda within the body of the lambda.

(defun beta (expression if-reduced if-not-reduced)
  (if (application? expression)
      (let ((operator (application-operator expression))
            (operands (application-operands expression)))
        (if (lambda? operator)
            (let ((bound-variables (lambda-bound-variables operator))
                  (body (lambda-body operator)))
              (if (same-length? bound-variables operands)
                  (funcall if-reduced
                           (xsubst body
                                   (table/extend* (table/empty)
                                                  bound-variables
                                                  operands)))
                  (funcall if-not-reduced)))
            (funcall if-not-reduced)))
      (funcall if-not-reduced)))

* (beta '((lambda (x y) (lambda (z) (* x y z))) a (+ z 3))
        #'identity (constantly nil))
(LAMBDA (#:Z460) (* A (+ Z 3) #:Z460))

A large, complex expression may or may not have subexpressions that can be β-reduced. If neither an expression or any of its subexpressions can be β-reduced, then we say the expression is in “β-normal form”. We may be able to reduce an expression to β-normal form by β-reducing where possible. A β-reduction can introduce further reducible expressions if we substitute a lambda expression for a symbol in operator position, so reducing to β-normal form is an iterative process where we continue to reduce any reducible expressions that arise from substitution.

(defun beta-normalize-step (expression)
  (expression-dispatch expression

    ;; case application
    (lambda (subexpressions)
      ;; Normal order reduction
      ;; First, try to beta reduce the outermost application,
      ;; otherwise, recursively descend the subexpressions, working
      ;; from left to right.
      (beta expression
            #'identity
            (lambda ()
              (labels ((l (subexpressions)
                         (if (null subexpressions)
                             '()
                             (let ((new-sub (beta-normalize-step (car subexpressions))))
                               (if (eq new-sub (car subexpressions))
                                   (let ((new-tail (l (cdr subexpressions))))
                                     (if (eq new-tail (cdr subexpressions))
                                         subexpressions
                                         (cons (car subexpressions) new-tail)))
                                   (cons new-sub (cdr subexpressions)))))))
                (let ((new-subexpressions (l subexpressions)))
                  (if (eq new-subexpressions subexpressions)
                      expression
                      (make-application new-subexpressions)))))))

    ;; case lambda
    (lambda (bound-variables body)
      (let ((new-body (beta-normalize-step body)))
        (if (eql new-body body)
            expression
            (make-lambda bound-variables new-body))))

    ;; case symbol
    (constantly expression)))

;;; A normalized expression is a fixed point of the
;;; beta-normalize-step function.
(defun beta-normalize (expression)
  (do ((expression expression (beta-normalize-step expression))
       (expression1 '() expression)
       (count 0 (+ count 1)))
      ((eq expression expression1)
       (format t "~%~d beta reductions" (- count 1))
       expression)))

You can compute just by using β-reduction. Here we construct an expression that reduces to the factorial of 3. We only have β-reduction, so we have to encode numbers with Church encoding.

(defun test-form ()
  (let ((table
         (table/extend*
          (table/empty)
          '(one
            three
            *
            pred
            zero?
            y)
          '(
            ;; Church numeral one
            (lambda (f) (lambda (x) (f x)))

            ;; Church numeral three 
            (lambda (f) (lambda (x) (f (f (f x)))))

            ;; * (multiply Church numerals)
            (lambda (m n)
              (lambda (f)
                (m (n f))))

            ;; pred (subtract 1 from Church numeral)
            (lambda (n)
              (lambda (f)
                (lambda (x) (((n (lambda (g)
                                   (lambda (h)
                                     (h (g f)))))
                              (lambda (u) x))
                             (lambda (u) u)))))

            ;; zero? (test if Church numeral is zero)
            (lambda (n t f) ((n (lambda (x) f)) t))

            ;; Y operator for recursion
            (lambda (f)
              ((lambda (x) (f (x x)))
               (lambda (x) (f (x x)))))

            )))
        (expr
         '((lambda (factorial)
             (factorial three))
           (y (lambda (fact)
                (lambda (x)
                  (zero? x
                   one
                   (* (fact (pred x)) x))))))))
    (xsubst expr table)))

* (test-form)

((LAMBDA (FACTORIAL) (FACTORIAL (LAMBDA (F) (LAMBDA (X) (F (F (F X)))))))
 ((LAMBDA (F) ((LAMBDA (X) (F (X X))) (LAMBDA (X) (F (X X)))))
  (LAMBDA (FACT)
    (LAMBDA (X)
      ((LAMBDA (N T F) ((N (LAMBDA (X) F)) T)) X
       (LAMBDA (F) (LAMBDA (X) (F X)))
       ((LAMBDA (M N) (LAMBDA (F) (M (N F))))
        (FACT
         ((LAMBDA (N)
            (LAMBDA (F)
              (LAMBDA (X)
                (((N (LAMBDA (G) (LAMBDA (H) (H (G F))))) (LAMBDA (U) X))
                 (LAMBDA (U) U)))))
          X))
        X))))))

* (beta-normalize (test-form))

127 beta reductions
(LAMBDA (F) (LAMBDA (X) (F (F (F (F (F (F X))))))))

This is the Church numeral for 6.

I find it pretty amazing that we can bootstrap ourselves up to arithmetic just by repeatedly β-reducing where we can. It doesn't seem like we're actually doing any work. We're just replacing names with what they stand for.

The β-substitution above replaces all the bound variables with their arguments if there is the correct number of arguments. One could easily implement a partial β-substitution that replaced only some of the bound variables. You'd still have an application, but some of the bound variables in the lambda would be eliminated and the corresponding argument would be removed.

"Programming Algorithms in Lisp" Is Out!

via Lisp, the Universe and Everything by Vsevolod Dyomkin on Mon, 08 Feb 2021 10:48:00 GMT

The updated version of my book "Programming Algorithms" has been released by Apress recently. It has undergone a number of changes that I want to elaborate on in this post.

But first, I'd like to thank all the people who contributed to the book or supported my work on it in other ways. It was an honor for me to be invited to Apress as "Practical Common Lisp" published by them a decade ago was my one-way ticket to the wonderful world of Lisp. Writing "Programming Algorithms" was, in a way, an attempt to give something back. Also, I was very curious to see how the cooperation with the publisher would go. And I can say that they have done a very professional job and helped significantly improve the book through the review process. That 5-10% change that is contributed by the editors, although it may seem insignificant, is very important to bring any book to the high standard that allows not to annoy many people. Unfortunately, I am not a person who can produce a flawless result at once, so helping with correcting those flaws is very valuable. Part of gratitude for that also, surely, goes to many of the readers who have sent their suggestions.

I was very pleased that Michał "phoe" Herda has agreed to become the technical reviewer. He has found a number of bugs and suggested lots of improvements, of which I could implement, maybe, just a third. Perhaps, the rest will go into the second edition :)

Now, let's speak about some of those additions to Programming Algorithms in Lisp.

Curious Fixes

First of all, all the executable code from the book was published in a github repo (and also republished to the oficial Apress repo). As suggested by Michał, I have added automated tests to ensure (for now, partially, but we plan to make the test suite all-encompassing) that everything compiles and runs correctly. Needless to say that some typos and other issues were found in the process. Especially, connected with handling different corner cases. So, if you have trouble running some code from the book, you can use the github version. Funny enough, I got into a similar situation recently, when I tried to utilize the dynamic programming example in writing a small tool for aligning outputs of different ASR systems and found a bug in it. The bug was is in the matrix initialization code:


-    (dotimes (k (1+ (length s1))) (setf (aref ld k 0) 0))
-    (dotimes (k (1+ (length s2))) (setf (aref ld 0 k) 0)))
+    (dotimes (k (1+ (length s1))) (setf (aref ld k 0) k))
+    (dotimes (k (1+ (length s2))) (setf (aref ld 0 k) k)))

Another important fix that originated from the review process touched not only the book but also the implementation of the slice function in RUTILS! It turned out that I was naively assuming that displaced arrays will automatically recursively point into the original array, and thus, inadvertently, created a possibility for O(n) slice performance instead of O(1). It explains the strange performance of array sorting algorithms at the end of Chapter 5. After fixing slice, the measurements started to perfectly resemble the theoretical expectations! And, also the performance has improved an order of magnitude :D


CL-USER> (let ((vec (random-vec 10000)))
           (print-sort-timings "Insertion " 'insertion-sort vec)
           (print-sort-timings "Quick" 'quicksort vec)
           (print-sort-timings "Prod" 'prod-sort vec))
= Insertion sort of random vector (length=10000) =
Evaluation took:
  0.632 seconds of real time
...
= Insertion sort of sorted vector (length=10000) =
Evaluation took:
  0.000 seconds of real time
...
= Insertion sort of reverse sorted vector (length=10000) =
Evaluation took:
  1.300 seconds of real time
...
= Quicksort of random vector (length=10000) =
Evaluation took:
  0.039 seconds of real time
...
= Quicksort of sorted vector (length=10000) =
Evaluation took:
  1.328 seconds of real time
...
= Quicksort of reverse sorted vector (length=10000) =
Evaluation took:
  1.128 seconds of real time
...
= Prodsort of random vector (length=10000) =
Evaluation took:
  0.011 seconds of real time
...
= Prodsort of sorted vector (length=10000) =
Evaluation took:
  0.011 seconds of real time
...
= Prodsort of reverse sorted vector (length=10000) =
Evaluation took:
  0.021 seconds of real time
...

Also, there were some missing or excess closing parens in a few code blocks. This, probably, resulted from incorrectly copying the code from the REPL after finishing experimenting with it. :)

New Additions

I have also added more code to complete the full picture, so to say, in several parts where it was lacking, from the reviewers' point of view. Most new additions went into expanding "In Action" sections where it was possible. Still, unfortunately, some parts remain on the level of general explanation of the solution as it was not possible to include whole libraries of code into the book. You can see a couple of snippets below:

Binary Search in Action: a Fast Specialized In-Memory DB

We can outline the operation of such a datastore with the following key structures and functions.

A dictionary *dict* will be used to map words to numeric codes. (We'll discuss hash-tables that are employed for such dictionaries several chapters later. For now, it will be sufficient to say that we can get the index of a word in our dictionary with (rtl:? *dict* word)). The number of entries in the dictionary will be around 1 million.

All the ngrams will be stored alphabetically sorted in 2-gigabyte files with the following naming scheme: ngram-rank-i.bin. rank is the ngram word count (we were specifically using ngrams of ranks from 1 to 5) and i is the sequence number of the file. The contents of the files will constitute the alternating ngram indices and their frequencies. The index for each ngram will be a vector of 32-bit integers with the length equal to the rank of an ngram. Each element of this vector will represent the index of the word in *dict*. The frequency will also be a 32-bit integer.

All these files will be read into memory. As the structure of the file is regular — each ngram corresponds to a block of (1+ rank) 32-bit integers — it can be treated as a large vector.

For each file, we know the codes of the first and last ngrams. Based on this, the top-level index will be created to facilitate efficiently locating the file that contains a particular ngram.

Next, binary search will be performed directly on the contents of the selected file. The only difference with regular binary search is that the comparisons need to be performed rank times: for each 32-bit code.

A simplified version of the main function get-freq intended to retrieve the ngram frequency for ranks 2-5 will look something like this:


(defun get-freq (ngram)
  (rt:with ((rank (length ngram))
            (codes (ngram-codes ngram))
            (vec index found?
                 (bin-search codes
                             (ngrams-vec rank codes)
                             :less 'codes<
                             :test 'ngram=)))
     (if found?
         (aref vec rank)
         0)))

where


(defun ngram-codes (ngram)
  (map-vec (lambda (word) (rtl:? *dict* word))
           ngram))

(defun ngrams-vec (rank codes)
  (loop :for ((codes1 codes2) ngrams-vec) :across *ngrams-index*
        :when (and (<= (aref codes1 0) (aref codes 0))
                   (codes< codes codes2 :when= t))
        :do (return ngrams-vec)))
             
(defun codes< (codes1 codes2 &key when=)
  (dotimes (i (length codes1)
              ;; this will be returned when all
              ;; corresponding elements of codes are equal
              when=)
    (cond ((< (aref codes1 i)
              (aref codes2 i))
           (return t))
          ((> (aref codes1 i)
              (aref codes2 i))
           (return nil)))))

(defun ngram= (block1 block2)
  (let ((rank (1- (length block1))))
    (every '= (rtl:slice block1 0 rank)
              (rtl:slice block2 0 rank)))

We assume that the *ngrams-index* array containing a pair of pairs of codes for the first and last ngram in the file and the ngrams data from the file itself was already initialized. This array should be sorted by the codes of the first ngram in the pair. A significant drawback of the original version of this program was that it took quite some time to read all the files (tens of gigabytes) from disk. During this operation, which measured in several dozens of minutes, the application was not responsive. This created a serious bottleneck in the system as a whole and complicated updates, as well as put normal operation at additional risk. The solution we utilized to counteract this issue was a common one for such cases: switching to lazy loading using the Unix mmap facility. With this approach, the bounding ngram codes for each file should be precalculated and stored as metadata, to initialize the *ngrams-index* before loading the data itself.

Pagerank MapReduce Explanation


;; this function will be executed by mapper workers
(defun pr1 (node n p &key (d 0.85))
  (let ((pr (make-arrray n :initial-element 0))
        (m (hash-table-count (node-children node))))
    (rtl:dokv (j child (node-children node))
      (setf (aref pr j) (* d (/ p m))))
    pr))

(defun pagerank-mr (g &key (d 0.85) (repeat 100))
  (rtl:with ((n (length (nodes g)))
             (pr (make-arrray n :initial-element (/ 1 n))))
    (loop :repeat repeat :do
      (setf pr (map 'vector (lambda (x)
                              (- 1 (/ d n)))
                    (reduce 'vec+ (map 'vector (lambda (node p)
                                                 (pr1 node n p :d d))
                                       (nodes g)
                                       pr)))))
    pr))

Here, we have used the standard Lisp map and reduce functions, but a map-reduce framework will provide replacement functions which, behind-the-scenes, will orchestrate parallel execution of the provided code. We will talk a bit more about map-reduce and see such a framework in the last chapter of this book.

One more thing to note is that the latter approach differs from the original version in that each mapper operates independently on an isolated version of the pr vector, and thus the execution of Pagerank on the subsequent nodes during a single iteration will see an older input value p. However, since the algorithm is stochastic and the order of calculations is not deterministic, this is acceptable: it may impact only the speed of convergence (and hence the number of iterations needed) but not the final result.

Other Significant Changes

My decision to heavily rely on syntactic utilities from my RUTILS library was a controversial one, from the start. And, surely, I understood it. But my motivation, in this regard, always was and still remains not self-promotion but a desire to present Lisp code so that it didn't seem cumbersome, old-fashioned, or cryptic (and, thankfully, the language provides all possibilities to tune its surface look to your preferences). However, as it bugged so many people, including the reviewers, for the new edition, we have come to a compromise to use all RUTILS code only qualified with the rtl prefix so that it was apparent. Besides, I have changed some of the minor purely convenience abbreviations to their standard counterparts (like returning funcall instead of call).

Finally, the change that I regret the most, but understand that it was inevitable, is the change of title and the new cover, which is in standard Apress style. However, they have preserved the Draco tree in the top right corner. And it's like a window through which you can glance at the original book :)  


So, that is an update on the status of the book.

For those who were waiting for the Apress release to come out, it's your chance to get it. The price is quite affordable. Basically, the same as the one I asked for (individual shipping via post is a huge expense).

And for those who have already gotten the original version of the book, all the major changes and fixes are listed in the post. Please, take notice if you had any issues.

I hope the book turns out to be useful to the Lisp community and serves both Lisp old-timers and newcomers.  

How can I send large arrays through ports?

via Elm - Latest posts by @Warry Maxime on Tue, 29 Dec 2020 14:24:54 GMT

right, I forgot that this changed. my use case dated from the 0.17 era o som’thin’. my bad !

How can I send large arrays through ports?

via Elm - Latest posts by @rupert Rupert Smith on Tue, 29 Dec 2020 12:03:29 GMT

It may also be worth pointing out that an Elm Array is not implemented as a plain JS Array.

An Elm Array is a functional data structure which is immutable. To avoid copying the entire array on every Array.set, it is actually structured as a tree (with a high branching factor). This means that updates to the array can alter just one branch of the tree, but much of the tree can share the same memory as the original.

So when you pass a JS array into a port and decode it as an Elm array, it won’t simply pass through unchanged. The JS array will be restructured into an Elm array.

Just thought you might like to know in case you were thinking that using an array would carry zero performance cost.

Say hello to Elm Designer 0.1—A Elm UI code generator

via Elm - Latest posts by @eimfach Robin G. on Tue, 29 Dec 2020 10:39:32 GMT

Holy moly, nice work for sure ! Can‘t wait for more updates :slight_smile:

How to write fuzz tests for a function which generates a dictionary?

via Elm - Latest posts by @mgold on Tue, 29 Dec 2020 05:44:03 GMT

Let’s take a step back. Why do you want to fuzz test this function? Unit testing is one of those things that you can find a lot of opinions about on the internet. But as long as you are satisfied that your code is correct, then you are testing well. So maybe start with, what’s the bug surface, what bugs do you want to show are not present in your code?

I’m worried about many repeated words. Perhaps something like this: (I have not compiled these tests; some small tweaks may be necessary)

fuzz (Fuzz.intRange 0 1000) "counts repeated words" <| \i ->
  List.repeat i "barnacles" |> Main.wordsDict |> Expect.equal [Dict.fromList [("barnacles", i)]]

This should give you confidence that you can count large numbers of repetitions, BUT only when there are no other words present and and the word is "barnacles". You could also map over List.range 0 10 and make unit tests for those cases, instead of the fuzz test.

I’m worried about certain strings being treated specially. I’m usually not, if I can look at the code and see that it’s not looking at lengths, prefixes, a word list, etc., and doing nefarious things in those cases. You could write a fuzz test that takes in random strings, or a randoms string to use instead of "barnacles".

But if I’m making a data structure that treats strings generically then… you can use the type system. Why not make the signature wordsDict : List comparable -> List (Dict comparable Int)? By making the function more generic, the compiler will reject any attempts to say, not count the empty string. (Unless that’s desired behavior, in which case, write a unit test.)

I’m worried about counting up all the words. One of the great things about fuzz tests is that you don’t have to compute the output value of the function under test, only some invariant that will be true about it. Let’s test that the length of the input list will equal the sum of the values of the dictionary.

-- use a small word list to ensure duplicates
myWords = ["barnacles", "turtles", "whales", "sharks"]

-- effective Elm programming involves combining simple functions together
listFrom : List a -> Fuzz.Fuzzer (List a)
listFrom words = words |> List.map Fuzz.constant |> Fuzz.oneOf |> Fuzz.list

fuzz (listFrom myWords) "length of input = sum of values of output" <| \input ->
  input |> Main.wordsDict |> Dict.values |> List.sum |> Expect.equal (List.length input)

You can write a similar test to check that all values are positive.

How can I send large arrays through ports?

via Elm - Latest posts by @noise-machines Thomas Bailey on Tue, 29 Dec 2020 00:19:22 GMT

Hi everyone!

Thanks for your help – I’ve got it working now.

I had a Debug.log first thing in my main function that wasn’t getting printed before the error happened, so I assumed the problem was as the array crossed the border into Elm. But after reducing my Elm code down, it looks like the actual issue was somewhere else.

Also, good to know that there’s a difference between Arrays and Lists! I think Arrays are better for my use case since I need random access.

Thanks again!

Custom path for elm tests fails

via Elm - Latest posts by @system system on Mon, 28 Dec 2020 23:58:49 GMT

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.

Test-only values

via Elm - Latest posts by @opvasger Asger Nielsen on Mon, 28 Dec 2020 23:49:10 GMT

I’ve worked around this situation once or twice before - I used this strategy, based on your example:

module Role exposing (Role, adminToBool, userToBool)

type Role = Admin | User

adminToBool: (Role -> Bool) -> Bool

userToBool : (Role -> Bool) -> Bool

Say hello to Elm Designer 0.1—A Elm UI code generator

via Elm - Latest posts by @gampleman Jakub Hampl on Mon, 28 Dec 2020 19:48:19 GMT

Very cool and I’m very happy you decided to take this on. I literally started working on something similar about a year back, but then realised I didn’t have time to actually work on it.

It looks really nice. I’m hoping there will be some abstraction features in the future.

Feedback on Animation Utils

via Elm - Latest posts by @supermario Mario Rogic on Mon, 28 Dec 2020 17:35:28 GMT

This looks really cool @andrewMacmurray! Love the elm-ui helpers. Planning to try it out on some looping animations with elm-ui this week!

Say hello to Elm Designer 0.1—A Elm UI code generator

via Elm - Latest posts by @passiomatic Andrea Peltrin on Mon, 28 Dec 2020 17:03:31 GMT

After a lot of work I’m excited to introduce you the first release of Elm Designer, a Elm UI code generator.

Elm Designer lets you build visually your page design and generates the necessary Elm UI code for you: simply drag and drop elements from the library in the document tree and style theme accordingly to your needs. You can them copy code from the Code tab.

I believe it is a great way to approach Elm UI, do some experiments or automate the creation of boring code.

Download

Elm Designer is distributed as an Electron app. Right now there’s a macOS binary available to download and you can run Elm Designer sources on Windows and Linux systems via CLI. Please take a look at the repo README for more information.

Version 0.1 goals

Given that it is a 0.1 version there’s a lot work yet to be done, however it is already usable. Right now Elm Designer can:

  • Create and transform simple designs into Elm code
  • Auto-save designs into browser localStorage
  • Cover Elm UI row , column , textColumn layout primitives and most of the form widgets; support padding and spacing; allow fonts formatting with native and external web fonts (thanks to Google Fonts)

Sensible defaults

I’ve integrated several Google Fonts in the app (more are coming!) and gave some reasonable appearance to headings, form fields and other Elm UI elements to make you start quickly.

Thank you

Elm Designer would not exist without these great packages:

  • mdgriffith/elm-ui - Ca va sans dire!
  • miniBill/elm-codec - JSON document encoding and decoding
  • norpan/elm-html5-drag-drop - Drag & drop operations between elements library and document tree
  • zwilias/elm-rosetree - Tree/Zipper types to represent and manipulate the document tree
  • TSFoster/elm-uuid - Gives each node in the document an unique ID
  • the-sett/elm-syntax-dsl - Elm code generation

Finally, a special thank you to all the fine folks on the Elm slack channel who helped me during the last months.

Problem snapping SVG to grid

via Elm - Latest posts by @AlienKevin Kevin Li on Mon, 28 Dec 2020 15:44:50 GMT

Problem

I’m making an SVG font editor where you can drag and drop components to create compound characters. The position and dimension of the component grows/shrinks in the unit size of the grid, but the rendered component doesn’t snap to grid.

Steps to reproduce

  1. Go to the live web app
  2. Click on the “+” button next to “Compound Characters”
  3. Enter an arbitrary letter “c”
  4. Press enter to create a compound character
  5. Drag any characters under “Simple Characters” to the grid editor on the right
  6. In the grid editor, drag the component around. You can see that it is not snapped to grid

Code

Model stores a dictionary of characters of MyChar type. There are two kinds of characters - SimpleChar and CompoundChar. They both contains MyCharRef which stores mainly the dimension (width & height) and position (x & y) of the character. The unit of measurement is percentage so the character can be scaled relative to its parent CompoundChar or the root SVG. A SimpleChar is basically an alias for MyCharRef and a CompoundChar contains a list of MyCharRef as its components in addition to its own information stored in a separate MyCharRef.

type MyChar
    = SimpleChar MyCharRef
    | CompoundChar MyCharRef (List MyCharRef)

type alias MyCharRef =
    { char : Char
    , id : Id
    , dimension : Vec2
    , position : Vec2
    }

The characters are rendered in a square grid of size boxUnits and has a border of width borderUnits round it. The actual size in px of a unit is stored in unitSize.

renderChar renders the character
onDragBy updates the position and dimension of components

My guesses

  • Maybe I messed up the position calculation in the renderChar function?
  • Maybe due to limited accuracy of the percentage unit in svg?

How can I send large arrays through ports?

via Elm - Latest posts by @noise-machines Thomas Bailey on Mon, 28 Dec 2020 14:04:34 GMT

Hi everyone! Thanks for the suggestions. Sounds like there should be a way to do this. I’ll try out some of your suggestions and report back with a small, self-contained example if I still can’t get it to work. Thanks for the help!

How can I send large arrays through ports?

via Elm - Latest posts by @rupert Rupert Smith on Mon, 28 Dec 2020 11:23:20 GMT

Worth noting that you cannot pass Bytes through a port.

How can I send large arrays through ports?

via Elm - Latest posts by @Warry Maxime on Mon, 28 Dec 2020 10:37:33 GMT

Hello,

Elm ports will check the type of every item in your list if you specify the type, and convert js arrays to linked list if you declare a List (whereas Elm Array are plain js arrays). The trick might be to declare your data as Json Value, an Array of Json Values or even using Bytes, then you can arrange the parsing so that it’s suiting your needs. Not an easy task, but that’s what I ended up doing that one time I had to face the same problem.

 newer latest older