Way

There is always a WAY.

.

(defun sum-of-squares(x y &key (a 1) (b 1))
  (+ (* a x x) (* b y y)))

(deftype candidate()
  '(simple-array boolean (*)))

(defmacro get-sieve-function(a b mod-results)
  `(lambda(x y)
     (let* ((n (sum-of-squares x y :a ,a :b ,b))
        (r (mod n 12)))
       (when (and (<= n limit)
          (not (null
            (member r ,mod-results))))
     (setf (aref candidates n)
           (not (aref candidates n)))))))

(defun get-atkin-prime-candidates-map(limit)
  (let* ((lmt (isqrt limit))
         (candidates (make-array
              (1+ limit)
              :initial-element nil))
         (stage1 (get-sieve-function 4 1 '(1 5)))
         (stage2 (get-sieve-function 3 1 '(7)))
         (stage3 (get-sieve-function 3 -1 '(11))))
    (declare (type candidate candidates))
    (declare (optimize (speed 3)))
    (loop for x from 1 to lmt do
      (loop for y from 1 to lmt do
    (progn
      (funcall stage1 x y)
      (funcall stage2 x y)
      (when (> x y)
        (funcall stage3 x y)))))
    candidates))

(defun atkin-sieve-map(candidates)
  (let ((len (length candidates)))
    (loop for i from 1 to (1- len)
      when (aref candidates i)
        do (loop for j from 1
             for n = (* j i i)
             while (< n len)
             do (setf (aref candidates n) nil))))
  (setf (aref candidates 2) T)
  (setf (aref candidates 3) T)
  candidates)

(defun eratosthene-sieve-map(limit)
  (let ((candidates
      (make-array
       (1+ limit) :initial-element T)))
    (declare (type candidate candidates))
    (declare (optimize (speed 3)))
    (progn
      (setf (aref candidates 0) nil)
      (setf (aref candidates 1) nil))
    (loop for i from 2 to limit
      when (aref candidates i)
        do (loop for j from (+ i i) to limit by i
             when (aref candidates j)
               do (setf (aref candidates j) nil)))
    candidates))

;; This is free software released
;; into the public domain.
;;
;; ykm

(defun get-primes(limit
          &key
            (generator :eratosthene))
  (let ((candidates
      (case generator
        (:atkin (atkin-sieve-map
             (get-atkin-prime-candidates-map
              limit)))
        (:eratosthene (eratosthene-sieve-map
               limit))
        (otherwise
         (error "not valid type
(:atkin :eratosthene)")))))
    (declare (type candidate candidates))
    (loop for i from 0 to (1- (length candidates))
      when (aref candidates i)
        collect i)))

(format t "soe: ~d
" (time (length (get-primes 12345678))))

(format t "soa: ~d
" (time (length (get-primes 12345678
                :generator :atkin))))

(defmacro log10 (x)
  `(/ (log ,x) (log 10)))

.

— Me@2022.09.06 03:24:36 PM

.

.

2022.09.06 Tuesday (c) All rights reserved by ACHK

It doesn’t matter

Euler problem 3.1

.

The bad news is: You cannot make people like, love, understand, validate, accept, or be nice to you.

The good news is: It doesn’t matter.

(defmacro sq (x)
  `(* ,x ,x))

(defmacro list-head (lst)
  `(car ,lst))

(defmacro list-tail (lst)
  `(cdr ,lst))

(defmacro last-item (lst)
  `(car (last ,lst)))

(defun good-reverse (lst)
  (labels ((rev (lst acc)
         (if (null lst)
         acc
         (rev
          (cdr lst)
          (cons (car lst) acc)))))
    (rev lst nil)))

(defun prime-sieve-a-list (input-lst)
  (labels ((sieve-iter (go-lst acc-list)
         (if (not go-lst) 
         acc-list        
         (if (> (sq (list-head go-lst))
            (last-item go-lst))

             (append (good-reverse acc-list)
                 go-lst)
             
             (sieve-iter
              (remove-if #'(lambda (x)
                     (=
                      (mod x (list-head go-lst))
                      0))
                 (list-tail go-lst))
              (cons (list-head go-lst)
                acc-list))))))

    (sieve-iter input-lst '())))

(defun range (max &key (min 0) (step 1))
  (loop :for n :from min :below max :by step
    collect n))

(defmacro prime-sieve (n)
  `(prime-sieve-a-list (cons 2 (range (1+ ,n)
                      :min 3
                      :step 2))))

(time (length (prime-sieve 1234567)))

;; 0.764 seconds of real time
;; 95360

(time (length (prime-sieve 12345678)))

;; 20.128 seconds of real time
;; 809227

— Me@2022-08-27 07:59:30 PM

.

.

2022.08.28 Sunday (c) All rights reserved by ACHK

High level machine language

susam 16 days ago

The first article in this issue of BYTE has a very interesting characterization of Lisp that I have not come across before. I mean, famous quotes like “Lisp is a programmable programming language” by John Foderaro and “The greatest single programming language ever designed” by Alan Kay are often mentioned in articles about Lisp. But in this issue of BYTE, the article “An Overview of LISP” by John Allen at page 10 has something very interesting to say. Excerpt from the article:

“The best description of the LISP programming language is that it is a high level machine language. That is, it shares many of the facets of contemporary machine language –the necessity for attention to detail and the freedom to manipulate the machine’s data and programs without restriction– yet LISP is high level in that the language contains the expressive power and convenience of traditional high level languages. The contradiction is resolvable: a LISP machine is just a higher level machine whose data items are organized differently from the binary bit patterns of most machines, and the LISP programming language is the assembly language for this machine.”

Consider the Emacs Lisp (Elisp) interpreter for example. Elisp interpreter is the Lisp machine. It understands Elisp symbolic expressions, the language of this machine. With enough code written in this machine’s language, we get this fine editing and productivity software known as Emacs!

aap_ 16 days ago

This exactly matches my thoughts. It seems that machine language and LISP are the only two languages (that I know anyway) where code and data are fundamentally the same kind of thing.

— Byte Magazine: LISP (1979)

— Hacker News

.

.

2022.08.22 Monday ACHK

開心 vs 關心

Euler problem 2

.

The older I get, the less I care about what people think about me. Therefore the older I get, the happier I am.

.

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

(defun fib (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        ((> n 1) (+ (fib (- n 2)) (fib (- n 1))))))

(time (fib 40))

;; Evaluation took:
;;   2.648 seconds of real time
;;   2.640080 seconds of total run time
;;   99.70% CPU
;;   9,002,590,370 processor cycles
;;   0 bytes consed
;; 

;; tail resursion

(defun fib-t (n)
  (labels ((fib-iter (m a b)
            (if (= m 0)
            a
            (fib-iter (- m 1) b (+ a b)))))
        (fib-iter n 0 1)))

(time (fib-t 40))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000002 seconds of total run time
;;   100.00% CPU
;;   2,184 processor cycles
;;   0 bytes consed
;;
  
;; infinite list

(defmacro append-last (lst obj)
  `(append ,lst (list ,obj)))

(defun fib-i (n)
  (labels ((fib-iter (m fib-list a b)
            (if (> m (- n 2))
            fib-list
            (fib-iter (1+ m)
                (append-last fib-list (+ a b))
                b
                (+ a b)))))
    (fib-iter 0 '(0 1) 0 1)))

(time (fib-i 40))

;; Evaluation took:
;;   0.000 seconds of real time
;;   0.000008 seconds of total run time 
;;   100.00% CPU
;;   21,960 processor cycles
;;   32,768 bytes consed


(defun filter (fn lst)
  (let ((acc nil))
    (dolist (x lst)
      (let ((val (funcall fn x)))
    (if val (push val acc))))
    (nreverse acc)))

(defmacro filter-list (fn lst)
  `(filter #'(lambda (x)
                (if (funcall ,fn x) x))
            ,lst))

(defmacro filter-2 (fn1 fn2 lst)
  `(filter-list #'(lambda (x)
                    (if (and
                    (funcall ,fn1 x)
                    (funcall ,fn2 x))
                    x))
                ,lst))

(reduce #'+ (filter-2 #'evenp
              #'(lambda (x) (< x 4000000))
              (fib-i 100)))

; 4613732

— Me@2022-08-07 12:34:19 PM

.

.

2022.08.09 Tuesday (c) All rights reserved by ACHK

Mega Man Zero 3

Euler problem 1

.

(proclaim '(optimize speed))

(reduce #'+ '(1 2 3 4))

; 10

(loop :for n :below 10 :collect n)

; (0 1 2 3 4 5 6 7 8 9)

(describe :below)

(defun range (max &key (min 0) (step 1))
   (loop :for n :from min :below max :by step
      collect n))
      
(- (+ (* 3 (reduce #'+ (range 334 :min 1 :step 1)))
      (* 5 (reduce #'+ (range 200 :min 1 :step 1))))
   (* 15 (reduce #'+ (range 67 :min 1 :step 1))))
   
; 233168

(defun sum-1-n (n)
  (/ (* n (+ n 1)) 2))
  
(- (+ (* 3 (sum-1-n 333))
      (* 5 (sum-1-n 199)))
   (* 15 (sum-1-n 66)))
   
; 233168

— Me@2022-08-01 03:29:01 PM

.

.

2022.08.01 Monday (c) All rights reserved by ACHK

Common Lisp Reloaded

; sudo apt-get install sbcl

; sudo apt-get install slime

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(setq inferior-lisp-program "sbcl")

(defun load-slime-with-correct-buffer-position ()

  (save-excursion (slime))
     
 
  (delete-other-windows) 
) 

(defun prelude-start-slime ()
  (unless (slime-connected-p)
    (load-slime-with-correct-buffer-position)))

(add-hook 'slime-mode-hook 'prelude-start-slime)

(set-register ?f '(file . "/path_to/lisp_file.lisp"))

— Me@2022-07-23 05:20:32 PM

.

.

2022.07.23 Saturday (c) All rights reserved by ACHK

Common Lisp vs Racket

flavio81 11 months ago [-]

The author, a famous and well-liked lisper, is not considering portability features. CL is an ANSI standard and code often runs with no changes in many distinct CL implementations/compilers/interpreters.

Also, related to that point: There are many different CL implementations out there that satisfy different use cases, like for example JVM deployment (ABCL), embedded systems (ECL), speed(SBCL), fast compile times (Clozure), pro-level support (LispWorks, ACL), etc. So the same code has a huge amount of options for deployment. It really makes Common Lisp be “write once, run anywhere”.

Then speed is also never mentioned. Lisp can be seriously fast; under SBCL it is generally 0.3x to 1x C speed; LispWorks might be faster, and there’s a PDF out there called “How to make Lisp go faster than C”, so that should give an idea of Lisp speed potential.

CL wasn’t created by philosophing about what a programming language should be for many years; CL was basically created by merging Lisps that were already proven in the industry (Maclisp, Zetalisp, etc), already proven to be good for AI, heavy computation, symbolic computation, launching rockets, writing full operating systems, etc.

CL is a “you want it, you got it” programming language. You want to circumvent the garbage collector? Need to use GOTOs for a particular function? Want to produce better assembly out? Need side effects? Multiple inheritance? Want to write an OS? CL will deliver the goods.

In short, I would guess that from a computer scientist or reseacher point of view, Racket is certainly more attactive, but for the engineer or start-up owner that wants to have killer production systems done in short time, or to create really complex, innovative systems that can be deployed to the real world, Common Lisp ought to be the weapon of choice!

— Why I haven’t jumped ship from Common Lisp to Racket just yet

— Hacker News

.

.

2022.07.13 Wednesday ACHK

Lisp macros 3

Power

Macros are one of the things that make Lisp so extensible, because they let you transform arbitrary code into other arbitrary code. This is true for macros in languages like C too, but Common Lisp macros are different because they’re part of the language.

In C you have a layer of macros on top, written in a preprocessor macro language. The macro layer and the language layer are separate from each other, with the macro layer providing one one extra level of abstractive power (which, don’t get me wrong, is certainly useful).

In Common Lisp, you write macros in Common Lisp itself. You can then use those macros to write functions, and use those functions to write more macros. Instead of two stratified layers it’s a feedback loop of abstractive power.

— A Road to Common Lisp

— Steve Losh

.

.

2022.05.22 Sunday ACHK

The Lisp debugger

oo101 7 days ago [-]

There are a few ways in which the shared objects method you suggest does not match the full power of Lisp debugging.

First of all, when a C program crashes, it just crashes. There is no REPL. There is only a core dump. So any live-debugging you plan to do is after the fact. After you have seen a crash, you would now begin to prepare for the next crash by launching your process via GDB or restarting your process and attaching a GDB to it. Whether a similar crash would occur again or not or when it would occur again depends on the nature of the bug. Now contrast this with Lisp debugging when your program crashes, it stops there and offers you an REPL to interact with the program right then. There is no need to wait for the next crash.

Secondly, when you debug with GDB, you would be dealing with syntaxes: The syntax of C that we are so familiar with. The GDB syntax to investigate the problem that we may be less familiar with. When the Lisp debugger offers the REPL to you, you are working with Lisp again. Your compiler, debugger, program, etc. all are part of the same unified environment where you just execute Lisp code to debug your issue.

Finally, putting your code in shared objects and reloading them requires you to go through the complete write-build-test-debug cycle. And then what do you do if your shared object itself crashes? With Lisp you skip the write-build-test part when all you want to do is debug an error. You jump straight to the debug part of the cycle and begin investigating the runtime state. And it works the same in a uniform manner whether your main program crashes or a dependency crashes.

— A Road to Common Lisp

— Hacker News

.

.

2022.05.05 Thursday ACHK

C and Lisp

numeromancer on Jan 25, 2010 [-]

In every art there is a dichotomy between the practical and the theoretical, and each has their fundamentals. In Comp. Sci., those two sets of fundamentals are these: sets of machine instructions, which come in several varieties; and lambda calculus, or one of the equivalent (by Church’s Thesis) formal systems. C and Lisp are similar in that they represent the first steps in each case to reach the other: C is a level above machine code, providing some abstraction and portability to the use of machine code, the fundamental elements of practical computing; lisp is a level above lambda calculus, providing a practical system for using functions, the fundamental elements of theoretical computing.

In short, mastery of C is concomitant with the ability to measure the cost of computation (sometimes, regardless of the value of it); mastery of Lisp is concomitant with the ability to measure the value of computation (sometimes, regardless of the cost).

Since C and Lisp lie on opposite borders of the universe of computation, knowing both will allow you to better measure the scope of that universe.

— Ask HN: Why does learning lisp make you a better C-programmer?

— Hacker News

.

.

2022.04.07 Thursday ACHK

DO

While DOLIST and DOTIMES are convenient and easy to use, they aren’t flexible enough to use for all loops. For instance, what if you want to step multiple variables in parallel?

(do (variable-definition*)
    (end-test-form result-form*)
  statement*)

— Practical Common Lisp

— Peter Seibel

.

(defun split-if (fn lst)
  (let ((acc nil))
    (do ((src lst (cdr src)))
        ((or (null src) (funcall fn (car src)))
         (values (nreverse acc) src))
      (push (car src) acc))))


>(split-if #'(lambda (x) (> x 4)) '(1 2 3 4 5 6 7 8 9 10))

(1 2 3 4)
(5 6 7 8 9 10)

— p.50

— On Lisp

— Paul Graham

.

Exercise 4.5

Implement the function split-if without using the macro do.

— Me@2019-01-30 09:58:30 PM

.

.

2019.01.30 Wednesday ACHK

duplicate

If (member o l) finds o in the list l, it also returns the cdr of l beginning with o. This return value can be used, for example, to test for duplication. If o is duplicated in l, then it will also be found in the cdr of the list returned by member. This idiom is embodied in the next utility, duplicate:

>(duplicate ’a ’(a b c a d))
(A D)

(defun duplicate (obj lst &key (test #’eql))
    (member obj (cdr (member obj lst :test test))
            :test test))

— p.51

— On Lisp

— Paul Graham

.

Exercise 4.4

Without using the existing function member, define duplicate as in

>(duplicate ’a ’(a b c a d))
(A D)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

— This answer is my guess. —


(defun my-member (obj lst)
    (cond ((not lst) NIL)
          ((eq obj (car lst)) lst)
          (t (my-member obj (cdr lst)))))

— This answer is my guess. —

— Me@2019-01-21 06:34:46 AM

.

.

2019.01.21 Monday (c) All rights reserved by ACHK

Equality Predicates

6.3. Equality Predicates

Common Lisp provides a spectrum of predicates for testing for equality of two objects: eq (the most specific), eql, equal, and equalp (the most general).

eq and equal have the meanings traditional in Lisp.

eql was added because it is frequently needed, and equalp was added primarily in order to have a version of equal that would ignore type differences when comparing numbers and case differences when comparing characters.

If two objects satisfy any one of these equality predicates, then they also satisfy all those that are more general.

.

[Function]
eq x y

(eq x y) is true if and only if x and y are the same identical object. (Implementationally, x and y are usually eq if and only if they address the same identical memory location.)

.

The predicate eql is the same as eq, except that if the arguments are characters or numbers of the same type then their values are compared. Thus eql tells whether two objects are conceptually the same, whereas eq tells whether two objects are implementationally identical. It is for this reason that eql, not eq, is the default comparison predicate for the sequence functions defined in chapter 14.

.

[Function]
eql x y

The eql predicate is true if its arguments are eq, or if they are numbers of the same type with the same value, or if they are character objects that represent the same character.

.

[Function]
equal x y

The equal predicate is true if its arguments are structurally similar (isomorphic) objects. A rough rule of thumb is that two objects are equal if and only if their printed representations are the same.

Numbers and characters are compared as for eql. Symbols are compared as for eq. This method of comparing symbols can violate the rule of thumb for equal and printed representations, but only in the infrequently occurring case of two distinct symbols with the same print name.

.

[Function]
equalp x y

Two objects are equalp if they are equal; if they are characters and satisfy char-equal, which ignores alphabetic case and certain other attributes of characters; if they are numbers and have the same numerical value, even if they are of different types; or if they have components that are all equalp.

— Common Lisp the Language, 2nd Edition

— Guy L. Steele Jr.

.

Conrad’s Rule of Thumb for Comparing Stuff:

1. Use eq to compare symbols

2. Use equal for everything else

— Land of Lisp, p.63

— Conrad Barski, M. D.

.

.

2019.01.16 Wednesday ACHK

Clasp

Overview

Clasp is a new Common Lisp implementation that seamlessly interoperates with C++ libraries and programs using LLVM for compilation to native code. This allows Clasp to take advantage of a vast array of preexisting libraries and programs, such as out of the scientific computing ecosystem. Embedding them in a Common Lisp environment allows you to make use of rapid prototyping, incremental development, and other capabilities that make it a powerful language.

— Clasp README.md

.

I followed the official instructions to build Clasp:

d_2019_01_04__12_06_48_pm_

The building process had been going on for about an hour; and then I got this error:

d_2019_01_04__17_53_17_pm_

d_2019_01_04__23_07_39_pm_

— Me@2019-01-04 10:11:43 PM

.

.

2019.01.04 Friday (c) All rights reserved by ACHK

Build cross-compiled ECL for Android, 3

EQL5-Android | Common Lisp for Android App Development 2018

.

d_2018_12_19__22_56_00_PM_

After successfully running the command ./1-make-ecl-host.sh, when I tried to run the command ./2-make-ecl-android.sh, I got the following errors:

d_2018_12_29__23_30_22_PM_

— Me@2018-12-29 11:21:46 PM

.

.

2018.12.30 Sunday (c) All rights reserved by ACHK

Build cross-compiled ECL for Android, 2

EQL5-Android | Common Lisp for Android App Development 2018

.

The step 2 is to “build cross-compiled ECL for Android”. It should have been straightforward to follow the instructions in the README page of the EQL5-Android project.

d_2018_12_19__22_56_00_PM_

However, when trying to run the command ./1-make-ecl-host.sh, I got the following error messages:

d_2018_12_19__23_11_14_PM_

The error was caused by the fact that my Ubuntu 18.04’s 64-bit gcc toolchain could not compile any source code to create 32-bit executables.

The solution is to run the following command to install the 32-bit gcc toolchain first:

sudo apt-get install g++-multilib libc6-dev-i386

— Me@2018-12-25 09:51:02 PM

.

.

2018.12.25 Tuesday (c) All rights reserved by ACHK

Build cross-compiled ECL for Android

EQL5-Android | Common Lisp for Android App Development 2018

.

The step 2 is to “build cross-compiled ECL for Android”. It should have been straightforward to follow the instructions in the README page of the EQL5-Android project.

d_2018_12_19__22_56_00_PM_

However, when trying to run the command ./1-make-ecl-host.sh, I got the following error messages:

d_2018_12_19__23_11_14_PM_

A more serious problem was that I could not even locate the error log file config.log.

.

Another abnormality was that while the process claimed that it was

Creating directory 'build',

the directory build was actually not created at all.

So I manually created that directory before running the command ./1-make-ecl-host.sh again. Only then, I could find the error log file config.log in the build directory, after the failure of the compilation.

— Me@2018-12-19 10:50:31 PM

.

.

2018.12.19 Wednesday (c) All rights reserved by ACHK

The Android NDK Tools

EQL5-Android | Common Lisp for Android App Development 2018

.

After installing the Android SDK Tools by installing Android Studio, originally, you would be able to install the Android NDK through Android Studio’s SDK Manager.

d_2018_12_16__17_27_49_PM_

However, since EQL5-Android requires an old version of the NDK (version 10e), you have to download the NDK from the Android’s official NDK webpage.

d_2018_12_16__16_22_31_PM_

In Ubuntu, move the file android-ndk-r10e-linux-x86_64.zip to the same location as the Android SDK and then unzip it.

— Me@2018-12-16 09:25:10 PM

.

.

2018.12.16 Sunday (c) All rights reserved by ACHK

The Android SDK Tools

EQL5-Android | Common Lisp for Android App Development 2018

.

After installing Qt, check whether its version is 5.9 or later.

d_2018_12_12__14_28_48_PM_

If so, install the Android SDK Tools by installing Android Studio.

If you use Ubuntu 18.04 or later, you can use the snap command to install Android Studio.

d_2018_12_12__22_11_20_PM_

Besides installing Android Studio, it also automatically updates Android Studio regularly.

— Me@2018-12-12 02:21:45 PM

.

.

2018.12.12 Wednesday (c) All rights reserved by ACHK