Homoiconicity.
https://www.expressionsofchange.org/dont-say-homoiconic/
A humorous footnote:
In fact, the original article excludes Lisp as an example of homoiconicity, but only because Lisp had not settled on a single representation in terms of s-expressions at the time of writing: “Finally, LISP is troubled with a dual language problem: an M-language, which is easy to read, and is used externally, and an S-language, with which the LISP processor operates, and which is usable externally only by the hardened initiates. It should be noted here that were the S-language the only LISP language, LISP would be close to being homo-iconic (excluding the machine-language functions).”
Don't Say “Homoiconic” (2018) (expressionsofchange.org)
88 points by dmux on Aug 11, 2019 | hide | past | favorite | 69 comments
I honestly am curious. I've seen a few examples presented for it, but they always seem like bad software engineering to me. Where's an example that does something in a cleaner way than alternatives present in other languages while remaining compatible with local reasoning?
If you don't like it, you can try https://rhombus-lang.org/ that is build on Racket and also has macros but uses a Python-like syntax.
Well, getting the interaction between modules and syntax transformations (macros) right is not an easy task.
"Composable and Compilable Macros: You Want it When?" Matthew Flatt http://dl.acm.org/authorize?24908
That's a perspective. If you're looking for a low-level language, then Scheme isn't it. (Forget iconicity - Scheme is garbage-collected. And supports continuations!)
If you don't program in machine code - which would maximize local reasoning - then you must know the language with the Correct balance of local reasoning and higher-level constructs. Knowing which language that is would add specificity to this discussion...
Pre-Scheme is a statically typed dialect of the Scheme programming language, combining the flexibility of Scheme with the efficiency and low-level machine access of C. The compiler uses type inference, partial evaluation, and other correctness-preserving transformations to compile a subset of Scheme into C with no additional runtime overhead. This makes Pre-Scheme a viable alternative to C for programming virtual machines, operating systems, and embedded systems where the runtime overhead of a complete Scheme implementation is not desirable.
https://ryansuchocki.github.io/microscheme/
Microscheme, or (ms) for short, is a functional programming language for the Arduino, and for Atmel 8-bit AVR microcontrollers in general. Microscheme is a subset of Scheme, in the sense that every valid (ms) program is also a valid Scheme program (with the exception of Arduino hardware-specific primitives). The (ms) compiler performs function inlining, and features an aggressive tree-shaker, eliminating unused top-level definitions. Microscheme has a robust FFI (Foreign Function Interface) meaning that C code may be invoked directly from (ms) programs. Therefore, the power of the existing wealth of Arduino libraries is available within Microscheme.
CRUNCH is an embedded compiler for a statically typed subset of R7RS Scheme, generating C code. The compiler uses type inference to decorate the code with type information without requiring declarations. CRUNCH can be used to translate embedded Scheme code sections, whole programs or multiple source modules into standalone executables or compiled code that can be invoked from Scheme.
The generated C code uses a small runtime-system contained completely in a single C header file. Reference counting is used for managing aggregate data like strings which removes the need for full tracing garbage collection or manual memory management while still having a relatively small overhead.
Since more or less a direct translation of Scheme to C is done, the generated code should run at roughly the same performance as C. No type-checking takes place as the types of all values have been inferred at compile time, and values are not tagged. With the exception of reference counted objects there is no additional runtime overhead and Scheme and C can directly interchange data. This makes CRUNCH very appropriate for writing programs that need a maximum of speed or that are target for constrained environments like deeply embedded systems. The code is portable to all systems that at least have a C compiler.
UNICODE strings are supported and can optionally be disabled for improving performance and reducing code size.
CRUNCH is heavily inspired by PreScheme, the low-level compiler that is originally part of the Scheme48 project. In fact, CRUNCH can be considered a modern reimplementation of PreScheme written in and for use with CHICKEN.
See also:
Crunch – a Scheme compiler with a minimal runtime (more-magic.net)
190 points by sjamaan on Dec 17, 2024 | hide | past | favorite | 72 comments
Assembly makes non-local reasoning mandatory, as any code can update any location in memory without restriction. All memory accesses are global. References need not even be by name - they can be via computed addresses. There are no restrictions in place allowing the structure of the program to provide boundaries on what pieces of code may be understood as units.
Mutation in scheme is possible, via set!, and set-car! and set-cdr!, but it's not recommended. Functional program design side-steps the issue.
see also:
SICP: 3.1.3 The Costs of Introducing Assignment
https://sarabander.github.io/sicp/html/3_002e1.xhtml#g_t3_00...
Coalton is an efficient, statically typed functional programming language that supercharges Common Lisp by taking great ideas from Haskell, Scheme, and OCaml.
https://coalton-lang.github.io/
Not well known, but surely good software engineering adding features. Lisp* is called the Programmable Programming Language for a reason.
pg wrote a treatise on Lisp macros (free download):
https://www.paulgraham.com/onlisp.html
(add to that something about great power - great responsibility and not holding it wrong)
You can abstract everything away. Not like Haskell where laziness accounts for some and typeclasses for some (and often an exponential growth in compile times). No, it property let's you change the language.
I got tired of loops sucking and made this, for example: https://rikspucko.koketteriet.se/bjoli/goof-loop
Chez compiles a project of about 35000 lines (with heavy macro usage) in less than 0.5s on -O2.
Homoiconicity is a fundamental language property, not an algorithm nor an implementation issue. Lisp implemented in Pascal is still homoiconic. C is not homoiconic, whether the compiler is implemented in C or in Pascal, and C cannot be made homoiconic without adding fundamentally new and different constructs to the language definition.
Further sources:
https://wiki.c2.com/?HomoiconicLanguages
https://wiki.c2.com/?HomoiconicExampleInManyProgrammingLangu...
Of course, you can. C is perfectly capable of writing C interpreters and compilers.
> And even if you could, strings + eval alone is not homoiconicity--programs are not manipulated by the compiler as unstructured text strings.
Lisps (typically) don't execute by walking over s-expressions, either. Lisp interpreters and compilers use more sophisticated representations.
Is the standard library part of the language? Would a variant of C that came with an interpreter in the standard library (but no other changes) count as homoiconic?
But the concept is employed in the Meta-Circular Evaluator.
Perhaps see:
4.1.5 Data as Programs
https://sarabander.github.io/sicp/html/4_002e1.xhtml#g_t4_00...
Another striking aspect of the evaluator is that it acts as a bridge between the data objects that are manipulated by our programming language and the programming language itself. Imagine that the evaluator program (implemented in Lisp) is running, and that a user is typing expressions to the evaluator and observing the results. From the perspective of the user, an input expression such as (* x x) is an expression in the programming language, which the evaluator should execute. From the perspective of the evaluator, however, the expression is simply a list (in this case, a list of three symbols: *, x, and x) that is to be manipulated according to a well-defined set of rules.
That the user’s programs are the evaluator’s data need not be a source of confusion. In fact, it is sometimes convenient to ignore this distinction, and to give the user the ability to explicitly evaluate a data object as a Lisp expression, by making eval available for use in programs. Many Lisp dialects provide a primitive eval procedure that takes as arguments an expression and an environment and evaluates the expression relative to the environment.
The difference is this is built in to many Lisps without the need to create a separate interpreter. And thus much more direct. It's definitional.
#include <hc.h>
int main(void) {
/* 1. Symbols: interned, identity-comparable. */
symbol x = #x;
symbol x2 = intern("x");
assert(x == x2); // same identity, not just strcmp
assert(x != #y);
printf("symbol name: %s\n", symbol_name(x)); // -> "x"
/* 2. Code is written in *the same syntax* as code that runs.
* `code{ 1 + 2 }` is a value of type `code` whose printed
* form is literally "1 + 2". No separate DSL. */
code expr = code{ 1 + 2 };
printf("as source: %s\n", code_to_string(expr)); // -> "1 + 2"
printf("evaluates: %ld\n", (long)eval(expr)); // -> 3
/* 3. Build the same AST programmatically; it is structurally
* equal to the literal above. */
code built = code_add(code_int(1), code_int(2));
assert(code_equal(expr, built));
/* 4. Quasiquote: a code template with a hole, written in C syntax.
* `~n` splices the runtime value of n into the form. */
long n = 40;
code tpl = code{ ~n + (1 + 1) };
printf("template: %s\n", code_to_string(tpl)); // -> "40 + (1 + 1)"
printf("evaluates: %ld\n", (long)eval(tpl)); // -> 42
/* 5. A program can rewrite its own code, because code is data.
* Double every integer literal in a form. */
code e2 = code{ (1 + 1) + 2 };
code doubled = map_code(e2, double_int_literals);
printf("rewritten: %s = %ld\n",
code_to_string(doubled), (long)eval(doubled));
// -> "(2 + 2) + 4 = 8"
/* 6. Definitions are code too. Write the definition in C syntax,
* then eval the code value to install it at runtime. */
code square_def = code{
long square(long x) { return x * x; }
};
eval(square_def);
printf("square(7) = %ld\n", (long)eval(code{ square(7) })); // -> 49
/* 7. Macros: compile-time functions from code to code, written
* in the same syntax they transform. */
code swap_macro = code{
macro swap(a, b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
};
eval(swap_macro); // install the macro
eval(code{ long u = 1; });
eval(code{ long v = 2; });
eval(code{ swap(u, v); }); // macro expands, then runs
printf("after swap: u=%ld v=%ld\n",
(long)eval(code{ u }), (long)eval(code{ v })); // -> u=2 v=1
return 0;
}
(include <hc.h>)
(defun int main ((void))
;; 1. Symbols: interned, identity-comparable.
(symbol x #x)
(symbol x2 (intern "x"))
(assert (== x x2)) ; same identity, not just strcmp
(assert (!= x #y))
(printf "symbol name: %s\n" (symbol_name x)) ; -> "x"
;; 2. Code is written in the *same syntax* as code that runs.
;; Now that the whole language is uniform, a plain quote is all
;; it takes: '(+ 1 2) is a `code` value that prints back as
;; "(+ 1 2)".
(code expr '(+ 1 2))
(printf "as source: %s\n" (code_to_string expr)) ; -> "(+ 1 2)"
(printf "evaluates: %ld\n" (long (eval expr))) ; -> 3
;; 3. Build the same AST programmatically; structurally equal.
(code built (code_add (code_int 1) (code_int 2)))
(assert (code_equal expr built))
;; 4. Quasiquote: a template with a hole. ,n splices n's value.
(long n 40)
(code tpl `(+ ,n (+ 1 1)))
(printf "template: %s\n" (code_to_string tpl)) ; -> "(+ 40 (+ 1 1))"
(printf "evaluates: %ld\n" (long (eval tpl))) ; -> 42
;; 5. A program can rewrite its own code. Double every int literal.
(code e2 '(+ (+ 1 1) 2))
(code doubled (map_code e2 double_int_literals))
(printf "rewritten: %s = %ld\n"
(code_to_string doubled) (long (eval doubled)))
; -> "(+ (+ 2 2) 4) = 8"
;; 6. Definitions are code too.
(code square_def '(defun long square ((long x)) (* x x)))
(eval square_def)
(printf "square(7) = %ld\n" (long (eval '(square 7)))) ; -> 49
;; 7. Macros: compile-time code -> code, written in the same
;; syntax they transform.
(code swap_macro '(defmacro swap (a b)
(set a (^ a b))
(set b (^ a b))
(set a (^ a b))))
(eval swap_macro) ; install the macro
(eval '(long u 1))
(eval '(long v 2))
(eval '(swap u v)) ; macroexpands, then runs
(printf "after swap: u=%ld v=%ld\n"
(long (eval 'u)) (long (eval 'v))) ; -> u=2 v=1
(return 0))It's obvious, and the rest of the comment confirms that:
> Would a variant of C that came with an interpreter in the standard library (but no other changes) count as homoiconic?
I already answered this, so this is clearly bad faith trolling/sealioning:
"even if you could, strings + eval alone is not homoiconicity--programs are not manipulated by the compiler as unstructured text strings."
These sorts of shallow complaints can be made of any feature than one is not familiar with, hasn't used, and doesn't know or understand the benefits of. In any case, no one is forcing people to use this language or take advantage of this feature.
P.S. The "response" actually ignores all points made, attacks strawmen, moves the goalposts, and is intellectually dishonest (the original comment was clearly a complaint, and besides it wouldn't matter if some other word like "criticism" or "dissatisfaction" were substituted--my point remains). Again, no one is forcing anyone.
The point is that these things are subjective, and there will never be a programming language that everyone likes the best.
If the term has any meaning, it's about how program source code can be represented and manipulated easily by the user. (And I say 'can' deliberately, because even Lisps still allow you to treat source code as a big flat string, if you want to.)
I don't think homoiconicity is all that much of a useful concept. It's very hard to pin down. Eg C can represent its own source code, too, if a bit clunkily. And Lisps generally don't execute by walking over s-expressions: their internal representation of their own logic typically uses more sophisticated structures (and adding native code compilers to the mix complicates matters further).