Re: on racket and other Lisps

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]