Login
You're viewing the sfba.social public feed.

Replies

  • Aug 5, 2026, 1:16 AM

    In the show's afterwords @ramin_hal9001 and I talked briefly about how and whether a #firstOrderLogic #dft #fourier transform program in #acl2 is a #commonLisp (high performance) fourier transform computer program, to which I say the answer is yes with two caveats:

    - First, I picked a bad example because acl2 only has rational numbers (as of 2024, including common lisp single and double floats), however this complicates the meaning of fft / approximation.

    Secondly, I explained stobjs as lisp

    💬 1🔄 1⭐ 0
  • Aug 5, 2026, 1:18 AM

    structs that are also monads and suggested that you would basically just change STOBJ to STRUCT between acl2 and common lisp.
    @ramin_hal9001
    rightly pointed out that this is technically wrong, because a monad (and a generalized von neuman state single threaded object) are extremely restrictive about what is allowed to happen / said to have happened computationally. So the common lisp program would need to enforce a compatable control flow around modifying the struct itself separately.

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 1:18 AM

    i.e. somewhat covered by saying "it's not threadsafe".
    @ramin_hal9001

    * There *is* acl2(r) - a variant of acl2 with a theory of real numbers, though formally dealing with real numbers is this whole big thing - similar to how there is acl2(p) concerning formal proofs and parallelism.

    However I basically meant / prefer to some extent theories of a rational approximation of a dft.

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 1:39 AM

    @screwlisp computing numbers that are not in the set of {integers modulo 2^64} is really difficult. I have always appreciated how Common Lisp and Scheme both show a great deal of respect to the field of numerical computation by providing programmers with a proper numerical tower.

    Re. monads: a struct is a part of a monad, the other part is the binding function that unfreezes the thunk and binds it’s result to an argument of the next thunk. I think the let* binding is a good example of the Identity monad, which is a trivial monad that does nothing but bind variables. You understand how the let* binding can be macro expanded to lambdas, right?

    (let*((a (f1 "hello"))
          (b (f2 "world")))
      (concat a b))

    …can be written as…

    (funcall
        (lambda (a)
          (funcall
              (lambda (b) (concat a b))
              (f2 "world")))
        (f1 "hello"))

    This is an example of how funcall performs the bind operation of the monad. You can introduce a struct or a record type to chain the lambda functions together and evaluate the monad using a function that runs funcall but also performs some other action before it binds the result of the funcall to the next lambda in the chain. Then if you write a macro like monadic-do where you can build up your chain of lambdas in your record types, it looks like an ordinary procedure but with different semantics than ordinary let*. This is essentially what a monad is.

    (monadic-do  'my-stateful-funcall
        (a := f1 "hello")
        (b := t2 "world")
        (concat a b))

    Monads are useful to Haskell because this allows you to express procedures using only the minimal semantics of System-F that Haskell provides to you, and can do so in a way that the type system can absolutely prove to be correct.

    But I don’t see much use for monads in Common Lisp or Scheme because these languages already provide you with procedures, macros, and other means of changing the semantics of your procedures.

    💬 1🔄 1⭐ 0
  • Aug 5, 2026, 5:11 AM

    @ramin_hal9001 I think I said they were von Neumann bottlenecks *like* monads. If we consider this stobj.lisp :
    (in-package "ACL2")

    (defstobj words
    (words-seen :type t :initially ()))

    (defun add-word
    (words word)
    (declare (xargs :stobjs (words)))
    (let ((words
    (if (true-listp (words-seen words))
    (update-words-seen
    (append
    (words-seen words)
    (list word))
    words)
    words)))
    (mv
    words
    (words-seen words))))

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 5:13 AM

    @ramin_hal9001 Whence we can see:

    $ cert.pl ./stobj.lisp

    $ acl2
    ACL2 !>(include-book "stobj")
    <...>
    ACL2 !>(add-word words "hello")
    (<words> ("hello"))
    ACL2 !>(add-word words "world")
    (<words> ("hello" "world"))

    acl2 describes stobjs as taking the draconian approach that stobjs are so syntactically restricted that it is unambiguous that there is only ever one state. In practice, any access to a stobj must return that stobj (i.e. with mv ~ values).

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 5:26 AM

    @ramin_hal9001 A lisp struct:
    CLIM-USER> (defstruct (words (:conc-name wr-))
    (words-seen () :type t))
    WORDS
    CLIM-USER> (defun add-word
    (words word)
    (values
    words
    (setf (wr-words-seen words)
    (append
    (wr-words-seen words)
    (list word)))))
    ADD-WORD
    CLIM-USER> #S(words)
    #S(WORDS :WORDS-SEEN NIL)
    CLIM-USER> (add-word * 'hello)
    #S(WORDS :WORDS-SEEN (HELLO))
    (HELLO)
    CLIM-USER> (add-word * 'world)
    #S(WORDS :WORDS-SEEN (HELLO WORLD))
    (HELLO WORLD)

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 5:28 AM

    @ramin_hal9001 Clearly common lisp does not enforce singlethreadedness in the way acl2 does; however if you use the acl2 code, this will happen incidentally. Translating stobjs to setf and structs, and loop to loop$, lambda to lambda$, apply to apply$, [] format to fmt aren't broad-spectrum automatable because there are differences, but can generally be macroed in a particular project I think.

    💬 3🔄 0⭐ 0
  • 💬 1🔄 1⭐ 0
  • 💬 1🔄 0⭐ 0
  • 💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • Aug 5, 2026, 5:50 AM

    @screwlisp sorry, I’m still trying to figure out the significance of stobjs here. They look to me more like the kind “environment” object used by languages like Prolog or Minikanren when performing unification of forms to statements. Any time a variable matches a value the variable is bound to that value in the environment, if a variable matches a variable, it checks whether there is a relation between those two variables (the “occurs check”) and fails if the relation is circular, or notes in the environment that the variables must be the same value.

    Is that what is going on here?

    Or is the struct some means of collecting thunks to form a procedure?

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 8:46 AM

    @ramin_hal9001 So there isn't a thunk (maybe a macro?). There isn't state - I can't have side-effects in acl2 - except for stobjs, which are deliberately similar to common lisp's structs. So the only notion of a memory structure also carries with it restrictive syntax to make any/all stobjs (~structs) von Neumann bottlenecks. This also makes them suitable for e.g. file io.

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 8:53 AM

    @screwlisp if the stobj isn’t state (or an “environment” if you will), why is the update-words-seen function defined for you after the (defstobj words (words-seen :type t :initially ())) macro evaluates? It seems as though it is intended to be updated, and therefore it functions as a state or as an environment. You say it has something to do with side effects, so is this how you store intermediate values during an ACL2 computation, how you inspect bound variables at certain points in the computation?

    I am just trying to understand how this relates to monads.

    It is also possible that the term “monad” is being overloaded here. Monad has a specific mathematical definition in category theory, but what we are talking about here is first order predicate calculus. So it is entirely possible “monad” has an entirely different meaning in this context.

    💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • Aug 5, 2026, 9:17 AM

    @vnikolov well, I am not sure myself. I know that Category Theory and set theory + FOL try to use different jargon but sometimes they overlap. I know the word “monad” is used in a few different domains, and each meaning is slightly different and very domain specific.

    @screwlisp

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 9:18 AM

    @vnikolov
    Yes, I was being informal in my formal methods.

    @ramin_hal9001
    Originally, there was a special von Neumann bottleneck state object named state (it's still there). My understanding is this sort-of merged with lisp structs. It's worth noting that acl2 is older than ansi cl, and nqthm is from about 1972.

    defstruct in lisp generates a bunch of utility functions by default, but is not exactly the same as defstobj either.

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 9:19 AM

    @vnikolov @ramin_hal9001

    So if you are going to perform io (which you would use a monad for), in acl2 a stobj performs this service because its restrictions make this admissable.

    💬 1🔄 0⭐ 0
  • 💬 1🔄 0⭐ 0
  • Aug 5, 2026, 9:27 AM

    @screwlisp from the term “Von Neumann bottleneck state object,” or “stobj,” I take it that this state object is like the memory bus between some kind of memory (like maybe a dictionary) and the pure ACL2 computation which is a pure function and thus behaves more like the circuitry in a CPU.

    But having never used ACL2 it is hard for me to imagine. If it is anything like Prolog or Minikanren, then I am guessing you can use it to store snapshots of the values of a computation, and this maybe could trigger an event handler of some kind as well, hence it causes IO to happen.

    So I suppose in that sense it could be pretty similar to what Haskell calls the “state monad transformer lifting IO”, the type for which is forall stobj result . StateT stobj IO result where stobj is some arbitrary CL structure with mutable fields.

    That is the most I can infer from the examples and explanations you have provided me so far. Beyond that, I’m just going to have to try it for myself.

    @vnikolov

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 10:16 AM

    @ramin_hal9001
    ACL2 !>:doc stobj
    Parent: PROGRAMMING.

    Single-threaded objects or ``von Neumann bottlenecks''

    In ACL2, a ``single-threaded object'' is a data structure whose use
    is so syntactically restricted that only one instance of the obj
    ...
    There are other functional languages supporting single-threadedness,
    for example Haskell's ``monads'' and Clean's ``uniqueness type
    system''. Of course, ACL2 provides a theorem prover that can prove
    theorems that involve such constructs.

    💬 0🔄 0⭐ 0
  • Aug 5, 2026, 5:53 AM

    @screwlisp @ramin_hal9001 "The great thing about #Lisp is that it has extremely simple syntax"

    ... except, of course, for #CommonLisp which is a complete baroque mess.

    Of course, it's largely a complete baroque mess because reader macros, and reader macros are useful shorthand, but `#$(words)`? Really?

    And noted also that #Clojure has its own baroquery hard-coded into its reader (`#{:a :b [:c @D]}`, anyone?), which is arguably worse, but...

    This might as well be #Perl.

    💬 3🔄 0⭐ 0
  • Aug 5, 2026, 6:07 AM

    “This might as well be Perl

    @simon_brooke ouch, that burns!

    Maybe not quite as bad as Perl, but abuse of #-prefixed self-evaluating forms do tend to make things difficult, don’t they. I prefer ordinary macros to self-evaluating forms.

    @screwlisp

    💬 1🔄 0⭐ 0
  • Aug 5, 2026, 6:13 AM

    @ramin_hal9001 @screwlisp In principle we could unroll all the macros and reader macros and get back to a clean elegant language that beginners could easily understand, appreciate and learn.

    I strongly believe that in #Lisp as well as other languages, the temptation to build arcane and complex notations is, in part, a mechanism of making ourselves seem like wizards by making what we write impenetrable to the uninitiated.

    💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 1🔄 0⭐ 0
  • Aug 5, 2026, 8:35 AM

    @vnikolov @simon_brooke
    I think I understand the confusion ! Sharpsign S is a reader macro (no real relation to macros)
    lispworks.com/documentation/Hy
    . Compare sharpsign o, sharpsign equals, sharpsign sharpsign, sharpsign a...
    #S(words :words-seen (foo bar baz))
    Is short for
    (make-words :words-seen '(foo bar baz))

    People often dis/like some of these. Simon pines for interlisp do-what-I-mean records. My friend Ksaj just hates 1/2 fractions. (/ 1 2) !
    @ramin_hal9001 @D

    💬 3🔄 0⭐ 0
  • Aug 5, 2026, 8:40 AM

    The meaning of reader macros, imagine you wrote a dispatch function in lisp like this:
    (defun my-reader-thing (stream char &optional n) (declare (ignore char n) (read stream t nil t))
    It goes into the readtable with set-dispatch-macro-character . So you are putting your own lisp program into something like #{ in closure for example into the current readtable.
    @vnikolov @simon_brooke @ramin_hal9001 @D

    💬 0🔄 0⭐ 0
  • Aug 5, 2026, 8:43 AM

    @screwlisp @vnikolov @ramin_hal9001 @D and reader macros most certainly are standard #ConmonLisp.

    That's the nature of the language: it provides you with the tools to rewrite itself. Of course, that has been integral to the whole #Lisp project ab initio.

    Reader macros provide shortcuts behind which to hide annoying boiler plate code; they make those familiar with them much more productive. But they also, I believe, make code much more difficult for newcomers to understand.

    💬 1🔄 0⭐ 0
  • 💬 1🔄 1⭐ 0
  • Aug 5, 2026, 11:05 AM

    Yes, this is an important feature¹.

    Another benefit is that consuming some kinds of non-Lisp data is very easy to implement with reader macros.
    As a quick example, reading assumed-to-be-valid JSON (at least in a good majority of cases) only needs one simple and five trivial macros.
    (The ones for open brace and open bracket would use `read-delimited-list', of course.)

    _________
    ¹ Redundant to add, one should know what one is doing, naturally (for sharpsign-dot this includes assigning the correct value to `*read-eval*').

    #CommonLisp

    @pascal_costanza @simon_brooke @screwlisp @ramin_hal9001 @D

    💬 1🔄 2⭐ 1
  • 💬 1🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • Aug 5, 2026, 8:54 AM

    «Sharpsign S»

    S as in "Structure", yes, but the above post had a dollar sign after the sharp sign.

    «#S(words :words-seen '(foo bar baz))
    Is short for
    (make-words :words-seen '(foo bar baz))»

    ... Except that the former is a literal constant, so it only needs to be read, while the latter is a run-time value, which must be in a for-evaluation position.

    [P.S.
    So the single quote must be dropped from the former to match the latter.]

    The same applies to the difference between 1/2 and (/ 1 2), of course.

    @screwlisp @simon_brooke @ramin_hal9001 @D

    💬 1🔄 1⭐ 3
  • 💬 0🔄 0⭐ 0