Path: ...!2.eu.feeder.erje.net!feeder.erje.net!feeds.news.ox.ac.uk!news.ox.ac.uk!nntp-feed.chiark.greenend.org.uk!ewrotcd!.POSTED.chiark.greenend.org.uk!not-for-mail
From: Mark Wooding <markw@distorted.org.uk>
Newsgroups: comp.lang.lisp
Subject: Re: on racket and other Lisps
Date: Wed, 05 Jun 2024 13:33:54 +0100
Message-ID: <86cyov8t71.fsf.markw@stratocaster.distorted.org.uk>
References: <87h6juklf3.fsf@yaxenu.org>
	<bbnepi1ir89f3t7ck6lbspn3uqns10jk56@4ax.com>
	<v335jg$8pci$1@dont-email.me>
	<86ikyv8jp9.fsf.markw@stratocaster.distorted.org.uk>
	<v3drb0$2f0ae$1@dont-email.me> <87zfs55qey.fsf@yaxenu.org>
	<v3e7pf$2kc2t$4@dont-email.me> <87ttic6bkm.fsf@yaxenu.org>
	<v3g98f$30ko4$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: chiark.greenend.org.uk; posting-host="chiark.greenend.org.uk:93.93.131.173";
	logging-data="16140"; mail-complaints-to="abuse@chiark.greenend.org.uk"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
Cancel-Lock: sha1:hbg2mV4AA+p635zwjvEvgXDLt4M=
Originator: markw@stratocaster.unsafe.distorted.org.uk ([172.29.199.9])
Bytes: 5262
Lines: 98

Lawrence D'Oliveiro <ldo@nz.invalid> writes:

> On Sat, 01 Jun 2024 10:23:53 -0300, Julieta Shem wrote:
>
> > What's your definition of homoiconicity?
>
> The AST can be represented in language objects.

That seems like an uninteresting definition.  Any language whose data
objects are /insufficient/ to represent an abstract syntax tree is
clearly too weak to do much of any use.  (Exercise: work out how to
represent trees in traditional Bourne shell.)

My definition, which I gave by implication earlier, is that the language
is /embedded/ in its own data values.  That is, the source code that you
write is interpreted /first/ as data values, and then /those data
values/ are evaluated or compiled according to semantics assigned to
them by the language definition.

Common Lisp is homoiconic by this definition.  Consider:

        (defun fib (n)
          (let ((a 0) (b 1))
            (do ((i (1- (integer-length n)) (1- i)))
                ((minusp i) a)
              (let ((aa (* a a)))
                (psetf a (+ aa (* 2 a b))
                       b (+ aa (* b b))))
              (when (logbitp i n)
                (psetf a (+ a b)
                       b a)))))

This is a list of four elements: two symbols, `defun' and `fib'; and two
lists, `(n)' and `(let ...)'.  If you evaluate or compile this list,
then you get a function named `fib' which computes the Nth Fibonacci
number, given a nonnegative integer N, but that's strictly secondary.

The non-Lisp homoiconic language which springs most immediately to my
mind is Tcl.  Interestingly, Tcl lacks a direct analogy to Lisp's
`quote': Tcl procedures are essentially fexprs, and they always receive
their arguments unevaluated.  A procedure must explicitly evaluate an
argument if that's what it wants.  Complicating things a little, Tcl has
at lest /two/ evaluation schemes for its values: arithmetic evaluation
via `expr', and command evaluation via `eval' or (more commonly)
`uplevel'.

Perhaps the strongest objection to this classification is that Tcl's
only data types are strings and associative arrays: the latter lack a
literal syntax, and the former are too trivial to embed a language into
in an interesting way.  Except that Tcl can reinterpret its strings in
multiple ways.  This used to be in implementation detail for the
commands concerned, but Tcl 8 introduced `dual-ported' variables, which
are converted lazily between the strings which are the apparent values,
and internal formats defined by interpreter extensions.  The most
interesting such interpretation is as a `list'.  Tcl lists are split
into items at whitespace, except where prevented by double quotes or
matching braces.

For example:

        package require math::bignum
        foreach name {bits testbit add mul} {
          namespace import ::math::bignum::$name
        }

        proc fib {n} {
          set n [::math::bignum::fromstr $n]
          set a 0; set b 1
          set w [bits $n]

          for {set i [expr {$w - 1}]} {$i >= 0} {incr i -1} {
            set aa [mul $a $a]
            set ab [mul $a $b]
            set twice_ab [add $ab $ab]
            set a [add $aa $twice_ab]
            set b [add $aa [mul $b $b]]

            if {[testbit $n $i]} {
              set t $a
              set a [add $a $b]
              set b $t
            }
          }
          return [::math::bignum::tostr $a]
        }

This file contains four lists, though the third is empty.  The first has
three elements: `package', `require', and `math::bignum'.  The second
has four elements: `foreach', `name', `bits testbit add mul' (itself a
list of four elements), and `newline import ::math::bignum::$name' (with
some extraneous whitespace elided).

Command evaluation clearly can be seen as acting on Tcl lists.
(Internally, the interpreter actually maintains a compiled
representation of the code, but I don't see that as significant.)
Expression evaluation, somewhat sadly, does not, and isn't homoiconic in
any interesting sense.

-- [mdw]